前言实现了一个简单的SMO算法来优化SVM的对偶问题，其中使用了两个循环以完全随机的方式选择α，具体实现参考《机器学习算法实践-SVM中的SMO算法》。本文在之前简化版本的SMO算法的基础上，利用α对的启发式选择来优化SVM，实现了PlattSMO算法。另外，由于最近自己实现了一个遗传算法框架GAFT，所以也尝试用遗传算法对SVM的原始形式进行优化。本文算法的对应实现参考：https://github.com/PytLab/MLBox/tree/master/svm遗传算法框架GAFT项目地址：https://github.com/PytLab/gaftHeuristicselectionintextSMOVariables在SMO算法中，我们每次都需要选择一对α进行优化。通过启发式选择，我们可以更有效地选择要优化的变量，使目标函数下降最快。第一个α1和第二个α2PlattSMO采用不同的启发式算法。第一个变量的选择第一个变量的选择是一个外循环，不同于之前的整个αα列表的方便，这里我们在整个样本集和非边界样本集之间进行交替：首先我们遍历整个训练set，检查是否违反KKT条件，如果改变点的αiαi和xi，yixi，yi违反KKT条件，则说明改变点需要优化。Karush-Kuhn-Tucker(KKT)条件是正定二次规划问题的最优点的充分必要条件。对于SVM对偶问题，KKT条件很简单：遍历整个训练集并优化对应的α后，我们只需要在第二轮迭代中遍历非边界α即可。所谓非边界α是指那些不等于边界0或C的Alpha值的点。同样的点还是需要检查是否违反KKT条件并优化。之后不断在两个数据集之间来回交替，最后当所有α都满足KKT条件时，算法停止。为了能够快速选择步长最大的α，我们需要缓存所有数据对应的error，所以我们专门写了一个SVMUtil类来保存svm中的重要变量和一些辅助方法：下面选择alternatetraversalfor第一个变量大概代码，对应的完整Python实现（完整实现见https://github.com/PytLab/MLBox/blob/master/svm/svm_platt_smo.py）：第二个变量的选择第二个变量SMO中的选择过程是一个内循环。在我们选择了第一个α1之后，我们希望我们选择的第二个变量α2经过优化后会有较大的变化。根据我们之前推导的公式可以知道，新的α2的变化取决于|E1?E2|，当E1为正时，则选择最小的Ei作为E2，通常将每个样本的Ei缓存到一个列表中,通过选择α2和|E1?E2|来近似最大化步长在列表中。有时按照上述的启发式方法，函数值仍然不能下降到足够的程度，这就是按照以下步骤进行选择：在非边界数据集上选择一个能够使函数值充分下降的样本作为第二个变量如果没有非边界数据集，则只对整个数据选择第二个变量。如果还是没有选择，重新选择第一个α1第二次变量选择的Python实现：Platt论文中的KKTconditionsallowacertainerrorThereisatolerancetoallowcertainerrorinthejudgmentofKKTconditions,以及相应的Python实现：PlattSMO的完整实现见：https://github.com/PytLab/MLBox/blob/master/svm/svm_platt_smo.py对于之前我们使用PlattSMO优化的数据集可以得到：Visualize分割线和支持向量：可以看出PlattSMO优化后的支持向量与简化版SMO算法略有不同。用遗传算法优化SVM由于最近写了一个遗传算法框架，遗传算法作为一种启发式非引导搜索算法非常好用，所以尝试用遗传算法优化SVM。使用遗传算法优化，我们可以直接优化SVM的初始形式，这是最直观的形式：顺便下载一下自己的遗传算法框架。借助这个框架，我们只需要写几十行代码就可以优化SVM算法。Python代码就可以了。最重要的是写适应度函数。根据上面的公式，我们需要计算数据集中每个点到分界线的距离并返回最小距离，然后将其放入遗传算法中进行进化迭代。遗传算法框架GAFT项目地址：https://github.com/PytLab/gaft，使用细节见README。好的，我们开始为进化迭代构建种群。创建个体和种群对于二维数据点，我们需要优化的参数只有三个，即[w1,w2]和b。个体的定义如下：这里设置种群大小为600，没有遗传算子和GA引擎来创建种群。有什么特别的，直接使用框架内置的算子就可以了。对于适应度函数的部分，我们只需要描述上面svm的初始形式，只需要三行代码：开始迭代这里，迭代300代种群，画出遗传算法优化后的分割线为得到分割曲线如下图所示：完整代码见：https://github.com/PytLab/MLBox/blob/master/svm/svm_ga.py总结本文介绍SVM的优化，主要实现PlattSMO算法对SVM模型进行优化，并尝试使用遗传算法框架GAFT对初始SVMs进行优化优化。
