smo算法

❶ SMO算法为什么要选两个变量

SMO算法由Microsoft Research的John C. Platt在1998年提出，并成为最快的二次规划优化算法，特别针对线性SVM和数据稀疏时性能更优。关于SMO最好的资料就是他本人写的《Sequential Minimal Optimization A Fast Algorithm for Training Support Vector Machines》了。
我拜读了一下，下面先说讲义上对此方法的总结。
首先回到我们前面一直悬而未解的问题，对偶函数最后的优化问题：

要解决的是在参数上求最大值W的问题，至于和都是已知数。C由我们预先设定，也是已知数。
按照坐标上升的思路，我们首先固定除以外的所有参数，然后在上求极值。等一下，这个思路有问题，因为如果固定以外的所有参数，那么将不再是变量（可以由其他值推出），因为问题中规定了

因此，我们需要一次选取两个参数做优化，比如和，此时可以由和其他参数表示出来。这样回带到W中，W就只是关于的函数了，可解。
这样，SMO的主要步骤如下：

意思是，第一步选取一对和，选取方法使用启发式方法（后面讲）。第二步，固定除和之外的其他参数，确定W极值条件下的，由表示。
SMO之所以高效就是因为在固定其他参数后，对一个参数优化过程很高效。
下面讨论具体方法：
假设我们选取了初始值满足了问题中的约束条件。接下来，我们固定，这样W就是和的函数。并且和满足条件：

由于都是已知固定值，因此为了方面，可将等式右边标记成实数值。

当和异号时，也就是一个为1，一个为-1时，他们可以表示成一条直线，斜率为1。如下图：

横轴是，纵轴是，和既要在矩形方框内，也要在直线上，因此
，
同理，当和同号时，
，
然后我们打算将用表示：

然后反代入W中，得

展开后W可以表示成。其中a,b,c是固定值。这样，通过对W进行求导可以得到，然而要保证满足，我们使用表示求导求出来的，然而最后的，要根据下面情况得到：

这样得到后，我们可以得到的新值。
下面进入Platt的文章，来找到启发式搜索的方法和求b值的公式。
这边文章使用的符号表示有点不太一样，不过实质是一样的，先来熟悉一下文章中符号的表示。
文章中定义特征到结果的输出函数为

与我们之前的实质是一致的。
原始的优化问题为：

求导得到：

经过对偶后为：

s.t.

这里与W函数是一样的，只是符号求反后，变成求最小值了。和是一样的，都表示第i个样本的输出结果（1或-1）。
经过加入松弛变量后，模型修改为：

由公式（7）代入（1）中可知，

这个过程和之前对偶过程一样。
重新整理我们要求的问题为：

与之对应的KKT条件为：

这个KKT条件说明，在两条间隔线外面的点，对应前面的系数为0，在两条间隔线里面的对应为C，在两条间隔线上的对应的系数在0和C之间。
将我们之前得到L和H重新拿过来：

之前我们将问题进行到这里，然后说将用表示后代入W中，这里将代入中，得

其中

这里的和代表某次迭代前的原始值，因此是常数，而和是变量，待求。公式（24）中的最后一项是常数。
由于和满足以下公式

因为的值是固定值，在迭代前后不会变。
那么用s表示，上式两边乘以时，变为：

其中

代入（24）中，得

这时候只有是变量了，求导

如果的二阶导数大于0（凹函数），那么一阶导数为0时，就是极小值了。
假设其二阶导数为0（一般成立），那么上式化简为：

将w和v代入后，继续化简推导，得（推导了六七行推出来了）

我们使用来表示：

通常情况下目标函数是正定的，也就是说，能够在直线约束方向上求得最小值，并且。
那么我们在（30）两边都除以可以得到

这里我们使用表示优化后的值，是迭代前的值，。
与之前提到的一样不是最终迭代后的值，需要进行约束：

那么

在特殊情况下，可能不为正，如果核函数K不满足Mercer定理，那么目标函数可能变得非正定，可能出现负值。即使K是有效的核函数，如果训练样本中出现相同的特征x，那么仍有可能为0。SMO算法在不为正值的情况下仍有效。为保证有效性，我们可以推导出就是的二阶导数，，没有极小值，最小值在边缘处取到（类比），时更是单调函数了，最小值也在边缘处取得，而的边缘就是L和H。这样将和分别代入中即可求得的最小值，相应的还是也可以知道了。具体计算公式如下：

至此，迭代关系式出了b的推导式以外，都已经推出。
b每一步都要更新，因为前面的KKT条件指出了和的关系，而和b有关，在每一步计算出后，根据KKT条件来调整b。
b的更新有几种情况：

来自罗林开的ppt
这里的界内指，界上就是等于0或者C了。
前面两个的公式推导可以根据
和对于有的KKT条件推出。
这样全部参数的更新公式都已经介绍完毕，附加一点，如果使用的是线性核函数，我们就可以继续使用w了，这样不用扫描整个样本库来作内积了。
w值的更新方法为：

根据前面的

公式推导出。
12 SMO中拉格朗日乘子的启发式选择方法
终于到了最后一个问题了，所谓的启发式选择方法主要思想是每次选择拉格朗日乘子的时候，优先选择样本前面系数的作优化（论文中称为无界样例），因为在界上（为0或C）的样例对应的系数一般不会更改。
这条启发式搜索方法是选择第一个拉格朗日乘子用的，比如前面的。那么这样选择的话，是否最后会收敛。可幸的是Osuna定理告诉我们只要选择出来的两个中有一个违背了KKT条件，那么目标函数在一步迭代后值会减小。违背KKT条件不代表，在界上也有可能会违背。是的，因此在给定初始值=0后，先对所有样例进行循环，循环中碰到违背KKT条件的（不管界上还是界内）都进行迭代更新。等这轮过后，如果没有收敛，第二轮就只针对的样例进行迭代更新。
在第一个乘子选择后，第二个乘子也使用启发式方法选择，第二个乘子的迭代步长大致正比于，选择第二个乘子能够最大化。即当为正时选择负的绝对值最大的，反之，选择正值最大的。
最后的收敛条件是在界内（）的样例都能够遵循KKT条件，且其对应的只在极小的范围内变动。
至于如何写具体的程序，请参考John C. Platt在论文中给出的伪代码。
13 总结
这份SVM的讲义重点概括了SVM的基本概念和基本推导，中规中矩却又让人醍醐灌顶。起初让我最头疼的是拉格朗日对偶和SMO，后来逐渐明白拉格朗日对偶的重要作用是将w的计算提前并消除w，使得优化函数变为拉格朗日乘子的单一参数优化问题。而SMO里面迭代公式的推导也着实让我花费了不少时间。
对比这么复杂的推导过程，SVM的思想确实那么简单。它不再像logistic回归一样企图去拟合样本点（中间加了一层sigmoid函数变换），而是就在样本中去找分隔线，为了评判哪条分界线更好，引入了几何间隔最大化的目标。
之后所有的推导都是去解决目标函数的最优化上了。在解决最优化的过程中，发现了w可以由特征向量内积来表示，进而发现了核函数，仅需要调整核函数就可以将特征进行低维到高维的变换，在低维上进行计算，实质结果表现在高维上。由于并不是所有的样本都可分，为了保证SVM的通用性，进行了软间隔的处理，导致的结果就是将优化问题变得更加复杂，然而惊奇的是松弛变量没有出现在最后的目标函数中。最后的优化求解问题，也被拉格朗日对偶和SMO算法化解，使SVM趋向于完美。

❷ 如何用python实现smo算法

在ml中常见的优化算法基本都是： sgd 这种对每个单变量进行同步更新 als(交替最小二乘）/smo(序列最小优化）这种交替（固定一个单变量，优化另一个单变量）思路。如果你熟悉smo，那么als就也可以理解了。 其它（希望更多的人补充）

❸ svm中smo算法解决对偶问题第二个alpha的选择的原则是什么

alpha>0 才会有y(wx+b)=0这个条件存在，所以确定分割超平面y=wx+b之后，才可以找到那些使得alpha>0的点也即支撑向量啊~

❹ 支持向量机学习算法

支持向量机学习算法主要有以下五种：

（1）获取学习样本（xⁱ，yⁱ），i=1，2…，其中xⁱ∈Rⁿ，y∈任 ｛1，-1｝^l，对样本进行预处理；

（2）选择进行非线性变换的核函数及对错分（误差）进行惩罚的惩罚因子c；

（3）形成二次优化问题用优化方法（如：Chuknlng算法、内点算法、SMO算法）；

（4）获得a，a^*及b₀的值，代入方程中，获得分类或函数拟合的支持向量机；

（5）将需预测或分类的数据代入支持向量机方程中获得结果。

基坑降水环境影响评价参数选取降水方式、岩土性质、水文地质边界、基坑侧壁状态、边载分布、后续使用年限、基础型式、差异沉降8级，目标输出模式对应4个级别：优等级（Ⅰ）、良好级（Ⅱ）、中等级（Ⅲ）、差级（Ⅳ）。

用一对多多类支持向量机水质分类法：有四类等级要划分，于是在抽取训练集的时候，分别抽取I所对应的向量作为正集，其余所对应的向量作为负集；Ⅱ所对应的向量作为正集，其余所对应的向量作为负集……，这四个训练集分别进行训练得到四个分类器。然后，利用这四个训练结果文件对测试集分别进行测试，最后每个测试都有一个结果，最终的结果便是这四个值中最大的一个。

利用支持向量机进行基坑降水环境影响评价就是寻找影响基坑降水环境系统和孕灾环境系统的指标和基坑降水环境影响等级之间的关系，可建立以下四个分类函数：

基坑降水工程的环境效应与评价方法

❺ 机器学习实战 SMO算法是否写错了

我确定，里头的完整版SMO算法是写错了。在寻找第二个变量时，每次只找了一个，优化失败后就放弃了，重新挑选第一个变量。这样最后算法结束后，还有不少变量不满足KKT条件。我一度以为这个算法不能收敛到全局最优。而且每次运行结果都不一样。后来，我把代码改了一下，在寻找第二个变量时，把所有可能符合条件的变量都尝试一遍。这样，算法就能收敛了。运行结束后，所有变量都能满足KKT条件。

❻ svm算法是什么

SVM(Support Vector Machine)中文名为支持向量机，是常见的一种判别方法。

支持向量机（Support Vector Machine, SVM）是一类按监督学习（supervised learning）方式对数据进行二元分类的广义线性分类器（generalized linear classifier），其决策边界是对学习样本求解的最大边距超平面（maximum-margin hyperplane）。

数值求解特点：

SVM的求解可以使用二次凸优化问题的数值方法，例如内点法和序列最小优化算法，在拥有充足学习样本时也可使用随机梯度下降。

在二次凸优化问题中，SMO的每步迭代都严格地优化了SVM的对偶问题，且迭代会在有限步后收敛于全局极大值。SMO算法的迭代速度与所选取乘子对KKT条件的偏离程度有关，因此SMO通常采用启发式方法选取拉格朗日乘子。

在每次迭代时，SGD首先判定约束条件，若该样本不满足约束条件，则SGD按学习速率最小化结构风险；若该样本满足约束条件，为SVM的支持向量，则SGD根据正则化系数平衡经验风险和结构风险，即SGD的迭代保持了SVM的稀疏性。

❼ SVM几种核函数的对比分析以及SVM算法的优缺点

SVM核函数的作用

SVM核函数是用来解决数据线性不可分而提出的，把数据从源空间映射到目标空间（线性可分空间）。

SVM中核函数的种类

1、线性核

优点：

• 方案首选，奥卡姆剃刀定律

• 简单，可以求解较快一个QP问题

• 可解释性强：可以轻易知道哪些feature是重要的

限制：只能解决线性可分问题

2、多项式核

基本原理：依靠升维使得原本线性不可分的数据线性可分；
升维的意义：使得原本线性不可分的数据线性可分；

优点：

• 可解决非线性问题

• 可通过主观设置幂数来实现总结的预判

缺点：

• 对于大数量级的幂数，不太适用

• 比较多的参数要选择

通常只用在已经大概知道一个比较小的幂数的情况


3、高斯核

优点：

• 可以映射到无限维

• 决策边界更为多样

• 只有一个参数，相比多项式核容易选择

缺点：

• 可解释性差(无限多维的转换，无法算w)

• 计算速度比较慢(解一个对偶问题)

• 容易过拟合(参数选不好时容易overfitting)

4、Sigmoid核

采用Sigmoid函数作为核函数时，支持向量机实现的就是一种多层感知器神经网络，应用SVM方法，隐含层节点数目(它确定神经网络的结构)、隐含层节点对输入节点的权值都是在设计(训练)的过程中自动确定的。而且支持向量机的理论基础决定了它最终求得的是全局最优值而不是局部最小值，也保证了它对于未知样本的良好泛化能力而不会出现过学习现象。

在实战中更多的是：

• 特征维数高选择线性核

• 样本数量可观、特征少选择高斯核（非线性核）

• 样本数量非常多选择线性核（避免造成庞大的计算量）

SVM的优缺点

1、SVM算法对大规模训练样本难以实施

SVM的空间消耗主要是存储训练样本和核矩阵，由于SVM是借助二次规划来求解支持向量，而求解二次规划将涉及m阶矩阵的计算（m为样本的个数），当m数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间。针对以上问题的主要改进有有J.Platt的SMO算法、T.Joachims的SVM、C.J.C.Burges等的PCGC、张学工的CSVM以及O.L.Mangasarian等的SOR算法。如果数据量很大，SVM的训练时间就会比较长，如垃圾邮件的分类检测，没有使用SVM分类器，而是使用了简单的naive bayes分类器，或者是使用逻辑回归模型分类。

2、用SVM解决多分类问题存在困难

经典的支持向量机算法只给出了二类分类的算法，而在数据挖掘的实际应用中，一般要解决多类的分类问题。可以通过多个二类支持向量机的组合来解决。主要有一对多组合模式、一对一组合模式和SVM决策树；再就是通过构造多个分类器的组合来解决。主要原理是克服SVM固有的缺点，结合其他算法的优势，解决多类问题的分类精度。如：与粗集理论结合，形成一种优势互补的多类问题的组合分类器。

3、对缺失数据敏感，对参数和核函数的选择敏感

支持向量机性能的优劣主要取决于核函数的选取,所以对于一个实际问题而言,如何根据实际的数据模型选择合适的核函数从而构造SVM算法。目前比较成熟的核函数及其参数的选择都是人为的,根据经验来选取的,带有一定的随意性.在不同的问题领域,核函数应当具有不同的形式和参数,所以在选取时候应该将领域知识引入进来,但是目前还没有好的方法来解决核函数的选取问题。

❽ SVM计算复杂度是多少，有好的说明资料或者参考文献吗

在理解了SVM的原理的情况下 继续理解SMO算法 紧接着可以参考《机器学习实战》中的SMO算法源码 分析其计算复杂度

网页链接可以参考这里的SMO算法讲解

❾ SVM中的对偶问题，KKT条件以及对拉格朗日乘子求值得SMO算法

拉格朗日乘子法 拉格朗日乘子（Lagrange multiplier） 基本的拉格朗日乘子法(又称为拉格朗日乘数法)，就是求函数f(x1,x2,...)在g(x1,x2,...)=0的约束条件下的极值的方法。其主要思想是引入一个新的参数λ（即拉格朗日乘子），将约束条件函数与原

❿ SVM算法，包括算法原理、算法实现、核函数参数的选取、优化、系数调整，能通俗地说明下吗谢谢

SVM 原理，在一个超空间找一个 切分的超平面，
SVM 算法实现，主要是解决SVM公式对偶问题，常用的是SMO，
SVM 核参数，隐含的将特征映射到高维空间，有兴趣可学习 learn with kernel.
SVM 参数调整分两部分，1 参数调整，用上述SMO算法，2 模型选择。

太累，不想写太多