支持向量机SVM

        SVM是一种二类分类模型，其基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机。SVM的学习策略就是间隔最大化，可以形式化为一个求解凸二次规划问题，也等价于正则化的合页损失函数最小化问题。
        支持向量机SVM由简至繁分别为：线性可分的SVM、线性SVM及非线性SVM。简单模型是复杂模型的基础，也是复杂模型的特殊情况。

• 当训练数据集线性可分时，通过硬间隔最大化学习线性可分SVM；
• 当训练数据集近似线性可分时，通过软间隔最大化学习线性SVM；
• 当训练数据集线性不可分时，通过使用核技巧及软间隔最大化，学习非线性SVM。

线性可分支持向量机与硬间隔最大化

线性可分SVM

        假设输入空间与特征空间是两个不同的空间。线性可分SVM、线性SVM假设这两个空间的元素一一对应，并将输入空间中的输入映射为特征空间中的特征向量。非线性SVM利用一个从输入空间到特征空间的非线性映射将输入映射为特征向量。这样，输入都由输入空间转换到特征空间，SVM的学习是在特征空间中进行的。
        假设给定一个线性可分的训练数据集
$$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$$
学习的目标是在特征空间中找到一个分离超平面，能将实例分到不同的类。分离超平面对应方程$w\cdot x+b=0$，它由法向量$w$和截距$b$决定，可以用$(w,b)$来表示。法向量指向的一侧为正类，另一侧为负类。
        一般地，当训练集线性可分时，存在无穷多个分离超平面可以将两类数据正确分开。感知机利用误分类最小的策略，求得分离超平面，但此时的解有无穷多个。线性可分SVM利用间隔最大化求最优分离超平面，此时的解是唯一的。

定义 线性可分SVM

        给定线性可分训练数据集，通过间隔最大化或等价地求解相应的凸二次规划问题学习得到的分离超平面为：
$$w^{\ast }\cdot x+b^{\ast }=0\text{\hspace{1em}(1)}$$
以及相应的分类决策函数
$$f(x)=sign(w^{\ast }\cdot x+b^{\ast })\text{\hspace{1em}(2)}$$

函数间隔与几何间隔

函数间隔

        一般来说，一个点距离分离超平面的远近可以表示分类预测的确信程度。在超平面$w\cdot x+b=0$确定的情况下，$|w\cdot x+b|$能够相对地表示点$x$距离超平面的远近，$w\cdot x+b$与类标记$y$的符号是否一致能够表示分类是否正确，所以可以综合两者来表示分类的正确性及确信度，这就是函数间隔。

定义 函数间隔

        对于给定的训练数据集$T$和超平面$(w,b)$，定义超平面$(w,b)$关于样本点$(x_i,y_i)$的函数间隔为：
$$\widehat{{\gamma }_i}=y_i(w\cdot x_i+b)\text{\hspace{1em}(3)}$$
定义超平面$(w,b)$关于训练数据集$T$的函数间隔为超平面到训练集中所有样本点的函数间隔最小值，即：
$$\hat{\gamma }=\underset{i=1,2,...,N}{\min }\widehat{{\gamma }_i}\text{\hspace{1em}(4)}$$
        函数间隔可以表示分类预测的正确性及确信度。但选择分离超平面时，只有函数间隔还不够，因为只要成比例地改变$w$和$b$，函数间隔也会成比例地改变，但是超平面本身并未改变。可以对分离超平面的法向量$w$加上某些约束，如规范化，$||w||=1$，使得间隔是确定的。此时函数间隔就变成了几何间隔。

几何间隔

        下图给出了超平面$(w,b)$及其法向量$w$。
        点$A$表示某一实例$x_i$，其类标记为$y_i=+1$。点$A$与超平面的距离由线段$AB$给出，记作${\gamma }_i$。
$${\gamma }_i=\frac{w}{||w||}\cdot x_i+\frac{b}{||w||}$$
其中$||w||$为$w$的$L_2$范数。这是点$A$在正侧的时候，如果在负一侧，则：
$${\gamma }_i=-\frac{w}{||w||}\cdot x_i+\frac{b}{||w||}$$
        一般地，当样本点被超平面正确分类时，点$x_i$与超平面的距离是：
$${\gamma }_i=y_i\left(\frac{w}{||w||}\cdot x_i+\frac{b}{||w||}\right)$$，由此可得几何间隔的概念。

定义 几何间隔
        对于给定的训练数据集和超平面，定义超平面$(w,b)$关于样本点$(x_i,y_i)$的几何间隔为
$${\gamma }_i=y_i\left(\frac{w}{||w||}\cdot x_i+\frac{b}{||w||}\right)\text{\hspace{1em}(5)}$$
         定义超平面$(w,b)$关于训练数据集$T$的几何间隔为超平面到训练集中所有样本点的几何间隔最小值，即：
$$\gamma =\underset{i=1,2,...,N}{\min }\widehat{{\gamma }_i}\text{\hspace{1em}(6)}$$
         超平面$(w,b)$关于样本点$(x_i,y_i)$的几何间隔一般是实例点到超平面的带符号距离，当样本点被正确分类时就是实例点到超平面的距离。
         函数间隔和几何间隔有以下关系：
$${\gamma }_i=\frac{\widehat{{\gamma }_i}}{||w||}\text{\hspace{1em}(7)}$$
$$\gamma =\frac{\hat{\gamma }}{||w||}\text{\hspace{1em}(8)}$$
如果$||w||=1$，函数间隔和几何间隔相等。如果$w、b$成比例地改变（超平面不会改变），函数间隔会成比例改变，而几何间隔不变。

间隔最大化

        SVM学习的基本想法是求解能够正确划分训练数据集并且几何间隔最大的分离超平面。对于线性可分的数据集而言，线性可分的超平面有无穷多个，但是几何间隔最大的超平面是唯一的，这里的间隔最大化称为硬间隔最大化。
        间隔最大化的直观解释是：对训练集找到几何间隔最大的超平面意味着以充分大的确信度对训练集进行分类。也就是说，不仅将正负实例点分开，而且对最难分的实例点（离超平面最近的点）也有足够大的确信度将其分开。这样的超平面应该对未知的新实例有很好的分类预测能力。

最大间隔分离超平面

        求得一个几何间隔最大的分离超平面，可以表示为下面的约束最优化问题：
$$\underset{w,b}{\max }\gamma \text{\hspace{1em}(9)}$$
$$s.t.y_i\left(\frac{w}{||w||}\cdot x_i+\frac{b}{||w||}\right)\ge \gamma ,i=1,2,...,N\text{\hspace{1em}(10)}$$
即我们希望最大化超平面$(w,b)$关于训练数据集的几何间隔$\gamma$，约束条件表示的是超平面$(w,b)$关于每个训练样本点几何间隔至少是$\gamma$。
        考虑几何间隔和函数间隔的关系式（8），可将这个问题改写为：
$$\underset{w,b}{\max }\frac{\hat{\gamma }}{||w||}1\text{\hspace{1em}(1)}$$
$$s.t.y_i(w\cdot x_i+b)\ge \hat{\gamma },i=1,2,...,N\text{\hspace{1em}(12)}$$
        函数间隔$\hat{\gamma }$的取值并不影响最优化问题的解，这样可以取$\hat{\gamma }=1$，将$\hat{\gamma }=1$代入上面的最优化问题，且有最大化$\frac{1}{||w||}$和最小化 $\frac{1}{2}||w|{|}^2$是等价的，于是可以得到下面的线性可分SVM学习的最优化问题
$$\underset{w,b}{\min }\frac{1}{2}||w|{|}^2\text{\hspace{1em}(13)}$$
$$s.t.y_i(w\cdot x_i+b)-1\ge 0,i=1,2,...,N\text{\hspace{1em}(14)}$$
这是一个凸二次规划问题。
        凸优化问题是指约束最优化问题
$$\underset{w}{\min }f(w)\text{\hspace{1em}(15)}$$
$$s.t.g_i(w)\le 0,i=1,2,...,k\text{\hspace{1em}(16)}$$
$$h_i(w)=0,i=1,2,...,l\text{\hspace{1em}(17)}$$
其中，目标函数$f(w)$和约束函数$g_i(w)$都是$R^n$上的连续可微的凸函数，约束函数$h_i(w)$是$R^n$上的仿射函数。

        当目标函数$f(w)$是二次函数且约束函数$g_i(w)$是仿射函数时，上述凸最优化问题称为凸二次规划问题。

        如果求出来约束最优化问题（13）~（14）的解$w^{\ast },b^{\ast }$，就可以得到最大间隔分离超平面$w^{\ast }\cdot x+b^{\ast }=0$及分类决策函数$f(x)=sign(w^{\ast }\cdot x+b^{\ast })$，即线性可分SVM。

算法 线性可分SVM学习算法——最大间隔法

输入：线性可分的训练集$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_n=N))\}$，其中$X\in \mathcal{X}=R^n$，$y_i\in \mathcal{Y}=\{+1,-1\},i=1,2,...,N$
输出：最大间隔分离超平面和分类决策函数。

（1）构造并求解指约束最优化问题
$$\underset{w,b}{\min }\frac{1}{2}||w|{|}^2$$
$$s.t.y_i(w\cdot x_i+b)-1\ge 0,i=1,2,...,N$$
求得最优解$w^{\ast },b^{\ast }$。

（2）由此得到分离超平面：
$$w^{\ast }\cdot x+b^{\ast }=0$$
分类决策函数：
$$f(x)=sign(w^{\ast }\cdot x+b^{\ast })$$

最大间隔分离超平面的存在唯一性

        若训练集$T$线性可分，则可将训练数据集中的样本点完全正确分开的最大间隔分离超平面存在且唯一。

支持向量和间隔边界

        在线性可分的情况下，训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量。支持向量是使得约束条件式（14）等号成立的点，即
$$y_i(w\cdot x_i+b)-1=0$$
        对于$y_i=+1$的正例点，支持向量在超平面
$$H_1:w\cdot x+b=1$$
上，对于$y_i=-1$的负例点，支持向量在超平面
$$H_2:w\cdot x+b=-1$$
上。如下图所示，在$H_1、H_2$上的点就是支持向量。

        注意到$H_1，H_2$平行，没有实例点落在它们中间。在$H_1，H_2$之间形成一条长带，其宽度称为间隔。间隔依赖于分离超平面的法向量$w$，等于$\frac{2}{||w||}$。$H_1，H_2$称为间隔边界。
        在决定分离超平面时只有支持向量起作用，其它的实例点并不起作用。如果移动支持向量将改变所求的解；但如果在间隔边界以外移动其它实例点，甚至去掉这些点，解不会改变。由于支持向量在确定分离超平面时起着决定性作用，所以这种分类模型叫支持向量机。支持向量的个数一般很少，所以SVM是由很少的“重要的”训练样本确定的。

学习的对偶算法

        为了求解线性可分SVM的最优化问题（13）（14）
$$\underset{w,b}{\min }\frac{1}{2}||w|{|}^2\text{\hspace{1em}(13)}$$
$$s.t.y_i(w\cdot x_i+b)-1\ge 0,i=1,2,...,N\text{\hspace{1em}(14)}$$
将它作为原始最优化问题，应用拉格朗日对偶性，通过求解对偶问题得到原始问题的最优解，即线性可分SVM的对偶算法。这样做的优点，一是对偶问题往往更容易求解；二是自然引入核函数，进而推广到非线性分类问题。转换后的对偶问题为：
$$\underset{\alpha }{\min }\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\text{\hspace{1em}(18)}$$
$$s.t.\sum _{i=1}^N{\alpha }_i{y}_i=0\text{\hspace{1em}(19)}$$
$${\alpha }_i\ge 0,i=1,2,...,N\text{\hspace{1em}(20)}$$
        对于线性可分训练数据集，假设对偶最优化问题（18）~（20）对$\alpha$ 的解为${\alpha }^{\ast }=({\alpha }_1^{\ast },{\alpha }_2^{\ast },...,{\alpha }_N^{\ast }{)}^T$，可以由${\alpha }^{\ast }$求得原始最优化问题（13）~（14）对$(w,b)$的解$w^{\ast },b^{\ast }$。

定理
        设${\alpha }^{\ast }=({\alpha }_1^{\ast },{\alpha }_2^{\ast },...,{\alpha }_N^{\ast }{)}^T$是对偶最优化问题（18）~（20）对 $\alpha$ 的解，则存在下标$j$，使得${\alpha }_j^{\ast }>0$，并可按下式求得原始最优化问题（13）~（14）的解$w^{\ast },b^{\ast }$:
$$w^{\ast }=\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i{x}_i\text{\hspace{1em}(21)}$$
$$b^{\ast }=y_j-\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i(x_i\cdot x_j)\text{\hspace{1em}(22)}$$

        由定理可知，分离超平面可以写成
$$\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i(x\cdot x_i)+b^{\ast }=0\text{\hspace{1em}(23)}$$
$$f(x)=sign\left(\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i(x\cdot x_i)+b^{\ast }\right)\text{\hspace{1em}(24)}$$
也就是说，分类决策函数只依赖于输入$x$和训练样本输入的内积，式（24）称为线性可分SVM的对偶形式。

算法 线性可分SVM学习算法

输入：线性可分的训练集$T=\{(x_1,y_1),(x_2,y_2),...,(x_N,y_n=N))\}$，其中$X\in \mathcal{X}=R^n$，$y_i\in \mathcal{Y}=\{+1,-1\},i=1,2,...,N$
输出：分离超平面和分类决策函数。

（1）构造并求解约束最优化问题
$$\underset{\alpha }{\min }\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$$
$${\alpha }_i\ge 0,i=1,2,...,N$$
求得最优解${\alpha }^{\ast }=({\alpha }_1^{\ast },{\alpha }_2^{\ast },...,{\alpha }_N^{\ast }{)}^T$。

（2）计算
$$w^{\ast }=\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i{x}_i$$
并选择${\alpha }^{\ast }$的一个正分量${\alpha }_j^{\ast }>0$，计算
$$b^{\ast }=y_j-\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i(x_i\cdot x_j)$$

（3）求得分离超平面
$$w^{\ast }\cdot x+b^{\ast }=0$$
分类决策函数：
$$f(x)=sign(w^{\ast }\cdot x+b^{\ast })$$

        在线性可分SVM中，$w^{\ast }、b^{\ast }$只依赖于训练数据中对应于${\alpha }_i^{\ast }>0$的样本点$(x_i,y_i)$，而其它样本点对$w^{\ast }$和 $b^{\ast }$没有影响，将训练数据中对应于${\alpha }_i^{\ast }>0$ 的实例点$x_i\in R^n$称为支持向量。

定义 支持向量
        考虑原始最优化问题（13）（14）及对偶最优化问题（18）~（20），将训练集中对应于${\alpha }_i^{\ast }>0$的样本点 $(x_i,y_i)$ 的实例$x_i\in R^n$称为支持向量。
        根据这一定义，支持向量一定在间隔边界上。由KKT互补条件知，
$${\alpha }_i^{\ast }(y_i(w^{\ast }\cdot x_i+b^{\ast })-1)=0,i=1,2,...,N$$
        对应于${\alpha }_i^{\ast }>0$ 的实例点$x_i$，有
$$y_i(w^{\ast }\cdot x_i+b^{\ast })-1=0$$
或
$$w^{\ast }\cdot x_i+b^{\ast }=\pm 1$$
即$x_i$一定在间隔边界上，与之前的定义一致。