線性SVM的推導

文章出處

線性SVM算法的一般過程

超平面方程

SVM是用來分類的。給定一系列輸入數據（n維向量），需要找到一個切分界線（n-1維的超平面），這里假定數據是線性可分的。比如，二維數據的超平面是直線，三維數據的超平面是二維平面。以二維數據為例：

二維平面的直線一般式：$Ax+By+C=0$，可以寫成向量的形式：
$$
\pmatrix {A B}\pmatrix {x\y}+C=0
$$
令$\vec w=\pmatrix {A\B}$,$\vec x=\pmatrix{x\y}$，$b=C$，則有：
$$
\vec w^T \vec x + b = 0
$$
這里的向量都是列向量。懂線性代數學的請無視~
將上述公式中向量的維度推廣到n維，就得到n維數據的超平面。直觀理解就是兩個類別的分界。

functional margin

functional margin直譯是：函數間距。聽起來抽象~
在前面定義的超平面公式基礎上，設$f(\vec x)=\vec w^T \vec x + b$，則：
$$
f(\vec x)表示\begin{cases}
超平面左側的數據點, &f(\vec x)>0\cr 超平面上的數據點, &f(\vec x)=0 \cr 超平面右側的數據點, &f(\vec x)<0\end{cases}
$$
超平面上的點顯然是幾乎沒有的，暫不考慮，剩余的就是兩個類別各自的數據點了，分居在超平面兩側。按慣例用$y_i$表示第$i$個類別，這里取：
$$
y=sign(f(\vec x))=\begin{cases}1, f(\vec x)<0 \cr -1, f(\vec x)>0 \end{cases}
$$
這里用1和-1而不是0和-1，是為了后續推導方便。$sign(x)$是取符號函數。

好了，終于可以定義functional margin了：
$$
\hat \gamma = y(\vec w^T\vec x + b) = yf(\vec x) = sign(f(\vec x))f(\vec x)=|f(\vec x)|
$$
用$f(\vec x)$和它的符號相乘，得到的結果始終是正的:$\forall \vec x, \hat \gamma > 0$。

geometrical margin

geometrical margin直譯為幾何距離，也就是點到超平面的距離，也就是點到直線距離再乘以1或者-1。1和-1分別對應兩個分類，也就是分類標簽$y$的取值。前面對于$y$值的設定就是為此處考慮的。

如圖，$\vec x_0$是超平面上一點，$\vec x$是任意一個點。這兩個點都是n維向量，先試著計算它們的距離$\gamma$：
$$
\gamma=d(\vec x, \vec x_0)=||\vec x - \vec x_0|| \
=\frac{\vec x - \vec x_0}{\vec e} \
=\frac{\vec x - \vec x_0}{\frac{\vec w}{||\vec w||}} \
=>...
$$
這里的問題在于，使用了向量除法，其中$\vec e$表示和$\vec x - \vec x_0$同方向的單位向量，雖然類似定比分點的公式，但是還是不嚴格。好在只要稍微轉換下書寫形式，把除法寫成乘法，就OK了:
$$
\vec x-\vec x_0 = \gamma \vec e =\gamma \frac{\vec w}{||\vec w||} \左乘\vec w^T:
\vec w^T(\vec x-\vec x_0)=\gamma \frac{\vec w^T \vec w}{||\vec w||} \
考慮f(\vec x_0)=0,f(\vec x)=\vec w^T\vec x，且\frac{\vec w^T \vec w}{||\vec w||}=||\vec w|| \因此有：
\gamma=\frac{f(\vec x)}{||\vec w||}
$$
需要指出的是：這里的$\vec x$不一定處在$\vec w$所指向的一側，它也許在相反一側，因而$\gamma$可正可負，所以需要定義一個始終是正值的幾何距離，即：根據functional margin來定義geometrical margin：
$$
\hat \gamma=yf(\vec x) \
\gamma=\frac{f(\vec x)}{||\vec w||} \
=>\tilde \gamma=y\gamma = \frac{\hat \gamma}{||\vec w||}
$$
注意!這里出現了新變量$\tilde \gamma$，是geometrical margin；$\hat \gamma$則表示functional margin；$\gamma$則表示向量$\vec x$和$\vec x_0$之間的距離。顯然，$\tilde \gamma$和$\hat \gamma$只相差一個縮放因子$||\vec w||$，而且他們都是大于0的值。

最大化幾何距離$\tilde \gamma$

前面引入了超平面、幾何距離等概念。顯然超平面上的點其所屬類別是模糊的，而當超平面上的點離開超平面，離開的越遠，其所屬分類就越明晰，也有人稱為：當點到超平面的margin越大，分類的confidence越大。總之，要讓分類效果明顯，就應當設法最大化margin。成千上萬的數據點，都去計算margin肯定不行，而且顯然只需要考慮距離超平面最近的那些點：這些點就是支持向量，支持向量到超平面的margin是所有點中最小的那一撮，設法最大化它們的margin就能完成最終的分類任務了。

那么，該最大化哪個margin呢？$\tilde \gamma$還是$\hat \gamma$呢？$\tilde \gamma$表示的是幾何距離，直覺上應該選擇它。試著考慮其具體表達式:
$$
\hat \gamma=|\vec w^T\vec x+b| \
\tilde \gamma=\frac{|\vec w^T\vec x+b|}{||\vec w||} \
=|\frac{\vec w^T}{||\vec w||}\vec x+\frac{b}{||\vec w||}|
$$
對于一個確定的超平面，$\vec w$和$b$的取值并不唯一，$||\vec w||$可大可小，通過縮放$\vec w$和$b$能保持超平面不變。但$\frac{\vec w}{||\vec w||}$和$\frac{b}{\vec w}$是唯一的，因而考慮最大化$\tilde \gamma$。實際上，不妨取$||\vec w||=1$，那么等比例縮放$b$，就能保持等式成立，而且此時$\hat \gamma$和$\tilde \gamma$取值相等。

此時，我們對于訓練數據集$S={x^{(i)}, y^{(i)};i=1,...,m}$，我們重新定義參數$(\vec w,b)$下的geometrical margin為：
$$\gamma=\min_{i=1,...,m} \gamma^{(i)}$$
直觀理解為：將超平面向1和-1兩個類的方向分別移動，最先觸碰到的那些點到分界超平面的距離為幾何距離$\gamma$。而這些最先被觸碰到的點，稱為支持向量(support vector)。當然，先前處于分界超平面上的點不算。

進一步確定極值條件

當前的目標是:
$$
\max (\min d(\vec x, \vec x_0))
$$，也就是：
$$
\max_{\gamma,\vec w,b} \frac {\hat \gamma}{||\vec w||} \
s.t.     y_i(\vec w^T \vec x_i+b) \ge \gamma,   i=1,...,m
$$
這里從凸優化的方法，否定了取$||\vec w||=1$的做法，采取了讓$\hat \gamma=1$的做法：支持向量到分解超平面的幾何距離為1。而最小化"支持向量到分界超平面的幾何距離"，等價于“最小化支持向量之間在垂直于分界超平面的方向上的距離”，也就是：
$$
\max Margin = 2/||\vec w||     (cond1)
$$
同時，現在的情況是：不算分界超平面上的點，所有點滿足：
$\vec w^T \vec x_i+b \ge 1$，對于所有$y_i=1$
$\vec w^T \vec x_i+b \le -1$，對于所有$y_i=-1$
也就是：
$$
y_i(\vec w^T \vec x_i + b)-1 \ge 0     (cond2)
$$
要滿足cond1和cond2，就能得到最終解。而cond1等價于：計算$\min ||\vec w||^2/2$。
對于不等式約束的條件極值問題，可以用拉格朗日方法求解。而拉格朗日方程的構造規則是：用約束方程乘以非負的拉格朗日系數，然后再從目標函數中減去。于是得到拉格朗日方程如下：
$$
L(\vec w,b,\alpha_i)=\frac{1}{2}||\vec w||^2-\sum_{i=1}^{l}\alpha_i(y_i(\vec w^T \vec x_i+b)-1)=\frac{1}{2}||\vec w||^2-\sum_{i=1}^{l}\alpha_i y_i(\vec w^T \vec x_i+b)+\sum_{i=1}^{l}\alpha_i
$$
其中：
$$
\alpha_i \ge 0     (4)
$$
那么我們要處理的規劃問題就變為：
$$
\min_{\vec w,b} \max_{\alpha_i \ge 0} L(\vec w,b,\alpha_i)     (5)
$$
上市才是嚴格的不等式約束的拉格朗日條件極值的表達式。對于這一步的變換，很多文章都沒有多做表述，或者理解有偏差，從而影響了讀者后續的推演。在此我將詳細地一步步推導，以解困惑。
（5）式是一個凸規劃問題，其意義是先對$\alpha$求偏導，令其等于0消掉α，然后再對w和b求L的最小值。要直接求解（5）式是有難度的，通過消去拉格朗日系數來化簡方程，對我們的問題無濟于事。所幸這個問題可以通過拉格朗日對偶問題來解決，為此我們把（5）式做一個等價變換：
$$
\min_{\vec w, b} \max_{\alpha_i \ge 0} L(\vec w,b,\alpha_i)= \max_{\alpha_i \ge 0}L(\vec w,b,\alpha_i)
$$
上式即為對偶變換，這樣就把這個凸規劃問題轉換成了對偶問題：
$$
\max_{\alpha_i \ge 0} \min_{\vec w,b}L(\vec w, b, \alpha_i)     (6)
$$
其意義是：原凸規劃問題可以轉化為先對w和b求偏導，令其等于0消掉w和b，然后再對α求L的最大值。下面我們就來求解（6）式，為此我們先計算w和b的偏導數。由（3）式有：
$$
\frac{\partial L(\vec w,b,\alpha_i)}{\partial \vec w}=\vec w-\sum_{i=1}^{l}\alpha_i y_i x_i \
\frac{\partial L(\vec w,b,\alpha_i)}{\partial b}=-\sum_{i=1}^{l}\alpha_i y_i     (7)
$$
為了讓L在w和b上取到最小值，令（7）式的兩個偏導數分別為0，于是得到：
$$
\vec w=\sim_{i=1}^{l}\alpha_i y_i x_i \
\sum_{i=1}^{l}\alpha_i y_i=0     (8)
$$
將（8）代回（3）式，可得：

再把（9）代入（6）式有：
$$
\max_{\alpha_i \ge 0} \min_{\vec w,b}L(\vec w,b,\alpha_i)=\max_{\alpha_i \ge 0}=\max_{\alpha_i \ge 0}{\sum_{i=1}^{l}\alpha_i-\frac{1}{2}\sum_{i=1}^{l}\sum_{j=1}^{l}\alpha_i \alpha_j y_i y_j(x_i·x_j)}     (10)
$$
考慮到（8）式，我們的對偶問題就變為：
$$
\max_{\alpha_i}{\sum_{i=1}^{l}\alpha_i}-\frac{1}{2}\sum_{i=1}^{l}\sum_{j=1}^{l}\alpha_i \alpha_j y_i y_j(x_i · x_j) \
s.t.   \sum_{\alpha_i}^{y_i}=0 \
\alpha_i \ge 0
$$
上式這個規劃問題可以直接從數值方法計算求解。
需要指出的一點是，（2）式的條件極值問題能夠轉化為（5）式的凸規劃問題，其中隱含著一個約束，即
$$
\alpha_i(y_i(\vec w · x_i + b)-1)=0     (12)
$$
這個約束是這樣得來的，如果（2）和（5）等效，必有：
$$
\max_{\alpha_i \ge 0}L(\vec w, b, \alpha_i) = \frac{1}{2}||\vec w||^2
$$
把（3）式代入上式中，得到：

化簡得到：
$$
\min_{\alpha_i \ge 0}{\sum_{i=1}^{l}\alpha_i (y_i(\vec w · x_i + b)-1)}=0     (13)
$$
又因為約束（1）式和（4）式，有：

所以要使（13）式成立，只有令：$\alpha_i(y_i(\vec w·x_i + b)-1) = 0$，由此得到（12）式的約束。該約束的意義是：如果一個樣本是支持向量，則其對應的拉格朗日系數非零；如果一個樣本不是支持向量，則其對應的拉格朗日系數一定為0。由此可知大多數拉格朗日系數都是0。

一旦我們從（11）式求解出所有拉格朗日系數，就可以通過（8）式的
$$
\vec w=\sum_{i=1}^{l}\alpha_i y_i x_i
$$
計算得到最優分割面H的法向量w。而分割閾值b也可以通過（12）式的約束用支持向量計算出來。這樣我們就找到了最優的H1和H2，這就是我們訓練出來的SVM。