課程名稱︰ 機器學習特論
課程性質︰ 選修
課程教師︰ 林智仁
開課學院： 電資院
開課系所︰ 資工系
考試日期（年月日）︰ 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) ?