5D Library › 信息几何、费希尔信息度量与自然梯度优化的统计流形 · English

第四章 自然梯度:不变性、速度与近似

「最陡」是相对于度量而言的

梯度下降 θ←θ−η∇L\theta \leftarrow \theta – \eta\nabla L 被说成「沿最陡方向下降」。但「最陡」需要先规定怎样度量步子的大小:梯度方向是在欧氏度量下、长度固定的步子中使损失下降最多的方向。换一套参数,欧氏长度变了,最陡方向也就变了。严格地说,梯度 ∂iL\partial_i L 是一个余向量,它按 J⊤J^\top 变换,而参数的增量是切向量,按 J−1J^{-1} 变换;把两者直接相减,结果依赖坐标。

如果用统计流形上的费希尔度量来规定步长,问题就变成:在 12dθ⊤Gdθ=ε2\tfrac12 d\theta^\top G\, d\theta = \varepsilon^2(即分布的 KL 变化约为 ε2\varepsilon^2)的约束下使 L(θ+dθ)L(\theta + d\theta) 下降最多。拉格朗日乘子法给出

dθ∝−G(θ)−1∇L(θ),d\theta \;\propto\; -\,G(\theta)^{-1}\nabla L(\theta) ,

甘利俊一称之为自然梯度 (Amari 1998)。G−1G^{-1} 把余向量「升」为切向量,所以 G−1∇LG^{-1}\nabla L 是一个几何对象,不依赖坐标。

证据

甘利 1998 年说了什么。 论文《自然梯度在学习中高效工作》载于《神经计算》第 10 卷第 2 期第 251–276 页 (Amari 1998)。它在黎曼参数空间中定义了最陡下降方向;证明了在线(逐个样本)的自然梯度学习在渐近意义下是费希尔有效的,即其估计误差达到第二章的克拉美—拉奥界;并认为自然梯度可以使多层感知器学习中的「平台」现象消失或减轻。后来,卡卡德把这一思想用于强化学习中的策略梯度 (Kakade 2001),帕斯卡努与本吉奥讨论了它与深度网络中其他二阶方法的关系 (Pascanu and Bengio 2014),奥利维耶等人把它推广为一类以不变性为原则的优化算法 (Ollivier et al. 2017)。

作者框架说甘利 1998 年给出了「自然梯度在病态山谷中消除坐标依赖震荡的证明」。核对后应改写为一个更弱但确实成立的事实:当费希尔矩阵等于损失的黑塞矩阵时——例如负对数似然是参数的二次函数,或典范连接的广义线性模型(逻辑回归、泊松回归)——自然梯度步就是牛顿步,而牛顿法在二次型上一步到达最小值,不受条件数影响。当损失是以网络输出为自然参数的指数族负对数似然时(例如平方误差、softmax 交叉熵),费希尔矩阵等于广义高斯—牛顿矩阵(一种总是半正定的曲率近似)(Martens 2020);这仍然不是黑塞矩阵。一般情形下二者并不相等,对一般的非凸问题也没有「消除震荡」的保证。

不变性:对流成立,对步只在一阶成立

自然梯度的不变性在什么意义上成立?考虑连续时间的流 θ̇=−G−1∇L\dot\theta = -G^{-1}\nabla L。在新坐标 ξ\xi 中,ξ̇=−Gξ−1∇ξL=−(J⊤GJ)−1J⊤∇θL=−J−1G−1∇θL=J−1θ̇\dot\xi = -G_\xi^{-1}\nabla_\xi L = -(J^\top G J)^{-1}J^\top\nabla_\theta L = -J^{-1}G^{-1}\nabla_\theta L = J^{-1}\dot\theta,所以两条轨迹描述的是同一条分布的路径。但实际算法走的是离散的一步:θk+1=θk−ηG−1∇L\theta_{k+1} = \theta_k – \eta G^{-1}\nabla L 是参数空间中的一条直线,而一套坐标中的直线在另一套坐标中一般是曲线。两套坐标中的离散步因此只在一阶上一致,差别是 O(η2)O(\eta^2) 每步、在固定时间内累积为 O(η)O(\eta)。马滕斯 2020 年的综述把这称为「近似的参数化不变性」(Martens 2020)。例外是仿射(线性)重参数化:直线仍映为直线,GG 按 J⊤GJJ^\top GJ 变换,离散的自然梯度步逐步对应,因而精确不变;一阶不变的结论针对非线性重参数化,下面程序中的 B、C、D 三套坐标相对于 A 都属于这种情况。

推导

# Is the natural gradient "parametrisation invariant"? Fit N(mu, sigma^2) to data with
# mean 1 and variance 4 (average negative log-likelihood), starting at (0, 0.5), in four
# coordinate systems: A (mu, sigma), B (mu, log sigma), C (mu, sigma^2) and D the
# expectation parameters (mu, mu^2 + sigma^2). K steps of size eta, eta * K = 2 fixed.
# The natural-gradient FLOW is the same in every chart; discrete steps differ by O(eta).
# Plain gradient descent differs by O(1). At eta = 1 the chart matters a great deal.
import math

M, V = 1.0, 4.0
CHARTS = {   # to (mu, sigma), from (mu, sigma), Jacobian d(mu, sigma)/d(theta)
    "A (mu, sigma)": (lambda t: t, lambda m, s: (m, s),
                      lambda t: ((1, 0), (0, 1))),
    "B (mu, log s)": (lambda t: (t[0], math.exp(t[1])), lambda m, s: (m, math.log(s)),
                      lambda t: ((1, 0), (0, math.exp(t[1])))),
    "C (mu, s^2)": (lambda t: (t[0], math.sqrt(t[1])), lambda m, s: (m, s * s),
                    lambda t: ((1, 0), (0, 0.5 / math.sqrt(t[1])))),
    "D expectation": (lambda t: (t[0], math.sqrt(t[1] - t[0] ** 2)),
                      lambda m, s: (m, m * m + s * s),
                      lambda t: ((1, 0), (-t[0] / math.sqrt(t[1] - t[0] ** 2),
                                          0.5 / math.sqrt(t[1] - t[0] ** 2))))}

def grad_ms(m, s):                       # gradient of log s + ((M-m)^2 + V)/(2 s^2)
    q = (M - m) ** 2 + V
    return (-(M - m) / s ** 2, 1 / s - q / s ** 3)

def run(chart, eta, K, natural=True):
    to, frm, jac = CHARTS[chart]; t = list(frm(0.0, 0.5))
    for _ in range(K):
        m, s = to(t); gm, gs = grad_ms(m, s); J = jac(t)
        g = [J[0][0] * gm + J[1][0] * gs, J[0][1] * gm + J[1][1] * gs]   # J' grad
        if natural:                                       # F = J' diag(1/s^2, 2/s^2) J
            a = (J[0][0] ** 2 + 2 * J[1][0] ** 2) / s ** 2
            b = (J[0][0] * J[0][1] + 2 * J[1][0] * J[1][1]) / s ** 2
            d = (J[0][1] ** 2 + 2 * J[1][1] ** 2) / s ** 2
            det = a * d - b * b; g = [(d * g[0] - b * g[1]) / det,
                                      (a * g[1] - b * g[0]) / det]
        t = [t[0] - eta * g[0], t[1] - eta * g[1]]
        try:
            m, s = to(t)
        except (ValueError, OverflowError):
            return None
        if not (s > 0) or abs(m) > 1e6:
            return None
    return to(t)

def kl(a, b):
    return math.log(b[1] / a[1]) + (a[1] ** 2 + (a[0] - b[0]) ** 2) / (2 * b[1] ** 2) - .5

flow = run("A (mu, sigma)", 1e-4, 20_000)
print(f"reference flow (A, eta 1e-4, 20,000 steps) at time 2: mu {flow[0]:.4f},"
      f" sigma {flow[1]:.4f}")
for natural in (True, False):
    print(("natural gradient" if natural else "plain gradient") +
          ": KL(flow || end point) per chart; spread = largest KL between charts")
    print("     eta     K    " + "  ".join(f"{c:>13s}" for c in CHARTS) + "   spread")
    for eta in (1.0, 0.5, 0.1, 0.02, 0.004):
        K = round(2 / eta); ends = [run(c, eta, K, natural) for c in CHARTS]
        cells = [f"{kl(flow, e):13.2e}" if e else f"{'diverged':>13s}" for e in ends]
        ok = [e for e in ends if e]
        spr = max(kl(a, b) for a in ok for b in ok) if len(ok) > 1 else float("nan")
        print(f"   {eta:5.3f} {K:5d}    " + "  ".join(cells) + f"  {spr:8.1e}")
one = run("D expectation", 1.0, 1)
print(f"one natural step of size 1 in chart D lands on (mu, sigma) = ({one[0]:.4f},"
      f" {one[1]:.4f}), the MLE")
# reference flow (A, eta 1e-4, 20,000 steps) at time 2: mu 0.8647, sigma 1.8999
# natural gradient: KL(flow || end point) per chart; spread = largest KL between charts
#      eta     K    A (mu, sigma)  B (mu, log s)    C (mu, s^2)  D expectation   spread
#    1.000     2         1.60e-01       7.17e+00       4.84e-03       4.84e-03   2.1e+06
#    0.500     4         1.57e-02       2.17e+00       1.98e-03       1.51e-03   9.5e+01
#    0.100    20         2.17e-04       7.23e-04       7.89e-05       5.81e-05   4.5e-04
#    0.020   100         7.49e-06       1.45e-05       3.10e-06       2.27e-06   6.5e-06
#    0.004   500         2.83e-07       5.43e-07       1.16e-07       8.44e-08   2.5e-07
# plain gradient: KL(flow || end point) per chart; spread = largest KL between charts
#      eta     K    A (mu, sigma)  B (mu, log s)    C (mu, s^2)  D expectation   spread
#    1.000     2         2.51e+00       1.62e+01       8.50e-01       7.07e-01   2.4e+13
#    0.500     4         1.83e+00       6.17e+00       4.59e-01       3.80e-01   7.4e+04
#    0.100    20         3.54e-01       1.79e-02       1.03e-02       8.62e-03   9.0e-01
#    0.020   100         1.50e-02       1.88e-02       9.98e-02       1.56e-01   1.8e-01
#    0.004   500         1.32e-02       1.89e-02       1.09e-01       1.67e-01   1.9e-01
# one natural step of size 1 in chart D lands on (mu, sigma) = (1.0000, 2.0000), the MLE

程序用四套坐标拟合同一个正态分布:(μ,σ)(\mu, \sigma)、(μ,log⁡σ)(\mu, \log\sigma)、(μ,σ2)(\mu, \sigma^2) 与期望参数 (μ,μ2+σ2)(\mu, \mu^2 + \sigma^2),固定总「时间」ηK=2\eta K = 2。参照的连续流在时间 2 时到达 μ=0.8647\mu = 0.8647、σ=1.8999\sigma = 1.8999。自然梯度下,四套坐标的终点与参照流的 KL 差距随步长减小而迅速缩小:η=0.1\eta = 0.1 时为 10−410^{-4} 量级,η=0.004\eta = 0.004 时为 10−710^{-7} 量级(KL 是距离的平方,所以按 η2\eta^2 下降);坐标之间的最大 KL 差距从 4.5×10−44.5\times10^{-4} 降到 2.5×10−72.5\times10^{-7}。普通梯度下降则完全不同:即使步长小到 0.004,四套坐标的终点与参照流的差距仍在 0.013 到 0.167 之间,坐标之间的差距 0.19 不随步长减小——它们走的是本质上不同的路径。

步长大时,自然梯度的不变性也明显失效:η=1\eta = 1 时坐标之间的差距达到 2.1×1062.1\times10^6(在 (μ,log⁡σ)(\mu, \log\sigma) 坐标中一步走得太远)。程序最后一行显示了另一面:在期望参数坐标中,步长为 1 的一步自然梯度恰好落在极大似然估计 (1,2)(1, 2) 上。这不是巧合:对指数族,记期望参数为 mm(以免与步长 η\eta 混淆),负对数似然对它的梯度是 Gm(m−m̂)G_m(m – \hat m),所以自然梯度 Gm−1∇L=m−m̂G_m^{-1}\nabla L = m – \hat m。换言之,「步长为 1 时哪套坐标最好」是一个依赖坐标的问题——不变性恰恰在这里不成立。

病态逻辑回归上的比较

作者框架的核心主张是:在病态(条件数大)的问题上,自然梯度比普通梯度快。下面的程序在逻辑回归上检验这一点,并如实报告它不占优的情形。特征协方差的条件数 κ\kappa 取 1、100 与 10,000,特征方向或沿坐标轴、或随机旋转;比较梯度下降(步长取 1/L1/L 的几个倍数中最好的)、Adam (Kingma and Ba 2015)(几个步长中最好的)、自然梯度(此时即牛顿法)与经验费希尔预条件。除了达到目标所需的步数,还按一个写明的规则折算计算量:一次梯度计为 1 个单位,构造并求解 d×dd\times d 的曲率矩阵额外计约 d+d2/(3n)d + d^2/(3n) 个单位。这个折算是作者的模型,不是任何硬件上的实测。

推导

# Natural gradient against gradient descent, Adam and the empirical Fisher on logistic
# regression (n = 100, d = 3, then d = 12) whose feature covariance has condition number
# kappa, eigenvectors along the axes or rotated. Steps to reach L* + 1e-4 (cap 2,000) and
# cost in gradient-evaluation units (building and solving the d x d curvature matrix adds
# about d + d^2/(3n) units per step). Every method takes the best step from a small grid
# (GD: multiples of 1/L, L = largest eigenvalue / 4). For logistic regression the Fisher
# equals the Hessian, so "NG" here is Newton's method.
import math, random

N, CAP, TOL = 100, 2000, 1e-4

def solve(A, b):
    n = len(b); M = [row[:] + [b[i]] for i, row in enumerate(A)]
    for c in range(n):
        p = max(range(c, n), key=lambda r: abs(M[r][c])); M[c], M[p] = M[p], M[c]
        for r in range(c + 1, n):
            f = M[r][c] / M[c][c]
            M[r] = [x - f * y for x, y in zip(M[r], M[c])]
    x = [0.0] * n
    for r in range(n - 1, -1, -1):
        x[r] = (M[r][n] - sum(M[r][k] * x[k] for k in range(r + 1, n))) / M[r][r]
    return x

def rotation(rng, D):                               # random orthogonal (Gram-Schmidt)
    Q = []
    while len(Q) < D:
        v = [rng.gauss(0, 1) for _ in range(D)]
        for q in Q:
            c = sum(a * b for a, b in zip(v, q)); v = [a - c * b for a, b in zip(v, q)]
        s = math.sqrt(sum(a * a for a in v)); Q.append([a / s for a in v])
    return Q

def task(kappa, rotate, seed, D):
    rng = random.Random(seed); ev = [kappa ** (-i / (D - 1)) for i in range(D)]
    I = [[float(i == j) for j in range(D)] for i in range(D)]
    R = rotation(rng, D) if rotate else I
    X = []
    for _ in range(N):
        z = [rng.gauss(0, 1) * math.sqrt(e) for e in ev]
        X.append([sum(R[i][j] * z[j] for j in range(D)) for i in range(D)])
    w = [2 * sum(R[i][j] / math.sqrt(ev[j]) * (0.5 if j else 1) for j in range(D))
         / math.sqrt(D) for i in range(D)]
    y = [1 if rng.random() < 1 / (1 + math.exp(-sum(a * b for a, b in zip(w, x))))
         else 0 for x in X]
    return X, y, max(ev)

def stats(X, y, w, curv=None):                    # loss, gradient, Fisher or EF
    D = len(w); L, g = 0.0, [0.0] * D; F = [[0.0] * D for _ in range(D)] if curv else None
    for x, t in zip(X, y):
        z = sum(a * b for a, b in zip(w, x))
        p = 1 / (1 + math.exp(-z)) if z >= 0 else math.exp(z) / (1 + math.exp(z))
        L += math.log1p(math.exp(-abs(z))) + max(z, 0) - t * z
        gi = [(p - t) * a for a in x]; g = [a + b for a, b in zip(g, gi)]
        if curv:
            h, u = ([p * (1 - p) * a for a in x], x) if curv == "F" else (gi, gi)
            for i in range(D):
                Fi, hi = F[i], h[i]
                for j in range(D):
                    Fi[j] += hi * u[j]
    s = 1 / N
    return L * s, [a * s for a in g], [[a * s for a in r] for r in F] if F else None

def optimise(X, y, method, lr, Lstar):
    D = len(X[0]); w = [0.0] * D; m = [0.0] * D; v = [0.0] * D
    for k in range(1, CAP + 1):
        L, g, F = stats(X, y, w, {"NG": "F", "EF": "E"}.get(method))
        if L <= Lstar + TOL:
            return k - 1
        if method in ("NG", "EF"):
            for i in range(D):
                F[i][i] += 1e-8
            step = solve(F, g)
        elif method == "Adam":
            m = [0.9 * a + 0.1 * b for a, b in zip(m, g)]
            v = [0.999 * a + 0.001 * b * b for a, b in zip(v, g)]
            step = [(a / (1 - 0.9 ** k)) / (math.sqrt(b / (1 - 0.999 ** k)) + 1e-8)
                    for a, b in zip(m, v)]
        else:
            step = g
        w = [a - lr * b for a, b in zip(w, step)]
        if any(abs(a) > 1e6 for a in w):
            return None
    return None

def best(X, y, method, grid, Lstar):
    res = [r for r in (optimise(X, y, method, lr, Lstar) for lr in grid) if r is not None]
    return min(res) if res else None

print(f"steps to L* + {TOL:g} (cost units in brackets); '-' = not reached in {CAP:,}")
print(" d   kappa  rotated    GD            Adam          NG (=Newton)   empirical F")
for D, kappa, rot in ((3, 1, 0), (3, 1, 1), (3, 100, 0), (3, 100, 1), (3, 10_000, 0),
                      (3, 10_000, 1), (12, 1, 1), (12, 100, 1)):
        c2 = 1 + D + D * D / (3 * N); COST = {"GD": 1, "Adam": 1, "NG": c2, "EF": c2}
        X, y, lmax = task(kappa, rot, seed=98 + kappa + D, D=D)
        w = [0.0] * D
        for _ in range(40):                                  # Newton to get L*
            L, g, F = stats(X, y, w, "F"); w = [a - b for a, b in zip(w, solve(F, g))]
        Lstar = stats(X, y, w)[0]
        r = {"GD": best(X, y, "GD", (1 / lmax, 4 / lmax, 16 / lmax), Lstar),
             "Adam": best(X, y, "Adam", (0.01, 0.03, 0.1, 0.3, 1.0), Lstar),
             "NG": optimise(X, y, "NG", 1.0, Lstar),
             "EF": best(X, y, "EF", (0.1, 0.3, 1.0), Lstar)}
        cell = lambda k: (f"{r[k]:5d} [{r[k] * COST[k]:6.0f}]" if r[k] is not None
                          else f"{'-':>5s} {'':8s}")
        print(f"{D:2d} {kappa:7,d}   {'yes' if rot else 'no ':3s}   " +
              "  ".join(cell(k) for k in ("GD", "Adam", "NG", "EF")))
# steps to L* + 0.0001 (cost units in brackets); '-' = not reached in 2,000
#  d   kappa  rotated    GD            Adam          NG (=Newton)   empirical F
#  3       1   no        7 [     7]     45 [    45]      3 [    12]      3 [    12]
#  3       1   yes       6 [     6]     37 [    37]      3 [    12]      4 [    16]
#  3     100   no      603 [   603]     58 [    58]      3 [    12]      4 [    16]
#  3     100   yes     574 [   574]     83 [    83]      3 [    12]      3 [    12]
#  3  10,000   no        -             109 [   109]      3 [    12]      3 [    12]
#  3  10,000   yes       -             404 [   404]      3 [    12]      3 [    12]
# 12       1   yes       9 [     9]     42 [    42]      3 [    40]     13 [   175]
# 12     100   yes     156 [   156]     54 [    54]      2 [    27]      4 [    54]

按步数,自然梯度在每一行都最少(2–3 步),与条件数和旋转无关,这是牛顿法的二次收敛。梯度下降的步数随条件数急剧增加:κ=100\kappa = 100 时约 600 步,κ=10,000\kappa = 10{,}000 时 2,000 步内达不到目标——这与梯度下降的收敛速度依赖条件数的经典结果一致 (Nocedal and Wright 2006)。Adam 介于两者之间;它的对角预条件在特征沿坐标轴时更有效(κ=10,000\kappa = 10{,}000 时 109 步),旋转后变差(404 步),因为对角矩阵无法表示旋转后的曲率。

按计算量,结论不同。条件良好(κ=1\kappa = 1)时,梯度下降只需 6–9 个单位,比自然梯度的 12 个(d=3d = 3)与 40 个(d=12d = 12)都少;d=12d = 12、κ=1\kappa = 1 时 Adam(42)与自然梯度(40)相当。只有在病态问题上,自然梯度按计算量才明显占优(d=12d = 12、κ=100\kappa = 100 时 27 个单位对 Adam 的 54 与梯度下降的 156)。每步代价随 d2d^2(构造)与 d3d^3(求解)增长,在有数百万参数的网络中精确的自然梯度根本无法计算,这就是需要下面两种近似的原因。d=3d = 3 时经验费希尔与费希尔表现相近(3–4 步);但 d=12d = 12、κ=1\kappa = 1 时经验费希尔需 13 步(175 个单位),费希尔只需 3 步(40 个单位)。下一节说明原因。

左:条件数 100、特征旋转的二维逻辑回归中,四种方法从原点出发的路径(灰线为损失等高线,星号为最优点);梯度下降与 Adam 沿狭长山谷缓慢移动,自然梯度几步到达;经验费希尔的第一步与自然梯度相同(起点处所有样本 p = 0.5,经验费希尔恰好等于费希尔),第二步越过最优点后折回。右:损失与最优值之差随迭代次数的变化(横轴前 10 步为线性、之后为对数刻度)。

经验费希尔不是费希尔

实践中常用的「经验费希尔」把费希尔矩阵 Ey∼pθ[∇ℓ∇ℓ⊤]E_{y\sim p_\theta}[\nabla\ell\nabla\ell^\top] 中对模型预测分布的期望换成对观测到的标签求平均:1n∑i∇ℓi∇ℓi⊤\tfrac1n\sum_i \nabla\ell_i\nabla\ell_i^\top。它只需要已经算出的逐样本梯度,所以很便宜。

证据

昆斯特纳、亨尼希与巴勒斯 2019 年的结论。 他们指出,经验费希尔一般不携带二阶(曲率)信息,它与费希尔或黑塞矩阵一致所需的条件(模型设定正确、样本量大、在最优点附近)在实践中不太可能满足,而且即使在简单的线性回归上,用它预条件也会造成严重问题;他们还批评了把经验费希尔与 Adam 等启发式方法联系起来的论证 (Kunstner et al. 2019)。

推导

# The empirical Fisher (EF, the mean of per-example g g') is not the Fisher. Linear
# regression y = x'theta + e, n = 200, d = 2, feature variances 1 and 0.01, fitted by the
# Gaussian likelihood with sigma = 1. Then the Fisher F = X'X/n is also the Hessian,
# while EF = sum r_i^2 x_i x_i'/n depends on the residuals r_i. (1) Near the optimum
# EF ~ s^2 F, where s is the TRUE noise sd: right only if the model's sigma is right.
# (2) Far from it EF is dominated by the gradient direction and the step stalls.
# (3) Steps to converge: Fisher (one Newton step), EF with the best fixed step, GD.
import math, random

def data(noise, seed, n=200):
    rng = random.Random(seed); X, y = [], []
    for _ in range(n):
        x = (rng.gauss(0, 1), rng.gauss(0, 0.1)); X.append(x)
        y.append(2 * x[0] - 3 * x[1] + noise * rng.gauss(0, 1))
    return X, y

def mats(X, y, t):
    n = len(X); g = [0.0, 0.0]; F = [[0.0] * 2 for _ in range(2)]
    E = [[0.0] * 2 for _ in range(2)]; L = 0.0
    for x, v in zip(X, y):
        r = x[0] * t[0] + x[1] * t[1] - v; L += r * r / 2
        for i in range(2):
            g[i] += r * x[i] / n
            for j in range(2):
                F[i][j] += x[i] * x[j] / n; E[i][j] += r * r * x[i] * x[j] / n
    return L / n, g, F, E

def solve2(A, b, damp=1e-10):
    a, c, d = A[0][0] + damp, A[0][1], A[1][1] + damp; det = a * d - c * c
    return [(d * b[0] - c * b[1]) / det, (a * b[1] - c * b[0]) / det]

def opt(t):                                    # exact least squares
    _, g, F, _ = mats(X, y, [0.0, 0.0]); s = solve2(F, g); return [-s[0], -s[1]]

def angle(u, v):
    c = (u[0] * v[0] + u[1] * v[1]) / math.hypot(*u) / math.hypot(*v)
    return math.degrees(math.acos(max(-1.0, min(1.0, c))))

print("(1) at the optimum: EF / F along each eigen-direction (model assumes sigma = 1)")
for noise in (1.0, 0.1, 3.0):
    X, y = data(noise, seed=2019); ts = opt(None)
    _, g, F, E = mats(X, y, ts)
    print(f"   true noise sd {noise:3.1f}: EF11/F11 = {E[0][0] / F[0][0]:7.4f},"
          f" EF22/F22 = {E[1][1] / F[1][1]:7.4f}  (s^2 = {noise ** 2:.2f})")
X, y = data(1.0, seed=2019); ts = opt(None)
print("(2) away from the optimum (true noise sd 1): direction and length of steps")
print("   distance   angle(EF step, Newton step)   |EF step| / |Newton step|")
for dist in (0.1, 1.0, 10.0, 100.0):
    worst, ratio = 0.0, []
    for k in range(12):
        a = 2 * math.pi * k / 12
        t = [ts[0] + dist * math.cos(a), ts[1] + dist * math.sin(a) / 10]
        _, g, F, E = mats(X, y, t)
        ne, ef = solve2(F, g), solve2(E, g)
        worst = max(worst, angle(ne, ef)); ratio.append(math.hypot(*ef) / math.hypot(*ne))
    print(f"   {dist:8.1f}   {worst:10.1f} deg (worst of 12)      "
          f"{min(ratio):.3g} to {max(ratio):.3g}")
print("(3) iterations to L* + 1e-6 from theta = (20, -30), cap 5,000; Fisher = Newton,")
print("    empirical = EF-preconditioned, GD = gradient descent (best step in brackets)")
for noise in (1.0, 0.1):
    X, y = data(noise, seed=2019); ts = opt(None); Ls = mats(X, y, ts)[0]
    res = {}
    for meth, grid in (("Fisher", (1.0,)), ("empirical", (0.03, 0.1, 0.3, 1.0)),
                       ("GD", (0.5, 1.0, 1.9))):
        best = None
        for lr in grid:
            t = [20.0, -30.0]
            for k in range(5001):
                L, g, F, E = mats(X, y, t)
                if L <= Ls + 1e-6 or not math.isfinite(L) or L > 1e12:
                    break
                s = {"Fisher": lambda: solve2(F, g), "empirical": lambda: solve2(E, g),
                     "GD": lambda: g}[meth]()
                t = [t[0] - lr * s[0], t[1] - lr * s[1]]
            if L <= Ls + 1e-6 and (best is None or k < best[0]):
                best = (k, lr)
        res[meth] = best
    print(f"   true noise sd {noise:3.1f}: " + "; ".join(
        f"{m} {b[0]} (step {b[1]:g})" if b else f"{m} -" for m, b in res.items()))
# (1) at the optimum: EF / F along each eigen-direction (model assumes sigma = 1)
#    true noise sd 1.0: EF11/F11 =  0.9798, EF22/F22 =  1.0849  (s^2 = 1.00)
#    true noise sd 0.1: EF11/F11 =  0.0098, EF22/F22 =  0.0108  (s^2 = 0.01)
#    true noise sd 3.0: EF11/F11 =  8.8186, EF22/F22 =  9.7643  (s^2 = 9.00)
# (2) away from the optimum (true noise sd 1): direction and length of steps
#    distance   angle(EF step, Newton step)   |EF step| / |Newton step|
#         0.1         32.3 deg (worst of 12)      0.922 to 1.23
#         1.0         35.9 deg (worst of 12)      0.248 to 0.923
#        10.0         22.5 deg (worst of 12)      0.00314 to 0.912
#       100.0         17.7 deg (worst of 12)      3.16e-05 to 0.281
# (3) iterations to L* + 1e-6 from theta = (20, -30), cap 5,000; Fisher = Newton,
#     empirical = EF-preconditioned, GD = gradient descent (best step in brackets)
#    true noise sd 1.0: Fisher 1 (step 1); empirical 544 (step 1); GD 417 (step 1.9)
#    true noise sd 0.1: Fisher 1 (step 1); empirical 2500 (step 0.3); GD 418 (step 1.9)

程序在线性回归上说明了三点。第一,在最优点处经验费希尔约等于真实噪声方差乘以费希尔:模型假定 σ=1\sigma = 1 而真实噪声标准差为 1 时,两者的对角元之比为 0.98 与 1.08;真实噪声为 0.1 时比值约 0.01,为 3 时约 9。也就是说,若模型的噪声尺度设定错误,经验费希尔把步长放大约一百倍(真实噪声 0.1)或缩小约九倍(真实噪声 3)。第二,离开最优点时,残差主要来自参数误差而不是噪声,经验费希尔被梯度方向主导:距离为 100 时,经验费希尔步的长度只有牛顿步的 3×10−53\times10^{-5} 到 0.28 倍,方向偏差最大 18 度,所以远离最优点时它几乎停滞。第三,从 (20,−30)(20, -30) 出发,费希尔(即牛顿法)一步到位;经验费希尔在噪声设定正确时需 544 步,在噪声为 0.1 时需 2,500 步——都比普通梯度下降(417 与 418 步)更慢。

K-FAC:可计算的近似

马滕斯与格罗斯 2015 年提出 K-FAC:把神经网络的费希尔矩阵近似为按层分块的对角矩阵(他们也给出了保留相邻层之间块的块三对角近似),每一块再近似为两个小矩阵的克罗内克积——该层输入激活的二阶矩 E[aa⊤]E[aa^\top] 与该层输出端反向传播量的二阶矩 E[gg⊤]E[gg^\top] (Martens and Grosse 2015)。克罗内克积的逆等于逆的克罗内克积,所以每层只需求两个小矩阵的逆。这个近似有两个来源:忽略层与层之间的块,以及假定 aa 与 gg 的统计独立性使期望可以分解。

推导

# K-FAC in miniature. A 3-4-1 tanh network with biases (21 parameters) for binary labels
# from a teacher network; n = 100 inputs, one input feature scaled by 0.1. (1) How well
# do the block-diagonal Fisher and the Kronecker-factored blocks E[aa'] (x) E[w dd']
# approximate the exact Fisher? (2) Steps to a target training loss fixed in advance
# (0.20; the loss at the start is 0.83) for GD, Adam, exact natural gradient and K-FAC
# (both damped by 1e-3), best step from a small grid, cap 600 steps.
import math, random

H, I, N, CAP, TARGET = 4, 3, 100, 600, 0.20
rng = random.Random(2015)
X = [[rng.gauss(0, 1), rng.gauss(0, 1), 0.1 * rng.gauss(0, 1)] for _ in range(N)]
T = [rng.gauss(0, 1.5) for _ in range(H * (I + 1) + H + 1)]

def forward(th, x):
    a1 = x + [1.0]; h = []
    for j in range(H):
        h.append(math.tanh(math.fsum(th[j * (I + 1) + k] * a1[k] for k in range(I + 1))))
    a2 = h + [1.0]; o = H * (I + 1)
    z = math.fsum(th[o + j] * a2[j] for j in range(H + 1))
    p = 1 / (1 + math.exp(-z)) if z >= 0 else math.exp(z) / (1 + math.exp(z))
    return a1, h, a2, z, p

Y = [1 if rng.random() < forward(T, x)[4] else 0 for x in X]
P = len(T)

def pieces(th):                                  # loss, gradient, per-example Jacobians
    L, g, J = 0.0, [0.0] * P, []
    for x, y in zip(X, Y):
        a1, h, a2, z, p = forward(th, x); o = H * (I + 1)
        d1 = [th[o + j] * (1 - h[j] ** 2) for j in range(H)]
        jz = [d1[j] * a1[k] for j in range(H) for k in range(I + 1)] + a2
        L += math.log1p(math.exp(-abs(z))) + max(z, 0) - y * z
        g = [gi + (p - y) * v / N for gi, v in zip(g, jz)]
        J.append((jz, p * (1 - p), a1, d1, a2))
    return L / N, g, J

def exact_fisher(J):
    F = [[0.0] * P for _ in range(P)]
    for jz, w, *_ in J:
        for i in range(P):
            wi = w * jz[i] / N; Fi = F[i]
            for k in range(i, P):
                Fi[k] += wi * jz[k]
    for i in range(P):
        for k in range(i):
            F[i][k] = F[k][i]
    return F

def kfac(J):                                     # block diagonal, each block A (x) G
    F = [[0.0] * P for _ in range(P)]; o = H * (I + 1)
    A1 = [[math.fsum(a1[k] * a1[m] for _, _, a1, _, _ in J) / N for m in range(I + 1)]
          for k in range(I + 1)]
    G1 = [[math.fsum(w * d1[j] * d1[l] for _, w, _, d1, _ in J) / N for l in range(H)]
          for j in range(H)]
    A2 = [[math.fsum(a2[k] * a2[m] for *_, a2 in J) / N for m in range(H + 1)]
          for k in range(H + 1)]
    G2 = math.fsum(w for _, w, *_ in J) / N
    for j in range(H):
        for k in range(I + 1):
            for l in range(H):
                for m in range(I + 1):
                    F[j * (I + 1) + k][l * (I + 1) + m] = G1[j][l] * A1[k][m]
    for k in range(H + 1):
        for m in range(H + 1):
            F[o + k][o + m] = G2 * A2[k][m]
    return F

def solve(A, b, damp):
    n = len(b); M = [A[i][:] + [b[i]] for i in range(n)]
    for i in range(n):
        M[i][i] += damp
    for c in range(n):
        p = max(range(c, n), key=lambda r: abs(M[r][c])); M[c], M[p] = M[p], M[c]
        for r in range(c + 1, n):
            f = M[r][c] / M[c][c]
            if f:
                M[r] = [x - f * y for x, y in zip(M[r], M[c])]
    x = [0.0] * n
    for r in range(n - 1, -1, -1):
        x[r] = (M[r][n] - math.fsum(M[r][k] * x[k] for k in range(r + 1, n))) / M[r][r]
    return x

def frob(A, B=None):
    return math.sqrt(math.fsum((a - (B[i][j] if B else 0)) ** 2 for i, r in enumerate(A)
                         for j, a in enumerate(r)))

th0 = [0.5 * rng.gauss(0, 1) for _ in range(P)]
_, _, J = pieces(th0); F = exact_fisher(J); K = kfac(J); o = H * (I + 1)
BD = [[F[i][j] if (i < o) == (j < o) else 0.0 for j in range(P)] for i in range(P)]
print(f"{P} parameters; relative Frobenius error at the initial point:")
print(f"   block-diagonal exact Fisher vs full Fisher: {frob(BD, F) / frob(F):.3f}")
print(f"   K-FAC (Kronecker blocks) vs full Fisher:    {frob(K, F) / frob(F):.3f}")
blk = [[F[i][j] for j in range(o)] for i in range(o)]
kb = [[K[i][j] for j in range(o)] for i in range(o)]
print(f"   layer-1 block: Kronecker vs exact block:    {frob(kb, blk) / frob(blk):.3f}")

def train(method, lr):
    th = th0[:]; m = [0.0] * P; v = [0.0] * P; hist = []
    for k in range(1, CAP + 1):
        L, g, J = pieces(th); hist.append(L)
        if L <= TARGET:
            break
        if method == "GD":
            s = g
        elif method == "Adam":
            m = [0.9 * a + 0.1 * b for a, b in zip(m, g)]
            v = [0.999 * a + 0.001 * b * b for a, b in zip(v, g)]
            s = [(a / (1 - 0.9 ** k)) / (math.sqrt(b / (1 - 0.999 ** k)) + 1e-8)
                 for a, b in zip(m, v)]
        else:
            s = solve(exact_fisher(J) if method == "NG" else kfac(J), g, 1e-3)
        th = [a - lr * b for a, b in zip(th, s)]
        if not all(math.isfinite(a) and abs(a) < 1e4 for a in th):
            break
    return hist

GRID = (("GD", (1.0, 3.0, 10.0)), ("Adam", (0.03, 0.1, 0.3)), ("NG", (0.1, 0.3, 1.0)),
        ("K-FAC", (0.1, 0.3, 1.0)))
runs = {(m, lr): train(m, lr) for m, grid in GRID for lr in grid}
target = TARGET
print(f"(2) steps to training loss {target:.2f}; cost per step in gradient units:"
      " GD and Adam 1,\n   NG 1 + P + P^2/(3n), K-FAC 1 + (factor sizes)/P")
cost = {"GD": 1, "Adam": 1, "NG": 1 + P + P * P / (3 * N),
        "K-FAC": 1 + ((I + 1) ** 2 + H * H + (H + 1) ** 2) / P}
for meth in ("GD", "Adam", "NG", "K-FAC"):
    best = None
    for (m, lr), h in runs.items():
        if m == meth:
            k = next((i for i, L in enumerate(h) if L <= target), None)
            if k is not None and (best is None or k < best[0]):
                best = (k, lr)
    if best:
        print(f"   {meth:6s} {best[0]:4d} steps (step {best[1]:g}); about"
              f" {best[0] * cost[meth]:.0f} gradient-evaluation units")
    else:
        print(f"   {meth:6s} not reached in {CAP} steps (lowest loss"
              f" {min(min(h) for (m, _), h in runs.items() if m == meth):.3f})")
# 21 parameters; relative Frobenius error at the initial point:
#    block-diagonal exact Fisher vs full Fisher: 0.654
#    K-FAC (Kronecker blocks) vs full Fisher:    0.670
#    layer-1 block: Kronecker vs exact block:    0.285
# (2) steps to training loss 0.20; cost per step in gradient units: GD and Adam 1,
#    NG 1 + P + P^2/(3n), K-FAC 1 + (factor sizes)/P
#    GD      532 steps (step 3); about 532 gradient-evaluation units
#    Adam    124 steps (step 0.3); about 124 gradient-evaluation units
#    NG       32 steps (step 0.3); about 751 gradient-evaluation units
#    K-FAC  not reached in 600 steps (lowest loss 0.205)

在一个只有 21 个参数的 3-4-1 网络上,程序先度量近似的质量:只保留层内块(块对角化)就使相对弗罗贝尼乌斯误差达到 0.654;再把块换成克罗内克积,总误差为 0.670;单看第一层,克罗内克积与精确块的相对误差为 0.285。在这个网络中,层间块并不小。

训练的比较同样如实报告:达到训练损失 0.20(起点为 0.83)的步数,精确自然梯度(阻尼 10−310^{-3})最少,32 步;Adam 124 步;梯度下降 532 步;K-FAC 在 600 步内没有达到(最低 0.205)。按计算量折算,精确自然梯度约为 751 个单位,多于 Adam 的 124 个。步长 1 时精确自然梯度发散,说明它需要阻尼或信赖域。这是一个很小的例子,不能说明 K-FAC 在大型网络上的表现——在那里它的设计目标正是用比精确费希尔低得多的代价得到有用的曲率信息——但它说明「自然梯度更快」与「K-FAC 等于自然梯度」都不能不加条件地成立。

已发表的基准比较

证据

没有一个优化器在所有任务上占优。 施密特、施奈德与亨尼希 2021 年在多个深度学习任务上比较了十余种优化器,结论是没有一种方法在所有任务上明显占优,调参预算与任务对排名的影响很大 (Schmidt et al. 2021)。张国栋等人 2019 年用噪声二次模型与实验说明,Adam、K-FAC 一类的预条件方法主要在大批量训练中带来好处,小批量时优势有限 (Zhang et al. 2019)。威尔逊等人 2017 年报告,自适应方法在一些任务上得到的解泛化较差 (Wilson et al. 2017)。达尔等人 2023 年的 AlgoPerf 基准把「在固定硬件上达到目标的时间」作为主要指标,并规定了调参协议 (Dahl et al. 2023),第八章的方案沿用这一思路。

假说 · 尚未验证 · 曲率近似的回报随条件数增长

作者的假说(尚未确立): 在固定计算预算下,K-FAC 相对于 Adam 的墙钟时间优势随任务的有效条件数(以训练早期费希尔矩阵的谱估计)单调增加;在条件数低于某个阈值的任务上,K-FAC 不比 Adam 快。什么样的结果能证明它是错的: 在第八章预注册基准的次要分析中,按事先定义的条件数分层后,时间比的对数与条件数的秩相关的置信区间包含零或为正(即 K-FAC 的相对优势不随条件数增加)。

本章小结

自然梯度 G−1∇LG^{-1}\nabla L 是费希尔度量下的最陡下降方向。它的不变性对连续时间的流严格成立,对离散步只在一阶成立:程序中步长 0.004 时坐标间差距为 2.5×10−72.5\times10^{-7},步长 1 时达到 2.1×1062.1\times10^6。作者框架所说的「证明」应改为:费希尔等于黑塞矩阵时自然梯度就是牛顿法。在病态逻辑回归上它的步数最少,但按计算量在条件良好时不如梯度下降;在一个小网络上,精确自然梯度步数最少而计算量约为 Adam 的六倍,K-FAC 未达到目标。经验费希尔不是费希尔:它的尺度随真实噪声改变一百倍,远离最优点时停滞。已发表的基准显示没有一个优化器在所有任务上占优。

参考文献

Amari, Shun-ichi. 1998. “Natural Gradient Works Efficiently in Learning.” Neural Computation 10 (2): 251–76. https://doi.org/10.1162/089976698300017746.
Dahl, George E., Frank Schneider, Zachary Nado, Naman Agarwal, et al. 2023. Benchmarking Neural Network Training Algorithms. arXiv:2306.07179.
Kakade, Sham M. 2001. “A Natural Policy Gradient.” Advances in Neural Information Processing Systems 14.
Kingma, Diederik P., and Jimmy Ba. 2015. “Adam: A Method for Stochastic Optimization.” 3rd International Conference on Learning Representations (ICLR).
Kunstner, Frederik, Philipp Hennig, and Lukas Balles. 2019. “Limitations of the Empirical Fisher Approximation for Natural Gradient Descent.” Advances in Neural Information Processing Systems 32: 4156–67.
Martens, James. 2020. “New Insights and Perspectives on the Natural Gradient Method.” Journal of Machine Learning Research 21 (146): 1–76.
Martens, James, and Roger Grosse. 2015. “Optimizing Neural Networks with Kronecker-Factored Approximate Curvature.” Proceedings of the 32nd International Conference on Machine Learning, Proceedings of machine learning research, vol. 37: 2408–17.
Nocedal, Jorge, and Stephen J. Wright. 2006. Numerical Optimization. 2nd ed. Springer.
Ollivier, Yann, Ludovic Arnold, Anne Auger, and Nikolaus Hansen. 2017. “Information-Geometric Optimization Algorithms: A Unifying Picture via Invariance Principles.” Journal of Machine Learning Research 18 (18): 1–65.
Pascanu, Razvan, and Yoshua Bengio. 2014. “Revisiting Natural Gradient for Deep Networks.” 2nd International Conference on Learning Representations (ICLR).
Schmidt, Robin M., Frank Schneider, and Philipp Hennig. 2021. “Descending through a Crowded Valley – Benchmarking Deep Learning Optimizers.” Proceedings of the 38th International Conference on Machine Learning, Proceedings of machine learning research, vol. 139: 9367–76.
Wilson, Ashia C., Rebecca Roelofs, Mitchell Stern, Nathan Srebro, and Benjamin Recht. 2017. “The Marginal Value of Adaptive Gradient Methods in Machine Learning.” Advances in Neural Information Processing Systems 30.
Zhang, Guodong, Lala Li, Zachary Nado, et al. 2019. “Which Algorithmic Choices Matter at Which Batch Sizes? Insights from a Noisy Quadratic Model.” Advances in Neural Information Processing Systems 32.

Fan, Y. (2026). Information Geometry, the Fisher Information Metric and Natural-Gradient Optimisation on Statistical Manifolds: From the Cramér–Rao Bound and Jeffreys's Prior to Singular Learning Theory, Read Beside Classical Chinese Thought on Change and Coordinates [信息几何、费希尔信息度量与自然梯度优化的统计流形] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.23836268 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).