SVM

SVM are the support vector machines which can be used for classification using a margin.

1.       SVM - Support vector machines is a large margin classifier that tries to classify the data points with largest margins so as to get more robustness.

Ø  Intuition to Logistic Regression:

In logistic regression, the decision boundary is sigmoid (WX) = 0.5 or WX = 0

For y =1 we want our prob to be approx. 1 and for y=0 we want prob to be almost 0

ð  (1/ 1+e^-Wx) = 1             => Wx to be large Wx>>0

ð  (1/ 1+e^-Wx) = 0             => Wx to be small Wx<<0

Instead of these conditions, we impose a more stronger condition that

For y =1, Wx>=1               &             For y=0, Wx<=-1

Ø  Decision Boundary: {x: Wx >=1} U {x: Wx<=-1}

Distance between these hyperplanes defines our margin which is 2/ ||W||

Ø  How margins in SVM are chosen?

We can express any dot product as a product of one vector’s projection onto other and Norm of the other vector i.e.

We need to minimize the objective function:

Minimize C [Cross entropy loss] + ||W||²

For a large C, Cross entropy loss will tend to be zero in order to minimize Loss and objective now is to minimize ||W||

Wx = p ||W|| where p is the projection of x on W

W ⁽ⁱ⁾ x> = 1           =>           p ||W|| >=1      if y_i =1

W ⁽ⁱ⁾ x<= -1           =>           p ||W|| <=-1    if y_i = 0

Now to minimize ||W||, we need p to be maximum or large (projections of each point to the orthogonal vector of our decision boundary) and hence it results in maximum margin classifier.

Ø  What are support vectors in SVM?

The points that are used for calculating the margins or the points which are closest to decision boundary are called support vectors. Min support vectors can be 2.

Bottom Line:  The max-margin hyperplane is completely determined by those {\displaystyle {\vec {x}}_{i}}which lie nearest to it. These {\displaystyle {\vec {x}}_{i}}are called support vectors.

Ø  What are different kinds of SVMs?

Hard Margin Linear SVM

In a training set where the data is linearly separable, and you are using a hard margin (no slack allowed), the support vectors are the points which lie along the supporting hyperplanes (the hyperplanes parallel to the dividing hyperplane at the edges of the margin). All of the support vectors lie exactly on the margin. Regardless of the number of dimensions or size of data set, the number of support vectors could be as little as 2

Soft-Margin Linear SVM

But what if our dataset isn't linearly separable? We introduce soft margin SVM. We no longer require that our data points lie outside the margin, we allow some amount of them to stray over the line into the margin. We use the slack parameter C to control this. (nu in nu-SVM) This gives us a wider margin and greater error on the training dataset, but improves generalization and/or allows us to find a linear separation of data that is not linearly separable.

Now, the number of support vectors depends on how much slack we allow and the distribution of the data. If we allow a large amount of slack, we will have a large number of support vectors. If we allow very little slack, we will have very few support vectors. The accuracy depends on finding the right level of slack for the data being analyzed. Some data it will not be possible to get a high level of accuracy, we must simply find the best fit we can.

Non-Linear SVM

This brings us to non-linear SVM. We are still trying to linearly divide the data, but we are now trying to do it in a higher dimensional space. This is done via a kernel function, which of course has its own set of parameters. When we translate this back to the original feature space, the result is non-linear:

Now, the number of support vectors still depends on how much slack we allow, but it also depends on the complexity of our model. Each twist and turn in the final model in our input space requires one or more support vectors to define. Ultimately, the output of an SVM is the support vectors and an alpha, which in essence is defining how much influence that specific support vector has on the final decision.

Here, accuracy depends on the trade-off between a high-complexity model which may over-fit the data and a large-margin which will incorrectly classify some of the training data in the interest of better generalization. The number of support vectors can range from very few to every single data point if you completely over-fit your data. This tradeoff is controlled via C and through the choice of kernel and kernel parameters.

I assume when you said performance you were referring to accuracy, but I thought I would also speak to performance in terms of computational complexity. In order to test a data point using an SVM model, you need to compute the dot product of each support vector with the test point. Therefore the computational complexity of the model is linear in the number of support vectors. Fewer support vectors means faster classification of test points.

Ø  What is the role of kernel in SVM?

We find the new features from taking Gaussian with some variance

·         l₁, l₂, l₃,…, l_n (new landmarks)  which we will chooses iteratively starting from taking li as the x_i

·         X_i Data Points

In this case l_i’s are found using a new optimization function which takes new features as inputs. Based on the Gaussian value of input x_i and new features f_i, output is calculated.

Parameters:

·         C – Regularization parameter. It is representative of how well u fit the training data. So, higher the value of C, more it fits to data. Sensitive to outliers {C very large implies more overfitting}  

o   Large C: Lower Bias, High Variance

o   Small C: Higher Bias, Low Variance

·         Gamma – Gaussian kernel Variance

o   Large: then features vary smoothly (Higher Bias Lower Variance)

o   Large: then features vary smoothly (Higher Bias Lower Variance)

·         Solver - {‘newton-cg’, ‘lbfgs’, ‘liblinear’, ‘sag’, ‘saga’}

·         Kernel - Gaussian, linear, polynomial, string, chi-square, radial basis

o   If large features then fit linear kernel

o   Gaussian kernel if low dimensional (Scale the feature before using)

Logistic regression vs SVM vs Neural Network

1. Spam Classification when we have n-10,000 features (Words), m: 10- 1000, then

·          use Logistic regression OR

·          SVM without a kernel

2. n-small, M- intermediate (10,000- 50,000)

·          use SVM with Gaussian Kernel

3. n- small, M- large (>50,000)

Create or add more features and go for SVM with linear kernel or Logistic Regression.

Advantages:

·         It works really well with clear margin of separation

·         It is effective in high dimensional spaces.

·         It is effective in cases where number of dimensions is greater than the number of samples.

·         It uses a subset of training points in the decision function (called support vectors), so it is also memory efficient.

Disadvantage:

·         It doesn’t perform well, when we have large data set because the required training time is higher

·         It also doesn’t perform very well, when the data set has more noise i.e. target classes are overlapping

·         SVM doesn’t directly provide probability estimates, these are calculated using an expensive five-fold cross-validation. It is related SVC method of Python scikit-learn library.

Links:

1.       https://www.youtube.com/watch?v=wfKGEzw0tSc&index=1&list=PLpWvmddrSwiHIyxJq0hw_9b8w2j_sWOVe  (Best Explanation)

2.       https://stackoverflow.com/questions/9480605/what-is-the-relation-between-the-number-of-support-vectors-and-training-data-and

3.       https://en.wikipedia.org/wiki/Support_vector_machine (Wikipedia- Mathematical stuff)

4.       https://nlp.stanford.edu/IR-book/html/htmledition/support-vector-machines-the-linearly-separable-case-1.html