Exercises for the course
Machine Learning 1
Winter semester 2020/21
Abteilung Maschinelles Lernen Institut fu ̈r Softwaretechnik und theoretische Informatik Fakult ̈at IV, Technische Universit ̈at Berlin Prof. Dr. Klaus-Robert Mu ̈ller Email: klaus-robert.mueller@tu-berlin.de
Exercise Sheet 7
Exercise 1: Dual formulation of the Soft-Margin SVM (5 + 20 + 10 + 5 P)
The primal program for the linear soft-margin SVM is
subject to
1 2 N min ∥w∥+C ξi w,b,ξ 2 i=1
∀Ni=1 : yi ·(w⊤φ(xi)+b)≥1−ξi and ξi ≥0
where ∥.∥ denotes the Euclidean norm, φ is a feature map, w ∈ Rd,b ∈ R are the parameter to optimize, and xi ∈ Rd,yi ∈ {−1,1} are the labeled data points regarded as fixed constants. Once the hard-margin SVM has been learned, prediction for any data point x ∈ Rd is given by the function
f(x) = sign(w⊤φ(x) + b).
(a) State the conditions on the data under which a solution to this program can be found from the Lagrange
dual formulation (Hint: verify the Slater’s conditions).
(b) Derive the Lagrange dual and show that it reduces to a constrained quadratic optimization problem. State
both the objective function and the constraints of this optimization problem.
(c) Describe how the solution (w, b) of the primal program can be obtained from a solution of the dual program.
(d) Write a kernelized version of the dual program and of the learned decision function. Exercise 2: SVMs and Quadratic Programming (10 P)
We consider the CVXOPT Python software for convex optimization. The method cvxopt.solvers.qp solves quadratic optimization problems given in the matrix form:
min 1x⊤Px+q⊤x x2
subject to Gx ≼ h and Ax = b.
Here, ≼ denotes the element-wise inequality: (h ≼ h′) ⇔ (∀i : hi ≤ h′i). Note that the meaning of the variables x and b is different from that of the same variables in the previous exercise.
(a) Express the matrices and vectors P,q,G,h,A,b in terms of the variables of Exercise 1, such that this quadratic minimization problem corresponds to the kernel dual SVM derived above.
Exercise 3: Programming (50 P)
Download the programming files on ISIS and follow the instructions.