课程名称︰ 机器学习特论
课程性质︰ 选修
课程教师︰ 林智仁
开课学院: 电资院
开课系所︰ 资工系
考试日期(年月日)︰ 2017/06/20
考试时限(分钟): 90 min
试题 :
Please give details of your answer. A direct answer without explanation is not
counted.
Your answers must be in English.
You can bring notes and the textbook. Other books or electronic devices are
not allowed.
"""
数学式用latex格式表示
可以丢到这个网站去看看原样
https://www.codecogs.com/latex/eqneditor.php
"""
Problem 1 (45pt)
Consider the following two optimization problems:
\min\limits_{w,\xi} \frac{1}{2} w^Tw + C \sum_{i=1}^{l} \xi_i
subject to y_i(w^T x_i) \geq 1 - \xi_i, i = 1,...,l,
\xi \succeq 0
(1)
and
\min\limits_{w} \fract{1}{2} w^Tw + C \sum_{i=1}^{l}
max(0,1-y_i w^T x_i) (2)
(a) (15 pts) Prove that for any optimal solution (w^*.\xi^*) of (1)
\xi^*_i = max (0,1 - y_i((w^*)^T x_i)).
(b) (15 pts) If (w^*,\xi^*) an optimal solution of (1),prove that w^* is also
an optimal solution of (2).
(c) (15 pts) If \bar{x} is an optimal solution of (2), can you construct an
optimal solution for (1)?
Your proof must be formal.
Problem 2 (10 pts)
Consider
f(x) = \frac{1}{2} ({x_1}^2 + r {x_2}^2)
Run one iteration of Newton method. Assume exact line search is used and x_0 =
\begin{bmatrix}
1\\
1
\end{bmatrix}
is the initial point.
(注:TA在考试的时候提醒,r > 0)
Problem 3 (45 pts)
Consider the following function
f(x_1,x_2) = {x_1}^2 + r {x_2}^2
We mentioned in the lecture that the gradient is orthogonal to the tangent
line. Here we would like to use the above funtion to do a detailed check.
(a) (15 pts) From a given (x_1,x_2),we would like to find the contour of
parameters t_1,t_2:
(x_1+t_1)^2 + r(x_2+t_2)^2 = {x_1}^2 + r{x_2}^2
Can you represent t_1 as a function of t_2 ?
(b) (15 pts) Assume x_1 > 0 and consider the situation of t\geq 0 , and both
t_1,t_2 are sufficiently close to zero (i.e. (t_1,t_2) \approx (0,0)).Let
g(t_2) =
\begin{bmatrix}
x_1 + t_1(t_2)\\
x_2 + t_2
\end{bmatrix},
where t_1(t_2) is the solution obtain from (a), What is \nabla g(t_2)?
(c) (15 pts) What are \nabla g(0) and \nabla f(
\begin{bmatrix}
x_1\\
x_2
\end{bmatrix}
)\nabla g(0) ?