机器学习笔记（10）——这就是SMO算法的推导，很容易理解可分离问题，所以不适用于线性不可分离的训练数据。这时候需要引入一个新的定义：软区间。如果训练数据中存在一些奇异点，即分类错误的样本点，去除这些奇异点后，剩下的大部分样本点组成的集合是线性可分的，对应的训练数据为线性可分区间也称为硬区间。线性不可分性是指某些样本点不能满足函数区间大于等于1的约束条件，即位于两条虚线之间；可以为每个样本点引入一个松弛变量$\xi_i>=0$，使函数区间加上这个松弛变量后大于等于1；并且对于每个松弛变量$\xi_i$，都会付出一个代价$\xi_i$，所以目标函数和约束会变成如下：其中C称为惩罚参数，新的目标函数就是让函数区间尽可能大，同时误分类样本点的个数尽可能少，C为协调两者的系数。对于线性不可分优化问题，就变成了凸二次优化问题（原问题）。当训练数据样本线性不可分时，模型就变成了线性支持向量机。线性支持向量机包括线性可分支持向量机。由于真实数据集往往是线性不可分的，因此线性支持向量机具有更广泛的适用性。利用拉格朗日乘数法的对偶性将这个原问题转化为对偶问题的形式如下：这里的推导过程和前面的原理类似，所以我只简单总结一下。首先根据目标函数和约束条件采用拉格朗日乘子法构造拉格朗日函数，然后依次推导三个变量，对偶问题即为拉格朗日函数的最大最小值问题，则形式为可以推导出上述对偶问题。SMO算法原理SMO算法是一种启发式算法。基本思想是：如果所有变量的解都满足优化问题的KKT条件，则得到最优解，因为KKT条件对于优化问题是充分必要的。健康）状况。否则，需要选择两个变量并固定其他变量来构造仅针对这两个变量的优化问题。这里的两个变量，其中一个是最严重违反KKT条件的，另一个是由约束条件决定的。这样就可以将原问题不断地分解成若干个子问题，从而提高整个算法的效率。为什么选择两个变量而不是一个？因为当时拉格朗日函数在求b的时候得到了一个等式约束，如下：如果我们只选择一个变量，固定其余变量，那么这个变量的值也已经固定了。最优解的上下界对于原优化问题，$\lambda_i$的上下界可以利用它的约束来计算。如果固定变量为$\lambda_1和\lambda_2$，在等式条件的约束下可以转化为如下形式，其中k为自己设定的常量：由于$\lambda_i$的取值范围总是从0到C之间，又对应$y_1=±1和y_2=±1$，有4种组合，可以归结为$y_1=y_2和y_1≠y_2$两种，所以可以得出这两个公式如下：假设上述约束的初始可行解为$\lambda_1^{old},\lambda_2^{old}$，对应的最优解为$\lambda_1^{new},\lambda_2^{new}$.因为现在两个变量的最优值位于平行于对角线的两条线段上，当一个达到最优值时，另一个也将达到最优值，所以可以转化为单个变量$\lambda_2$优化问题。由于$\lambda_2^{new}$总是满足不等式约束，所以这个解的值一定在一个范围内。这里，下界设置为L，上限设置为H。这个L和H是$\lambda_2^{new}$所在的线段端点的边界。当$y_1≠y_2$时，$\lambda_2^{new}$的上下界如下：当$y_1=y_2$时，$\lambda_2^{new}$的上下界如下：约束后进行目标函数变换最后下面需要对原问题的目标函数做一些处理，因为SMO算法的思想是先选择两个变量固定剩下的变量，所以目标函数被“开”了，相应的处理如下：合并过程后：其中K(i,j)是正定核的知识，下一篇会讲到。这里我们只需要知道K(i,j)=K(j,i)。当上述公式中的元素组合时，将使用此属性。因为在constraints中已经确定只有$\lambda_2$被优化，所以目标函数在推导$\lambda_2$的时候只想让$\lambda$的下标为2，其余变量需要使用常量或者$\lambda_2$替换。这里需要引入一个新的概念：error$E_i$。当i=1,2时，误差$E_i$为分类决策函数$g(x)$的预测值与真实值$y_i$的差值。目标函数公式中的$\lambda_1$可以用$\lambda_2$代替，如下：另外，目标函数中还有下标在3以上的累加集，相当于一个常数，也存在于$g中(x_i)$，可推导出如下等式：将目标函数的元素置换后，对$\lambda_2$求导，可得到如下公式：经过进一步转置处理：最后，误差$E_i,v_i$而关于k的等式约束可以带入上式：其中$\eta$称为学习率，但是这里$\lambda_2$还没有被上面得到的上下界约束剪枝，所以这里暂且用一个新值$\lambda^{new,unc}$代替$\lambda_2$。对上述约束进行剪枝后，最优解可以记为$\lambda_2^{new}$，如下：将得到的$\lambda_2^{new}$代入方程得到$\lambda_1^{的值ofnew}$is:variableselection如前所述，SMO算法会在每个子问题中选择两个变量，“一个变量是最严重违反KKT条件的”，这意味着KKT是最不满足条件的，下面介绍选择变量的具体操作。SMO指的是选择第一个变量作为外循环。首先遍历整个样本集，选择最严重违反KKT条件的样本点，将其对应的变量作为第一个变量。具体操作是检查样本点是否满足KKT条件，如下：前两个条件可以用上面提到的硬区间对应的KKT条件来理解，我们先回顾一下：这两个条件可以判断什么时候$\lambda_i=0$时，样本点必须位于两边虚线外；当$0<\lambda_i
