记录SVM 复习过程中的几个问题:
点到直线(平面）的距离公式
假设平面上一点\(P(x_0,y_0)\),一条直线\(l:ax+by+c=0\)，那么点P到直线l的距离是多少？
介绍几个概念: 方向向量: 直线上的向量以及与之平行的向量叫做直线的方向向量 假设直线斜率为k,那么它的一个方向向量是\((1,k)\) 所以，这里直线l的方向向量是\((1,-a/b)\)
法向量: 与直线垂直的向量为该直线的法向量。 根据定义，假设直线斜率为k，那么它的法向量是\((-k,1)\) 所以，这里直线l的法向量是\((a/b,1)\)
内积: 向量内积为两个向量对应元素乘积的和。 假设向量M、N,那么M与N的内积等于M到N的投影长度乘以N的模
\[M*N=|M|*|N|*cos(\theta)\]现在求解点P到直线l的距离。
假设直线上一点\(Q(x_1,y_1)\),那么QP向量为\((x_0-x_1,y_0-y_1)\)
根据上面的介绍，n为法向量(a/b,1), 也就是(a, b)。
P到直线的距离就是向量\(\vec{QP}\)在法向量n上面的投影,也就是\(\Vert\vec{QP}\Vert\cdot cos(\theta)\)
根据内积的定义 \(\vec{QP} \cdot n = \Vert\vec{QP}\Vert \cdot \Vert n\Vert \cdot cos(\theta)\)
所以 ，距离d表示如下:
\[d = \frac{\vec{QP} \cdot n}{\Vert n\Vert} = \frac {\lvert a(x_0-x_1) + b(y_0-y_1)\rvert}{\sqrt{a^2+b^2}} = \frac {a x_0 + b y_0 - (a x_1 + b y_1)}{\sqrt{a^2+b^2}} = \frac {a x_0 + b y_0 + c}{\sqrt{a^2+b^2}}\]所以，如果平面上直线为wx+b=0，那么点x到该直线的距离为:
\[d=\frac{|wx+b|}{\left\|w\right\|_2}\]点到平面的距离公式也可以根据这个思路来推导，具体如下：
如何得到SVM的优化目标
在SVM中有两个概念，一个是函数间隔\(\widehat {\gamma}\)，一个是几何间隔\(\gamma\)，且定义如下:
假设数据集T，超平面(w,b),样本点\((x_i,y_i)\),则
\[\widehat\gamma_i =y_i(w*x_i)+b\] \[\gamma_i = y_i(\frac{w*x_i+b}{\left\|w\right\|_2})\]显然:
\[\gamma_i=\frac{\widehat\gamma_i}{\left\|w\right\|_2}\]两个间隔都包含了样本的label，这样不仅可以表示分类的置信度，也可以表示分类是否正确。函数间隔有个不好的地方，那就是当我们任意缩放w和b的时候，函数间隔也会跟着变化，但是此时，超平面却没有变化。相比之下，几何间隔却没有这个问题。所以，几何间隔是一个更合适的距离评价指标。所以，SVM的优化目标如下：
\[max\ \gamma\]且有如下约束条件:
\[y_i(\frac{w^Tx_i+b}{\left\|w\right\|_2}) = \gamma_i \geq \gamma, \quad i=1,\ldots,n\]表示所有样本点的几何距离都大于最小的那个几何距离。
由于几何间隔和函数间隔的关系，我们的优化目标也可以写成下面的形式:
\[\begin{equation} max \frac{\widehat \gamma}{\left\|w\right\|_2} s.t.\ y_i(w^Tx_i+b) = \widehat \gamma_i \geq \widehat \gamma, \quad i=1,\ldots,n \end{equation}\]而根据上面的讨论，即使分离超平面不变，函数间隔也会变化。即函数间隔的取值并不影响该优化问题的求解。由于我们的目标是得到分离超平面，和函数间隔无关，所以，我们可以将其固定下来。而根据上面的表达式，我们可以选择固定 \(\widehat \gamma\),或者固定\(\left\|w\right\|_2\),反正我们都可以在得到最优的几何间隔\(\gamma\)后去求解另外一方。而为了推导和优化的方便，我们选择固定\(\widehat \gamma\),令其为1。则优化问题变成:
\[\max \frac{1}{\|w\|}, \quad s.t. y_i(w^Tx_i+b)\geq 1, i=1,\ldots,n\]一般为了优化的方便，SVM的优化问题通常使用下面的形式：
\[\min \frac{1}{2}\|w\|^2, \quad s.t. y_i(w^Tx_i+b)\geq 1, i=1,\ldots,n\]假设最优解为\(w^{\ast}, b^{\ast}\),此时的分离超平面为
\[w^\ast\cdot x+b^\ast= 0\]为什么可以将函数间隔设置为1
1.将参数\(w, b\)同比例缩放，函数间隔有变化，但是分离超平面并不会改变
因为分离超平面是\(y(wx+b) = 0\),所以\(w,b\)同比例缩放之后，结果还是等于0。
2.基于1，将函数间隔设置为1之后分离超平面没有改变，但是w的值是有变化的，但是设置为1前后的w是存在等比例缩放关系的。
函数间隔设置为1是为了求解方便，其实也可以设置为其他值，设置为其他值和设置为1时求解出来的\(w、b\)是不同的，但是存在同比例缩放的关系的。
参考: https://www.zhihu.com/question/64568136
什么是支持向量
训练集中，距离分离超平面最近的样本被称为支持向量,此时，这些样本使得约束条件中的等号成立，也就是函数间隔为1，几何间隔为\(\frac{1}{\Vert w \Vert}\)。
\[y_i(w^Tx_i+b) = 1\]支持向量的作用是什么呢？对于分离超平面来说，只有支持向量会影响分离超平面，其余的样本点对分离超平面并不起作用。即移动支持向量则分离超平面也会发生变化，移动其余的样本分离超平面并不会发生变化。这应该就是距离分离超平面最近的样本点为什么被称为支持向量的原因。
线性可分支持向量机中非支持向量的\(\alpha\)是否为0？为什么
要解答这个问题，就要先弄清\(\alpha\)是啥。
SVM的求解是通过对偶问题来求解的。\(\alpha\)就是对偶问题的参数。下面介绍对偶问题是怎么得到的，然后介绍不同样本点的\(\alpha\)有什么特点。
首先，引入拉格朗日函数。
首先，为原始最优化问题中的每个不等式约束引入一个拉格朗日乘子\(\alpha_i \geq 0 i=1,2,...,N\)
\[L(w,b,\alpha)=\frac{1}{2}{\left\|w\right\|^2} +\sum_{i=1}^N\alpha_i(1-y_i(w x_i +b))\]此时，原始问题可以表示成
\[\mathop{min}\limits_{w,b} \mathop{max}\limits_{\alpha} L(w,b,\alpha)\]对应的对偶问题为:
\[\mathop{max}\limits_{\alpha} \mathop{min}\limits_{w,b} L(w,b,\alpha)\]下面，分两步求解该问题。
首先，求 \(\mathop{min}\limits_{w,b} L(w,b,\alpha)\)
分别对\(w,b\)求偏导并令其为0
\[\frac{\partial L}{\partial w}=w-\sum_{i=1}^N\alpha_i y_i x_i =0\] \[\frac{\partial L}{\partial b}=-\sum_{i=1}^N\alpha_i y_i = 0\]所以
\[w=\sum_{i=1}^N\alpha_i y_i x_i\] \[\sum_{i=1}^N\alpha_i y_i = 0\]将这两个结果重新代入到拉格朗日函数中，得到
\[L(w,b,\alpha)=\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 y_i( (\sum_{j=1}^{N} \alpha_j y_j x_j )\cdot x_i + b) +\sum_{i=1}^N \alpha_i \\ =-\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\]即
\[\mathop{min}\limits_{w,b} L(w,b,\alpha)=-\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\]然后，求\(\mathop{min}\limits_{w,b} L(w,b,\alpha)\)对\(\alpha\)的极大，即对偶问题:
\[\mathop{max}\limits_{\alpha} -\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\]一般，都会使用最小化，所以，得到如下等价的对偶问题:
\[\mathop{min}\limits_{\alpha} \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\]假设\(w^\ast,b^\ast, \alpha^\ast\)分别是原始问题和对偶问题的解，那么, 当\(w^\ast,b^\ast, \alpha^\ast\)满足KKT条件时，原始问题和对偶问题的最优值是相等的，此时，可以通过求解对偶问题来求解原始问题。
这里需要论证一下。 先介绍一下Slater条件。
考虑最优化问题
\[\begin{aligned} &minimize\ f_0(x) \\ &subject\ to\\ & f_i(x) <= 0, i = 1, ..., m \\ & Ax = b \end{aligned}\]其中, \(f_0(x), f_1(x) ... f_m(x)\)是凸函数，等式约束是仿射函数，且不等式约束是严格可行的，即存在一个可行解x，使得所有不等式约束都严格小于0，那么强对偶成立，即 存在\(x^\ast, \alpha^\ast,\beta^\ast\)，使得\(x^\ast\)是原始问题的解，\(\alpha^\ast,\beta^\ast\)是对偶问题的解，且原始问题的最优值和对偶问题的最优值相等。
当满足Slater条件时，则强对偶性成立，即slater条件是强对偶的充分条件(但不是必要条件)，此时，可以通过求解对偶问题来获得原始问题的最优解。
而SVM问题中原始问题显然是满足Slater条件的，所以我们可以通过求解对偶问题来求解原始问题。
kkt条件是不等式约束问题存在极值解的必要条件，当问题满足强对偶时，也一定满足kkt条件，此时kkt条件是不等式约束问题存在极值的充分必要条件。 所以我们可以先求解对偶问题的最优解，然后通过kkt条件来求得原问题的最优解。
KKT条件如下：
\[\frac{\partial L(w^\ast, b^\ast,\alpha^\ast)} {\partial w} = w^\ast - \sum_{i=1}^N \alpha_i^\ast y_i x_i = 0\] \[\frac{\partial L(w^\ast, b^\ast,\alpha^\ast)}{\partial b}=-\sum_{i=1}^N\alpha_i^\ast y_i = 0\] \[\alpha_i(1-y_i(w x_i +b)) = 0 , i = 1, 2, ...,N\] \[1-y_i(w x_i +b) \le 0 , i = 1, 2, ...,N\] \[\alpha_i \ge 0 , i = 1, 2, ...,N\]所以，
\[\omega^\ast = \sum_i \alpha_i^\ast y_i x_i\]其中，至少存在一个\(\alpha_j^\ast>0\)，对该样本有:
\[y_j(w^\ast \cdot x_j + b^\ast) -1 = 0\]这里解释下为什么至少存在一个\(\alpha_j^{\ast}>0\)。 因为如果\(\alpha^{\ast}\)都为0，那么\(\omega^\ast\)也为0，也就是说原始问题中的几何间隔就是无穷大，显然是不可能的。
经过简单推导，可以得到:
\[b^\ast = y_j - \sum_{i=1}^N \alpha_i^\ast y_i (x_i \cdot x_j)\]这就是原始最优化问题的解。
此时，分离超平面是
\[\sum_{i=1}^N \alpha_i^\ast y_i(x\cdot x_i)+b^\ast = 0\]分类的决策函数是
\[f(x)=sign(\sum_{i=1}^N \alpha_i^\ast y_i(x\cdot x_i)+b^\ast )\]从上面的解中可以看出来,\(w^\ast,b^\ast\)只依赖于训练集中\(\alpha_i^\ast>0\)的样本点。这些\(\alpha_i^\ast>0\)的样本点即支持向量。
那么，现在回到问题：非支持向量的\(\alpha\)是否为0?
答案是肯定的，因为\(\alpha\)非0的都是支持向量，而\(\alpha\)为0的就是非支持向量了。非支持向量的函数间隔有什么特点呢?
根据上面的KKT条件，对于非支持向量样本，有如下不等式成立；
\[1-y_i(w^\ast x_i +b^\ast) <= 0\]也就是函数间隔是大于等于1的，也就是说存在一些样本，处在间隔边界上，但是它的\(\alpha\)为0，这时它是非支持向量，而不是支持向量。
其他处在间隔边界上的样本，因为\(\alpha\)为0，它就是支持向量。
线性支持向量机中支持向量有什么特点
这个问题和上面的问题比较类似。解答这个问题需要先知道什么是线性支持向量机。
对于线性可分数据集，我们使用的硬间隔最大化，对应线性可分支持向量机，但是对于线性不分开的数据集，我们就需要使用软间隔最大化，对应的算法就是线性支持向量机。线性支持向量机的做法是对每个样本引入一个松弛变量\(\xi\ge 0\),使得函数间隔加上该松弛变量之后大于1，这样，约束条件变成:
\[y_i(w\cdot x_i +b) \ge 1-\xi_i\]优化目标就变成
\[\frac{1}{2}\left\|w\right\|^2+C*\sum_{i=1}^N \xi_i\]\(C\)称为惩罚系数，用于平衡函数间隔和误分类比例。C越大，对误分类的惩罚越大，C越小，对误分类的惩罚越小。该目标函数表示同时使得函数间隔尽量大，同时使得误分类数量越小。
此时，优化问题变成:
\[\mathop{min}\limits_{w,b,\xi} \frac{1}{2}\left\|w\right\|^2+C*\sum_{i=1}^N \xi_i \\ s.t. y_i(w\cdot x_i +b) \ge 1-\xi_i , i =1,2,...,N \\ \xi_i \ge 0 , i =1,2,...,N\]定义拉格朗日函数:
\[L(w,b,\xi,\alpha,\mu)=\frac{1}{2}\left\|w\right\|^2+C*\sum_{i=1}^N \xi_i + \sum_{i=1}^N\alpha_i(1-\xi_i - y_i(w*x_i+b)) -\sum_{i=1}^N \mu_i *\xi_i\]和线性可分支持向量机一样， 此时，原始问题是
\[\mathop{min}\limits_{w,b,\xi} \mathop{max}\limits_{\alpha,\mu} L(w,b,\xi,\alpha,\mu)\]对应的对偶问题为:
\[\mathop{max}\limits_{\alpha,\mu} \mathop{min}\limits_{w,b,\xi} L(w,b,\xi,\alpha,\mu)\]同样，分为两步来求解对偶问题
1.求解\(\mathop{min}\limits_{w,b,\xi} L(w,b,\xi,\alpha,\mu)\)
拉格朗日函数分别对\(w,b,\xi_i\)求偏导并令其为0
\[\frac{\partial L}{\partial w}=w-\sum_{i=1}^N\alpha_i y_i x_i =0\] \[\frac{\partial L}{\partial b}=-\sum_{i=1}^N\alpha_i y_i = 0\] \[\frac{\partial L}{\partial \xi_i}=C-\alpha_i - \mu_i = 0\]得到:
\[w=\sum_{i=1}^N\alpha_i y_i x_i \\ \sum_{i=1}^N\alpha_i y_i = 0 \\ C=\alpha_i + \mu_i\]将三个式子代入拉格朗日函数，得到
\[L(w,b,\xi,\alpha,\mu)=\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i\alpha_j y_i y_j (x_i\cdot x_j )+C\sum_{i=1}^N \xi_i -\sum_{i=1}^N \alpha_i y_i( (\sum_{j=1}^{N} \alpha_j y_j x_j )\cdot x_i + b) +\sum_{i=1}^N \alpha_i -\sum_{i=1}^N \alpha_i \xi_i - \sum_{i=1}^N \mu_i \xi_i \\ =-\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 + \sum_{i=1}^N \xi_i (C-\alpha_i-\mu_i)-\sum_{i=1}^N \alpha_i y_i b \\ =-\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\]所以,有
\[\mathop{min}\limits_{w,b,\xi} L(w,b,\xi,\alpha,\mu)=-\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\]和线性可分支持向量机在这一步的形式是一样的。
然后，再对\(\mathop{min}\limits_{w,b,\xi} L(w,b,\xi,\alpha,\mu)\)对\(\alpha\)求极大,即得对偶问题:
\[\begin{aligned} &\mathop{max}\limits_{\alpha} -\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 \\ &C-\alpha_i - \mu_i = 0 \\ & \alpha_i \ge 0 \\ &\mu_i \ge 0, i =1,2,...,N \end{aligned}\]对上述表示形式进行一系列变换，消去\(\mu_i\),得到如下形式:
\[\begin{aligned} &\mathop{min}\limits_{\alpha} \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 \\ &0 \le \alpha_i \le C , i=1,2,...,N \end{aligned}\]下面使用KKT条件通过求解对偶问题求解原始问题
\[\frac{\partial L(w^\ast, b^\ast,\xi^\ast,\alpha^\ast,\mu^\ast)} {\partial w} = w^\ast - \sum_{i=1}^N \alpha_i^\ast y_i x_i = 0\] \[\frac{\partial L(w^\ast, b^\ast,\xi^\ast,\alpha^\ast,\mu^\ast)}{\partial b}=-\sum_{i=1}^N\alpha_i^\ast y_i = 0\] \[\frac{\partial L(w^\ast, b^\ast,\xi^\ast,\alpha^\ast,\mu^\ast)}{\partial \xi_i}=C-\alpha_i^\ast-\mu_i^\ast=0\] \[\alpha_i^\ast(1-\xi_i^\ast-y_i(w^\ast x_i +b^\ast)) = 0 , i = 1, 2, ...,N\] \[\mu_i \xi_i = 0, i=1,2,...,N\] \[1-\xi_i^\ast-y_i(w^\ast x_i +b^\ast) \le 0 , i = 1, 2, ...,N\] \[\alpha_i^\ast \ge 0 , i = 1, 2, ...,N\] \[\xi_i^\ast \ge 0 , i =1,2,...,N\] \[\mu_i \ge 0 ,i =1,2,...,N\]\(w^\ast\)直接可以得到，\(b^\ast\)需要简单推导下。
假设存在某个样本的\(\alpha^\ast\) 满足\(0 \lt \alpha^\ast \lt C\),那么有 \(\mu^\ast=C-\alpha^\ast \ne 0\),所以该样本的\(\xi^\ast=0\),所以有\(y_j(w^\ast\cdot x_j + b^\ast)-1 = 0\)
\[b^\ast = y_j - \sum_{i=1}^N y_i \alpha_i^\ast (x_i \cdot x_j)\]至此，我们可以得到线性支持向量机的分离超平面和分离决策函数了。
下面，回到问题，此时的支持向量有什么特点呢
和线性可分支持向量机一样，支持向量的样本的\(\alpha>0\),但是考虑到\(\alpha\)是有边界的和松弛变量，支持向量又分为几种情况。我们从KKT条件入手:
\[\alpha_i^\ast(1-\xi_i^\ast-y_i(w^\ast x_i +b^\ast)) = 0 , i = 1, 2, ...,N\] \[\mu_i \xi_i = 0, i=1,2,...,N\] \[C-\alpha_i^\ast-\mu_i^\ast=0\]- 当\(0\ \lt \alpha\lt C\) 时，\(\mu\ne 0\),所以此时\(\xi=0\),这样这个支持向量对应的样本就在间隔边界上。
- 当\(\alpha=C\)时，\(\xi\)的值就没有约束了
由于间隔边界满足关系:\(y_i(w^\ast x_i +b^\ast)=1-\xi_i^\ast\), \(\xi^\ast\)可以分为如下几种情况:
\(\xi^\ast\ =\ 0\)时，支持向量在间隔边界上。
\(0 < \xi^\ast < 1\)时，在分离超平面和间隔边界之间，分类正确。
\(\xi^\ast = 1\)时，在分离超平面上。
\(\xi^\ast > 1\)时，在分离超平面误分类一侧。
可以看到，与线性可分支持向量机相比，支持向量不止存在于间隔边界上，间隔边界和分离超平面之间、分离超平面上，甚至分离超平面误分类一侧都有可能存在支持向量。
和线性可分支持向量机一样，非支持向量的\(\alpha = 0\)。因为这些向量的函数间隔大于1，即\(y_i(w^\ast x_i +b^\ast) > 1-\xi_i^\ast\)
SMO算法中的b是怎么求解的
对偶问题的求解是通过SMO算法来求解的。该算法类似于坐标下降法，每次选取两个\(\alpha\)，固定其余\(\alpha\),然后求解这两个\(\alpha\)的最优化问题。此时该问题是一个二次规划问题，且存在解析解。该子问题关于这两个\(\alpha\)的解会更接近原始问题的解。所以，这样一步步迭代下去。直至满足终止条件。 这里涉及到两个问题:
1.选择哪两个\(\alpha\) 2.在选定后怎么求解这两个\(\alpha\)
下面先解决第2个问题。
对偶问题：
\[\mathop{min}\limits_{\alpha} \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N \alpha_i\alpha_j y_i y_j K(x_i\cdot x_j ) -\sum_{i=1}^N \alpha_i \\ s.t. \sum_{i=1}^N\alpha_i y_i = 0 \\ 0 \le \alpha_i \le C , i=1,2,...,N\]假设我们选取的\(\alpha\)分别为\(\alpha_1,\alpha_2\),那么上述问题改写为:
\[\mathop{min}\limits_{\alpha_1,\alpha_2} W(\alpha_1,\alpha_2) = \frac{1}{2} K_{11}\alpha_1^2+\frac{1}{2} K_{22}\alpha_2^2 + \alpha_1\alpha_2 y_1y_2K_{12}+ y_1\alpha_1 \sum_{i=3}^N y_i \alpha_i K_{i1}+y_2\alpha_2 \sum_{i=3}^N y_i\alpha_i K_{i2} -(\alpha_1+\alpha_2) \\ s.t. \alpha_1 y_1 + \alpha_2 y_2 = -\sum_{i=3}^N \alpha_i y_i = \phi \\ 0 \le \alpha_i \le C , i = 1,2\]\(K_{ij}=K(x_i,x_j),i,j=1,2,...,N,\phi\) 是常数,目标函数中省略了和\(\alpha_1,\alpha_2\)无关的常数
根据两个约束条件，\(\alpha_1,\alpha_2\)其实是在一个[0,C]\(\times\) [0,C]的矩形区域内,且是在平行于该矩形的对角线的直线上。所以，其实这就是一个单变量的优化问题。
假设我们考虑优化\(\alpha_2\)。
假设初始值为\(\alpha_1^{old}, \alpha_2^{old}\),最优解为\(\alpha_1^{new}, \alpha_2^{new}\),那么 假设 \(\alpha_2^{new}\)的取值范围为[L,H],那么，
当\(y1\ne y_2\)时, \(\alpha_1^{old} - \alpha_2^{old}= \varsigma\)
\[L=max(0, \alpha_2^{old}-\alpha_1^{old}), H=min(C, C+\alpha_2^{old}-\alpha_1^{old})\]当\(y1 = y_2\)时, \(\alpha_1^{old} + \alpha_2^{old}= \varsigma\)
\[L=max(0, \alpha_1^{old}+\alpha_2^{old}-C), H=min(C,\alpha_1^{old}+\alpha_2^{old})\]如下图所示：
下面，求解不考虑约束条件下的\(\alpha_2^{new}\)
为了叙述方便，记样本预估值为
\[g(x)=\sum_{i=1}^N\alpha_i y_i K(x_i,x)+b\]样本误差为
\[E_i=g(x_i)-y_i = (\sum_{j=1}^N \alpha_j y_j K(x_j,x_i)+b)- y_i, i=1,2\] \[v_i = \sum_{j=3}^N \alpha_j y_j K(x_i,x_j)=g(x_i)-b - \sum_{j=1}^2 \alpha_j y_j K(x_i, x_j) , i=1,2\]此时，目标函数变成
\[W(\alpha_1, \alpha_2)= \frac{1}{2} K_{11}\alpha_1^2+\frac{1}{2} K_{22}\alpha_2^2 + \alpha_1\alpha_2 y_1y_2K_{12}+ y_1\alpha_1 v_1 +y_2\alpha_2 v_2 -(\alpha_1+\alpha_2)\]根据约束条件，\(\alpha_1\)可以表示如下:
\[\alpha_1 y_1 = \phi-\alpha_2 y_2\]经过变换
\[\alpha_1 = y_1 (\phi - \alpha_2 y_2 )\]代入到目标函数
\[W(\alpha_2)= \frac{1}{2} K_{11}(y_1 (\phi - \alpha_2 y_2 ))^2+\frac{1}{2} K_{22}\alpha_2^2 + (y_1 (\phi - \alpha_2 y_2 ))\alpha_2 y_1y_2K_{12}+ y_1(y_1 (\phi - \alpha_2 y_2 )) v_1 +y_2\alpha_2 v_2 -(y_1 (\phi - \alpha_2 y_2 )+\alpha_2) \\ = \frac{1}{2} K_{11}(\phi - \alpha_2 y_2)^2+\frac{1}{2} K_{22}\alpha_2^2 + (\phi - \alpha_2 y_2 ) \alpha_2 y_2 K_{12} + (\phi - \alpha_2 y_2 )v_1 + y_2\alpha_2 v_2 -y_1(\phi - \alpha_2 y_2) - \alpha_2\]对\(\alpha_2\)求导
\[\frac{\partial W}{\partial \alpha_2}=-K_{11}y_2(\phi - \alpha_2 y_2)+K_{22}\alpha_2 +\phi y_2K_{12}- 2K_{12}\alpha_2-y_2v_1 + y_2 v_2 + y_1 y_2 -1 \\ =-K_{11}y_2\phi + K_{11}\alpha_2 + K_{22}\alpha_2 + \phi y_2K_{12}- 2K_{12}\alpha_2-y_2v_1 + y_2 v_2 + y_1 y_2 -1\]令其为0， 得到
\[\alpha_2 = \frac{y_2(K_{11}\phi - \phi K_{12} + v_1-v_2 - y_1 +y_2)}{K_{11}+K_{22}-2K_{12}}\]将\(v1,v2\)及\(\alpha_1^{old}y_1+\alpha_2^{old}y_2=\phi\)代入进来
\[\alpha_2^{new,unc} = \frac{y_2(K_{11}(\alpha_1^{old}y_1+\alpha_2^{old}y_2) - K_{12}(\alpha_1^{old}y_1+\alpha_2^{old}y_2) + g(x_1)-b-\alpha_1^{old}y_1K_{11}-\alpha_2^{old} y_2 K_{12}-(g(x_2)-b - \alpha_1^{old}y_1K_{12}-\alpha_2^{old} y_2 K_{22}) - y_1 +y_2)}{K_{11}+K_{22}-2K_{12}} \\ = \frac{y_2(K_{11}y_2\alpha_2^{old}-2K_{12}y_2\alpha_2^{old}+ K_{22}y_2 \alpha_2^{old} +g(x_1)-y_1-g(x_2)+y_2)}{K_{11}+K_{22}-2K_{12}} \\ =\frac{(K_{11}-2K_{12}+K_{22})\alpha_2^{old} + y_2(E_1-E_2)}{K_{11}+K_{22}-2K_{12}}\]令\(\eta=K_{11}+K_{22}-2K_{12}\),则有
\[\alpha_2^{new,unc}= \alpha_2^{old} + \frac{y_2(E_1-E_2)}{\eta}\]结合 \(\alpha_2\)的约束，得到最终的表达式
\[\begin{equation} \alpha_2^{new}= \begin{cases} H& {\alpha_2^{new,unc}\gt H } \\ \alpha_2^{new,unc}& {L \le \alpha_2^{new,unc}\le H } \\ L& {\alpha_2^{new,unc} \lt L } \end{cases} \end{equation}\]又由于\(\alpha_1 y_1 + \alpha_2 y_2 = \phi\)
得
\[\alpha_1^{new} y_1 + \alpha_2^{new} y_2 = \alpha_1^{old} y_1 + \alpha_2^{old} y_2\]所以
\[\alpha_1^{new} + \alpha_2^{new} y_1 y_2 = \alpha_1^{old} + \alpha_2^{old} y_1 y_2\] \[\alpha_1^{new} = \alpha_1^{old} + ( \alpha_2^{old}-\alpha_2^{new})y_1 y_2\]现在我们计算阈值b 和误差\(E_i\)
根据KKT 条件:
\[\frac{\partial L(w^\ast, b^\ast,\xi^\ast,\alpha^\ast,\mu^\ast)} {\partial w} = w^\ast - \sum_{i=1}^N \alpha_i^\ast y_i x_i = 0\] \[\frac{\partial L(w^\ast, b^\ast,\xi^\ast,\alpha^\ast,\mu^\ast)}{\partial b}=-\sum_{i=1}^N\alpha_i^\ast y_i = 0\] \[\frac{\partial L(w^\ast, b^\ast,\xi^\ast,\alpha^\ast,\mu^\ast)}{\partial \xi_i}=C-\alpha_i^\ast-\mu_i^\ast=0\] \[\alpha_i^\ast(1-\xi_i^\ast-y_i(w^\ast x_i +b^\ast)) = 0 , i = 1, 2, ...,N\] \[\mu_i \xi_i = 0, i=1,2,...,N\] \[1-\xi_i^\ast-y_i(w^\ast x_i +b^\ast) \le 0 , i = 1, 2, ...,N\] \[\alpha_i^\ast \ge 0 , i = 1, 2, ...,N\] \[\xi_i^\ast \ge 0 , i =1,2,...,N\] \[\mu_i \ge 0 ,i =1,2,...,N\]可以得到
\[\omega^\ast = \sum_{i=1}^N \alpha_i^\ast y_i x_i\]对应的分离超平面:
\[\sum_{i=1}^N \alpha_i^\ast y_i(x\cdot x_i)+b^\ast = 0\]记样本的预估值为\(g(x_i)\)，表示如下:
\[g(x_i) = \sum_{j=1}^N \alpha_j^\ast y_j(x_j\cdot x_i)+b^\ast\]根据KKT条件，有如下关系成立:
\[\alpha_i = 0 \Leftrightarrow y_i g(x_i) \ge 1 \\ 0 \lt \alpha_i \lt C \Leftrightarrow y_i g(x_i) = 1 \\ \alpha_i = C \Leftrightarrow y_i g(x_i) \le 1\]所以
当\(0 \lt \alpha_1^{new} \lt C\)时
\[\sum_{i=1}^N \alpha_i y_i K_{i1}+b = y_1\]所以
\[b_1^{new} = y_1 - \alpha_1^{new} y_1 K_{11}- \alpha_2^{new} y_2 K_{21} - \sum_{i=3}^N \alpha_i y_i K_{i1}\]而
\[E_1^{old} = \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_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} - E_1^{old}\]代入得
\[b_1^{new} = (\alpha_1^{old}-\alpha_1^{new}) y_1 K_{11}+ (\alpha_2^{old}-\alpha_2^{new}) y_2 K_{21} + b^{old} - E_1^{old}\]同理可得，当 \(0 \lt \alpha_2^{new} \lt C\)时
\[b_2^{new} = (\alpha_1^{old}-\alpha_1^{new}) y_1 K_{12}+ (\alpha_2^{old}-\alpha_2^{new}) y_2 K_{22} + b^{old} - E_2^{old}\]可以证明:
1.当\(\alpha_1^{new}\)和\(\alpha_2^{new}\)均在(0,C)之间时，\(b_1^{new}=b_2^{new}\)
2.当\(\alpha_1^{new}\)和\(\alpha_2^{new}\) 取值0 或者C时，此时\(b_1^{new}\)和\(b_2^{new}\)之间的数均符合KKT条件，此时，二者的均值\(\frac{b_1^{new}+b_2^{new}}{2}\)作为\(b^{new}\)
证明过程参考: https://zhuanlan.zhihu.com/p/62367247
如何理解核技巧
SVM 为什么不直接求解原始问题，原始问题比对偶问题更难求解吗
参考:
https://en.wikipedia.org/wiki/Distance_from_a_point_to_a_line
https://www.cnblogs.com/graphics/archive/2010/07/10/1774809.html
https://zhuanlan.zhihu.com/p/62367247
https://www.cnblogs.com/pinard/p/6111471.html
https://zhuanlan.zhihu.com/p/49331510
http://matafight.github.io/2015/05/13/KKT%E6%9D%A1%E4%BB%B6%E4%B8%8E%E6%8B%89%E6%A0%BC%E6%9C%97%E6%97%A5%E5%AF%B9%E5%81%B6%E6%80%A7/