区97视频,国产美女视频福利

〇、說明

支持向量機(jī)(Support Vector Machine,SVM)是監(jiān)督學(xué)習(xí)中非常經(jīng)典的算法。筆者主要參考學(xué)習(xí)的是李航老師《統(tǒng)計(jì)學(xué)習(xí)方法（第二版）》[1]和周志華老師的西瓜書《機(jī)器學(xué)習(xí)》[2]。

如有錯(cuò)誤疏漏，煩請(qǐng)指正。如要轉(zhuǎn)載，請(qǐng)聯(lián)系筆者，hpfhepf@gmail.com。

一、問題描述

如此系列筆記的上一篇《支持向量機(jī)（一）——線性可分支持向量機(jī)導(dǎo)出》[3]所述，給定線性可分訓(xùn)練數(shù)據(jù)集 $T=\{(x_{1},y_{1}),(x_{2},y_{2}),…(x_{N},y_{N})\}$ ，其中 $x_{i}\in \mathcal X = \mathbb{R}^n$ ， $y_{i}\in \mathcal{Y}=\{+1,-1\}$ ， $i=1,2,\cdot \cdot \cdot ,N$ 。

求解如下優(yōu)化問題的最優(yōu)解

優(yōu)化問題一：

$\begin{split}&\mathop{min}\limits_{w,b} \quad & \frac{1}{2} ||w||^2 \\&s.t. & y_{i}(w\cdot x_{i}+b) \geq 1,\ \ i=1,2,\dots,N\end{split} \tag{1}$

可得最大間隔分離超平面

$w^*\cdot x+b^* =0 \tag{2}$

和對(duì)應(yīng)的分類決策函數(shù)

$f(x)=sign(w^* \cdot x +b^*) \tag{3}$

二、朗格朗日對(duì)偶算法

優(yōu)化問題一（式 $(1)$ ）是一個(gè)凸二次規(guī)劃問題，可以通過求解拉格朗日對(duì)偶問題來求解。關(guān)于凸優(yōu)化內(nèi)容可以參見筆者相關(guān)筆記。

構(gòu)建拉格朗日函數(shù)

$L(w,b; \alpha )=\frac{1}{2}||w||^2+\sum_{i=1}^N\alpha_{i}(1-y_{i}(w\cdot x_{i}+b)) \tag{4}$

其中， $\alpha =(\alpha_{1},\alpha_{2},\dots,\alpha_{N})^T,\ \alpha_{i} \geq 0$ 為拉格朗日乘子組成的向量。

原問題是凸優(yōu)化問題，則拉格朗日強(qiáng)對(duì)偶性成立，所以如下優(yōu)化問題和原優(yōu)化問題等價(jià)，具體請(qǐng)參見[4]

優(yōu)化問題二：

$\mathop{max}\limits_{\alpha} \ \mathop{min}\limits_{w,b} \ L(w,b;\alpha) \tag{5}$

也就是說，優(yōu)化問題二的最優(yōu)解，即是優(yōu)化問題一的最優(yōu)解。

三、求解拉格朗日對(duì)偶問題

第一步，先求解 $\mathop{min}\limits_{w,b} \ L(w,b;\alpha)$

對(duì)拉格朗日函數(shù)分別對(duì) $w$ 和 $b$ 求偏導(dǎo)，并令其等于0。

$\frac{\partial}{\partial w} L(w,b;\alpha)=w-\sum_{i=1}^N \alpha_{i}y_{i}x_{i}=0 \tag{6}$

$\frac{\partial}{\partial b} L(w,b;\alpha)=-\sum_{i=1}^N \alpha_{i}y_{i}=0 \tag{7}$

可得

$w=\sum_{i=1}^N \alpha_{i}y_{i}x_{i} \tag{8}$

$\sum_{i=1}^N \alpha_{i}y_{i}=0 \tag{9}$

將 $(8)$ 式和 $(9)$ 式代入拉格朗日函數(shù)（ $(4)$ 式）

$\begin{align}L(w,b;\alpha) =& \frac{1}{2} ||w||^2 + \sum_{i=1}^N \alpha_{i}y_{i}(1-(w \cdot x_{i}+b)) \\=& \frac{1}{2} \sum_{i=1}^N\sum_{j=1}^N \alpha_{i} \alpha_{j} y_{i} y_{j}(x_{i} \cdot x_{j}) + \sum_{i=1}^N \alpha_{i} y_{i} - \sum_{i}^N \alpha_{i} y_{i}((\sum_{j=1}^N \alpha_{j} y_{j} x_{j}) \cdot x_{i}) - b \sum_{i=1}^N \alpha_{i} y_{i} + \sum_{i=1}^N \alpha_{i} \\=& -\frac{1}{2} \sum_{i=1}^N\sum_{j=1}^N \alpha_{i} \alpha_{j} y_{i} y_{j}(x_{i} \cdot x_{j}) + \sum_{i=1}^N \alpha_{i} \end{align}$

也即

$\mathop{min}\limits_{w,b} L(w,b;\alpha) = -\frac{1}{2} \sum_{i=1}^N\sum_{j=1}^N \alpha_{i} \alpha_{j} y_{i} y_{j}(x_{i} \cdot x_{j}) + \sum_{i=1}^N \alpha_{i} \tag{10}$

第二步，求解對(duì)偶問題 $\mathop{max}\limits_{\alpha}\ \mathop{min}\limits_{w,b} \ L(w,b;\alpha)$

由 $(10)$ 式和 $(9)$ 式，可得

優(yōu)化問題三：

$\begin{split}&\mathop{min}\limits_{\alpha} \ &\frac{1}{2} \sum_{i=1}^N\sum_{j=1}^N \alpha_{i} \alpha_{j} y_{i} y_{j}(x_{i} \cdot x_{j}) - \sum_{i=1}^N \alpha_{i} \\& s.t. & \sum_{i=1}^N \alpha_{i} y_{i}=0 \\&& \alpha_{i} \geq 0, \ \ i=1,2,\dots,N\end{split} \tag{11}$

這就是線性可分支持向量機(jī)的對(duì)偶優(yōu)化問題。求解此優(yōu)化問題請(qǐng)參見此系列筆記的后續(xù)篇章（敬請(qǐng)期待）。

第三步，求解分類超平面 $(w^*,b^*)$ 和分類模型

當(dāng)求解優(yōu)化問題三（式 $(11)$ ）的最優(yōu)解為 $\alpha^* = (\alpha^*_{1},\alpha^*_{2},\dots,\alpha^*_{N})^T$ ，根據(jù)式 $(8)$ 可得

$w^*=\sum_{i=1}^N \alpha^*_{i}y_{i}x_{i} \tag{12}$

接下來求解截距 $b$ 的最優(yōu)解 $b^*$ 。

根據(jù)凸優(yōu)化問題的KTT條件：優(yōu)化問題一（式 $(1)$ ）是凸優(yōu)化問題，則滿足KKT條件的點(diǎn)是原問題和對(duì)偶問題的最優(yōu)解（具體請(qǐng)參見[4]）。

$\begin{align}& y_{i}(w^*\cdot x_{i}+b^*) \geq 1,\ \ i=1,2,\dots,N \tag{13a} \\& \alpha^*_{i}(1-y_{i}(w^* \cdot x_{i}+b^*))=0,\ \ i=1,2,\dots,N \tag{13b} \\& \alpha^*_{i} \geq 0 ,\ \ i=1,2,\dots,N \tag{13c}\\& \frac{\partial}{\partial w} L(w^*,b^*;\alpha^*)=w^*-\sum_{i=1}^N \alpha^*_{i}y_{i}x_{i}=0 \tag{13d} \\& \frac{\partial}{\partial b} L(w^*,b^*;\alpha^*)=-\sum_{i=1}^N \alpha^*_{i}y_{i}=0 \tag{13e}\end{align}$

由式 $(13d)$ 也可得出式 $(12)$ 。

將式 $(13b)$ 單獨(dú)拿出來，在 $\alpha^*_{i},\ i=1,2,\dots,N$ 中選擇一個(gè) $\alpha^*_{i}>0$ (支持向量)，則有

$\begin{align}& y_{i}(w^*_{i} \cdot x_{i}+b^*)-1=0 \tag{14a}\\\implies \ & y_{i}=w^*_{i}\cdot x_{i}+b^* \tag{14b}\\\implies \ & b* =y^*_{i}-w^*\cdot x_{i} \tag{14c}\end{align}$

將式 $(12)$ 代入式 $(14c)$ ，對(duì)于任一 $\alpha_{j} >0$ ，有

$b* =y^*_{j}-\sum_{i=1}^N \alpha^*_{i}y_{i}(x_{i} \cdot x_{j}) \tag{15}$

到此，對(duì)于已經(jīng)求出優(yōu)化問題的朗格朗日乘子的最優(yōu)解 $\alpha^*=(\alpha^*_{1},\alpha^*_{2}, \dots,\alpha^*_{N})^T$ ，則線性可分支持向量機(jī)的最優(yōu)超平面為 $w^*\cdot x+b^* = 0$ 的參數(shù)為

$\begin{align}& w^*=\sum_{i=1}^N \alpha^*_{i}y_{i}x_{i} \\& b* =y^*_{j}-\sum_{i=1}^N \alpha^*_{i}y_{i}(x_{i} \cdot x_{j}) , \ \alpha^*_{j} >0 \end{align}\tag{16}$