<jupyter_start><jupyter_text>Support Vector MachinesIn the first part of this exercise, you will  build  support vector machines(SVMs) for solving  binary classification problems. You will experiment with yourclassifier on three example 2D datasets. Experimenting with these datasetswill help you gain  intuition into how SVMs work and how to use a Gaussiankernel with SVMs.<jupyter_code>import random
import numpy as np
import matplotlib.pyplot as plt

# This is a bit of magic to make matplotlib figures appear inline in the notebook
# rather than in a new window.

%matplotlib inline
plt.rcParams['figure.figsize'] = (10.0, 8.0) # set default size of plots
plt.rcParams['image.interpolation'] = 'nearest'
plt.rcParams['image.cmap'] = 'gray'

# Some more magic so that the notebook will reload external python modules;
# see http://stackoverflow.com/questions/1907993/autoreload-of-modules-in-ipython

%load_ext autoreload
%autoreload 2<jupyter_output><empty_output><jupyter_text>Data set 1We will begin  with a 2D example dataset which can be separated by alinear boundary.  Inthis dataset, the positions of the positive examples (green circles) and thenegative examples (indicated with red circles) suggest a natural separation indicatedby the gap. However, notice that there is an outlier positive example  onthe far left at about (0.1, 4.1). As part of this exercise, you will also see howthis outlier affects the SVM decision boundary.<jupyter_code>import linear_svm
import utils
from sklearn import preprocessing, metrics
from linear_classifier import LinearSVM_twoclass

############################################################################
#  Part  0: Loading and Visualizing Data                                   #
#  We start the exercise by first loading and visualizing the dataset.     #
#  The following code will load the dataset into your environment and plot #
#  the data.                                                               #
############################################################################

# load ex4data1.mat

X,y = utils.load_mat('data/ex4data1.mat')

utils.plot_twoclass_data(X,y,'x1', 'x2',['neg','pos'])
plt.show()<jupyter_output><empty_output><jupyter_text>The hinge loss function and gradientNow you will implement the hinge loss cost function and its gradient for support vector machines.Complete the **binary\_svm\_loss** function in **linear\_svm.py**  to return the cost and gradient for the hinge loss function. Recall that the hinge loss function is$$ J(\theta) = \frac{1}{2m} \sum_{j=0}^{d} {\theta_j}^2 + \frac{C}{m} \sum_{i=1}^{m} max(0, 1 -y^{(i)}h_\theta(x^{(i)})) $$where $h_{\theta}(x) = \theta^ T x$ with $x_0 = 1$.  $C$ is the penalty factor which measures how much misclassifications are penalized. If $y^{(i)}h_\theta(x^{(i)})) > 1$, then $x^{(i)}$ is correctly classified and the loss associated with that example is zero. If $y^{(i)}h_\theta(x^{(i)})) < 1$, then $x^{(i)}$ is not within the appropriate margin (positive or negative) and the loss associated with that example is greater than zero. The gradient of the hinge lossfunction  is a vector of the same length as $\theta$ where the $j^{th}$ element, $j=0,1,\ldots,d$ is defined as follows:\begin{eqnarray*} \frac{\partial J(\theta)}{\partial \theta_j}  & = &\left \{\begin{array}{l l}\frac{1}{m} \theta_j + \frac{C}{m} \sum_{i=1}^{m} -y^{(i)}x_j^{(i)}& \mbox{ if } y^{(i)}h_\theta(x^{(i)})) < 1\\\frac{1}{m} \theta_j & \mbox{ if } y^{(i)}h_\theta(x^{(i)})) >= 1\\\end{array} \right. \end{eqnarray*}Once you are done, the cell below will call your **binary\_svm\_loss** function with a zero vector $\theta$. You should see that the cost $J$ is 1.0. The gradient of the loss function with respect to an all-zeros $\theta$ vector is also computed and should be $[-0.12956186 -0.00167647]^T$.<jupyter_code>############################################################################
#  Part 1: Hinge loss function and gradient                                #
############################################################################

C = 1
theta = np.zeros((X.shape[1],))

yy = np.ones(y.shape)
yy[y==0] = -1
J,grad = linear_svm.binary_svm_loss(theta,X,yy,C)


print("J = %.4f grad = %s" %(J,grad))<jupyter_output>J = 1.0000 grad = [-0.12956186 -0.00167647]<jupyter_text>Impact of varying CIn this part of the exercise, you will try using different values of the Cparameter with SVMs. Informally, the C parameter is a positive value thatcontrols the penalty for misclassified training examples. A large C parametertells the SVM to try to classify all the examples correctly. C plays a rolesimilar to $\frac{1}{\lambda}$, where $\lambda$ is the regularization parameter that we were usingpreviously for logistic regression.The SVM training function is in **linear\_classifier.py** -- this is a gradient descent algorithm that uses your loss and gradient functions. The cell below will train an SVM on the example data set 1 with C = 1. It first scales the data to have zero mean and unit variance, and adds the intercept term to the data matrix.When C = 1, you should find that the SVM puts the decision boundary inthe gap between the two datasets and misclassifies the data point on the farleft. Your task is to try different values of C on this dataset. Specifically, youshould change the value of C in the cell below to C = 100 and run the SVMtraining again. When C = 100, you should find that the SVM now classifiesevery single example correctly, but has a decision boundary that does notappear to be a natural fit for the data. Include a plot of the decision boundary for C = 100 in writeup.pdf.<jupyter_code>############################################################################
# Scale the data and set up the SVM training                               #
############################################################################

# scale the data

scaler = preprocessing.StandardScaler().fit(X)
scaleX = scaler.transform(X)

# add an intercept term and convert y values from [0,1] to [-1,1]

XX = np.array([(1,x1,x2) for (x1,x2) in scaleX])
yy = np.ones(y.shape)
yy[y == 0] = -1
yy[y == 0] = -1

############################################################################
#  Part  2: Training linear SVM                                            #
#  We train a linear SVM on the data set and the plot the learned          #
#  decision boundary                                                       #
############################################################################

############################################################################
# You will change this line below to vary C.                               #
############################################################################

C = 1

svm = LinearSVM_twoclass()
svm.theta = np.zeros((XX.shape[1],))
svm.train(XX,yy,learning_rate=1e-4,reg=C,num_iters=50000,verbose=True,batch_size=XX.shape[0])

# classify the training data

y_pred = svm.predict(XX)

print("Accuracy on training data = %.3f" %metrics.accuracy_score(yy,y_pred))

# visualize the decision boundary

utils.plot_decision_boundary(scaleX,y,svm,'x1','x2',['neg','pos'])
############################################################################
# Scale the data and set up the SVM training                               #
############################################################################

# scale the data

scaler = preprocessing.StandardScaler().fit(X)
scaleX = scaler.transform(X)

# add an intercept term and convert y values from [0,1] to [-1,1]

XX = np.array([(1,x1,x2) for (x1,x2) in scaleX])
yy = np.ones(y.shape)
yy[y == 0] = -1
yy[y == 0] = -1

############################################################################
#  Part  2: Training linear SVM                                            #
#  We train a linear SVM on the data set and the plot the learned          #
#  decision boundary                                                       #
############################################################################

############################################################################
# You will change this line below to vary C.                               #
############################################################################

C = 100

svm = LinearSVM_twoclass()
svm.theta = np.zeros((XX.shape[1],))
svm.train(XX,yy,learning_rate=1e-4,reg=C,num_iters=50000,verbose=True,batch_size=XX.shape[0])

# classify the training data

y_pred = svm.predict(XX)

print("Accuracy on training data = %.3f" %metrics.accuracy_score(yy,y_pred))

# visualize the decision boundary

utils.plot_decision_boundary(scaleX,y,svm,'x1','x2',['neg','pos'])<jupyter_output>iteration 0 / 50000: loss 100.000000
iteration 100 / 50000: loss 30.590663
iteration 200 / 50000: loss 21.232761
iteration 300 / 50000: loss 16.888655
iteration 400 / 50000: loss 14.368906
iteration 500 / 50000: loss 12.473422
iteration 600 / 50000: loss 11.533702
iteration 700 / 50000: loss 11.139755
iteration 800 / 50000: loss 10.755964
iteration 900 / 50000: loss 10.372323
iteration 1000 / 50000: loss 9.988833
iteration 1100 / 50000: loss 9.605493
iteration 1200 / 50000: loss 9.222303
iteration 1300 / 50000: loss 8.856682
iteration 1400 / 50000: loss 8.516792
iteration 1500 / 50000: loss 8.278231
iteration 1600 / 50000: loss 8.052670
iteration 1700 / 50000: loss 7.828877
iteration 1800 / 50000: loss 7.613761
iteration 1900 / 50000: loss 7.429853
iteration 2000 / 50000: loss 7.304432
iteration 2100 / 50000: loss 7.179061
iteration 2200 / 50000: loss 7.054830
iteration 2300 / 50000: loss 6.996859
iteration 2400 / 50000: loss 6.941865
iteration 2500 / 50000: loss 6.886834
iteration 260[...]<jupyter_text>SVMs with Gaussian kernels In this part of the exercise, you will be using SVMs to do non-linear classification.In particular, you will be using SVMs with Gaussian kernels ondatasets that are not linearly separable.To find non-linear decision boundaries with the SVM, we need to first implementa Gaussian kernel. You can think of the Gaussian kernel as a similarityfunction that measures the distance between a pair of examples,$(x^{(i)}, x^{(j)})$. The Gaussian kernel is also parameterized by a bandwidth parameter,$\sigma$,  which determines how fast the similarity metric decreases (to 0)as the examples are further apart.You should now complete the function **gaussian\_kernel** in **utils.py** to computethe Gaussian kernel between two examples. The Gaussian kernelfunction is defined as:$$ k(x^{(i)},x^{(j)}) = exp\left(- \frac{{||x^{(i)}-x^{(j)}||}^2}{2\sigma^2}\right) $$When you have completed the function, the cell belowwill test your kernel function on two provided examples and you should expectto see a value of 0.324652.<jupyter_code>############################################################################
#  Part  3: Training SVM with a kernel                                     #
#  We train an SVM with an RBF kernel on the data set and the plot the     #
#  learned decision boundary                                               #
############################################################################

# test your Gaussian kernel implementation

x1 = np.array([1,2,1])
x2 = np.array([0,4,-1])
sigma = 2

print("Gaussian kernel value (should be around 0.324652) = %.5f" %utils.gaussian_kernel(x1,x2,sigma))<jupyter_output>Gaussian kernel value (should be around 0.324652) = 0.32465<jupyter_text>SVMs with Gaussian kernels on Dataset 2The next cell will load and plot dataset 2. Fromthe plot, you can observe that there is no linear decision boundary thatseparates the positive and negative examples for this dataset. However, byusing the Gaussian kernel with the SVM, you will be able to learn a non-lineardecision boundary that can perform reasonably well for the dataset.If you have correctly implemented the Gaussian kernel function, the cell belowwill proceed to train the SVM with the Gaussian kernel on this dataset.The decision boundary found by the SVM with C = 1 and a Gaussiankernel with $\sigma = 0.01$ will be plotted. The decision boundary is able to separate most of the positive andnegative examples correctly and follows the contours of the dataset well.<jupyter_code># load ex4data2.mat

X,y = utils.load_mat('data/ex4data2.mat')

# visualize the data

utils.plot_twoclass_data(X,y,'', '',['neg','pos'])

# convert X to kernel form with the kernel function

sigma = 0.02

# compute the kernel (slow!)

K = np.array([utils.gaussian_kernel(x1,x2,sigma) for x1 in X for x2 in X]).reshape(X.shape[0],X.shape[0])

# scale the kernelized data matrix

scaler = preprocessing.StandardScaler().fit(K)
scaleK = scaler.transform(K)

# add the intercept term

KK = np.vstack([np.ones((scaleK.shape[0],)),scaleK.T]).T

# transform y from [0,1] to [-1,1]

yy = np.ones(y.shape)
yy[y == 0] = -1

# set up the SVM and learn the parameters

svm = LinearSVM_twoclass()
svm.theta = np.zeros((KK.shape[1],))
C = 1
svm.train(KK,yy,learning_rate=1e-4,reg=C,num_iters=20000,verbose=True,batch_size=KK.shape[0])

# visualize the boundary

utils.plot_decision_kernel_boundary(X,y,scaler,sigma,svm,'','',['neg','pos'])<jupyter_output>iteration 0 / 20000: loss 1.000000
iteration 100 / 20000: loss 0.909639
iteration 200 / 20000: loss 0.819280
iteration 300 / 20000: loss 0.728923
iteration 400 / 20000: loss 0.638568
iteration 500 / 20000: loss 0.549187
iteration 600 / 20000: loss 0.464934
iteration 700 / 20000: loss 0.385395
iteration 800 / 20000: loss 0.314347
iteration 900 / 20000: loss 0.255687
iteration 1000 / 20000: loss 0.209960
iteration 1100 / 20000: loss 0.174572
iteration 1200 / 20000: loss 0.148580
iteration 1300 / 20000: loss 0.127957
iteration 1400 / 20000: loss 0.111948
iteration 1500 / 20000: loss 0.099269
iteration 1600 / 20000: loss 0.088947
iteration 1700 / 20000: loss 0.080530
iteration 1800 / 20000: loss 0.073272
iteration 1900 / 20000: loss 0.066809
iteration 2000 / 20000: loss 0.061174
iteration 2100 / 20000: loss 0.056112
iteration 2200 / 20000: loss 0.051827
iteration 2300 / 20000: loss 0.048282
iteration 2400 / 20000: loss 0.045170
iteration 2500 / 20000: loss 0.042354
iteration 2600 / 20000: [...]<jupyter_text>Selecting hyperparameters for SVMs with Gaussian kernelsIn this part of the exercise, you will gain more practical skills on how to usea SVM with a Gaussian kernel. The next cell will load and displaya third dataset. In the provided dataset, **ex4data3.mat**, you are given the variables **X**,**y**, **Xval**, **yval**.  You will be using the SVM with the Gaussiankernel with this dataset. Your task is to use the  validation set **Xval**, **yval** to determine thebest C and $\sigma$ parameter to use. You should write any additional code necessaryto help you search over the parameters C and $\sigma$. For both C and $\sigma$, wesuggest trying values in multiplicative steps (e.g., 0.01, 0.03, 0.1, 0.3, 1, 3, 10, 30).Note that you should try all possible pairs of values for C and $\sigma$ (e.g., C = 0.3and $\sigma$ = 0.1). For example, if you try each of the 8 values listed above for Cand for $\sigma$, you would end up training and evaluating (on the  validationset) a total of $8^2 = 64$ different models.When  selecting  thebest C and $\sigma$ parameter to use, you train on {\tt X,y} with a given C and $\sigma$, and then  evaluate the error of the model on the validation set. Recall that for classification, the error is defined as thefraction of the  validation examples that were classified incorrectly.You can use the **predict** method of the SVM classifier to generate the predictions for the validation set.  After you have determined the best C and $\sigma$ parameters to use, youshould replace the assignments to **best\_C** and **best\_sigma** in the cell below.<jupyter_code>############################################################################
#  Part  4: Training SVM with a kernel                                     #
#  We train an SVM with an RBF kernel on the data set and the plot the     #
#  learned decision boundary                                               #
############################################################################

# load ex4data3.mat

X,y,Xval,yval = utils.loadval_mat('data/ex4data3.mat')

# transform y and yval from [0,1] to [-1,1]

yy = np.ones(y.shape)
yy[y == 0] = -1

yyval = np.ones(yval.shape)
yyval[yval == 0] = -1

# visualize the data

utils.plot_twoclass_data(X,y,'x1', 'x2',['neg','pos'])


############################################################################
# TODO                                                                     #
# select hyperparameters C and sigma for this dataset using                #
# Xval and yval                                                            #
############################################################################
Cvals = [0.01,0.03,0.1,0.3,1,3,10,30]
sigma_vals = [0.01,0.03,0.1,0.3,1,3,10,30]

# TODO       
# select hyperparameters here; loopover all Cvals and sigma_vals. 
# About 8-10 lines of code here
best = 1.0
para = (0, 0)
for C in Cvals:
    for sigma in sigma_vals:
        K = np.array([utils.gaussian_kernel(x1,x2,sigma) for x1 in X for x2 in X]).reshape(X.shape[0],X.shape[0])
        scaler = preprocessing.StandardScaler().fit(K)
        scaleK = scaler.transform(K)
        KK = np.vstack([np.ones((scaleK.shape[0],)),scaleK.T]).T
        Kval = np.array([utils.gaussian_kernel(x1,x2,sigma) for x1 in Xval for x2 in X]).reshape(Xval.shape[0],X.shape[0])
        scaleKval = scaler.transform(Kval)
        KKval = np.vstack([np.ones((scaleKval.shape[0],)),scaleKval.T]).T
        svm = LinearSVM_twoclass()
        svm.theta = np.zeros((KK.shape[1],))
        svm.train(KK,yy,learning_rate=1e-4,reg=C,num_iters=20000,batch_size=KK.shape[0])
        yyval_pre = svm.predict(KKval)
        cur = np.sum((yyval_pre != yyval) * 1.0) / yyval.shape[0]
        print(f'validation error is {cur}')
        if cur < best:
            best = min(cur, best)
            para = (C, sigma)
############################################################################
#       END OF YOUR CODE                                                   #
############################################################################
print(f'best Cval is {para[0]}, best sigma is {para[1]}, validation error is {cur}')


# TODO: make sure you put in the best_C and best_sigma from the analysis above!


best_C = 0.3
best_sigma = 0.1

# train an SVM on (X,y) with best_C and best_sigma
best_svm = LinearSVM_twoclass()

############################################################################
# TODO: construct the Gram matrix of the data with best_sigma, scale it, add the column of ones
# Then use svm_train to train best_svm with the best_C parameter. Use 20,000 iterations and
# a learning rate of 1e-4. Use batch_size of the entire training data set.
# About 5-6 lines of code expected here.
############################################################################
K = np.array([utils.gaussian_kernel(x1,x2,best_sigma) for x1 in X for x2 in X]).reshape(X.shape[0],X.shape[0])
scaler = preprocessing.StandardScaler().fit(K)
scaleK = scaler.transform(K)
KK = np.vstack([np.ones((scaleK.shape[0],)),scaleK.T]).T
best_svm.theta = np.zeros((KK.shape[1],))
best_svm.train(KK,yy,learning_rate=1e-4,reg=best_C,num_iters=20000,batch_size=KK.shape[0])

############################################################################
#       END OF YOUR CODE                                                   #
############################################################################

# visualize the boundary (uncomment this line after you learn the best svm)

utils.plot_decision_kernel_boundary(X,y,scaler,best_sigma,best_svm,'','',['neg','pos'])<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.20214966947570268, 'fraction_numerical': 0.061159610435484686, 'mean_word_length': 3.9631855747558227, 'pattern_counts': {'":': 0, '<': 28, '<?xml version=': 0, '>': 27, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 25, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '443903', 'license': 'MIT', 'n_tokens_mistral': 6574, 'n_tokens_neox': 5602, 'n_words': 2081, 'path': 'HW4/submit/binary_svm.ipynb', 'repo_name': 'JavisDaDa/COMP540ML', 'size': '19817'}