支持向量机

一.线性可分SVM与硬间隔最大化

给定线性可分训练数据集，通过间隔最大化，可以求解对应的凸二次规划问题得到分离超平面$w^*x+b^*=0$，以及相应的分类决策函数$f(x)=sign(w^*x+b^*)$。即需要找到一个超平面，将两个类别区分开，SVM试图寻找一个超平面来对样本进行分割，把样本中的正例和反例用超平面分开，而是尽最大的努力使正例和反例之间的间隔margin最大以获得比较好的泛化能力。如下图：\

函数间隔：给定超平面$(w,b)$，关于样本点$(x_i,y_i)$的函数间隔为$\hat{\gamma }_i=y_i(wx_i+b)$。 若对超平面法向量$w$加约束，例如$||w||=1$，使得间隔确定，此时称为几何间隔$\gamma_i =y_i(\frac{w}{||w||}x_i+\frac{b}{||w||})$。

问题抽象成数学形式如下：

$$\mathop{\max}_{w,b} \frac{\hat{\gamma}} {||w||}$$ $$s.t. y_i(wx_i+b) \geq \hat{\gamma}, i=1,2,\cdots,N$$

令$\hat{\gamma}=1$，且最大化$frac{1} {||w||}$和最小化$frac{1} {2}||w||^2$等价，所以问题变为：\

$$\mathop{\min}_{w,b} \frac{1} {2} ||w||^2$$ $$s.t. y_i(wx_i+b) - 1 \geq 0, i=1,2,\cdots,N$$

这是一个凸二次优化问题。什么叫凸？凸集是指有这么一个点的集合，其中任取两个点连一条直线，这条线上的点仍然在这个集合内部。例如下图，对于凸函数（在数学表示上，满足约束条件是仿射函数，也就是线性的Ax+b的形式）来说，局部最优就是全局最优，但对非凸函数来说就不是了。二次表示目标函数是自变量的二次函数。

二.对偶优化问题

在约束最优化问题中，常常利用拉格朗日对偶性将原始问题转换为对偶问题，通过求解对偶问题而得到原始问题的解。

对于$f(x), c_i(x), h_j(x)$是定义在$\mathbb{R}^n$上的连续可微分函数，则对于如下最优化问题：

$$\mathop{\min}_{x \in \mathbb{R}^n}f(x)$$ $$s.t. c_i(x) \leq 0, i=1,2,\cdots,k; h_j(x)=0, j=1,2,\cdots,l$$

可引入广义拉格朗日函数$L(x,\alpha,\beta)=f(x)+\sum_{i=1}^{k}\alpha_ic_i(x)+\sum_{j=1}^{l}\beta_jh_j(x)$，其中$\alpha_i,\beta_j$为拉格朗日乘子，$\alpha_i \geq 0$，可令不满足约束条件的$i,j$的$\alpha_i,\beta_j$趋于无穷，其余取0，则原始问题变为:

$$\mathop{\min}_{x}\theta_P(x)=\mathop{\min}_{x} \mathop{\max}_{\alpha,\beta} L(x,\alpha,\beta)$$

即广义拉格朗日函数的极小极大问题；
另外可以定义其对偶问题：

$$\theta_D(\alpha, \beta) = \mathop{\min}_{x} L(x,\alpha,\beta)$$

极大化上式，即$\mathop{\max}_{\alpha,\beta}\theta_D(\alpha, \beta)$称为广义拉格朗日函数的极大极小问题。 若原始问题和对偶问题都有最优值，则$d^*=\mathop{\max}_{\alpha,\beta}\theta_D(\alpha, \beta) \leq \mathop{\min}_{x}\theta_P(x)=p^*$，当且仅当满足KKT条件时，取得等号。 定理1: 假设函数$f(x), c_i(x)$是凸函数，$h_j(x)$是仿射函数；且$c_i(x)$存在x使得所有i成立，则存在$x^*,\alpha^*,\beta^*使得原问题和对偶问题都最优。$

所以对于SVM的凸二次优化问题的拉格朗日函数为：

$$L(x,\alpha,\beta)=\frac{1}{2}||w||^2-\sum_{i=1}^{N}\alpha_iy_i(wx_i+b)+\sum_{i=1}^{N}\alpha_i$$

同时对拉格朗日函数分别对$w,b$求导，令其等于0，得到：

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

代入原拉格朗日函数得到：

$$\mathop{\min}_{w,b}L(x,\alpha,\beta)=-\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}\alpha_i$$

再对$\alpha$求极大$\mathop{\max}_{\alpha} \mathop{\min}_{w,b}L(x,\alpha,\beta)$。 若将该式由极大转换为极小，即得等价得对偶问题：

$$\mathop{\min}_{\alpha} \mathop{\max}_{w,b}L(x,\alpha,\beta)=\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}\alpha_i$$

又因为这两个问题满足定理1，所以可以对对偶问题求解即可。

松弛向量与软间隔最大化

之前讨论的情况都是建立在样本的分布比较优雅和线性可分的假设上，在这种情况下可以找到近乎完美的超平面对两类样本进行分离。如图所示：

但对于线性不可分训练数据是不适用的。线性不可分意味着在某些样本点$(x_i,y_i)$不能满足函数间隔大于等于1的约束条件，所以我们引入一个松弛变量$\xi_i \geq 0$，约束条件变为：

$$y_i(w \cdot x+b) \geq 1-\xi_i$$

同时，目标函数也因此写为：

$$frac {1} {2}||w||^2+C\sum_{i=1}^{N}\xi_i$$

$C>0$称为惩罚参数。因此引入松弛向量后，原问题转变为：

$$\mathop{\min}_{w,b,\xi} frac {1} {2}||w||^2+C\sum_{i=1}^{N}\xi_i$$ $$s.t. y_i(w \cdot x+b) \geq 1-\xi_i, i=1,2,\cdots,N$$ $$\xi_i \geq 0, i=1,2,\cdots,N$$

这仍然是一个凸二次规划问题，利用同样的解法，得到原问题和对偶问题如下：

$$\mathop{\max}_{\alpha} -\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}\alpha_i$$ $$\mathop{\min}_{\alpha} \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}\alpha_i$$ $$s.t. \sum_{i=1}^{N}\alpha_iy_i=0, 0 \leq \alpha_i \leq C, i=1,2,\cdots,N$$

由此求出的分类器称为线性支持向量机。

非线性支持向量机

对于线性分类问题，线性支持向量机是一种有效的解决方案，但是对于非线性问题，需要利用非线性支持向量机。主要特点是利用核技巧，核技巧是利用核函数将非线性可分问题在新的空间中变成线性可分问题。

设X是输入空间，又设H为特征空间，如果存在一个从X到H的映射$\phi(x):X\rightarrow H$使得所有的$x,z \in X$，函数$K(x,z)$满足条件$K(x,z)=\phi(x)\cdot \phi(z)$，则称$K(x,z)$为核函数，$\phi(x)$为映射函数。

多类问题

目前讨论的都是二分类问题，那么支持向量机能否用于解决多类问题，如果每两个类别训练一个分类器，则需要M(M+1)/2个分类器，这样需要非常多的分类器。
其中一种方法是：对于M多类问题，会使用L个二元分类器，创建一个$M \times L$的期望标签矩阵：

$$\begin{bmatrix}-1& -1& -1& +1& -1& +1\\+1& -1& +1& +1& -1& -1\\+1& +1& -1& -1& -1& +1\\-1& -1& +1& -1& +1& +1 \end{bmatrix}$$

对于第一个分类器，其对四个类别的响应为(-1,+1,+1,-1)，第二个分类器，其响应为(-1,-1,+1,-1)，以此类推，这样对于每个类别将产生一个码字，例如第一类的码字为(-1,-1,-1,+1,-1,+1)。然后计算该码字与M个编码的汉明距离，这个码字将被划分到距离最小的类中。对于SVM多类问题的研究有不少在这个方法上扩展得到。

---

• Previous
  决策树
• Next
  分解机