支援向量機|機器學習推導系列（七）

一、硬間隔SVM

1. 模型定義

假設有以下數據：

\left \{(x_{i},y_{i})\right \}_{i=1}^{N},x_{i}\in \mathbb{R}^{p},y_{i}\in \{+1,-1\}

SVM的主要思想是在特徵空間中尋找一個最大間隔的超平面w^{T}x+b實現數據的二分類，SVM屬於判別模型。這裡的間隔指的是樣本點到分離超平面的距離的最小值，用函數margin(w,b)來表達。下圖中在w\cdot x+b=1和w\cdot x+b=-1線上的樣本點就叫支援向量：

超平面實現將數據的正例和負例分隔開，因此有：

\left.\begin{matrix} y_{i}=+1,w^{T}x_{i}+b>0\\ y_{i}=-1,w^{T}x_{i}+b<0 \end{matrix}\right\}y_{i}(w^{T}x_{i}+b)>0,for\; \forall i=1,2,\cdots ,N

另外最大間隔通過以下方式來表達：

①\; 首先要明确样本点到超平面的距离公式：\\ distance(w,b,x_{i})=\frac{\left | w^{T}x+b\right |}{\left \| w\right \|}\\ (可以参考初中知识点：点到直线距离d=\frac{\left | Ax+By+C\right |}{\sqrt{A^{2}+B^{2}}})\\ ②\; 因此间隔可以表达为：\\ margin(w,b)=\underset{x_{i}}{min}\; distance(w,b,x_{i})=\underset{x_{i}}{min}\frac{\left | w^{T}x_{i}+b\right |}{\left \| w\right \|},i=1,2,\cdots ,N\\ ③\; 最大间隔可以表达为：\\ \underset{w,b}{max}\; margin(w,b)=\underset{w,b}{max}\; \underset{x_{i}}{min}\frac{\left | w^{T}x_{i}+b\right |}{\left \| w\right \|}=\underset{w,b}{max}\; \underset{x_{i}}{min}\frac{y_{i}(w^{T}x_{i}+b)}{\left \| w\right \|},i=1,2,\cdots ,N

然後求解支援向量機就可以轉化為以下帶約束的優化問題：

\left\{\begin{matrix} \underset{w,b}{max}\; margin(w,b)=\underset{w,b}{max}\; \underset{x_{i}}{min}\frac{y_{i}(w^{T}x_{i}+b)}{\left \| w\right \|},i=1,2,\cdots ,N\\ s.t.\; y_{i}(w^{T}x_{i}+b)>0,i=1,2,\cdots ,N \end{matrix}\right.

上述優化問題還可以進一步轉化：

由约束y_{i}(w^{T}x_{i}+b)>0,i=1,2,\cdots ,N可以得出\\ \exists \gamma >0使得\underset{x_{i}}{min}\; y_{i}(w^{T}x_{i}+b)=\gamma \\ 由于确定同一个超平面的w,b可以任意放缩，所以这里的\gamma 可以约束等于1。\\ 则\underset{w,b}{max}\; margin(w,b)\\ =\underset{w,b}{max}\; \underset{x_{i}}{min}\frac{y_{i}(w^{T}x_{i}+b)}{\left \| w\right \|}\\ =\underset{w,b}{max}\frac{1}{\left \| w\right \|}\underset{=\gamma =1}{\underbrace{\underset{x_{i}}{min}\; y_{i}(w^{T}x_{i}+b)}}\\ =\underset{w,b}{max}\frac{1}{\left \| w\right \|}\\ =\underset{w,b}{min}\frac{1}{2}w^{T}w\\ i=1,2,\cdots ,N

由此上述優化問題轉化為：

\left\{\begin{matrix} \underset{w,b}{min}\frac{1}{2}w^{T}w \\ s.t.\; y_{i}(w^{T}x_{i}+b)\geq 1,i=1,2,\cdots ,N \end{matrix}\right.

這是一個帶N個約束的凸優化問題。

2. 優化問題的轉化

上述優化問題可以使用拉格朗日乘子法來求解，構建拉格朗日函數：

L(w,b,\lambda )=\frac{1}{2}w^{T}w+\sum_{i=1}^{N}\lambda _{i}(1-y_{i}(w^{T}x_{i}+b))\\ \lambda =\begin{pmatrix} \lambda _{1} & \lambda _{2} & \cdots & \lambda _{N} \end{pmatrix}^{T}

然後上述優化問題就可以轉換為以下優化問題：

\left\{\begin{matrix} \underset{w,b}{min}\; \underset{\lambda }{max}L(w,b,\lambda )=\frac{1}{2}w^{T}w+\sum_{i=1}^{N}\lambda _{i}(1-y_{i}(w^{T}x_{i}+b))\\ s.t.\; \lambda _{i}\geq 0,i=1,2,\cdots ,N \end{matrix}\right.

我們可以簡單地看一下為什麼可以這麼轉化：

当1-y_{i}(w^{T}x_{i}+b)>0时，由于\lambda _{i}\geq 0，所以\underset{\lambda }{max}L(w,b,\lambda )=\infty \\ 当1-y_{i}(w^{T}x_{i}+b)\leq 0时，由于\lambda _{i}\geq 0，所以\underset{\lambda }{max}L(w,b,\lambda )=\frac{1}{2}w^{T}w \\ 因此\underset{w,b}{min}\; \underset{\lambda }{max}L(w,b,\lambda )=\underset{w,b}{min}\left \{\frac{1}{2}w^{T}w,\infty \right \}=\frac{1}{2}w^{T}w

然後使用以下結論繼續對該優化問題進行轉化：

min\; max\; L的对偶问题为max\; min\; L,有以下结论：\\ min\; max\; L\geq max\; min\; L\\ 可以简单地认为对于L先取最大，再从最大里面取最小就一定大于等于先取最小，再从最小里面取最大\\ 类似于“凤尾”\geq “鸡头”\\ 如果min\; max\; L是凸优化问题，所以min\; max\; L=max\; min\; L，为强对偶关系

因此該優化問題可以繼續轉化：

\left\{\begin{matrix} \underset{\lambda }{max}\; \underset{w,b}{min}\;L(w,b,\lambda )=\frac{1}{2}w^{T}w+\sum_{i=1}^{N}\lambda _{i}(1-y_{i}(w^{T}x_{i}+b))\\ s.t.\; \lambda _{i}\geq 0,i=1,2,\cdots ,N \end{matrix}\right.

總結一下，該優化問題經歷了以下轉化過程：

①\; 带约束优化问题\left\{\begin{matrix} \underset{w,b}{max}\; margin(w,b)=\underset{w,b}{max}\; \underset{x_{i}}{min}\frac{y_{i}(w^{T}x_{i}+b)}{\left \| w\right \|},i=1,2,\cdots ,N\\ s.t.\; y_{i}(w^{T}x_{i}+b)>0,i=1,2,\cdots ,N \end{matrix}\right.\\ ②\; 带约束优化问题\left\{\begin{matrix} \underset{w,b}{min}\;\frac{1}{2}w^{T}w\\ s.t.\; y_{i}(w^{T}x_{i}+b)\geq 1,i=1,2,\cdots ,N \end{matrix}\right.\\ ③\; 无约束优化问题\left\{\begin{matrix} \underset{w,b}{min}\; \underset{\lambda }{max}L(w,b,\lambda )=\frac{1}{2}w^{T}w+\sum_{i=1}^{N}\lambda _{i}(1-y_{i}(w^{T}x_{i}+b))\\ s.t.\; \lambda _{i}\geq 0,i=1,2,\cdots ,N \end{matrix}\right.\\ ④\; 无约束优化问题\left\{\begin{matrix} \underset{\lambda }{max}\; \underset{w,b}{min}\;L(w,b,\lambda )=\frac{1}{2}w^{T}w+\sum_{i=1}^{N}\lambda _{i}(1-y_{i}(w^{T}x_{i}+b))\\ s.t.\; \lambda _{i}\geq 0,i=1,2,\cdots ,N \end{matrix}\right.

3. 模型求解

  • 對b求導

\frac{\partial L}{\partial b}=\frac{\partial \sum_{i=1}^{N}\lambda _{i}-\sum_{i=1}^{N}\lambda _{i}y_{i}(w^{T}x_{i}+b)}{\partial b}=\frac{\partial -\sum_{i=1}^{N}\lambda _{i}y_{i}b}{\partial b}=-\sum_{i=1}^{N}\lambda _{i}y_{i}=0\\ 因此得出\sum_{i=1}^{N}\lambda _{i}y_{i}=0

  • 求解w

将上一步的结果代入L(w,b,\lambda )\\ L(w,b,\lambda )=\frac{1}{2}w^{T}w+\sum_{i=1}^{N}\lambda _{i}-\sum_{i=1}^{N}\lambda _{i}y_{i}w^{T}x_{i}-\underset{=0}{\underbrace{\sum_{i=1}^{N}\lambda _{i}y_{i}b}} \\ =\frac{1}{2}w^{T}w+\sum_{i=1}^{N}\lambda _{i}-\sum_{i=1}^{N}\lambda _{i}y_{i}w^{T}x_{i} \\ \frac{\partial L}{\partial w}=w-\sum_{i=1}^{N}\lambda _{i}y_{i}x_{i}=0 \\ 得出w^{*}=\sum_{i=1}^{N}\lambda _{i}y_{i}x_{i}

這裡我們可以看出w^{*}是數據的線性組合。

  • 得出\underset{w,b}{min}\;L(w,b,\lambda )

接着将上一步的结果代入L(w,b,\lambda )\\ \underset{w,b}{min}\;L(w,b,\lambda )=\frac{1}{2}(\sum_{i=1}^{N}\lambda _{i}y_{i}x_{i})^{T}(\sum_{j=1}^{N}\lambda _{j}y_{j}x_{j})+\sum_{i=1}^{N}\lambda _{i}-\sum_{i=1}^{N}\lambda _{i}y_{i}(\sum_{j=1}^{N}\lambda _{j}y_{j}x_{j})^{T}x_{i}\\ =\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda _{i}\lambda _{j}y_{i}y_{j}x_{i}^{T}x_{j}-\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda _{i}\lambda _{j}y_{i}y_{j}{\color{Red}{x_{j}^{T}x_{i}}}+\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}^{T}x_{j}-\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda _{i}\lambda _{j}y_{i}y_{j}{\color{Red}{x_{i}^{T}x_{j}}}+\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}^{T}x_{j}+\sum_{i=1}^{N}\lambda _{i}

因此該優化問題就相當於：

\left\{\begin{matrix} \underset{\lambda }{max}\; -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda _{i}\lambda _{j}y_{i}y_{j}x_{i}^{T}x_{j}+\sum_{i=1}^{N}\lambda _{i},i=1,2,\cdots ,N \\ s.t.\; \lambda _{i}\geq 0,i=1,2,\cdots ,N \end{matrix}\right.

也就相當於：

\left\{\begin{matrix} \underset{\lambda }{min}\; \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda _{i}\lambda _{j}y_{i}y_{j}x_{i}^{T}x_{j}-\sum_{i=1}^{N}\lambda _{i},i=1,2,\cdots ,N\\ s.t.\; \lambda _{i}\geq 0,i=1,2,\cdots ,N \end{matrix}\right.

  • KKT條件

首先定義該優化問題的KKT條件：

\left\{\begin{matrix} \frac{\partial L}{\partial w}=0,\frac{\partial L}{\partial b}=0\\ \lambda _{i}(1-y_{i}(w^{T}x_{i}+b))=0\\ \lambda _{i}\geq 0\\ 1-y_{i}(w^{T}x_{i}+b)\leq 0 \end{matrix}\right.

該優化問題滿足上述KKT條件，這是由於以下定理：

原问题、对偶问题具有强对偶关系\Leftrightarrow 满足KKT条件

KKT條件中\lambda _{i}(1-y_{i}(w^{T}x_{i}+b))=0也叫鬆弛互補條件，即\lambda _{i}和1-y_{i}(w^{T}x_{i}+b)總有一個為0。也就是說只有支援向量對應的\lambda _{i}才可能有值（\lambda _{i}\neq 0），而其他不在w\cdot x+b=1和w\cdot x+b=-1上的樣本點對應的\lambda _{i}一定為0，該性質可以用來求出b^{*}。

我們已經根據\frac{\partial L}{\partial w}=0求出了w^{*}，接下來要求出b^{*}，我們可以通過求解\underset{\lambda }{min}\; \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\lambda _{i}\lambda _{j}y_{i}y_{j}x_{i}^{T}x_{j}-\sum_{i=1}^{N}\lambda _{i},i=1,2,\cdots ,N\\來得出各個\lambda _{i}，而這個過程也是支援向量機演算法計算量最大的地方，這裡我們就不展示過程了。

找出求解得到的不等於0的\lambda _{i}，也就是支援向量對應的\lambda _{i}，假設其中一個支援向量為(x_{k},y_{k})，則有1-y_{k}(w^{T}x_{k}+b)=0，最終可以解得：

b^{*}=y_{k}-w^{T}x_{k}=y_{k}-\sum_{i=1}^{N}\lambda _{i}y_{i}x_{i}^{T}x^{k}

二、軟間隔SVM

我們的訓練數據通常不是理想的線性可分，有時甚至是線性不可分的數據。對於存在雜訊的一些數據，我們應該允許一點分類錯誤，因此我們需要對目標函數進行一些調整：

\underset{w,b}{min}\; \frac{1}{2}w^{T}w+loss

1. 使用誤分類點的個數作為loss

loss=\sum_{i=1}^{N}I\left \{y_{i}(w^{T}x_{i}+b)<1\right \}

顯然使用的指示函數是不連續的，不利於求解，所以不使用這種loss函數。

2. 使用距離作為loss

\left.\begin{matrix} 如果y_{i}(w^{T}x_{i}+b)\geq 1,loss=0\\ 如果y_{i}(w^{T}x_{i}+b)< 1,loss=1-y_{i}(w^{T}x_{i}+b) \end{matrix}\right\}loss=max\left \{0,1-y_{i}(w^{T}x_{i}+b)\right \}

該函數為合頁損失函數（hinge loss），令z=y_{i}(w^{T}x_{i}+b)，則loss對z的影像如下：

合頁損失函數

3. 軟間隔SVM的優化問題

\left\{\begin{matrix} \underset{w,b}{min}\; \frac{1}{2}w^{T}w+C\sum_{i=1}^{N}max\left \{0,1-y_{i}(w^{T}x_{i}+b)\right \}\\ s.t.\; y_{i}(w^{T}x_{i}+b)\geq 1,i=1,2,\cdots ,N \end{matrix}\right.

引入\xi _{i}=1-y_{i}(w^{T}x_{i}+b),\xi _{i}\geq 0,i=1,2,\cdots ,N，則該優化問題轉化為：

\left\{\begin{matrix} \underset{w,b}{min}\; \frac{1}{2}w^{T}w+C\sum_{i=1}^{N}\xi _{i}\\ s.t.\; y_{i}(w^{T}x_{i}+b)\geq 1-\xi _{i},i=1,2,\cdots ,N \end{matrix}\right.

上面的式子中，常數C可以看作允許的錯誤⽔平，同時上式為了進⼀步消除max符號，對數據集中的每⼀個觀測，我們可以認為其⼤部分滿⾜約束，但是其中部分違反約束，因此這部分約束變成y_{i}(w^{T}x_{i}+b)\geq 1-\xi _{i}。

軟間隔SVM也是使用拉格朗日乘子法進行求解。


Tags:

VirMach 便宜 VPS