优化方法（2）：前向策略与最小角回归

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

上一节收尾留了话：“更多优化方法下一节继续。“这一节把剩下的讲完：第三种 forward strategy（前向策略），以及讲师口中”最常用的、或者我们觉得最有用的” least angle regression（最小角回归，常叫 LARS）。讲完这两样，整个线性模型部分就收官了——所以本节最后还有一段讲师特意做的全章总结，值得合上讲义后自己复述一遍。

💡 核心导读

• 前向策略：与 forward selection 同样从几何出发，但改用”小步试探”——每次同时算 $\varepsilon x_1$ 和 $\varepsilon x_2$ 两个方向的损失变化，谁降得多走谁，一步一步蹭到最优。
• 不会错过：$\varepsilon$ 是特别小的一个”平滑的值”，走出的 $\theta_1 = k\varepsilon$、$\theta_2 = m\varepsilon$ 就是 $k$ 次、$m$ 次小步的叠加。
• 最小角回归（LARS）：先用 forward selection 的眼光找到与 $y$ 相关最大的方向，走到”等角”处，然后沿两根特征角分线小步前进——结合了前两种方法的优点。
• 收官：线性模型这一整块，“闭着眼睛想，我们实际上就会一件事”——最后一段总结把从最小二乘到正则化到逻辑回归全部串起来。

方法三：前向策略

先说名字。中文资料里经常管 forward strategy 叫”前向梯度”，但讲师特意澄清：strategy 更多是策略的含义，并没有梯度的意思——它想做的事情是在这个平面里不断地沿着不同的轴移动，沿着与 $y$ 夹角更小（相关性更大）的方向去移动，一直找到最好的结果为止。它是一种完全基于计算的形式。

它和 forward selection 的区别，讲师用一句话点破：selection 是在一个维度上”一下子找到最合适的”，strategy 是两边的同时调整。

展开说。forward selection 的第一步，是在 $\theta_1$ 这个维度上一口气走到底：$\theta_1$ 取不同的值，每取一个值都要算一遍 cost function——往这个方向走，损失函数一直在减小，到了某一个值之后再往这边走，损失函数增大了，那这个值在这个维度上就是最合适的值。把 $\theta_1$ 确定好之后，再从 $\theta_2$ 的方向上走，同样沿着损失函数减小的方向不断调整，直到小到某一个值、再调就反弹，那个值就是最合适的。每一步只认一根轴，而且一步到位。

forward strategy 不一样。它每走一步都特别小：

• 开始先沿着一个方向做一个小的调整——走一个 $\varepsilon x_1$，看损失函数降了多少；
• 到了这一点之后，两个方向都要考虑：$\varepsilon x_1$ 往这边走会怎样、$\varepsilon x_2$ 往那边走会怎样，比较哪个方向比较好。比如还是 $x_1$ 这个方向好，那就继续往前走；
• 再到下一步，又要考虑两个方向——也许这次 $x_2$ 的方向更好，那就换过去。方向是可以随时切换的，一切以”哪个方向让损失降得多”为准。

讲师在图上比划的正是这个过程：从原点出发，先沿 $x_1$ 走一段，边走边看，中途切到 $x_2$，再切回来……每次更新的时候，在这两个轴的方向各取一个小的 $\varepsilon$，每次都要算 $\varepsilon x_1$ 和 $\varepsilon x_2$，更新完了之后回头看：这一次更新完的结果，$J$ 是变大了还是变小了？沿着损失函数变小的方向去不断调整。

为什么叫”不会错过”？ 走到平面上任何一点的时候，$\theta_1$ 就等于好多次 $\varepsilon$ 的叠加——比如说 $k$ 次 $\varepsilon$ 的叠加；$\theta_2$ 就是这个方向上大概 $m$ 次 $\varepsilon$ 的叠加。$\varepsilon$ 是一个特别小、特别平滑的值，所以每次的更新都不会跳过最优点。一步一步蹭过去，最终得到一组新的 $\theta_1$、$\theta_2$，使得 $J(\theta_1, \theta_2)$ 最小。把它跑起来（数据故意选成 $x_1$、$x_2$ 严格正交，方便看清每一步）：

# ---- forward strategy: 每步同时试 e*x1 和 e*x2 两个方向, 谁降得多走谁 ----
x1 = (1, 1, 0)
x2 = (1, -1, 0)
y = (3, 1, 1)          # y 带一段平面外的分量 (0,0,1)

def J(t1, t2):
    return sum((a * t1 + b * t2 - yi) ** 2 for a, b, yi in zip(x1, x2, y))

def forward_strategy(eps, max_steps=100000):
    t1 = t2 = 0.0
    k = m = 0                          # k: 走了 x1 方向的次数, m: 走了 x2 方向的次数
    snaps = []
    for step in range(1, max_steps + 1):
        d1 = J(t1 + eps, t2) - J(t1, t2)   # 沿 x1 走一小步 e 的损失变化
        d2 = J(t1, t2 + eps) - J(t1, t2)   # 沿 x2 走一小步 e 的损失变化
        if d1 <= d2 and d1 < 0:            # x1 方向降得更多 (或持平), 走 x1
            t1 += eps; k += 1
        elif d2 < 0:                       # 否则走 x2
            t2 += eps; m += 1
        else:                              # 两个方向都不再降: 停
            return t1, t2, k, m, step - 1, snaps
        if step in (1, 50, 100, 150, 200, 250, 290):
            snaps.append((step, t1, t2, J(t1, t2)))
    return t1, t2, k, m, max_steps, snaps

print("epsilon = 0.01:")
t1, t2, k, m, steps, snaps = forward_strategy(0.01)
for s, a, b, j in snaps:
    print(f"  走{s:3d}步: theta=({a:.2f},{b:.2f})  J={j:.4f}")
print(f"  停: 共 {steps} 步; x1 方向走了 {k} 次 (theta1 = k*e = {k*0.01:.2f}),")
print(f"      x2 方向走了 {m} 次 (theta2 = m*e = {m*0.01:.2f}), 终点 J={J(t1,t2):.4f}")

t1b, t2b, kb, mb, stepsb, _ = forward_strategy(0.07)
print(f"\nepsilon = 0.07 (粗): 共 {stepsb} 步, 终点 theta=({t1b:.2f},{t2b:.2f}), J={J(t1b,t2b):.4f}")

epsilon = 0.01:
  走  1步: theta=(0.01,0.00)  J=10.9202
  走 50步: theta=(0.50,0.00)  J=7.5000
  走100步: theta=(1.00,0.00)  J=5.0000
  走150步: theta=(1.25,0.25)  J=3.2500
  走200步: theta=(1.50,0.50)  J=2.0000
  走250步: theta=(1.75,0.75)  J=1.2500
  走290步: theta=(1.95,0.95)  J=1.0100
  停: 共 300 步; x1 方向走了 200 次 (theta1 = k*e = 2.00),
      x2 方向走了 100 次 (theta2 = m*e = 1.00), 终点 J=1.0000

epsilon = 0.07 (粗): 共 43 步, 终点 theta=(2.03,0.98), J=1.0026

读这张表。先大段走直线：前 100 步全部沿 $x_1$——这个方向与 $y$ 的相关性大（$\langle y,x_1\rangle = 4$，而 $\langle y,x_2\rangle = 2$），每一步都降得更多。中途切向：走到 $(1.00, 0.00)$ 之后，两个方向的降幅追平了，于是开始交替——看快照 $(1.25, 0.25)$、$(1.50, 0.50)$、$(1.75, 0.75)$，每一步换一个方向，走成一条对角线，最后停在 $(2.00, 1.00)$。叠加计数：$x_1$ 方向累计走了 $k = 200$ 次、$x_2$ 方向 $m = 100$ 次，所以 $\theta_1 = k\varepsilon = 2.00$、$\theta_2 = m\varepsilon = 1.00$——“$\theta_1$ 是 $k$ 次 $\varepsilon$ 的叠加”这句话的数值形态。地板是 1.0000：这份 $y$ 在特征平面外还有一段 $(0,0,1)$ 的分量，所以 $J$ 无论如何降不到 0——终点 $J = 1.0000$ 恰好是这段分量的长度平方，说明已经走到了 $y$ 的投影上。粗步长 $\varepsilon = 0.07$ 那一行是诚实对照：步长不整除最优值时，会停在最优附近 $\pm\varepsilon$ 以内、$J$ 略高于地板（1.0026）——$\varepsilon$ 越小停得越贴，代价是步数变多。

关键点回顾：我们在几何上到底在干什么

讲师在这里特意停下来重新描述了一遍——“这个可能是一个特别关键点，如果上次课不记得的话，这次可能确实会理解有问题。”

$x_1$、$x_2$ 是两个向量，构成一个平面。$\theta_1$、$\theta_2$ 各是一个数，作用是等比的扩大或者缩小：如果 $\theta_1$ 是一个小于 1 的数，$\theta_1 x_1$ 就是把 $x_1$ 缩短到这个方向上更近的一点；如果 $\theta_1$ 大于 1，就是放大到更远的一点。$x_1$ 本身只指定了一个方向，$\theta$ 控制它在这个方向上缩放多少。

两个缩放好的向量相加，$\theta_1 x_1 + \theta_2 x_2$，就是我们构造出来的结果。我们希望它和期待学习的 $y$ 之间距离最小——那就说明 $y$ 应该恰好是它所够不着的那一点的投影 $\hat{y}$：$\hat{y}$ 一定由 $x_1$、$x_2$ 的线性组合构成，而 $y - \hat{y}$ 这个向量一定垂直于 $x_1$、$x_2$ 所构成的平面。

一旦垂直，损失函数就最小；反过来，假设你调的 $\theta$ 不合适——比如 $\theta_1$ 调大了——构造出来的组合点就滑过了投影的位置，$y$ 减去它的距离反而变大，损失函数立刻变大。只有找到合适的 $\theta$，它才能落在投影上，距离才最小。而”距离的平方”这件事写下来，$y - (\theta_1 x_1 + \theta_2 x_2)$ 的长度平方——这不就是我们的损失函数吗？（两步搭出这个投影的 forward selection 版本几何，上一节已经配了数值演示；本节代码的终点 $J = 1.0000$、残差 $(0,0,1)$ 垂直于平面，正是同一个投影的”小步蹭过去”版。）

从两个向量到 n 个向量

有同学会问：为什么非得画两个向量？讲师的回答很实在：原则上它不会是两个向量构成的平面，它应该是 n 个向量构成的平面——因为 $X$ 原则上是一个特别大的矩阵。

把矩阵按列写全（讲师特意把常数列也写上）：

$$\underbrace{\begin{bmatrix}1\\ 1\\ \vdots\\ 1\end{bmatrix}}_{x_0\ \text{永远是 }1}\theta_0 + \underbrace{\begin{bmatrix}x_{11}\\ x_{21}\\ \vdots\\ x_{N1}\end{bmatrix}}_{N\times 1}\theta_1 + \cdots + \underbrace{\begin{bmatrix}x_{1n}\\ x_{2n}\\ \vdots\\ x_{Nn}\end{bmatrix}}_{N\times 1}\theta_n = \begin{bmatrix}y_1\\ y_2\\ \vdots\\ y_N\end{bmatrix}$$

第一列 $x_0$ 永远是 1（第 4 章就见过的 $x_0 \equiv 1$ 技巧），后面每一列都是一个 $N \times 1$ 的长向量。我们构造的就是一个这么长的向量：在每一个维度上乘上一个缩放的比值，所有的维度上都乘上各自的比值，张成一个高维的平面。要在这个高维平面里构造出 $y$ 的 $\hat{y}$，使 $\hat{y}$ 与 $y$ 之间的距离最小——道理和二维示意图完全一样。之所以只画两维，只是因为高维空间画不出来，用一张二维的图来示意。

方法四：最小角回归（LARS）

现在说本节的主角：least angle regression，最小角回归，大家经常管它叫 LARS——讲师对它的定位是”最常用的、或者是我们觉得最有用的”。它仍然沿用前面所有方法的整体思想，只是从另外一种方向去考虑这个问题。

第一步，先找到与 $y$ 相关性最大的维度（比如 $x_1$），沿这个方向走一小段，得到一个 $\theta_1 x_1$ 的点——注意是一小段，不是像 forward selection 那样一步走到底。

第二步，从这里开始走角分线。$x_1$ 与 $x_2$ 的角分线有一个漂亮的代数性质：角分线上的任何一个点，都是 $x_1 + x_2$ 的等比组合——

$$\theta_1 x_1 + \theta_2 (x_1 + x_2) = (\theta_1 + \theta_2) x_1 + \theta_2 x_2 = \theta_1' x_1 + \theta_2' x_2$$

沿角分线前进一段，相当于同时给两个系数各加一份：新的系数 $\theta_1' = \theta_1 + \theta_2$、$\theta_2' = \theta_2$ 是重新组合出来的。所以走在角分线上，$x_1$ 和 $x_2$ 两个方向是等比增加的——这正是”最小角”的含义：这个方向与两根特征轴的夹角相等，跟谁都不偏心。

之后的过程和 forward strategy 一模一样：每一次加一个小的 $\varepsilon$，沿着角分线不断地向前走，直到损失函数最小就停止。所以讲师的总结是：LARS 是 forward strategy 和 forward selection 两种方法的结合——类似地用了 forward selection 的部分，先一步找到最合适的那个维度；之后再在这条角分线上不断地加一小块一小块，求到最优的点。跑一遍（数据沿用上一节的同一组，可以和 forward strategy 的终点互相印证）：

# ---- LARS 简化演示: 先沿最相关特征走到"等角", 再沿角分线小步前进 ----
x1 = (1, 1, 0)
x2 = (1, -1, 0)
y = (3, 1, 1)

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

def J(t1, t2):
    return sum((a * t1 + b * t2 - yi) ** 2 for a, b, yi in zip(x1, x2, y))

def r_of(t1, t2):
    return [yi - a * t1 - b * t2 for a, b, yi in zip(x1, x2, y)]

print("数据: x1=(1,1,0), x2=(1,-1,0), y=(3,1,1)  (x1 与 x2 正交)")
print(f"初始相关性: <y,x1>={dot(y, x1):.1f}, <y,x2>={dot(y, x2):.1f}  -> 与 y 相关更大的是 x1")

print("\n第一步: 沿 x1 小步前进 (e=0.25), 直到两根轴与残差的相关性追平:")
t1 = t2 = 0.0
e = 0.25
for step in range(1, 5):
    t1 += e
    r = r_of(t1, t2)
    print(f"  走{step}步: theta=({t1:.2f},{t2:.2f})  <r,x1>={dot(r, x1):.2f}  "
          f"<r,x2>={dot(r, x2):.2f}  J={J(t1, t2):.3f}")
print("  <- 两边追平 (2.00 = 2.00), 停止单轴前进, 改走角分线")

print("\n第二步: 沿 x1 与 x2 的角分线前进 (角分线上的点都是 (1+d)*x1 + d*x2):")
for step in range(1, 5):
    t1 += e
    t2 += e
    r = r_of(t1, t2)
    print(f"  走{step}步: theta=({t1:.2f},{t2:.2f})  <r,x1>={dot(r, x1):.2f}  "
          f"<r,x2>={dot(r, x2):.2f}  J={J(t1, t2):.3f}")
print("  <- 相关性同步降到 0, 残差与整个平面垂直, 停")

r = r_of(t1, t2)
print(f"\n终点: y_hat = {t1:.1f}*x1 + {t2:.1f}*x2,  残差 = ({r[0]:.2f}, {r[1]:.2f}, {r[2]:.2f})")
print(f"验证: <残差,x1>={dot(r, x1):.2f}, <残差,x2>={dot(r, x2):.2f},  J={J(t1, t2):.3f} = 残差长度平方")
print("系数重组: 角分线共前进 d=1.00, 相当于新系数 theta1' = 1+1 = 2, theta2' = 0+1 = 1")

数据: x1=(1,1,0), x2=(1,-1,0), y=(3,1,1)  (x1 与 x2 正交)
初始相关性: <y,x1>=4.0, <y,x2>=2.0  -> 与 y 相关更大的是 x1

第一步: 沿 x1 小步前进 (e=0.25), 直到两根轴与残差的相关性追平:
  走1步: theta=(0.25,0.00)  <r,x1>=3.50  <r,x2>=2.00  J=9.125
  走2步: theta=(0.50,0.00)  <r,x1>=3.00  <r,x2>=2.00  J=7.500
  走3步: theta=(0.75,0.00)  <r,x1>=2.50  <r,x2>=2.00  J=6.125
  走4步: theta=(1.00,0.00)  <r,x1>=2.00  <r,x2>=2.00  J=5.000
  <- 两边追平 (2.00 = 2.00), 停止单轴前进, 改走角分线

第二步: 沿 x1 与 x2 的角分线前进 (角分线上的点都是 (1+d)*x1 + d*x2):
  走1步: theta=(1.25,0.25)  <r,x1>=1.50  <r,x2>=1.50  J=3.250
  走2步: theta=(1.50,0.50)  <r,x1>=1.00  <r,x2>=1.00  J=2.000
  走3步: theta=(1.75,0.75)  <r,x1>=0.50  <r,x2>=0.50  J=1.250
  走4步: theta=(2.00,1.00)  <r,x1>=0.00  <r,x2>=0.00  J=1.000
  <- 相关性同步降到 0, 残差与整个平面垂直, 停

终点: y_hat = 2.0*x1 + 1.0*x2,  残差 = (0.00, 0.00, 1.00)
验证: <残差,x1>=0.00, <残差,x2>=0.00,  J=1.000 = 残差长度平方
系数重组: 角分线共前进 d=1.00, 相当于新系数 theta1' = 1+1 = 2, theta2' = 0+1 = 1

三处观察。第一步走到”等角”：沿 $x_1$ 每走一小步，$\langle r, x_1\rangle$ 从 3.50 逐级往下掉，而 $\langle r, x_2\rangle$ 一直守在 2.00——走满 4 步，两边追平（2.00 = 2.00），这一段就到头了。这就是”最小角”的第一个含义：走到与下一个特征相关性相等的地方为止，不是一步到最优。角分线上等比同步：第二阶段的每一步，$\theta_1$ 和 $\theta_2$ 同步各加 0.25（等比增加），两个相关性从 1.50、1.00、0.50 一路严格相等地同步下降——走在角分线上，与两根轴的相关性永远持平，直到同时归零。与 forward strategy 殊途同归：终点同样是 $(2.00, 1.00)$、$J = 1.000$、残差 $(0, 0, 1)$ 垂直于平面——上一节用 300 个小步蹭到的投影点，LARS 沿”先单轴、后角分线”的路线 8 步就走到了。

两个诚实的注脚。其一，这份演示数据里 $x_1$ 与 $x_2$ 正交，角分线恰好就是 $(x_1 + x_2)$ 方向；特征不正交时，角分线的方向和步长都要解一个小线性系统来保持”等角”性质，机制相同、计算更长。其二，讲师对全节的定位是：具体的公式没有展开——本课的目的就是用几何的方式，让大家了解这几个算法都在做什么；而且现在所有这几个算法都有合适的现成 code，可以直接去使用，实际上不需要从头到尾地自己编代码。回看这三个”前向”方法，它们和上一节的坐标下降一样，都是把”上节课用向量描述的最小二乘”继续用平面、空间里向量的形式走出来的——每一步都看得见在做什么。

线性模型全章收官

到这里，讲师宣布：线性模型基本就算讲完了。收尾这段总结值得原样复述——

大家仔细想，线性这一块闭着眼睛想了这么久，我们实际上就会一件事：给了好多点之后（空间里或者高维空间里的很多点），如何找一个线性方程去拟合。就这一件事。

当这个线性方程过于复杂、或者维度过于高的时候，你想同时选择一些合适的特征，就可以给线性方程加一些 regularization、加一些约束项，加完约束项之后重新去优化：

• 加的是 L2 范数（岭回归）：直接可以进行优化，用我们以前的解析式就可以得到（第 9.2 节的 $(X^TX + \lambda I')^{-1}X^Ty$）；
• 加的是 L1 范数（拉索）：一范数的约束不可导，解析式做不出来，那就用相当于计算的方法来进行优化——上一节和这一节的坐标下降、前向选择、前向策略、LARS，全部都是为它准备的。

同时，还可以把线性模型放进 sigmoid function 里面，就会变成更广义的线性模型——比如罗吉斯特回归（逻辑回归）。它其实是个非线性模型，但它的基础还是线性模型（第 8.5、9.1 节）。

所以这些线性模型有一个共同的基本思想：如何选择合适的 $\theta$——每一个特征的系数。在系数的选择上，让它去逼近你最期望的结果；而”最期望结果的逼近”，往往是通过构造一个损失函数来完成的——最简单的情况，直接求它的平方和；再复杂一点，就是平方和加上约束项。我们学了这么久，线性方程（线性模型）做的就是这么一件事。

（讲师在视频结尾预告”下次课开始讲一些主要是概率和统计方面的东西”；按课程实际编排，下一章先进入拉格朗日乘子法与最大间隔——通往支持向量机的数学准备，概率统计的深入内容在后面的统计学习一章兑现。）

📝 动手练一练

1. 三种”前向”的关系：forward selection、forward strategy、LARS 三者的走法各是什么？为什么说小步 $\varepsilon$ “不会错过”最优点？

2. LARS 手算：三个样本，$x_1 = (1, 1, 0)$、$x_2 = (1, -1, 0)$（正交），$y = (5, 1, 2)$。按 LARS 的两步走：第一步沿哪个方向、走到哪里”等角”？第二步沿角分线走到哪里停？最终 $\theta$ 是多少，验证残差与两个特征都垂直。

本章小结

• 前向策略（forward strategy）：中文常叫”前向梯度”但并无梯度含义；每步同时算 $\varepsilon x_1$、$\varepsilon x_2$ 两个方向的损失变化、谁降得多走谁、随时换向；$\theta_1 = k\varepsilon$、$\theta_2 = m\varepsilon$——$\varepsilon$ 特别小，所以不会错过。数值实证：300 步停在 $(2.00, 1.00)$、$J = 1.0000$ 恰为平面外分量的长度平方；粗步长 0.07 停在 $(2.03, 0.98)$、$J = 1.0026$。
• 几何上的”一件大事”：$\theta$ 控制各特征方向的等比缩放，$\theta_1x_1 + \theta_2x_2$ 的组合落在 $y$ 的投影 $\hat{y}$ 上时 $y - \hat{y}$ 垂直于平面、损失最小；$\theta$ 调过头距离立刻变大——损失函数就是这个距离的平方。
• n 维一般化：$X$ 是大矩阵、$x_0$ 永远是 1、每列 $N \times 1$，n 个向量张成高维平面——二维图只是示意。
• LARS：先沿最相关特征走到”等角”，再沿角分线（点都是 $x_1 + x_2$ 的等比组合、两系数等比同步增加）小步前进到垂直；是 forward selection 与 forward strategy 的结合，讲师定位”最常用、最有用”。正交演示 8 步走到与 300 小步相同的投影点 $(2.00, 1.00)$。具体公式本课未展开——目的是几何地理解算法在做什么；现成 code 可直接用，不需要自己从头编。
• 线性模型收官：闭眼想只会一件事——给高维空间的点找线性方程拟合；复杂/高维了就加约束项重新优化（L2 走解析式、L1 走计算方法）；放进 sigmoid 就成了逻辑回归这类”基础是线性”的非线性模型；一切归结为选合适的特征系数 $\theta$、构造损失函数（平方和，或平方和加约束项）逼近。

📋 行动清单

• 用自己的话讲清 forward selection（一步一根轴走到底）与 forward strategy（小步双向试探）的区别，以及 LARS 怎么”结合”两者
• 跑代码一：把 $\varepsilon$ 从 0.01 改成 0.001，观察步数的变化和终点贴得有多近
• 跑代码二：把 $y$ 换成 $(5, 1, 2)$ 重跑 LARS 演示，对照练一练第 2 题的手算（等角点 $\theta_1 = 1$、角分线前进 $d = 2$）
• 合上讲义，复述”线性模型这一章我们实际上就会的一件事”，以及 L1 与 L2 两条路线各自的求解方式
• 预习下一章《拉格朗日乘子法》——支持向量机的数学准备

—— 小象教研组