SVM 计算过程：一笔到底算完，再走进核方法

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

前三节把 SVM 的理论全部搭好了：最大间隔、对偶形式、支持向量。这一节讲师做了一件最踏实的事——拿出一个真正的 SVM 问题，从头到尾用手算完：先用”高中数学”直观地解一遍，再用对偶形式解一遍，两条路到达同一个答案。而算完之后的追问才是真正的压轴：笔算都能解，那我们搞对偶形式到底是为了什么？——答案藏在对偶形式的长相里：它每一块都是内积，而内积，正是通往核方法（处理线性不可分数据）的那扇门。

💡 核心导读

• 直观解法：三点例 (3,3)、(4,3)、(1,1)，消掉 $b$、代入消元、求导置零——高中数学解出最优边界。
• 对偶解法：把例子代进对偶形式，展开双重求和、用约束消元、分 case 试探，解出 $\alpha^* = (1/4,\ 0,\ 1/4)$。
• 殊途同归：对偶解恢复出 $w = (1/2, 1/2)$、$b = -2$，与直观解分毫不差；$\alpha_2 = 0$——$x_2$ 不是支持向量。
• 对偶的真正红利：整个对偶形式里，数据只以内积 $x_i^Tx_j$ 出现——把它换成核函数 $K(x_i, x_j)$，就得到 Kernel 方法。
• 核方法初见：二维里怎么都分不开的四组点，用多项式核映射到三维，一个平面干干净净分开。

一个手算可解的 SVM：三点例

讲师开场先抛出那个悬了两节的问题——求最大边界背后的直觉到底是什么——然后话锋一转：SVM 很难算，“这是我不记得是哪本书上的例子，我觉得挺好的，通过一个例子可以给大家更多的理解”。数据三个点：

• 正类（$y = +1$）：$x_1 = (3, 3)$、$x_2 = (4, 3)$
• 负类（$y = -1$）：$x_3 = (1, 1)$

画在平面上，两类隔着一大片空地。讲师先给了直觉预告：离边界最近的点，$\alpha$ 要大于 0；而绿色的 $x_2$，“大家能想象得到，它还不太可能在边界上”。这是一个特别简单的问题——我们自己就可以把边界算出来。当然，不能就这么糊弄过去：我们要认认真真地把它算出来。

直观解法：高中数学就够了

先不走对偶，按定义来。边界最大 $\Rightarrow$ 模最小 $\Rightarrow$ 优化 $\frac{1}{2}\Vert w\Vert^2$。二维里 $\Vert w\Vert^2 = w_1^2 + w_2^2$。三个约束逐点写出来（把数代进去要 $\ge 1$ 或 $\le -1$）：

$$3w_1 + 3w_2 + b \ge 1 \qquad 4w_1 + 3w_2 + b \ge 1 \qquad w_1 + w_2 + b \le -1$$

第一个技巧：消掉 $b$。把第三式两边取负（$w_1 + w_2 + b \le -1 \Rightarrow -w_1 - w_2 - b \ge 1$），再与第一式相加——$b$ 和 $-b$ 正负约掉，$3w_1 - w_1 = 2w_1$、右端 $1 + 1 = 2$（讲师的口算：“1 减负 1 是 2”）：

$$w_1 + w_2 \ge 1$$

第二个技巧：代入消元。最优解一定贴住 $w_1 + w_2 = 1$（和一旦超过 1，平方和只会更大），于是 $w_2 = 1 - w_1$，目标变成单变量：

$$w_1^2 + (1-w_1)^2 = 2w_1^2 - 2w_1 + 1$$

（讲师：“这就是普通的高中数学，大家不要有什么问题。“）求导置零：$4w_1 - 2 = 0 \Rightarrow w_1 = \frac{1}{2}$；由对称性 $w_2 = \frac{1}{2}$。代回第一式：$\frac{3}{2} + \frac{3}{2} + b = 1 \Rightarrow b = -2$。最优超平面：$\frac{1}{2}x_1 + \frac{1}{2}x_2 - 2 = 0$。 用代码验一遍账：

# 直观解 w=(1/2,1/2), b=-2 验证三约束
import math

w_opt = (0.5, 0.5)
b_opt = -2.0
X = [(3, 3), (4, 3), (1, 1)]
y = [1, 1, -1]

print("直观解 w=(1/2,1/2), b=-2 验证三约束:")
for i in range(3):
    f = y[i] * (w_opt[0]*X[i][0] + w_opt[1]*X[i][1] + b_opt)
    print(f"  x{i+1}{X[i]} (y={y[i]:+d}): y*(w*x+b) = {f:.4f}")
print(f"  超平面: 0.5*x1 + 0.5*x2 - 2 = 0")
print(f"  margin = 2/||w|| = {2/math.sqrt(w_opt[0]**2 + w_opt[1]**2):.4f}")

直观解 w=(1/2,1/2), b=-2 验证三约束:
  x1(3, 3) (y=+1): y*(w*x+b) = 1.0000
  x2(4, 3) (y=+1): y*(w*x+b) = 1.5000
  x3(1, 1) (y=-1): y*(w*x+b) = 1.0000
  超平面: 0.5*x1 + 0.5*x2 - 2 = 0
  margin = 2/||w|| = 2.8284

$x_1$、$x_3$ 恰好压在边界上（函数间隔 = 1），$x_2$ 在边界外老远（1.5）。到此为止，直观解完成了使命——但讲师紧接着抛出本节的灵魂设问：“我们直接用这种笔算的形式也可以算，那我们搞那些特别复杂的对偶形式，是为了什么？” 先按下不表，把对偶这条路也走完。

对偶解法：把例子代进去

对偶形式（上一节的成果）：$\max_\alpha\ \sum_i\alpha_i - \frac{1}{2}\sum_i\sum_j \alpha_i\alpha_j y_i y_j (x_i^Tx_j)$，s.t. $\sum_i\alpha_i y_i = 0$、$\alpha_i \ge 0$。讲师先给了一个变换自由：求 max 也可以整体取负变成求 min——“这都是可以的”，下面按 min 的口径走。

第一部分 $\sum_i\alpha_i$，三个数据就是 $\alpha_1 + \alpha_2 + \alpha_3$，没有悬念。第二部分才是重头戏，双重求和逐项展开。先算 (1,1) 项：$\alpha_1^2 \cdot y_1y_1 \cdot x_1^Tx_1$——$y_1y_1 = 1$；$x_1^Tx_1 = 3\times3 + 3\times3 = 18$。

这里讲师插了一个对称性小课：拿 $a, b, c$ 三个数演示 $(a+b+c)(a+b+c)$ 的展开——真正的不同项只有 $a^2, b^2, c^2$，而每一个交叉项（$ab$、$ac$、$bc$）都有一个对称的孪生兄弟。所以双重求和里，$\alpha_1\alpha_2$ 这种项会出现两次——$(1,2)$ 一次、$(2,1)$ 一次。接着逐项算内积：

$$x_1^Tx_1 = 18,\quad x_2^Tx_2 = 25,\quad x_3^Tx_3 = 2,\quad x_1^Tx_2 = 21,\quad x_1^Tx_3 = 6,\quad x_2^Tx_3 = 7$$

注意 $x_1^Tx_3$ 和 $x_2^Tx_3$ 这两项前面挂着 $y_iy_j$：$x_3$ 是负类，所以 $y_1y_3 = y_2y_3 = -1$——“因为 3 的类别跟 1、2 不一样，两个 y 相乘一定是负一”。全部加起来：

$$L = \frac{1}{2}\left[18\alpha_1^2 + 25\alpha_2^2 + 2\alpha_3^2 + 42\alpha_1\alpha_2 - 12\alpha_1\alpha_3 - 14\alpha_2\alpha_3\right]$$

（交叉项 $\times 2$：$21\times2 = 42$、$-6\times2 = -12$、$-7\times2 = -14$。）

约束也具体化：$\alpha_1 + \alpha_2 - \alpha_3 = 0$（$\alpha_3$ 的 $y$ 是负的），即 $\alpha_3 = \alpha_1 + \alpha_2$。拿它把 $\alpha_3$ 整个替换掉（讲师：“如果有三个 $\alpha$，可以用 SMO 算法在三维空间里不断固定一个、调整另外两个——数值方法、编程序。但我们这边没法编程序，就用代数把 $\alpha_3$ 消掉”）：

$$S(\alpha_1, \alpha_2) = 4\alpha_1^2 + \frac{13}{2}\alpha_2^2 + 10\alpha_1\alpha_2 - 2\alpha_1 - 2\alpha_2$$

（讲师：“这个算过好多遍了，应该不会错。”）

先试驻点：$\partial S/\partial\alpha_1 = 8\alpha_1 + 10\alpha_2 - 2 = 0$，$\partial S/\partial\alpha_2 = 13\alpha_2 + 10\alpha_1 - 2 = 0$，联立解出：

$$\alpha_1 = \frac{3}{2}, \qquad \alpha_2 = -1$$

$\alpha_2 = -1 < 0$——违反约束，这个解不对。这正是上一章 KKT 讲过的情形（一维例子 $\lambda^* \in \lbrace 0,\ 2b\rbrace$ 的翻版）：驻点不在可行范围内，最优解必然贴在某个边界上——要么 $\alpha_1 = 0$、要么 $\alpha_2 = 0$，“这两种肯定有一种是正确的”。分 case 测试：

• case A（$\alpha_1 = 0$）：$S = \frac{13}{2}\alpha_2^2 - 2\alpha_2$，求导 $13\alpha_2 - 2 = 0 \Rightarrow \alpha_2 = \frac{2}{13}$；
• case B（$\alpha_2 = 0$）：$S = 4\alpha_1^2 - 2\alpha_1$，求导 $8\alpha_1 - 2 = 0 \Rightarrow \alpha_1 = \frac{1}{4}$。

比较两个候选的 $S$ 值，取小的（我们在求 min）：$S(\frac{1}{4}, 0) < S(0, \frac{2}{13})$——case B 胜出。最终解：

$$\alpha^* = \left(\frac{1}{4},\ 0,\ \frac{1}{4}\right)$$

$\alpha_1, \alpha_3 > 0$、$\alpha_2 = 0$——$x_2$ 果然不是支持向量，讲师开场的直觉预告兑现。最后恢复参数：$w = \alpha_1y_1x_1 + \alpha_3y_3x_3 = \frac{1}{4}(3,3) + \frac{1}{4}(-1)(1,1) = (\frac{3}{4}-\frac{1}{4},\ \frac{3}{4}-\frac{1}{4}) = (\frac{1}{2}, \frac{1}{2})$；$b$ 由边界点反解：$y_1(w^Tx_1 + b) = 1 \Rightarrow b = 1 - 3 = -2$。全程代码对账：

# 对偶解全程: 驻点违约束 -> 分 case -> 恢复 w, b
X = [(3, 3), (4, 3), (1, 1)]   # 同一批三点数据
y = [1, 1, -1]

def S(a1, a2):
    # S(a1, a2) = 4a1^2 + 13/2 a2^2 + 10 a1 a2 - 2a1 - 2a2 (已消元 alpha3 = a1 + a2)
    return 4*a1**2 + 6.5*a2**2 + 10*a1*a2 - 2*a1 - 2*a2

print("消元后的 S(a1, a2) = 4a1^2 + 6.5a2^2 + 10a1a2 - 2a1 - 2a2")
print()
print("偏导置零的驻点: a1 = 1.5, a2 = -1.0  -> a2 = -1 < 0 违反约束!")
print()

a2_A = 2.0/13.0
print(f"case A (a1=0): 13a2 - 2 = 0 -> a2 = 2/13 = {a2_A:.4f}, S = {S(0, a2_A):.4f}")
a1_B = 0.25
print(f"case B (a2=0): 8a1 - 2 = 0 -> a1 = 1/4 = {a1_B:.4f}, S = {S(a1_B, 0):.4f}")
print(f"S(1/4, 0) = {S(a1_B, 0):.4f} < S(0, 2/13) = {S(0, a2_A):.4f} -> case B 最小, 取 a=(1/4, 0, 1/4)")
print()

alpha = [0.25, 0.0, 0.25]
w = [0.0, 0.0]
for i in range(3):
    for d in range(2):
        w[d] += alpha[i] * y[i] * X[i][d]
b = y[0] - (w[0]*X[0][0] + w[1]*X[0][1])
print(f"alpha* = {alpha}")
print(f"w* = 1/4*(3,3) + 1/4*(-1)*(1,1) = ({w[0]:.4f}, {w[1]:.4f})")
print(f"b* = y1 - w*x1 = {b:.4f}")
print("与直观解完全一致!")

消元后的 S(a1, a2) = 4a1^2 + 6.5a2^2 + 10a1a2 - 2a1 - 2a2

偏导置零的驻点: a1 = 1.5, a2 = -1.0  -> a2 = -1 < 0 违反约束!

case A (a1=0): 13a2 - 2 = 0 -> a2 = 2/13 = 0.1538, S = -0.1538
case B (a2=0): 8a1 - 2 = 0 -> a1 = 1/4 = 0.2500, S = -0.2500
S(1/4, 0) = -0.2500 < S(0, 2/13) = -0.1538 -> case B 最小, 取 a=(1/4, 0, 1/4)

alpha* = [0.25, 0.0, 0.25]
w* = 1/4*(3,3) + 1/4*(-1)*(1,1) = (0.5000, 0.5000)
b* = y1 - w*x1 = -2.0000
与直观解完全一致!

两条路，同一个答案：$w = (1/2, 1/2)$、$b = -2$，超平面 $\frac{1}{2}x_1 + \frac{1}{2}x_2 - 2 = 0$。通过对偶形式，把最好的 $\alpha$ 解出来；有了 $\alpha$，$w$ 和 $b$ 唾手可得——这就是完整的 SVM 计算过程。

对偶形式换来了什么：全是内积

现在回答那个被按下的设问。回头看对偶形式——讲师指出关键观察：每一块都写成了内积的形式。$\alpha$ 是要优化的参数，$y$ 就是正一负一，剩下的全部计算，都落在内积 $x_i^Tx_j$ 上。所以整个优化方法就变成了：怎么去求这个内积。

核函数由此登场：给它一个记号 $K(x_i, x_j)$——直接求两者的内积，再通过一个核函数映射到另外一个方向。这一步看似只是换记号，实际打开了一整个新世界——因为我们线性 SVM 有一个与生俱来的前提：数据必须线性可分（“无论要不要最大边界，数据必须可分才行”）。而有些空间里的数据根本不可分——但通过 kernel 的映射，到另外一个空间就变成可分的了。

为什么需要核：二维分不开的四组点

讲师的经典例子（课件 Note_14 同款）：紫色四个点 $(1,1), (1,-1), (-1,1), (-1,-1)$——内圈；绿色四个点 $(2,2), (2,-2), (-2,2), (-2,-2)$——外圈。紫的抱成一团缩在中间，绿的站在四角。在这个平面里，你想找一条直线把两类分开，是不可能的——直觉上的最优边界是一个圆。

解法：构造一个多项式核，把 $\mathbb{R}^2$ 映射到 $\mathbb{R}^3$：

$$(x_1, x_2)\ \to\ (z_1, z_2, z_3), \qquad z_1 = x_1^2, \qquad z_2 = \sqrt{2}\,x_1x_2, \qquad z_3 = x_2^2$$

拿数据走一遍：

# 多项式核映射: 二维不可分 -> 三维线性可分
import math

pur = [(1, 1), (1, -1), (-1, 1), (-1, -1)]   # 紫色内圈
grn = [(2, 2), (2, -2), (-2, 2), (-2, -2)]   # 绿色外圈

def phi(x1, x2):
    return (x1*x1, math.sqrt(2)*x1*x2, x2*x2)

print("多项式核映射 (x1,x2) -> (x1^2, sqrt(2)x1x2, x2^2):")
print("紫色四点:")
for x in pur:
    z = phi(*x)
    print(f"  {x} -> ({z[0]:.0f}, {z[1]:+.4f}, {z[2]:.0f})")
print("绿色四点:")
for x in grn:
    z = phi(*x)
    print(f"  {x} -> ({z[0]:.0f}, {z[1]:+.4f}, {z[2]:.0f})")
print("紫色四个点两两重合成 (1,+-1.4142, 1) 两点; 绿色重合成 (4,+-5.6569, 4) 两点")
print()

ok = all(phi(*x)[0] == 1 for x in pur) and all(phi(*x)[0] == 4 for x in grn)
print(f"分离面 z1 = 2.5: 紫色全部 z1 = 1 < 2.5, 绿色全部 z1 = 4 > 2.5 -> {'一个平面分开' if ok else 'FAIL'}")
print()

print("核技巧对账: K(x,x') = (x.x')^2 vs 三维显式内积 phi(x).phi(x'):")
pairs = [((1,1),(1,1)), ((1,1),(2,2)), ((1,-1),(2,-2)), ((1,1),(1,-1))]
for x, xp in pairs:
    dot2 = x[0]*xp[0] + x[1]*xp[1]
    K = dot2 ** 2
    zx, zxp = phi(*x), phi(*xp)
    dot3 = zx[0]*zxp[0] + zx[1]*zxp[1] + zx[2]*zxp[2]
    print(f"  x={x}, x'={xp}: K = ({dot2})^2 = {K:.4f}, phi 内积 = {dot3:.4f}, 差 = {K - dot3:.1e}")

多项式核映射 (x1,x2) -> (x1^2, sqrt(2)x1x2, x2^2):
紫色四点:
  (1, 1) -> (1, +1.4142, 1)
  (1, -1) -> (1, -1.4142, 1)
  (-1, 1) -> (1, -1.4142, 1)
  (-1, -1) -> (1, +1.4142, 1)
绿色四点:
  (2, 2) -> (4, +5.6569, 4)
  (2, -2) -> (4, -5.6569, 4)
  (-2, 2) -> (4, -5.6569, 4)
  (-2, -2) -> (4, +5.6569, 4)
紫色四个点两两重合成 (1,+-1.4142, 1) 两点; 绿色重合成 (4,+-5.6569, 4) 两点

分离面 z1 = 2.5: 紫色全部 z1 = 1 < 2.5, 绿色全部 z1 = 4 > 2.5 -> 一个平面分开

核技巧对账: K(x,x') = (x.x')^2 vs 三维显式内积 phi(x).phi(x'):
  x=(1, 1), x'=(1, 1): K = (2)^2 = 4.0000, phi 内积 = 4.0000, 差 = 0.0e+00
  x=(1, 1), x'=(2, 2): K = (4)^2 = 16.0000, phi 内积 = 16.0000, 差 = 0.0e+00
  x=(1, -1), x'=(2, -2): K = (4)^2 = 16.0000, phi 内积 = 16.0000, 差 = 0.0e+00
  x=(1, 1), x'=(1, -1): K = (0)^2 = 0.0000, phi 内积 = -0.0000, 差 = 4.4e-16

三件事在输出里同时兑现：

• 四个点映射成两个点：紫色的 $(1,1)$ 和 $(-1,-1)$ 映到同一个 $(1, \sqrt{2}, 1)$，$(1,-1)$ 和 $(-1,1)$ 映到 $(1, -\sqrt{2}, 1)$；绿色同样两两重合到 $(4, \pm 4\sqrt{2}, 4)$。重叠反而帮了忙——三维空间里，紫色全落在 $z_1 = 1$、绿色全落在 $z_1 = 4$，一个平面 $z_1 = 2.5$ 干干净净把两类分开。“二维空间里不可分的数据，用一个多项式 kernel 映射到三维空间，就是一个线性可分的问题了。”
• 核技巧（kernel trick）：注意最妙的一行对照——$\langle\phi(x), \phi(x')\rangle$ 恰好等于 $(x\cdot x')^2$。也就是说，想知道映射后三维空间里的内积，根本不用真的去算三维坐标，在二维里把 $(x\cdot x')^2$ 一乘就出来了。这就是”把内积换成核函数的值”的完整含义——对偶形式原封不动，把每个 $x_i^Tx_j$ 换成 $K(x_i, x_j)$，就完成了升级。
• 机器毛边彩蛋：最后一行 $(1,1)\cdot(1,-1)$ 数学上恰好为零（两个方向正交），机器上留着 $4.4\times10^{-16}$ 的浮点毛边——老朋友了，看清就好。

讲师的点睛总结：$x_i$ 乘 $x_j$ 本身就是一个最简单的线性 kernel——直接相乘；但它还可以变成多项式的形式，还可以变成高斯 kernel 等等。“总之的目的，就是要在另外一个空间里边，把内积形式换成核函数的一个值。“——这就是从 SVM 走向 kernel function、kernel machine 的完整例子。

Kernel Machine 与一段研究史

2000 年初，SVM 火起来正是因为它有很完整的数学表述——把一个机器学习问题变成一个完整的优化问题；而且”原来在某个空间不可分的数据，可以在高维空间里通过 kernel 的映射变成可分”。这个观察带动了一大批核函数研究：用什么样的核函数、对应什么空间、有什么特性、对某些数据分得更好还是更坏。这一族方法的延伸，得名 Kernel Machine。

讲师也给了一段诚实的当代评价：深度学习出来之后，这种方法并不一定是最优良的——现在的实际数据往往量很大，要拟合更复杂的函数关系时，也许深度神经网络会更好，“这一边的研究稍微会有一些减弱，但实际上也是一个非常好的方向”。再往前看，以后还会学到 metric learning（度量学习）——它跟 kernel 映射服从某种关系：都是给定数据、找一个函数把它映射到另外一个空间，让关系在那个空间里更明显。“在机器学习大的范畴里边，这个思想都是类似的。”

📝 动手练一练

1. 驻点为何被弃：对偶求解中，偏导置零解出 $\alpha_1 = 3/2$、$\alpha_2 = -1$，为什么这个解不能用？随后”要么 $\alpha_1 = 0$、要么 $\alpha_2 = 0$“的分 case 逻辑，理论依据是什么？

2. 核映射手算：用本节的多项式核 $(x_1,x_2)\to(x_1^2, \sqrt{2}x_1x_2, x_2^2)$，(1) 算出 $x = (3, 3)$ 映射后的三维坐标；(2) 验证 $x = (3,3)$、$x' = (2,-2)$ 这一对满足 $\langle\phi(x), \phi(x')\rangle = (x\cdot x')^2$。

本章小结

• 三点例全程手算：直观解（消 $b$ → $w_1 + w_2 \ge 1$ → 代入 $2w_1^2 - 2w_1 + 1$ → 求导 $w_1 = w_2 = 1/2$、$b = -2$）与对偶解（展开 $18/25/2/42/-12/-14$ → 消元 $S(\alpha_1,\alpha_2)$ → 驻点 $\alpha_2 = -1$ 违约束 → 分 case → $\alpha^* = (1/4, 0, 1/4)$）殊途同归。
• 支持向量兑现：$\alpha_2 = 0$——不在边界上的 $x_2$ 对 $w$ 零贡献；$w = \alpha_1y_1x_1 + \alpha_3y_3x_3$，$b$ 由边界点反解。
• 对偶的红利：对偶形式每一块都是内积 $x_i^Tx_j$——把内积换成核函数 $K(x_i, x_j)$，线性 SVM 升级为 Kernel 方法，处理线性不可分。
• 多项式核例子：$(x_1,x_2)\to(x_1^2, \sqrt{2}x_1x_2, x_2^2)$，二维不可分的内圈/外圈四点，映射后四点两两重合、一个平面 $z_1 = 2.5$ 分开；核技巧 $\langle\phi(x),\phi(x')\rangle = (x\cdot x')^2$——不用去三维，二维直接算。
• 视野：$x_i^Tx_j$ 本身就是最简单的线性核；还可换多项式、高斯核等——这一族方法的延伸叫 Kernel Machine；深度学习兴起后此方向研究减弱但仍是好方向；与 metric learning 思想同源。

📋 行动清单

• 把 $S(\alpha_1, \alpha_2)$ 的消元过程在纸上完整推一遍——从 $L = \frac{1}{2}[18\alpha_1^2 + \cdots - 14\alpha_2\alpha_3]$ 代入 $\alpha_3 = \alpha_1 + \alpha_2$ 开始
• 跑代码块二，自己加第四个点（比如 $x_4 = (5,3)$ 正类），先猜它的 $\alpha$ 是多少，再想怎么验证
• 跑代码块三，把绿色的外圈点改成 $(3,3)$ 附近，看映射后 $z_1$ 的取值怎么变、分离面还在不在
• 回想讲师开场的直觉之问——“为什么要求最大的边界”——用本节看到的稀疏性（边界只由少数点撑起）组织一遍自己的回答
• 预习下一章：贝叶斯公式——统计学习的另一半地图，从”优化视角”切换到”概率视角”

—— 小象教研组