Maximum margin classifiers

• Also known as optimal separating hyperplane
• Margin is the distance between hyperplane and closest training data point
• We want to select a hyperplane for which this distance is maximum
• Once we identify optimal separating hyper plane there can be many equidistance training points with the shortest distance from hyperplane
• Such point are called support vectors
  • These points support the hyperplane in a sense that if they are moved slightly optimal hyperplane will also move

Training

• Equation 9.10 ensures that left hand side of equation 9.11 gives perpendicular distance from the hyperplane
• Equation assumes y has two values (+1) and (-1)

Support Vector classifier

• Maximum margin classifier does not work when supporting hyperplane does not exist.
• Support vector classifier relaxes optimization objective to get that work
• Unlike maximum margin classifier this one is less prone to overfit as well
  • The formal one is very sensitive to change in single observation
• Also know as soft margin classifier

• ε variable allows training point to be on wrong side of margin
  • If ε > 0 it is on the wrong side of margin
  • If ε > 1 it is on the wrong side of hyperplane
• Parameter C is the budget that constraints how many points are allowed on wrong side of hyperplane
• C is selected with cross validation and controls bias variance trade off
• Point that lies directly on the margin or on the wrong side of margin for their class are called support vectors
  • Because these points affects the choice of hyperplane
  • And this is the property which makes it robust to outliers
    • LDA calculates mean of all the observation
    • However LR is less sensitivity to outliers
• Computation note – when we try to solve above optimization problem with lagrange multiplier we found that it depends on dot product of training samples
  • This will be very important when we discuss support vector machine in next section
  • Dot product is only with support vector, both while training and while solving [1]

Support vector machine

• Above two classifier does not work when desired decision boundary is not linear

• One solution is to create polynomial features (as we generally do for LR)
• But fundamental problem with this approach is that how many and which terms you should create
• Also creating large number of feature raises computational problem

• For the case of SVM, that fact that it involved only dot product of observation allows us to perform kernel trick.
• Kernel acts as similarity function
• Above equation makes it clear that we are not calculating(and storing) higher order polynomial still taking the advantage of it
• Second one is polynomial kernel and last one is radial kernel
• This video shows visualization of kernel trick

Multiclass SVM

• One vs all and one vs rest is used for multiclass classification using SVM

 Hinge Loss

• Loss is 0 for w*x which are not support vectors
• Look at equation 9.14 and 9.15 above
  • Looking at its property episilon, it relates to hinge loss
  • Yet to check it in SVM lagrange solution though
• In hinge loss also we would predict +1 if w*x > 0 else -1
• Why not keep boundary at 0
  • This can make w a zero to make positive training example right
  • Zero parameter vector would mean while prediction we would always get 0
    • Because prediction is w*x
    • This makes it difficult to assign labels during prediction
  • We keep boundary away from 0 to make zero we don’t get 0 parameter vector

References

[0] : An Introduction to Statistical Learning – http://www-bcf.usc.edu/~gareth/ISL/

[1] : https://towardsdatascience.com/understanding-support-vector-machine-part-2-kernel-trick-mercers-theorem-e1e6848c6c4d

Few Points:

• LR model probability with logistic function
• LDA models probability with multivariate Gaussian function
• LR find maximum likelihood solution
• LDA find maximum a posterior using Bayes’ formula

When classes are well separated

When the classes are well-separated, the parameter estimates for logistic regression are surprisingly unstable. Coefficients may go to infinity. LDA doesn’t suffer from this problem.

LR gets unstable in the case of perfect separation

If there are covariate values that can predict the binary outcome perfectly then the algorithm of logistic regression, i.e. Fisher scoring, does not even converge.

If you are using R or SAS you will get a warning that probabilities of zero and one were computed and that the algorithm has crashed.

This is the extreme case of perfect separation but even if the data are only separated to a great degree and not perfectly, the maximum likelihood estimator might not exist and even if it does exist, the estimates are not reliable.

The resulting fit is not good at all.

Math behind LR

For example suppose y = 0 for x=0 and y=1 for x = 1. To maximize the likelihood of the observed data, the “S”-shaped logistic regression curve has to model h(Θ) as 0 and 1. This will lead β to reach infinite, which causes the instability.

Few terms:

Complete Separation – when x completely predicts both zero and 1

Quasi-Complete separation – when x completely predicts either 0 or 1

When can LDA fail

It can fail if either the between or within covariance matrix(Sigma) is singular but that is a rather rare instance.

In fact, If there is complete or quasi-complete separation then all the better because the discriminant is more likely to be successful.

LDA is popular when we have more than two response classes, because it also provides low-dimensional views of the data.

In the post on LDA, QDA we had said that LDA is generalization of Fisher’s discriminant analysis (which involves project data on lower dimension to that achieves maximum separation).

LDA may result in information loss

The low-dimensional representation has a problem that it can result in loss of information. This is less of a problem when the data are linearly separable but if they are not the loss of information might be substantial and the classifier will perform poorly

Another assumption of LDA that it assumes equal covariance matrix for all classes, in which case we might go for QDA. Blog post on LDA, QDA list more consideration about the same.

References

https://stats.stackexchange.com/questions/188416/discriminant-analysis-vs-logistic-regression#

Click to access separation.pdf

Click to access Classification_HDD.pdf

{In practice it is used more for classification than for regression}

This resemble gaussian mixture models in that you git one gaussian for each class. 
Don't forget one important difference though. LDA is supervised, Mixture models are unsupervised.

Linear Discriminant Analysis (LDA)

In logistic regression (LR), we estimate the posterior probability directly. In LDA we estimate likelihood and then use Bayes theorem. Calculating posterior using bayes theorem is easy in case of classification because hypothesis space is limited.

Equation 2 computes probability of class k given x. This is a posterior instead of just point estimates.

Equation 4 is derived from equation 3 only. Probability(k) would be highest for the class for which Delta(k) will be highest.

LDA estimates mean and variance from data and uses equation 4 for classification.

We also need to estimate π_k, which I think would be n_k/N.

Assumptions made:

• f(x) is normal
• Variance(sigma) is same for all classes

When more than one predictor, we go for multivariate gaussian

Some comparisons

• Compare this with mixture models, where there is a responsibility vector for each sample
  • There labels are not available (unsupervised learning) and hence is solved by EM (Expectation Maximization)
• Compare this with naive bayes, there assumption is each feature is independent
  • Here we have parameter for each (class, feature), there we have parameter for each feature
  • Also here f captures probability of class (k) given x, there after bayes rules we calculate probability of x given class k
  • Hence the name naive bayes
  • Here we have joint distribution (multivariate gaussian, there it is independent distribution for each features)
  • Both LDA and navie bayes try to calculate posterior while logistic regression maximizes likelihood function

Quadratic Descriminant Analysis (QDA)

Unlike LDA, QDA assumes that each class has its own covariance matrix. It is called quadratic because below function is quadratic of x.

When to use LDA, QDA

• This is related to bias variance trade-off
• For p predict and k classes
  • LDA estimates k*p parameters
  • QDA estimates additional k*p*(p+1)/2 parameters
• So LDA has much lower variance and classifier built can suffer from high bias
• LDA should be used when number of training sample are less, because we want to avoid high variance problem
• QDA has high variance, so it should be used when number of training samples are more
  • Another scenario would the case when common covariance matrix among K classes is untenable

A note on Fisher’s Linear Discriminant Analysis

• It is simply LDA in case of two classes.
• We can derive this similarity mathematically.
• In literature we found it from the perspective that it project data on a line which achieves maximum separation
• We can state without loss of generality that LDA also provides low dimensional view on data

Math

• We want to project 2-D data on a line which
  • maximizes the difference between projected mean
  • minimizes within class variance
• Such a direction can be found by maximizing fisher criterion (J)