Support Vector Machine

关于SVM的笔记，因为涉及多次对偶问题以及线性规划问题的求解，故记录下公式公式推导过程，以便对SVM的基本原理有更进一步的了解。

样本点的表示

设有 $m$ 个样本点 $D = \lbrace(X_1,y_1) ,(X_2,y_2)...(X_m,y_m) \rbrace$ 。
其中每个样本点为 $d$ 维 $X_i = (x_1, x_2...x_d)$ 。
每个样本的标签取值为 $y_i = \pm 1$ ， $+1$ 表示属于该标签， $-1$ 表示不属于

超平面的表示

设存在d维的超平面: $w_1x_1+w_2x_2 + ... w_dx_d + b = 0$
令 $W = (w_1,w_2 ... w_d)$
超平面方程可以写成:

$W^TX + b = 0$

(1.1)

$W$ 为超平面的法向量， $b$ 为超平面的位移。
特殊地，当d=2时超平面是一条直线： $w_1x_1 + w_2x_2 + b = 0$ 斜率 $-\cfrac{w_1}{w_2}$ ,截距 $-\cfrac{b}{w_2}$

正确分类的表示

如果一个样本 $(X_i, y_i)$ 正确分类，则必有：

$\begin{cases} W^TX_i+b \ge + 1 ,y_i= + 1 \\ W^TX_i+b \le - 1 ,y_i= - 1\end{cases}$

(1.4)

也就是如果超平面能正确分类样本点，则当样本点 $Y_i = +1$ 时，代入 $X_i$ 到超平面方程后得到的值是大于 $+1$ 的，反之当样本点 $Y_i = -1$ 时，代入 $X_i$ 到超平面方程后得到的值是小于 $-1$ 的。注意到 $Y_i$ 的取值仅仅是符号的作用，所以可以把式(1.4)简化为：

$y_i (W^TX_i+b) \ge 1$

(1.5)

样本点到超平面的距离

一个点 $X =(x_1, x_2, ..., x_d)$ 到超平面的距离可表示为

$d = \cfrac{\vert w_1x_1+w_2x_2 + ...w_dx_d + b \vert}{\sqrt{w_1^2+w_2^2 + ... w_d^2}}$

(1.2)

用矩阵的形式表示W和X，同时用 $\Vert w \Vert$ 表示 $\sqrt{w_1^2+w_2^2 + .. w_d^2}$ , 则式 $(1.2)$ 可以写成：

$d = \cfrac{\vert W^TX \vert}{\Vert w \Vert}$

(1.3)

目标函数的确立

当样本集严格线性可分时，存在不止一种 $W$ 和 $b$ 的组合满足上式。因此必须找出最优的超平面来分割。设 $y_i = +1$ 的样本为正样本, $y_i = -1$ 的样本为负样本，则最优的定义就是离超平面最近的正样本和负样本的距离都最大。设间隔为离超平面最近的正样本和负样本的距离之和，则目标就是找出一组 $W$ 和 $b$ 使得间隔的值最大。

设经过最近正样本的超平面为 $W^TX+b=1$ 也即 $W^TX+b-1=0$ , 经过最近负样本的超平面为 $W^TX+b +1 = 0$ 。由于 $W$ 相等故两直线平行，间隔为两平行线的距离：

$d = \cfrac{\vert (b-1) - (b+1) \vert}{\Vert w \Vert} = \cfrac{2}{\Vert w \Vert}$

(1.6)

由于最大化 $\cfrac{2}{\Vert w \Vert}$ 比较难计算，因此转化成最小化 $\cfrac{1}{2}\Vert w \Vert^2$

因为我们要在正确分类的前提下求间隔的最大值，也就是结合式(1.5)和(1.6）转化成一个在一定约束条件下的规划问题(1.7)。

$\begin{cases} \min\limits_{W, b} \cfrac{1}{2}\Vert w \Vert^2 \\ \text{subject to: } y_i (W^TX_i+b)\ge 1 , i = 1,2,3...m \end{cases}$

(1.7)

整合约束和目标函数

在特定约束下求最值时麻烦的，因为不能直接求目标函数最值，然后再去比较是否符合约束。最简单的方式就是引入拉格朗日算子将目标函数和约束整合在一起。设 $\alpha$ 是拉格朗日算子。
因为 $y_i (W^TX_i+b) \ge 1$ 可写成 $1-y_i (W^TX_i+b) \le 0$ ,则有