支持向量机

一、什么是支持向量机

支持向量机(Suport Vector Machine,常简称为SVM），是一个监督式学习的方式。支持向量机属于一般化线性分类器，这类分类器的特点是能够同时最小化经验误差与最大化几何边缘区，因此支持向量机机也被称为最大边缘区分类器。

SVM.png

max margin.png

蓝色和红色的线圈出来的点就是所谓的支持向量，离分界线最近的点，如果去掉这些点，直线多半要改变位置。Classifier Boundary就是决策函数f(x)，在两个类的中间。红色和蓝色之间的间隙就是我们要的最大化分类的间隙。

二、关于拉格朗日乘子法和KKT条件

1.关于拉格朗日乘子法

有拉格朗日乘子法的地方，必然是一个组合优化问题。比如
$\begin{align} min \space f = 2x_1^2+3x_2^2+7x_3^2 \\ s.t. 2x_1 + x_2 = 1 \\ 2x_2+3x_3 = 2 \end{align}$

这是一个带等式约束的优化问题，有目标值，有约束条件，不能直接求导。可以使用拉格朗日方法，把这个约束乘以一个系数加到目标函数中去，这样相当与既考虑了原目标函数，也考虑了约束条件。然后分别对x求导等于0，
$\begin{align} \frac{\partial{f}}{\partial{x_2}} = 4x_1+2\alpha_1 = 0 \implies x_1 = -0.5\alpha_1 \\ \frac{\partial f} {\partial x_2} = 6x_2+\alpha_1+2\alpha_2 = 0 \implies x_2 = -\frac{\alpha_1+2\alpha_2}{6} \\ \frac{\partial f}{\partial x_3} = 14x_3+3\alpha_2 = 0 \implies x_3 = -\frac{3\alpha_2}{14} \end{align}$
把它带点菜约束条件中去，可以看到，2个变量两个等式，最终可再带回去求x就可以了。更高一层，带有不等式的约束问题怎么办？需要用更一般化的拉格朗日乘子法，即KKT条件，来求解这个问题。

2.关于KKT条件

任何原始问题约束条件无非最多三种，等式约束，大于号约束，小于号约束，而这三种最终通过将约束方程简化成两类：约束方程等于0和约束方程小于0。

假设原始问题约束条件为下例所示：
$\begin{align} min \space f = x_1^2-2x_1+1+x_2^2+4x_2+4 \\ s.t. \space x_1 + 10x_2 > 10 \\ 10x_1 - 10 x_2 < 10 \end{align}$
那么把约束条件变个样子
$\begin{align} s.t. \space 10 -x_1 - 10x_2 < 0 \\ 10x_1 - 10 x_2 < 10 \end{align}$
现在拿到目标函数中去变成
$\begin{align} L(x,\alpha) = f(x)+\alpha_1 g_1(x)+\alpha_2 g_2(x) \\ = x_1^2 - 2x_1+1+x_2^2+4x_2+4+\alpha_1(10-x_1+10x_2)+\alpha_2(10x_2-x_2-10) \end{align}$

那么KKT条件的定理是什么呢？就是如果一个优化问题在转变成
$L(x,\alpha,\beta) = f(x) +\sum \alpha_ig_i(x) + \sum \beta_ih_i(x)$
其中g是不等式约束，h是等式约束。那么KKT条件就是函数的最优值，它必定满足下面条件：

L对各个x求导为0
$h(x) = 0$
$\sum \alpha_ig_i(x) = 0 ,\alpha_i \le 0$

这三个等式很好理解，重点是第三个句子不好理解，因为我们知道在约束条件变完或，所有的 $g(x) \le 0$ ，且求和还要为0。那么为什么KKT的条件是这样的呢？

某次的g(x)在为最优解起作用，那么它的系数值（可以）不为0，如果某次g(x)没有为下一次的最优解起作用，那么它的系数就必须为0。

三、函数间隔和几何间隔

函数间隔
对于给定的训练数据集T合超平面(w,b)，定义超平面(w,b)关于样本点 $(x_i,y_i)$ 的函数间隔为 $\hat{\gamma_i} = y_i(\omega*x_i+b)$

函数间隔可以表示分类预测的正确性及确信度。但是选择超平面时，只有函数间隔是不够的，因子只要成比较改变 $\omega$ 和b，超平面并没有改变，但函数间隔却扩大了。

几何间隔
对于给定的训练数据集T和超平面 $(\omega,b)$ ，定义超平面 $(\oemga,b)$ 关于样本点 $(x_i,y_i)$ 的几何间隔为 $\hat \gamma = y_i(\frac{\omega}{\|\omega\|}*x_i+\frac{b}{\|\omega\|}$ ,其中 $\|\omega\|$ 为 $\omega$ 的 $L_2$ 范数。

如果 $\|\omega\|=1$ ，那么函数间隔和几何间隔相等。如果超平面参数 $\omega,b$ 成比例地改变（超平面没有改变），函数间隔也成比例改变，而几何间隔不变。

四、间隔最大化

支持向量机的基本想法是求解能够正确分训练数据集并且几何间隔最大的分离超平面。对线性可分的训练数据集而言，线性可分分离超平面有无穷多个（等价于感知机），但是几何间隔最大的分离超平面时唯一的。这里的间隔最大化被称为硬间隔最大化。

间隔最大化的直观解释是：对训练数据集找到几何间隔最大的超平面意味着以充分大的确信度对训练数据进行分类。也就是说，不仅将正负实例点分开，而且对最难分的实例点（离超平面最近的点）也有足够大的确信度将他们分开。这样的超平面应该对未知的新实例有很好的分类预测能力。

1.最大间隔分离超平面

下面考虑如何求一个几何间隔最大的分离超平面，即最大间隔分离超平面。具体地，这个问题可以表示为下面的约束最优化问题：
$\begin{align} \mathop{\max}_{\omega,b} \space \gamma \\ s.t. \space y_i(\frac{\omega}{\|\omega\|}*x_i+\frac{b}{\|\omega\|}) \ge \gamma (i=1,2,\dots,N)\\ \end{align}$
即我们希望最大化超平面 $(\omega,b)$ 关于训练数据集的集合间隔 $\gamma$ ，约束条件表示的是超平面 $(\omega,b)$ 关于每个训练样本点的集合间隔至少是 $\gamma$

考虑几何间隔和函数间隔的关系式，可将这个问题改成为
$\begin{align} \mathop{\max}_{\omega,b} \space \hat{\gamma} \\ s.t. \space y_i(\omega*x_i+b) \ge \hat{\gamma}) (i = 1,2,\dots,N)\\ \end{align}$
函数间隔 $\hat\gamma$ 并不影响最优化问题的解。事实上，假设将 $\omega和b$ 成比例改变为 $\lambda\omega和\lambda b$ ,这时函数间隔变成 $\lambda\hat\gamma$ 。函数间隔的改变对最优化问题的不等式约束没有影响，对目标函数的优化也没有影响，也就事实说，它产生一个等价的最优化问题。这样，就可以取 $\hat\gamma=1$ 。将 $\hat\gamm=1$ 代入上面的最优化问题。注意最大化 $\frac{1}{\|\omega\|}$ 和最小化 $\frac{1}{2}\|\omega\|$ 是一样的。

于是就得到下面的线性可分支持向量机学习的最优化问题
$\begin{align} \mathop{\min}_{\omega,b} \space \frac{1}{2}\|\omega\|^2 \\ s.t. \space y_i(\omega*x_i+b)-1 \ge 0 (i = 1,2,\dots,N)\\ \end{align}$
这是一个凸二次规划问题(contex quadratic programming)问题。
凸优问题是指约束最优化问题
$\begin{align} \mathop{\min}_{\omega} \space f(\omega) \\ s.t. \space g_i(\omega) \ge 0 (i = 1,2,\dots,N) \\ h_i(\omega) = 0(i=1,2,\dots,l) \end{align}$
其中，目标函数 $f(\omega)$ 和约束函数 $g_i(\omega)$ 都是 $R^n$ 上的可连续可微的凸函数，约束函数 $h_i(\omega)$ 是 $R^n$ 的仿射函数。当木匾函数是 $f(\omega)$ 是二次函数且约束函数 $g_i(\omega)$ 是仿射函数时，上述的凸优化问题成为凸二次规划问题。
如果求出约束最优化问题的解 $\omega^*,b^*$ ，那么就可以得出最大间隔分离超平面 $\omega^**x+b^*=0$ 及决策函数 $f(x)=sign(\omega^*x+b^*)$ ，即线性可分支持向量机模型。

五、学习的对偶算法

为了求解线性可分支持向量机的最优化问题，将它作为原始最优化问题，应用到拉格朗日对偶性，通过求解对偶问题得到原始问题的最优解，这就是线性可支持向量机的对偶算法(dual algorithm)。这样做的优点，一是对偶问题往往根据容易求解；二是自然引入核函数，进而推广到非线性可分类问题。

首先构建拉格朗日函数(Lagrange function)。为此，对每一个不等式约束引入拉格朗日乘子(Lagrange multiplier) $\alpha_i \ge 0 ,i=1,2,\dots,N$ 定义拉格朗日函数：
$L(\omega,b,\alpha)=\frac{1}{2}\|\omega\|^2-sum_{i=1}^N\alpha_iyi(\omega*x_i+b)+\sum_{i=1}^N \alpha_i$
其中 $\alpha=(\alpha_1,\alpha_2,\dots,\alpha_N)^T$ 为拉格朗日乘子向量。

根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题 $\mathop{max}_{\alpha}\mathop{\min}_{\omega,b}L(\omega,b,\alpha)$

为了得到对偶函数问题的解，需要先求 $L(\omega,b,\alpha)$ 对 $\omega,b$ 的极小，再求 $\alpha$ 的极大
(1)求 $\mathop{\min}_{\omega,b}L(\omega,b,\alpha)$
将拉格朗日函数 $L(\omega,b,\alpha)$ 分别对 $\omega,b$ 求偏导数并令其等于0
$\begin{align} \bigtriangledown_{\omega}L(\omega,b,\alpha)=\omega-\sum_{i=1}^N\alpha_iy_ix_i=0 \\ \bigtriangledown_bL(\omega,b,\alpha) = -sum_{i=1}^N\alpha_iy_i=0 \\ \omega = \sum_{i=1}^N\alpha_iy_ix_i=0 \space(1)\\ \sum_{i=1}^N\alpha_iy_i=0 \space(2) \end{align}$

将（1）代入拉格朗日函数，并利用(2)，即可得
$\begin{equation}\label{eq1} \begin{split} L(\omega,b,\alpha)=-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i*x_j)-\sum_{i=1}^N\alpha_iy_i((\sum_{j=1}^N\alpha_jy_jx_j)*x_i+b)+ \sum_{i=1}^N\alpha_i \\ =-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i*x_j)+\sum_{i=1}^N\alpha_i \end{split} \end{equation}$
即
$\mathop{\min}_{\omega,b}=-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i*x_j)+\sum_{i=1}^N\alpha_i$
(2)求 $\mathop{\min}_{\omega,b}$ 对 $\alpha$ 的极，即对偶问题
$\mathop{max}_{\omega} \space -\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i*x_j)+\sum_{i=1}^N\alpha_i \space(3)$
$s.t. \space \sum_{i=1}^N\alpha_iy_i = 0(\alpha_i \ge 0 ,i=1,2,\dots,N)$
将公式(3)的目标函数由极大值转换成求极小，就得到下面与之等价的对偶最优化问题
$\mathop{min}_{\omega} \space \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i*x_j)+\sum_{i=1}^N\alpha_i \space(3)$
$s.t. \space \sum_{i=1}^N\alpha_iy_i = 0(\alpha_i \ge 0 ,i=1,2,\dots,N) \space(4)$

(3)解 $\omega^*,b^*$
假设 $\alpha^*=(\alpha_1^*,\alpha_2^*,\dots,\alpha_l^*)^T$ 是对偶最优化问题的解，则存在下标使得 $\alpha_j^* > 0$ ，并求按下式求得原始最优化的解 $\omega^*,b$

根据KKT条件成立，即得
$\begin{equation}\label{eq1} \begin{split} \bigtriangledown_{\omega}L(\omega^*,b^*,\alpha^*) = \omega^*-\sum_{i=1}^N\alpha_i^*y_ix_i = 0\\ \bigtriangledown_b L(\omega^*,b^*,\alpha^*)=-\sum_{i=1}^N \alpha_i^*y_i =0 \\ \alpha_i^*(y_i(\omega^**x_i+b^*)-1) \ge 0,i=1,2,\dots,N \\ y_i(\omega^**x_i+b^*)-1 \ge 0,i =1,2,\dots,N \\ \alpha_i^* \ge 0 ,i =1,2,\dots,N \end{split} \end{equation}$
因此
$\omega^*=\sum_{i=1}^N \alpha_i^*y_ix_i\space(5)$
$y_j^2=1$ ,且至少存在一个 $\alpha_j > 0$ ，假设 $\alpha^* = 0$ ,那么 $\omega= 0$ 不是原始问题的解,所以
$b^{*}=y_j-\sum_{i=1}^N \alpha_i^*y_i(x_i*x_j) \space(6)$

那么分离的超平面可以写成
$\sum_{i=1}^N\alpha_i^*y_i(x*x_i)+b^*=0\space(7)$
决策函数可以写成
$f(x)=sign(\sum_{i=1}^N\alpha_i^*y_i(x*x_i)+b^*) \space (8)$

由此可以看出，分类决策函数只依赖于输入x和训练样本输入的内积，式（8）称为线性可分支持向量机的对偶形式。

案例
训练数据正例点是 $x_1 = (3,3)^T,x_2=(4,3)^T$ ，负例点是 $x_3=(1,1)^T$ ，试用线性可分支持向量机
解：根据所给数据，对偶问题是
$\begin{equation}\label{eq1} \begin{split} \mathop{\min}_{\alpha} \space \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i*x_j)-\sum_{i=1}^N\alpha_i \\ = \frac{1}{2}(18\alpha_1^2+25\alpha_2^2+2\alpha_3^2+42\alpha_1\alpha_2-12\alpha_1\alpha_3-14\alpha_2\alpha_3)-\alpha_1-\alpha_2-\alpha_3 \\ s.t. \space \alpha_1+\alpha_2-\alpha_3 = 0 \\ \alpha_i \ge 0,i =1,2,3 \end{split} \end{equation}$

两个向量 $\overrightarrow{a}=[a_1,a_2,\dots,a_n]$ 和 $\overrightarrow{b}=[b_1,b_2,\dots,b_n]$ 的点积定义为：
$\overrightarrow{a} \ast \overrightarrow{b} = \sum_{i=1}^Na_ib_i=a_1b_1+a_2b_2+\dots+a_nb_n$

解这一优化问题，将 $a_3=a_1+a_2$ 代入目标函数并记为
$s(a_1,a_2)=4a_1^2+\frac{13}{2}a_2^2+10a_1a_2-2a_1-2a_2$

对 $a_1,a_2$ 求偏导令其为0，易知 $s(a_1,a_2)在点(\frac{3}{2},-1)^T$ 处取极值，该点不满足约束条件 $a_2\ge 0$ ，所以最小值应在边界上达到。

当 $a_1 = 0时，最小值s(0,\frac{2}{13})=-\frac{2}{13}$ ，当 $a_2=0时，最小值s(\frac{1}{4},0)=-\frac{1}{4}$ ，于是 $s(a_1,a_2)在a_1=\frac{1}{4}，a_2=0处最小，此时a_3=a_1+a_2=\frac{1}{4}$

这样, $a_1^*=a_2^*=\frac{1}{4}$ 对应的实例点 $x_1,x_3$ 是支持向量，计算可得 $w_1^*=w_2^*=\frac{1}{2}$ , $b^*=-2$

分离超平面为 $\frac{1}{2}x^{(1)}+\frac{1}{2}x^{(2)}-2=0$
分离决策函数为 $f(x)=sign(\frac{1}{2}x^{(1)}+\frac{1}{2}x^{(2)}-2)$

六、软间隔最大化

线性可分问题的支持向量机学习方法，对线性不可分训练数据是不适用的，因为这时上述方法中的不等式约束不能都成立。线性不可分意味着不能满足函数间隔大于等于1的约束条件。为了解决这个问题，对每个样本点 $(x_i,y_i)$ 都引入一个松弛变量 $\xi_i \ge 0$ ，使得函数间隔加上变量大于等于1，这样约束条件变为
$y_i(w*x_i+b) >= 1 -\xi_i$
同时对于每个松弛变量 $\xi_i$ ，支付一个代价 $\xi_i$ ,目标函数由原来的 $\frac{1}{2}\|w\|^2$ 变成
$\frac{1}{2}\|w\|^2+C\sum_{i=1}^N\xi_i \space(6.1)$
C>0为惩罚参数，一般由应用问题解决，C值大时对误分类的惩罚增大，C值小时对误分类的惩罚减小。最小化木匾函数有2层意思：使得 $\frac{1}{2}\|2\|^2$ 尽量小，即间隔尽量大，同时使误分类点的个数尽量小，C是调和两者的系数

七、非线性支持向量机与核函数

1.背景知识

(1)核技巧

非线性分类问题是指通过非线性模型才能很好地进行分类的问题。非线性问题往往不好求解，希望通过线性分类问题的方法解决这个问题，所采取的方法是进行一个非线性变换，将非线性问题变成线性问题，通过解变换后的线性问题的方法求解原来的非线性问题。

用线性分类方法求解非线性分类问题分两步：首先使用一个变换将原来空间的数据映射到新空间；然后在新空间里用线性分类学习方法从训练数据中学习分类模型。核技巧就属于这样的方法。

(2)核函数定义

设X是输入空间（欧氏空间 $R^n$ 的子集或离散集合），又设H为特征向量（希伯而空间H），如果存在一个从X到H的映射
$\phi(x):X \to H$
使得对所有 $x,z \in X$ ，函数 $K(x,z)$ 满足条件
$K(x,z)=\phi(x)*\phi(z)$
则称K(x,z)为核函数， $phi(x)$ 为映射函数， $\phi(x)*\phi(z)为\phi(x)和\phi(z)的内积$ 。通常计算K(x,z)比较容易，而通话 $\phi(x)和\phi(z)$ 计算K(x,z)并不容易。

$\phi$ 是输入空间到特征空间的迎神，特征空间一般是高维的，甚至是无穷维，可以看到，对于给定的核K(x,z)，特征空间H和映射函数 $\phi$ 的取法并不唯一，可以取不同的特征空间，即便是在同一特征空间也可以取不同的映射。

(3)核技巧在支持向量机中的应用

在对偶目标函数中的内积 $x_i*x_j$ 可以用核函数 $K(x,z)=\phi(x)*\phi(z)$ 来代替，此时对偶问题的目标函数成为
$W(\alpha)=\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum_{i=1}^N\alpha_i$
这等价于经过映射函数 $\phi$ 将原来的输入空间变换到一个新的特征空间，将输入空间中的内积 $x_i*x_j$ 变换成特征空间中的内积 $\phi(x_i)*\phi*(x_j)$ ，在新的特征空间里从训练样本中学习线性支持向量机。学习是隐式地在特征空间进行的，不需要显式地定义特征空间和营业日函数。在实际应用中，往往依赖领域知识直接选择核函数。

2.常用核函数

(1)多项式核函数(polynomial kernal function)

$K(x,z)=(x*z+1)^p$
对应的支持向量机是一个p次多项式分类器，在此情形下，分类决策函数成为
$f(x)=sign(\sum_{i=1}^{N_s}a_i^*y_i(x_i*x+1)^p+b^*)$

(2)高斯核函数(Guassian kernel function)

$K(x,z)=exp(-\frac{\|x-z\|^2}{2\sigma^2})$
对应的支持向量机是高斯径向基函数(radial basis function)分类器。在此情形下，分类决策函数成为
$f(x)=sign(\sum_{i=1}^{N_s}a_i^*y_i(exp(-\frac{\|x-z\|^2}{2\sigma^2})+b^*)$

(3)字符串核函数

核函数不仅可以定义在欧式空间，还可以定义在离散数据的集合上。比如，字符串核函数是定义在字符串集合上的核函数。字符串核函数在文本分类、信息检索、生物信息学等方面都有应用。

两个字符串s和t上的字符串核函数是基于映射 $\phi_n$ 的特征空间中的内积：
$k_n(s,t)=\sum_{\mu \in \Sigma^n}[\phi_n(s)]_{\mu}[\phi_n(t)]_{\mu}$
$=\sum_{\mu \in \Sigma^n}\sum_{(i,j):s(i)=t(j)=\mu}\lambda^{l(i)}\lambda^{l(j)}$
字符串核函数 $k_n(s,t)$ 给出了字符串s和t中长度等于n的所有子串组成的特征向量的余弦相似度。直观上看，两个字符串相同的字串越多，它们就越相似，字符串核函数的值就越大。字符串核函数可以由动态规划快速地计算。

八、序列最小最优化算法

支持向量机的学习问题可以形式化为求解凸二次规划问题，这样的凸二次规划问题具有全局最优解，并且有许多最优化算法可以用于这一问题的求解。但是当训练样本容量很大时，这些算法往往变得非常低效，以至无法使用。

序列最小最优化(sequential minimal optimization,SMO)算法，是一种启发式算法，其基本思路是：如果所有变量的解都满足此最优化问题的KKT条件，那么这个最优化问题的解就得到了。因为KKT条件是该最优化问题的充分必要条件。否则，选择两个变量，固定其他变量，针对这两个变量构建一个二次规划问题。这个二次规划问题的目标是使函数值变得更小。重要的是，这时子问题可以通过解析方法求解，这样就可以大大提高整个算法的计算速度。子问题有两个变量，一个是违反KKT条件最严重的那一个，另一个由约束条件自动确定。如此，SMO算法将原问题不断分解为子问题并对子问题求解，进而达到求解原问题的目的。

1.两个变量二次规划的求解办法

假设两个变量是 $\alpha_1,\alpha_2$ ，其他变量 $\alpha_i(i=3,4,\dots,N)$ 是固定的，于是SNO的最优化问题的子问题可以写成。

$\begin{align} \mathop{min}_{\alpha_1,\alpha_2} \space W(\alpha_1,\alpha_2)=\frac{1}{2}K_{11}\alpha_1^2+\frac{1}{2}K_{22}\alpha_2^2+y_1y_2K_{12}\alpha_1\alpha_2 \\ -(\alpha_1+\alpha_2)+y_1\alpha_1\sum{i=3}^Ny_i\alpha_iK_{i1}+y_2\alpha_iK_{i2} \space(7.1) \\ s.t. \alpha_1y_1+\alpha_2y_2 = - \sum_{i=3}^N y_i \alpha_i = \zeta \space(7.2)\\ 0 \leq \alpha_i \leq C \space(7.3) (i =1,2) \end{align}$
其中， $K_{ij}=K(x_i,x_j),i,j=1,2,\dots,N,\zeta$ 是常数，目标函数中省略不含 $\alpha_1,\alpha_2$ 的常数项。

为了求解两个变量的二次规划问题，约束可以用二维空间中的图形表示

二变量优化问题.png

不等式约束(7.3)使得 $(\alpha_1,\alpha_2)$ 在盒子[0,C][0,C]内，等式约束(7.2)使 $(\alpha_1,\alpha_2)$ 在平行于盒子[0,C][0,C]的对角线的直线上。因此要求的是目标函数在一条平行于对角线的线段上最优值。这使得两个变量的最优化问题成为实质上的单变量最优化文图，不访考虑为变量 $\alpha_2$ 的最优化问题。

假设初始化可行解为 $\alpha_1^{old},\alpha_2^{old}$ ，最优化解为 $\alpha_1^{new},\alpha_2^{new}$ ，并且假设沿着约束方向未经剪辑时 $\alpha_2$ 的最优解为 $\alpha_2^{new,func}$

由于 $\alpha_2^{new}$ 需满足不等式约束(7.3)，所以最优值 $\alpha_2^{new}$ 的取值范围必须满足条件
$L \leq \alpha_2^{new} \leq H$
其中，L与H是 $\alpha_2^{new}$ 所在对角线段端点的界，如果 $y_1 \ne y_2$
$L = max(0,\alpha_2^{old}-\alpha_1^{old}),H=min(C,C+\alpha_2^{old}-\alpha_1^{old})$
如果 $y_1 = y_2$ ，则
$L=max(0,\alpha_2^{old}+\alpha_1^{old}-C),H=min(C,a_2^{old},a_1^{old})$

下面首先要求沿着约束方向未经剪辑即未考虑不等式约束(7.3)时 $a_2$ 的最优解 $a_2^{new,func}$ ，然后在解决剪辑后 $a_2$ 的解 $a_2^{new}$ ，我们用定理来描述这个结果
$g(x)=\sum_{i=1}^Na_iy_uK(x_i,x)+b \space (7.4)$
令
$E_i=g(x_i)-y_i=(\sum_{j=1}^Na_jy_jK(x_j,x_i)+b)-y_i(i=1,2) \space(7.5)$

当i=1,2时， $E_i$ 为函数g(x)对输入 $x_i$ 的预测值与真实输出 $y_i$ 之差

定理最优化问题(7.1)~(7.3)沿着约束方向未经剪辑时的解是
$a_2^{new,unc}=a_2^{old}+\frac{y_2(E_1-E_2)}{\eta$
其中 $\eta=K_{11}+K_{22}-2K_{12}=\|Phi(x_1)-\Phi(x_2)\|^2$
$\Phi(x)$ 是输入空间到特征空间的映射

经剪辑后的 $a_2$ 的解是
$a_2^{new} = \begin{cases} H & \quad a^{new,func} > H \\ a^{new,func}& \quad L \leq a_2^{new,func} \leq H \\ L & \quad a_2^{new,func} < L \end{cases}$
由 $a_2^{new}求得a_1^{new}$ 是
$a_1^{new} = a_1^{old}+y_1y_2(a_2^{old}-a_2^{new})$

最后编辑于：2019.08.04 10:28:47

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 212,542评论 6赞 493
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 90,596评论 3赞 385
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 158,021评论 0赞 348
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 56,682评论 1赞 284
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 65,792评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,985评论 1赞 291
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,107评论 3赞 410
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,845评论 0赞 268
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,299评论 1赞 303
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,612评论 2赞 327
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,747评论 1赞 341
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,441评论 4赞 333
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,072评论 3赞 317
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,828评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,069评论 1赞 267
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 46,545评论 2赞 362
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 43,658评论 2赞 350