拉格朗日对偶问题：把 w 和 b 全部换成 α

小象实战讲义 · 机器学习算法精讲

上一节把”找最大间隔”变成了优化问题 $\min \frac{1}{2}\Vert w\Vert^2$ s.t. $y_i(w^Tx_i+b)\ge 1$，并且顺手把拉格朗日函数也构造好了。但这个函数里同时住着三类参数——$\alpha$、$w$、$b$，而且一边要求最大值、一边要求最小值——讲师直言：很难做，不太好解。这一节他做的全部事情其实就一件：把 $w$ 和 $b$ 从问题里彻底消掉，只剩下 $\alpha$。消完之后问题变成什么样、约束条件还剩下哪两条、这样做为什么不是”为了显示数学的技巧”，就是本节的主线。讲师开讲时还预告了一个问题——“为什么最大间距是比较好的？（已经有同学问了）“——这个直觉要到《SVM 计算过程》一节用一个完整例子来回答，本节先把推导走通。

💡 核心导读

• 大框架：非等式优化天然是”最大 × 最小”的问题 $\min_x\max_{\lambda\ge 0} L$；把 $\max$ 和 $\min$ 调换次序，先求内层最小、再求外层最大——这就是对偶式。
• 第一步：$L$ 对 $w$ 求导置零 ⟹ $w = \sum_i \alpha_i y_i x_i$——最优的 $w$ 是训练样本的线性组合。
• 第二步：$L$ 对 $b$ 求导置零 ⟹ $\sum_i \alpha_i y_i = 0$——$b$ 从问题里消失。
• 代回：两处二次型恰好相等、$b$ 项被等式约束整块清零 ⟹ $L(\alpha) = \sum_i \alpha_i - \frac{1}{2}\sum_i\sum_j \alpha_i\alpha_j y_i y_j (x_i^T x_j)$。
• 收获：变量只剩 $\alpha$，约束只剩两条（$\alpha_i \ge 0$、$\sum_i \alpha_i y_i = 0$）——SVM 的对偶形式（dual form）。

回顾：非等式优化是”最大 × 最小”的问题

先用两分钟把上次的东西接上（KKT 条件的完整版在《拉格朗日乘子法（3）》一节，这里只取结论）。一维例子：优化 $f(x) = x^2$，约束 $x \ge b$（标准形 $g(x) = b - x \le 0$）。拉格朗日函数：

$$L(x, \lambda) = x^2 + \lambda(b - x), \qquad \lambda \ge 0$$

对 $x$ 求导置零得 $2x - \lambda = 0$，即 $x^* = \lambda/2$；约束激活时 $x = b$，代回去 $\lambda^* = 2b$。两种情况（最优解在约束范围内/外）被同一组条件统一成 $\lambda^* = \max(0, 2b)$、$x^* = \max(0, b)$。

这次回顾要往上再抬一层。讲师的总结：等式优化已经学过（求导置零）；非等式优化，要同时考虑最优解所在的范围——正因为要”兼顾”最优解在约束之内、之外两种情况，整个问题才长成了”最大值 × 最小值”的形状：

$$\min_{x}\ \max_{\lambda \ge 0}\ L(x, \lambda)$$

里层先对付 $\lambda$：找一个”最好的、最大的”$\lambda$，大到让限制条件被满足为止；外层再对 $x$ 求最小。

接着是本节的第一个关键动作——把 $\max$ 和 $\min$ 调换次序（讲师：“我们可以把这个 max 和 min 调换一下，也是可以的”）：

$$\max_{\lambda \ge 0}\ \min_{x}\ L(x, \lambda)$$

顺序变了，做事的顺序也变了：先求内层关于原始变量的最小值，再求外层关于拉格朗日乘子的最大值。讲师明说做这个替换”是为了以后我们一会讲今天课程的方便”——今天 SVM 的推导，用的正是这个次序。（轻注：交换 $\min$ 和 $\max$ 的次序在数学上需要条件——例如凸问题等情形下两边才相等——本课视频没有展开这一层，这里按讲师的处理直接采用。）

上次的优化问题和它的拉格朗日函数

接着回顾上次课的成果（详见《最大间隔》一节）：两组数据要分开，能分开的线有无数条，要找间距最大的那条。间距 $= 2/\Vert w\Vert$，所以使间距最大，相当于使 $\Vert w\Vert$ 最小；而为了数学上的方便，我们求的是模的平方最小——讲师在这里补了理由：取平方之后求导容易，$L_2$ 范数的导数好求、能得出有益的结果（乘常数、取平方都不改变最优解的位置）。整个优化问题：

$$\min_{w,\ b}\ \ \frac{1}{2}\Vert w\Vert^2 \qquad \text{s.t.} \quad y_i(w^Tx_i + b) \ge 1,\ \ i = 1, \dots, N$$

（$N$ 是样本个数——上一节记作 $m$，同一个数；讲师板书习惯说”大 N”。）约束挪成标准形 $g_i(w, b) = 1 - y_i(w^Tx_i + b) \le 0$ 之后，按上次的办法构造拉格朗日函数（上一节已经写好，乘子不用 $\lambda$、换成 SVM 惯例的 $\alpha$）：

$$L(w, b, \alpha) = \frac{1}{2}\Vert w\Vert^2 + \sum_{i=1}^{N}\alpha_i\left[1 - y_i(w^Tx_i + b)\right]$$

每一个样本一条约束，所以乘子也有 $N$ 个：$\alpha_1, \alpha_2, \dots, \alpha_N$。按本节开头的大框架，它对应：

$$\min_{w,\ b}\ \max_{\alpha_i \ge 0}\ L(w, b, \alpha)$$

为什么要变成对偶式：三个参数，一边最大一边最小

先停一下，看看眼前这个优化问题的”长相”。讲师的观察：它关于三个参数——$\alpha_i$、$w$、$b$——而且一边在求最大值、一边在求最小值。这样的优化问题很难做，不太好解。

那变成对偶形式，图什么？讲师把话说得很直白：不是为了显示数学的技巧。要做的事情是——把 $w$ 和 $b$ 的问题，全部用 $\alpha$ 去代替。这样一来，优化就只关于 $\alpha$ 这一类参数，减少了需要优化的数量。这就是对偶化的全部动机。

第一步：对 w 求导置零

现在动手。对 $L$ 的第一项，$\frac{1}{2}\Vert w\Vert^2$ 是 $w$ 的模平方——对 $w$ 求导，模平方直接吐出 $w$ 本身。第二项里与 $w$ 相乘的是 $x_i$，前面还挂着 $y_i$ 和 $\alpha_i$，要对 $i$ 连加。求导置零：

$$\frac{\partial L}{\partial w} = w - \sum_{i=1}^{N}\alpha_i y_i x_i = 0$$

于是得到本节第一条关键关系式：

$$w = \sum_{i=1}^{N}\alpha_i y_i x_i$$

最优的 $w$，是全部训练样本的线性组合，组合系数是 $\alpha_i y_i$。看一眼量纲就放心：$x$ 是向量，$y$ 和 $\alpha$ 都是标量（常量），标量乘向量再连加，出来还是向量——$w$ 本来就应该是向量。

（记号插曲：讲师板书时把每个样本的乘子写成上角标 $\alpha^{(i)}$——他的原话是”大部分的公式、大部分的书里边都是用下角标，但是我这里边一直上角标，大家统一一下”。本讲义沿用全课统一的下标记号 $\alpha_i$，与上一节一致，意思相同。）

第二步：对 b 求导置零

线性函数是 $w^Tx_i + b$ 的形式。$L$ 里跟 $b$ 有关的项：$y_i$ 要乘上 $b$、$\alpha_i$ 也要乘上 $b$，然后对 $i$ 连加。求导置零的结果干脆利落：

$$\sum_{i=1}^{N}\alpha_i y_i = 0$$

注意这一步的副作用——$b$ 从问题里消失了（讲师：“那 b 已经消失了”）。$b$ 一消失，$w$ 就可以完全用刚才的形式替代：整个 $L$ 里，将不再有独立的 $w$ 和 $b$。

第三步：代回展开（初学者可以跟着走一遍）

这一步公式繁琐。讲师特意放慢了节奏：“因为很多还是有初学的同学……我还是希望给大家从头再写一遍；已经推导过、知道很清晰的同学，可以把这段跳过，这是没什么问题的。”

先把记号备齐。模平方就是转置自乘：$\Vert w\Vert^2 = w^Tw$。把 $w = \sum_i \alpha_i y_i x_i$ 代进去，一列乘一行：

$$\frac{1}{2}\Vert w\Vert^2 = \frac{1}{2}\left(\sum_{i=1}^{N}\alpha_i y_i x_i\right)^{T}\left(\sum_{j=1}^{N}\alpha_j y_j x_j\right) = \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_j y_i y_j (x_i^Tx_j)$$

（两个连加相乘，左边用 $i$、右边就得换个字母用 $j$，把它们区分开——最后每个 $i$ 都要跟每个 $j$ 配一遍。）

这里有个点乘记号的约定，讲师专门停下来讲：乘出来的东西里，$\alpha$ 和 $y$ 全是标量，只有 $x$ 是向量——所以 $x_i$ 乘 $x_j$，实际上是 $x_i^T x_j$（转置点乘），乘完是一个实数。“我们可以写成 $x_i^T x_j$ 的形式，但为了简洁就不写这样的形式了——写成 $x_i x_j$ 的时候，大家心里知道是两个向量的点乘就可以。”

第二块，把求和项 $\sum_i \alpha_i[1 - y_i(w^Tx_i + b)]$ 拆开：

$$\sum_{i=1}^{N}\alpha_i - \sum_{i=1}^{N}\alpha_i y_i (w^Tx_i) - b\sum_{i=1}^{N}\alpha_i y_i$$

三件事同时发生：

1. 第一块 $\sum_i \alpha_i$ 原样保留；
2. 中间块的 $w$ 再代一次 $w = \sum_j \alpha_j y_j x_j$，得到 $\sum_i\sum_j \alpha_i\alpha_j y_i y_j (x_i^Tx_j)$——和模平方展开出来的那一大块，一模一样（讲师：“这一大块和这一大块又是相等的”）；
3. 尾巴上的 $b\sum_i \alpha_i y_i$：第二步已经求出 $\sum_i \alpha_i y_i = 0$，所以这一项是 $b \times 0$——整块直接消掉（讲师：“b 乘上 0，这部分都等于 0，直接给它消掉”）。

最后合并：模平方贡献 $\frac{1}{2}$ 份二次型，中间块减掉 $1$ 份二次型，两处相等所以净剩 $-\frac{1}{2}$ 份：

$$L(\alpha) = \sum_{i=1}^{N}\alpha_i - \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_j y_i y_j (x_i^Tx_j)$$

i 和 j 到底在加什么：写程序最容易看出来

公式里 $\sum_i\sum_j$ 写起来紧凑，具体在加什么？讲师当场展开了：“就变成了 $\alpha_1$ 乘 $\alpha_1$、$\alpha_1$ 乘 $\alpha_2$、$\alpha_1$ 乘 $\alpha_3$，一直到 $\alpha_1$ 乘 $\alpha_N$……如果我们写程序呢，就特别容易看出来”——$i$ 从 1 到 $N$ 扫一遍、$j$ 也从 1 到 $N$ 扫一遍，每一个 $(i, j)$ 组合都乘一次，最后统统累加。拿两个样本的真数据走一遍：

# 双重求和到底在加什么: 两样本逐项展开 (讲师: "写程序特别容易看出来")
X = [1.0, -1.0]    # 两个一维样本
y = [1, -1]        # 标签
alpha = [0.5, 0.5] # 一组乘子

total = 0.0
for i in range(2):
    for j in range(2):
        term = alpha[i] * alpha[j] * y[i] * y[j] * (X[i] * X[j])
        total += term
        print(f"i={i+1}, j={j+1}: 项 = {alpha[i]:.2f}*{alpha[j]:.2f}*{y[i]:+d}*{y[j]:+d}*({X[i]:+g}*{X[j]:+g}) = {term:+.4f}")

print()
print(f"双重求和 = {total:.4f}")
print(f"对偶目标 = sum(alpha) - 1/2 * 双重求和 = {sum(alpha):.2f} - {0.5 * total:.4f} = {sum(alpha) - 0.5 * total:.4f}")

i=1, j=1: 项 = 0.50*0.50*+1*+1*(+1*+1) = +0.2500
i=1, j=2: 项 = 0.50*0.50*+1*-1*(+1*-1) = +0.2500
i=2, j=1: 项 = 0.50*0.50*-1*+1*(-1*+1) = +0.2500
i=2, j=2: 项 = 0.50*0.50*-1*-1*(-1*-1) = +0.2500

双重求和 = 1.0000
对偶目标 = sum(alpha) - 1/2 * 双重求和 = 1.00 - 0.5000 = 0.5000

四个 $(i,j)$ 组合各算一遍：两个正标签同类相乘得正、正负标签异类相乘 $y_iy_j = -1$ 但 $x_ix_j$ 也是 $-1$，负负得正——四项全是 $+0.25$，总和 $1.0$。对偶目标 $= 1 - 0.5 = 0.5$。公式里的双重 $\sum$，就是这个双重 for 循环。

最终形式：SVM 的对偶问题

把整个逻辑串起来（讲师的收官叙事）：

1. 原问题是 $\min_{w,b}\max_{\alpha_i \ge 0} L(w, b, \alpha)$；
2. 调换次序——先把内层关于 $w$、$b$ 的最小值求出来：求导置零给出两个条件（$w = \sum_i \alpha_i y_i x_i$ 与 $\sum_i \alpha_i y_i = 0$）；
3. 代回：$w$ 和 $b$ 全部变成 $\alpha$；
4. 剩下的问题只有一件事——怎么调 $\alpha$，使整个 $L$ 最大：

$$\max_{\alpha}\ \ \sum_{i=1}^{N}\alpha_i - \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_j y_i y_j (x_i^Tx_j)$$

$$\text{s.t.} \quad \sum_{i=1}^{N}\alpha_i y_i = 0, \qquad \alpha_i \ge 0,\ \ i = 1, \dots, N$$

约束只剩两条，来历都要记牢：$\alpha_i \ge 0$ 是拉格朗日乘子处理不等式约束的本性（不等式的乘子必须非负）；$\sum_i \alpha_i y_i = 0$ 是对 $b$ 求导置零的产物——代回展开全靠它清掉 $b$ 项。

讲师在这里埋了一个彩蛋：很多条件里，还会给 $\alpha$ 加一个上限——$\alpha_i \le C$，“希望 $\alpha$ 不要特别大”。他顺手点破：这”实际上就是我们已经学过的一种 regularization——给它加一个约束项”（第 9 章岭回归/LASSO 的老朋友，下一节还会回响）。如果暂时不想管这个上限，“直接就是 $\ge 0$，这也没啥问题”。

这就是把 SVM 的最大间距问题换成拉格朗日的对偶问题——讲师给的英文名：dual form of Lagrange multiplier。求出最优的 $\alpha$ 之后，$w$ 由第一步的关系式直接给出（$w = \sum_i \alpha_i y_i x_i$，全是已知量）。

对偶式在最优处兑现吗：一个能手算的完整例子

两样本、一维特征，就能把整套对偶式从头到尾走一遍。数据：$x_1 = +1$（$y_1 = +1$）、$x_2 = -1$（$y_2 = -1$）。由对称性设 $\alpha_1 = \alpha_2 = a$——等式约束 $\sum_i \alpha_i y_i = a - a = 0$ 自动满足。代入对偶目标：

$$D(a) = 2a - 2a^2$$

一个单变量抛物线，开口向下。扫描看顶点、再在顶点处对账：

# 两样本完整验证: D(a) = 2a - 2a^2, 顶点处对偶目标 = 原问题目标
import math

X = [1.0, -1.0]   # 两个一维样本
y = [1, -1]       # 标签

def dual(a):
    # 内层 min 的解: w = sum(a*y*x) = 2a (对称情形); b 的系数 sum(a*y)=0, b 不再出现
    s = 0.0
    for i in range(2):
        for j in range(2):
            s += a * a * y[i] * y[j] * (X[i] * X[j])
    return 2 * a - 0.5 * s, 2 * a

print("D(a) = 2a - 2a^2  (两样本 x=+1/-1, 对称设 a1=a2=a)")
print(f"{'a':>4} | {'D(a)':>6} | {'w=2a':>5}")
for a in (0.1, 0.3, 0.5, 0.7, 0.9):
    d, w = dual(a)
    print(f"{a:4.1f} | {d:6.4f} | {w:5.1f}")
print("抛物线开口向下, 顶点在 a=0.5: D 最大 = 0.5000")
print()

# ---- 顶点 a=0.5 处: 对偶目标与原问题目标对账 ----
a = 0.5
alpha = [a, a]
w = sum(alpha[i] * y[i] * X[i] for i in range(2))   # 第一步关系式恢复 w
b = 0.0                                          # 数据关于原点对称, 边界取在原点
d, _ = dual(a)
primal = 0.5 * w * w
print(f"最优 a=0.5: w = sum(a*y*x) = {w:.4f}")
print(f"对偶目标 D(0.5) = {d:.4f} ; 原问题目标 0.5*||w||^2 = {primal:.4f}  -> 相等: {math.isclose(d, primal)}")
print(f"约束验证: y1*(w*x1+b) = {y[0]*(w*X[0]+b):.4f} (>=1, 恰取等); y2*(w*x2+b) = {y[1]*(w*X[1]+b):.4f} (恰取等)")
print(f"等式约束 sum(a*y) = {alpha[0]*y[0] + alpha[1]*y[1]:.4f} (=0)")
print(f"间距 margin = 2/||w|| = {2/abs(w):.4f}")

D(a) = 2a - 2a^2  (两样本 x=+1/-1, 对称设 a1=a2=a)
   a |   D(a) |  w=2a
 0.1 | 0.1800 |   0.2
 0.3 | 0.4200 |   0.6
 0.5 | 0.5000 |   1.0
 0.7 | 0.4200 |   1.4
 0.9 | 0.1800 |   1.8
抛物线开口向下, 顶点在 a=0.5: D 最大 = 0.5000

最优 a=0.5: w = sum(a*y*x) = 1.0000
对偶目标 D(0.5) = 0.5000 ; 原问题目标 0.5*||w||^2 = 0.5000  -> 相等: True
约束验证: y1*(w*x1+b) = 1.0000 (>=1, 恰取等); y2*(w*x2+b) = 1.0000 (恰取等)
等式约束 sum(a*y) = 0.0000 (=0)
间距 margin = 2/||w|| = 2.0000

三件事在顶点同时兑现：

• 对偶 = 原始：$D(0.5) = 0.5000$，原问题目标 $\frac{1}{2}\Vert w\Vert^2 = 0.5000$，分毫不差。内层 min 已把 $w$、$b$ 消干净，外层 max 在顶点取到的，正是原问题的最优值——对偶化没有丢掉任何东西。
• $w$ 直接恢复：$w = \sum_i \alpha_i y_i x_i = 0.5 + 0.5 = 1$，决策边界 $w^Tx + b = 0$ 就是原点 $x = 0$，间距 $2/\Vert w\Vert = 2$。
• 非最优的 $\alpha$ 都更低：$a = 0.3$ 或 $0.7$ 时 $D = 0.42$，$a = 0.1$ 或 $0.9$ 时 $D = 0.18$——对偶目标被 $\max$ 顶着往顶点走，两边对称下降。

至于”给定一组 $\alpha$ 怎么系统地把这个最大化问题解出来”，下一节开头会看到一种坐标轴式的迭代解法（SMO 算法）——固定其余的 $\alpha$、一次调一个，不断循环逼近最优。

📝 动手练一练

1. 约束的来历：SVM 对偶问题的两条约束——$\alpha_i \ge 0$ 与 $\sum_i \alpha_i y_i = 0$——分别从哪里来？

2. 换组数据再走一遍：数据改成 $x_1 = +2$（$y_1 = +1$）、$x_2 = -2$（$y_2 = -1$），对称设 $\alpha_1 = \alpha_2 = a$。(1) 写出对偶目标 $D(a)$ 并求顶点；(2) 验证顶点处 $D(a^*) = \frac{1}{2}\Vert w\Vert^2$；(3) 算出间距。

本章小结

• 大框架：非等式优化 = “最大 × 最小”（$\min_x\max_{\lambda\ge 0} L$）；调换次序后先求内层最小、再求外层最大——对偶式。动机不是炫技：把 $w$、$b$ 全换成 $\alpha$，减少需要优化的数量。
• 两个置零条件：$w = \sum_i \alpha_i y_i x_i$（最优 $w$ = 训练样本的线性组合，系数 $\alpha_i y_i$）；$\sum_i \alpha_i y_i = 0$（$b$ 从问题里消失）。
• 代回展开：模平方与求和项展开出的二次型恰好相等，合并剩 $-\frac{1}{2}$ 份；$b$ 项被 $\sum_i \alpha_i y_i = 0$ 整块清零 ⟹ $L(\alpha) = \sum_i \alpha_i - \frac{1}{2}\sum_i\sum_j \alpha_i\alpha_j y_i y_j (x_i^Tx_j)$。
• 点乘记号：$x_i x_j$ 默认是 $x_i^Tx_j$（转置点乘、结果是实数）——$\alpha$、$y$ 全是标量，只有 $x$ 是向量。
• 最终形式：$\max_\alpha L(\alpha)$，s.t. $\alpha_i \ge 0$、$\sum_i \alpha_i y_i = 0$——dual form of Lagrange multiplier；彩蛋：实践中常加上限 $\alpha_i \le C$，本质是 regularization。
• 数值兑现：两样本例 $D(a) = 2a - 2a^2$，顶点 $a = 0.5$ 处对偶目标 $0.5$ = 原问题目标 $0.5$，$w = 1$、间距 $2$，两条约束全过。

📋 行动清单

• 把对偶展开从头手推一遍——重点盯三处：模平方的转置自乘、两处二次型”恰好相等”、$b$ 项的清零
• 跑代码块二，看 $D(a)$ 抛物线怎么在顶点同时兑现”对偶 = 原始”与约束取等
• 想一想：$\alpha_i \le C$ 这个上限，和第 9 章岭回归/LASSO 的 $\lambda$ 是不是同一种思想（下一节继续回响）
• 预习下一节《支持向量》——$\alpha_i$ 取零与非零各对应什么样的样本（上一节结尾埋的钩，在那里揭晓）；开头还会看到解对偶问题的 SMO 算法
• 讲师预告的”为什么最大间距比较好”（《SVM 计算过程》一节用一个完整例子回答）可以先自己想一想答案

—— 小象教研组