SVM

作者: BigPeter | 来源:发表于2018-12-12 23:10 被阅读0次

概述

支持向量机（Support Vector Machine）是一个分类算法，主要思想是间隔最大化。推导过程中将间隔最大化转化为带约束条件的凸优化问题，通过引入拉格朗日乘子法和对偶学习法来简化该优化问题，最后转为为拉格朗日乘子的带约束条件的优化问题。在整个推导过程中由于引入对偶学习很自然的引入了核方法。最后的优化问题通过SMO算法解决。

线性可分支持向量机

对于线性可分数据集，一定存在将数据集完全分离的超平面，假设某分离超平面是 $y=w^Tx+b$ ，某个数据点 $(x_i, y_i)$ 到超平面的函数距离为 $\hat{r_i}=|w^Tx_i+b| =y_i(w^Tx_i+b)$ ,当超平面和数据点确定时，超平面可由无数对（w,b）确定，函数距离会随着w，b的变化而变化，引入几何距离 $r_i=\frac{|w^Tx_i+b|}{||w||}=\frac{\hat{r_i}}{||w||}$ ，几何距离不随着（w,b）的变化变化。定义数据点到超平面的几何距离为 $r=\min_{i} r_i =\min_{i}\frac{\hat{r_i}}{||w||}$ .

SVM的思想是最大化数据点到超平面的距离，即 $\max_{w,b}r\\s.t. r_i\geq r, for \ i=1,2 \ldots n$

即

$\max_{w,b}\frac{\hat{r}}{||w||}\\s.t. \hat{r_i}\geq \hat{r}, for \ i=1,2 \ldots n$

因为平面和点固定时函数距离可取任意非负值，令 $\hat{r}=1$ 不会改变上面的优化问题，得

$\max_{w,b}\frac{1}{||w||}\\s.t. \hat{r_i}\geq 1, for\ i=1,2 \ldots n$

最大化 $\frac{1}{||w||}$ 等价于最小化 $\frac{1}{2}||w||^2$ ,得

$\min_{w,b}\frac{1}{2}||w||^2\\s.t. y_i(w^Tx_i+b)\geq 1, for\ i=1,2 \ldots n$

得到上面最优化问题的解 $(w^*, b^*)$ 后，间隔最大的分离超平面就是 $y={w^*}^Tx+b^*$ .

可以通过Lagrange Multiplier解上述问题，Lagrange Function为

$L(w,b,\alpha)=\frac{1}{2}||w||^2-\sum_{i=1}^n\alpha_i[y_i(w^Tx_i+b)-1]\\ s.t.\alpha_i\geq0, for \ i=1,2\ldots,n$

令 $\theta =\max_{\alpha, \alpha \geq0} L(w,b,\alpha)=\max_{\alpha, \alpha \geq0} \{\frac{1}{2}||w||^2-\sum_{i=1}^n\alpha_i[y_i(w^Tx_i+b)-1]\}$ ,可知在满足约束条件的情况下 $\theta =\frac{1}{2}||w||^2$ (如果有某个数据点违反了约束条件，即 $y_i(w^Tx_i+b)-1<0$ ),那么 $\theta$ 无穷大），优化问题变为

$\min_{w,b}\theta =\min_{w,b}\max_{\alpha, \alpha \geq0} L(w,b,\alpha)=\min_{w,b}\max_{\alpha, \alpha \geq0} \{\frac{1}{2}||w||^2-\sum_{i=1}^n\alpha_i[y_i(w^Tx_i+b)-1]\}=P^*$

该问题称为原始问题,对偶问题为

$\max_{\alpha, \alpha \geq0}\min_{w,b} L(w,b,\alpha)=\max_{\alpha, \alpha \geq0}\min_{w,b}\{\frac{1}{2}||w||^2-\sum_{i=1}^n\alpha_i[y_i(w^Tx_i+b)-1]\}=Q^*$ ，

且有 $Q^*\leq P^*$ .

最优化问题满足Slater条件即存在 $x_i$ 使得不等式严格成立，所以 $Q^*= P^*$ ，可以通过求解对偶问题来获得原始问题的解。

K.K.T条件是 $Q^*= P^*$ 的充分必要条件，表达为

$\triangledown_wL(w^*,b^*,\alpha^*)=0\\ \triangledown_bL(w^*,b^*,\alpha^*)=0\\ \triangledown_\alpha L(w^*,b^*,\alpha^*)=0\\ \alpha_i(y_i(w^Tx_i+b)-1)=0,for\ i=1,2\ldots,n\\ \alpha_i\geq0,for\ i=1,2\ldots,n\\ y_i(w^Tx_i+b)-1 \geq 0, for\ i=1,2\ldots,n$

求解 $\min_{w,b}L(w,b,\alpha)$ ,对w,b求偏导，有

$\frac{dL(w,b,\alpha)}{dw}=w-\sum_{i=1}^n\alpha_iy_ix_i =0$

$\frac{dL(w,b,\alpha)}{db}=-\sum_{i=1}^n\alpha_iy_i =0$

即

$w=\sum_{i=1}^n\alpha_iy_ix_i\\\sum_{i=1}^n\alpha_iy_i=0$

有

$\begin{align*}\min_{w,b} L(w,b,\alpha)&=\min_{w,b}\{\frac{1}{2}||w||^2-\sum_{i=1}^n\alpha_i[y_i(w^Tx_i+b)-1]\}\\&=\frac{1}{2}w^T(\sum_{i=1}^n\alpha_iy_ix_i)-w^T\sum_{i=1}^n\alpha_iy_ix_i -\sum_{i=1}^n\alpha_iy_ib+\sum_{i=1}^n\alpha_i \\&=\sum_{i=1}^n\alpha_i-\frac{1}{2}w^T(\sum_{i=1}^n\alpha_iy_ix_i)\\&=\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j(x_i\cdot x_j) \\&s.t. \sum_{i=1}^n\alpha_iy_i=0\\&\alpha_i\geq0, for \ i=1,2,\ldots, n\end{align*}$

优化问题变为

$\max_{\alpha}\sum_{i=1}^n\alpha_i-\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j(x_i\cdot x_j) \\s.t. \sum_{i=1}^n\alpha_iy_i=0\\\alpha_i\geq0, for \ i=1,2,\ldots, n$

该优化问题可以通过SMO有效求解。假设得到的最优解为 $\alpha^*$ ,则

$w^*=\sum_{i=1}^n\alpha^*_iy_ix_i=\sum_{i,\alpha^*_i\gt0}\alpha^*_iy_ix_i$

通过kkt条件， $b^*=\frac{1}{y_j}-{w^*}^Tx_j=y_j-\sum_{i=1}^n\alpha^*_iy_i(x_i\cdot x_j),for\ some\ \alpha^*_j\gt0$

分离超平面为 $y={w^*}^Tx+b^*=\sum_{i,\alpha^*_i\gt0}\alpha^*_iy_i(x_i\cdot x)+b^*$

通过推导过程可知，如果 $\alpha_i\gt 0$ ,则 $y_i(w^Tx_i+b)=1$ ，对应的实例 $x_i$ 是支持向量，位于间隔边界上。如果 $\alpha_i=0$ ，则实例 $x_i$ 位于正确分类的间隔边界外。

线性支持向量机

线性可分支持向量机不能处理线性不可分数据集，因此引入线性支持向量机。线性支持向量机在线性可分支持向量机的基础上引入松弛变量 $\xi$ 来处理离异点。

最优化问题变为

$\min_{w,b}\frac{1}{2}||w||^2+C\sum_{i=1}^n\xi_i\\ s.t.\ y_i(w^Tx_i+b)\geq 1-\xi_i, for \ i=1,2\ldots,n \\ \xi_i\geq 0, for \ i=1,2\ldots,n$

其中 $\sum_{i=1}^n\xi_i$ 是离异点偏差量的惩罚，C是常数超参，用来控制“间隔最大化”和“离异点偏差量最小”。

Lagrange function为

$L(w,b,\xi,\alpha,\beta)=\frac{1}{2}||w||^2+C\sum_{i=1}^n\xi_i-\sum_{i=1}^n\alpha_i(y_i(w^Tx_i+b) - (1-\xi_i))-\sum_{i=1}^n\beta_i\xi_i \\ s.t.\ \alpha_i\geq0, for \ i=1,2,\ldots,n\\\beta_i\geq0, for \ i=1,2,\ldots,n$

使用对偶学习法，先求内层最小化。L对w,b,\xi求导，有

$\frac{dL}{dw}=w-\sum_{i=1}^n\alpha_iy_ix_i=0\\ \frac{dL}{db}=-\sum_{i=1}^n\alpha_iy_i=0 \\ \frac{dL}{d\xi_i}=C-\alpha_i-\beta_i=0$

即

$w=\sum_{i=1}^n\alpha_iy_ix_i\\ \sum_{i=1}^n\alpha_iy_i=0\\ C -\alpha_i-\beta_i=0, for \ i=1,2,\ldots, n$

所以外层最大化的函数为

$\begin{align*}L(w,b,\xi,\alpha,\beta)&=\frac{1}{2}||w||^2+C\sum_{i=1}^n\xi_i-\sum_{i=1}^n\alpha_i(y_i(w^Tx_i+b) - (1-\xi_i))-\sum_{i=1}^n\beta_i\xi_i \\ &=\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+C\sum_{i=1}^n\xi_i-\sum_{i=1}^n\alpha_i\xi_i-\sum_{i=1}^n\beta_i\xi_i\\&=\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)+\sum_{i=1}^n(C-\alpha_i-\beta_i)\xi_i\\\&=\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)\end{align*}\\ s.t. \sum_{i=1}^n\alpha_iy_i=0\\ \alpha_i\geq0, for \ i=1,2,\ldots,n\\ \beta_i\geq0, for \ i=1,2,\ldots,n\\C-\alpha_i-\beta_i=0, for \ i=1,2,\ldots,n$

约束条件可简化为

$\sum_{i=1}^n\alpha_iy_i=0\\0\leq\alpha_i\leq C, for \ i=1,2,\ldots,n$

解决该最优化问题后得到最优解 $\alpha^*$ ,则

$w^*=\sum_{i=1}^n\alpha^*_iy_ix_i=\sum_{i,\alpha^*_i\gt0}\alpha^*_iy_ix_i$

通过kkt条件， $b^*=\frac{1}{y_j}-{w^*}^Tx_j=y_j-\sum_{i=1}^n\alpha^*_iy_i(x_i\cdot x_j),for\ some\ 0 \lt\alpha^*_j\lt C$

最后得到分离超平面 $y={w^*}^Tx+b^*$

软间隔的支持向量在：间隔边界，间隔边界和分离超平面之间或分离超平面误分一侧。如果 $\alpha_i=0$ ,实例位于正确分类的间隔边界外；如果 $0\lt \alpha_i\lt C$ ,则 $\beta_i\gt0$ , $\xi_i=0$ , $y_i(w^Tx_i+b)=1$ ,实例刚好在间隔边界上，是支持向量；若 $\alpha_i=C$ ,则 $\beta=0$ , $\xi_i\gt0$ ,如果 $\xi_i<1$ ,实例位于分离超平面和间隔边界之间，如果 $\xi_i=1$ ,实例位于分离超平面上，如果 $\xi_i\gt1$ ，实例位于分离超平面误分一侧,都属于支持向量。

合页损失(hinge loss)函数： $Loss(x, y)=[k-distance(x, plane)]_+$ ,如果x到分离超平面的距离小于k，损失为两者的差，大于等于k时，为0.确保当距离足够大(k)时损失才为0.

从损失函数的角度看，支持向量机可看作是模型是 $y=sign(w^Tx+b)$ ,损失函数为

$Loss(x, y|w, b)=\sum_{i=1}^n[1-y_i(w^Tx_i+b)]_++\lambda ||w||^2$

的分类模型，损失函数第一项是经验损失，可以理解为当实例被正确划分且确信度够高（实例到分离超平面的距离大于等于1）时损失为0，否则损失为 $1-y(w^Tx+b)$ 。损失函数第二项是权重为 $\lambda$ 的正则项，w的 $L_2$ 范数。可以证明该损失函数与原来的最优化问题等价。令 $\xi_i\gt0,[1-y_i(w^Tx_i+b)]_+=[\xi_i]_+=\xi_i$ ,有

$Loss(x, y|w, b)=\sum_{i=1}^n\xi_i+\lambda||w||^2$

取 $\lambda=\frac{1}{2C}$ ,得到原来的最优化问题。

注：损失函数中第一项用函数距离是因为简单。假设超平面不变，成比例的增大w,b,损失函数会增大；成比例的减小w,b,对于正确分类的点损失函数可能会增大，错误分类的点损失函数会减小，此时最小距离有下界1，因此在某个临界的w,b后，成比例的减小w，b损失函数不会变小，需要改变超平面。效果和使用几何距离一样。

非线性支持向量机

在前面对偶学习法的推导中我们发现最优化的目标函数和决策函数都只涉及实例间的内积，因此可以用核方法替代这个内积，从而将输入空间扩展到更高维的特征空间，来处理更复杂的线性不可分数据集。

目标函数变为

$\max_{\alpha}\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_jK(x_i, x_j)$

决策函数变为

$f(x)=sign(\sum_{i,\alpha^*_i\gt0}\alpha^*_iy_iK(x_i, x)+b^*)$

这样做的思路是通过一个非线性变换将输入空间转换到特征空间，使输入空间线性不可分的数据在特征空间中线性可分，从而可以使用前面的线性支持向量机来解决问题。上面两个式子中，原来的 $(x_i\cdot x)$ 用 $K(x_i,x)$ 替换了，相当于隐式地将 $x_i$ 和 $x$ 转换到更高维的特征空间再计算内积，在这个特征空间里数据集可能是线性可分的。

SMO

【待更新】

SVM

概述

线性可分支持向量机

线性支持向量机

非线性支持向量机

SMO

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读