Now we know how the plot looks in 3 dimension. Now we will try to plot the hyperplane for separating this data set

I have manually drawn the hyperplane in the above diagram. We will try to validate our intuition in this case to make sure what I claim actually happens.

Our kernel function is K(x,y)=(x, y, x2+y2 ). Now we need to plot this hyperplane that separate the points.

If we see the values in the plot generated we can see that the value for the hyper plane will be

• X-axis : -1.5 to 1.5  (length of the plane)
• Y-axis : -1.5 to 1.5  (breadth of the plane)
• Z-axis : .5  (height at which the plane separates red and blue)

Plot a meshgrid with these values and we can see that it matches our claim.

The code to generate the plots have been provided in my github account. Here we have manually plotted the decision boundary. Now we will try to get the same result using the scikit learn svm classifier and validate our results to see if it matches our intuition.

This is the output of using  a linear kernel gives accuracy of 58%. We can see its performance is very bad trying to separate non-linear data set. 

The performance of SVM on this data set using a ‘rbf’ kernel is given below. It has 100 percent classification accuracy which is stunning.

This basically is the projection of the hyper-plane on to the lower dimension. But also remember that this does use the gaussian function as its kernel function not what we defined in the beginning.  Please follow the below link to read up more on gaussian kernels.

This wraps up our little discussion on SVM and how it works. In the next post we will look into another classifier – the logistic regression and hope to understand it better.

Code for the Plots available on my github account: https://github.com/vsuriya93/coding-machine-learning/blob/master/SVM/code.py

Useful Links:

1. Gaussian Kernel : https://www.quora.com/What-is-the-intuition-behind-Gaussian-kernel-in-SVM
2. SVM scikit learn: http://scikit-learn.org/stable/modules/generated/sklearn.svm.SVC.html#sklearn.svm.SVC

Link: https://codingmachinelearning.wordpress.com/2016/07/25/support-vector-machines-kernel-explained/

In this post we will continue from where we previously left off. Now we have generated a toy data set looking like a doughnut where your linear decision boundary does not perform well. Look at the data set below

This is how our data set looks. We will define a kernel for this data set and see how this data can be projected up to a 3-dim surface so that the points can be linearly separable.

Kernel is just a function which takes input as an n-dim vector and gives a n+k dimension vector as output, where k is the number of dimension we have projected the data up

In our case we let k=1. So our kernel takes input as 2 dim (x,y) and projects the data to 3 dim (x,y,z)

We define kernel as follows: K(x,y)=(x, y, x2+y2 )

That is, if we have points (x,y) =(1,2) then K(x,y)=(1,2,5) and so on every point in the data set gets transformed. Now if we visualise the data in 3-dim space we have the following transformation of the data.

This is how the kernel transformation works. In this case we have an intuitive idea of what should be the kernel function. But coming with the best kernel for a given problem is close to impossible. So typically in practise choose the Gaussian or RBF Kernel or the polynomial kernel. Remember kernel is just a mathematical function that projects the data up.

Now once this is done, we can see a clear separation of the data set in the higher dimensional plane, so we can apply SVM to get a linear hyperplane that separates the points. Once we have the hyperplane we can project the plane down to a lower dimension and it will look like circle as we saw in the previous post.

Scikit learn provides opportunity to define your own kernel. But this is rarely used. We can use the default option by setting kernel as non-linear or polynomial.

Code for generating the above plots is provided in my github account. The link for the same is given below

Link: https://github.com/vsuriya93/coding-machine-learning/blob/master/SVM/Kernel_transform.py

In the next post we will pick up from here. Now that we have our data projected up – how to get a large margin classifier here? We will be using scikit for building the classifier and plotting the decision boundary.

To summarize:

• Kernels are mathematical functions
• They project data from n-dim to n+k-dim space
• k tells the number of dimensions to project up
• We can manually define kernels – but this is rarely done

References:

• https://www.cs.cmu.edu/~ggordon/SVMs/new-svms-and-kernels.pdf
• http://www.support-vector.net/icml-tutorial.pdf

Link:  https://codingmachinelearning.wordpress.com/2016/07/13/support-vector-machines-svm/

I ended the last post, by saying if we have a not-linearly separable data set then the linear SVM decision boundary will fail miserably !! So what to do then? To help us solve this problem we have SVMs which can give non linear decision boundary. Hurray! We have a solution! However, before that you need to have a question in your mind.

SVM gives hyper-plane as its decision boundary, then how can it be nonlinear ??
Answer to the above question is – you are right. This is what we are going to deal in this post – SVM Kernels

This was not giving us good results. Now how do get a non-linear decision boundary for the above data set? The answer is to use kernels.

Kernel: This actually is a function that maps the data to a higher dimension where the data is separable

In simple words, the data is not linearly separable in this 2-dimension. So I will project the data up by some number of dimensions using a mapping function. In that dimension plane the data will be separable.

Once we get the hyper plane in the n+k dimensional space – where k is the projection of the data up from n dimensional space we can project the hyper-plane back down again to get a decision boundary that can separate points. 

In very simple terms this is what SVM Kernel does. It projects the data up by k dimensions such that the data points are now separable in the higher dimensional plane.

Some popular choice for kernel functions are:

• Gaussian Kernel: https://en.wikipedia.org/wiki/Gaussian_function
• Polynomial Kernel: https://en.wikipedia.org/wiki/Polynomial_kernel

Recap:

• SVMs are powerful in the sense that they can generate non-linear decision boundaries.
• Kernels help in projecting data to a higher dimensional space where the points can be linearly separated.
• Popular ones are RBF (also called the gaussian) and polynomial

In practise we rarely write our own kernel function. For most practical purposes we use the default Gaussian kernel. Nevertheless we can write our own kernel function and see how it works. We will deal with this in our next post. Till then.. Guten Tag!

Reference:

• http://scikit-learn.org/stable/modules/generated/sklearn.svm.SVC.html#sklearn.svm.SVC
• https://www.quora.com/What-are-Kernels-in-Machine-Learning-and-SVM
• http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-034-artificial-intelligence-fall-2010/lecture-videos/lecture-16-learning-support-vector-machines/

Link: https://codingmachinelearning.wordpress.com/2016/07/05/decision-trees-derivation-demystified/

In this post, we deal with one another awesome classifier, called the Support Vector Machines (SVM). They are called large margin classifiers – you will soon understand why. Here is a problem

You see the red points and blue points in the x-y axis of the plot. Our aim is to come up with a margin or a line, which can help us separate the classes (dots). You have 3 choices in front of you. Which one will you choose ? Obviously the dashed line correct? The reason, intuitively your brain has checked the distance between the two classes and fit a line that has the largest margin of divide between the two classes. This is a very basic understanding of the large margin classifier called the SVM. What it does, is to get a hyperplane separating the two classes such that they have a wide margin between them to allow for generalisation.

SVM derivation and proof is quite mathematically taxing, I will deal with it separately later. In this post we will focus on knowing how to use SVM.

First we will create some data points to understand the way SVM works. If the points are linearly separable, then it is just a simple cakewalk. The above diagram explains it all. What if the points are not linearly separable. For example we have data in the form of doughnut – 2 circles, one inside another. Here a simple linear classifier will not work here.

We again use the scikit-learn package to generate the data set for demonstration purposes. Just by using a linear decision boundary we cannot achieve a good classification. Please see the below image for illustration.

What to do in such situation ? how do we classify the points? How to deal with non linearly separable points?

All these questions will be answered in the later posts, but for now it is enough we understand what actually an SVM does.

Now we will move on to how to use SVM. It is quite simple by using scikit. We need to instantiate an object of SVC class and call fit and method and voila we are done.

We will now see how to fit an SVM for data. Say data is in variable train and labels are stored in variable target. We will have the following command to fit an SVM

Simple enough ? Scikit learn package takes care of how to get the best decision boundary to split the points.

To obtain the prediction on the test set invoke the predict method of the classifier on the test set. The prediction will be returned as output.

There you go, you now know how to fit and SVM to the data. It is quite simple when you are using default parameters.

In the next post, we will see about what is the meaning of a kernel, and  how to get an decision boundary that can separate non linearly distributed points and so on.

Also we need to look up on the parameters of SVC() constructor for tuning the parameters etc, which will be explained further in the next set of posts. Till then bye!!

Note: Code for generating the doughnut-shaped dataset is posted on github

https://github.com/vsuriya93/coding-machine-learning/blob/master/decision-tree/create_dataset.py

References:

• http://scikit-learn.org/stable/modules/generated/sklearn.svm.SVC.html#sklearn.svm.SVC
• https://en.wikipedia.org/wiki/Support_vector_machine

This is the next, fun part of this problem. But before that make sure you have read Kaggle Handwritten Digit Recognition – Part-2

In this post we address the questions of why, what and how. This is going to be exiting. So we had chosen SVM as our choice of classifier. Some may feel why SVM in the first place. I chose SVM because I wanted to!!

What is SVM

We had earlier seen the representation of each instance. It looks like (pixel1,pixel 2,pixel 3,…,pixel 784) and corresponding label. Similarly we have 42000 training instances. Each of this instance is just a point in the 784 dimensional space. To make things clearer, consider a single point, say 1. It is just 1 dimensional. Now the point (1,1) is point in 2 dimensions, represented by (x,y). So on (1,1,1) is in 3 dimension. In the entire 3 dimension (x,y,z) is just a point. The same idea follows when we say that the digit instance is just a point in 784 dimensional space.

Points spread in 3-Dimensional space

Once we get this idea, that all the features add just to the dimension (fondly known as the curse of the dimensionality) we have each point representing an instance in the space. SVM aims to find the largest margin classifier, which helps to divide and classify the points in space. How it is done and the math behind it, I skip.

Large Margin Classifier

Your SVM classifier, (take it from me) will find the largest margin between the points in space. And when a test instance arrives just substitute the values in the equation of the hyperplane to find which class the instance belongs to.

Say for example, 2-D hyperplane is x+2y. Test instance is (2,-2), substitute in the equation we get, 2 + 2 * (-2) = -2 < 0 so it belongs to class 1. If >0 then class 2. This is for 2-Dimension. But our data is in 784 dimension space, so the hyperplane will have 784 variables and quite a bit complex. But all the pain to find it has already been taken care. That is python-scikit.

The scikit, fit function will take care of finding the largest margin classifier, and the hyperplane that splits all the instances in space.

For visualization of the MINST dataset please look up here.

Once the scikit fit is done, we call the scikit predict function which takes care of substitution of the test instance values to obtain the required classification.

Voila, now you have a very rough idea of what is an SVM and what it does.

Why I chose SVM

The answer is quite intuitive. Each of the numbers 0,1,2…,9 are quite distinct from each other. So it makes sense to assume that they will be well spread in space, as we can see it in the MINST visualization. Using a large margin classifier will surely help us to classify the points in space, by maximizing the boundary between the points.

But then, 784 dimensions is really too much.. Dont you feel.. It becomes really tedious and computationally difficult to deal with such high dimensions. And also most of the entries in the matrix (each image is a matrix) is 0. You can see it for yourself, most of the space is just white!! This leads me to the next topic for the next post, Principle Component Analysis (PCA).

We will see about dimensionality reduction in the next few posts.

In this post we have the following objective:

1. To understand the MINST data
2. Obtain a Support Vector Machine Classifier
3. Predict and obtain output

Have you read https://codingmachinelearning.wordpress.com/2015/07/23/kaggle-handwritten-character-digit-recognition-problem-part-1/ before ?

Understanding the MINST  data:

MINST data, contains pixel values of digits. That is, every image is just  a matrix of pixels. For the MINST data, it is of size 28*28.  

The equivalent pixel representation..

These are the representations. This is our 1 instance of number 4. Like this we have many similar entries for 4. Similarly we have a lot many instances for numbers from 0 to 9.

This is out data set.

Support Vector Machine (SVM) Classifier:

I  am not going to go into the details of what,why and how SVM. But for now,  we will work with the SVM classifier. To start off it can be an black box type implementation done in python scikit. Once the data is loaded into scikit (using pandas, or the typical open function), we have the following commands to build the SVM.

clf=SVC()

clf.fit(train,train_labels)

This fit function in scikit, will take care of everything. There is no scary maths or optimization to implement!!

Prediction:

Once you have the test-set for which we need the prediction, we have the following predict function.

output=clf.predict(test_set).

output will contain the final prediction. Voila, you have now built your first digit recognizer. But there is a very long way to go. This is a very good beginning  for us in using SVM.

In my next posts we will go into the details of what is  SVM, how SVM works, when to use and about dimensionality reduction.