优化方法（1）：坐标下降与前向选择

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

上一节结尾留了话：L1 范数在零点不可导，梯度下降做不出梯度，“会用其他的方法来求这个 LASSO 的优化”。这一节就兑现——介绍几种定量的计算方法。要优化的目标没变，还是上一节那个 $\min_\theta \frac{1}{2N}(\Vert X\theta-y\Vert_2^2 + \lambda\Vert\theta\Vert_1)$；变的是”怎么走”。

💡 核心导读

• 方法一：坐标下降（coordinate descent）——与梯度下降对照：一个根据梯度下降，一个根据坐标轴下降。
• 机制：固定其他所有维度，在单根坐标轴上搜到最低点 stop、固定，换下一根轴，再搜——路径走成”之”字。
• 起点是个 trick：可以从与 $y$ 相关性最大的维度开始，更有效率——但影响有限，按顺序搜照样能到。
• 方法二：前向选择（forward selection）——从最小二乘的几何出发：$y$ 在特征平面上的投影，一个方向一个方向地搭出来。
• 共同代价：一个维度一个维度地走，计算复杂度摆在那里；维度特别大时，先选谁是有学问的。

方法一：坐标下降

先摆对照：我们原先的方法叫 gradient descent，根据梯度进行下降；这个叫 coordinate descent，根据坐标轴下降。

道理非常简单。假设是二维空间，参数只有 $\theta_1$、$\theta_2$，损失函数 $J(\theta)$ 的等高线一圈圈摆在那里。我们先随便取一个起点，在给定的这个点上，看沿哪个方向值最小——比如沿 $\theta_1$ 这根轴更低，那就先沿 $\theta_1$ 走到这根轴上的最低点，stop，把这个维度的值固定住；然后换 $\theta_2$ 的方向，在 $\theta_2$ 这根轴上再搜最低点，再 stop、再固定；回过头来再搜 $\theta_1$……如此往复。走出来的路径是一个”之”字：横一步、竖一步、再横一步，可以没完地继续走下去，直到走不动为止。

一般化到 $n$ 维也是一样：$\theta$ 有 $j = 1 \sim n$ 个维度，先调整 $\theta_1$，再调整 $\theta_2$，一路到 $\theta_n$，循环往复——每次只在某一个维度上找最小值，找到了就固定，再选另一个维度继续搜。

从哪个维度开始？ 有个技巧：可以先求各个 $\theta_j$ 与 $y$ 之间的 correlation（相关度/相似度），从相似度最大的那个维度开始，使搜索更有效率。但注意讲师的原话：这样做”最后的影响是有限的”——它是个 trick，不是必需品。从 $\theta_1$ 顺着往下走、甚至随机走，也都能取到最优值。所以坐标下降的性格是：比较粗暴、比较简单，但不需要任何其他技巧。它的代价是每一个维度都要去搜索一遍。

把这套”逐轴找最低点”跑起来。先看普通最小二乘损失（$\lambda=0$），再看 LASSO 损失（$\lambda>0$，绝对值的尖角照样搜得动）：

# ---- 4 个样本, 两个特征相关 (内积 9): 坐标下降会走出看得见的"之"字 ----
X = [
    [1.0, 1.0],
    [1.0, 2.0],
    [2.0, 1.0],
    [2.0, 2.0],
]
y = [3.2, 4.8, 3.8, 6.2]

def J(t1, t2, lam):
    s = 0.0
    for row, yi in zip(X, y):
        s += (row[0] * t1 + row[1] * t2 - yi) ** 2
    s *= 0.5
    return s + lam * (abs(t1) + abs(t2))

def axis_min(t_other, axis, lam):
    # 固定另一坐标后, 轴上的损失 = 两段抛物线拼一个尖角(绝对值项)。
    # 最低点必在三个候选之一: 正半轴顶点 / 负半轴顶点 / 尖角零点 -- 逐个代入 J 挑最小。
    c = d = 0.0
    for row, yi in zip(X, y):
        xj = row[axis - 1]
        r = yi - row[2 - axis] * t_other     # 固定另一坐标后的残差
        c += xj * r
        d += xj * xj
    cand = [0.0]
    for z in (c - lam, c + lam):
        v = z / d
        if v > 1e-15 or v < -1e-15:
            cand.append(v)
    def J_axis(v):
        a, b = (v, t_other) if axis == 1 else (t_other, v)
        return J(a, b, lam)
    return min(cand, key=J_axis)

def coordinate_descent(lam, max_rounds=300):
    t1 = t2 = 0.0
    snaps = {}
    for r in range(1, max_rounds + 1):
        old = (t1, t2)
        t1 = axis_min(t2, 1, lam)
        t2 = axis_min(t1, 2, lam)
        if r in (1, 2, 3, 5, 10, 20, 50):
            snaps[r] = (t1, t2)
        if max(abs(t1 - old[0]), abs(t2 - old[1])) < 1e-12:
            return t1, t2, r, snaps
    return t1, t2, max_rounds, snaps

print("数据 (x1, x2 -> y), 两个特征相关 (内积 9):")
for row, yi in zip(X, y):
    print(f"  ({row[0]:.0f}, {row[1]:.0f}) -> {yi}")

t1, t2, r0, s0 = coordinate_descent(0.0)
print("\nlambda = 0.0 (普通最小二乘损失):")
for r, (a, b) in sorted(s0.items()):
    print(f"  轮 {r:2d}: theta = ({a:.3f}, {b:.3f})  J = {J(a, b, 0.0):.3f}")
print(f"  轮 {r0}: 收敛, theta = ({t1:.6f}, {t2:.6f})")
XTX = [[sum(X[i][a] * X[i][b] for i in range(4)) for b in range(2)] for a in range(2)]
XTy = [sum(X[i][a] * y[i] for i in range(4)) for a in range(2)]
check = [XTX[0][0] * t1 + XTX[0][1] * t2 - XTy[0], XTX[1][0] * t1 + XTX[1][1] * t2 - XTy[1]]
print(f"  验证: (X^T X)theta - X^T y = ({check[0]:.1e}, {check[1]:.1e})  <- 站在正规方程的零点上")

t1, t2, r5, s5 = coordinate_descent(0.5)
print("\nlambda = 0.5 (LASSO 损失, 同一套轴搜索照样跑得动):")
for r, (a, b) in sorted(s5.items()):
    if r in (1, 2, 3, 5, 10, 20):
        print(f"  轮 {r:2d}: theta = ({a:.3f}, {b:.3f})")
print(f"  轮 {r5}: 收敛, theta = ({t1:.6f}, {t2:.6f})  <- 比正规方程解恰好各小 0.026")

数据 (x1, x2 -> y), 两个特征相关 (内积 9):
  (1, 1) -> 3.2
  (1, 2) -> 4.8
  (2, 1) -> 3.8
  (2, 2) -> 6.2

lambda = 0.0 (普通最小二乘损失):
  轮  1: theta = (2.800, 0.380)  J = 3.158
  轮  2: theta = (2.458, 0.688)  J = 2.099
  轮  3: theta = (2.181, 0.937)  J = 1.405
  轮  5: theta = (1.775, 1.303)  J = 0.650
  轮 10: theta = (1.270, 1.757)  J = 0.149
  轮 20: theta = (1.033, 1.970)  J = 0.081
  轮 50: theta = (1.000, 2.000)  J = 0.080
  轮 129: 收敛, theta = (1.000000, 2.000000)
  验证: (X^T X)theta - X^T y = (6.6e-12, 3.6e-15)  <- 站在正规方程的零点上

lambda = 0.5 (LASSO 损失, 同一套轴搜索照样跑得动):
  轮  1: theta = (2.750, 0.375)
  轮  2: theta = (2.413, 0.679)
  轮  3: theta = (2.139, 0.925)
  轮  5: theta = (1.738, 1.286)
  轮 10: theta = (1.240, 1.734)
  轮 20: theta = (1.006, 1.945)
  轮 128: 收敛, theta = (0.973684, 1.973684)  <- 比正规方程解恰好各小 0.026

读这张路径表。“之”字：$\theta_1$ 第一步冲到 2.800（过冲），$\theta_2$ 被它拽到 0.380（欠着）；下一轮 $\theta_1$ 回落到 2.458，$\theta_2$ 升到 0.688——两个维度互相牵扯，因为这两个特征相关（内积 9）。每一步 J 都在降：3.158 → 2.099 → … → 0.080，单调往下，从不停顿。终点双保险：$\lambda=0$ 时 129 轮后精确站在正规方程的解 $(1, 2)$ 上，代回 $(X^TX)\theta - X^Ty$ 只剩 $10^{-12}$ 量级的浮点毛边；$\lambda=0.5$ 时同一套循环在 LASSO 损失上照样收敛，解变成 $(0.9737, 1.9737)$——比正规方程解恰好各小 0.026，绝对值惩罚把两个系数各削了一刀。这正是”求 LASSO 的优化”的第一种方法：不需要梯度，只要每根轴上找得到最低点。

方法二：前向选择

第二个方法叫 forward selection，前向选择。要理解它，必须记得上次课讨论最小二乘时的向量空间视角——当时讲它，就是为了给这一课打基础。

回顾一下。给定数据矩阵 $X$，它的列向量 $x_1$、$x_2$ 张成一个平面；我们希望学到的值是 $y$，但 $y$ 压根就不在 $x_1, x_2$ 构成的平面里——无论怎么线性组合都构造不出等于 $y$ 的向量。我们能求的是 $y$ 在这个平面上的投影 $\hat{y}$：它完全由 $\hat{y} = \theta_1x_1 + \theta_2x_2 + \theta_0$ 构造出来，而残差 $e = y - \hat{y}$ 必须与整个平面垂直。这正是最小二乘解的几何意义（第 8 章）。把矩阵形式写全（讲师特意把常数列也写上）：

$$\begin{bmatrix}1 & x_{11} & x_{12}\\ 1 & x_{21} & x_{22}\end{bmatrix}\begin{bmatrix}\beta_0\\ \beta_1\\ \beta_2\end{bmatrix} = \begin{bmatrix}y_1\\ y_2\end{bmatrix}$$

按列看，它说的就是 $\beta_1 x_1 + \beta_2 x_2 + \beta_0 \cdot \mathbf{1} = y$——把两个向量各自等比伸缩，再相加，凑出目标向量（省略常数列本质上是一样的）。

前向选择做的事：不是一口气求出 $\theta_1$、$\theta_2$，而是一个方向一个方向地搭。第一步，先看 $x_1$ 和 $x_2$ 哪个跟 $y$ 的关系更近；假设 $x_1$ 更近，就先在 $x_1$ 的方向上找一个合适的 $\theta_1$，让 $\theta_1x_1$ 落在 $y$ 的投影途中。做完这一步，它们之间仍然有距离。第二步，在 $x_2$ 的方向上再延伸一段 $\theta_2x_2$——最后延到的那个点，正好是 $y$ 在平面上的投影，残差最小。跑一遍（这份演示数据里 $x_1$ 与 $x_2$ 严格正交，$y$ 带着一段平面外的分量）：

# ---- 前向选择: 4 个样本, x1 与 x2 严格正交, y 带一段平面外的分量 ----
x1 = [1.0, 1.0, -1.0, -1.0]
x2 = [1.0, -1.0, 1.0, -1.0]
y = [3.1, 1.1, -0.9, -2.9]

def dot(a, b):
    return sum(u * v for u, v in zip(a, b))

def scale(v, s):
    return [s * u for u in v]

def sub(a, b):
    return [u - v for u, v in zip(a, b)]

print("数据: x1 = (1,1,-1,-1), x2 = (1,-1,1,-1) (正交), y = (3.1, 1.1, -0.9, -2.9)")
print(f"第一步 选择: <x1,y> = {dot(x1, y):.1f},  <x2,y> = {dot(x2, y):.1f}  -> 选 x1 (跟 y 关系更近)")

theta1 = dot(x1, y) / dot(x1, x1)
pred = scale(x1, theta1)
res = sub(y, pred)
print(f"第一步 投影: theta1 = {dot(x1, y):.1f} / {dot(x1, x1):.1f} = {theta1:.3f}")
print(f"  预测 = {[round(v, 1) for v in pred]},  残差 = {[round(v, 1) for v in res]}")

theta2 = dot(x2, res) / dot(x2, x2)
pred2 = [a + b for a, b in zip(pred, scale(x2, theta2))]
res2 = sub(y, pred2)
print(f"第二步 延伸: 残差与 x2 的内积 = {dot(x2, res):.1f},  theta2 = {dot(x2, res):.1f} / {dot(x2, x2):.1f} = {theta2:.3f}")
print(f"  预测 = {[round(v, 1) for v in pred2]},  残差 = {[round(v, 1) for v in res2]}")

print(f"\n验证 残差垂直于整个平面: <残差,x1> = {dot(res2, x1):.3f},  <残差,x2> = {dot(res2, x2):.3f}")
print(f"最终: y_hat = {theta1:.1f}*x1 + {theta2:.1f}*x2,  残差平方和 = {dot(res2, res2):.2f}")

数据: x1 = (1,1,-1,-1), x2 = (1,-1,1,-1) (正交), y = (3.1, 1.1, -0.9, -2.9)
第一步 选择: <x1,y> = 8.0,  <x2,y> = 4.0  -> 选 x1 (跟 y 关系更近)
第一步 投影: theta1 = 8.0 / 4.0 = 2.000
  预测 = [2.0, 2.0, -2.0, -2.0],  残差 = [1.1, -0.9, 1.1, -0.9]
第二步 延伸: 残差与 x2 的内积 = 4.0,  theta2 = 4.0 / 4.0 = 1.000
  预测 = [3.0, 1.0, -1.0, -3.0],  残差 = [0.1, 0.1, 0.1, 0.1]

验证 残差垂直于整个平面: <残差,x1> = 0.000,  <残差,x2> = -0.000
最终: y_hat = 2.0*x1 + 1.0*x2,  残差平方和 = 0.04

三处观察。选择看相关：$x_1$ 与 $y$ 的内积 8.0，$x_2$ 只有 4.0——第一步选 $x_1$，投影系数 $\theta_1 = 8/4 = 2$。延伸看残差：剩下的残差 $(1.1, -0.9, 1.1, -0.9)$ 与 $x_2$ 的内积是 4.0，$\theta_2 = 1$——搭完两步，$\hat{y} = 2x_1 + x_2$，残差 $(0.1, 0.1, 0.1, 0.1)$ 正是 $y$ 平面外的那段分量。垂直性的数值兑现：残差与 $x_1$、$x_2$ 的内积分别是 0.000 和 −0.000——数学上精确为零，机器上带 $10^{-17}$ 量级的毛边（那个 −0.000 就是毛边压出来的负零，第 8 章见过同款）。

实践注：这份演示数据里 $x_1$ 与 $x_2$ 垂直，两步投影恰好一次就落在 $y$ 的整体投影上；特征不垂直时，第二步会把第一步的落点拽偏——想精确落位，就得像坐标下降那样一轮一轮来回走。两种方法在这里悄悄接上了头。

代价与收尾

前向选择的问题也很直白：它需要一个维度一个维度地求、一个方向一个方向地走，存在计算复杂度的问题。维度比较小的时候，这是很合适的方法；维度特别大的时候，先选择哪一个、后选择哪一个，也是有学问的——要看每一个维度跟 $y$ 之间的 correlation。（本节视频到这里收尾，更多优化方法下一节继续。）

📝 动手练一练

1. 两种下降的本质区别：梯度下降和坐标下降，在”往哪儿走”这件事上有什么本质不同？对 LASSO 这种零点不可导的目标，为什么坐标下降照样能走？

2. 前向选择手算：三个样本，$x_1 = (1, 1, 2)$、$x_2 = (1, -1, 0)$（两者正交），$y = (2.5, 0.5, 1.5)$。按前向选择的步骤手算：第一步该选哪个特征？$\theta_1$ 是多少？第二步的 $\theta_2$ 呢？最终残差是多少，验证它与两个特征都垂直。

本章小结

• 定位：LASSO 的 L1 在零点不可导、梯度下降失灵——本节给出两种”用其他方法”的定量解法。
• 坐标下降：与梯度下降对照（根据梯度 vs 根据坐标轴）；固定其余维度、单轴搜到最低 stop、换轴再搜，路径走”之”字；可以从与 $y$ 相关性最大的维度起步（trick，影响有限）；粗暴、简单、不需要其他技巧。
• 数值实证：相关特征上 129 轮收敛到正规方程解 $(1, 2)$（代回只剩浮点毛边）；LASSO 损失同一套循环收敛到 $(0.9737, 1.9737)$，比正规方程解恰好各小 0.026。
• 前向选择：最小二乘几何的延伸——$y$ 不在特征平面内，先选与 $y$ 关系更近的方向投影，再沿下一方向延伸，最终 $\hat{y}$ 落在 $y$ 的投影上、残差 $e$ 垂直于平面（数值验证内积为 0）。
• 代价：一个维度一个维度走，计算复杂度摆着；维度特别大时，先选谁有学问（看每个维度与 $y$ 的 correlation）。

📋 行动清单

• 用自己的话讲清”根据梯度下降”与”根据坐标轴下降”的区别，以及为什么后者不怕绝对值的尖角
• 跑代码一：把起点从 $(0,0)$ 改成 $(2.5, 0.0)$，观察”之”字路径殊途同归
• 跑代码一：把 $\lambda$ 改成 $5$，看两个系数被削掉多少、会不会有谁恰好归零
• 跑代码二：给 $y$ 再加一段平面外分量（如 $(0.2, 0, 0, -0.2)$），验证最终残差恰好等于它、且仍与两特征垂直
• 预习下一节《优化方法（2）》

—— 小象教研组