机器学习之支持向量机

    支持向量机(Support vector machines，SVM)是一种二分类模型，其基本模型是定义在特征空间上的间隔最大的线性分类器。学习策略是间隔最大化，最终转化为一个凸二次规划问题求解。

    支持向量机学习方法包含构建由简至繁模型：线性可分支持向量机、线性支持向量机以及非线性支持向量机。

线性可分支持向量机

    线性可分支持向量机(linear support vector machine in linearly separable case)主要用于给定的训练数据是线性可分的，通过硬间隔最大化，来学习一个线性分类器实现数据的分类。

算法描述

    给定线性可分的训练数据集，我们学习的目标是在特征空间中找到一个分离超平面，能将数据分到不同的平面中。通过间隔最大化或等价地求解相应的凸二次规划问题学习到的超平面为

$$\omega·x+b=0$$

该超平面是由平面的法向量$\omega$和截距$b$决定的。该平面相对应的决策函数$f(x)=sign(\omega·x+b)$称为线性可分支持向量机。
根据题设，针对二分类问题:$y(x)=\omega·x+b$
有：

$$\begin{cases} y(x_i) \ge 0===y_i=+1 \\ y(x_i) \le 0===y_i=-1 \end{cases}$$

即，$y_i·y(x_i)\ge 0$

几个概念

函数间隔
    一个点距离超平面的远近可以表示分类预测的确信程度，函数间隔用$y(\omega·x+b)$量化。
几何间隔
    函数间隔除以$||\omega||$,具体来推导一下，设几何间隔为图中的$\gamma$：

$$x=x_0+\gamma\frac{\omega}{||\omega||}$$

两边同时乘以$\omega^T$得：
\begin{equation}\begin{split}\omega^Tx&=\omega^Tx_0+\gamma\frac{\omega^T\omega}{||\omega||}\\\\
&=-b+\gamma ||\omega||\\\\
\end{split}\end{equation}可以得到几何间隔：

$$\gamma=\frac{\omega^Tx+b}{||\omega||}=\frac{f(x)}{||\omega||}$$

为了得到$\gamma$的绝对值，乘以对应类别，可得：

$$\gamma=\frac{\omega^Tx+b}{||\omega||}=\frac{yf(x)}{||\omega||}$$

支持向量
    在线性可分的情况下，训练数据集中的样本点与分离超平面距离最近的样本点的实例称之为支持向量。支持向量使得下面的公式成立：

$$y_i(\omega x_i+b)-1=0$$

目标函数

    支持向量机学习的基本思想就是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。对于线性可分的数据集，线性可分分离的超平面有无穷个，但是几何间隔最大的最大的分离超平面是唯一的。几何间隔最大的超平面可以对最难分的点，也就是距离超平面最近的点分割的很开，即有足够的确信度将它们分开。因此，我们建立目标函数为：

$$arg\max\{\min(\frac{y_i(\omega^Tx_i+b)}{||\omega||}\}$$

在这里我们可以通过等比例缩放，使得$\min(y_i(\omega^Tx_i+b))$为1，则目标函数可以转化为：

$$arg\max\frac1{||\omega||},s.t.y_i(\omega^Tx_i+b) \ge 1,i=1,2,…,n$$

该目标函数等价于

$$\min\frac12||\omega||^2,s.t.y_i(\omega^Tx_i+b) \ge 1,i=1,2,…,n$$

带有约束问题的极值问题，我们一般通过拉格朗日乘子法来求：

$$L(\omega,b,\alpha)=\frac12||\omega||^2-\sum_{i=1}^n\alpha_i(y_i(\omega^Tx+b)-1)\tag{1}$$

原问题是极小极大问题:

$$\min\limits_{\omega,b} \max_{\alpha}L(\omega,b,\alpha)$$

应用拉格朗日的对偶性，将原始问题变化成其对偶问题，变成极大极小问题。

$$\max\limits_{\alpha}\min_{\omega,b} L(\omega,b,\alpha)$$

求解对偶问题，需要先求$L(\omega,b,\alpha)$对$\omega$、$b$的极小，再求对$\alpha$的极大。
(1)$\min\limits_{\omega,b}L(\omega,b,\alpha)$
对$\omega$、$b$求偏导，令其等于0.

$$\frac{\partial L}{\partial \omega}=\omega-\sum_{i=1}^N\alpha_i^Ny_ix_i=0$$ $$\frac{\partial L}{\partial b}=-\sum_{i=1}^N\alpha_i^Ny_i=0$$

解得：

$$\omega=\sum_{i=1}^N\alpha_iy_ix_i\tag{2}$$ $$\sum_{i=1}^N\alpha_iy_i=0\tag{3}$$

将(2)带入拉格朗日函数(1)，结合公式(3)，(1)可以表示为：
\begin{equation}\begin{split}L(\omega,b,\alpha)&=\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jx_ix_j-\sum_{i=1}^N\alpha_iy_i((\sum_{j=1}^N\alpha_jx_jx_j)x_i+b)+\sum_{i=1}^N\alpha_i\\\\
&=-\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jx_ix_j+\sum_{i=1}^N\alpha_i
\end{split}\end{equation}即：

$$\min\limits_{\omega,b}L(\omega,b,\alpha)=-\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jx_ix_j+\sum_{i=1}^N\alpha_i$$

(2)求$\min\limits_{\omega,b}L(\omega,b,\alpha)$对$\alpha$的极大：

$$\max\limits_{\alpha}\sum_{i=1}^n\alpha_i-\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jx_ix_j$$ $$s.t.\sum_{i=1}^n\alpha_iy_i=0,\alpha_i \ge 0,i=1,2,…,n$$

整理目标函数，添加负号，得对偶优化问题

$$\min\limits_{\alpha}\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jx_ix_j-\sum_{i=1}^n\alpha_i$$ $$s.t.\sum_{i=1}^n\alpha_iy_i=0,\alpha_i \ge 0,i=1,2,…,n$$

根据$SMO$算法可以求得对偶问题中的$\alpha$。

线性支持向量机

    线性支持向量机(linear support vector machine)主要用于给定的训练数据是线性不可分的，通过软间隔最大化，来学习一个线性分类器实现数据的分类。

算法描述

    对于线性不可分的数据，如果是因为数据有噪音而使得数据是非线性结构，使用上述算法是不行的，现象不可分意味着某些样本点不能满足函数间隔大于等于1的约束条件。正是由于噪声的存在，使得超平面有点偏斜，为了解决这个问题，允许数据点在一定程度上偏离超平面，我们引入了松弛因子$\xi_i \ge 0$,使得函数间隔加上松弛变量大于等于1，这样约束条件变成：

$$y_i(\omega x_i+b) \ge 1-\xi_i$$

同时，我们还需要在原来的目标函数后面加上一项，使得这些$\xi_i$的综合也要最小:

$$\min \frac12||\omega||^2+C\sum_{i=1}^n\xi_i$$

$C>0$成为惩罚参数，是超参数，人为设定，最小化目标函数包含两层含义：使得$\frac12||\omega||^2$尽量小即间隔尽量大，同时使错误分类的点的个数要尽可能的少。

目标函数

    线性不可分的线性支持向量机的学习问题又变成了一个凸二次优化的问题：

$$\min\limits_{\omega,b,\xi}\frac12||\omega||^2+C\sum_{i=1}^N \xi_i$$ $$s.t. y_i(\omega x_i+b)\ge1-\xi_i,i=1,2,…,N;\xi_i \ge 0,i=1,2,…,N$$

同样地，采用拉格朗日乘子法来求极值问题，原始问题的拉格朗日函数是：

$$L(\omega,b,\xi,\alpha,\mu)=\frac12||\omega||^2+C\sum_{i=1}^N\xi_i-\sum_{i=1}^n\alpha_i(y_i(\omega^Tx+b)-1+\xi_i)-\sum_{i=1}^N\mu_i\xi_i\tag{4}$$

(1)$\min\limits_{\omega,b}L(\omega,b,\alpha)$
对$\omega$、$b$、$\xi$求偏导，令其等于0.

$$\frac{\partial L}{\partial \omega}=\omega-\sum_{i=1}^N\alpha_i^Ny_ix_i=0$$ $$\frac{\partial L}{\partial b}=-\sum_{i=1}^N\alpha_i^Ny_i=0$$ $$\frac{\partial L}{\partial \xi}=C-\alpha_i-\mu_i=0$$

解得：

$$\omega=\sum_{i=1}^N\alpha_iy_ix_i\tag{5}$$ $$\sum_{i=1}^N\alpha_iy_i=0\tag{6}$$ $$C=\alpha_i+\mu_i\tag{7}$$

将(5)(6)(7)带入拉格朗日函数(4)，(4)可以表示为：
\begin{equation}\begin{split}L(\omega,b,\xi,\alpha,\mu)&=\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jx_ix_j-\sum_{i=1}^N\alpha_iy_i((\sum_{j=1}^N\alpha_jx_jx_j)x_i+b)+\sum_{i=1}^N\alpha_i\\\\
&=-\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jx_ix_j+\sum_{i=1}^N\alpha_i
\end{split}\end{equation}即：

$$\min\limits_{\omega,b,\xi}L(\omega,b,\xi,\alpha,\mu)=-\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jx_ix_j+\sum_{i=1}^N\alpha_i$$

(2)求$\min\limits_{\omega,b,\xi}L(\omega,b,\xi,\alpha,\mu)$对$\alpha$的极大，得到对偶问题：

$$\max\limits_{\alpha}\sum_{i=1}^n\alpha_i-\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jx_ix_j$$ $$s.t.\sum_{i=1}^n\alpha_iy_i=0;C-\alpha_i-\mu_i=0$$ $$\alpha_i \ge 0,i=1,2,…,n;\mu_i \ge 0,i=1,2,…,n\tag{8}$$

公式(8)等价于$0\le \alpha_i\le C$
可以将该问题求极大问题转化为求极小，于是得到对偶问题。根据$SMO$算法可以求得对偶问题中的$\alpha$。

非线性支持向量机

    非线性支持向量机(linear support vector machine)主要用于给定的训练数据是非线性的，通过核函数将原始数据映射到更高维的空间，来解决在原始空间中线性不可分的问题。

算法描述

    给定线性不可分的训练数据集，我们首先在低维空间中计算，然后通过核函数将输入数据映射到高纬特征空间，最终在高纬特征空间中构造出最优分离超平面，从而把平面不好分的非线性数据分开。因此该问题可以分解为两步，第一步是首先通过非线性映射将数据变换到一个特征空间，第二步是在特征空间中找到一个分离超平面，学习到的超平面可以表示为

$$\omega·\Phi(x)+b=0$$

再结合公式(2)，决策函数可以表示为：

$$f(x)=sign(\sum_{i=1}^N \alpha_iy_i(\Phi(x_i)\Phi(x))+b)\tag{9}$$

其中$\Phi$是映射函数，根据公式(9)如果可以直接计算内积$\Phi(x_i)\Phi(x)$，就可以将两个步骤融合到一起建立一个非线性的学习期，这样直接计算的方法称之为核函数方法。
具体算法流程：

1. 目标函数
       选取适当的核函数$k(x,z)$和适当的参数$C$,构造并求解最优化问题 $$\max\limits_{\alpha}\sum_{i=1}^n\alpha_i-\frac12\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jk(x_i,x_j)$$ $$s.t.\sum_{i=1}^n\alpha_iy_i=0;C-\alpha_i-\mu_i=0$$ $$0\le \alpha_i\le C,i=1,2,…,N$$ 根据$SMO$算法求得最优解$\alpha^{*}=(\alpha_1^{*},\alpha_2^{*},…,\alpha_N^{*})^T$
2. 计算$b^{*}$
   选取$\alpha^{*}$的正分量$0\le \alpha_i\le C$,计算$b^{*}$ $$b^{*}=y_j-\sum_{i=1}^N\alpha_i^{*}y_ik(x_ix_j)$$
3. 构造决策函数 $$f(x)=sign(\sum_{i=1}^N \alpha_i^{*}y_ik(x,x_i)+b^{*}$$

   常见的核函数

4. 多项式核
       用数学公式可以表示为： $$k(\vec x,\vec y)=(\vec x \vec y+c)^2$$
5. 高斯核
       用数学公式可以表示为： $$k(\vec x,\vec y)=e^{-\frac{||\vec x-\vec y||^2}{2\delta^2}}$$

   SMO

       先占坑，后期补上。

   参考资料

   李航,统计学习方法，清华大学出版社，2012
   支持向量机通俗导论（理解SVM的三层境界）