最大间隔：把分类问题变成优化问题

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

前三节把拉格朗日乘子法从头到尾搭了一遍——等式约束、不等式约束、KKT 条件。为什么花这么大力气做这件事？讲师开宗明义：我们所有构造的这些问题，就是为了下面的实际情况。这个”实际情况”就是 SVM（支持向量机）的核心思想——最大间隔（Max Margin）。这一节会看到：一堆数据点要分成两类，能分开的线有无数条，怎么从数学上挑出”最好的那一条”——最后把它变成一个刚好能用上一节工具的优化问题。

💡 核心导读

• 换一种写法：直线方程从 $y = \theta_0 + \theta_1 x_1 + \theta_2 x_2$ 换成 SVM 惯例的 $w^T x + b = 0$；向量 $w$ 恰好是这条线的法向量。
• 聪明的构造：标签取 $\lbrace -1, +1\rbrace$（不用 $\lbrace 0, 1\rbrace$），于是 $y_i(w^T x_i + b)$ 一个乘积就能判断分对分错——正正得正、负负得正。
• 等比缩放：把离线最近的点放到 $w^T x + b = \pm 1$ 两条边界线上，分类条件强化成 $y_i(w^T x_i + b) \ge 1$。
• 间距公式：两条边界线之间的距离 $\text{margin} = 2/\Vert w\Vert$——间距最大，等价于 $\Vert w\Vert$ 最小。
• 落地：$\min \frac{1}{2}\Vert w\Vert^2$ s.t. $y_i(w^T x_i + b) \ge 1$——上一节准备好的不等式优化工具，马上用上。

先把直线的方程换一种写法

在高维空间里把数据分成两类的时候，经常会出现这样的情况：同时满足条件的线不止一条。线的上面是一个区域、下面是一个区域，任何一条能把两类点各归各区的线都算数。所以第一步，先把线的方程重新描述一下。

我们以前用的表示方法是 $y = \theta_0 + \theta_1 x_1 + \theta_2 x_2$。从今天起换一种结构，写成：

$$w^T x + b = 0$$

（讲师的说法：“以前我们用 $\theta$ 和 $\theta_0$，现在因为 SVM 都用这个系数表示，那我们也用这个”——大部分书也用 $w$ 代表权重。这个写法的实质，是把输入和输出都放进同一个向量里，让这组向量满足一个等于零的关系。）$w^T x + b$ 大于 0，代表线上面那部分区域；小于 0，代表下面那部分；等于 0，就是中间这条线本身。

拿一个具体例子换算一遍。$y = 2x + 3$：令 $x = 0$ 得 $y = 3$、令 $y = 0$ 得 $x = -3/2$，两点一画，这条红线就出来了。把它改写成等于零的形式：

$$2x - y + 3 = 0 \quad\Longleftrightarrow\quad \underbrace{[2,\ -1]}_{w^T}\begin{bmatrix}x \\ y\end{bmatrix} + 3 = 0$$

这里藏着一个非常重要的几何事实：$w = (2, -1)$ 这个向量，垂直于这条线。拿线的方向向量 $(1, 2)$ 来验：$2\times 1 + (-1)\times 2 = 0$，点积为零，垂直。再换一条线试试：$y = -\frac{1}{2}x + 1$ 改写成 $-\frac{1}{2}x - y + 1 = 0$，$w = (-\frac{1}{2},\ -1)$，与这条线的方向 $(2, -1)$ 点积 $(-\frac{1}{2})\times 2 + (-1)\times(-1) = 0$——仍然垂直。（同一条线的方程整体乘 $-1$，$w$ 跟着反向，垂直关系不变——上一节 $h$ 与 $-h$ 的老提醒。）

一句话确认：线性函数 $w^T x + b = 0$ 里，$w$ 代表这条线的法线方向。二维里它是一条线；到了高维空间，就是高维空间里的一个”面”——超平面（Hyperplane）：二维是线、三维是面、更高维统称超平面。

用一个乘积判断分对还是分错

数据还是老样子：$x_1 \to y_1,\ \dots,\ x_N \to y_N$，$x$ 属于 $n$ 维的高维空间；$y$ 是二分类的标签。这里有一个刻意的约定：不用 $\lbrace 0, 1\rbrace$，用 $\lbrace -1, +1\rbrace$ 代表两类——为什么这么换，马上就能看到。

给定一个 $x$，拿 $w^T x + b$ 一算：大于 0，预测 $y = +1$；小于 0，预测 $y = -1$。那某个 $x_i$ 到底被分对了还是分错了？讲师构造了一个非常聪明的函数：

$$y_i \cdot (w^T x_i + b)$$

只看这个乘积的符号：大于 0，分对了（correctly classified）；小于 0，分错了（wrong classified）。道理就藏在 $\pm 1$ 里：如果 $w^T x_i + b > 0$（预测 $+1$）而真实的 $y_i$ 恰好也是 $+1$，正正得正；如果 $w^T x_i + b < 0$（预测 $-1$）而 $y_i = -1$，负负得正——只要分对，乘积必是正的；分错，一正一负，乘积必是负的。这就是标签用 $\lbrace -1, +1\rbrace$ 而不用 $\lbrace 0, 1\rbrace$ 的原因：换上这套标签，“分对分错”才装得进一个乘积里。

于是回到开场的局面：能把这些点完整分成两部分的线，经常有多种可能——讲师在黑板上画了 A、B、C 三条线，每一条都能完美地分开。那问题自然来了：既然都能满足条件，怎么去选择一个最好的线？这就是我们接下来要构造的具体问题。

最大的边界：把最近的点放到 ±1 上

讲师的板书是四个点：两个黄色点是一类，两个绿色点是一类。要找一条 $w^T x + b = 0$，使两类之间的间距（margin）最大——注意一个细节：每一个类别，都至少有一个数据落在这个边界之上。从直觉上看，有最大边界的那条线，就是最好的线；在中间随便再画一条别的线，肯定不如它。

那怎么把”间距”变成能算的东西？先解决一个尺度问题。任何一个点，只要在线上面，$w^T x + b$ 就大于 0；在线下面，就小于 0——但这个值本身可大可小。而优化间距的时候，这个距离无论多大、多小，都可以整同比地进行放缩：把 $w$ 和 $b$ 一起乘上同一个常数，线本身不动（上下的区域划分完全不变），变的只是函数值的刻度。那就干脆把刻度定死——让离线最近的那些点，恰好落在 $w^T x + b = \pm 1$ 这两条线上。

于是画面变成三条平行线：$w^T x + b = +1$ 一条、$w^T x + b = -1$ 一条、$w^T x + b = 0$ 在正中间。分类条件跟着强化：

$$y_i \cdot (w^T x_i + b) \ge 1$$

含义是：所有的数据，要么恰好在这两条边界线上，要么在边界线之外——不但分对，还要离分界线有一段安全距离。

间距到底有多大

现在算这两条边界线之间的距离。设间距对应的位移是 $\lambda$：从下边界上的一个点 $x_1$ 出发，沿着 $w$ 的方向（上一节刚确认过，$w$ 就是这条线的法线方向）走一段，落到上边界的点 $x_2$ 上：

$$x_2 = x_1 + \lambda w$$

两个点各自身在边界上，所以：

$$w^T x_1 + b = -1 \qquad w^T x_2 + b = +1$$

把 $x_2 = x_1 + \lambda w$ 代入第二个式子并展开：

$$w^T x_1 + \lambda\, w^T w + b = +1$$

第一项和第三项合起来正是 $w^T x_1 + b = -1$，代入：

$$-1 + \lambda\, \Vert w\Vert^2 = +1 \quad\Longrightarrow\quad \lambda\, \Vert w\Vert^2 = 2 \quad\Longrightarrow\quad \lambda = \frac{2}{\Vert w\Vert^2}$$

（$w^T w$ 就是 $w$ 的模的平方。）而间距本身就是这个位移向量的模：

$$\text{margin} = \Vert x_2 - x_1\Vert = \Vert \lambda w \Vert = \lambda \Vert w \Vert = \frac{2}{\Vert w\Vert}$$

间距 $= 2/\Vert w\Vert$，每一侧的半间距是 $1/\Vert w\Vert$。$\Vert w\Vert$ 越大，间距越小；$\Vert w\Vert$ 越小，间距越大。

方法论旁注：很多书（包括不同人讲的课）算间距用的是”点到直线的距离”——那也是可以的；但讲师自己的路数是上面这个”从一个边界点沿 $\lambda w$ 走到另一个边界点”的构造，他自己觉得这种方式更容易理解一点。

拿 $y = 2x + 3$（即 $2x - y + 3 = 0$，$w = (2, -1)$、$b = 3$）把这套推导数值过一遍：

# ---- 讲师的间距推导: 数值验证 margin = 2/||w|| ----
# 直线 y = 2x + 3, 即 2x - y + 3 = 0:  w = (2, -1), b = 3
import math

w1, w2, b = 2.0, -1.0, 3.0
norm = math.sqrt(w1 ** 2 + w2 ** 2)
print(f"直线 2x - y + 3 = 0: w = (2, -1), b = 3, ||w|| = {norm:.4f}")
print(f"法向量检查: w·(1,2) = {w1*1.0 + w2*2.0:.1f} (方向 (1,2) 是直线方向, 点积为零 -> 垂直)")
print()

x1 = (0.0, 4.0)
print(f"下边界点 x1 = (0, 4): w^T x1 + b = {w1*x1[0] + w2*x1[1] + b:.1f} (应为 -1)")

lam = 2.0 / (norm ** 2)
x2 = (x1[0] + lam * w1, x1[1] + lam * w2)
print(f"lambda = 2/||w||^2 = 2/{norm**2:.0f} = {lam:.1f}")
print(f"上边界点 x2 = x1 + lambda*w = ({x2[0]:.4f}, {x2[1]:.4f}): w^T x2 + b = {w1*x2[0] + w2*x2[1] + b:.4f} (应为 +1)")
print()

d = math.sqrt((x2[0]-x1[0])**2 + (x2[1]-x1[1])**2)
print(f"间距 = |x2 - x1| = {d:.4f}")
print(f"     = lambda*||w|| = {lam:.1f} * {norm:.4f} = {lam*norm:.4f}  (= 2/||w||)")
print(f"半间距 = 1/||w|| = {1.0/norm:.4f}")

直线 2x - y + 3 = 0: w = (2, -1), b = 3, ||w|| = 2.2361
法向量检查: w·(1,2) = 0.0 (方向 (1,2) 是直线方向, 点积为零 -> 垂直)

下边界点 x1 = (0, 4): w^T x1 + b = -1.0 (应为 -1)
lambda = 2/||w||^2 = 2/5 = 0.4
上边界点 x2 = x1 + lambda*w = (0.8000, 3.6000): w^T x2 + b = 1.0000 (应为 +1)

间距 = |x2 - x1| = 0.8944
     = lambda*||w|| = 0.4 * 2.2361 = 0.8944  (= 2/||w||)
半间距 = 1/||w|| = 0.4472

位移一步到位：$x_1 = (0, 4)$ 贴在下边界（$w^T x_1 + b = -1$），沿 $\lambda w = 0.4\times(2, -1)$ 一走，$x_2 = (0.8, 3.6)$ 精确落在上边界（$+1$，分毫不差）。间距两种算法——直接量 $|x_2 - x_1|$、或者 $\lambda\Vert w\Vert$——都得到 $0.8944 = 2/\Vert w\Vert$。

把分类问题变成优化问题

有了 $\text{margin} = 2/\Vert w\Vert$，开场的 A/B/C 之问就可以量化回答了——三条线都能分开同一组点，但各自的间距不同：

# ---- 三条线都能分开, 哪条最好? 算 margin ----
# 板书例: 黄色 +1 类两点, 绿色 -1 类两点
import math

pts = [((1.0, 2.0), +1), ((2.0, 1.0), +1),   # 黄色
       ((3.0, 4.0), -1), ((4.0, 3.0), -1)]    # 绿色

def margin_of(w1, w2, b, name):
    # 1) 先验证: 所有点都被分开 (y_i * (w^T x + b) > 0)
    scores = []
    for (x1, x2), y in pts:
        s = y * (w1 * x1 + w2 * x2 + b)
        scores.append(s)
    ok = all(s > 0 for s in scores)
    # 2) 等比缩放: 把最近的点 (得分最小) 放到 1 上
    m = min(scores)
    w1s, w2s, bs = w1 / m, w2 / m, b / m
    norm = math.sqrt(w1s ** 2 + w2s ** 2)
    margin = 2.0 / norm
    print(f"线 {name}: w=({w1:.0f},{w2:.0f}), b={b:.0f} -> 全部分对: {ok}, "
          f"最近点得分 {m:.0f} -> 缩放后 ||w||={norm:.4f}, margin=2/||w||={margin:.4f}")
    return margin

print("黄色 +1: (1,2), (2,1);  绿色 -1: (3,4), (4,3)")
print()
mA = margin_of(-1.0, -1.0, 5.0, "A(居中)")
mB = margin_of(-1.0, -1.0, 4.0, "B(偏一侧)")
mC = margin_of(-1.0, -2.0, 6.0, "C(斜着)")
print()
print(f"margin 对比: A={mA:.4f} > B={mB:.4f} > C={mC:.4f}")
print("三条线都能把两类完美分开, 但 A 的间距最大 —— 直觉上'中间那条'最好")

黄色 +1: (1,2), (2,1);  绿色 -1: (3,4), (4,3)

线 A(居中): w=(-1,-1), b=5 -> 全部分对: True, 最近点得分 2 -> 缩放后 ||w||=0.7071, margin=2/||w||=2.8284
线 B(偏一侧): w=(-1,-1), b=4 -> 全部分对: True, 最近点得分 1 -> 缩放后 ||w||=1.4142, margin=2/||w||=1.4142
线 C(斜着): w=(-1,-2), b=6 -> 全部分对: True, 最近点得分 1 -> 缩放后 ||w||=2.2361, margin=2/||w||=0.8944

margin 对比: A=2.8284 > B=1.4142 > C=0.8944
三条线都能把两类完美分开, 但 A 的间距最大 —— 直觉上'中间那条'最好

三条线全都把两类完美分开（每一行都先验了”全部分对: True”），但 A 的间距 $2.8284$ 最大——直觉在此兑现成数字。所以整个问题变成：在所有能把数据分开的线里，找间距最大的那条。两个条件写在一起：

• 约束：所有数据被正确分类、且在边界之外——$y_i(w^T x_i + b) \ge 1$（$i = 1, \dots, m$）；
• 目标：间距最大——$\max\ 2/\Vert w\Vert$。

最大化 $2/\Vert w\Vert$，等价于最小化 $\Vert w\Vert$，也等价于最小化 $\frac{1}{2}\Vert w\Vert^2$（乘常数、取平方都不改变最优解的位置；带上 $\frac{1}{2}$ 是让后面求导干净）。这就是大家最常用的、SVM 所要优化的函数：

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

一个机器学习的分类问题，就这样变成了一个完整的优化问题。而且它的约束恰好是不等式——上一节刚准备好的工具马上能用。把约束挪成标准形式 $g_i \le 0$：

$$g_i(w, b) = 1 - y_i(w^T x_i + b) \le 0$$

按上一节的办法构造拉格朗日函数（关于 $w$ 和一串乘子的函数）：

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

（乘子这里不用 $\lambda$ 了——SVM 的惯例记号是 $\alpha_i$，讲师顺势换了名字：“我们也就换个名叫 $\alpha_i$”。）接下来怎么解？对 $w$ 求导、同时对所有的 $\alpha_i$ 求导，置零——注意 $w$ 是一个向量，“等于零”是等于一串零（每个分量都是零）。具体怎么解，下一节详细展开；这里先埋一个钩子：$\alpha_i = 0$ 的时候是什么情况？$\alpha_i \ne 0$ 的时候又是什么情况？——它们都能精确地对应回分类问题本身，下一章揭晓。

讲师的收尾把这三讲串成了一句完整的话：从数学的根子上、最底层，了解整个优化——尤其是带限制条件的优化，分等式的和不等式的，中间给的是特别清晰的几何例子；而机器学习里的最大边界问题，通过刚才构造出来的边界，变成了一个完整的优化问题；优化问题怎么解？通过拉格朗日乘子去解。下一节课，就把这两点结合到一起。

📝 动手练一练

1. ±1 的用意：为什么二分类标签要用 $\lbrace -1, +1\rbrace$ 而不是 $\lbrace 0, 1\rbrace$？请用”判断分对分错”的那个乘积构造说明。如果用 $\lbrace 0, 1\rbrace$，这个构造还成立吗？

2. 手算间距：设 $w = (3, 4)$、$b = 5$。(1) 两条边界线 $w^T x + b = \pm 1$ 之间的间距是多少？(2) 下边界上有一点 $x_1 = (1, y_1)$，求 $y_1$；(3) 按讲师的构造求 $\lambda$、算出 $x_2 = x_1 + \lambda w$，并验证 $w^T x_2 + b = +1$。

本章小结

• 方程换装：$y = \theta_0 + \theta_1 x_1 + \theta_2 x_2$ 换成 $w^T x + b = 0$（SVM 惯例记号）；$w$ 是法向量、垂直于这条线；高维空间里线推广为超平面（Hyperplane）。
• 聪明构造：标签 $\lbrace -1, +1\rbrace$，$y_i(w^T x_i + b) > 0$ 分对、$< 0$ 分错——正正得正、负负得正。
• 等比缩放：$w$、$b$ 同乘常数，线与区域划分不变；把最近的点放到 $\pm 1$ 边界上，条件强化为 $y_i(w^T x_i + b) \ge 1$——要么在线上，要么在线外。
• 间距公式：$x_2 = x_1 + \lambda w$、$\lambda = 2/\Vert w\Vert^2$ ⟹ margin $= \lambda\Vert w\Vert = 2/\Vert w\Vert$，半间距 $1/\Vert w\Vert$；A/B/C 三条能分开的线里，间距最大的是”中间那条”。
• 优化落地：$\min \frac{1}{2}\Vert w\Vert^2$ s.t. $y_i(w^T x_i + b) \ge 1$；约束改写成 $1 - y_i(w^T x_i + b) \le 0$ 后，拉格朗日函数 $L = \frac{1}{2}\Vert w\Vert^2 + \sum\alpha_i[1 - y_i(w^T x_i + b)]$——对 $w$（等于一串零）与所有 $\alpha_i$ 求导置零，下一节解。
• 埋钩：$\alpha_i = 0$ 与 $\ne 0$ 各对应什么情况，能精确对应回分类问题——下一章揭晓。

📋 行动清单

• 把 $y = -\frac{1}{2}x + 1$ 改写成 $w^T x + b = 0$ 的形式，写出 $w$，并验证 $w$ 与线方向垂直
• 自己重推一遍 $\lambda = 2/\Vert w\Vert^2 \Rightarrow \text{margin} = 2/\Vert w\Vert$，再用 $w = (3, 4)$ 手算间距
• 跑代码块一，把 C 线换成自己设计的一条”歪线”，看 margin 如何进一步变小
• 用一句话说清：为什么等比缩放之后，“分对”可以升级成”$\ge 1$”
• 预习下一节《拉格朗日对偶问题》——$L(w, b, \alpha)$ 怎么解、$\alpha_i$ 的零与非零意味着什么，都在那里展开

—— 小象教研组