課程名稱︰機器學習特論 課程性質︰資工系選修 課程教師︰林智仁 開課學院：電機資訊學院 開課系所︰資訊工程學系 考試日期（年月日）︰2018/06/26 考試時限（分鐘）：170 試題 : ● Please give details of your answer. A direct answer without explanation is not counted. ● Your answers must be in English. ● Please carefully read problem statements. ● During the exam you are not allowed to borrow others' class notes. ● Try to work on easier questions first. ● Exam time: 170 mimutes. Problem 1 (30 pts) Consider the following two problems from slide 8-10: \begin{equation}\label{eq1} \begin{aligned} \max_{\bm\lambda\in\mathbb R^N,\bm\mu\in\mathbb R^M} &&&\bm1^T\bm\lambda+\bm1^T\bm\mu\\ \text{subject to}&&&2\left\|\sum_{i=1}^N\lambda_i\bm x_i -\sum_{i=1}^M\mu_i\bm y_i\right\|_2\le1\\ &&&\bm1^T\bm\lambda=\bm1^T\bm\mu,\bm\lambda\succeq\bm0,\bm\mu\succeq\bm0, \end{aligned} \end{equation} \begin{equation}\label{eq2} \begin{aligned} \min_{t\in\mathbb R,\bm\theta\in\mathbb R^N,\bm\gamma\in\mathbb R^M}&&&t\\ \text{subject to}&&&\left\|\sum_{i=1}^N\theta_i\bm x_i =\sum_{i=1}^M\gamma_i\bm y_i\right\|_2\le t\\ &&&\bm\theta\succeq\bm0,\bm1^T\bm\theta=1,\bm\gamma\succeq\bm0, \bm1^T\bm\gamma=1. \end{aligned} \end{equation} Assume (\ref{eq1}) has an optimal solution \begin{equation}\label{eq3} (\bm\lambda^*,\bm\mu^*)\ne\bm0. \end{equation} (a) (10 pts) Formally prove that \[\bm\lambda^*\ne\bm0\] \[\bm\mu^*\ne\bm0.] Note that in any step of the proof you must specify the condition or the property of (\ref{eq1}) used. (b) (10 pts) Prove that under (\ref{eq3}), there is no feasible solution of (\ref{eq2}) with t = 0. (c) (10 pts) Generate a feasible solution for (\ref{eq2}) and formally prove that it is an optimal solution of (\ref{eq2}). Problem 2 (30 pts) Note that (\ref{eq1}) is the dual problem of the following primal problem \begin{equation}\label{eq4} \begin{aligned} \min_{\bm a,b}&&&\frac12\|\bm a\|_2\\ \text{subject to}&&&\bm a^T\bm x_i+b\ge1,i=1,\ldots,N\\ &&&\bm a^T\bm y_i+b\le-1,i=1,\ldots,M. \end{aligned} \end{equation} After changing to use our notation, we know that if we take the square norm of the objective function to have \[\begin{aligned} \min_{\bm x,b}&&&\frac12\|\bm w\|_2\\ \text{subject to}&&&y_i(\bm w^T\bm x_i+b)\ge1\ \forall i, \end{aligned}\] then the dual is \begin{equation}\label{eq5} \begin{aligned} \min_{\bm\alpha}&&&\frac12\bm\alpha^TQ\bm\alpha-\bm1^T\bm\alpha\\ \text{subject to}&&&\bm\alpha\succeq\bm0,\bm y^T\bm\alpha=0. \end{aligned} \end{equation} Assume that (\ref{eq5}) has an optimal solution \begin{equation}\label{eq6} \bm\alpha^*\ne\bm0. \end{equation} Through the following sub-problems we aim to show that in fact (\ref{eq5}) is equivalent to the dual problem (\ref{eq2}) of (\ref{eq4}). (a) (10 pts) Prove that under (\ref{eq6}), there is no feasible α ≠ 0 such that \[\bm\alpha^TQ\bm\alpha = 0.\] (b) (10 pts) Assume that \[y_i=\begin{cases} 1 & \text{if }i \in \{1, \ldots, N\}\\ -1 & \text{if }i \in \{N+1, \ldots, M\} \end{cases}\] Since $\bm y^T\bm\alpha = 0$ implies $\sum_{i=1}^N \alpha_i = \sum_{i=N+1}^M \alpha_i$, we can introduce a new variable λ and rewrite $\bm y^T\bm\alpha = 0$ as two constraints \[\sum_{i=1}^N \alpha_i = \lambda, \sum_{i=N+1}^M \alpha_i = \lambda\] From (\ref{eq6}), $\bm\alpha^*$ is an optimal solution of both (\ref{eq5}) and the following optimization problem \[\begin{aligned} \min_{\bm\alpha}&&&\frac12\bm\alpha^TQ\bm\alpha-\bm1^T\bm\alpha\\ \text{subject to}&&&\bm\alpha\succ\bm0,\bm y^T\bm\alpha=0. \end{aligned}\] Then we can define \[\bm\beta = \frac{\bm\alpha}\lambda.\] and the dual problem is rewritten as \[\begin{aligned} \min_{\bm\beta,\lambda}&&&\frac12\lambda^2\bm\beta^TQ\bm\beta-2\lambda\\ \text{subject to}&&&\bm\beta\succeq\bm0,\sum_{i=1}^N\beta_i=1 \text{ and }\sum_{i=N+1}^M\beta_i=1. \end{aligned}\] This is an optimization problem with variables β and λ. Can you eliminate the variable λ to get a new equivalent convex optimization problem of β? (c) (10 pts) Show that the optimization problem obtained in (b) can be converted to (\ref{eq2}) in problem 1. Problem 3 (10 pts) Consider the following function \[f(x) = e^x + e^{-x}, x \in \mathbb R.\] (a) (5 pts) Prove that this function is strongly convex by showing that there exists an m > 0 such that f''(x) ≧ m, ∀x. Find the largest possible m. (b) (5 pts) Suppose $x^* \in \mathbb R$ minimizes f(x), directly prove that \[f(x)-f(x^*) \le \frac1{2m}\|f'(x)\|^2.\] Here m is the largest possible one obtained in (a). Problem 4 (30 pts) Consider the following three (label, feature-vector) pairs: \[y_1 = -1, \bm x_1 = [0, 0]^T\] \[y_2 = 1, \bm x_2 = [1, 0]^T\] \[y_3 = 1, \bm x_3 = [0, 1]^T\] That is, we have https://i.imgur.com/ff9A3wP.png \begin{tikzpicture} \draw[->] (-1, 0) -- (3, 0); \draw[->] (0, -1) -- (0, 3); \filldraw (0, 0) circle(1pt) node[anchor=south west]{$\bm x_1$}; \draw[fill=white] (2, 0) circle(1pt) node[anchor=north]{$\bm x_2$}; \draw[fill=white] (0, 2) circle(1pt) node[anchor=east]{$\bm x_3$}; \end{tikzpicture} Consider the standard SVM optimization problem: \begin{equation}\label{eq7} \begin{aligned} \min_{\bm w,\bm\xi,b}&&&\frac12\bm w^T\bm w+C\sum_{i=1}^l\xi_i\\ \text{subject to}&&&y_i(\bm w^T\bm x_i+b)\ge1-\xi_i\ \forall i\\ &&&\xi_i\ge0\ \forall i, \end{aligned} \end{equation} where C ∈ (0, ∞). (a) (15 pts) Solve the dual problem for every C ∈ (0, ∞). Note that the dual problem is \[\begin{aligned} \min_{\bm\alpha}&&&\frac12\bm\alpha^TQ\bm\alpha-\bm1^T\bm\alpha\\ \text{subject to}&&&0\le\alpha_i\le C,\ \forall i\\ &&&\bm y^T\bm\alpha=0, \end{aligned}\] where \[Q_{ij} = y_iy_j\bm x_i^T\bm x_j\]. (b) (15 pts) Find the primal solution of (\ref{eq7}). Draw a figure to show how the decision hyper plane $\bm w^T\bm x + b = 0$ changes as C changes. -- 第01話 似乎在課堂上聽過的樣子 第02話 那真是太令人絕望了 第03話 已經沒什麼好期望了 第04話 被當、21都是存在的 第05話 怎麼可能會all pass 第06話 這考卷絕對有問題啊 第07話 你能面對真正的分數嗎 第08話 我，真是個笨蛋 第09話 這樣成績，教授絕不會讓我過的 第10話 再也不依靠考古題 第11話 最後留下的補考 第12話 我最愛的學分 --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.230.44.40 (臺灣) ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1744882297.A.BE1.html ※ 編輯: xavier13540 (36.230.44.40 臺灣), 04/17/2025 17:51:50