机器学习-SVM

支持向量机是非常高效的一种有监督机器学习算法，是一个二类分类模型，他的基本模型是定义在特征空间上的间隔最大的现行分类器，间隔最大使它有别于感知机；此外核函数的应用，使该算法可以应用有非线性空间。

支持向量机由简入繁主要包含如下几种：

• 线性可分支持向量机
• 线性支持向量机
• 非线性支持向量机

线性可分支持向量机

函数间隔和几何间隔

给定数据集$T=[(x_1,y_1),(x_2,y_2),(x_3,y_3),\mathrm{.}\mathrm{.}\mathrm{.},(x_n,y_n)]$，其中$x_i\in R^n$，$y_i\in [-1,+1]$，$i=1,2,\mathrm{.}\mathrm{.}\mathrm{.},N$，$x_i$为第$i$个特征向量，$y_i$为$x_i$的类标签。学习的目标是在特征空间内找到一个分离超平面，能够将实例分到不同的类，分离超平面对应于方程$\omega \mathrm{.}x+b=0$，它由法向量$\omega$以及对应的截距$b$构成。分离超平面将整个样本空间划分为两类，一类为正，即$y=1$，另一类为负，即$y=-1$。训练的过程根据间隔最大化来求得最优分离超平面的过程。

一个点距离分离超平面的距离可以表示该分类预测的确信程度，可以使用$\mathrm{\mid }\omega \mathrm{.}x+b\mathrm{\mid }$表示点$x$距离超平面的远近，此外，$\omega \mathrm{.}x+b$与类标记$y$是否一致来表示分类的正确性。因此使用$y(\omega \mathrm{.}x+b)$表示分类的正确性及确信度。这就是函数间隔的概念。

函数间隔使用符号$\overline{{\gamma }_i}$存在如下公式
$$\widehat{{\gamma }_i}=y_i(w\mathrm{.}{x}_i+b)$$
使用函数间隔可以表示实例预测的正确性和确信度，但是会存在一个问题，如果成比例的增加参数$w$和$b$，得到的函数间隔变大了两倍，但是对应的分离超平面没有变化，这是时候需要对参数进行规范化，使得对于一个实例来说其参数是确定的。此时函数间隔便成为几何间隔。

使用符号${\gamma }_i$表示，得到公式
$${\gamma }_i=y_i(\frac{w}{\mathrm{\mid }\mathrm{\mid }w\mathrm{\mid }\mathrm{\mid }}\mathrm{.}{x}_i+\frac{b}{\mathrm{\mid }\mathrm{\mid }w\mathrm{\mid }\mathrm{\mid }})$$

• 其中$\mathrm{\mid }\mathrm{\mid }w\mathrm{\mid }\mathrm{\mid }$为$w$的$L_2$范数

定义超平面$(w,b)$关于训练数据集$T$的几何间隔为超平面(w,b)关于$T$所有样本点$(x_i,y_i)$的几何间隔的最小值，
$$\gamma =\underset{i=1,2,\mathrm{.}\mathrm{.}\mathrm{.},N}{\min }{\gamma }_i$$
这也就是对训练集进行训练的过程。

几何间隔和函数间隔的关系
$$\begin{array}{rl}{\displaystyle {\gamma }_i}& {\displaystyle =\frac{\widehat{{\gamma }_i}}{\mathrm{\mid }\mathrm{\mid }w\mathrm{\mid }\mathrm{\mid }}}\\ {\displaystyle \gamma }& {\displaystyle =\frac{\widehat{\gamma }}{\mathrm{\mid }\mathrm{\mid }w\mathrm{\mid }\mathrm{\mid }}}\end{array}$$

如果存下$\mathrm{\mid }\mathrm{\mid }w\mathrm{\mid }\mathrm{\mid }=1$，则函数间隔和几何间隔相等。

间隔最大化

对训练数据集进行训练的过程实际上就是求得满足几何间距最大化的过程，对于确定的数据集，几何间隔最大化的分离超平面是确定的，此时不仅正负实例被分开，并且距离分离超平面最近的点也具有足够大的确信度将其分开。

得到目标函数和约束条件如下
$$\begin{array}{rl}{\displaystyle }& {\displaystyle \underset{w,b}{\max }\gamma }\\ {\displaystyle }& {\displaystyle s\mathrm{.}t\mathrm{.}{y}_i(\frac{w}{\mathrm{\mid }\mathrm{\mid }w\mathrm{\mid }\mathrm{\mid }}\mathrm{.}{x}_i+\frac{b}{\mathrm{\mid }\mathrm{\mid }w\mathrm{\mid }\mathrm{\mid }})\ge \gamma ,i=1,2,\mathrm{.}\mathrm{.}\mathrm{.},N}\end{array}$$
目标函数为最大化几何间隔，并且满足约束条件，样本即集中所有样本的几何间隔都不小于几何间隔。

参考几何间隔和函数间隔之间存在的关系，可以对目标函数及约束条件进行修正
$$\begin{array}{rl}{\displaystyle }& {\displaystyle \underset{w,b}{\max }\gamma =\frac{\widehat{\gamma }}{\mathrm{\mid }\mathrm{\mid }w\mathrm{\mid }\mathrm{\mid }}}\\ {\displaystyle }& {\displaystyle s\mathrm{.}t\mathrm{.}{y}_i(\frac{w}{\mathrm{\mid }\mathrm{\mid }w\mathrm{\mid }\mathrm{\mid }}\mathrm{.}{x}_i+\frac{b}{\mathrm{\mid }\mathrm{\mid }w\mathrm{\mid }\mathrm{\mid }})\ge \gamma =\frac{\widehat{\gamma }}{\mathrm{\mid }\mathrm{\mid }w\mathrm{\mid }\mathrm{\mid }},}& {\displaystyle i=1,2,\mathrm{.}\mathrm{.}\mathrm{.},N}\\ {\displaystyle }& {\displaystyle \Rightarrow y_i(w\mathrm{.}{x}_i+b)\ge \widehat{\gamma },}& {\displaystyle i=1,2,\mathrm{.}\mathrm{.}\mathrm{.},N}\end{array}$$
因为目标函数和约束条件都存在函数间隔，因此函数间隔的取值最优化问题的解，设$\bar{\gamma }=1$,至此，得到了线性可分支持向量机的最优化问题

$$\begin{array}{rl}{\displaystyle }& {\displaystyle \underset{w,b}{\min }\frac{1}{2}\mathrm{\mid }\mathrm{\mid }w\mathrm{\mid }{\mathrm{\mid }}^2}\\ {\displaystyle }& {\displaystyle s\mathrm{.}t\mathrm{.}{y}_i(w\mathrm{.}{x}_i+b)-1\ge 0i=1,2,\mathrm{.}\mathrm{.}\mathrm{.},N}\end{array}$$

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

存在性

样本集中包含正负类样本，也就是说最优解肯定不是$(w,b)=(0,b)$，由此可以说明最大分离超平面的存在性

唯一性

比较麻烦。。。，以后有空再来详细证明。

支持向量和间隔边界

所谓支持向量就是满足$y_i(w\mathrm{.}{x}_i+b)-1=0$的实例，也就是说这些实例为最优化问题的约束条件的边界情形。

对于类别为$y=+1$的正点，支持向量在超所在的超平面为
$$H_1:w\mathrm{.}x+b=1$$
对于类别为$y=-1$的正点，支持向量在超所在的超平面为
$$H_2:w\mathrm{.}x+b=-1$$
对于线性可分的样本集来说，没有实例会落在分离超平面$H_1,H_2$之间，在超平面之间的距离称为间隔，间隔依赖于分离超平面的法向量$w$，等于$\frac{2}{\mathrm{\mid }\mathrm{\mid }w\mathrm{\mid }\mathrm{\mid }}$，两个超平面$H_1{H}_2$是间隔边界。

在进行分离超平面计算时，只有支持向量决定。任意线性可分的两组点，它们在SVM分类超平面上的有赢都是线性不可分的。在间隔边界之外的点不会影响最优解的计算，也就是说，分离超平面由支持向量来确定。

对偶算法

之所以使用对偶算法是因为

• 对偶问题更容易求解
• 可以引入核函数进而推广至非线性分类问题

对偶问题的定义

如果存在这样的目标函数和约束条件
$$\begin{array}{rlr}{\displaystyle }& {\displaystyle \underset{x\in R^2}{\min }}& {\displaystyle f(x)}\\ {\displaystyle }& {\displaystyle s\mathrm{.}t\mathrm{.}}& {\displaystyle g_i(x)\le 0}& {\displaystyle i=1,2,\mathrm{.}\mathrm{.}\mathrm{.},k}\\ {\displaystyle }& {\displaystyle }& {\displaystyle h_j(x)=0}& {\displaystyle j=1,2,\mathrm{.}\mathrm{.}\mathrm{.},l}\end{array}$$
得到其拉格朗日函数为
$$L(x,\alpha ,\beta )=f(x)+\sum _{i=1}^k{\alpha }_i{g}_i(x)+\sum _{j=1}^l{\beta }_j{h}_j(x)$$
并且有${\alpha }_i\ge 0$

其对偶问题为
$$\underset{\alpha ,\beta }{\max }\underset{x}{\min }L(x,\alpha ,\beta )$$

svm优化函数的对偶问题

根据对偶函数的定义可以应用到svm优化函数

将优化函数的目标函数和约束条件创建拉个朗日函数
$$\begin{array}{rl}{\displaystyle L(w,b,\alpha )}& {\displaystyle =\frac{1}{2}\mathrm{\mid }\mathrm{\mid }w\mathrm{\mid }{\mathrm{\mid }}^2-\sum _{i=1}^N{\alpha }_i{y}_i(w\mathrm{.}{x}_i+b)+\sum _{i=1}^N{\alpha }_i}\\ {\displaystyle {\alpha }_i}& {\displaystyle \ge 0i=1,2,\mathrm{.}\mathrm{.}\mathrm{.},N}\end{array}$$

根据拉格朗日对偶性，得到对偶问题的极大极小问题
$$\underset{\alpha }{\max }\underset{w,b}{\min }L(w,b,\alpha )$$
也就是先进行极小在进行极大计算
$$\begin{array}{rl}{\displaystyle {\mathrm{\nabla }}_{w}L(w,b,\alpha )=0}& {\displaystyle \Rightarrow w=\sum _{i=1}^N{\alpha }_i{y}_i{x}_i}\\ {\displaystyle {\mathrm{\nabla }}_{b}L(w,b,\alpha )=0}& {\displaystyle \Rightarrow \sum _{i=1}^N{\alpha }_i{y}_i=0}\\ {\displaystyle {\mathrm{\nabla }}_{\alpha }L(w,b,\alpha )=0}& {\displaystyle \Rightarrow \underset{\alpha }{\max }-\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i\mathrm{.}{x}_j)+\sum _{i=1}^N{\alpha }_i}\end{array}$$

最优问题及其解

有上述的公式可以得到对偶问题的最优化问题
$$\begin{array}{rl}{\displaystyle \underset{\alpha }{\min }}& {\displaystyle \frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i\mathrm{.}{x}_j)-\sum _{i=1}^N{\alpha }_i}\\ {\displaystyle s\mathrm{.}t\mathrm{.}}& {\displaystyle \sum _{i=1}^N{\alpha }_i{y}_i=0}\\ {\displaystyle }& {\displaystyle {\alpha }_i\ge 0i=1,2,\mathrm{.}\mathrm{.}\mathrm{.},N}\end{array}$$
最优问题对应的解就是
$$\begin{array}{rl}{\displaystyle w^{\ast }}& {\displaystyle =\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i{x}_i}\\ {\displaystyle b^{\ast }}& {\displaystyle =y_j-\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i(x_i\mathrm{.}{x}_j)}\end{array}$$
决策函数可以写成
$$f(x)=sign(w^{\ast }\mathrm{.}x+b^{\ast })=sign(\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i(x\mathrm{.}{x}_i)+b^{\ast })$$

线性支持向量机

软间隔

对于线性可分的数据使用线性可分支持向量机可以完成任务，但是对于线性不可分的数据，这时候就要线性可分支持向量机的硬间隔变为软间隔，线性不可分实际上意味着在数据集中存在某些点不能满足函数间隔大于等于1的最优问题约束条件，修改约束条件
$$y_i(w\mathrm{.}{x}_i+b)\ge 1-{\xi }_i$$
同时目标函数修改为
$$\frac{1}{2}\mathrm{\mid }\mathrm{\mid }w\mathrm{\mid }{\mathrm{\mid }}^2+C\sum _{i=1}^N{\xi }_i$$

• 其中$C$是惩罚参数，类似于正则化的概念

得到对于线性支持向量机的最优化问题
$$\begin{array}{rl}{\displaystyle \underset{w,b,\xi }{\min }}& {\displaystyle \frac{1}{2}\mathrm{\mid }\mathrm{\mid }w\mathrm{\mid }{\mathrm{\mid }}^2+C\sum _{i=1}^N{\xi }_i}\\ {\displaystyle s\mathrm{.}t\mathrm{.}}& {\displaystyle y_i(w\mathrm{.}{x}_i+b)\ge 1-{\xi }_i}& {\displaystyle i=1,2,\mathrm{.}\mathrm{.}\mathrm{.},N}\\ {\displaystyle }& {\displaystyle {\xi }_i\ge 0}& {\displaystyle i=1,2,\mathrm{.}\mathrm{.}\mathrm{.},N}\end{array}$$
实际上线性支持向量机是对线性可分支持向量机的扩展，具有更好的适用性。

从图中可以看到，分离分离超平面将数据集分为两个部分，由于数据集为线性不可分，因此存在软间隔。数据集中的示例会存在三种情形，及其对应的存在对偶问题解与软间隔的关系如下：

• 在间隔边界与分离超平面之间
  $$a_i^{\ast }=C0<{\xi }_i<1$$

• 在间隔边界上
  $$a_i^{\ast }<C{\xi }_i=1$$

• 在分离超平面误分的一侧
  $$a_i^{\ast }<C{\xi }_i>1$$

对偶算法

同样是首先得到拉格朗日函数
$$\begin{array}{rl}{\displaystyle L(w,b,\xi ,\alpha ,\mu )}& {\displaystyle =\frac{1}{2}\mathrm{\mid }\mathrm{\mid }w\mathrm{\mid }{\mathrm{\mid }}^2+C\sum _{i=1}^N{\xi }_i-\sum _{i=1}^N{\alpha }_i[y_i(w\mathrm{.}{x}_i+b)-1+{\xi }_i]+\sum _{i=1}^N{\mu }_i{\xi }_i}\\ {\displaystyle {\alpha }_i}& {\displaystyle \ge 0i=1,2,\mathrm{.}\mathrm{.}\mathrm{.},N}\\ {\displaystyle {\mu }_i}& {\displaystyle \ge 0i=1,2,\mathrm{.}\mathrm{.}\mathrm{.},N}\end{array}$$
然后对偶问题的极大极小问题
$$\underset{\alpha ,\mu }{\max }\underset{w,b,\xi }{\min }L(w,b,\alpha )$$

最优问题及其解

所以极大极小问题进行求偏导并且偏导数为0，则可以得到对偶问题最优解
$$\begin{array}{rl}{\displaystyle \underset{\alpha }{\min }}& {\displaystyle \frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i\mathrm{.}{x}_j)-\sum _{i=1}^N{\alpha }_i}\\ {\displaystyle s\mathrm{.}t\mathrm{.}}& {\displaystyle \sum _{i=1}^N{\alpha }_i{y}_i=0}\\ {\displaystyle }& {\displaystyle 0\le {\alpha }_i\le Ci=1,2,\mathrm{.}\mathrm{.}\mathrm{.},N}\end{array}$$
对应的最优解为
$$\begin{array}{rl}{\displaystyle w^{\ast }}& {\displaystyle =\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i{x}_i}\\ {\displaystyle b^{\ast }}& {\displaystyle =y_j-\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i(x_i\mathrm{.}{x}_j)}\end{array}$$
可以看到最优解与线性可分支持向量机相同，只是最优解的约束条件里有原来的$a_i\ge 0$ 增加了新的约束条件为$0\le {\alpha }_i\le C$

线性支持向量机的决策函数可以写成
$$f(x)=sign(w^{\ast }\mathrm{.}x+b^{\ast })=sign(\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i(x\mathrm{.}{x}_i)+b\ast )$$

最优化问题的Hinge损失函数等价形式

Hinge损失函数，主要用于解决间隔最大化的问题，定义如下
$$\begin{array}{rl}{\displaystyle \iota (y_i,\widehat{y_i})=}& {\displaystyle \max \{0,1-y_i\mathrm{.}\widehat{y_i}\}}\\ {\displaystyle y_i\in }& {\displaystyle \{-1,1\}}\end{array}$$
那么如何将SVM的损失函数写成Hinge的格式，下面开始。

对应于svm中，存在等式关系
$$\widehat{y}=w\mathrm{.}x+b$$
则函数的定义可以写成如下形式
$$\iota (y_i,\widehat{y_i})=\max \{0,1-y(w\mathrm{.}x+b)\}$$
可以写成如下形式
$$\begin{array}{r}{\displaystyle \max \{0,1-y(w\mathrm{.}x+b)\}=[1-y\mathrm{.}(w\mathrm{.}x+b){]}_{+}}\end{array}$$
其中存在关系如下
$$[1-y\mathrm{.}(w\mathrm{.}x+b){]}_{+}=\{\begin{array}{ll}1-y\mathrm{.}(w\mathrm{.}x+b)& 1-y\mathrm{.}(w\mathrm{.}x+b)>0\\ 0& 1-y\mathrm{.}(w\mathrm{.}x+b)\le 0\end{array}$$
也就是说，当SVM正确分类并且函数间隔$y\mathrm{.}(w\mathrm{.}x+b)>1$时函数损失为0，否则函数损失为$1-y_i\mathrm{.}(w\mathrm{.}{x}_i+b)$

根据上面部分得到的线性支持向量机的原始最优化问题
$$\begin{array}{rl}{\displaystyle \underset{w,b,\xi }{\min }}& {\displaystyle \frac{1}{2}\mathrm{\mid }\mathrm{\mid }w\mathrm{\mid }{\mathrm{\mid }}^2+C\sum _{i=1}^N{\xi }_i}\\ {\displaystyle s\mathrm{.}t\mathrm{.}}& {\displaystyle y_i(w\mathrm{.}{x}_i+b)\ge 1-{\xi }_i}& {\displaystyle i=1,2,\mathrm{.}\mathrm{.}\mathrm{.},N}\\ {\displaystyle }& {\displaystyle {\xi }_i\ge 0}& {\displaystyle i=1,2,\mathrm{.}\mathrm{.}\mathrm{.},N}\end{array}$$
观察最优化问题，存在约束条件${\xi }_i\ge 0$，因此可以令$[1-y_i\mathrm{.}(w\mathrm{.}{x}_i+b){]}_{+}={\xi }_i$，存在如下关系，当$1-y_i\mathrm{.}(w\mathrm{.}{x}_i+b)>0$时存在$1-y_i\mathrm{.}(w\mathrm{.}{x}_i+b)={\xi }_i$，存在关系式$y_i\mathrm{.}(w\mathrm{.}{x}_i+b)=1-{\xi }_i$；当$1-y_i\mathrm{.}(w\mathrm{.}{x}_i+b)\le 0$时存在$1-y_i\mathrm{.}(w\mathrm{.}{x}_i+b)={\xi }_i=0$同样存在关系式$y_i\mathrm{.}(w\mathrm{.}{x}_i+b)\ge 1-{\xi }_i$因此当$1-y_i\mathrm{.}(w\mathrm{.}{x}_i+b){]}_{+}={\xi }_i$时满足原始最优问题的约束条件。

现在观察最优化问题的目标函数
$$\underset{w,b,\xi }{\max }\frac{1}{2}\mathrm{\mid }\mathrm{\mid }w\mathrm{\mid }{\mathrm{\mid }}^2+C\sum _{i=1}^N{\xi }_i$$
可以改写成如下形式
$$\begin{array}{rllll}& {\displaystyle \underset{w,b,\xi }{\min }\frac{1}{2}\mathrm{\mid }\mathrm{\mid }w\mathrm{\mid }{\mathrm{\mid }}^2+C\sum _{i=1}^N{\xi }_i}& {\displaystyle ⟺\underset{w,b}{\min }\frac{1}{2}\mathrm{\mid }\mathrm{\mid }w\mathrm{\mid }{\mathrm{\mid }}^2+C\sum _{i=1}^N[1-y_i\mathrm{.}(w\mathrm{.}{x}_i+b){]}_{+}}& & \\ & {\displaystyle }& {\displaystyle ⟺\underset{w,b}{\min }\sum _{i=1}^N[1-y_i\mathrm{.}(w\mathrm{.}{x}_i+b){]}_{+}+\lambda \mathrm{\mid }\mathrm{\mid }w\mathrm{\mid }{\mathrm{\mid }}^2}& & \end{array}$$
至此也就得到了SVM的最优化问题的Hinge损失函数的等价形式。

非线性支持向量机

上面主要是说的线性可分支持向量机和线性支持向量机，在原始数据的向量空间存在分离超平面将数据划分，而算法学习的过程就是找到该分离超平面的过程。但是在实际中，数据绝大部分是非线性的，这时候可以利用核函数的技巧进行原始数据的非线性映射，将原始数据映射到线性可分的高维空间，并在高维空间上利用线性支持向量机的相关算法进行数据划分，在聚类计算中，同样有利用核函数的方法。

对于非线性支持向量机来说，算法的目标就不是找到分离超平面了，而是找到分离超曲面。并且通过核函数的方法对原来的数据空间进行非线性变换，将其转换到线性空间，将非线性问题转换到线性问题。

在原数据空间中，因为是分离超曲面，可以看做分离超平面的形式为
$$w_1(x^{(1)}{)}^2+w_2(x^{(2)}{)}^2+b=0$$
假设给定的数据空间是$x\subset {\mathbf{\text{R}}}^2$，样本为$x=(x^{(1)},x^{(2)})\in \mathbf{\text{X}}$，进行线性变换之后的数据空间为$z\subset {\mathbf{\text{R}}}^2$，样本为$z=(z^{(1)},z^{(2)})\in \mathbf{\text{Z}}$，存在非线性变化
$$z=\varphi (x)=((x^{(1)}{)}^2,(x^{(2)}{)}^2{)}^T$$
在新的数据空间中，原来的分离超曲面变换为
$$w_1{z}^{(1)}+w_2{z}^{(2)}+b=0$$

核函数

假设$\mathbf{\text{X}}$是输入空间，$\mathbf{\text{H}}$是特征空间，假设存在一个输入空间到特征空间的映射$\varphi (x):\mathbf{\text{X}}\to \mathbf{\text{H}}$使得所有的$x,z\in \mathbf{\text{X}}$，存在函数满足条件：
$$\mathbf{\text{K}}(x,z)=\varphi (x)\mathrm{.}\varphi (z)$$

• $\mathbf{\text{K}}(x,z)$就是核函数，$\varphi (x)$就是映射函数，$\varphi (x)\mathrm{.}\varphi (z)$表示二者的內积。

核函数的思想：

在学习和预测的时候只定义核函数$\mathbf{\text{K}}(x,z)$，并不直接定义映射函数$\varphi (x)$，一般来说直接计算$\mathbf{\text{K}}(x,z)$更加简单。此外，核函数$\mathbf{\text{K}}(x,z)$通常来讲并不是唯一的。

核函数与支持向量机

在线性支持向量机中，对偶算法最优问题为
$$\begin{array}{rl}{\displaystyle \underset{\alpha }{\min }}& {\displaystyle \frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i\mathrm{.}{x}_j)-\sum _{i=1}^N{\alpha }_i}\\ {\displaystyle s\mathrm{.}t\mathrm{.}}& {\displaystyle \sum _{i=1}^N{\alpha }_i{y}_i=0}\\ {\displaystyle }& {\displaystyle 0\le {\alpha }_i\le Ci=1,2,\mathrm{.}\mathrm{.}\mathrm{.},N}\end{array}$$
其中$y=\{-1,+1\}$

将內积$x_i\mathrm{.}{x}_j$使用核函数代替$\mathbf{\text{K}}(x_i,x_j)$，得到对偶问题为：
$$\begin{array}{rl}{\displaystyle \underset{\alpha }{\min }}& {\displaystyle \frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j\mathbf{\text{K}}(x_i,x_j)-\sum _{i=1}^N{\alpha }_i}\\ {\displaystyle s\mathrm{.}t\mathrm{.}}& {\displaystyle \sum _{i=1}^N{\alpha }_i{y}_i=0}\\ {\displaystyle }& {\displaystyle 0\le {\alpha }_i\le Ci=1,2,\mathrm{.}\mathrm{.}\mathrm{.},N}\end{array}$$
对应的决策函数为：
$$\begin{array}{rl}{\displaystyle f(x)=sign(w^{\ast }\mathrm{.}x+b^{\ast })}& {\displaystyle =sign(\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i(x\mathrm{.}{x}_i)+b^{\ast })}\\ {\displaystyle }& {\displaystyle =sign(\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i\mathbf{\text{K}}(x_i,x_j)+b^{\ast })}\end{array}$$
其中参数$w^{\ast }$和$b^{\ast }$为优化问题的解。

观察解题思路，实际上就是非线性数据空间进行核函数映射，将其映射到线性可分的高维空间，在高维空间上，使用线性支持向量的方法进行运算

常用核函数

通常所说的核函数指的是正定核函数

• 多项式核函数
  $$\mathbf{\text{K}}(x,z)=(x\mathrm{.}z+1{)}^p$$
  这是一个一个$p$次多项式，在这种情形下，分类决策函数为
  $$\begin{array}{rl}{\displaystyle f(x)}& {\displaystyle =sign(\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i\mathbf{\text{K}}(x_i,x_j)+b^{\ast })}\\ {\displaystyle }& {\displaystyle =sign(\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i(x\mathrm{.}z+1{)}^p+b^{\ast })}\end{array}$$

• 高斯核函数
  $$\mathbf{\text{K}}(x,z)=exp(-\frac{\mathrm{\mid }\mathrm{\mid }x-z\mathrm{\mid }{\mathrm{\mid }}^2}{2{\sigma }^2})$$
  对应的分类决策函数为
  $$\begin{array}{rl}{\displaystyle f(x)}& {\displaystyle =sign(\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i\mathbf{\text{K}}(x_i,x_j)+b^{\ast })}\\ {\displaystyle }& {\displaystyle =sign(\sum _{i=1}^N{\alpha }_i^{\ast }{y}_{i}exp(-\frac{\mathrm{\mid }\mathrm{\mid }x-z\mathrm{\mid }{\mathrm{\mid }}^2}{2{\sigma }^2})+b^{\ast })}\end{array}$$

SMO-序列最小最优化算法

线性支持向量机的最优化问题为
$$\begin{array}{rl}{\displaystyle \underset{\alpha }{\min }}& {\displaystyle \frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i\mathrm{.}{x}_j)-\sum _{i=1}^N{\alpha }_i}\\ {\displaystyle s\mathrm{.}t\mathrm{.}}& {\displaystyle \sum _{i=1}^N{\alpha }_i{y}_i=0}\\ {\displaystyle }& {\displaystyle 0\le {\alpha }_i\le Ci=1,2,\mathrm{.}\mathrm{.}\mathrm{.},N}\end{array}$$
对应的最优解为
$$\begin{array}{rl}{\displaystyle w^{\ast }}& {\displaystyle =\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i{x}_i}\\ {\displaystyle b^{\ast }}& {\displaystyle =y_j-\sum _{i=1}^N{\alpha }_i^{\ast }{y}_i(x_i\mathrm{.}{x}_j)}\end{array}$$
这个问题中，变量是${\alpha }_i$,一个变量对应一个实例$(x_i,y_i)$,变量的总数与样本集中实例的数量相等为$N$

SMO算法包含两个部分

• 两个变量二次规划的求解方法
• 选择变量的启发式算法

两个变量二次规划的求解方法

先选择两个变量${\alpha }_1,{\alpha }_2$,固定其余的变量，最优化问题变为
$$\begin{array}{rlr}{\displaystyle }& {\displaystyle \underset{\alpha }{\min }}& {\displaystyle \frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_j(x_i\mathrm{.}{x}_j)-\sum _{i=1}^N{\alpha }_i}\\ {\displaystyle \Rightarrow }& {\displaystyle \underset{{\alpha }_1,{\alpha }_2}{\min }}& {\displaystyle \frac{1}{2}{K}_{11}{\alpha }_1^2{y}_1^2+\frac{1}{2}{K}_{22}{\alpha }_2^2{y}_2^2+y_1{y}_2{K}_{12}{\alpha }_1{\alpha }_2+y_1{\alpha }_1\sum _{i=3}^N{\alpha }_i{y}_i{K}_{i1}+y_2{\alpha }_2\sum _{i=3}^N{\alpha }_i{y}_i{K}_{i1}}\\ {\displaystyle }& {\displaystyle s\mathrm{.}t\mathrm{.}}& {\displaystyle {\alpha }_1{y}_1+{\alpha }_2{y}_2=-\sum _{i=3}^N{\alpha }_i{y}_i=\zeta }\\ {\displaystyle }& {\displaystyle }& {\displaystyle 0\le {\alpha }_i\le C}\end{array}$$