DASE 7113 · 课程精讲

无约束优化算法

共 47 页。按原课件顺序,左侧看原页,右侧读讲解。

逐页目录 · 共 47 页
  1. 这讲的主线:知道条件以后,怎样真的算出解
  2. 先记住判断目标:梯度等于零
  3. 逻辑回归的任务:预测录取概率
  4. 先算连续分数 z
  5. Sigmoid:把任意分数变成概率
  6. 交叉熵:怎样惩罚错误的概率
  7. 把逻辑回归写成矩阵运算
  8. 梯度推导:为什么最后只剩 Xᵀ(p−y)
  9. 迭代法的第一步:方向和距离分开选
  10. 沿一个方向,把多维问题变成一维函数
  11. 下降方向只要求走一小步时有效
  12. 二次函数练习:算出梯度和两条搜索曲线
  13. 读两张曲线:负梯度也会走过头
  14. 扫描所有单位方向:公平比较哪边下降最多
  15. 为什么负梯度最陡;原页边界应怎样读
  16. 最速下降法的完整循环
  17. 什么时候停止:三种常见检查
  18. 策略一:固定步长
  19. 模拟录取模型:临界点怎么求
  20. 逐句读数据生成代码
  21. 先用现成求解器得到参照答案
  22. 自己写固定步长梯度下降
  23. 读固定步长的比较图
  24. 策略二:沿当前方向选最好的步长
  25. 先把无限搜索范围缩成有限区间
  26. 用倍增法自动找右端点
  27. 网格搜索:最容易实现的一维搜索
  28. 只看一个中点,还不能决定丢哪一半
  29. 黄金分割比例为什么是 0.618
  30. 黄金分割如何复用旧点
  31. 把缩区间的动画拆成三轮
  32. 代码分支一:左点较低,更新右边界
  33. 代码分支二:右点较低,更新左边界
  34. 直接调用一维求解器
  35. 把固定步长程序改成线搜索
  36. 逻辑回归的精确线搜索代码
  37. 精确线搜索为什么轮数少,却未必省时间
  38. 策略三:非精确线搜索
  39. 参考直线:什么叫下降得足够多
  40. 回溯线搜索:不合格就乘一个小于一的数
  41. 三种步长放在一起比较
  42. 牛顿法第一步:在当前位置造一个二次近似
  43. 把近似抛物线的最低点当作下一步
  44. 多维牛顿法:由最小化二次模型推出来
  45. 逻辑回归为什么适合这个牛顿练习
  46. 逐句实现牛顿法,不必真的构造大对角矩阵
  47. 读最终结果:牛顿法快在哪里,成本在哪里
原第 1 页

这讲的主线:知道条件以后,怎样真的算出解

原课件第1页
点击原页可打开 PDF。

上一讲用“梯度等于零”求出了线性回归的最优参数。这一讲遇到逻辑回归:梯度也能写出来,但令它为零以后,得到的是难以直接解开的非线性方程。

因此要学习迭代算法:从一个初始点出发,反复修改,逐渐接近最优解。路线是:逻辑回归建模 → 下降方向 → 梯度下降 → 三种选步长的方法 → 牛顿法。每个算法都围绕三个问题:往哪里走、走多远、什么时候停。

对应课堂录音Week07 Part01 00:12:56–00:18:19Week07 Part01 02:10:34–02:16:06
原第 2 页

先记住判断目标:梯度等于零

原课件第2页
点击原页可打开 PDF。

本页复习可微无约束凸优化的最优性条件:minx∈Rnf(x),x* 最优⟺∇f(x*)=0.

x 是全部待选参数组成的向量,∇f 把每个参数的偏导数排在一起。梯度为零,表示所有一阶变化率都为零。

例如 f(x)=(x−3)2,令 2(x−3)=0 很容易解出 x=3。但如果参数出现在指数函数里面,方程未必能这样直接整理出答案。最优性条件告诉我们最后应该满足什么;算法负责带我们走到那里。

对应课堂录音Week07 Part01 01:31:31–01:38:40
原第 3 页

逻辑回归的任务:预测录取概率

原课件第3页
点击原页可打开 PDF。

每名学生有两个输入:x1 是缩放到 0 到 1 的 GPA,x2 表示是否有论文,有为 1、没有为 0。输出 y 表示录取结果:录取为 1,未录取为 0。

例如学生 A 的输入为 (0.85,0),学生 B 为 (0.75,1)。训练数据还包括他们实际是否被录取的标签 y。

我们要学的是一个从输入到录取概率的映射。直接用普通直线预测,可能得到 −0.2 或 1.4,这不适合作为概率。因此先算一个可以任意取值的分数,再把分数压到 0 和 1 之间。

对应课堂录音Week07 Part01 00:12:56–00:18:19Week07 Part01 00:18:19–00:22:14
原第 4 页

先算连续分数 z

原课件第4页
点击原页可打开 PDF。

定义 z=β0+β1x1+β2x2。把它理解为模型给学生的综合分数:分数越高,模型认为录取越可能。

  1. β0 是基础分,也称截距。
  2. β1 决定 GPA 对分数的影响。例如 β1=100,GPA 增加 0.01,分数增加 1。
  3. β2 决定“有论文”带来的分数变化。若它为 10,从没有论文变为有论文,分数增加 10。

例如参数取 (β0,β1,β2)=(−85,100,10),学生 (x1,x2)=(0.8,1) 的分数是 −85+100×0.8+10=5。此时得到的是分数 5,接下来才把它转为概率。

对应课堂录音Week07 Part01 00:18:19–00:22:14
原第 5 页

Sigmoid:把任意分数变成概率

原课件第5页
点击原页可打开 PDF。

逻辑函数,也叫 sigmoid,定义为 p=Pr(y=1∣x)=σ(z)=11+e−z. 由于 e−z>0,分母始终大于 1,所以概率在 0 与 1 之间。

  1. z=0:e0=1,所以 p=1/(1+1)=0.5。图中 S 形曲线经过中间点。
  2. z=2:p=1/(1+e−2)≈0.881。分数为正,录取概率大于一半。
  3. z=−2:p=1/(1+e2)≈0.119。分数为负,录取概率小于一半。

读图时横轴是分数 z,纵轴是概率。两端逐渐变平:分数继续增大时,概率逐渐靠近 1;继续减小时,概率逐渐靠近 0。

对应课堂录音Week07 Part01 00:18:19–00:22:14
原第 6 页

交叉熵:怎样惩罚错误的概率

原课件第6页
点击原页可打开 PDF。

第 i 名学生的预测概率记为 pi,真实标签是 yi∈{0,1}。单条损失是 ℓi=−yilogpi−(1−yi)log(1−pi).

  1. 若实际录取,yi=1,第二项消失,剩下 −logpi。预测 0.9 时损失约 0.105;预测 0.1 时损失约 2.303。
  2. 若实际未录取,yi=0,第一项消失,剩下 −log(1−pi)。预测 0.1 时损失约 0.105;预测 0.9 时损失约 2.303。
  3. 所以把正确标签的概率设得越高,损失越小;非常自信地预测错误,损失会很大。
  4. 将所有样本的损失相加,选择使 l(β)=∑iℓi 最小的参数。这就是逻辑回归的训练问题。

本页左侧从 xi 算出 zi,中间从 zi 算出 pi,右侧用真实 yi 评分。整个过程可以沿着这条链读。

对应课堂录音Week07 Part01 00:18:19–00:22:14
原第 7 页

把逻辑回归写成矩阵运算

原课件第7页
点击原页可打开 PDF。

和线性回归一样,把每名学生的一行特征写成 (1,xi1,…,xim),组成 X∈Rn×(m+1)。参数 β、分数 z、概率 p、标签 y 都是列向量。

z=Xβ,pi=11+e−zi,l=−yTlogp−(1−y)Tlog(1−p).
  1. 先做一次矩阵乘法 Xβ,得到全部 n 个分数。
  2. 对每个分数分别计算 sigmoid,得到 n 个概率;指数和除法都是逐元素计算。
  3. logp 也是逐元素取对数。yTlogp 就是 ∑iyilogpi。
  4. 1 表示全 1 向量,长度为 n。第二个内积处理标签为零的那部分损失。

这一步把许多样本的求和,整理成几行矩阵表达式,为求导和编程做准备。

原第 8 页

梯度推导:为什么最后只剩 Xᵀ(p−y)

原课件第8页
点击原页可打开 PDF。

沿着 β→z→p→l 逐层使用链式法则。先只看一个样本:

  1. 对概率求导:∂ℓi∂pi=−yipi+1−yi1−pi.
  2. 将 pi=(1+e−zi)−1 对 zi 求导。外层求导给出 −(1+e−zi)−2,内层给出 −e−zi,两者相乘为 e−zi(1+e−zi)2=pi(1−pi),其中 1−pi=e−zi/(1+e−zi)。乘上第一步的结果,得到 ∂ℓi∂zi=(−yipi+1−yi1−pi)pi(1−pi)=−yi(1−pi)+(1−yi)pi=pi−yi.
  3. 把常数列记为 Xi0=1,则 zi=∑jXijβj,所以 ∂zi/∂βj=Xij。
  4. 先对第 j 个参数算偏导,再把各样本的贡献相加,得到 ∂l∂βj=∑i∂ℓi∂zi∂zi∂βj=∑iXij(pi−yi). 这恰好是 XT(p−y) 的第 j 个分量,因此 ∇l(β)=XT(p−y)。 维度为 (m+1)×n 乘 n×1,结果与参数的长度相同。

令梯度为零得到 XT(σ(Xβ*)−y)=0. 参数藏在 sigmoid 的指数里面,这已经是非线性方程,无法照搬线性回归的逆矩阵公式。

一个样本算到更新:只取截距和一个输入,特征行为 (1,2),真实标签为1。从 β=(0,0)T 开始,z=0、p=0.5,所以 ∇ℓ=[12](0.5−1)=[−0.5−1]. 取步长0.1,更新后 β=(0.05,0.1)T,新分数为 0.05+2×0.1=0.25,新概率约0.56218。正确标签的概率从0.5升高,损失 −logp 从约0.69315降到0.57594。梯度里的负号正是让这次更新提高正确标签的概率。

原第 9 页

迭代法的第一步:方向和距离分开选

原课件第9页
点击原页可打开 PDF。

当前参数是 xk,上标 k 表示第几轮迭代。我们想找一个新点 xk+1,让它的目标值更小。

xk+1=xk+αkdk.

dk 是方向向量,决定往哪走;αk≥0 是步长,决定沿这个向量走多少倍。图中的小点是起点,不同箭头代表不同方向。

例如当前在 (2,2),取 d=(−1,−2)、α=0.1,则新点为 (2,2)+0.1(−1,−2)=(1.9,1.8)。实际走过的欧氏距离是 α‖d‖2,方向没有单位化时,它不等于 α。

老师用“下山”解释:先找能往低处走的方向,再决定走多远。只选好方向还不够,跨得太大也可能又走到高处。

对应课堂录音Week07 Part01 00:26:35–00:32:16Week10 Part01 00:36:06–00:41:40
原第 10 页

沿一个方向,把多维问题变成一维函数

原课件第10页
点击原页可打开 PDF。

固定当前点 xk 和方向 d,定义 g(α)=f(xk+αd). 此时只改变一个数 α:它表示走到这条射线的哪个位置。g(0)=f(xk) 是出发点的目标值。

如果要求任意 α≥0 都有 g(α)≤g(0),就意味着沿这个方向走多远都不会变差。这个要求太强,连许多很好的下坡方向也会被排除。

例如 f(x)=x2,从 xk=1 向左取 d=−1,有 g(α)=(1−α)2。α=0.5 时降到 0.25;α=1 到达最低值 0;但 α=3 时走过头,函数值变成 4,高于原来的 1。向左明明能下坡,不能因为走过头会变差就否认它是下降方向。

对应课堂录音Week07 Part01 00:26:35–00:32:16Week07 Part01 00:41:13–00:46:39Week07 Part01 01:14:22–01:24:45
原第 11 页

下降方向只要求走一小步时有效

原课件第11页
点击原页可打开 PDF。

实用的要求是:存在一个正数 α¯,使每个 0<α<α¯ 都有 f(xk+αd)<f(xk)。换句话说,朝这个方向走足够小的一步,目标就会下降。

继续看 g(α)=(1−α)2。要比原来的 1 小,解 (1−α)2<1⟺α2−2α<0⟺0<α<2. 所以向左是下降方向,算法只需要挑一个合适的正步长。

如果函数可微,检查起点的一维导数就很方便:g′(0)=∇f(xk)Td. 若 g′(0)=−c 且 c>0,那么只要 α>0 取得足够小,差商 [g(α)−g(0)]/α 就会足够接近 −c,例如小于 −c/2。再乘以正数 α,得到 g(α)−g(0)<0。

对应课堂录音Week07 Part01 00:41:13–00:46:39
原第 12 页

二次函数练习:算出梯度和两条搜索曲线

原课件第12页
点击原页可打开 PDF。

函数仍是 f(x1,x2)=2x12+4x1x2+5x22−8x1−6x2+10。当前点为 (2,2)。

  1. 代入梯度:∇f(2,2)=[4×2+4×2−84×2+10×2−6]=[822]. 起点函数值为 f(2,2)=26。
  2. 沿正梯度 d1=(8,22),路径为 (2+8α,2+22α)。代回原函数并展开,得到 g1(α)=26+548α+3252α2。
  3. 沿负梯度 d2=(−8,−22),路径为 (2−8α,2−22α)。得到 g2(α)=26−548α+3252α2。

548 来自 82+222;二次项系数逐项合并为 2×82+4×8×22+5×222=128+704+2420=3252。画图前先得到这两个表达式,就能清楚知道每个横坐标 α 代表什么。

对应课堂录音Week07 Part01 00:32:56–00:35:15Week07 Part01 00:41:13–00:46:39
原第 13 页

读两张曲线:负梯度也会走过头

原课件第13页
点击原页可打开 PDF。

左图对应正梯度:g1(α)=26+548α+3252α2。对于正步长,两项增量都为正,所以曲线一直上升,它不是下降方向。

右图对应负梯度:g2(α)=26−548α+3252α2。

  1. 出发斜率为 g2′(0)=−548,所以一开始下降。
  2. 令 g2′(α)=−548+6504α=0,得该直线上最好的步长 α≈0.08425584。
  3. 此时新点约为 (1.32595,0.14637),函数值约为 2.91390。
  4. 要保持优于起点,需 −548α+3252α2<0,即 0<α<0.16851169。再大就走过头了;例如 α=0.2 时,目标值为 46.48。

注意:沿这条直线的最小值约为 2.914,整个二维问题的最小值为 5/3。一次线搜索只优化当前方向,随后仍需重新计算方向。

用 Python 重画两条搜索曲线
import numpy as np
import matplotlib.pyplot as plt

alpha = np.linspace(0, 0.2, 201)
g_up = 26 + 548*alpha + 3252*alpha**2
g_down = 26 - 548*alpha + 3252*alpha**2
plt.plot(alpha, g_up, label="gradient")
plt.plot(alpha, g_down, label="negative gradient")
plt.axhline(26, color="gray", linestyle="--")
plt.xlabel("alpha")
plt.ylabel("objective")
plt.legend()
plt.show()

两条曲线共用同一列步长。灰线标出出发点的目标值 26,橙线低于灰线的区间对应更新后目标值下降的步长。

动手试 · 沿负梯度走多远

用本页的 g(α)=26−548α+3252α²。先找谷底,再把步长拖到 0.20。

对应课堂录音Week07 Part01 00:32:56–00:35:15
原第 14 页

扫描所有单位方向:公平比较哪边下降最多

原课件第14页
点击原页可打开 PDF。

比较方向时,先把每条箭头的长度定为 1,再沿每个方向移动同样的距离 δ=0.01。代码把形成下降的箭头用蓝色标出,再用红色标出扫描中最低的一条。

import numpy as np
import matplotlib.pyplot as plt

def f(x):
    x1, x2 = x
    return 2*x1**2 + 4*x1*x2 + 5*x2**2 - 8*x1 - 6*x2 + 10

x0 = np.array([2.0, 2.0])
theta = np.linspace(0, 2*np.pi, 100, endpoint=False)
directions = np.column_stack((np.cos(theta), np.sin(theta)))
values = np.array([f(x0 + 0.01*d) for d in directions])
best = np.argmin(values)
descends = values < f(x0)
print(directions[best], values[best])

fig, ax = plt.subplots(subplot_kw={"projection": "polar"})
for i, angle in enumerate(theta):
    color = "tab:red" if i == best else "tab:blue" if descends[i] else "0.8"
    ax.plot([angle, angle], [0, 1], color=color)
plt.show()
  1. 角度 θ 从正 x1 方向逆时针计量。cos2θ+sin2θ=1,所以由余弦和正弦拼成的每一行都是单位向量。endpoint=False 让 0° 和 360° 这个方向只出现一次。
  2. 列表推导式逐条计算 f(x0+0.01d)。values 和 directions 使用同一个下标,因此 argmin 找出最低值的下标后,就能取出对应的方向。descends 逐项比较目标是否跌破起点的 26。
  3. 100 个角度相距 360∘/100=3.6∘。这次最好的方向是 248.4∘,向量约为 (−0.36812,−0.92978)T,一步后目标约为 25.76660。

下一页从导数推导的单位负梯度约为 (−0.34174,−0.93979)T。直接沿它走 0.01,目标约为 25.76650。扫描只能从指定的 100 个方向中选择,一阶推导则描述距离趋近 0 时的最佳方向。

对应课堂录音Week07 Part01 00:59:11–01:14:22Week07 Part01 01:14:22–01:24:45
原第 15 页

为什么负梯度最陡;原页边界应怎样读

原课件第15页
点击原页可打开 PDF。

图中箭头从同一点出发,红箭头表示能下降的方向,蓝色箭头指向负梯度。向下偏左是本例下降最多的方向,因为梯度为 (8,22)。

  1. 一小步的变化约为 f(x+δd)−f(x)≈δ∇f(x)Td。因此内积越负,一阶下降越多。
  2. 令 v=∇f(x),且 v≠0。对单位方向 ‖d‖2=1,柯西不等式给出 |vTd|≤‖v‖2‖d‖2=‖v‖2,因此 vTd 最低只能到 −‖v‖2。
  3. 把 d=−v/‖v‖2 代入,得到 vTd=−vTv/‖v‖2=−‖v‖2,达到下界。这就是欧氏距离下的一阶最速下降方向。

严格下降的一阶充分条件是 ∇f(x)Td<0,等价于 dT[−∇f(x)]>0,也就是与负梯度夹角小于 90°。原页写的“≥0”包含了边界;等于零时要继续看高阶项,不能直接判为下降。例如本例取 d=(22,−8),内积为零,但二次增量为正。

用3、4、5看“最陡”:假设当前梯度为 (3,4),比较三个长度都是1的方向。向左 (−1,0) 的内积为−3,向下 (0,−1) 为−4,单位负梯度 (−3/5,−4/5) 为 −9/5−16/5=−5。同样走很小的距离0.01,一阶预测分别下降约0.03、0.04、0.05。

对应课堂录音Week07 Part01 00:46:40–00:59:11Week07 Part01 00:59:11–01:14:22Week07 Part01 01:14:22–01:24:45Week07 Part01 01:24:46–01:31:31Week08 Part01 00:00:20–00:06:46
原第 16 页

最速下降法的完整循环

原课件第16页
点击原页可打开 PDF。

直接采用负梯度方向,就得到更新式 xk+1=xk−αk∇f(xk). 不断重复这一步,就是本讲的最速下降法。

  1. 指定起点 x0,例如先把所有参数设为零。
  2. 在当前点计算梯度。梯度每轮都要重新算,因为函数在不同位置的坡度不同。
  3. 选择步长 αk>0,沿负梯度方向更新。
  4. 检查停止条件。满足就退出;否则把新点当作当前点,再做下一轮。

代入前面的二次例子,x0=(2,2)、梯度为 (8,22),若 α0=0.05,则 x1=(2,2)−0.05(8,22)=(1.6,0.9)。这一步的目标值从 26 降为 6.73。之后要在 (1.6,0.9) 处重算梯度,而不是一直沿旧箭头走。

再算下一轮:在 (1.6,0.9),梯度变成 (4×1.6+4×0.9−8, 4×1.6+10×0.9−6)=(2,9.4)。继续取步长0.05,得到 (1.6,0.9)−0.05(2,9.4)=(1.5,0.43),目标继续降到3.4245。两轮梯度从 (8,22) 变为 (2,9.4),说明方向会随位置调整。

对应课堂录音Week07 Part01 01:24:46–01:31:31Week07 Part01 01:59:13–02:04:42
原第 17 页

什么时候停止:三种常见检查

原课件第17页
点击原页可打开 PDF。

计算机不能等无限多轮,需要设置容差 ε>0,例如 10−6。本页给出三个停止信号:

  1. 梯度很小:‖∇f(xk)‖2<ε。范数是梯度向量的长度。例如梯度为 (3×10−7,4×10−7),范数为 5×10−7,小于 10−6。它直接对应“梯度等于零”的最优性条件。
  2. 变量几乎不动:‖xk−xk−1‖2<ε。比较这轮和上一轮参数变化。
  3. 目标几乎不变:|f(xk)−f(xk−1)|<ε。比较相邻两轮损失。

后两项适合发现停滞,但步长太小时也可能出现“几乎不动”。实际练习优先检查梯度,并设置最大迭代次数。读程序时还要分清目标是误差总和还是平均值,二者的梯度差一个样本数倍数,容差的数值也会随之改变。

对应课堂录音Week07 Part01 01:31:31–01:38:40
原第 18 页

策略一:固定步长

原课件第18页
点击原页可打开 PDF。

固定步长就是选好常数 α,每轮都使用同一个值。优点是每轮计算简单:求一次梯度,直接更新。

用 f(x)=x2 看步长的作用。因为 f′(x)=2x,更新式为 xk+1=xk−2αxk=(1−2α)xk.

  1. 若 α=0.1,每轮乘 0.8。从 1 开始:1、0.8、0.64、0.512,逐渐接近零。
  2. 若 α=0.5,每轮乘零,一步到零点。
  3. 若 α=1.1,每轮乘 −1.2,方向来回反转,绝对值越来越大,算法发散。

这个简单例子的收敛范围是 |1−2α|<1,即 0<α<1。一般问题的合适范围由函数的曲率决定,不能把同一个步长数值直接套到所有问题。

对应课堂录音Week07 Part01 01:31:31–01:38:40Week07 Part01 01:59:13–02:04:42
原第 19 页

模拟录取模型:临界点怎么求

原课件第19页
点击原页可打开 PDF。

本例用于生成数据的模型为 z=100x1+10x2−85,p=11+e−z. 这里的系数先由我们设定,之后再只给算法数据,让它尝试把系数学回来。

  1. 临界概率 p=0.5 对应分数 z=0。因此临界线为 100x1+10x2−85=0。
  2. 没有论文时 x2=0,所以临界 GPA 为 x1=85/100=0.85。
  3. 有论文时 x2=1,所以 100x1+10−85=0,得到 x1=0.75。
  4. GPA 为 0.8、没有论文时,z=−5,p≈0.00669;同样 GPA、有论文时,z=5,p≈0.99331。

这组数值让输入到概率的关系很明显。生成真实标签时仍需按概率抽取 0 或 1,而不是直接把概率当作标签。

对应课堂录音Week07 Part01 01:31:31–01:38:40
原第 20 页

逐句读数据生成代码

原课件第20页
点击原页可打开 PDF。
import numpy as np

np.random.seed(0)
N = 1000
GPA = np.random.normal(80, 10, N).clip(30, 100) / 100
PAPER = np.random.choice([0, 1], size=N, p=[0.8, 0.2])
One = np.ones(N)
X = np.column_stack((GPA, PAPER, One))
weight_real = np.array([100, 10, -85])
z = X @ weight_real
p = 1 / (1 + np.exp(-z))
y = np.random.binomial(1, p)
  1. 产生 1000 个 GPA,均值 80、标准差 10;先用 clip 把数值限制在 30 至 100,再除以 100。
  2. choice 独立产生论文标记:0 的概率是 0.8,1 的概率是 0.2。
  3. X 的三列依次为 GPA、PAPER、全 1 列,形状是 1000×3。
  4. 所以参数顺序为“GPA 系数、论文系数、截距”,与前面写 (1,x1,x2) 时的顺序不同,但模型本身相同。
  5. 先算 1000 个分数,再转为概率。
  6. binomial(1,p) 对每个概率做一次伯努利抽样:输出 1 的概率为 pi,否则输出 0。

固定种子运行这段代码,得到 372 个标签 1。这些 X,y 就是后续所有算法共同使用的数据。

用 print(X[0], z[0], p[0], y[0]) 可以查看第一条样本。GPA 约为 0.976405,有论文,设计矩阵第一行约为 (0.976405,1,1)。和 (100,10,−85)T 做点积得到 z0≈22.64052,对应概率极接近 1,这次抽样得到标签 y0=1。

对应课堂录音Week07 Part01 01:31:31–01:38:40Week07 Part01 01:49:10–01:59:13
原第 21 页

先用现成求解器得到参照答案

原课件第21页
点击原页可打开 PDF。

本页先调用现成的逻辑回归求解器,获得参数参照,再检查自己写的算法是否接近它。数据生成沿用上一页。

from sklearn.linear_model import LogisticRegression
model = LogisticRegression(C=np.inf, fit_intercept=False,
                           max_iter=10000, tol=1e-10)
model.fit(X, y)
print(model.coef_)
  1. C=np.inf 让正则化强度为零,对应课件的无正则化损失。课件原代码用 penalty="none" 表达相同意图;这里给出已运行的写法。
  2. fit_intercept=False 很关键:我们已经在 X 的最后一列放了全 1,所以不再额外增加截距。
  3. fit(X,y) 开始训练;coef_ 取出训练后的参数。

得到参数约为 (96.88708,9.83687,−82.47006),与课件列出的 (96.88,9.84,−82.47) 接近。它们不等于生成参数 (100,10,−85),因为只有有限条随机抽样数据;训练求的是这份数据的最优拟合。

原第 22 页

自己写固定步长梯度下降

原课件第22页
点击原页可打开 PDF。

先运行第20页,得到 X,y,N。课件使用平均交叉熵,其梯度为 XT(p−y)/N。从零参数开始,每轮先检查当前梯度,再更新参数。

w = np.zeros(X.shape[1])
step_size = 1.0
for k in range(1000000):
    z = X @ w
    p = 1 / (1 + np.exp(-z))
    gradient = X.T @ (p - y) / N
    if np.linalg.norm(gradient, 2) < 1e-8:
        break
    w = w - step_size * gradient
z = X @ w
p = 1 / (1 + np.exp(-z))
grad_norm = np.linalg.norm(X.T @ (p - y) / N)
print(w)
print(grad_norm)
  1. zeros 生成三个零参数。起初全部分数为零,因此每条预测概率都是 0.5。
  2. p−y 衡量每条预测与标签的偏差;左乘 XT 把所有样本对各参数的影响汇总起来,再除以样本数。
  3. norm(...,2) 求梯度的欧氏长度。足够小就停止。
  4. 否则减去“步长乘梯度”,保存新参数,进入下一轮。

本例初始平均梯度约为 (0.068968,−0.0435,0.128),步长 1 更新后 w1≈(−0.068968,0.0435,−0.128)。这次更新把平均损失从约 0.69315 降至 0.67391。代码最后在最新参数处重算梯度范数。按本页设定运行,步长 1 用完 100 万次更新后,梯度范数约为 2.49×10−7,仍高于停止阈值 10−8。下一页比较不同步长下需要多少轮。

对应课堂录音Week07 Part01 01:38:43–01:49:06Week07 Part01 01:59:13–02:04:42
原第 23 页

读固定步长的比较图

原课件第23页
点击原页可打开 PDF。

横轴是迭代次数,右下角的 106 表示横轴标记还要乘一百万;纵轴是梯度范数,使用对数刻度。纵轴每下降两格,范数通常减少一百倍。

  1. 蓝线步长 1:梯度范数持续下降,但到很小的容差需要很多轮。
  2. 橙线步长 5、绿线步长 10:在这份数据上达到同一范数需要的轮数更少。
  3. 红线步长 50:长期停在较高位置,没有像其他曲线一样降到零附近。它说明步长过大,算法没有正常收敛。

老师在课堂还展示了过大步长下的数值问题:sigmoid 可能非常接近 0 或 1,直接算 logp 会出现无穷大。可先把损失改写到分数 zi 上。由 pi=ezi/(1+ezi) 得 logpi=zi−log(1+ezi),同时 1−pi=1/(1+ezi),所以 log(1−pi)=−log(1+ezi)。代入第6页并合并 log(1+ezi) 的两项,得到 L(w)=1N∑i[log(1+ezi)−yizi]. NumPy 的 np.logaddexp(0, z) 直接稳定计算 log(e0+ez),所以可以写成 np.mean(np.logaddexp(0, z) - y*z)。

原第 24 页

策略二:沿当前方向选最好的步长

原课件第24页
点击原页可打开 PDF。

既然步长影响很大,可以在每轮重新选择:固定当前位置和负梯度,定义 g(α)=f(xk−α∇f(xk)),αk=argminα≥0g(α).

argmin 返回“让函数最小的那个自变量”,所以这里返回步长 αk,不是最小函数值。

  1. 先算当前梯度 v=∇f(xk),在这次线搜索中保持它不变。
  2. 试不同 α,每次计算候选点 xk−αv 的目标值。
  3. 选使这条线上的目标值最小的 α,再更新参数。

多维问题暂时变成了只有一个未知数的优化。若 f 凸,沿直线限制得到的 g 也凸。在前面的二次例子中,直接求导得到这一轮的最优步长 548/6504≈0.08426。一般函数需要一维搜索来求它。

对应课堂录音Week07 Part01 02:04:42–02:08:46
原第 25 页

先把无限搜索范围缩成有限区间

原课件第25页
点击原页可打开 PDF。

要在 [0,∞) 上搜索,先找一个足够大的右端点 α0。本页后续统一使用 g(α)=e−α+α2. 它的二阶导数为 g″(α)=e−α+2>0,所以严格凸。

我们的目标是找到一个右端点,使它前面已有更低的函数值。例如 g(0.25)≈0.84130,而 g(0.5)≈0.85653,说明到 0.5 时已经开始回升。

对于凸函数,相邻区间的割线斜率不会下降。以任意 b>0.5 为例,g(b)−g(0.5)b−0.5≥g(0.5)−g(0.25)0.5−0.25≈0.0609>0. 左边分母为正,故 g(b)>g(0.5)。右端之外都更高,可以在 [0,0.5] 内找最小点。

得到有限区间后,就能用网格搜索或黄金分割继续缩小范围。

对应课堂录音Week07 Part01 00:26:35–00:32:16Week07 Part01 02:10:34–02:16:06Week07 Part01 02:18:21–02:24:13Week07 Part01 02:29:02–02:34:44
原第 26 页

用倍增法自动找右端点

原课件第26页
点击原页可打开 PDF。

课件从 α=0.125 开始。只要新的试探值还在下降,就把步长翻倍;遇到回升时,当前步长可作右端点。

import numpy as np

def g(alpha):
    return np.exp(-alpha) + alpha**2

alpha = 0.125
previous = g(0.0)
while True:
    current = g(alpha)
    if current >= previous:
        upper = alpha
        break
    previous = current
    alpha = 2 * alpha
print(upper)
  1. 起点 g(0)=1。试 0.125,得到 0.89812,下降,继续。
  2. 把步长翻倍到 0.25,得到 0.84130,仍下降,继续。
  3. 翻倍到 0.5,得到 0.85653,高于上一点 0.84130,因此停止。
  4. 取右端点 upper=0.5,接着在 [0,0.5] 内找谷底。

变量 previous 每次保存的是上一次试探点的函数值,不是一直保存 g(0)。程序用于实际数据时,再加上最大试探次数,便于处理沿该方向一直下降的情况。

对应课堂录音Week07 Part01 02:18:21–02:24:13Week07 Part01 02:29:02–02:34:44
原第 27 页

网格搜索:最容易实现的一维搜索

原课件第27页
点击原页可打开 PDF。

确定区间以后,最直接的办法是均匀取很多个候选步长,全部算一遍,再选函数值最低的那个。这就是网格搜索。

import numpy as np

alphas = np.linspace(0.0, 0.5, 51)
values = np.exp(-alphas) + alphas**2
index = np.argmin(values)
alpha_best = alphas[index]
print(alpha_best, values[index])
  1. 0 到 0.5 之间取 51 个点,相邻间距是 0.01。
  2. 对 51 个步长分别算目标值,argmin 返回最小值所在的位置编号。
  3. 再用这个编号取出对应步长,得到 α=0.35,函数值约 0.82718809。

真正的最小点约为 0.35173371,网格没有恰好取到它。把间距改成 0.001 可以更精细,但候选点数量也约增加十倍。网格法适合先找大概位置;若需要很高精度,逐步缩小区间更省计算。

对应课堂录音Week07 Part01 02:04:42–02:08:46Week07 Part01 02:10:34–02:16:06Week07 Part01 02:41:04–02:42:46
原第 28 页

只看一个中点,还不能决定丢哪一半

原课件第28页
点击原页可打开 PDF。

图中左右红线是当前边界 0 和 0.5,中间红线在 0.25。蓝曲线是 g(α)=e−α+α2。现在要在这个小区间里继续定位谷底。

只知道中点函数值低于两个端点,还不能判定最小点在它左边还是右边:谷底可能略偏左,也可能略偏右。这个例子里谷底在 0.25 右边,但算法不能靠“看起来像”决定。

改进办法是:在区间内部放两个有顺序的点 u<v,比较 g(u) 与 g(v)。如果右点更低,就能排除左端的一部分;如果左点更低,就排除右端的一部分。下面的黄金分割法就是按这个原则不断缩小区间。

例如区间为 [0,0.5],分别看 gL(α)=(α−0.2)2 与 gR(α)=(α−0.3)2。两者在中点0.25的值都为0.0025,而且都低于各自两个端点;但一个谷底在中点左边0.2,另一个在右边0.3。仅凭“中点低于两端”,无法选择保留哪半边。

对应课堂录音Week07 Part01 02:24:13–02:27:28
原第 29 页

黄金分割比例为什么是 0.618

原课件第29页
点击原页可打开 PDF。

黄金分割法不仅要缩小区间,还希望旧的内部点能在新区间中继续使用。这样每轮只需要新计算一个函数值。

本页图中的小写 a,b,c 是线段长度,与后面代码中代表区间端点的 a、b 含义不同。设 b 是原区间长度,某次缩短后保留长度 a。原来被舍掉的一段长度为 c=b−a。看保留右侧的情况,旧右试探点距原右端就是 c。当它成为新区间的左试探点时,距新右端的距离应为新区间长度乘以比例 r=a/b。因此要让它保持原位置,需令 c/a=a/b,即 (b−a)/a=a/b。

  1. 因为 a=rb,所以 (b−a)/a=(1−r)/r。
  2. 令它等于 r,得 1−r=r2,即 r2+r−1=0。
  3. 解二次方程,取正根:r=5−12≈0.618034.

因此对于长度为 L 的区间,内部点放在距左端约 0.382L 和 0.618L 的位置。两点关于中点对称。每次舍去一端,剩余长度约为原长度的 0.618 倍。

对应课堂录音Week07 Part01 02:24:13–02:27:28Week07 Part01 02:29:02–02:34:44
原第 30 页

黄金分割如何复用旧点

原课件第30页
点击原页可打开 PDF。

设当前区间为 [A,B],长度 L=B−A,取 u=A+(1−r)L,v=A+rL,r≈0.618034.

  1. 若 g(u)>g(v),左点比右点高。凸曲线的谷底不可能在 [A,u),所以保留 [u,B]。
  2. 新区间长度为 B−u=rL。旧点 v 距新左端 u 的距离为 (2r−1)L。
  3. 由 r2=1−r 可得 2r−1=(1−r)r。所以旧点 v 恰好落在新区间应放的左内部点位置。
  4. 旧点的函数值已知,只需再计算一个新的右内部点。

若 g(u)<g(v),则对称地保留 [A,v],旧左内部点成为新右内部点。若两值相等,凸性保证 [u,v] 内至少有一个最小点,两边任选一个保留都可以。初始算两个值,以后每轮只新增一次函数计算。

对应课堂录音Week07 Part01 02:29:02–02:34:44
原第 31 页

把缩区间的动画拆成三轮

原课件第31页
点击原页可打开 PDF。

原页用图展示区间逐轮变窄。红虚线是当前边界,两个蓝点是内部试探点,黑曲线是目标函数。用本例的实际数值把过程拆开:

  1. 初始区间 [0,0.5],内部点约为 0.190983、0.309017;函数值约为 0.862621、0.829660。右点更低,丢掉左边,保留 [0.190983,0.5]。
  2. 新内部点约为 0.309017、0.381966;函数值约为 0.829660、0.828416。右点仍低,保留 [0.309017,0.5]。
  3. 新内部点约为 0.381966、0.427051;函数值约为 0.828416、0.834803。这次左点更低,保留 [0.309017,0.427051]。

最小点约 0.351734,始终留在新区间里。

原第 32 页

代码分支一:左点较低,更新右边界

原课件第32页
点击原页可打开 PDF。

代码先初始化黄金比例、两个内部点及函数值:

phi = (np.sqrt(5) - 1) / 2
alpha1 = a + (1-phi)*(b-a)
alpha2 = a + phi*(b-a)
g1, g2 = g(alpha1), g(alpha2)

若 g1 < g2,保留左侧区间,按顺序执行:

b = alpha2
alpha2 = alpha1
g2 = g1
alpha1 = a + (1-phi)*(b-a)
g1 = g(alpha1)
  1. 把旧右内部点作为新右端点。
  2. 把旧左内部点移动到“新右内部点”这个角色,连同已有函数值一起复用。
  3. 用新区间重新算左内部点,只在这个新点计算一次 g。

例如区间 [0.309017,0.5],两内部点为 0.381966、0.427051,左点较低。执行后保留 [0.309017,0.427051],旧 0.381966 成为新右内部点。外层条件 while b-a > tol 表示只要区间仍宽于容差,就继续缩。

对应课堂录音Week07 Part01 02:34:46–02:41:03
原第 33 页

代码分支二:右点较低,更新左边界

原课件第33页
点击原页可打开 PDF。

与上一页对称。如果 g1 >= g2,保留右侧区间:

a = alpha1
alpha1 = alpha2
g1 = g2
alpha2 = a + phi*(b-a)
g2 = g(alpha2)
  1. 旧左内部点成为新左端点。
  2. 旧右内部点成为新左内部点,旧 g2 直接改名为新 g1。
  3. 计算一个新右内部点和它的函数值。

例如初始区间 [0,0.5],因为 g(0.190983)>g(0.309017),执行后左端点变为 0.190983,旧 0.309017 被保留下来,新右内部点为 0.381966。

把两页的分支放进同一个 if ... else ...,每轮只执行其中一个。区间宽度达到容差后,返回中点估计最小点。因为区间包含真实最小点,中点与它的误差最多为区间宽度的一半。

运行包含两个分支的完整黄金分割搜索
import numpy as np

def g(alpha):
    return np.exp(-alpha) + alpha**2

a, b = 0.0, 0.5
tol = 1e-6
phi = (np.sqrt(5) - 1) / 2
alpha1 = a + (1-phi)*(b-a)
alpha2 = a + phi*(b-a)
g1, g2 = g(alpha1), g(alpha2)

while b-a > tol:
    if g1 < g2:
        b = alpha2
        alpha2, g2 = alpha1, g1
        alpha1 = a + (1-phi)*(b-a)
        g1 = g(alpha1)
    else:
        a = alpha1
        alpha1, g1 = alpha2, g2
        alpha2 = a + phi*(b-a)
        g2 = g(alpha2)

alpha_min = (a+b) / 2
print(alpha_min, g(alpha_min))

程序会打印步长约 0.351734、最小目标值约 0.827184。形如 alpha2, g2 = alpha1, g1 的一行把旧位置和它的函数值一起保存,避免对同一个点再调用一次 g。

对应课堂录音Week07 Part01 02:34:46–02:41:03
原第 34 页

直接调用一维求解器

原课件第34页
点击原页可打开 PDF。

理解算法以后,可以直接让 SciPy 完成黄金分割搜索:

import numpy as np
from scipy.optimize import minimize_scalar

def g(alpha):
    return np.exp(-alpha) + alpha**2
result = minimize_scalar(g, method='golden', bracket=(0, 0.5))
print(result.x)
print(result.fun)
  1. g 输入一个步长,返回一个目标值。
  2. method='golden' 选择黄金分割法;bracket 提供初始搜索信息。
  3. result.x 是最小点,约为 0.35173371;result.fun 是最小函数值,约为 0.82718403。

这里的 bracket=(0,0.5) 不是强制边界,求解器可以继续扩展搜索。如果任务要求严格限制在指定区间,可用 minimize_scalar(g, bounds=(0, 0.5), method='bounded')。本例的最小点位于区间内部,两种方式都能找到它。

对应课堂录音Week07 Part01 02:04:42–02:08:46Week07 Part01 02:41:04–02:42:46Week08 Part01 00:00:20–00:06:46Week08 Part01 00:29:57–00:35:19
原第 35 页

把固定步长程序改成线搜索

原课件第35页
点击原页可打开 PDF。

本页重放第 22 页逻辑回归程序,让我们只替换选步长的部分。数据 X,y、当前参数 w、预测 p 和平均梯度 v=XT(p−y)/N 全部保持原来的计算方式。

  1. 第22页原来的更新行是 w = w - step_size * gradient,其中 step_size 固定为 1。
  2. 现在定义一维函数 g(α)=L(w−αv)。这里 L 是平均交叉熵。
  3. 在这一轮中保持 w 和 v 不变,试多个 α,由一维求解器找到更合适的值。
  4. 再执行 w←w−αv。进入下一轮后,重新计算新的梯度和新的一维函数。
对应课堂录音Week07 Part01 00:41:13–00:46:39Week07 Part01 01:59:13–02:04:42Week08 Part01 00:29:57–00:35:19
原第 36 页

逻辑回归的精确线搜索代码

原课件第36页
点击原页可打开 PDF。

先运行第20页生成数据,再沿用第22页的训练循环。把下面的导入放到循环前,把后续代码整体缩进一级,替换循环里的 w = w - step_size * gradient。这样检查完停止条件后,才为当前这一步搜索步长。

from scipy.optimize import minimize_scalar

# Insert the following code inside the training loop.
def g(alpha):
    w_new = w - alpha * gradient
    z_new = X @ w_new
    return np.mean(np.logaddexp(0, z_new) - y*z_new)

result = minimize_scalar(g, method='golden', bracket=(0, 50))
learning_rate = result.x
w = w - learning_rate * gradient
  1. w_new 是候选参数,还没有覆盖当前 w。
  2. 用候选参数计算新分数 z_new。
  3. logaddexp(0,z_new) 稳定地计算 log(1+ezi),返回当前候选步长对应的平均交叉熵。
  4. 求解器会多次调用 g,比较不同步长。
  5. 取出搜索得到的步长,才真正更新 w。第一次从零参数出发时,result.x 约为 3.10831,result.fun 约为 0.65780;第22页固定步长 1 的对应损失约为 0.67391。

第23页推导了这里的损失写法。每次调用 g 都会重新处理全部 1000 条数据,因此线搜索会增加每轮耗时。

对应课堂录音Week08 Part01 00:29:57–00:35:19
原第 37 页

精确线搜索为什么轮数少,却未必省时间

原课件第37页
点击原页可打开 PDF。

横轴是外层迭代次数,纵轴是梯度范数,对数坐标。蓝线用固定步长,橙线用精确线搜索。图中橙线下降更快,在大约四万多轮达到很小的梯度,蓝线则要十几万轮。

但横轴一轮,并不代表相同的计算量:

  1. 固定步长每轮算一次梯度,直接更新。
  2. 精确线搜索每轮除了梯度,还需多次计算候选参数下的损失。
  3. 一维求解器若为了更精确的步长做很多次函数评价,单轮就会明显更慢。

第36页的第一个线搜索可通过 result.nfev 检查函数评价次数。一次运行中,求解器调用了 49 次 g,每次都用到 1000 条数据。对比总耗时前,要把这部分重复计算也算进去。

对应课堂录音Week08 Part01 00:06:46–00:10:12
原第 38 页

策略三:非精确线搜索

原课件第38页
点击原页可打开 PDF。

精确线搜索要尽量找到 g(α) 的谷底。非精确线搜索的想法更直接:只要某个步长带来的下降够明显,就接受它。

沿负梯度仍使用 g(α)=f(xk−α∇f(xk))。方向没有改变,改变的是挑步长的要求。

  1. 先试一个较大的候选步长。
  2. 检查新函数值有没有达到规定的下降量。
  3. 如果没有,缩小步长再试。
  4. 一旦满足要求,立即更新参数,不再追求这条线的最小点。
对应课堂录音Week07 Part01 02:04:42–02:08:46Week08 Part01 00:06:46–00:10:12
原第 39 页

参考直线:什么叫下降得足够多

原课件第39页
点击原页可打开 PDF。

先算沿负梯度的初始斜率。令 v=∇f(xk),则 g′(0)=∇f(xk)T(−v)=−vTv=−‖v‖22. 梯度不为零时,这个数严格为负。

出发点的切线是 g(0)−α‖v‖22。但对凸曲线,切线在曲线下方,直接要求函数低于切线通常做不到。于是选 0<γ<1,把斜率缩缓,得到稍高的参考线:

g(0)−γα‖v‖22.

要求候选点位于这条参考线下方:g(α)≤g(0)−γα‖v‖22. 这就是 Armijo 充分下降条件。

参考线和曲线都从 g(0) 出发,但曲线的初始斜率更负。只要 v≠0,两者之差在起点的导数为 −(1−γ)‖v‖22<0,所以曲线在足够小的正 α 处会落到参考线下方。图中的另一处交点由蓝色竖线标出。对这条凸曲线,从零到该交点的步长都满足条件。

对应课堂录音Week08 Part01 00:06:46–00:10:12Week08 Part01 00:10:13–00:15:33Week08 Part01 00:15:34–00:19:38Week08 Part01 00:19:43–00:24:30
原第 40 页

回溯线搜索:不合格就乘一个小于一的数

原课件第40页
点击原页可打开 PDF。

取缩小比例 0<ρ<1 和下降参数 0<γ<0.5。课件把缩小比例写作 β。先运行第20页生成数据。把 def loss 放在第22页训练循环前,把 alpha = 50.0 到末尾整体缩进一级,替换循环里的固定步长更新行。

def loss(params):
    z = X @ params
    return np.mean(np.logaddexp(0, z) - y*z)

alpha = 50.0
rho = 0.5
gamma = 0.25
value_now = loss(w)
grad_sq = gradient @ gradient
while loss(w - alpha*gradient) > value_now - gamma*alpha*grad_sq:
    alpha = rho * alpha
w = w - alpha*gradient
  1. value_now 是当前参数的平均损失,gradient @ gradient 是当前梯度各分量的平方和。它们在这一轮回溯中固定。
  2. 先试 α=50,用候选参数计算新的平均损失,和参考线上同一横坐标对应的值比较。每个外层迭代重新从 50 开始。
  3. 若新损失高于参考线,就把步长乘 ρ,例如 50 → 25 → 12.5。
  4. 直到新损失低于或等于参考线,退出循环并更新。

具体算一轮:f(x)=x2,当前 x=2,梯度为 4,f(x)=4。取 γ=0.25,为便于手算,先试 α=1,新点 −2,目标 4,而参考值 4−0.25×1×16=0,不合格。缩到 0.5,新点 0、目标 0,参考值为 2,满足 0≤2,接受。

核对逻辑回归第一轮:哪一个步长通过?

零参数的平均损失为 log2≈0.69315,平均梯度的平方范数约为 0.02303。每次用新的 α 算两列,并判断候选损失是否小于等于参考值。

步长候选损失参考值判断
503.180910.40524减半
251.605140.54919减半
12.50.906480.62117减半
6.250.690530.65716减半
3.1250.657800.67515接受

最后一行的参考值来自 0.69315−0.25(3.125)(0.02303)≈0.67515。这一轮共减半四次,更新只使用通过检查的 3.125。

对应课堂录音Week07 Part01 01:59:13–02:04:42Week08 Part01 00:10:13–00:15:33Week08 Part01 00:15:34–00:19:38Week08 Part01 00:19:43–00:24:30Week08 Part01 00:24:31–00:27:29Week08 Part01 00:29:57–00:35:19
原第 41 页

三种步长放在一起比较

原课件第41页
点击原页可打开 PDF。

蓝线是固定步长,橙线是精确线搜索,绿线是非精确线搜索。纵轴仍为梯度范数,横轴仍为外层迭代次数。

  1. 蓝线在这次演示中下降较慢,到同一精度需要更多外层迭代。
  2. 橙线与绿线大部分重合,说明非精确线搜索即使没有把每轮步长求到最精细,也能在这份数据上得到近似的外层收敛速度。
  3. 非精确线搜索只需检查下降是否达标。第一次试探就通过时,只需额外评价一次候选点的损失;回退一次,就再评价一次。

以梯度范数降到约 10−7 为例,图上精确和非精确线搜索大约在 4 万轮达到,固定步长大约在 11 万轮达到。按第40页的参数重复运行,梯度范数达到第22页的 10−8 停止阈值约需 4.33 万次更新。图中的横轴只计外层迭代,总耗时还取决于每轮评价多少次损失。

对应课堂录音Week08 Part01 00:35:23–00:42:18
原第 42 页

牛顿法第一步:在当前位置造一个二次近似

原课件第42页
点击原页可打开 PDF。

回到简单的一维函数 g(α)=e−α+α2,当前点取 a0=0.1。牛顿法先用一个好求最小值的抛物线,近似当前位置附近的原函数。

  1. 求导:g′(α)=−e−α+2α,g″(α)=e−α+2。
  2. 代入 0.1,得到 g(0.1)≈0.91483742,g′(0.1)≈−0.70483742,g″(0.1)≈2.90483742。
  3. 泰勒展开保留到二阶:q(α)=g(0.1)+g′(0.1)(α−0.1)+12g″(0.1)(α−0.1)2.
  4. 代入数字:q(α)≈0.91483742−0.70483742(α−0.1)+1.45241871(α−0.1)2.

q 与原函数在当前点具有相同的函数值、斜率和曲率。图中两条曲线在 0.1 附近很接近,所以可以先求 q 的最低点作为下一次位置。

对应课堂录音Week08 Part01 00:35:23–00:42:18Week08 Part01 00:42:18–00:50:24
原第 43 页

把近似抛物线的最低点当作下一步

原课件第43页
点击原页可打开 PDF。

上一页已经得到二次近似 q。对它求导并令导数为零:

q′(α)=g′(a0)+g″(a0)(α−a0)=0.

于是得到一维牛顿更新 a1=a0−g′(a0)g″(a0).

  1. 从 a0=0.1 开始,a1=0.1−−0.704837422.90483742≈0.34264264.
  2. 在新点重新计算原函数的一阶、二阶导数,再更新,得到 a2≈0.35172292。
  3. 重复一次得到 a3≈0.35173371,已经非常接近真正最小点。

每一步都在新位置重建近似,不是反复使用最初那条抛物线。原函数含指数不好直接求根,二次近似却容易解,这就是牛顿法的核心思路。

对应课堂录音Week08 Part01 00:42:18–00:50:24Week08 Part01 00:50:27–00:56:51Week10 Part01 00:26:19–00:28:22
原第 44 页

多维牛顿法:由最小化二次模型推出来

原课件第44页
点击原页可打开 PDF。

多维变量用位移 s=x−xk 表示,记当前梯度 v=∇f(xk)、Hessian H=∇2f(xk)。二次近似是 q(s)=f(xk)+vTs+12sTHs.

  1. 常数 f(xk) 对位移的导数为零。
  2. 一次项 vTs 的梯度是 v。
  3. 把二次项写成 12∑i∑jHijsisj。对 sr 求导,每次 sr 出现在左边产生 12∑jHrjsj,出现在右边产生 12∑iHirsi。因为 Hir=Hri,这两半相加就是 ∑jHrjsj=(Hs)r。因此完整的二次项梯度为 Hs。
  4. 令模型梯度为零:v+Hs=0,解线性方程 Hs=−v。
  5. 若 H 正定,二次模型有唯一最小点 s=−H−1v,所以 xk+1=xk−H−1∇f(xk).

实现时直接解 Hs=−v。若 H 正定且 v≠0,则 vTs=−sTHs<0,所以 s 是下降方向,二次模型给它的完整步幅仍需要适合原函数。若 H 不正定,需先确认或修正方向,再决定沿它走多远。

Hessian怎样决定下一步:取 f(x)=12x12+5x22,当前点为 (1,1)。梯度 v=(1,10)T,Hessian为 H=[10010]。解 Hs=−v 就是解 s1=−1、10s2=−10,所以位移为 (−1,−1),新点为 (0,0)。第二个方向的梯度大10倍,但曲率也大10倍;除去曲率影响后,这个方向同样只需移动1。普通梯度步若取步长0.1,会到 (0.9,0)。

对应课堂录音Week08 Part01 00:50:27–00:56:51Week08 Part01 00:59:31–01:05:02Week08 Part01 01:07:38–01:09:30
原第 45 页

逻辑回归为什么适合这个牛顿练习

原课件第45页
点击原页可打开 PDF。

对于逻辑回归的损失总和,梯度已经是 v=XT(p−y)。再对参数求一次导数:

  1. 每个 pi 对分数的导数为 pi(1−pi)。
  2. 把这些数放在对角线上:D=diag(p1(1−p1),…,pn(1−pn))。
  3. 梯度的第 j 个分量是 ∑iXij(pi−yi)。对 wk 求导时,Xij,yi 固定,而 ∂pi/∂wk=pi(1−pi)Xik。因此 Hjk=∑iXijpi(1−pi)Xik. 左乘 XT 会把各行贡献相加,乘对角矩阵 D 则给各行乘上各自的权重,所以矩阵形式是 H=XTDX。
  4. 对任意向量 u,uTHu=∑ipi(1−pi)(Xiu)2≥0,所以损失凸。
  5. 每轮解 Hstep=v,再令 w←w−step。这里 step 是代码中要减去的量;第44页的位移 s=−step。若所有权重正且 X 满列秩,Hessian 正定。

本例有 1000 个样本、3 个参数,所以 X 为 1000×3,D 为 1000×1000,最终 Hessian 只有 3×3。梯度和 Hessian 若都除以 N,牛顿位移不变,因为用平均损失解的是 (H/N)step=v/N,两边同乘 N 就回到 Hstep=v。

两条样本做一轮牛顿更新:取 X=[1011]、y=(0,1)T,从 w=(0,0)T 开始。此时 p=(0.5,0.5)T,所以 v=XT(p−y)=[0−0.5],D=[0.25000.25],H=[0.50.250.250.25]. 解 Hstep=v:第一式为 0.5step0+0.25step1=0,第二式为 0.25step0+0.25step1=−0.5。相减得 step0=2,再得 step1=−4,因此 w1=(0,0)−(2,−4)=(−2,4)。两条样本的新分数为−2和2,正确标签概率都约为0.88080,损失总和从 2log2≈1.38629 降到约0.25386。

对应课堂录音Week08 Part01 01:07:38–01:09:30
原第 46 页

逐句实现牛顿法,不必真的构造大对角矩阵

原课件第46页
点击原页可打开 PDF。

先运行第20页得到数据。下面的程序使用逐行加权来计算 DX,计算结果与先创建矩阵 D 再乘 X 一致。

from scipy.special import expit
w = np.zeros(X.shape[1])
for k in range(100):
    p = expit(X @ w)
    gradient = X.T @ (p-y)
    if np.linalg.norm(gradient) < 1e-10:
        break
    weights = p*(1-p)
    H = X.T @ (weights[:, None]*X)
    step = np.linalg.solve(H, gradient)
    w = w - step
z = X @ w
print(w)
print(np.mean(np.logaddexp(0, z) - y*z))
  1. expit 稳定地计算 sigmoid。
  2. 梯度是损失总和的梯度,这里没有除以 N。
  3. weights[:,None] 把 1000 个权重变成一列,再分别乘到 X 的每一行上;结果就是 DX。例如第45页的小矩阵中,权重为 (0.25,0.25)T,两行加权后得到 [0.2500.250.25]。课件的 1000 条数据做的是同一种广播运算。
  4. 左乘 XT 得到 3×3 的 Hessian。
  5. solve(H, gradient) 解 Hstep=gradient,再从参数中减去这个位移。课件用 inv(H) @ gradient 直接表达同一公式。

第一轮从零参数出发,pi=0.5,得到的更新后参数约为 (13.69149,1.58232,−11.74069)。之后每轮重新计算概率、梯度和 Hessian,逐步接近最后的解。

对应课堂录音Week08 Part01 01:16:59–01:17:30Week08 Part01 01:19:22–01:24:44
原第 47 页

读最终结果:牛顿法快在哪里,成本在哪里

原课件第47页
点击原页可打开 PDF。

右侧列表从迭代 0 的初始点开始,给出每次的损失总和梯度范数:

已完成更新次数梯度范数
0151.76568
141.67301
217.27175
37.58022
42.99918
50.82229
60.10801
70.003368
8约 7.52×10⁻⁶
9约 8.8×10⁻¹¹

九次更新后,参数约为 (96.88708,9.83687,−82.47006),平均交叉熵约为 0.11811702,与前面的现成求解器相符。左图中的梯度下降需许多轮,右边牛顿法只用个位数到十轮左右,差别很明显。

这里的 Hessian 只有 3×3。若有 N 个样本和 d 个参数,直接形成稠密的 XTDX 要累加 d2 个长度为 N 的内积,运算量约为 Nd2。矩阵占 d2 个数,再直接解线性方程的运算量约为 d3。第46页省去的是 N×N 的对角矩阵,仍需计算和求解 d×d 的 Hessian。

对应课堂录音Week08 Part01 01:19:22–01:24:44