[Solved] B555 Written Assignment 4

1. In this question we consider the hard margin SVM formulation as developed in class and thetextbook. Recall that we stated that for this type of optimization problem there is no duality gap. That is, the primal and dual objective functions have the same value at their optimal solutions. Use this fact and other facts developed in class to show that the maximum margin can be calculated from the dual solution . More specifically show that .
2. The soft margin SVM formulation developed in class called for minimizing subject to constraints (for all i) 1 _i t_i(v^T(x_i) + v₀) 0 and _i 0.

Consider the alternative formulation QSVM that uses a quadratic penalty on _i which is: minimize subject to constraints (for all i) 1 _i t_i(v^T(x_i) + v₀) 0.

Note that we do not need the constraint _i 0 in this formulation because _i < 0 increases the objective function and makes the constraints harder to satisfy. Develop the dual formulation of QSVM: that is (1) compute the dual objective function, (2) state the dual optimization problem, and (3) argue that QSVM is also a kernel method.

3. In this problem we show that many machine learning problems have solutions that can beexpressed through kernels. Consider the standard formulation where a_i = w^T(x_i), and where we have a loss function `(a<sub>i</sub>,t<sub>i</sub>). For example we might use the square loss `(a_i,t_i) = (t_ia_i)² or the classification log loss `(a_i,t_i) = t_i lny_i +(1t_i)ln(1y_i) where y_i = (a_i) etc. But for this question we consider any loss function. In addition consider any regularization function R(b) which is monotonically increasing, where b is a scalar.

Now consider a machine learning objective of the form ^P_i `(a_i,t_i) + R(w^Tw).

Show the the optimal solution can be expressed as w = ^P_{i i}(x_i) that is, it is a weighted sum of training examples. Note that this shows that predictions on test example z can be computed as w^T(z) = ^P_{i i}K(x_i,z).

4. In lecture we provided a general form for optimizing the hyper-parameters of Gaussian ProcessRegression (GPR). In general there is no closed form and we must use some iterative gradient based optimization. Consider GPR where one hyperparameter, ₀, gives the overall scale of the covariance. Specifically, assume the covariance matrix has the form C(x_n,x_m) = ₀k(x_n,x_m) where k(,) is any valid kernel. Show that the marginal likelihood can be optimized w.r.t. ₀ in closed form and develop the solution for ₀.

1