核技巧
映射函数： \phi(x): X \rightarrow H
X为输入空间（欧氏空间R^n的子集或离散集合）
H为特征空间，一般是高维的
函数K(x, z) = \phi(x) · \phi(z)，则称K(x, z)为核函数
将 \langle x_i, x_j \rangle 替换为 K(x_i, x_j) 此时对偶问题为
\mathop{max}\limits_{\lambda}-\frac{1}{2}\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{N}\lambda_i\lambda_jy_iy_jK(x_i,x_j) + \sum\limits_{i=1}^{N}\lambda_i正定核的充要条件
K(x,z)对应的Gram矩阵是半正定矩阵
序列最小最优化(SMO)算法
选定两个变量\lambda_1和\lambda_2，则原问题可以写成
\mathop{min}\limits_{\lambda_1,\lambda_2}~W(\lambda_1,\lambda_2) = \frac{1}{2}K_{11}{\lambda_1}^2 + \frac{1}{2}K_{22}{\lambda_2}^2 + y_1y_2K_{12}\lambda_1\lambda_2 - (\lambda_1 + \lambda_2) + y_1\lambda_1\sum\limits_{i=3}^{N}y_i\lambda_iK_{i1} + y_2\lambda_2\sum\limits_{i=3}^{N}y_i\lambda_iK_{i2}
\\
s.t. ~~~\lambda_1y_1 + \lambda_2y_2 = -\sum\limits_{=3}^{N}y_i\lambda_i, ~~~
0 \leq \lambda_i \leq C因为只有两个变量，约束可以用二维空间中的图形表示
假设初始可行解为 \lambda_1^{old}, ~\lambda_2^{old} 最优解为 \lambda_1^{new}, ~\lambda_2^{new} 未剪辑的最优解为 \lambda_1^{new,unc},~ \lambda_2^{new,unc}
可知
L \leq \lambda_2^{new} \leq H若y_1 != y_2
L = max(0, \lambda_2^{old} - \lambda_1^{old})
\\
H = min(C, C + \lambda_2^{old} - \lambda_1^{old})若y_1 == y_2
L = max(0, \lambda_2^{old} + \lambda_1^{old} - C)
\\
H = min(C, \lambda_2^{old} + \lambda_1^{old})为了方便，记
g(x) = \sum\limits_{i=1}^{N}\lambda_iy_iK(x_i,x) + b
\\
E_i = g(x_i) - y_i可以得到
\lambda_2^{new,unc} = \lambda_2^{old} + \frac{y_2(E_1 - E_2)}{\eta}
\lambda_1^{new} = \lambda_1^{old} + y_1y_2(\lambda_2^{old} - \lambda_2^{new})下面叙述SMO算法的一般步骤
1.第一个变量的选择
检验训练样本(x_i,y_i)是否满足KKT条件，即
\lambda_i = 0 \Leftrightarrow y_ig(x_i) \geq 1
\\
0 \leq \lambda_i \leq C \Leftrightarrow y_ig(x_i) = 1
\\
\lambda_i = C \Leftrightarrow y_ig(x_i) \leq 1优先选择间隔边界上的支持向量点(0 \leq \lambda_i \leq C)，如果没有，再从整个训练集中选择
2.第二个变量的选择
选择\lambda_2^{new}，使其对应的|E_1 - E_2|最大，即
如果E_1是正的 选择最小的E_i作为E_2
如果E_1是负的 选择最大的E_i作为E_2