Exercises for the course
Machine Learning 1
Winter semester 2021/22
fu ̈r Softwaretechnik und theoretische ̈at IV, ̈at Berlin Prof. Dr. Klaus- ̈ller Email:
Copyright By PowCoder代写 加微信 powcoder
Exercise Sheet 8
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.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com