感知机学习算法

感知机是二类分类的线性分类模型，它假设训练数据线性可分的前提下，在特征向量空间中寻找能够将样本完全正确划分开的分离超平面。
为了找到这个分离超平面，同时也为了优化的便利，感知机重点关注误分类点到分离超平面的距离(损失函数如下)，并通过SGD对其进行优化。
$$ L(w,b) = -\sum{y_i(wx_i + b)} , x_i \in M$$

感知机的学习算法如下[2]：

输入：训练集$T = \{(x_1,y_1),(x_2,y_2),\ldots,(x_N,y_N)\}$,其中$x_i \in R^n, y_i \in \{ -1,+1\}, i=1,2,\ldots,N$;学习率 $\eta(0 \lt \eta \le 1);$
输出：$f(x) = sign(wx + b)$

选取初值$w_0, b_0$;
从训练集中选择样本$(x_i, y_i)$;
如果$y_i(wx_i + b) \le 0$: $w \leftarrow w + \eta y_i x_i;\\ b \leftarrow b + \eta y_i;$
转到步骤2,直到训练集中没有误分类点。

分析一下最核心的迭代公式：

$w_{t+1} \leftarrow w_t + \eta y_i x_i; \\ b_{t+1} \leftarrow b_t + \eta y_i$

如果对上述迭代式均左乘$y_i$并右乘$x_i$[1],则得到：

$y_i w_{t+1}^T x_i \leftarrow y_i w_t^T x_i + \eta (y_i x_i)^2; \\ y_i b_{t+1} \leftarrow y_i b_t + \eta y_i^2$

因为$(y_i x_i)^2 \ge 0$,$y_i^2 = 1$以及$0 \lt \eta \le 1$,所以会得到：

$y_i w_{t+1}^T x_i \ge y_i w_t^T x_i \\ y_i b_{t+1} \gt y_i b_t$

两个不等式相加得到
$${y_i w_{t+1} x_i + y_i b_{t+1}} \gt {y_i w_t^T x_i + y_i b_t}$$
因为这里的$(x_i,y_i)$是误分类点且上式左右两边均表示该样本对应的负损失，因此此不等式表明：误分类点$(x_i,y_i)$是朝着使损失函数减小的方向改变w,b的

另外可以从核心迭代式得到的结果[2]是最后学习到的参数可以分别表示为：
$$ w = \sum_{i=1}^N \alpha_i y_i x_i; \quad b = \sum_{i=1}^N \alpha_i y_i $$
上式中的$\alpha_i = n_i \eta$,其中$n_i$表示$(x_i,y_i)$作为误分类样本参与修改$w,b$的次数，$n_i$越大，表明$(x_i,y_i)$距离分离超平面越近，对感知机的学习影响越大。

总的来说，感知机模型简单易于解释，也有Novikoff定理[2]保证在数据集线性可分时模型一定是收敛的，但是PLA会由于初值$w_0,b_0$的选择以及误分类点选择顺序的不同而产生不同的模型[2]，而且误分类的离群点会对其产生较大的影响，加之只能够适用于线性可分的二分类问题，因此单个的感知机在实际中应用比较少。

针对PLA解的不确定性，一种解决办法是采用Aggregation[3]，即建立多个感知机模型(采用不同的初始值和样本顺序)后采用多数投票的方式综合预测，但是仍然容易受到离群点的影响;另一种解决办法是增加分离超平面的约束条件，这就是SVM的出发点。

线性可分支持向量机

SVM原始形式

支持向量机在PLA的基础上增加寻找最佳分离超平面的约束条件：间隔最大化，这里的“间隔”是指超平面$(w,b)$关于训练数据集 $T$的几何间隔，定义为：
$$ \gamma = \min_{i=1,\ldots,N} \quad y_i ({wx_i \over \begin{Vmatrix} w \end{Vmatrix}} + {b \over \begin{Vmatrix} b \end{Vmatrix}}) $$
它选择了超平面关于样本点$(x_i,y_i)$的几何间隔(即上式去掉min函数后剩下的部分)的最小值，之所以选择几何间隔来度量样本点到分离超平面的距离是因为它不会随$w,b$成比例的改变而改变[2]。支持向量机希望所找到的最佳分离超平面能够使$\gamma$最大，是因为此时的分离超平面的鲁棒性最好，如下图所示:

直观上来看上图，A中有一个样本D紧靠分离超平面，如果该样本D是具有代表性的（非离群点），那么由于随机误差的存在，与D类似的测试样本$F$会随机分布在D的周围，这时由于D距离分离超平面太近会容易使得测试样本$F$的类别判错；与之相对应的，在图C中，这种情况则会好很多。图中距离分离超平面最近的样本点到该超平面的距离就代表了该超平面将这些样本分开的确信度[2]，也代表了这样的超平面的鲁棒性和泛化能力。

总的来说，线性可分SVM希望在能够完全正确的将样本分类的前提下，寻找到最佳的分离超平面$(w,b)$，利用数学语言来描述SVM的诉求便得到下面的最优化问题：
$$ \begin{cases} \max_{w,b} \quad \gamma \\ s.t. \quad y_i ({wx_i \over \begin{Vmatrix} w \end{Vmatrix}} + {b \over \begin{Vmatrix} b \end{Vmatrix}}) \ge \gamma, \quad i=1,2,\ldots,N \\ \end{cases} \tag{0} $$

令$\gamma = {{\hat \gamma} \over \begin{Vmatrix} w \end{Vmatrix}}$ ，即：
$$ \hat \gamma = \min_{i=1,\ldots,N} y_i(wx_i+b) \quad \tag{1} $$
因此原来的最优化问题可以改写为：
$$ \begin{cases} \max_{w,b} \quad { {\hat \gamma} \over {\begin{Vmatrix} w \end{Vmatrix}} } \\ s.t. \quad y_i (wx_i + b) \gt \hat \gamma, \quad i=1,2,\ldots,N \\ \end{cases} \tag{2} $$
在优化问题(2)里面，如果将$w,b$缩放为$\lambda w,\lambda b$，则根据式子(1)$\hat \gamma$会变为$\lambda {\hat \gamma}$，因此优化问题(2)的不等式约束不变; 又因为目标函数中的$| w |$同样变为$\lambda {| w |}$，因此优化问题(2)的目标函数也不变。因此为了求解的方便，我们总可以找到这样一个$\lambda$使得$\lambda {\hat \gamma} = 1$，从而优化问题(2)可以改写为：
$$ \begin{cases} \min_{w,b} \quad {1 \over 2}{\| w \|}^2 \\ s.t. \quad y_i(wx_i + b) \ge 1 \end{cases} \tag{3} $$
注意上式用到了等式：${ \max_{w,b} \quad {1 \over {\| w \|}^2} } \Leftrightarrow { \min_{w,b} {1 \over 2}{\| w \|}^2} $
至此，我们终于得到了大家喜闻乐见的SVM优化问题的原始形式，我这里的思路是按照李航老师《统计学习方法》[2]的第七章进行的，更加直观易懂的推导过程强烈建议大家阅读参考文献[4]的第一部分。

SVM原始的优化问题清晰之后，咱们再回到之前所说的最佳分离超平面。如果我们得到了优化问题(3)的最优解$(\hat w,\hat b)$，也就确定来最佳分离超平面的方程$L_0:\quad \hat w x + \hat b = 0$，同时在$L_0$两侧距离${1 \over {| w |}}$处确定了两个平行于$L_0$的间隔边界：

$\begin{cases} L_1: \quad \hat w x + b = 1 \\ L_2: \quad \hat w x + b = -1 \\ \end{cases} \tag{4}$

所有的正类样本在$L_1$的$\hat w$方向所指那一侧，所有的负类样本都在$L_2$的$\hat w$反方向所指的那一侧，间隔边界中间没有样本点

SVM的对偶形式

从SVM的原始算法到对偶算法需要借助拉格朗日对偶性这座桥梁，然后借助KKT条件建立对偶问题的最优解与原始问题的最优解的数学联系，达到通过求解对偶问题的最优解来间接得到原始问题最优解的目的。下面分别从拉格朗日对偶性和KKT条件两方面对整个过程进行梳理，具体的理论推导在参考文献[2]的附录有详细的过程。

拉格朗日对偶性

第一步，对于优化问题(3)中的每个不等式约束${1 - y_i(wx_i + b)} \le 0$引进拉格朗日乘子${\alpha_{i} \ge 0}, i=1,2,\ldots,N$，并定义拉格朗日函数：
$$ L(w,b,\alpha) = {1 \over 2}{\| w \|}^2 - \sum_{i=1}^N{\alpha_i y_i {wx_i + b}} + \sum_{i=1}^N \alpha_i \tag{5} $$
第二步，利用拉格朗日函数$L(w,b,\alpha)$将原始的优化问题(3)改写为等价的形式:

$(3) \Leftrightarrow \min_{w,b} \max_{\alpha;\alpha_i \ge 0} L(w,b,\alpha) \tag{6}$

第三步，写出对偶问题以及建立与优化问题(6)的关系，对偶问题如下：

$\max_{\alpha;\alpha_i \ge 0} \min_{w,b} L(w,b,\alpha) \tag{7}$

它与优化问题(6)存在如下的关系：

${\max_{\alpha;\alpha_i \ge 0} \min_{w,b} L(w,b,\alpha) } \le {\min_{w,b} \max_{\alpha;\alpha_i \ge 0} L(w,b,\alpha)} \tag{8}$

上面的不等式关系可以用一句话概括：整体A不大于整体B，则A中的最大值也必不大于B中的最小值。且等号成立当且仅当$\alpha^\star$和$w^\star,b^\star$分别是对偶问题(7)和原始问题(3或5)的最优解。所以现在的关键是：满足什么样的条件我们才能够有底气说$\alpha^\star$和$w^\star,b^\star$分别是对偶问题和原始问题的最优解？

KKT条件

上面问题的答案就是KKT条件，它向我们保证：只要你找到的$\alpha,w,b$能够满足下面的所有条件，那么恭喜你，你找到了最佳的那组解。

$\left\{ \begin{array}{rcl} \nabla w L(w,b,\alpha)=0 \\ \nabla b L(w,b,\alpha)=0 \\ \nabla \alpha L(w,b,\alpha)=0 \\ \alpha_i[1-y_i(wx_i + b)]=0 \\ 1 - y_i(wx_i + b) \le 0 \\ \alpha_i \ge 0,\quad i=1,2,\ldots,N \end{array} \right. \tag{9}$

第一步，将(5)中的拉格朗日函数代入KKT条件，得：

$\left\{ \begin{array}{rcl} w - \sum_{i=1}^N \alpha_i y_i x_i = 0 \\ -\sum_{i=1}^N \alpha_i y_i = 0 \\ 1 - y_i(wx_i + b) = 0 \\ \alpha_i[1 - y_i(wx_i + b)] = 0 \\ y_i(wx_i + b) - 1 \ge 0 \\ \alpha_i \ge 0,\quad i=1,2,\ldots,N \end{array} \right. \tag{10}$

第二步，建立最优解之间的关系。通过反证法[2]可以证明必然存在某个样本点$(x_i,y_i)$的$\alpha_j \gt 0$，从而可以从(10)中的第4个等式保证第3个等式一定是成立的，同时也不违反第5个不等式，于是可以得到最优解$\alpha^\star,w^\star,b^\star$之间的关系：

$\begin{cases} w^\star = \sum_{i=1}^N \alpha^\star y_i x_i \\ b^\star = y_j - \sum_{i=1}^N \alpha^\star y_i (x_i \cdot x_j) \\ \end{cases} \tag{11}$

到了这里，我们只需要找出对偶问题的最优解$\alpha^\star$就能够找到那个最大间隔分离超平面$(w^\star,b^\star)$。
第三步，回到对偶问题(7)，可以看到需要先找出$L(w,b,\alpha)$对于$w,b$的最小值，从拉格朗日函数(5)可知$L(w,b,\alpha)$是关于$w,b$的凸函数，因此分别对$w,b$求偏导并令其等于0[2]，得到：

$w = \sum_{i=1}^N \alpha_i y_i x_i \quad \sum_{i=1}^N \alpha_i y_i = 0 \tag{12}$

第四步，将(12)中的第一个等式代回到拉格朗日函数(5)进行整理，并将(12)的第二个等式做为约束，得到最终形式的对偶问题：

$\left\{ \begin{array}{rcl} \max_{\alpha} \quad -{1 \over 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; \quad \alpha_i \ge 0, \quad i=1,2,\ldots,N\\ \end{array} \right. \tag{13}$

最后利用后一节的SMO算法找到$\alpha_j \ge 0$的样本点$(x_j,y_j)$，然后通过等式(11)就能够找出最大间隔分离超平面的位置$(w^\star,b^\star)$。其中$\alpha_j \gt 0$对应的样本$(x_j,y_j)$称为支撑向量，这些样本点满足$y_j(wx_j + b) = 1$，说明它们正好落在间隔边界上，但是在间隔边界上的样本点不一定都是支撑向量，因为它们可能有$\alpha_i = 0$。

线性支持向量机

线性可分支持向量机只适用于数据集线性可分的情况，对于非线性可分的数据集，我们仍然希望找到这样一个分离超平面既能够使分类间隔${2 \over {| w |}}$尽量大，同时使的样本点违反约束条件的程度尽可能低，为了衡量样本违反约束条件的程度，对每个样本点引进一个松弛变量$\xi_i \ge 0$,这个值越大，代表该样本违反约束条件的程度越高（实际上，当$\xi_i \gt 1$时表示样本$(x_i,y_i)$产生来误分类）。此时对应的原始凸二次规划问题为：

$\left\{ \begin{aligned} \min_{w,b,\xi} \quad {1 \over 2}{\| w \|}^2 + C \sum_{i=1}^N \xi_i \\ s.t. \quad y_i(wx_i + b) \ge {1 - \xi_i}; \quad \xi_i \ge 0,i=1,2,\ldots,N \end{aligned} \right. \tag{14}$

优化问题(14)的解$w$是唯一的，但是$b$的解存在于一个区间[2]。对应的对偶问题与(13)相比，只是$\alpha_i$的约束增加了一个上限，即$0 \le \alpha_i \le C$。同样，满足$0 \lt \alpha_j \lt C$的样本点$(x_j,y_j)$称为支撑向量，它们用来确定$b$值，因为对于满足$0 \lt \alpha_j \lt C$的不同样本点计算出来的$b$值可能不同，因此实际计算时可以取这些$b$的平均值[2]。

SMO算法

SMO算法要解的是如下凸二次规划问题：
$$ \left\{ \begin{array}{rcl} \min_{\alpha} {{1 \over 2} \sum_{i=1}^N \sum_{j=1}^N {\alpha_i \alpha_j y_i y_j K(x_i,x_j)} -\sum_{i=1}^N \alpha_i} \\ s.t. \sum_{i=1}^N {\alpha_i y_i} = 0 ;\quad 0 \le \alpha_i \le C,i=1,2,\ldots,N \\ \end{array} \right. \tag{15} $$
SMO算法主要的思路是：初始化所有的变量$\alpha_i,i=1,2,\ldots,N$，从中选择两个变量计为$\alpha_1^{old} = \alpha_1,\alpha_2^{old} = \alpha_2$，保持其他变量$\alpha_3,\ldots,\alpha_N$不变;通过(15)中的第一个等式约束可以将$\alpha_1$用$\alpha_2$表示出来，再将$\alpha_1$代回到(15)的目标函数中得到关于$\alpha_2$的二次函数，令其偏导等于零可以得到$\alpha_2$的一个更新值，计为$\alpha_2^{new,uncut}$; 注意到$\alpha_2^{new,uncut}$可能不满足(15)中的不等式约束，因此需要对其进行一次剪辑操作，剪辑的示意图如下：

剪辑后的值计为$\alpha_2^{new,cutted}$，然后根据这个剪辑后的值计算$\alpha_1^{new}$，此时不再需要对$\alpha_1^{new}$进行剪辑操作。此时，我们已经完成来一轮对$\alpha_1,\alpha_2$的优化更新，因为分离超平面$(w,b)$参与了每一轮的变量优化更新，因此需要在每一轮变量的优化更新之后对$w,b$进行更新，而$w=\sum_{i=1}^N \alpha_i y_i x_i$即$w$隐式的通过$\alpha_i$的更新完成了更新，而$b$的更新则需要从中选择一个满足$0 \lt \alpha_j \lt C$的$\alpha_j$来进行更新，而剪辑之后的$\alpha_2^{new,cutted}, \alpha_1^{new}$总是满足$0 \le \alpha_i \le C$，因此根据$\alpha_2^{new,cutted},\alpha_1^{new}$来对$b$进行更新，以便参与下一轮的变量优化更新过程。

代码实现

SMO的python代码在我的github，代码的实现主要参考了[6]中的算法步骤，下面对代码中比较关键的部分进行解释，同时记录下代码中我觉得有疑惑的地方。

关键代码行解释

样本点筛选

1	while(0 in alpha) and counter < max_iter:

这个while循环判断参与当前迭代轮次的样本的拉格朗日乘子$\alpha$是否全部非0,如果是，说明这些样本点全部是支撑向量，结束循环;否则，保留$\alpha_i \neq 0$的样本点（这一步操作在while循环体的末尾）进入下一个迭代轮次，因为这些$\alpha_i \neq 0$的样本点才是可能的支撑向量[6]

KKT条件的违反准则

1	if (y[i] * E_i < -tolerance and alpha[i] < C) or (y[i] * E_i > tolerance and alpha[i] > 0) :

这个if判断语句在第一个for循环体里面，作用是选择违反KKT条件的样本点进入内层for循环参与参数的更新，这里判断一个样本是否违反KKT条件的标准是：

$(\alpha_i \lt C \quad \&\& \quad y_i E_i \lt 0 )\quad or \quad (\alpha_i \gt 0 \quad \&\& \quad y_i E_i \gt 0) \tag{16}$

上式判断标准的详细来源与解释请参考[4]的1.5部分的内容。在上面实际的代码中，我们将当前分类器对输入$x_i$的预测值与真实输出$y_i$的差(即上式的$y_i E_i$部分)放松到精度${tolerance}$范围内进行判断[2]

剔除无效的$\alpha$

1 2	if L == H: continue

$\alpha_1, \alpha_2$的可行域是被$0 \le \alpha_1,\alpha_2 \le C$方形区域所截取的一段线段，当$L = H$时，表明这段线段退化到方形区域的左上角或者右下角的一个点，这两点处的$\alpha_1,\alpha_2$必有其中一个为0,另一个取值C，从而不满足支撑向量的要求$0 \lt \alpha_i \lt C$，因此放弃当前寻找到的$(x_j,y_j)$而寻找下一个。

正定核验证

1
2
3

phi = 2 * kernel(x_data[i,:], x_data[j,:]) - kernel(x_data[i,:],x_data[i,:]) - kernel(x_data[j,:],x_data[j,:])
if phi >= 0:
    continue

注意${phi}$计算的是:

$2K_{12}-K_{11}-K_{22}=2x_1^T x_2 -x_1^T x_1 - x_2^T x_2 = -{\| x_2 - x_1 \|}^2 \le 0 \tag{17}$

这一步检测的是核函数是否为正定核，SVM要求(5)中目标函数的$K(x_i,x_j)$必须是正定核，它能够保证不等式(17)是成立的。

$\alpha$的更新精度

1 2	if abs(alpha[j] - alpha[i]) < tolerance: continue

如果$\alpha_j$更新前后的值的差距小于精度${tolerancce}$，说明$\alpha_j$更新程度过小，同时因为后面$\alpha_i$的更新需要用到$\alpha_j^{old} - \alpha_j$，因此$\alpha_i$的更新程度也会非常小，我们选择寻找下一个样本点进行更新。

分离超平面的参数和方程

1
2
3

w = np.dot( np.multiply(alpha, y), x_data )
true_b = y[0] - np.dot(x_data[0,:], w)
yy = (np.dot(-w[0], xx) - true_b) / w[1]

在找出所有的支撑向量之后，分别按照下列表达式对分离超平面的法向量$w$和阈值$b$进行更新：

$\begin{cases} w^\star = \sum_{i=1}^N {\alpha_i^{\star} y_i x_i} \\ b^\star = y_j - \sum_{i=1}^N {y_i \alpha_i^\star (x_i \cdot x_j)} \quad j \in \{ j | 0 \lt \alpha_j^\star \lt C\} \end{cases} \tag{18}$

记住分离超平面的方程为$WX + b = 0$，在二维的特征向量空间中，向量$\vec X = (x_0,x_1)$，对应的平面法向量为$\vec W = (w_0,w_1)$，因此根据分离超平面的方程形式可以得到：

$w_0 x_0 + w_1 x_1 +b =0 \quad \Rightarrow \quad x_1 = -{w_0 \over w_1} x_0 - {b \over w_1} \tag{19}$

式子(19)也就是上面代码中第三行代码的依据。

疑惑

代码里面关于$E$的计算、每一轮$\alpha_i \neq 0$的样本点的筛选，这两部分我参考了[5]中博主的Matlab实现，这两点也是我目前没有想明白的地方。

$E$的原始计算公式是$E_i = \sum_{j=1}^N {\alpha_j y_j K(x_j,x_i) + b} - y_i, i=1,2,\ldots,N$，但是在[7]的实现中（line 100 and 114），阈值$b$并没有参与到$E$的计算中来，而$E_i,E_j$的值有两个作用：一个是更新$\alpha_2^{new,uncut}$;另一个是用于计算$b_1,b_2$。因为$\alpha_2^{new,uncut}$的计算需要的是$E_i - E_j$，因此在这里$b$不参与$E_i,E_j$的计算不会影响到$\alpha_2^{new,uncut}$的更新。但是在$b_1,b_2$的更新过程(line 169 and 170)[7]中，会因为$E_i,E_j$值的不同而变化，可是这样计算出来的最后的$b$是正确的，为什么？
在两个for循环走完一遍之后，从数据集$(X,Y)$中选择$\alpha_k \neq 0$的样本$(x_k,y_k)$进行保留，参与到下一个迭代轮次的支撑向量的选择，直到某一轮次之后的$\alpha_i \neq 0,i=1,2,\ldots,N$为止，此时对应的样本均是支撑向量。对于每次这样选择的理由，[6]中的解释如下，并没有说明具体的理由。

“Useful data are those samples whose $\alpha$ had a nonzero value during the previous algorithm iteration”

多分类扩展

one-against-all

对于M(M>2)类的多分类问题，依次将属于$M_i,i=1,2,\ldots,M$类的样本作为正类，剩余其他类别的样本全部看作负类，寻找对应的最佳分离超平面$g_i(x),i=1,2,\ldots,M$，对于$x \in M_i$中的样本，必有$g_i(x)>0$成立，而对于$x \notin M_i$中的样本，则有$g_i(x) < 0$成立。因此在得到M个分离超平面后，对于测试数据$x$根据下列的规则确定预测类别：

$assign \quad x \quad M_i \quad if \quad i=argmax_k{g_k(x)}$

One-against-all方法有两个缺陷：一是容易在特征空间产生多个$g_i(x)>0$的公共区域，位于这些区域的样本类别无法区分；二是在M较大的时候，容易转换后的每个二分类问题是失衡的，即正类样本数远小于负类样本数，从而影响分类效果。

one-against-one

这种方法是每次从M个类别的样本里面选择2个类别的样本$Mi,M_j$寻找对应的分离超平面$g{ij}(x)$，总共需要$C_M^2 = M(M-1)/2$个分离超平面。分类时，对于测试样本x，根据这$M(M-1)/2$个决策函数的结果进行投票决定类别标签。

error-correcting output codes

参考文献

林轩田机器学习基石
李航统计学习方法
林轩田机器学习技法
Sequential Minimal Optimization for SVM
A Comprehensive Post about SVM Model and SMO Algorithm
Simplified SMO Algorithm
Matlab Version Implementation of Simplied SMO Algorithm