In the last post, we saw an English version of linear regression devoid of all mathematics, optimizations blah blah. This post, aims at understanding the mathematical nuances and the beauty of simple gradient descent optimization for obtaining the line of best fit. Just to recap, we have a line of best fit given by linear regression. We claim, that this line captures the trend and pattern in the data. Here is what we are going to do:

• Obtain and understand the data set
• Loading the data set
• Steps in coding the classifier
• Understanding the Bias term in linear regression
• How to define error

Obtain and understand the data set

We will use a simple house price prediction data set – with 2 columns. First column is the area of the house and the second column is the price of the house. In our case, the second column, is the column of interest (also our labels). That means, once I have a trained linear regression model available, given area of a house, I should be able to predict price for it.

Problem:

Given area of the house, we should be able to obtain a prediction price for the same.

Loading the data set

To simplify the loading headache, we will directly use pandas package to help us load the data set (it is plainly a single line code). Pandas will actually load the dataset into memory!! You can refer about pandas here

Steps in coding the classifier

We have the following steps in coding the linear regression classifier: Let X denote the area of the house, and Y denote the house price (labels)

• We have X and Y loaded an ready
• Add a Bias column to X, i.e Add a column of 1’s to X. So our new data matrix will be [colum_of_ones X]
• Define prediction, i.e Y = MX + C, where M is slope and C is intercept (both a floating point numbers!!)
• Define error/cost. We will be using root mean squared error as our cost functions
• Use gradient descent, to find the best values for M and C such that they minimize the error

Don’t worry. We will go through each of these steps in detail. I will also release final version of this code for guidance and checking purposes.

Understanding the Bias term in linear regression

Once we know how to load data, the next step is to add the bias component. Many have this question, why have a bias term? Well I am here to give you an convincing answer. What is our learning objective in linear regression? We need to get the best value for M and C, such that Y = MX + C becomes the line of best fit. Now, see the equation carefully.

Y = M*X + 1*C: This explains the bias term, 1, for each instance.

Say if I don’t have a bias term, and it is zero. Then my equation will be of the form, Y=MX. What is the problem with this? This say that, when X = 0 the Y has to be 0, which imply that the line of best fit has to pass through the origin each time. Got it? This need not always be true, the data need not always be spread around the origin, can be biased. Hence we add the bias term to the network, which can actually help in moving the line of best fit up and down – not constraining it to pass through the origin.

Defining Error in Linear regression

We define error in a very intuitive manner – the simplicity and the ease of it will amaze you. We will:

• Use the difference between the observed (actual) and the predicted value
• Sum the squares of the difference ( squares is a must, otherwise errors may cancel out due to different signs)
• Normalize (divide) by the total number of examples

So the Error Term will be: ∑ Square (| H(x,c) – Y |) / M where

H(x,c) = MX + C and Y is the observed value from our dataset. M is the total number of instances/examples. This is how we define error. Very intuitive right?

Now how do we start the regression? For that you need to wait till the next post that will get you started with random initialization of values for M and C and iteratively converge to the best solution!

Till then, Bye.

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

In this post we will deal with Decision Tree Classifier(DTC). DTC can be simply assumed as a series of if-else questions asked at each decision node. For example if I need to know a given object is a car or not, I will ask a series of questions which can be interpreted as if-else statements. I ask, if the object had 4 tyres. If yes then does it have a box-like structure around it. If yes then does it have a steering-wheel and gear box. If answer to all of these decision questions is yes probably the object is car. Else it may not be a car.

This is a very small example of a decision tree. This is used only for illustration purpose and I hope it drives the message that DTC is nothing but a series of if-else situations at each decision node.

Now we will look into the iris data set and try to implement decision tree classifier algorithm on the same. By implement, most the classifiers have been coded and integrated in scikit sklearn package. We will all we need by using sklearn

Iris data set contains details about different flowers. Based on the features we need to be able to predict the flower type. Please find the description of iris data set here

• First step is to load the iris data set into variables x and y where x contains the data (4 columns) and y contains the target.
• Split the data into train and validation set so that we can see the performance of our model on “previously unseen” instances
• Sepal length,Sepal width, Petal length, Petal width are its features and the targets are setosa (0), Iris virginica(1) and Iris versicolor(2)
• Visualize the data set to see how the points are spread in space

This is the plot we obtain by plotting the first 2 feature points (of sepal length and width). Now we invoke sklearn decision tree classifier to learn from iris data. This simply translates to the following code.

This piece of code, creates an instance of Decision tree classifier and fit method does the fitting of the decision tree. We then invoke predict method to be able to get the prediction for the test-set where our accuracy is close to 90% (on the 30 test instances)

We can also aim to plot the decision surface for the iris data set and see how decision tree classifiers learn rectangular boundaries. The pair wise plots for the iris data set is clearly provided in the sklearn. Link provided at the end of the article.

Our aim here is to perform PCA on the data set, project data on its principle components and reduce data to 2 dimensions. The visualisation of the above task is given below and the code for the same will be made freely available on github.

This is the PCA plot of the data and that now we can focus on obtaining the decision surface of the classifier we have built. Also we can get the tree-type structure for the same using the dot image from sklearn.

We now plot the decision surface for the same.

We can see clearly the rectangular decision boundary learned by our classifier. If a point falls in the blue surface it will be classified as setosa(0) and so on.

Things to remember:

• Decision tree gives rectangular decision boundaries
• It can be thought of as series of if-else questions at each decision node

In the next post we will look into learning SVM and the kind of decision boundary it can generate. Till then bye!!

Code : https://github.com/vsuriya93/coding-machine-learning/tree/master/decision-tree
Sklearn iris visualization: http://scikit-learn.org/stable/auto_examples/tree/plot_iris.html

This post, we will see how to use SVD for reducing dimension. Before that we need to understand the problems associated with PCA so as to appreciate SVD. PCA computes eigenvalues to capture variance. But one cannot compute eigenvalues for non-square matrix.

In SVD we do not have eigenvectors. Instead we have left and right singular vectors and SVD is possible even on non-square matrices. The only bottleneck is the fact that it is a quadratic time algorithm.

The latest thing in NLP is using word vectors for representing word such that the semantics and the context of the word is preserved. The notion of inner product in the vector space triggers the idea of similarity. But if we use one-hot encoding method, computing inner product does not represent similarity. In one hot encoding we represent each word as a vector of 0’s and 1’s where 1 occurs when the word is considered.

For example we have the following 5 words in the dictionary/vocabulary: I, like, motel, hotel, enjoy

The one-hot representation for like will be [0,1,0,0,0] and for enjoy will be [0,0,0,0,1] and so on. Here if we take inner product between hotel and motel which is [0,0,0,1,0] * [0,0,1,0,0] it will tell they are not similar but in reality they are. How to capture this notion. Though we may be solving this problem here, we will use SVD to aid us in this process.

Consider the following 3 sentences in our vocabulary:

1. I like deep learning.
2. I like NLP.
3. I enjoy flying.

We can build a co-occurrence matrix (by taking 1 window context around each word) and to reduce dimension and to capture the word similarity we will use SVD.Code for computing SVD and displaying the plot is also provided in this post.

The “numpy svd” function returns 3 outputs. U, s and v. U contains left singular vectors(need not be a square matrix), s is matrix that contains eigenvalues and v contains the right singular vectors (again, need not be square)

We can decompose the co-occurrence matrix as x=u*s*v . Based on the eigenvalues in s matrix we can reduce dimension by taking k most significant vectors. Thus we can see how SVD can also be used as dimensionality reduction tool.

When we visualise the word vectors we obtained by taking svd of the co-occurrence matrix we get the following output.

We can see that enjoy is closed to like than flying and so on. The dependency is preserved just by choosing the left singular vector and plotting them.

Summary:

• We saw a cool application of SVD in word vector representation.
• SVD is not restricted to square matrices and gives out left and right singular vectors than just eigenvectors
• Using the eigenvalues in the s matrix of u,s,v decomposition and thresholding based on the user’s need we can select first k singular vectors which helps in dimensionality reduction
• SVD is quadratic time algorithm O(N2). On large matrices computational time will increase drastically

Next Post:

In the next series of posts I will be writing about classifiers in general. That is what are the various classifiers we have, and how they behave, what type of decision boundary they represent and so on.

Code for executing the above application is made publicly available on github.Please follow the below link to the code and to the visualization output. Thank you.

Link: https://github.com/vsuriya93/coding-machine-learning/tree/master/SVD

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.