1   Dataset

For this assignment, you are provided with a synthetic dataset generated by the make blobs() function from the scikit-learn package. The code to generate and split the dataset is included. When you work on the assignment, please do not modify the data generation code (i.e., the first cell in the notebook). Similar to the last assignment, the dataset contains a set of 2-d features xi= (x ,x) with binary labels yi∈ {−1, 1}.

A word of caution: It is extremely important that you use the test data only once before reporting the final test loss. Before that step, you should always use your training and validation data to tune your model.

2   Programming: Support Vector Machine (SVM) (50 points)

2.1   SVM with primal formulation

In this problem, you will implement, train, and evaluate a soft-margin SVM using the provided dataset. The class definition for SVMTrainer is structurally similar to trainers in previous assignments. The parts you need to implement are described as follows.

Hinge loss and its derivative   The hinge loss equation below is the same as the one in lecture slides, except that we use w to explicitly represent the non-bias weights, and b to refer to the bias term.

L(w, b) = wTw+Cmax n0, 1 − y(i) wTx(i) +bo

The derivative of the hinge loss function is also given below. Note that the loss function above calculates the total loss of all samples, as it sums up the loss from index 1 to N.  However, the derivative below is a per-sample formulation (i.e., a single gradient for each sample). In your implementation, you can either use 1) the per-sample gradient update or 2) the batch gradient update. They are conceptually the same as batch size = 1 and batch size = N (N is the number of training samples). When you initialize your model parameters, you can either initialize a single θ vector or b and w separately.

= ( wTx(i) +b > 0

= ),e wTx(i) +b > 0

Gradient descent step   Similar to Assignments 1 and 2, this function performs a one-step gradient update on your model weights, except that you will use the derivative of the hing loss described above.

Prediction   In the previous assignment, your prediction is a probability output by your sigmoid() func- tion. In this assignment, you’ll need to use the sign of your raw prediction as your final prediction because the labels in the dataset are {−1, 1} instead of {0, 1}.

Support vectors   Given weights w and bias b and a training example (xi ,yi), if the value of y(i) wTx(i) +b

is equal to 1, that example is regarded as a support vector. However, due to the limited precision in Python and NumPy, you will rarely get exactly 1.0, but some value very close to 1 (e.g., 0.999946, 1.000023012). Therefore, you should pick some arbitrary small value ε and include an example as a support vector if

y(i) wTx(i) +b = 1 ±ε. You may want to complete the plot decision boundary() function first (de- scribed in Section2.3) before plotting the support vectors.

Accuracy calculation   This function is used to calculate prediction accuracy, and you can adapt your implementation from assignment 2.

Training, validation, and evaluation   You will initialize a trainer, train your SVM, and tune your model by trying different sets of regularization parameter c, learning rate α, and number of epochs. For evaluation, you will compute the test loss and accuracy, which should be the same as what you do for validation data in train(). Only call evaluate() once after finishing tuning hyperparameters.

2.2   SVM with dual formulation

In this problem, you will implement the dual formulation of SVM with gradient descent. The loss function and its constraints are given below. Note that you cannot directly use this loss function with gradient descent, as 1) it is a maximization problem in the dual formulation and 2) it has constraint.

xL(α) = αi − αiαjy(i)y(j)x(i)Tx(j)

s.t. C ≥ αi ≥ 0 ∀i, αiy(i) = 0

First, you will need to convert the maximization problem to a minimization problem. Constraint wise, to ensure C ≥ αi ≥ 0, you will need to clip α after each gradient update so that all parameters are between 0 and C. More specifically, after each gradient update, you adjust your α such that it satisfies the constraint by setting values in α larger than C to C, and values less than 0 to 0.  You may want to use np.clip() from NumPy.  To impose ∑i αiy(i) = 0, a simple solution is to add a term penalty · ∑i(αiy(i))2  to the loss

function, and the penalty is a parameter you need to define when you create your trainer. You will also need to calculate the derivative of the final loss function to compute your gradient. When you add an additional term to your loss function, do not forget to take the derivative.

In the provided starter code, the class DualSVMTrainer is a child class of the default SVMTrainer. You will have to overwrite gradient descent step(), hinge loss(), hinge loss derivative(), and possi- bly also train() and evaluate(), depending on your specific implementation. However, if your imple- mentation largely differs from SVMTrainer, feel free to overwrite any class attributes or functions based on your needs. Additionally, you will need to write an additional function compute bw() to convert α back to weights w and bias b (or θ).

For the dual SVM implementation, we recommend initializing α with values larger than 0. For example, you can use np.random.rand() to draw values from a uniform distribution over [0, 1). You may also need to try more sets of hyperparameters for dual SVM to achieve a low loss and more epochs for it to converge.

2.3   Additional tasks and experiments

Plotting decision boundary, margin, and support vectors   You will also write a function

plot decision boundary() to plot the decision boundary and margin. An example plot is given above. Before calling this function, you need to call plot data() to visualize the data points. Once your compute support vectors, you can use plt.scatter() with parameters facecolors="none",  edgecolors="k", label="sv" to highlight them.

Hard-margin SVM   After implementing both the soft-margin SVM and its dual form, convert them to their hard-margin counterparts, and train them on the same datasets. (Hint: You do not have to rewrite your SVM to achieve this.)  After tuning hyperparameters for all four models (i.e., soft+hard-margin SVMs in primal and dual formulation), include the decision boundary plots in your report.

Noisy data   The default dataset given is linearly-separable. Now, randomly select two examples in your training set with labels 1 and -1, swap their labels, and retrain your primal and dual SVMs with regularization parameter C = {0.01, 0.1, 1, 10, 100}. Include your decision boundary plots for each C in the final report and describe how the boundary and margin change. You should have 2 ×5 = 10 (2 for two models and 5 for five parameters C) plots for this part.