SVM入门到实现

2017-08-28

1.原始问题

输入：T=｛(x1,y1),(x2,y2),…,(xn,yn)｝,xi属于Rn，yi属于{-1,+1}

输出：w，b

学习目标：在特征空间找到一个超平面将实例分到不同的类。

分离超平面：w·x+b=0

分类决策函数：f(x)=sign(w·x+b)

在超平面确定的情况下，|w·x+b|可以相对的表示点x到超平面的距离远近。则可用y(w·x+b)表示分类的正确性及确信度。即函数间隔： $\widehat{\gamma} _{i}=y_{i}(w\cdot x_{i}+b)$

由于函数间隔不稳定（成倍改变w，b时超平面不变，函数间隔却会改变），所以引入几何间隔（一般是实例点到超平面的带符号距离）。即对w加以约束。如规范化||w||=1，使得间隔是确定的。

几何间隔： $\gamma _{i}=y_{i}(\frac{w}{||w||}\cdot x_{i}+\frac{b}{||w||})$

则目标为求得一个几何间隔最大的分离超平面。可表示如下： $max_{w,b} \gamma$ s.t. 　 $y_{i}(\frac{w}{||w||}\cdot x_{i}+\frac{b}{||w||}) \geqslant \gamma ,i=1,2,...,N$

其中几何间隔可以等价为函数间隔 / ||w||=1，同时对于最优化问题，函数间隔的取值不影响解。（因为w，b按比例乘以k，那么函数间隔也变成k倍，即函数间隔*k / ||kw||=函数间隔 / ||w||）这样就可以取函数间隔=1.代入后注意到最大化1/||w|| 等价于最小化||w||。

所以得到SVM最优化问题：

$min_{w,b} \frac{1}{2}||w||^{2}$ s.t. 　 $y_{i}(w\cdot x_{i}+b)-1\geqslant 0,i=1,2,...,N$

2.软间隔问题

线性不可分时的线性支持向量机：考虑训练数据中少量的特异点。对每个样本点引入松弛变量 $\xi_{i}\geq 0$ ，同时支付一个代价。

则原始问题变为如下凸二次规划问题：

$min_{w,b,\xi }　 \frac{1}{2}||w||^{2}+C\sum_{i=1}^{N}\xi _{i}$ s.t. 　 $y_{i}(w\cdot x_{i}+b)\geq 1-\xi_{i},i=1,2,...N$ 　　　 $\xi _{i}\geq 0,i=1,2,...N$

3.拉格朗日对偶问题

优点：1.对偶问题更容易求解；2.可以自然引入核函数。

拉格朗日函数：

　　　 $L(w,b,\xi ,\alpha ,\mu )\equiv \frac{1}{2}||w||^{2}+C\sum_{N}^{i=1}\xi _{i} -\sum_{N}^{i=1}\alpha _{i}(y_{i}(w\cdot x_{i}+b)-1+\xi _{i})-\sum_{N}^{i=1}\mu_{i}\xi _{i}$ 其中， $\alpha_{i} \geq 0,\mu_{i}\geq 0$ 。

则原始问题等价于拉格朗日函数的极小极大问题： $min_{w,b,\xi }max_{\alpha,\mu }L(w,b,\alpha )$

则对偶问题为极大极小问题： $max_{\alpha,\mu }min_{w,b,\xi }L(w,b,\alpha )$

首先求L对 $w,b,\xi$ 的极小：　　　 $\bigtriangledown _{w}L(w,b,\xi,\alpha,\mu)=w-\sum_{i=1}^{N}\alpha_{i}y_{i}x_{i}=0$ 　　　 $\bigtriangledown _{b}L(w,b,\xi,\alpha,\mu)=-\sum_{i=1}^{N}\alpha_{i}y_{i}=0$ 　　　 $\bigtriangledown _{\xi _{i}}L(w,b,\xi,\alpha,\mu)=C-\alpha_{i}-\mu _{i}=0$ 可得：　　　 $w=\sum_{i=1}^{N}\alpha_{i}y_{i}x_{i}$ 　　　 $\sum_{i=1}^{N}\alpha_{i}y_{i}=0$ 　　　 $C-\alpha_{i}-\mu _{i}=0$ 将上面三个式子代入到拉格朗日函数 $L(w,b,\xi,\alpha,\mu)$ 中，得：　　　 $min_{w,b,\xi }L(w,b,\xi,\alpha,\mu)=-\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}$

再对上式求α的极大，即得对偶问题：

　　　 $max_{\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$ 　　　　　　 $0\leq \alpha \leq C$ 其中，由约束 $C-\alpha_{i}-\mu _{i}=0$ , $\alpha_{i} \geq 0,\mu_{i}\geq 0$ 消去ui可得 $0\leq \alpha \leq C$

原问题是凸二次规划问题，解满足KKT条件。设对偶问题的解为： $\alpha^{*}=(\alpha_{1}^{*},\alpha_{2}^{*},...,\alpha_{N}^{*})^{T}$ 若存在α * 的一个分量j满足 $0< \alpha_{j}^{*}< C$ ，则原始问题解w，b为：　　　　　　 $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})$

4.SMO算法

问题变为求解对偶问题的解α。编程求解时一般初始化α为全0。

SMO思路：若所有变量的解都满足此优化问题的KKT条件，则解就得到了。否则，选择两个变量，固定其他变量，针对这两个变量构建一个二次规划问题。子问题有两个变量，一个是选择违反KKT条件最严重的那一个，另一个由约束条件自动确定。

整个SMO算法包含两个部分：求解两个变量二次规划的解析方法和选择变量的启发式方法。

于是SMO的最优化问题的子问题为：

$min_{\alpha_{1} \alpha_{2} } W(\alpha_{1} \alpha_{2})=\frac{1}{2}K_{11}\alpha _{1}^{2}+\frac{1}{2}K_{22}\alpha _{2}^{2}+y_{1}y_{2}K_{12}\alpha _{1}\alpha _{2}-(\alpha _{1}+\alpha _{2})+y_{1}\alpha _{1}\sum_{i=3}^{N}y_{i}\alpha _{i}K_{i1}+y_{2}\alpha _{2}\sum_{i=3}^{N}y_{i}\alpha _{i}K_{i2}$ 　　　　s.t.　　 $\alpha _{1}y_{1}+\alpha _{2}y_{2}=-\sum_{i=3}^{N}y_{i}\alpha _{i}=\zeta$ 　　　　　　　 $0< \alpha_{i}< C,i=1,2$ 其中Kij=K(xi,xj)，ζ为常数，且上式省略了不含α1，α2的常数项。

设问题初始可行解为 $\alpha_{1}^{old},\alpha_{2}^{old}$ ，最优解为 $\alpha_{1}^{new},\alpha_{2}^{new}$ ，且假设在沿着约束方向未经剪辑时α2的最优解为 $\alpha_{2}^{new,unc}$ 。

记， $g(x)=\sum_{i=1}^{N}\alpha _{i}y_{i}K(x_{1},x)+b$ 令 $E_{i}=g(x_{i})-y_{i}= \left [ \sum_{j=1}^{N}\alpha _{j}y_{j}K(x_{j},x_{i})+b\right ]-y_{i},i=1,2$ 则有：　　　　　　 $\alpha _{2}^{new,unc}=\alpha _{2}^{old}+\frac{y_{2}(E_{1}-E_{2})}{\eta }$ 其中，　　　　　 $\eta=K_{11}+K_{22}-2K_{12}=||\Phi(x_{1}) -\Phi(x_{2})||^{2}$

由于α的不等式约束，最优值范围要满足： $L\leq \alpha_{2}^{new}\leq H$ 其中L,H是α2对角线段端点的界，且有　　　　　　 $\left\{\begin{matrix}y_{1}\neq y_{2}\left\{\begin{matrix} L=max(0,\alpha _{2}^{old}-\alpha _{1}^{old})\\ H=min(C,C+\alpha _{2}^{old}-\alpha _{1}^{old}) \end{matrix}\right. \\ y_{1}= y_{2}\left\{\begin{matrix} L=max(0,\alpha _{2}^{old}+\alpha _{1}^{old}-C)\\ H=min(C,\alpha _{2}^{old}+\alpha _{1}^{old}) \end{matrix}\right. \end{matrix}\right.$

则有： $\alpha _{2}^{new}=\left\{\begin{matrix} H,\alpha _{2}^{new,unc}>H\\ \alpha _{2}^{new,unc},L\leq \alpha _{2}^{new,unc}\leq H \\ L,\alpha _{2}^{new,unc}<L \end{matrix}\right.$

同时可求得： $\alpha _{1}^{new}=\alpha _{1}^{old}+y_{1}y_{2}(\alpha _{2}^{old}-\alpha _{2}^{new})$

变量的选择方法

SMO算法再每个子问题中选择两个变量优化，其中至少一个变量是违反KKT条件的。

1.第一个变量(外层循环) 在训练样本中选择违反KKT条件最严重的样本点。即检查是否满足KKT条件：　　　　　 $\begin{matrix} \alpha _{i}=0\Leftrightarrow y_{i}g(x_{i})\geq 1 \\ 0<\alpha _{i}<C\Leftrightarrow y_{i}g(x_{i})=1 \\ \alpha _{i}=C\Leftrightarrow y_{i}g(x_{i})\leq 1 \end{matrix}$ 其中， $g(x_{i})=\sum_{j=1}^{N}\alpha _{j}y_{j}K(x_{i},x_{j})+b$

2.第二个变量(内层循环) 标准是希望使α2能有足够变化。为了加快计算速度，一种简单做法是选择α2是其对应|E1-E2|最大。即若E1为正，则选最小的Ei为E2；反之E1为负选最大的Ei为E2.

3.计算阈值b和差值Ei 每次完成两个变量优化后都要重新计算b。由KKT条件：

若 $0<\alpha_{1}^{new}<C$ ： $b_{1}^{new}=-E_{1}-y_{1}K_{11}(\alpha _{1}^{new}-\alpha _{1}^{old})-y_{2}K_{21}(\alpha _{2}^{new}-\alpha _{2}^{old})+b^{old}$ 若 $0<\alpha_{2}^{new}<C$ ： $b_{2}^{new}=-E_{2}-y_{1}K_{12}(\alpha _{1}^{new}-\alpha _{1}^{old})-y_{2}K_{22}(\alpha _{2}^{new}-\alpha _{2}^{old})+b^{old}$

若 $\alpha _{1}^{new},\alpha _{2}^{new}$ 都满足大于0小于C，则b1new=b2new。若 $\alpha _{1}^{new},\alpha _{2}^{new}$ 是0或C，则b1_new和b2_new及之间的数都符合KKT条件，这时选择他们中点作为b_new.

每次优化后还必须更新对应的Ei值，并保存再列表中： $E_{i}^{new}=\sum_{S}y_{j}\alpha _{j}K(x_{i},x_{j})+b^{new}-y_{i}$ 其中S是所有支持向量xj的集合。

END

参考资料：《统计学习方法》

Coding

Writing

Living