SMO算法原理

揭开SMO算法的神秘面纱：优化非线性SVM的奥秘

在我们深入理解机器学习的旅程中，上一节我们探讨了非线性SVM与核函数的数学魅力。今天，让我们聚焦于被誉为“序列最小优化”（Sequential Minimal Optimization, SMO）的算法，它是解决复杂非线性问题的利器，由Platt在1998年提出。

在探索SMO之前，先重温一下目标优化函数，它在非线性SVM中扮演着核心角色。当引入软间隔和核函数时，我们的目标是寻找一个向量，使得函数达到极小值。该函数可以表示为：

向量为m维，设:

令:

考虑到输入变量只有，简化为:

进一步化简为:

这里，常数。

我们的任务是解决一个二次规划问题，选择自变量为，约束条件形如一个正方形盒子的对角线。实际上，这是一个单变量优化问题，目标是在这条线段上找到最优解。

初始解为，未考虑不等式约束的最优解为。由于：

我们可以推导出剪辑后解的表达式。这里，我们探讨了如何通过计算预测值与真实值的差值来简化目标函数：

令:

目标优化函数化简为:

通过求导并令：

继续化简得：

为了满足不等式约束，我们需要将限制在内，从而得到的表达式：

接下来，SMO算法的精髓在于如何选择优化的两个变量。它分为两步：外层循环选择违反KKT条件最严重的样本点作为第一个变量，内层循环则寻找能使目标函数变化显著的第二个变量。

外层循环：首先检查每个样本点是否满足KKT条件。选择违反条件最严重的点，若所有支持向量均满足，再考虑其他条件。

内层循环：对于已选择的，目标是找到能使或者最大化的。通过选择合适的，优化过程得以快速推进。

每次优化后，SMO算法会更新阈值和差值。当，根据KKT条件，我们可以推导出和的更新公式。

SMO算法的巧妙之处在于其高效地处理非线性问题，通过两变量的迭代优化，逐步逼近最优解。通过理解这些核心步骤，你将能够更好地掌握这一强大工具在机器学习中的应用。