★ FEATURED ARTICLE 学 SVM 的人分成两拨一拨能把对偶问题从头推到尾另一拨靠背公式撑过面试两个月后连 α 的约束是0 ≤ α ≤ C还是α ≥ 0都要愣一下。分水岭就卡在一个地方——拉格朗日算子和KKT条件这套东西到底在干什么。很多人管它叫算子其实标准叫法是乘子multiplier名字的差别背后是理解深度算子听起来像个神秘装置乘子则明明白白告诉你它是给约束配的一个价格。这篇不打算把 SVM 讲成一本凸优化教材我想干的事情更具体把拉格朗日函数是怎么被逼出来的、KKT 那五条为什么一条都不能少、以及这套理论最后怎么在 SVM 里落成一行行能跑的代码全部摊开说清楚。如果你正在啃 SVM 的推导或者写过调包代码但不知道C和gamma到底在动什么这篇应该能帮你把中间那层窗户纸捅破。全文涉及的内容会从动机、构造、KKT 逐条拆解、对偶理论一路走到手写简化 SMO代码是可以直接跑的。1. 约束优化的真实痛点为什么 SVM 绕不开这一套1.1 一个让新手懵圈的现场假设你手头有个最朴素的需求找一个点让它离原点最近但又必须落在某条直线上。写成数学就是min (x² y²)满足x y 2。不用任何高深工具代进去就完事了y 2 - x代入得到2x² - 4x 4求导4x - 4 0x 1, y 1最近距离平方是 2。这是一元函数极值初中生也能做。问题在于真实问题里约束不是一条直线这么客气。机器学习里出现的约束通常是成百上千条而且是不等式。SVM 的原始问题就是典型min ½‖w‖²同时要求对每一个训练样本y_i(w·x_i b) ≥ 1。这里w可能有上万维样本可能有几万个约束就是几万条不等式。你不可能像消元那样一个个代进去。这时候有两条路。第一条是直接在有约束的可行域里做搜索比如投影梯度每次走一步走完再投影回可行域。这条路能走但很别扭——投影到高维半空间的交集上本身就是个子问题而且一旦约束是等式加不等式的混合投影的计算量会失控。第二条路是把约束塞进目标函数里把有约束问题变成无约束问题然后套用我们熟悉的无约束优化工具。拉格朗日乘子法就是第二条路也是 SVM 走的那条路。我见过不少人第一次看到L(w, b, α) ½‖w‖² - Σα_i[y_i(w·x_i b) - 1]时的反应是这个式子哪来的。答案不神秘它就是目标函数 每个约束配一个系数乘上这个约束的违背量。1.2 拉格朗日乘子的几何直觉等高线与约束面相切要真正理解乘子得先接受一个几何图像。考虑二维平面上min f(x, y)受曲线g(x, y) 0约束。画出f的等高线是一圈圈闭合曲线约束曲线是一条线。假如最优点落在约束曲线上某处你沿着约束曲线走f的值不能继续下降——否则它就不是最优点了。这意味着在最优点附近约束曲线的切线方向与f的等高线切线方向一致换句话说两条曲线相切。相切在代数上意味着什么等高线的法向量是∇f约束曲线的法向量是∇g。两个曲线相切法向量就平行。于是存在一个标量λ使得∇f -λ∇g或者写成∇f λ∇g 0。这个式子就是拉格朗日乘子法的全部灵魂。λ不是什么玄学参数它是两个梯度共线时的比例系数。你如果记不住符号就记住这一句在最优点目标函数的梯度必须被约束的法向抵消掉因为任何沿着约束曲面的方向都不能让目标继续下降。SVM 里同样的故事发生在更高的维度。½‖w‖²的等高线是一圈圈超球面每条约束y_i(w·x_i b) 1在参数空间里是一个超平面。最优的w落在这些超平面的交集边界上∇(½‖w‖²) w必须被若干条起作用约束的法向线性组合出来。把这句话写成式子w Σ α_i y_i x_i就自然而然地掉出来了——它是梯度共线的直接翻译。1.3 SVM 为什么非要对偶形式有人会问原始问题不是已经能用二次规划求解器直接解了吗为什么教材非要绕一圈搞对偶这个问题问得很好因为如果只是想解一个线性可分的 SVM确实可以直接调 QP 求解器。但对偶形式带来了三样原始形式给不了的东西。第一样是核技巧的入口。对偶问题里样本只以x_i · x_j内积的形式出现从来不需要单独访问x_i或者x_j本身。这意味着你可以把内积整体换成一个核函数K(x_i, x_j)等价于把数据隐式映射到一个更高维甚至无穷维的空间里去而完全不用显式构造那个映射。这个能力是 SVM 从线性分类器变成非线性分类器的根本而它只在对偶形式下才成立。第二样是约束结构的简化。原始问题是n条线性不等式约束可行域是一个多面体对偶问题是n个箱约束0 ≤ α_i ≤ C加一条等式Σ α_i y_i 0。箱约束的好处是它天然可分解每次只动两个坐标就能解析地求出最优步长这就是 SMO 算法能高效工作的前提。你去解原始问题n条耦合的线性不等式可没有这么友好的结构。第三样是稀疏性的显式化。对偶解里绝大多数α_i会精确等于 0只有少数落在边界上的样本对应的α_i为正这些样本就是支持向量。这个性质直接从 KKT 的互补松弛条件里读出来不需要任何额外的工程手段。分类时只需要计算支持向量的内积推理成本跟支持向量数量成正比而不是跟训练集大小成正比。提示对偶形式不是更高级的等价写法它是一个能在特定维度关系下带来计算优势的重参数化。当特征维度远大于样本数时比如文本、生物特征对偶问题的变量数是n而不是d这个差距是数量级的。2. 拉格朗日函数怎么构造把约束折叠进目标2.1 等式约束的构造套路从最简单的情况入手min f(x)满足h(x) 0。构造拉格朗日函数L(x, λ) f(x) λh(x)。然后对x求偏导置零得到∇f(x) λ∇h(x) 0联立h(x) 0一共n 1个方程解n 1个未知数x的n个分量加λ。这套流程之所以有效核心在于它把一个在曲面上找极值的问题转换成了在无约束空间中找一个鞍点的问题。L(x, λ)关于x是要求极小关于λ是要求极大——因为λ的符号会自动调整到让h(x)这一项起惩罚作用。鞍点这个说法一开始听着别扭但你可以这么想如果x违反了约束λ就会往加重惩罚的方向调逼着x回到可行域而x一旦回到可行域λ就没有继续增大的动力了。两边互相较劲最后停下来的位置就是最优点。多个等式约束只是把一项扩展成和式L(x, λ) f(x) Σ λ_i h_i(x)。每个约束配一个自己的乘子互不干扰因为它们各自对应一个独立的法向。2.2 乘子的符号别背公式看梯度方向符号是新手最容易搞混的地方。有人写f - λh有人写f λh还有人把不等式的符号和等式混在一起。我自己的记法是只看约束的形式不看教材的约定。如果约束写成h(x) 0那么λh和-λh都对只是λ的符号相反最终解出的x完全一样。因为等式约束是双向的h 0和-h 0是同一个集合。如果约束写成g(x) ≤ 0那么必须用μg(x)且要求μ ≥ 0。为什么是这个符号因为在最优点如果约束是起作用的也就是g(x) 0那么目标函数的梯度必须指向可行域内部才能继续下降而可行域内部是g 0那一侧∇g指向g增大的方向也就是可行域外部。要让∇f被拉回来就需要∇f -μ∇g且μ ≥ 0即∇f μ∇g 0且μ ≥ 0。如果你的约束写成了g(x) ≥ 0SVM 里就是这种形式y_i(w·x_i b) - 1 ≥ 0那么为了维持μ ≥ 0的约定就要写成-μg(x)。SVM 教材里那个L ½‖w‖² - Σα_i[y_i(w·x_i b) - 1]的负号就是这么来的。我第一次推导时在这里卡了半小时就是因为照着≤ 0的模板抄结果α的符号全反了最后对偶问题成了最大化一个负定二次型。注意符号约定不统一是凸优化资料里最常见的坑。看任何一份推导第一步先确认它用的是g ≤ 0还是g ≥ 0然后再往下读别硬套记忆里的公式。2.3 手算一个等式约束的例子拿一个能算到底的例子练手min x² y²满足x y 2。构造L(x, y, λ) x² y² λ(x y - 2)。对x求偏导2x λ 0得x -λ/2。 对y求偏导2y λ 0得y -λ/2。所以x y。代回约束2x 2x y 1λ -2。目标值1 1 2。这个结果和我们直接消元得到的一致。注意λ -2是负数这完全正常——等式约束的乘子符号没有限制。同时注意一个细节λ的量纲是目标函数单位每约束单位这里约束x y增加 1最优值会增加λ -2等下实际是减小 2。因为约束从x y 2放宽到x y 3最优点变成(1.5, 1.5)目标值4.5增加了 2.5 而不是 -2。这里我算错了方向。正确的敏感度关系是把约束写成h(x) x y - 2 0那么∂(最优值)/∂(约束右端项) -λ 2。验证一下右端从 2 变到 3约束变成x y 3最优点(1.5, 1.5)目标值2.25 2.25 4.5相对原来增加了 2.5。而-λ 2只给出了一阶近似因为这是个二次函数二阶项贡献了剩下的 0.5。乘子给的是局部敏感度不是全局增量这一点在理解影子价格时非常重要。2.4 从等式到不等式符号是这么变的不等式的引入让整个框架复杂了一档因为多了一个这个约束到底起不起作用的判断。考虑min f(x)受g(x) ≤ 0。构造L(x, μ) f(x) μg(x)μ ≥ 0。现在有两种情况。如果无约束最优解本身就满足g(x) 0那约束是松的最优点就是无约束最优点此时∇f 0要让∇f μ∇g 0成立只能是μ 0。反过来如果μ 0那么为了让等式成立∇f必须非零也就是最优点被约束顶住了必然是g(x) 0。把这两种情况合起来写就是μg(x) 0。这一条叫互补松弛是整个 KKT 体系里信息量最大的一条后面会专门展开。它说的是乘子和约束违背量两者至少有一个是零。约束不起作用的时候乘子为零乘子为正的时候约束一定卡在边界上。这个逻辑放到 SVM 里就是α_i 0的样本y_i(w·x_i b) - 1 0它们离边界很远对模型没有影响α_i 0的样本y_i(w·x_i b) - 1 0它们恰好压在间隔边界上这就是支持向量。支持向量的定义不是离决策边界近的点而是互补松弛条件里乘子非零的那些点这两个说法在硬间隔下等价但在软间隔下就有了差别后面细说。3. KKT 条件逐条拆解五个条件到底在说什么3.1 原始可行性约束得先满足第一条最没有技术含量但对写代码的人最重要g_j(x) ≤ 0h_i(x) 0。这就是说你找到的那个点必须在可行域里。在实际求解里这一条对应的是裁剪操作。SMO 每次更新两个乘子α_i和α_j之后必须把它们强制投影回0 ≤ α ≤ C且Σ α_i y_i 0的可行域。两步更新里等式约束由解析公式保证箱约束靠clip保证α_j更新完先裁到区间[L, H]再由等式约束反推α_i。这个裁剪不是可选的工程优化它是原始可行性的直接要求不裁的话下一轮算出来的所有量都没有意义。我见过一个初学者写的版本忘了裁剪跑了几百轮之后α出现了负值然后w的计算结果莫名其妙最后排查了半天才发现问题。这类错误的特征是损失函数可能还在下降但解已经跑出了可行域KKT 违反度的计算完全失效。3.2 平稳性梯度为零这件事在约束下的正确形态第二条是∇f(x) Σ μ_j ∇g_j(x) Σ λ_i ∇h_i(x) 0。这一条我在 1.2 节已经用几何图像解释过了它是目标梯度被约束法向抵消的代数表达。需要强调的一点是这个条件是在拉格朗日函数上求梯度为零不是原目标函数。很多人第一次看会说最优点梯度怎么会是零明明在边界上梯度不为零。当然不为零∇f一般不在原点是零∇L才是零。搞混这两个会带来严重的后果比如在写代码时用∇f的范数作为收敛判据那就会永远等不到收敛。在 SVM 里平稳性条件给出两个结果∇_w L 0 ⇒ w Σ α_i y_i x_i∇_b L 0 ⇒ Σ α_i y_i 0。第一个式子说明w完全由训练样本的加权和表示权重就是α_i y_i第二个式子说明正负类的乘子加权和为零。后一个式子在 SMO 里是硬性约束每次更新完两个变量必须重新满足它。3.3 对偶可行性不等式乘子的符号要求第三条μ_j ≥ 0。这条约束看着最没内容实际上它是整个理论成立的关键支柱。如果没有它μ可以取负值那么拉格朗日函数关于μ就不再是凹的弱对偶性就崩了所有的对偶结论都会失效。这条约束并没有直接出现在拉格朗日函数的构造里它是被逼出来的。你如果固定x把拉格朗日函数看成μ的函数L(x, μ) f(x) μg(x)。如果g(x) 0违反了约束要让这个函数有上界μ只能取 0 到无穷如果g(x) ≤ 0μ增大时L会减小上确界在μ → ∞时取到且值为∞。所以对偶函数q(μ) inf_x L(x, μ)只在μ ≥ 0上有意义这就是这条条件在数学上的来源。在 SVM 里α_i ≥ 0就是这一条。软间隔版本里它变成0 ≤ α_i ≤ C上界C来自另一个约束的对偶可行性这个我放到 5.6 节讲。3.4 互补松弛整个 KKT 里最有信息量的一条第四条μ_j g_j(x) 0逐分量成立。我在 2.4 节已经讲了它的推导逻辑这里只讲它在 SVM 里的实际后果因为这一条是理解支持向量最直接的入口。硬间隔 SVM 的互补松弛是α_i [y_i(w·x_i b) - 1] 0。逐个样本分析α_i 0这个样本对w没有贡献因为它不出现在w Σ α_i y_i x_i里。它的约束是松的y_i(w·x_i b) 1离边界有距离。α_i 0约束必须取等号y_i(w·x_i b) 1。这个样本恰好压在间隔边界上它就是支持向量。于是w只由支持向量决定训练完以后那些α_i 0的样本可以直接扔掉预测时完全用不上。这就是 SVM 稀疏性的来源。它不是设计出来的优化技巧而是互补松弛条件的直接推论。软间隔的情况稍微丰富一点因为α_i被封在[0, C]内于是分三种情况α_i 0不在间隔内也不在边界上y_i f(x_i) 1。0 α_i C正好在间隔边界上y_i f(x_i) 1。这类叫自由支持向量。α_i C在间隔内部或者被误分类y_i f(x_i) ≤ 1。这类叫边界支持向量。第三种情况下乘子被上界卡住不能再增大所以约束是松的y_i f(x_i) 1但乘子非零互补松弛仍然成立——因为它只要求α_i和y_i f(x_i) - 1里有一个为零现在α_i C ≠ 0那y_i f(x_i) - 1必须为零不对这里得小心。软间隔的 KKT 里互补松弛有两组α_i[y_i f(x_i) - 1 ξ_i] 0和(C - α_i)ξ_i 0。当α_i C时第二组要求ξ_i 0也不对。第二组是β_i ξ_i 0其中β_i C - α_i。α_i C时β_i 0ξ_i可以任意非负所以松弛变量为正、样本落在间隔内部甚至被误分类都是允许的。这个细节在推公式的时候很容易搞错方向我在 5.6 节会把完整的两组条件列清楚。3.5 凸性KKT 从必要升级为充要的开关到这里五条齐了原始可行性、平稳性、对偶可行性、互补松弛。有教材把平稳性拆成原始/对偶两组成了六条也有把凸性当成第五条 KKT 条件的。我倾向于后者因为对做 SVM 的人来说凸性是最该被单独强调的一条。原因是这样对于一般的光滑约束优化问题KKT 条件是必要条件——最优点处一定满足 KKT但满足 KKT 的点不一定是最优点也可能是鞍点或者局部极大点。而对凸优化问题目标函数凸、等式约束仿射、不等式约束凸KKT 条件升级成充要条件只要一个点满足 KKT它就是全局最优解。这个升级至关重要。它意味着你不需要找到最优解再验证 KKT而是可以直接求解 KKT 方程组解出来就是最优解。SMO 之所以能用一个简单的启发式迭代收敛到全局最优靠的就是这个性质。它每一轮都在减少 KKT 违反度而 KKT 违反度归零等价于找到全局最优。SVM 的原始问题是min ½‖w‖²受线性不等式约束目标函数是严格凸的二次函数约束是仿射的完美符合凸优化的条件。所以 KKT 在这里是充要的没有任何理论上的坑。3.6 一个手工验证互补松弛的例子还是拿一个能算完的例子min (x - 1)² (y - 1)²满足x y ≤ 1。无约束最优是(1, 1)代入约束1 1 2 1违反了。所以约束一定起作用。构造L (x-1)² (y-1)² μ(x y - 1)μ ≥ 0。平稳性2(x-1) μ 02(y-1) μ 0得x y 1 - μ/2。互补松弛μ(x y - 1) 0。假设μ 0则x y 1x y - 1 1 0矛盾。所以μ 0必有x y 1即2(1 - μ/2) 12 - μ 1μ 1。检验μ 1 ≥ 0满足对偶可行性。最优解x y 0.5目标值0.25 0.25 0.5。这个例子里μ 1也有直观解释约束右端从 1 放宽到 1.2最优点会向(1, 1)移一点目标值大约下降0.1左右-μ给出的一阶敏感度是-1方向对得上。4. 对偶函数与强对偶SVM 对偶推导的地基4.1 对偶函数的定义与它为什么一定是凹的定义拉格朗日函数之后取它对原始变量x的下确界得到q(λ, μ) inf_x L(x, λ, μ)。这个q叫对偶函数。它有一个非常反直觉但极其重要的性质不管原问题是不是凸的q一定是凹函数。证明只需要一行。L(x, λ, μ)关于(λ, μ)是仿射的也就是一堆线性函数的和。一族仿射函数逐点取下确界结果一定是凹的这个性质叫下确界保持凹性因为凹函数的下水平集是凸的取交还是凸的。所以q是凹的无论f、g、h长什么样。这个性质的实际意义在于对偶问题max q(λ, μ)受μ ≥ 0是一个凹最大化问题等价于凸最小化。也就是说哪怕原始问题是难啃的非凸问题它的对偶问题也是凸的可以用凸优化工具求解。对 SVM 来说我们更关心的是另一个推论q的具体表达式是可以解析算出来的。因为L关于w和b是二次加线性的下确界可以直接用求导置零的方式算出来得到q(α) Σ α_i - ½ ΣΣ α_i α_j y_i y_j x_i·x_j。这个式子是α的凹二次函数最大化它就是一个标准的二次规划问题。4.2 弱对偶一个几行就能证明但极其关键的结论设p*是原始问题的最优值d*是对偶问题的最优值。弱对偶说d* ≤ p*。证明对任意可行的x满足g(x) ≤ 0、h(x) 0和任意μ ≥ 0有L(x, μ) f(x) μg(x) ≤ f(x)因为μ ≥ 0且g(x) ≤ 0乘积非正。而q(μ) inf_x L(x, μ) ≤ L(x, μ) ≤ f(x)。这个不等式对任意可行的x成立取x为原始最优解x*得q(μ) ≤ f(x*) p*。再对μ取上确界d* ≤ p*。这几行推导没有用到任何凸性假设所以它普适。它的含义是对偶问题给出的永远是原始最优值的下界而且这个界是能算的因为对偶问题是凸的。SVM 里的实际用途是如果你用某种启发式方法在解对偶问题任何时刻的q(α)值都是原始最优值的下界你可以用它做单调性检测。更有用的是p* - d*这个差值叫对偶间隙它是零的时候说明两边都找到了解可以做收敛判据。4.3 强对偶成立的条件与 SVM 的合规性强对偶说d* p*对偶间隙为零。这不是无条件成立的。最常用的充分条件是Slater 条件问题是凸的且存在一个严格可行点即存在x使得所有不等式约束严格成立g_j(x) 0等式约束成立。SVM 满足这个条件吗原始问题是凸二次规划约束是y_i(w·x_i b) - 1 ≥ 0。只要数据是线性可分的就一定能找到一组(w, b)让所有约束严格大于零把‖w‖缩小一点就行。所以 Slater 条件成立强对偶成立。对于线性不可分的数据硬间隔 SVM 的可行域是空的原始问题无解这套推导直接失效。这也是软间隔必须引入的原因它不是为了容忍噪声而做的工程妥协而是让可行域非空、让强对偶仍然成立的数学要求。引入松弛变量ξ之后可行域重新变成非空的Slater 条件再次成立整套理论继续可用。提示很多教程说软间隔是为了处理噪声这个说法对但不完整。从优化理论角度看硬间隔在线性不可分数据上连可行解都没有问题本身是病态的软间隔是把问题变成良性问题的必要改造。4.4 对偶间隙为零意味着什么强对偶成立时原始最优解和对偶最优解之间有一个很强的联系如果x*是原始最优、(λ*, μ*)是对偶最优那么x*一定是L(x, λ*, μ*)关于x的极小点。这一点是 KKT 平稳性条件的来源也是 SMO 能通过解对偶问题得到原始解w的理论依据。更实用的一点是对偶间隙可以当收敛判据。SMO 迭代过程中α每更新一次都可以算出一个q(α)值和一个原始可行解的f值用当前的w、b代入两者的差就是当前的间隙上界。不过实际实现里很少有人真的去算这个因为计算原始可行解的开销不小大家更常用 KKT 违反度作为替代判据原因我在第 6 节解释。5. 把 SVM 塞进这套框架对偶推导全过程5.1 原始问题硬间隔的形式化给定训练集{(x_i, y_i)}y_i ∈ {-1, 1}硬间隔 SVM 要找一个超平面w·x b 0使得所有样本都被正确分类且离超平面的最小距离几何间隔最大化。几何间隔是y_i(w·x_i b) / ‖w‖。由于w和b可以同比例缩放而不改变超平面我们约定让最近的样本满足y_i(w·x_i b) 1这样几何间隔就是1/‖w‖。最大化1/‖w‖等价于最小化‖w‖再平方除以二就是为了求导方便min_{w,b} ½‖w‖²s.t. y_i(w·x_i b) ≥ 1, i 1..n。函数间隔取 1 这个约定不是随意的它是利用缩放自由度做的规范化。没有这个规范w可以任意小问题就没有下界。这个细节在推导时经常被略过但它是整个形式化能成立的前提。5.2 构造拉格朗日函数按 2.2 节的符号约定约束写成了≥ 0的形式所以要用减号配乘子L(w, b, α) ½‖w‖² - Σ α_i [y_i(w·x_i b) - 1]α_i ≥ 0。展开一下会更清楚每一项的来源L ½‖w‖² - Σ α_i y_i w·x_i - b Σ α_i y_i Σ α_i。第一项是原始目标后面三项分别是约束里的w部分、b部分和常数部分配上的乘子。5.3 对 w 和 b 求偏导为什么置零就是全局最优对w求梯度∇_w L w - Σ α_i y_i x_i。置零得w Σ α_i y_i x_i。对b求偏导∂L/∂b -Σ α_i y_i。置零得Σ α_i y_i 0。这里有一个必须说清楚的细节为什么置零就一定是全局最小而不是局部极值看L关于w的 Hessian是单位矩阵I正定。所以L关于w是严格凸的二次函数唯一的驻点就是全局最小点。这个论证很简单但很重要因为它保证了q(α) inf_w L这个下确界是可以解析算出来的不需要解任何子问题。b的情况更微妙。L关于b是线性的系数是-Σ α_i y_i。线性函数没有内部极小点系数非零时b → ±∞会让L → -∞下确界是负无穷只有系数为零时L与b无关下确界才有限。于是Σ α_i y_i 0这个条件不是我们额外加上的约束而是下确界有限这件事本身逼出来的。任何一组让Σ α_i y_i ≠ 0的α对应的对偶函数值都是-∞在最大化时会被自动淘汰。这个视角比求导置零更深一层它解释了为什么对偶问题里会凭空多出一条等式约束。我当年就是在这里想通的对偶问题的约束不是人为设定的是拉格朗日函数本身的结构决定的你只是把哪些α能让下确界有限这个条件显式写了出来。5.4 回代得到对偶问题把w Σ α_i y_i x_i和Σ α_i y_i 0代回L。第一项½‖w‖² ½ (Σ α_i y_i x_i)·(Σ α_j y_j x_j) ½ ΣΣ α_i α_j y_i y_j (x_i·x_j)。第二项-Σ α_i y_i w·x_i -Σ α_i y_i (Σ α_j y_j x_j)·x_i -ΣΣ α_i α_j y_i y_j (x_i·x_j)。第三项-b Σ α_i y_i 0用了等式约束。第四项Σ α_i。合起来L Σ α_i - ½ ΣΣ α_i α_j y_i y_j (x_i·x_j)。对偶问题就是最大化这个式子max_α Σ α_i - ½ ΣΣ α_i α_j y_i y_j (x_i·x_j)s.t. Σ α_i y_i 0, α_i ≥ 0。写成矩阵形式令K是 Gram 矩阵K_ij x_i·x_jy是标签向量Q (y y^T) ⊙ KHadamard 积则目标函数是1^T α - ½ α^T Q α。Q是半正定的所以这是凹二次最大化标准的凸二次规划。注意这里Q的维度是n × n。当样本数上万时光存Q就要占 800MB 内存float64这是个实打实的工程约束第 6 节会讲怎么处理。5.5 KKT 在 SVM 中的具体形态支持向量从哪冒出来把 KKT 四条逐条翻译到 SVM原始可行性y_i(w·x_i b) ≥ 1α_i ≥ 0。平稳性w Σ α_i y_i x_iΣ α_i y_i 0。对偶可行性α_i ≥ 0。互补松弛α_i [y_i(w·x_i b) - 1] 0。第四条是全部价值所在。它把样本分成两类α_i 0的非支持向量和α_i 0的支持向量。而后者必须满足y_i(w·x_i b) 1。这个等式给出了b的计算方法随便挑一个α_i 0的样本b y_i - w·x_i。理论上任何一个支持向量都能算出同样的b。实际实现里通常会取所有自由支持向量的平均值因为浮点误差会让每个算出来的b略有不同取平均更稳。我试过只用第一个支持向量算b在某些病态数据上偏差能到1e-2量级取平均之后降到1e-10以下。这个差别在测试集上可能不明显但如果你要做 KKT 违反度检查偏差大了会误判。5.6 软间隔C 是怎么进场的软间隔引入松弛变量ξ_i ≥ 0原始问题变成min ½‖w‖² C Σ ξ_is.t. y_i(w·x_i b) ≥ 1 - ξ_i, ξ_i ≥ 0。C是惩罚系数控制最大化间隔和最小化违反量之间的权衡。C越大越不容忍违反C → ∞退化成硬间隔。拉格朗日函数L ½‖w‖² C Σ ξ_i - Σ α_i[y_i(w·x_i b) - 1 ξ_i] - Σ β_i ξ_iα_i ≥ 0, β_i ≥ 0。对ξ_i求偏导C - α_i - β_i 0即α_i β_i C。由于β_i ≥ 0得到α_i ≤ C。这就是上界的来源——它不是人为加的限制是对ξ的对偶可行性条件推出来的。把ξ消掉之后对偶问题变成max_α Σ α_i - ½ ΣΣ α_i α_j y_i y_j K_ijs.t. Σ α_i y_i 0, 0 ≤ α_i ≤ C。目标函数和硬间隔完全一样唯一的区别是多了上界C。这个变化看似微小但让整个问题在线性不可分数据上变得有解。软间隔的互补松弛有两组必须写全α_i [y_i(w·x_i b) - 1 ξ_i] 0(C - α_i) ξ_i 0按α_i的取值分三种情况α_i 取值ξ_iy_i f(x_i)样本位置α_i 00≥ 1间隔外分类正确0 α_i C0 1恰在间隔边界上α_i C≥ 0≤ 1间隔内或被误分类第三种情况里ξ_i可以大于零这就是为什么α_i C的样本允许违反间隔。行 2 里ξ_i必须为零是因为C - α_i 0互补松弛逼着ξ_i 0再代回第一组条件就得到y_i f(x_i) 1。这套分类是调参时的核心依据。你如果发现绝大多数α_i都顶在C上说明C太小或者数据本身噪声太大模型基本没学到东西如果所有α_i都严格在(0, C)内部说明C给得很大、数据近似线性可分可以考虑直接用硬间隔的结论。5.7 核技巧只有对偶形式才能干的事对偶问题里样本只以x_i·x_j的形式出现。这个事实的价值在于你可以把这个内积整体替换成K(x_i, x_j) φ(x_i)·φ(x_j)其中φ是一个到高维甚至无穷维空间的映射而完全不用构造φ。常用的核核函数表达式参数适用场景线性核x_i·x_j无高维稀疏数据文本分类多项式核(γ x_i·x_j r)^dγ, r, d特征交互明显的中低维数据RBF 核exp(-γ‖x_i - x_j‖²)γ通用默认选择边界光滑Sigmoid 核tanh(γ x_i·x_j r)γ, r少见参数敏感为什么只有对偶形式能这么干因为原始问题里w是显式的你要做非线性映射就得真的构造φ(x)并把w升到高维维度爆炸无法承受。对偶形式里w被消掉了只剩内积而内积可以用核函数在原始维度上算成本只跟原始维度有关。RBF 核对应的φ是无穷维的这个映射根本没法显式构造但对偶形式下毫无压力。这就是核技巧的威力也是 SVM 在深度学习兴起之前长期占主导地位的技术原因。γ的直观含义是单个样本的影响半径。γ越大exp(-γ‖x_i - x_j‖²)衰减越快影响半径越小决策边界越扭曲容易过拟合γ越小边界越平滑容易欠拟合。6. 动手实现简化 SMO 与 KKT 违反度校验6.1 准备工作核矩阵与工作变量SMO 的思路是把一个大 QP 拆成一串只有两个变量的子问题。为什么是两个因为等式约束Σ α_i y_i 0必须始终成立一次只动一个变量会立刻破坏它动两个才能同时满足等式和箱约束。这是 SMO 选择两个乘子的数学理由不是工程上的随意决定。每次选取一对(i, j)固定其他所有α子问题有解析解α_j^{new} α_j - y_j (E_i - E_j) / η其中η 2K_ij - K_ii - K_jj。η的推导值得看一眼η K_ii K_jj - 2K_ij ‖φ(x_i) - φ(x_j)‖² ≥ 0。它是两个样本在特征空间里的距离平方。如果两个样本在特征空间完全重合η 0子问题退化无法更新这时必须跳过这一对。代码里要显式判η ≤ 0的情况。更新完α_j之后α_i由等式约束反推α_i^{new} α_i y_i y_j (α_j - α_j^{new})。裁剪区间由箱约束和等式约束共同决定若y_i ≠ y_jL max(0, α_j - α_i)H min(C, C α_j - α_i)。若y_i y_jL max(0, α_i α_j - C)H min(C, α_i α_j)。这两组公式要记牢写反了会导致不收敛。我自己的记忆方法是y不同意味着两个乘子在等式约束里符号相反它们会互相争夺总量y相同则是一起分享总量所以上界受α_i α_j约束。偏置b的更新也有讲究b1 b - E_i - y_i(α_i^{new} - α_i)K_ii - y_j(α_j^{new} - α_j)K_ijb2 b - E_j - y_i(α_i^{new} - α_i)K_ij - y_j(α_j^{new} - α_j)K_jj如果α_i更新后在(0, C)内部用b1否则看α_j用它对应的b2两个都被卡在边界上就用(b1 b2)/2。注意这里的E_i、E_j必须是更新前的值更新完α之后再算E就错了。6.2 两个乘子的解析更新与裁剪区间完整的核心循环逻辑import numpy as np def kkt_violated(a, y, E, C, tol): 判断单个样本是否违反 KKT 条件 r y * E if a 1
阅读完成 · 觉得有帮助？
