SMO算法原理
揭开SMO算法的神秘面纱：优化非线性SVM的奥秘
在我们深入理解机器学习的旅程中，上一节我们探讨了非线性SVM与核函数的数学魅力。今天，让我们聚焦于被誉为“序列最小优化”（Sequential Minimal Optimization, SMO）的算法，它是解决复杂非线性问题的利器，由Platt在1998年提出。
在探索SMO之前，先重温一下目标优化函数，它在非线性SVM中扮演着核心角色。当引入软间隔和核函数时，我们的目标是寻找一个向量，使得函数达到极小值。该函数可以表示为：
向量为m维，设:
令:
考虑到输入变量只有，简化为:
进一步化简为:
这里，常数。
我们的任务是解决一个二次规划问题，选择自变量为，约束条件形如一个正方形盒子的对角线。实际上，这是一个单变量优化问题，目标是在这条线段上找到最优解。
初始解为，未考虑不等式约束的最优解为。由于：
我们可以推导出剪辑后解的表达式。这里，我们探讨了如何通过计算预测值与真实值的差值来简化目标函数：
令:
目标优化函数化简为:
通过求导并令：
继续化简得：
为了满足不等式约束，我们需要将限制在内，从而得到的表达式：
接下来，SMO算法的精髓在于如何选择优化的两个变量。它分为两步：外层循环选择违反KKT条件最严重的样本点作为第一个变量，内层循环则寻找能使目标函数变化显著的第二个变量。
外层循环：首先检查每个样本点是否满足KKT条件。选择违反条件最严重的点，若所有支持向量均满足，再考虑其他条件。
内层循环：对于已选择的，目标是找到能使 或者 最大化的 。通过选择合适的 ，优化过程得以快速推进。
每次优化后，SMO算法会更新阈值 和差值 。当 ，根据KKT条件，我们可以推导出 和 的更新公式。
SMO算法的巧妙之处在于其高效地处理非线性问题，通过两变量的迭代优化，逐步逼近最优解。通过理解这些核心步骤，你将能够更好地掌握这一强大工具在机器学习中的应用。