SVM对偶算法解析：从线性可分到Lagrange对偶问题

"这篇文章主要介绍了SVM学习中的对偶算法，包括问题的引入、二次规划的概念，以及Lagrange对偶性的应用。" 在机器学习领域，支持向量机（Support Vector Machine，简称SVM）是一种强大的监督学习模型，特别适用于分类任务。SVM的核心思想是寻找一个能够最大化类别间边界的超平面。当数据线性可分时，SVM的目标是最小化决策边界的宽度，同时确保所有样本点都在正确的一侧，即间隔最大化。 对于线性可分的SVM，优化问题通常表述为一个二次规划问题。这是一个形式为最小化二次函数并受线性约束的优化问题。具体来说，目标是找到权重向量w和偏置项b，使得所有样本点满足分类条件，即yi(w·xi + b) ≥ 1，其中yi表示样本点的类别（+1或-1），xi是特征向量。这个问题的可行域是凸的，因此存在唯一的全局最优解。 然而，直接解决这个带约束的优化问题往往很困难，尤其是当样本数量N较大时。为了解决这个问题，人们常常采用Lagrange乘子法，引入拉格朗日乘数αi来转换为无约束优化问题。拉格朗日函数L定义为原始目标函数加上每个约束条件的乘积与拉格朗日乘子的乘积。然后通过求解L对w、b和α的偏导数等于零的条件来找到最优解。 然而，原始问题的约束是不等式，而Lagrange乘子法适用于等式约束，这导致了方法的不适用。为了解决这个问题，引入了Lagrange对偶性。对偶问题是从原问题的约束条件出发，通过引入拉格朗日乘子αi，构造一个新的优化问题，其目标函数是原问题的拉格朗日函数，但约束条件变成了原问题的KKT条件（Karush-Kuhn-Tucker条件）。对偶问题的一个关键性质是，对于凸优化问题，其最优解至少不会比原问题的解差，且在某些情况下两者相等，即强对偶性。 在SVM的对偶问题中，样本点不再直接影响权重向量w，而是通过拉格朗日乘子αi间接影响。每个αi对应一个样本点，如果αi非零，那么对应的样本点就是支持向量，它们决定了超平面的位置。通过对偶问题的求解，可以有效地处理大规模数据集，因为它减少了优化变量的数量（从原始的特征维度到样本数量）。 总结起来，SVM的对偶算法是通过Lagrange对偶性将复杂的带约束优化问题转化为无约束问题，从而简化了求解过程，特别是在处理高维和大规模数据时。对偶问题的解决方案不仅给出了最优的超平面，还提供了对样本分布和决策边界的深刻理解。