优先选择遍历非边界数据样本，因为非边界数据样本更有可能需要调整，边界数据样本常常不能得到进一步调整而留在边界上。由于大部分数据样本都很明显不可能是支持向量，因此对应的α<script type="math/tex" id="MathJax-Element-1606">α</script>乘子一旦取得零值就无需再调整。遍历非边界数据样本并选出他们当中违反KKT 条件为止。当某一次遍历发现没有非边界数据样本得到调整时，遍历所有数据样本，以检验是否整个集合都满足KKT条件。如果整个集合的检验中又有数据样本被进一步进化，则有必要再遍历非边界数据样本。这样，不停地在遍历所有数据样本和遍历非边界数据样本之间切换，直到整个样本集合都满足KKT条件为止。以上用KKT条件对数据样本所做的检验都以达到一定精度ε就可以停止为条件。如果要求十分精确的输出算法，则往往不能很快收敛。

对整个数据集的遍历扫描相当容易，而实现对非边界αi<script type="math/tex" id="MathJax-Element-1607">α_i</script>的扫描时，首先需要将所有非边界样本的αi<script type="math/tex" id="MathJax-Element-1608">α_i</script>值（也就是满足0<αi<C<script type="math/tex" id="MathJax-Element-1609">0<α_iαi<script type="math/tex" id="MathJax-Element-1610">α_i</script>值。

SMO称选择第2个变量的过程为内层循环。第2个变量选择的标准是希望能使α2<script type="math/tex" id="MathJax-Element-1611">\alpha_2</script>有足够大的变化。

记g(x)=∑Ni=1αiyiK(xi,x)+b<script type="math/tex" id="MathJax-Element-1612">g(x) = \sum_{i=1}^N \alpha_i y_iK(x_i, x) + b</script>, 令Ei=g(xi)?yi=(∑Ni=1αiyiK(xi,x)+b)?yi,i=1,2<script type="math/tex" id="MathJax-Element-1613">E_i = g(x_i) - y_i= (\sum_{i=1}^N \alpha_i y_iK(x_i, x) + b) - y_i,\qquad i = 1, 2</script>。

当i=1,2<script type="math/tex" id="MathJax-Element-1614">i = 1, 2</script>时，Ei<script type="math/tex" id="MathJax-Element-1615">E_i</script>是函数g(xi)<script type="math/tex" id="MathJax-Element-1616">g(x_i)</script>对输入xi<script type="math/tex" id="MathJax-Element-1617">x_i</script>的预测值与真实输出yi<script type="math/tex" id="MathJax-Element-1618">y_i</script>之差。

对于第2个变量α2<script type="math/tex" id="MathJax-Element-1619">\alpha_2</script>的选择，一个简单的做法是选择让|E1?E2|<script type="math/tex" id="MathJax-Element-1620">|E_1 - E_2|</script>最大的变化。为了节省计算时间，将所有Ei<script type="math/tex" id="MathJax-Element-1621">E_i</script>值保存在一个列表中。

如果上述方法选择的变量不能使目标函数有足够的下降，那么采用以下启发式规则继续选择第2个变量。遍历在间隔边界上的支持向量点，依次将其对应的向量作为α2<script type="math/tex" id="MathJax-Element-1622">\alpha_2</script>试用，直到目标函数有足够的下降。若找不到合适的，则遍历训练数据集；若仍找不到合适的α2<script type="math/tex" id="MathJax-Element-1623">\alpha_2</script>，则放弃第一个变量α1<script type="math/tex" id="MathJax-Element-1624">\alpha_1</script>，再通过外层循环寻求另外的α1<script type="math/tex" id="MathJax-Element-1625">\alpha_1</script>。

选择这两个拉格朗日乘子后，我们需要先计算这些参数的约束值。然后再求解这个约束最大化问题,下面用αi,αj<script type="math/tex" id="MathJax-Element-1626">\alpha_i, \alpha_j</script>表示选择的第1个和第2个变量。

首先，我们需要给αj<script type="math/tex" id="MathJax-Element-1627">α_j</script>找到边界L≤αj≤H<script type="math/tex" id="MathJax-Element-1628">L\le α_j \le H</script>，以保证αj<script type="math/tex" id="MathJax-Element-1629">α_j</script>满足0≤αj≤C<script type="math/tex" id="MathJax-Element-1630">0\le α_j\le C</script>的约束。这意味着αj<script type="math/tex" id="MathJax-Element-1631">α_j</script>必须落入这个盒子中。由于只有两个变量(αi,αj<script type="math/tex" id="MathJax-Element-1632">α_i, α_j</script>)，约束可以用二维空间中的图形来表示，如下图：

不等式约束使得(αi,αj<script type="math/tex" id="MathJax-Element-1633">α_i, α_j</script>)在盒子[0, C]x[0, C]内，等式约束使得(αi,αj<script type="math/tex" id="MathJax-Element-1634">α_i, α_j</script>)在平行于盒子[0, C]x[0, C]的对角线的直线上。因此要求的是目标函数在一条平行于对角线的线段上的最优值。这使得两个变量的最优化问题成为实质的单变量的最优化问题。由图可以得到，αj<script type="math/tex" id="MathJax-Element-1635">α_j</script>的上下界可以通过下面的方法得到：

我们优化的时候，αj<script type="math/tex" id="MathJax-Element-1636">α_j</script>必须要满足上面这个约束。也就是说上面是αj<script type="math/tex" id="MathJax-Element-1637">α_j</script>的可行域。然后我们开始寻找αj<script type="math/tex" id="MathJax-Element-1638">α_j</script>，使得目标函数最大化。通过推导得到αj<script type="math/tex" id="MathJax-Element-1639">α_j</script>的更新公式如下：

这里Ek<script type="math/tex" id="MathJax-Element-1640">E_k</script>可以看做对第k<script type="math/tex" id="MathJax-Element-1641">k</script>个样本，SVM的输出与期待输出，也就是样本标签的误差。

而η<script type="math/tex" id="MathJax-Element-1642">η</script>实际上是度量两个样本和i和j<script type="math/tex" id="MathJax-Element-1643">和i和j</script>的相似性的。在计算η<script type="math/tex" id="MathJax-Element-1644">η</script>的时候，我们需要使用核函数，那么就可以用核函数来取代上面的内积。

得到新的αj<script type="math/tex" id="MathJax-Element-1645">α_j</script>后，我们需要保证它处于边界内。换句话说，如果这个优化后的值跑出了边界L和H，我们就需要简单的裁剪，将αj<script type="math/tex" id="MathJax-Element-1646">α_j</script>收回这个范围：

最后，得到优化的αj<script type="math/tex" id="MathJax-Element-1647">α_j</script>后，我们需要用它来计算αi<script type="math/tex" id="MathJax-Element-1648">α_i</script>：

到这里，和αi和αj<script type="math/tex" id="MathJax-Element-1649">和α_i和α_j</script>的优化就完成了

最后就是更新阈值b<script type="math/tex" id="MathJax-Element-1650">b</script>了，使得两个样本和i和j<script type="math/tex" id="MathJax-Element-1651">和i和j</script>都满足KKT条件。如果优化后αi<script type="math/tex" id="MathJax-Element-1652">α_i</script>不在边界上（也就是满足0<αi<C<script type="math/tex" id="MathJax-Element-1653">0<α_iyigi(xi)=1<script type="math/tex" id="MathJax-Element-1654">y_ig_i(x_i)=1</script>，这样我们才可以计算b<script type="math/tex" id="MathJax-Element-1655">b</script>），那下面的阈值b1<script type="math/tex" id="MathJax-Element-1656">b_1</script>是有效的，因为当输入xi<script type="math/tex" id="MathJax-Element-1657">x_i</script>时它迫使SVM输出yi<script type="math/tex" id="MathJax-Element-1658">y_i</script>。

同样，如果0<αj<C<script type="math/tex" id="MathJax-Element-1659">0 < \alpha_j < C</script>,那么下面的b2<script type="math/tex" id="MathJax-Element-1660">b_2</script>也是有效的：

如果0<αi<C<script type="math/tex" id="MathJax-Element-1661">0 < \alpha_i < C</script>和0<αj<C<script type="math/tex" id="MathJax-Element-1662">0 < \alpha_j < C</script>都满足，那么和b1和b2<script type="math/tex" id="MathJax-Element-1663">和b_1和b_2</script>都有效，而且他们是相等的。如果他们两个都处于边界上（也就是αi=0<script type="math/tex" id="MathJax-Element-1664">α_i=0</script>或者αi=C<script type="math/tex" id="MathJax-Element-1665">α_i=C</script>，同时αj=0<script type="math/tex" id="MathJax-Element-1666">α_j=0</script>或者αj=C<script type="math/tex" id="MathJax-Element-1667">α_j=C</script>），那么在b1<script type="math/tex" id="MathJax-Element-1668">b_1</script>和b2<script type="math/tex" id="MathJax-Element-1669">b_2</script>之间的阈值都满足KKT条件，一般我们取他们的平均值b=b1+b22<script type="math/tex" id="MathJax-Element-1670">b=\frac{b1+b2}{2}</script>。所以，总的来说对b<script type="math/tex" id="MathJax-Element-1671">b</script>的更新如下：

每次完成两个变量的优化后，还必须更新对应的Ei<script type="math/tex" id="MathJax-Element-1672">E_i</script>值，并将它们保存在列表中。

KKT条件分析

KKT条件具体可以查看深入理解拉格朗日乘子法（Lagrange Multiplier) 和KKT条件。

假设我们优化得到的最优解是：和αi,βi,ξi,w和b<script type="math/tex" id="MathJax-Element-1717">和α_i,β_i, ξ_i, w和b</script>。我们的最优解需要满足KKT条件：

同时βi,ξi<script type="math/tex" id="MathJax-Element-1718">β_i, ξ_i</script>都需要大于等于0，而αi<script type="math/tex" id="MathJax-Element-1719">α_i</script>需要在0和C之间。那可以分三种情况讨论：

因此，KKT条件变成了：

第一个式子表明如果αi=0<script type="math/tex" id="MathJax-Element-1720">α_i=0</script>，那么该样本落在两条间隔线外。第二个式子表明如果αi=C<script type="math/tex" id="MathJax-Element-1721">α_i=C</script>，那么该样本有可能落在两条间隔线内部，也有可能落在两条间隔线上面，主要看对应的松弛变量的取值是等于0还是大于0，第三个式子表明如果0<αi<C<script type="math/tex" id="MathJax-Element-1722">0<α_i（这点很重要，b<script type="math/tex" id="MathJax-Element-1723">b</script>就是拿这些落在分隔线上的点来求的，因为在分割线上wTx+b=1<script type="math/tex" id="MathJax-Element-1724">w^Tx+b=1</script>或者wTx+b=?1<script type="math/tex" id="MathJax-Element-1725">w^Tx+b=-1</script>嘛，才是等式，在其他地方，都是不等式，求解不了b<script type="math/tex" id="MathJax-Element-1726">b</script>）。具体形象化的表示如下：

from sklearn import datasets
import numpy as np
from sklearn.cross_validation import train_test_split

iris = datasets.load_iris() # 由于Iris是很有名的数据集，scikit-learn已经原生自带了。
X = iris.data[:, [2, 3]]
y = iris.target # 标签已经转换成0，1，2了
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=0) # 为了看模型在没有见过数据集上的表现，随机拿出数据集中30%的部分做测试

# 为了追求机器学习和最优化算法的最佳性能，我们将特征缩放
from sklearn.preprocessing import StandardScaler
sc = StandardScaler()
sc.fit(X_train) # 估算每个特征的平均值和标准差
sc.mean_ # 查看特征的平均值，由于Iris我们只用了两个特征，所以结果是array([ 3.82857143,  1.22666667])
sc.scale_ # 查看特征的标准差，这个结果是array([ 1.79595918,  0.77769705])
X_train_std = sc.transform(X_train)
# 注意：这里我们要用同样的参数来标准化测试集，使得测试集和训练集之间有可比性
X_test_std = sc.transform(X_test)
X_combined_std = np.vstack((X_train_std, X_test_std))
y_combined = np.hstack((y_train, y_test))

# 导入SVC
from sklearn.svm import SVC
svm = SVC(kernel=‘linear‘, C=1.0, random_state=0) # 用线性核，你也可以通过kernel参数指定其它的核。
svm.fit(X_train_std, y_train)
# 打印决策边界，这个函数是我自己写的，如果你想要的话，我发给你
plot_decision_regions(X_combined_std, y_combined, classifier=svm, test_idx=range(105,150))
plt.xlabel(‘petal length [standardized]‘)
plt.ylabel(‘petal width [standardized]‘)
plt.legend(loc=‘upper left‘)
plt.show()

svm = SVC(kernel=‘rbf‘, random_state=0, gamma=x, C=1.0) # 令gamma参数中的x分别等于0.2和100.0
svm.fit(X_train_std, y_train) # 这两个参数和上面代码中的训练集一样
plot_decision_regions(X_combined_std, y_combined, classifier=svm, test_idx=range(105,150))
plt.xlabel(‘petal length [standardized]‘)
plt.ylabel(‘petal width [standardized]‘)
plt.legend(loc=‘upper left‘)
plt.show()