SVM深度解析：最优间隔分类器与拉格朗日对偶

"这篇内容是关于支持向量机（Support Vector Machine, SVM）的详细解释，基于Andrew Ng的CS229课程，并进行了简化和改进。SVM是一种监督学习算法，常用于分类和回归任务。" 支持向量机（SVM）的核心思想是寻找一个最优的分类超平面，该超平面能够最大化两类样本之间的间隔。在二维空间中，这相当于找一条直线，使得两类点被此直线最远地分开。在高维空间中，这个超平面可能是一个超平面，而不是直线。 变量定义如下：x是n维输入样本，代表分类特征；y是分类标签，通常取1或-1。函数g(z)是一个阶跃函数，当z大于等于0时返回1，否则返回-1。SVM的分类器h(x)是通过一个线性组合wTx + b来确定的，其中w是权重向量，b是偏置项。 函数间隔（ functional margin）定义为样本点到决策边界的距离，如果y(i) = 1，我们希望wTx(i) + b远大于0；若y(i) = -1，我们希望wTx(i) + b远小于0。但是，函数间隔会受到w的大小影响，即它可以被任何非零标量倍增而不改变分类结果，因此引入了几何间隔（geometric margin），它是样本点在与w正交方向上的实际距离，不受w大小影响。 在SVM中，目标是找到具有最大几何间隔的超平面。给定线性可分的训练集，优化问题是找到一组w和b，使得每个样本点的几何间隔至少为γ，并且w的范数为1。但是，这个优化问题包含非凸约束，所以需要转换。通过设置w和b，使得wTx(i) + b = γy(i)，我们可以得到一个新的凸优化问题，这通常可以通过拉格朗日对偶法解决。 拉格朗日对偶问题的构建涉及定义主优化问题和广义拉格朗日函数。拉格朗日乘数αi和βi用来平衡原始问题的约束。通过引入这些乘数，我们可以将原始的非凸问题转化为一个对偶问题，这个对偶问题更容易求解。在满足某些条件下，对偶问题的解等价于原问题的解，这被称为强对偶性。 通过对偶问题，我们可以找到最优的w和b，进而构建出最优的分类超平面。在实践中，SVM通过解决对偶问题，利用核技巧（如高斯核、多项式核等）能够处理非线性可分的情况，实现对复杂数据的高效分类。这就是支持向量机的基本原理和优化过程。