很多人在学支持向量机SVM的时候最先被劝退的不是分类间隔而是“拉格朗日乘子法”这几个字明明前面还在讲怎么找一条最大间隔的直线怎么后脚就冒出来一堆 α、对偶问题、KKT 条件仿佛换了本书。我当年也是这样翻了好几版讲义才把这条线串明白。其实线性可分 SVM 的推导本质上就是解一个带不等式约束的凸优化问题拉格朗日乘子法正是处理这类约束的标准工具一点都不玄乎。这篇文章我打算顺着“几何直观 → 优化建模 → 拉格朗日变换 → 对偶求解 → 手算例题”这条路径把公式从头到尾完整推一遍最后用一组非常干净的三点数据带你手动算出 α、w、b。整个过程可以拿纸笔跟着走不需要依赖任何机器学习库。学完之后你再看 SMO、核函数、软间隔都会顺很多。适合正在学 SVM 的算法初学者、准备面试刷推导的人以及想补数学基础的开发者。1. 从“找最大间隔直线”说起线性可分SVM到底在解什么问题1.1 先有分类任务再有超平面假设我们有 n 个样本每个样本有特征向量 x_i类别标签是 y_i并且为了后面的数学推导方便约定二分类的标签为 1 和 -1而不是 0 和 1。如果存在一个超平面 w·x b 0 能把正负样本完全分开我们就说这个数据集是线性可分的。这里 w 是超平面的法向量b 是偏置项向量点乘 w·x 是“投影”的意思。在这个条件下所有满足 w·x_i b 0 的样本可以被判定为正类满足 w·x_i b 0 的样本判定为负类。但问题是能把两类数据分开的超平面通常有无数个。例如一条向右侧偏一点的直线、向左侧偏一点的直线都可能把训练样本完全分开。那么问题来了这无数条线里哪一条才是“最好”的SVM 给出的答案非常直观选那条“站在正负样本正中间”的线。也就是说这条线要离最近的正样本和最近的负样本都尽可能远。这样做的好处是模型对噪声和轻微扰动的容忍度更高泛化能力通常也更好。一个离样本太近的决策边界往往换个新样本就分错了。1.2 用数学描述“间隔”要衡量“离得远不远”先要定义距离。一个点 x_i 到超平面 w·x b 0 的距离公式是|w·x_i b| / ||w||这是中学就学过的点到直线距离公式在高维空间的推广。对于样本 x_i我们不仅关心它到超平面的绝对值距离还关心它是否被正确分类。如果把标签 y_i 乘进去就得到 y_i (w·x_i b)这个值如果正说明分类正确如果负说明分类错误。它的几何含义是带方向的“函数间隔”。训练集里所有样本的函数间隔最小值就决定了这个超平面离数据“最近”的距离。SVM 想要的超平面是让这个最小函数间隔尽量大。但我们马上会遇到一个问题w 和 b 同时放大或缩小任意倍数超平面本身不变函数间隔 y_i(w·x_ib) 却会跟着放大缩小所以“函数间隔”不是一个规范的量。解决办法是除以 ||w||也就是用几何间隔来度量y_i (w·x_i b) / ||w||这个式子表示样本 x_i 到超平面的带符号距离缩放 w、b 不会改变它的值。SVM 的目标就是最大化所有训练样本中最小几何间隔。1.3 把最大化间隔写成优化问题因为训练集线性可分我们可以通过尺度调整让距离超平面最近的样本满足y_i (w·x_i b) 1这个“1”不是凭空规定的。任何超平面都可以通过等比例缩放 w 和 b使最近样本的函数间隔恰好为 1。做完这个归一化之后所有样本的约束就统一成y_i (w·x_i b) ≥ 1此时几何间隔就变成了 1 / ||w||。最大化最小几何间隔等价于最大化 1/||w||再等价于最小化 ||w||。为了后面求导方便通常写成min 1/2 ||w||²subject to y_i (w·x_i b) ≥ 1对所有 i。这就是线性可分 SVM 的原始优化问题。这里最小化 ||w||² 而不是 ||w||是因为平方后函数光滑、便于求导并且最优解不变。为什么要 1/2纯粹是求导后消掉系数让公式干净。2. 拉格朗日乘子法速成从等式约束到不等式约束2.1 等式约束下的拉格朗日乘子法复习先说最经典的等式约束问题。比如min x y subject to x² y² 1这是一个在单位圆上找 xy 最小值的几何问题。没有约束时xy 没有下界加了约束后x 和 y 被限制在一个圆上。怎么解拉格朗日乘子法的思路是把这个带约束问题转成一个无约束问题。定义拉格朗日函数L(x, y, λ) x y λ(x² y² - 1)然后对所有变量分别求偏导并令其为 0。为什么可以这样做因为在极值点上目标函数的梯度方向必须与约束曲面的法向量方向平行拉格朗日乘子 λ 就用来表示这两个梯度之间的大小关系。用一句直观的话说如果不平行只要沿约束曲面稍微走一步目标函数还能继续下降所以不可能达到极值。这种手法本身不复杂但 SVM 稍微复杂了一点因为它的约束是不等式不是等式。2.2 不等式约束与KKT条件处理不等式约束需要引入 KKT 条件。所谓 KKT 条件简单理解就是拉格朗日乘子法在不等式约束下的扩展版。考虑一个形式化的问题min f(w) subject to g_i(w) ≤ 0i 1, ..., m为了方便先把不等式整理成小于等于 0 的形式。定义拉格朗日函数L(w, α) f(w) Σ_i α_i g_i(w)其中 α_i ≥ 0。极值点除了需要满足梯度为 0、原始约束 g_i(w) ≤ 0 以外还必须满足一个核心条件α_i · g_i(w) 0这个条件叫互补松弛条件。它的意思是如果第 i 个约束没有被激活也就是 g_i(w) 0那么 α_i 必须等于 0如果 α_i 0那么对应的约束必须取到等号 g_i(w) 0。可以用一个生活化类比来理解不等式约束就像一面围栏物体在没有抵到围栏时围栏对物体没有作用力只有当物体刚好压到围栏上时才会产生一个支撑力。这里的“支撑力”就是 α_i“围栏”就是约束边界。SVM 中那些真正落在最大间隔边界上的样本点就是“压到围栏”的点它们对应的 α_i 会大于 0其他离边界远的点对应 α_i 等于 0。这个性质是整个支持向量机名字的来源。需要说明的是KKT 条件在普通非凸问题里只是必要条件但在 SVM 的线性可分场景下目标函数是凸二次函数约束是线性不等式满足强对偶条件所以 KKT 条件既是必要条件也是充分条件。这给了我们后续通过对偶问题求解的底气。2.3 把SVM原始问题改写成拉格朗日函数现在把 SVM 原始问题套进这个框架。我们的约束是y_i (w·x_i b) ≥ 1为了变成小于等于 0 的标准形式写成1 - y_i (w·x_i b) ≤ 0对应每个样本引入一个拉格朗日乘子 α_i ≥ 0构造拉格朗日函数L(w, b, α) 1/2 ||w||² Σ_i α_i [1 - y_i (w·x_i b)]也有的教材写成减号形式本质上一种写法。我个人习惯用这个加号形式因为约束条件的符号和 α 的正负号不会混淆。接下来就要用这个 L 函数做文章。注意在拉格朗日函数里我们并不是直接求 L 的极小值就结束了而是要构造“原始问题”和“对偶问题”的博弈关系。原始问题是先对 α 求最大、再对 w 和 b 求最小对偶问题则是反过来先对 w 和 b 求最小、再对 α 求最大。在凸问题里这两个问题的解相等这就是强对偶性。实际计算中对偶问题往往更好解所以我们走对偶路线。3. 线性可分SVM推导三步拿到对偶问题3.1 对 w 和 b 求偏导得到关键等式求解对偶问题的第一步是固定 α先让 L 关于 w 和 b 取得最小值。因为 L 是关于 w 和 b 的凸函数直接求偏导并令其为 0就能得到最优条件。先对 w 求偏导∂L / ∂w w - Σ_i α_i y_i x_i 0所以w Σ_i α_i y_i x_i这个式子非常重要。它说明最优超平面的法向量 w可以表示成所有样本点的线性组合组合系数是 α_i y_i。也就是说最终的超平面完全由样本点决定而不是凭空冒出来的。再对 b 求偏导∂L / ∂b -Σ_i α_i y_i 0于是得到Σ_i α_i y_i 0注意这里没有直接解出 b 的表达式而是得到了一个关于 α 的线性约束。b 的求解要留到后面通过 KKT 条件处理。3.2 消去 w 和 b得到对偶函数得到了 w 关于 α 的表达式之后把它代回拉格朗日函数就能消掉原始变量 w 和 b。我们把 L(w, b, α) 一项一项展开。先看二次项1/2 ||w||² 1/2 (Σ_i α_i y_i x_i) · (Σ_j α_j y_j x_j) 1/2 Σ_i Σ_j α_i α_j y_i y_j (x_i · x_j)再看约束项里的第一部分Σ_i α_i y_i (w·x_i) Σ_i Σ_j α_i α_j y_i y_j (x_i · x_j)约束项里还有一部分是 Σ_i α_i y_i b但这一项等于 b · Σ_i α_i y_i b · 0 0所以在代回时直接消失。把这几项合在一起L 1/2 ΣΣ α_i α_j y_i y_j (x_i·x_j) - ΣΣ α_i α_j y_i y_j (x_i·x_j) Σ_i α_i Σ_i α_i - 1/2 Σ_i Σ_j α_i α_j y_i y_j (x_i·x_j)于是对偶问题变成max_α W(α) Σ_i α_i - 1/2 Σ_i Σ_j α_i α_j y_i y_j (x_i · x_j) subject to α_i ≥ 0且 Σ_i α_i y_i 0注意原来的最小值问题现在变成了一个只关于 α 的最大值问题。这个转变就是“拉格朗日对偶”。很多人推导到这里容易懵但只要跟着算一遍会发现每一步都是代入消元没有跳跃。3.3 KKT互补松弛条件与b的求解光靠对偶问题我们已经能求出 α但还要找回 b。这里必须用 KKT 互补松弛条件α_i [y_i (w·x_i b) - 1] 0这个条件告诉我们要么 α_i 0样本点落在间隔边界之外对模型没有贡献要么 y_i(w·x_ib)1样本点刚好落在最大间隔的边界上这种点就是支持向量。对于任意一个支持向量 x_s因为满足 y_s(w·x_s b) 1所以可以直接解得b y_s - w·x_s注意这里看到 y_s 直接出现在公式里不需要再除以 y_s因为对支持向量来说 y_s 是 ±1两边乘一个 y_s 后等式就变成 w·x_s b y_s。实际计算时为了避免浮点数误差导致选到略微偏离边界的样本通常把所有支持向量分别算出的 b 取平均值这样更稳定。3.4 决策函数与支持向量的本质有了 w 和 b决策函数就是f(x) sign(w·x b)把 w Σ α_i y_i x_i 代进去决策函数变成f(x) sign(Σ_i α_i y_i (x_i · x) b)这里出现了一个非常关键的现象预测时我们只需要计算新样本 x 与训练样本 x_i 的内积而大量 α_i 0 的样本根本不需要参与计算。只有支持向量的 α_i 非零换句话说支持向量机的模型参数虽然看起来长但真正“撑住”超平面的只有一小部分样本这个性质叫稀疏性。这也是为什么这类模型被称为“支持向量机”决定边界的不是所有样本而是那些“顶”在间隔边界上的支持向量。同时“只需要内积”这个性质也为后来的核技巧埋下了伏笔如果数据在当前空间线性不可分可以把它映射到更高维空间只要内积能算整个推导依然成立。不过这是后话线性可分的推导是理解一切的基础。4. 一个可以手算的例题三个点的线性可分SVM4.1 数据与优化目标为了把前面的公式落到纸面上我选一个故意设计得很简单的数据集。正类有两个点A (1, 2) B (2, 1)负类有一个点C (0, 0)这三个点有一个很漂亮的对称性A 和 B 都在直线 x y 3 上C 在原点。从几何上看最佳分界线大概率是一条与 x y 方向垂直的线也就是法向量方向为 (1, 1)。我们不用猜直接用对偶问题算。先把原始优化问题写出来。我们的目标是min 1/2 (w1² w2²) subject to y_A (w·A b) ≥ 1 y_B (w·B b) ≥ 1 y_C (w·C b) ≥ 1其中 y_A y_B 1y_C -1。三个变量是 w1、w2、b。4.2 构造对偶问题根据第三节的推导对偶问题是极大化 W(α)其中 α1、α2 对应正类点 A、Bα3 对应负类点 C。约束是α1, α2, α3 ≥ 0 α1·1 α2·1 α3·(-1) 0也就是α3 α1 α2接着计算样本之间的内积。A、B、C 三个点的内积矩阵是A·A 1²2² 5 B·B 2²1² 5 A·B B·A 1×2 2×1 4 A·C B·C C·C 0因为 C 是原点所以凡是和 C 相关的内积项全部为 0。这对手算非常友好。把内积代入对偶目标函数W(α) α1 α2 α3 - 1/2 [ 5α1² 8α1α2 5α2² ]为什么没有 α3 的二次项因为 C 和自己的内积是 0和 A、B 的内积也是 0所以 α3 只会以一次项出现不会出现在二次项中。后面我们会看到这个“巧合”让手算变得极其简单。4.3 求解α把 α3 α1 α2 代入目标函数W 2α1 2α2 - 1/2 (5α1² 8α1α2 5α2²)整理一下W 2α1 2α2 - 2.5α1² - 4α1α2 - 2.5α2²现在问题变成了在 α1 ≥ 0、α2 ≥ 0 条件下最大化这个二元函数。既然没有其他不等式约束直接对 α1 和 α2 求偏导并令其等于 0∂W/∂α1 2 - 5α1 - 4α2 0 ∂W/∂α2 2 - 4α1 - 5α2 0两个方程长得非常对称相减得到 α1 α2再代回任意一个方程2 - 9α1 0所以α1 α2 2/9 α3 α1 α2 4/9三个 α 都大于 0说明三个点全部会成为支持向量。这个结果也符合直觉A、B、C 确实是恰好撑住最大间隔边界的三个点。4.4 恢复 w 和 b利用 w Σ α_i y_i x_iw (2/9) × 1 × (1, 2) (2/9) × 1 × (2, 1) (4/9) × (-1) × (0, 0) (2/9 4/9, 4/9 2/9) (6/9, 6/9) (2/3, 2/3)和我们一开始的猜测一致w 的方向确实是 (1, 1) 方向。接着用支持向量 A 求解 b。因为 A 在间隔边界上满足 w·A b 1所以b 1 - w·A 1 - (2/3 × 1 2/3 × 2) 1 - 2 -1再用 C 验证一下。C 是负类满足 w·C b -1代入0 (-1) -1完全一致。于是最终的决策超平面是(2/3)x1 (2/3)x2 - 1 0化简一下就是x1 x2 1.5两个分类间隔边界分别是正类一侧的 x1 x2 3 和负类一侧的 x1 x2 0。A、B 正好都落在正类边界上C 落在负类边界上几何间隔大小为 3 / (2√2)最大间隔为 2/||w|| 3/√2。4.5 验证KKT条件看看每个样本的贡献我们最后验证一下互补松弛条件。对 A 来说α1 2/9 0并且函数间隔y_A(w·A b) 1 × (2 - 1) 1刚好取等号条件成立。B 同样算出来是 1C 算出来也是 1。三个点都牢牢压在间隔边界上所以它们的 α 都大于 0。反过来如果我们往数据集里加入一个离边界更远的正类点 D (3, 3)它的函数间隔会是 4 或者更大远大于 1那么根据互补松弛条件它对偶变量 α_D 必须等于 0。也就是说这个远点不会进入 w 的表达式决策边界不会因为它的加入而改变。理解这一点才算真正理解“支持向量”这四个字的含义真正决定模型的只有那些贴在边界上的点。5. 推导和实现中容易踩的坑5.1 拉格朗日函数符号写反这是初学者最常见的问题。同样是约束 y_i(w·x_i b) ≥ 1可以写成 1 - y_i(w·x_ib) ≤ 0也可以写成 y_i(w·x_ib) - 1 ≥ 0不同的写法会直接影响拉格朗日乘子的符号和 KKT 条件的形式。如果在某本教材里看到 α 符号和你习惯的不一样不要慌只要保持同一套符号体系从头到尾自洽结果是一样的。我个人的经验是写成“1 - y_i(w·x_ib) ≤ 0”这种形式配合 α≥0最容易记住也最不容易出符号错误。5.2 b 为什么不能直接求出来有些朋友在推导到对 b 求偏导那一步时会发现求导结果里根本没有 b 的表达式只有 Σα_i y_i 0于是疑惑 b 去哪了。原因是 b 在目标函数里没有正则项它只通过约束条件起作用所以无法从一阶条件中直接确定。b 必须依赖 KKT 的互补松弛条件从支持向量样本上反解。实操中还有一个细节如果支持向量不止一个建议用所有支持向量算出的 b 取平均因为浮点误差会让个别点看起来没有严格满足等式取平均能减小误差。5.3 对偶问题不能无脑用梯度上升对偶问题是二次规划问题直接对 W(α) 做梯度上升会遇到两个麻烦一是要保证 α_i ≥ 0 和 Σα_i y_i 0 两个约束始终成立二是样本多时内积矩阵规模很大。实际工程中很少直接手写二次规划求解而是使用 SMO 这类专用算法。SMO 的主要思想是每次只更新两个 α_i因为受等式约束限制至少两个变量才能在更新时保持 Σα_i y_i 0 不破坏。这个思路在理解了本节的对偶推导之后会显得非常自然。5.4 线性可分是起点不是终点看到这里你可能会想现实中哪有这么干净的线性可分数据确实真实数据里绝大多数情况是线性不可分的或者虽然是线性可分但存在噪声。线性可分 SVM 的意义在于它是整个 SVM 家族的地基。后续的软间隔 SVM只是把硬约束 y_i(w·x_ib)≥1 换成加了松弛变量的形式核 SVM只是把样本点之间的内积 x_i·x_j 换成核函数 K(x_i, x_j)。如果你把本文的推导过程亲手写过一遍再去看软间隔和核方法会发现只是多了一两个变量和一张“内积替换表”思路完全一样。就我个人经验来说这个三点例题虽然小但当年我花了一个下午把拉格朗日函数展开、求偏导、代回、解二次规划一步步算到最终结果后整个人对 SVM 的理解是质变的。那种“原来 α 和间隔边界真的是严格对应的”的感觉只靠看书是得不到的。所以我建议你拿起纸笔把第 4 节的例题完整走一遍。算完之后再看 SMO、核函数、软间隔你的思路会清晰非常多。