# Machine Learning Homework 4 SVM Department : Forsetry Student : M10912004 Name : De-Kai Kao (高得愷) E-mail : block58697@gmail.com ## 1. Linear hard-margin SVM For the data set $$ X=[\vec{x}_{1}\; \vec{x}_{2}\; \vec{x}_{3} ] = [(1,2)\;(2,1)\;(4,2)]\\Y=[y_{1}\;y_{2}\;y_{3}]=[-1\;1\;1] $$ * Plot ![](https://hackmd.io/_uploads/ByY34fF43.png) 1. Determine the supporting vectors $$ Decison\;Boundary:\vec{w}\cdot\vec{x}+b=0\\Upper\;Boundary:\vec{w}\cdot\vec{x}+b=1\\Lower\;Boundary:\vec{w}\cdot\vec{x}+b=-1 $$ $$ Width\;d=\overrightarrow{x^{-}x^{+}}\frac{\vec{w}}{||w||}\\ =\frac{1}{||w||}w^T(x^+-x^-)\\=\frac{1}{||w||}(w^Tx^+-w^Tx^-)\\=\frac{1}{||w||}[1-b-(1-b)]\\d=\frac{2}{||w||} $$ $$ argmax_{w,b}\frac{2}{||w||}\Rightarrow argmin_{w,b}\frac{||w||^2}{2}\\Objective \;Function：f_{i}(w)=argmin_{w,b}\frac{||w||^2}{2}\\s.t.\;f_i(w)=y_{i}(\vec{w}\cdot \vec{x_i}+b)\ge1,\;i=1,2,...,N $$ * 基於KKT條件的二次規劃問題，需要引入拉格朗日乘數(lagrange multiplier)求得最佳解。 $$ Lp(w,b,\lambda)=\frac{1}{2}||w||^2+\sum_{i=1}^{N}\lambda_{i}[1-y_{i}(\vec{w}\cdot \vec{x_i}+b)]......(1)\\ $$ * 拉格朗日乘數可以透過引入未知標量($\lambda$)，分別 $w,b$ 偏微分，直接求多元函數條件的極值 * 若多元函數不帶約束條件求極值時，分別 $w,b$ 偏微分解方程，極為無條件極值 * 當 $f_{i}(w)>0$ 無約束 $\lambda_{i}=0$ * 當 $f_{i}(w)=0,\;\lambda_{i}\neq0$ 即可求出支持向量 $$ \frac{\partial Lp}{\partial w}=0\Rightarrow \vec{w}=\sum_{i=1}^N\lambda_{i}y_{i}\vec{x_{i}}.......(2 )\\\frac{\partial Lp}{\partial b}=0\Rightarrow -\sum_{i=1}^N\lambda_{i}y_{i}.......(3) $$ * 將(2)帶回(1)式，可得 $$ Dual form\;\;L_{D}(\lambda)=\sum_{i=1}^N\lambda_{i}-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\lambda_{i}\lambda_{j}y_{i}y_{j}(x_{i}\cdot x_{j})......(4) $$ * 因為 $L_{D}(\lambda)$ 已經沒有變量 $w,b$ 故將$X,\; Y$ 代入 $L_{D}(\lambda)$ * Case1 支持向量為 $\vec{x}_1\; \vec{x}_2$ 因 $\vec{x_3}$ 為非支持向量，所以 $\lambda_3=0$ \begin{aligned} L_{D}(\lambda)&=(\lambda_{1}+\lambda_{2})-\frac{1}{2}[\lambda_{1}\lambda_{1}(4)-\lambda_{1}\lambda_{2}(4)-\lambda_{2}\lambda_{1}(4)+\lambda_{2}\lambda_{2}(4)]\end{aligned} * 代入限制條件 $$ s.t.=\lambda\ge0,\;\sum^N_{i=1}\lambda_{i}y_{i}=0\\\Rightarrow\lambda_{1}y_{1}+\lambda_{2}y_{2}=0\\-\lambda_{1}+\lambda_{2}=0\\\lambda_{1}=\lambda_{2} $$ * $L_{D}(\lambda)=2\lambda_{1}-(0)\quad\lambda_{1,2}\in\mathbb{R}$ * Case1 支持向量為 $\vec{x}_1\; \vec{x}_2$ ，將其代入 $Upper\;\&\;Lower\;boundary$ $$ 1\vec{w_1}+2\vec{w_2}+b=1\\2\vec{w_1}+1\vec{w_2}+b=-1\\Upper\;boundary\;-\;Lower\;boundary\\\Rightarrow\;\vec{w_1}=\vec{w_2}-2\\ $$ * 目標函數 $f_{i}(w)=argmin_{w,b}\frac{||w||^2}{2}$ $$ \Rightarrow\vec{w_1}^2+\vec{w_2}^2=(\vec{w_2}-2)^2+\vec{w_2}^2\\=2\vec{w_2}^2-4\vec{w_2}+4\\\frac{\partial L_D}{\partial \vec{w_2}}=0,\quad4\vec{w_2}-4=0,\quad\vec{w_2}=1,\quad\vec{w_1}=-1\\Upper\;boundary:1\times(-1)+2\times1+b=1\\b=0 $$ * Result: $$Decison\;Boundary:-x_1+x_2=0\\Upper\;Boundary:-x_1+x_2=1\\Lower\;Boundary:-x_1+x_2=-1$$ 2. Derive and plot the decision boundaries using Hard-margin SVM . ![](https://hackmd.io/_uploads/r107TIkSh.png) * Case2 支持向量為 $\vec{x_1}\; \vec{x_3}$ ， $\vec{x_2}$ 會和限制條件抵觸 $$ s.t.\;f_i(w)=y_{i}(\vec{w}\cdot \vec{x_i}+b)\ge1,\;i=1,2,...,N\\f_i(\vec{x_2})=y_i(\vec{w}\cdot \vec{x_2}+b)\ngeq1$$ * 討論： 課堂講義上只有兩點的計算範例，當資料是兩點以上就需要判定是否為支持向量，但在這次的例題中我仍然無法全然確定哪些並非支持向量，在 Case2 的例題中，其實是無法在未知 $\vec{w}\;\&\;b$ 的情況下判定是否為支持向量，本題非支持向量是由散佈圖中推論出來。可以理解的部分是引入拉格朗日乘數後，支持向量是在 $\lambda\neq0$ 時可以求出，$\lambda=0$ 對應的即為非支持向量，但仍然無法完全從對偶公式中判別支持向量與否，有從網路上得知可以用SMO或二次規劃等數值優化技術，很抱歉但無法在本次作業理解所有的公式。 ## 2. Linear soft-margin SVM For the data set $$ X=[\vec{x}_{1}\; \vec{x}_{2}\; \vec{x}_{3}\; \vec{x}_{4} ] = [(1,2)\;(2,1)\;(3,1)\;(5,1)]\\Y=[y_{1}\;y_{2}\;y_{3}\;y_{4}]=[-1\;1\;1\;1] $$ * Plot ![](https://hackmd.io/_uploads/rySa4OANn.png =60%x) A slack variable is chosen to be C=0.5 1. Determine the supporting vectors \begin{aligned}L=min_{w,\xi_i}\frac{||w||^2}{2}+C\sum_{i=1}^{N}\xi_i\quad s.t.:\;y_{i}(\vec{w}\cdot\vec{x_{i}}+b)\ge1-\xi_i,\;\xi\ge0 \end{aligned} * 同樣需要引入拉格朗日乘數來求得最佳解 $$ Lp(w,b,\lambda,\mu,\xi)=\\\frac{1}{2}||w||^2+C\left(\sum_{i=1}^{N}\xi_{i}\right)-\sum^N_{i=1}\lambda_{i}(1-y_{i}(\vec{w}\cdot\vec{x_{i}}+b)-1+\xi_i)-\sum^N_{i=1}\mu_i\xi_i......(1)\\ $$ * 根據KKT條件將不等式約束轉換成等式 $$ \lambda_i\ge0,\;\lambda_i[y_i(\vec{w}\;\cdot\vec{x_i}+b)-1+\xi_i]=0\\\mu_i\ge0,\;\mu_i\xi_i=0 $$ * 分別對 $w,b,\xi_i$ 偏微分令其為零 $$ \frac{\partial Lp}{\partial w}=0\Rightarrow \vec{w}=\sum_{i=1}^N\lambda_{i}y_{i}\vec{x_{i}}\\\frac{\partial Lp}{\partial b}=0\Rightarrow \sum_{i=1}^N\lambda_{i}y_{i}=0\\\frac{\partial Lp}{\partial \xi}=0\Rightarrow C-\lambda_i-\mu_i=0\\ $$ * 整合可得目標函數 $$ L_D=max\sum^N_{i=1}\lambda_i-\frac{1}{2}\sum^N_{i=1}\sum^N_{j=1}\lambda_i\lambda_jy_iy_j(\vec{x_i}\cdot\vec{x_j})\\s.t.\quad\sum^N_{i=1}\lambda_iy_i=0,\;0\le\lambda_i\le C=0.5 $$ $$ \left\{ \begin{aligned} &\lambda=0\quad 即點在兩條 Boundary 之外\\&\lambda=C\quad 即點在兩條 Boundary 之內\\&0\le\lambda_i\le C\quad 即點在兩條 Boundary 上，即為支持向量 \end{aligned} \right\}...(2) $$ * Case1 支持向量為 $\vec{x}_1\; \vec{x}_2;\quad \lambda_3=0,\lambda_4=0$ $$ \lambda_1y_1+\lambda_2y_2=0\\\lambda_1=\lambda_2\\L_D=(\lambda_1+\lambda_2)-\frac{1}{2}(\lambda_1\lambda_1(4)-\lambda_1\lambda_2(4)-\lambda_2\lambda_1(4)+\lambda_2\lambda_2(4))\\=2\lambda_1-(0) $$ * $L_{D}(\lambda)=2\lambda_1-(0)\quad\lambda_{1,2}\in\mathbb{R}$ * Case2 支持向量為 $\vec{x}_1\; \vec{x}_3;\quad \lambda_2=0.5,\lambda_4=0$ $$ \lambda_1y_1+\lambda_2y_2+\lambda_3y_3=0\\-\lambda_1+0.5+\lambda_3=0\quad\lambda_1=\lambda_3+0.5\\ $$ \begin{aligned} L_D&=(\lambda_1+0.5+\lambda_3)-\frac{1}{2}[\\&\quad\lambda_1\lambda_1(4)-\lambda_1(0.5)(4)-\lambda_1\lambda_3(5)\\&\quad-(0.5)\lambda_1(4)+(0.5)(0.5)(5)+(0.5)\lambda_3(6)\\&\quad-\lambda_3\lambda_1(5)+\lambda_3(0.5)(7)+\lambda_3\lambda_3(10))\\&=3(\lambda_3)^2+\lambda_3-\frac{3}{8}\end{aligned} $$ \frac{\partial L_D}{\partial \lambda_3}=6\lambda_3+1=0,\quad \lambda_3=-\frac{1}{6},\;\lambda_1=\frac{1}{3} $$ * . * $\lambda_3$ 為負值... * Case3 支持向量為 $\vec{x}_1\; \vec{x}_4\quad \lambda_{2,4}=0.5$ $$ \lambda_1y_1+\lambda_2y_2+\lambda_3y_3+\lambda_4y_4=0\\-\lambda_1+0.5+\lambda_3+0.5=0\quad\lambda_1=\lambda_3+1 $$ \begin{aligned} L_D &=(\lambda_1+1+\lambda_3)-\frac{1}{2}[\\&\quad\lambda_1\lambda_1(4)-\lambda_1 (0.5)(4)-\lambda_1\lambda_3(5)-\lambda_1(0.5)(7)\\&\quad-(0.5)\lambda_1(4)+(0.5)(0.5)(4)+(0.5)\lambda_3(7)-(0.5)(0.5)(11)\\&\quad-\lambda_3\lambda_1(5)+\lambda_3(0.5)(7)+\lambda_3\lambda_3(10)+\lambda_3(0.5)(16))\\&\quad-(0.5)\lambda_1(7)+(0.5)(0.5)(11)+(0.5)\lambda_3(16)+(0.5)(0.5)(26)]\\&=2\lambda_3+2-\frac{1}{2}[\\&\quad4(\lambda_3)^2+8\lambda_3+4-2\lambda_3-2-5(\lambda_3)^2-5\lambda_3-3.5\lambda_3-3.5\\&\quad-2\lambda_3-2+1+3.5\lambda_3+2.75\\&\quad-5(\lambda_3)^2-5\lambda_3+3.5\lambda_3+10(\lambda_3)^2+8\lambda_3\\&\quad-3.5\lambda_3-3.5+2.75+8\lambda_3+6.5]\\&=4(\lambda_3)^2+10\lambda_3+10\end{aligned} $$ \frac{\partial L_D}{\partial \lambda_3}=8\lambda_3+10=0,\quad \lambda_3=-\frac{5}{4},\;\lambda_1=-\frac{1}{4} $$ * $\lambda_{1,3}$ 為負值... 2. Derive and plot the decision boundaries using Soft-margin SVM. 在所有 Case 計算出的 $\lambda$ 值皆有負值和式(2)衝突，無法計算 $\vec{w}=\sum_{i=1}^N\lambda_{i}y_{i}\vec{x_{i}}$ ## Python sklearn soft-margin * Import packages ``` import matplotlib.pyplot as plt import numpy as np import pandas as pd import pylab as pl import seaborn as sns from sklearn import svm from sklearn.metrics import accuracy_score ``` * 生成三個label各200筆的資料 ``` # Set up the parameters for the normal distributions mean1 = 20 std1 = 5 mean2 = 50 std2 = 10 mean3 = 60 std3= 4 n = 200 # Generate n random samples of x1 and x2 x1 = np.random.normal(mean1, std1, n) y1 = np.random.normal(mean1, std1, n) x2 = np.random.normal(mean2-0.5, std2, n) y2 = np.random.normal(mean2, std2, n) x3 = np.random.normal(mean3, std3, n) y3 = np.random.normal(mean1-0.5, std3, n) mean = np.mean(np.concatenate((x1, x2, x3, y1, y2, y3))) sigma = np.std(np.concatenate((x1, x2, x3, y1, y2, y3))) zx1 = (x1-mean) / sigma zy1 = (y1-mean) / sigma zx2 = (x2-mean) / sigma zy2 = (y2-mean) / sigma zx3 = (x3-mean) / sigma zy3 = (y3-mean) / sigma xy1 = np.stack((zx1, zy1), axis=1) xy2 = np.stack((zx2, zy2), axis=1) xy3 = np.stack((zx3, zy3), axis=1) # plt.xlim(0, 100) # plt.ylim(0, 100) plt.plot(xy1[:,0], xy1[:,1], 'g.', xy2[:,0], xy2[:,1], 'y.', xy3[:,0], xy3[:,1], 'r.') plt.gca().axis('equal') one = np.insert(xy1, 2, 1, axis=1) two = np.insert(xy2, 2, 2, axis=1) three = np.insert(xy3, 2, 3, axis=1) df = pd.DataFrame(np.concatenate((one, two, three)), columns = ['x','y','label']) df['label'] = df['label'].astype(int) print(df) ``` ![](https://hackmd.io/_uploads/B1ztzseS3.png) * 將資料拆分成訓練資料和測試資料 ``` train = df.sample(frac=0.8) test = df.loc[df.index.difference(train.index)] X = train[train.columns[:2]] Y = train[train.columns[2]] X_test = test[test.columns[:2]] Y_test = test[test.columns[2]] ``` * 最後使用sklearn套件 ``` svc = svm.SVC(kernel='linear').fit(X, Y) # create a mesh to plot in x_min, y_min = X.min()-1 x_max, y_max = X.max()+1 h=.02 # step size in the mesh xx, yy = np.meshgrid(np.arange(x_min, x_max, h), np.arange(y_min, y_max, h)) titles = 'SVC with linear kernel' Z = svc.predict(np.c_[xx.ravel(), yy.ravel()]) # Put the result into a color plot Z = Z.reshape(xx.shape) plt.contourf(xx, yy, Z, cmap=plt.get_cmap('terrain'), alpha=0.8) colors = {1:'g', 2:'y', 3:'r'} # Plot also the training points plt.scatter(X_test.x, X_test.y, c=Y_test.map(colors), alpha=0.8) plt.xlim(xx.min(), xx.max()) plt.ylim(yy.min(), yy.max()) plt.title(titles) plt.show() ``` ![](https://hackmd.io/_uploads/Bk15SjgS3.png) * Result of accuracy score:0.975 ``` svc.predict(np.array(X_test)) accuracy_score(svc.predict(np.array(X_test)), np.array(Y_test)) # 0.975 ``` https://hackmd.io/Zfw0FsTjTdi8z2aOQwzTew?view ![](https://hackmd.io/_uploads/SJeP1yfr2.png)