IEOR 165 Discussion 6: Support Vector Machines¶
In this discussion we will take a look at two examples of using support vector machines (SVMs) for analyzing real world data sets. We will first consider a simple two dimensional example using NFL field goal data and then we will then analyze a famous data set (the MNIST data set), to see if we can use SVMs to identify numbers from hand written characters.
Before we begin let's review the theoretical foundations of SVMs. Over the majority of this course we have been looking at problems of regression , that is problems where we are interested in estimating a continuous relationship from or data (suc as a likelihood function or linear model). However, SVMs are designed to answer questions of classification (sometimes reffered to as questions of detection), in which we are interested in finding a discrete relationship in our data.
In the abstract setting we consider (just as with linear models) that our data comes in the form of $(x,y)$, however where before we assumed $y \in \mathbb{R}$ we will now assume that $y$ can belong to one of two classes $y \in \{-1,1\}$. When computing a linear SVM we are interested in finding a model of the form: $$y_i = \text{sign}(\beta^T x_i + \beta_0)\epsilon_i $$
Where $\epsilon$ is some i.i.d noise such that $\epsilon_i \in \{-1,1\}$. In words, we assume that the data is asigned a vlue of $-1$ or $1$ depending on what side of a hyperplane it is, but with some probability the sign of the label may be flipped which makes it difficult to infer the true value. As described in lecture we want to find the value of $\beta$ which creates the greatest separation between the inequalities: $$\beta^T x + \beta_0 \geq 1 $$ $$\beta^T x + \beta_0 \leq 1 $$
This is equivalent to finding the values of $\beta$ which cause the greatest separation between the data and the linear function $\beta^T x + \beta_0 = 0$. In the classification community the distance between the closest data point and this line is called the margin of the classifier, and hence SVMs are referred to as maximum margin estimators. In general the optimization problem we need to solve for fitting a linear SVM is given by the from: $$ \min_\beta\{ \|\beta\|_2^2 - \lambda\sum_{i=1}^n u_i : y_i(\beta^Tx_i + \beta_0) \geq 1 - u_i \quad \forall i = 1,...,n\}$$
Forutnately, solving this optimization problem can be done using specialized software packages (which in fact often solve the dual form). In this discussion we will focus on how we can implement this sort of classifier to analyze real world data.
Example 1: Predicting Success of Field Goal Kick¶
Consider the following data set of all field goal attempts in the 2003 season of the NFL.
import pandas as pd
nfl_data = pd.read_excel('nfl_kick_data.xlsx')
nfl_data.iloc[:20,:]
Suppose we wanted to construct a linear SVM model to analyze this data, what should be our predictors and what should be our lables?
One option is to predict the success of each kick based on which week of the season the attempt was performed and how many yards the kick was attempted for. As a linear SVM model this would look like: $$\text{success}_i = \text{sign}(\beta_1 \text{yards}_i + \beta_2\text{week}_i + \beta_0)\epsilon_i $$
Before we begin our analysis we need to process our data so that it fits the SVM paradigm, this means to first ensure that our labels are $\{-1,1\}$. We note that Success seems to be $\{0,1\}$ but we can easily transform it by adding a new collumn which we will call $\text{Success_svm} = 2\cdot \text{Success} - 1$, this transforms all 0s to -1s and all 1s remain 1s. In general it is convention to keep successes (or objects of detection) as 1s and failures (or undesireable cases) as -1s. Doing this transformation gives us the following augmented dataset:
nfl_data['Success_svm'] = 2*nfl_data['Success'] -1
nfl_data.iloc[:20,:]
Now we are almost ready to begin our analysis. Recall that models can be sensative to issues of scaling in our data and the values of Yards are seginficantly larger then those of Week. We will normalize Yards and add it as the collumn Yards_norm to ensure we don't have scaling issues.
nfl_data['Yards_norm'] = nfl_data['Yards']/max(nfl_data['Yards'])
nfl_data.iloc[:20,:]
Now let's construct our SVM Model:
from sklearn import svm
import numpy as np
X = nfl_data[['Yards_norm','Week']]
Y = nfl_data['Success_svm']
X = pd.DataFrame.as_matrix(X)
Y = pd.DataFrame.as_matrix(Y)
model = svm.SVC(kernel='linear')
model.fit(X,Y)
We can inspect the results of our model by plotting a scatter plot of the data and seeing where our linear separator lies in the plane.
%matplotlib inline
import matplotlib.pyplot as plt
fig = plt.figure()
beta_vals = model.coef_[0]
print(beta_vals)
print(beta_null)
beta_null = model.intercept_
xx = np.linspace(0.2,.6,1000)
plt.plot(xx, -beta_vals[0]/beta_vals[1]*xx - beta_null/beta_vals[1])
plt.scatter(X[:, 0], X[:, 1], c=Y, alpha=0.8)
plt.autoscale(tight=True)
Example 2: Using SVM to Identify Handwritten Characters from Images (using MNIST data set)¶
In this example we will identify different handwritten numbers using the MNIST (Mixed National Institute of Standards and Technology) data set. MNIST is a famous data set used to calibrate various machine learning and statistical methods to identify numerical characters based on hand written black and white 28x28 pixel images which were provided by high school students employed by the US census beaureaux. Here is what these images look like:
The data we have is the label of the image (which number it is supposed to be) and the shade value of each pixel in the picture. The full training data set for MNIST contains over 60,000 different images but below we have an example of the first 20.
import pandas as pd
mnist_train_data = pd.read_csv('mnist_train.csv',names=range(785))
mnist_train_data.iloc[:20,:]
For this example we will construct an svm model to distinguish the number 3 from the number 7 based on hand written image data. So first lets only take the data labled 3 and 7 from our data set.
#index_vlas = (mnist_train_data.iloc[:,0] == 7) or (mnist_train_data.iloc[:,0] == 3)
data_37 = mnist_train_data[(mnist_train_data[0] == 7) | (mnist_train_data[0] == 3) ]
data_37.iloc[:20,:]
Let us construct and SVM model which will detect wether or not we have an image which corresponds to the number 3. This means we are interested in a model of the form:
$$\text{is 3}_i = \text{sign}(\sum_{j=1}^{784}\text{pixel}_{i,j}\cdot\beta_{j} + \beta_0)\epsilon_i$$Again let us do some pre processing and ensure that our SVM labels are following our paradigm of $\{-1,1\}$ so lets add a new collumn 'is_3' which will be one of the label is 3 and -1 if the label is 7.
data_37['is_3'] = 2*(data_37.iloc[:,0] == 3) - 1
data_37.iloc[:20,:]
Now let's train a linear SVM classifier on this data and see how it performs.
var_names = list(data_37)
X = data_37[var_names[1:-1]]
Y = data_37['is_3']
X = pd.DataFrame.as_matrix(X)
Y = pd.DataFrame.as_matrix(Y)
model = svm.SVC(kernel='linear')
model.fit(X,Y)
print(model.coef_[0])
print(model.intercept_)
To test the predictive power of our model let's see what prediction error it achieves on the testing set.
mnist_test_data = pd.read_csv('mnist_test.csv',names=range(785))
test_37 = mnist_test_data[(mnist_test_data[0] == 7) | (mnist_test_data[0] == 3) ]
test_37['is_3'] = -1*np.ones(len(test_37))
test_37['is_3'].loc[test_37.iloc[:,0] == 3] = 1
X_test = test_37[var_names[1:-1]]
Y_test = test_37['is_3']
X_test = pd.DataFrame.as_matrix(X_test)
Y_test = pd.DataFrame.as_matrix(Y_test)
Y_test = np.around(Y_test)
model.score(X_test,Y_test)
So simply using a linear kernel we were able to product >97% accuracy in destinguishing between hand written number 3's and number 7's. However, we know that prediction accuracy could potentially be improved by considering a different kernel function. Recall that the linear kernel function is given by the dot product $x \cdot x$, and corresponds to simply using the features we have in our data set and separating them by a hyper plane. By using nonlinear kernels we can infer more complicated relationships in our data, since the kernels extract additional features (such as different powers, trigonometric transforms etc.) from our data. This corresponds to projecting our data onto a higher dimensional space and finding a best fitting hyperplane in this new projected space. When performing this operation we need to consider potential for overfitting since we are adding potentially infinite new features to our data set, and we are losing the interpretability of our model since we are not able to retrieve the hyperplane parameters ($\beta$) for the lifted classifier.
Much like in the case of kernel density estimation a commonly used kernel for nonelinear SVMs is the Gaussian or normal kernel given by: $K(x_1,x_2) = \exp(-\gamma (x_1-x_2)^2)$. This sort of kernel heuristically allows us to incorporate all polynomial information about our data since: $$\exp(-\gamma (x_1-x_2)^2) = \sum_{k=0}^\infty \frac{(-\gamma (x_1-x_2)^2)^k}{k!} $$
So essentially by using this kernel it is as if we are extracting an "infinite" amount of features from our data set. Let us train an SVM with this sort of kernel on our data set and test its predictive ability.
model_normal = svm.SVC(kernel='rbf')
model_normal.fit(X,Y)
model_normal.score(X_test,Y_test)
Our prediction score decreased when we implemented a gaussian kernel why could this occur?
One potential reason is over fitting, but note that with this new kernel we have introduced a parameter $\gamma$. Running the model with the default $\gamma$ value may not be the best course of action and in general we would want to use some sort of cross validation for the $\gamma$ to have a truely fair comparisson of our two models.