十三、支持向量機SVM

SVM（Support Vector Machines）

? ? 近年已被深度學(xué)習(xí)所替代

? ? SVM尋找區(qū)分兩類的超平面（hyper plane），使邊際（margin）最大


向量內(nèi)積：x.y = x_1y_1+x_2y_2+...+x_ny_n

? ? ? ? ? ? ? ? ? x.y = ||x||||y||cos(\theta)

范數(shù)：||x|| = \sqrt{x.x} = \sqrt{x_1^2+x_2^2+..+x_n^2}

當(dāng)||x||\neq 0時，可以求余弦相似度：cos(\theta) = \frac{x.y}{||x||||y||}


w.x_1+b=1

w.x_2+b=-1

w.(x_1-x_2) = 2

||w||||x_1-x_2||cos(\theta) = 2

||w||*d = 2

d = \frac{2}{||w||}

算法推論：

? ? 轉(zhuǎn)化為凸優(yōu)化問題：

????w.x+b\geq 1,則分類\ y=1

????w.x+b \leq -1,則分類\ y=-1

——》y(w.x+b)\geq 1，求d = \frac{2}{||w||}最大值，即求min \frac{||w||^2}{2}


? ? 而凸優(yōu)化問題一般有三種情況：

? ? ? ? 1、無約束優(yōu)化問題：????min(f(x)) ?? 費馬定理

? ? ? ? 2、帶等式約束的優(yōu)化問題：????minf(x)

? ? ? ? ? ? ? ? -拉格朗日乘子法：

? ? ? ? ? ? ? ? ? ? s.t. ?? h_i(x) = 0, \ \ \ i=1,2,...,n

????????????????????L(x,\lambda) = f(x)+\sum_{i=1}^{n}\lambda_ih_i(x)

? ? ? ? 3、帶不等式約束的優(yōu)化問題：????minf(x)

? ? ? ? ? ? ? ? -KKT條件

? ? ? ? ? ? ? ? ? ? s.t.????h_i(x) = 0,\ \ \ \ i=1,2,...,n

? ? ? ? ? ? ? ? ? ? ? ? ? ? ??g_i(x)\leq 0,\ \ \ \ i=1,2,...,k

????????????????????L(x,\lambda,v) = f(x)+\sum_{i=1}^{k}\lambda_ig_i(x)+\sum_{i=1}^{n}v_ih_i(x)

????而算法是在y(w.x+b)\geq 1的條件下求min \frac{||w||^2}{2}

? ? 實際上min \frac{||w||^2}{2}存在時，y(w.x+b)取1，即屬于第2種情況

? ? 廣義拉格朗日乘子法：

????????L(w,b,a) = \frac{1}{2}||w||^2 - \sum_{i=1}^{n} \alpha_i(y_i(w^Tx_i + b)-1)

????????\frac{\partial L}{\partial w} = 0 \rightarrow w = \sum_{i=1}^{n} \alpha_iy_ix_i

????????\frac{\partial L}{\partial b} = 0 \rightarrow \sum_{i=1}^{n} \alpha_iy_i = 0

? ? 而KKT條件（Karush-Kuhn-Tucker最優(yōu)化條件）

? ? ? ? 是拉格朗日乘子法的一種推廣，可以處理有不等號的約束條件

? ? 進一步簡化為對偶問題

????????L(w,b,\alpha) = \frac{1}{2}||w||^2 - \sum_{i=1}^{n} \alpha_i(y_i(w^Tx_i + b)-1)

? ? ? ? 上述問題可以改寫成：

????????????min_{w,b}\ max_{a_i\geq 0}\ L(w,b,\alpha) = p^*

? ? ? ? 可以等價為下列對偶問題：

????????????max_{a_i\geq 0}\ min_{w,b}\ L(w,b,\alpha) = d^*

????????????L(w,b,\alpha) = \frac{1}{2}||w||^2 - \sum_{i=1}^{n} \alpha_i(y_i(w^Tx_i + b)-1)

????????????????????\frac{\partial L}{\partial w} = 0 \rightarrow w = \sum_{i=1}^{n} \alpha_iy_ix_i

? ? ? ? ? ? ? ? ? ??\frac{\partial L}{\partial b} = 0 \rightarrow \sum_{i=1}^{n} \alpha_iy_i = 0

? ? ? ? ? ? 消除w，b——

????????????L(w,b,\alpha) = \sum_{i=1}^{n}\alpha_i - \frac{1}{2}\sum_{i,j=1}^{n}\alpha_i\alpha_jy_iy_jx_i^Tx_j

????????????max_{\alpha_i\geq 0}\ min_{w,b}\ L(w,b,\alpha) = max_\alpha\ [\sum_{i=1}^{k}\alpha_i - \frac{1}{2}\sum_{i,j=1}^{k}\alpha_i\alpha_jy_iy_jx_i^Tx_j]

? ? ? ? ? ? s.t.????\sum_{i=1}^{k}\alpha_iy_i = 0,\ \ \ \alpha_i \geq 0,i=1,2,...,n

????????????min_\alpha[\frac{1}{2}\sum_{i,j=1}^{k}\alpha_i\alpha_jy_iy_jx_i^Tx_j - \sum_{i=1}^{k}\alpha_i] = min_\alpha[\frac{1}{2}\sum_{i,j=1}^{k}\alpha_i\alpha_jy_iy_j(x_i.x_j) - \sum_{i=1}^{k}\alpha_i]

? ? ? ? ? ? s.t.????\sum_{i=1}^{k}\alpha_iy_i = 0,\ \ \ \alpha_i \geq 0,i=1,2,...,n

? ? ? ? ? ? 由此可得最優(yōu)解\alpha^*，帶入后得

????????????????w^* = \sum_{i=1}^{n}\alpha_i^*y_ix_i,\ \ \ \ b^* = y_i-(w^*)^Tx_i

SMO算法

? ? 針對線性SVM和稀疏數(shù)據(jù)時性能更優(yōu)

????min_\alpha[\frac{1}{2}\sum_{i,j=1}^{k}\alpha_i\alpha_jy_iy_jx_i^Tx_j - \sum_{i=1}^{k}\alpha_i] = min_\alpha[\frac{1}{2}\sum_{i,j=1}^{k}\alpha_i\alpha_jy_iy_j(x_i.x_j) - \sum_{i=1}^{k}\alpha_i]

? ? s.t. ?? \sum_{i=1}^{k}\alpha_iy_i = 0,\ \ \ \alpha_i \geq 0,i=1,2,...,n

? ? s.t.????C\geq \alpha_i \geq 0,\ \ \ i=1,2,...,n

? ? 基本思路是先根據(jù)約束條件隨機給\alpha賦值，然后每次選舉兩個\alpha，調(diào)節(jié)這兩個\alpha使得目標函數(shù)最小。然后再選取兩個\alpha，調(diào)節(jié)\alpha使得目標函數(shù)最小。以此類推


線性不可分的情況

? ? 引入松弛變量與懲罰函數(shù)

? ? 松弛變量\varepsilon

????????y_i(w_i.x_i+b)\geq 1-\varepsilon _i,\ \ \varepsilon _i\geq 0

? ? ? ? 約束條件沒有體現(xiàn)錯誤分類的點要盡量接近分類邊界

? ? 懲罰函數(shù)C\sum_{i=1}^{n}\varepsilon _i

????????min\frac{||w||^2}{2}+C\sum_{i=1}^{n}\varepsilon _i

? ? ? ? 使得分錯的點越少越好，距離分類邊界越近越好

? ? 線性不可分下的對偶問題：

? ? ——》min_\alpha[\frac{1}{2}\sum_{i,j=1}^{k}\alpha_i\alpha_jy_iy_jx_i^Tx_j - \sum_{i=1}^{k}\alpha_i] = min_\alpha[\frac{1}{2}\sum_{i,j=1}^{k}\alpha_i\alpha_jy_iy_j(x_i.x_j) - \sum_{i=1}^{k}\alpha_i]

? ? ? ? ? ? s.t.????\sum_{i=1}^{k}\alpha_iy_i = 0,\ \ \ \alpha_i \geq 0,i=1,2,...,n

? ? ? ? ? ? s.t.????C\geq \alpha_i \geq 0,\ \ \ i=1,2,...,n

eg：


????可知目標函數(shù)為：min_\alpha f(\alpha)， ?? s.t.????\alpha_1+\alpha_2 - \alpha_3=0，\alpha_i\geq 0,i=1,2,3

????其中????f(\alpha) = \frac{1}{2}\sum_{i,j=1}^{3}\alpha_i\alpha_jy_iy_j(x_i.x_j) - \sum_{i=1}^{3}\alpha_i

? ? ? ? ? ? ? ? ? ? ? ? ? ?=\frac{1}{2}(18\alpha_1^2+25\alpha_2^2+2\alpha_3^2+42\alpha_1\alpha_2 - 12\alpha_1\alpha_3-14\alpha_2\alpha_3) - \alpha_1-\alpha_2-\alpha_3

? ? 然后，將\alpha_3 = \alpha_1+\alpha_2帶入目標函數(shù)，得到一個關(guān)于\alpha_1和\alpha_2的函數(shù)

????????????????S(\alpha_1,\alpha_2) = 4\alpha_1^2+\frac{13}{2}\alpha_2^2+10\alpha_1\alpha_2-2\alpha_1-2\alpha_2

? ? 對\alpha_1，\alpha_2求偏導(dǎo)，并令其為0

? ? 可知S(\alpha_1,\alpha_2)在（1.5，-1）處取極值

? ? 而（1.5，-1）不滿足\alpha_i\geq 0的約束條件，可推斷最小值在邊界上達到

? ? 經(jīng)計算，

? ? ? ? 當(dāng)\alpha_1=0時，S(\alpha_1=0,\alpha_2=\frac{2}{13})=-0.1538

? ? ? ? 當(dāng)\alpha_2=0時，S(\alpha_1=\frac{1}{4},\alpha_2=0)=-0.25

? ? 所以，S(\alpha_1,\alpha_2)在\alpha_1=\frac{1}{4},\alpha_2=0時取最小值

? ? 此時可算出\alpha_3 = \alpha_1+\alpha_2=\frac{1}{4}

? ? 所以，\alpha_1,\alpha_3不等于0，所以對應(yīng)點x_1和x_3就應(yīng)該是支持向量

? ? 進而

????????w^* = \sum_{i=1}^{3}\alpha_i^*y_ix_i = \frac{1}{4}*(3,3)-\frac{1}{4}*(1,1)=(\frac{1}{2},\frac{1}{2})

? ? 即w_1 = w_2 = 0.5。進而有

????????b^* = 1-(w_1,w_2).(3,3)=-2

? ? 因此最大間隔分類超平面為

????????\frac{1}{2}x_1+\frac{1}{2}x_2-2=0

? ? 分類決策函數(shù)為

????????f(x) = sign(\frac{1}{2}x_1+\frac{1}{2}x_2-2)

非線性的情況

? ? 把低維空間的非線性問題映射到高維空間，變成求解線性問題

映射舉例：

? ? 3維輸入向量x=(x_1,x_2,x_3)

? ? 轉(zhuǎn)化到6維空間Z中去：

????????????\phi _1(x) = x_1,\phi _2(x) = x_2,\phi _3(x) = x_3,

????????????\phi _4(x) = (x_1)^2,\phi _5(x) = x_1x_2\ and\phi _3(x) = x_1x_3

? ? 新的決策超平面d(Z) = WZ+b，其中W和Z是向量，這個超平面是線性的，解出W和b之間，并且?guī)Щ卦匠?/p>

????????????d(Z) = W_1x_1+W_2x_2+W_3x_3+W_4(x_1)^2+W_5x_1x_2+W_6x_1x_3+b

? ? ? ? ? ? ? ? ? ? ? =W_1Z_1+W_2Z_2+W_3Z_3+W_4Z_4+W_5Z_5+W_6Z_6+b

存在的問題：

? ? 1、維度災(zāi)難

? ? 2、如何選擇合理的非線性轉(zhuǎn)換

? ? ? ? ? ? 核函數(shù)


? ? 我們可以構(gòu)造核函數(shù)使得運算結(jié)果等同于非線性映射，同時運算量要遠遠小于非線性映射

????????K(x_i,x_j) = \phi (x_i).\phi (x_j)

? ? h次多項式核函數(shù)：????K(x_i,x_j) =(x_i,x_j+1)^h

? ? 高斯徑向基函數(shù)核函數(shù)：????K(x_i,x_j) =e^{\frac{-||x_i-x_j||^2}{2\sigma ^2}}

? ? S型核函數(shù)：????K(x_i,x_j) =tanh(kx_i.x_j-\delta )

SVM優(yōu)點

? ? -算法復(fù)雜度由支持向量的個數(shù)決定，而非數(shù)據(jù)維度，所以不太易產(chǎn)生overfitting

? ? -SVM訓(xùn)練出來的模型完全依賴于支持向量（Support Vectors）即使訓(xùn)練集里面所有非支持向量的點都被去除，重復(fù)訓(xùn)練過程，結(jié)果仍會一樣

? ? -一個SVM如果訓(xùn)練得出的支持向量個數(shù)比較小，SVM訓(xùn)練出的模型比較容易泛化

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容