如果您想体验更好的阅读：请戳这里littlefish.top
##线性不可分情况
线性可分问题的支持向量机学习方法，对线性不可分训练数据是不适用的，为了满足函数间隔大于1的约束条件，可以对每个样本$(x_i, y_i)引进一个松弛变量\xi_i \ge 0$，使函数间隔加上松弛变量大于等于1,，
y\_i (w \cdot x\_i + b) \ge 1 - \xi\_i
目标函数变为
\frac 1 2 {||w||^2} + C \sum\_{j=1}^N \xi\_i
其中，C>0称为惩罚参数，值越大对误分类的惩罚越大，值越小对误分类的惩罚越小。
因此，最小化目标函数也就是使12||w||2尽量小（间隔尽量大），同时使误分类点的个数尽量小。
线性不可分的线性支持向量机的学习问题变成如下凸二次规划问题：
###线性支持向量学习算法
- 选择惩罚参数C>0，构造并求解凸二次规划问题
求得最优解α∗=(α∗1,α∗2,...,α∗N)T
- 计算$w^*=\sum_{i=1}N \alpha_i* y_i x_i$
选择$\alpha^*的一个分量\alpha_j^*适合条件0<\alpha_j^*<C$，计算
b^\*=y\_i - \sum\_{i=1}^N y\_i \alpha\_i^\*(x\_i \cdot x\_j)
- 求得分离超平面
w^\* \cdot x + b^\* = 0
分类决策函数：
f(x) = sign(w^\* \cdot x + b^\*)
##核函数
用线性分类方法求解非线性分类问题分为两步：首先使用一个变换将原空间的数据映射到新空间；然后在新空间里用线性分类学习方法从训练数据中学习分类模型。
核技巧应用在支持向量机的基本思想：通过一个非线性变换将输入空间（欧式空间$Rn或离散集合）对应于一个特征空间（希尔伯特空间H），使得在输入空间Rn$中的超曲面模型对应于特征空间H中的超平面模型（支持向量机）。
##非线性支持向量分类机
###非线性支持向量机
从非线性分类训练集，通过核函数与间隔最大化或凸二次规划，学习得到的分类决策函数：
f(x)=sign(\sum\_{i=1}^N \alpha\_i^\*y\_i K(x,x\_i) + b^\*)
称为非线性支持向量，K(x,z)是正定核函数。
###学习算法
- 选择适当的核函数K(x,z)和适当的参数C，构造并求解最优化问题
求解最优解α∗=(α∗1,α∗2,...,α∗N)
- 选择α∗的第一个正分量0<α∗j<C，计算
b^\*=y\_i - \sum\_{i=1}^N \alpha\_i^\* y\_i K(x\_i \cdot x\_j)
- 构造决策函数
f(x)=sign(\sum\_{i=1}^N \alpha\_i^\* y\_i K(x \cdot x\_i) + b^\*)
##序列最小优化算法
SMO算法是一种启发式算法。如果所有变量都满足KKT条件，那么这个最优化问题就解决了（KKT问题是该最优化问题的充要条件），否则，选择两个变量，固定其他变量，针对这两个变量构造二次规划问题。该方法会使原始二次规划问题的目标函数变小，不断分解自问题并对子问题求解进而达到求解原问题的目的。
由于
\sum\_{i=1}^N \alpha\_i y\_i = 0
所以
\alpha\_i = - \frac 1 {y\_i} \sum\_{i=2}^N \alpha\_i y\_i
###两个变量的二次规划求解
假设选择两个变量α1，α2，
$$\min_{\alpha_1\alpha_2} \quad = \frac 1 2 K_{11} \alpha_12 + \frac 1 2 K_{22} \alpha_22 + y_1 y_2 K_{12} \alpha_1 \alpha_2 \
\quad (\alpha_1 + \alpha_2) + y_1 \alpha_1 \sum_{i=3}^N y_i \alpha_i K_ + y_2\alpha_2\sum_{i=3}^N y_i \alpha_i K_{12} \
s.t. \quad \alpha_1 y_1 + \alpha_2 y_2 = - \sum_{i=3}^N y_i \alpha_i = \xi \
0 \le \alpha_i \le C, i=1,2$$
由于只有两个变量$(\alpha_i,\alpha_j)，因此根据两变量的符号情况约束条件可用二位空间中的图表示（参考\alpha_1 y_1 + \alpha_2 y_2 = \xi(常数)$），
L和H是α取值的最小和最大值，如果yi!=yj，则
L=\max(0,\alpha\_2 - \alpha\_1), H=\min(C,C+\alpha\_2-\alpha\_1)
如果yi=yj，则
L=\max(0,\alpha\_2 + \alpha\_1 + C), H=\min(C,\alpha\_2+\alpha\_1)
令
g(x) = \sum\_{i=1}^N \alpha\_i y\_i K(x\_i, x) + b
得到误差值：
E\_i = g(x\_i) - y\_i = ( \sum\_{i=1}^N \alpha\_i y\_i K(x\_i, x) + b) - y\_i$, \quad i = 1,2
此最优问题的解是：
\alpha\_2^{new} = \alpha\_2^{old} + y\_2 \frac {(E\_1 - E\_2)} \eta
其中，
\eta = K\_{11} + K\_{22} - 2K\_{12} = {||\phi(x\_1) - \phi(x\_2)||}^2
ϕ(x)为输入空间到特征空间的映射，经过剪辑后是
H,\quad \alpha_2^ > H \
\alpha_2^, \quad L \le \alpha_2^ \le H \
L,\quad \alpha_2^ < L \end
则\alpha_1^为
\alpha\_1^{new} = \alpha\_1^{old} + y\_1 y\_2 (\alpha\_2^{old} - \alpha\_2^{new})
###变量的选择方法
SMO算法在每个子问题中选择两个变量优化，其中至少一个变量是违反KKT条件的。
1.第1个变量的选择
SMO算法在外层循环中选取违反KKT条件最严重的样本点，并将其对应的变量作为第1个变量，KKT条件如下
其中，g(x\_i) = \sum_{j=1}^N \alpha\_j y\_j K(x\_i,x\_j)+b。
该检验在ϵ范围内进行的，在校验过程中，外层循环首先遍历所有满足条件0<αi<C的样本点，即在间隔边界上的支持向量点，检验它们是否满足KKT条件。如果这些样本点都满足KKT条件，那么遍历整个训练集，检验它们是否满足KKT条件。
2.第2个变量的选择
SMO算法在内层循环，假设在外层循环中已经找到第一个变量α1，现在要在内层循环中找到第2个变量α2，第2个变量选择的标准是希望能使α2有足够的变化。根据上一节可知，$\alpha_2^是依赖|E_1 - E_2|的，为了加快计算速度，最简单的做法是选择|E_1 - E_2|最大的（如果E_1为负值，则选择最大的E_i作为E_2，否则选择最小的E_i为E_2，需要保存所有的E_i$）。
3.计算阈值b和差值Ei
在每次完成两个变量优化后，都要重新计算阈值b。
由KKT条件得
\sum\_{i=1}^N \alpha\_i y\_i K\_{i1} + b = y\_i
从而
b\_1^{new} = y\_1 - \sum\_{i=3}^N \alpha\_i y\_i K\_{i1} - \alpha\_1^{new} y\_1 K\_{11} - \alpha\_2^{new} y\_2 K\_{21}
由于Ei=g(xi)−yi=(∑Ni=1αiyiK(xi,x)+b)−yi, \quad i = 1,2$，则
E\_1 = g(x\_1) - y\_1 = \sum\_{i=3}^N \alpha\_i y\_i K\_{i1} + \alpha\_1^{old} y\_1 K\_{11} + \alpha\_2^{old} y\_2 K\_{21} + b^{old} - y\_1
将上式中的$y_i - \sum_{i=3}N \alpha_i y_i K_ 代入b_1$的公式中，得到
b\_1^{new} = -E\_1 - y\_1 K\_{11} (\alpha\_1^{new} - \alpha\_1^{old} ) - y\_2 K\_{21} (\alpha\_2^{new} - \alpha\_2^{old} ) + b^old
对于b的取值：
\frac {b_1^ + b_2^} 2,\quad \alpha_i^ == 0 or C，满足KKT条件\end
