上一讲用“梯度等于零”求出了线性回归的最优参数。这一讲遇到逻辑回归:梯度也能写出来,但令它为零以后,得到的是难以直接解开的非线性方程。
因此要学习迭代算法:从一个初始点出发,反复修改,逐渐接近最优解。路线是:逻辑回归建模 → 下降方向 → 梯度下降 → 三种选步长的方法 → 牛顿法。每个算法都围绕三个问题:往哪里走、走多远、什么时候停。
共 47 页。按原课件顺序,左侧看原页,右侧读讲解。
沿着 逐层使用链式法则。先只看一个样本:
令梯度为零得到 参数藏在 sigmoid 的指数里面,这已经是非线性方程,无法照搬线性回归的逆矩阵公式。
一个样本算到更新:只取截距和一个输入,特征行为 ,真实标签为1。从 开始,、,所以 取步长0.1,更新后 ,新分数为 ,新概率约0.56218。正确标签的概率从0.5升高,损失 从约0.69315降到0.57594。梯度里的负号正是让这次更新提高正确标签的概率。
左图对应正梯度:。对于正步长,两项增量都为正,所以曲线一直上升,它不是下降方向。
右图对应负梯度:。
注意:沿这条直线的最小值约为 2.914,整个二维问题的最小值为 。一次线搜索只优化当前方向,随后仍需重新计算方向。
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。
比较方向时,先把每条箭头的长度定为 1,再沿每个方向移动同样的距离 。代码把形成下降的箭头用蓝色标出,再用红色标出扫描中最低的一条。
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()
endpoint=False 让 0° 和 360° 这个方向只出现一次。values 和 directions 使用同一个下标,因此 argmin 找出最低值的下标后,就能取出对应的方向。descends 逐项比较目标是否跌破起点的 26。下一页从导数推导的单位负梯度约为 。直接沿它走 0.01,目标约为 25.76650。扫描只能从指定的 100 个方向中选择,一阶推导则描述距离趋近 0 时的最佳方向。
图中箭头从同一点出发,红箭头表示能下降的方向,蓝色箭头指向负梯度。向下偏左是本例下降最多的方向,因为梯度为 。
严格下降的一阶充分条件是 ,等价于 ,也就是与负梯度夹角小于 90°。原页写的“≥0”包含了边界;等于零时要继续看高阶项,不能直接判为下降。例如本例取 ,内积为零,但二次增量为正。
用3、4、5看“最陡”:假设当前梯度为 ,比较三个长度都是1的方向。向左 的内积为−3,向下 为−4,单位负梯度 为 。同样走很小的距离0.01,一阶预测分别下降约0.03、0.04、0.05。
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)
clip 把数值限制在 30 至 100,再除以 100。choice 独立产生论文标记:0 的概率是 0.8,1 的概率是 0.2。binomial(1,p) 对每个概率做一次伯努利抽样:输出 1 的概率为 ,否则输出 0。固定种子运行这段代码,得到 372 个标签 1。这些 就是后续所有算法共同使用的数据。
用 print(X[0], z[0], p[0], y[0]) 可以查看第一条样本。GPA 约为 0.976405,有论文,设计矩阵第一行约为 。和 做点积得到 ,对应概率极接近 1,这次抽样得到标签 。
本页先调用现成的逻辑回归求解器,获得参数参照,再检查自己写的算法是否接近它。数据生成沿用上一页。
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_)
C=np.inf 让正则化强度为零,对应课件的无正则化损失。课件原代码用 penalty="none" 表达相同意图;这里给出已运行的写法。fit_intercept=False 很关键:我们已经在 的最后一列放了全 1,所以不再额外增加截距。fit(X,y) 开始训练;coef_ 取出训练后的参数。得到参数约为 ,与课件列出的 接近。它们不等于生成参数 ,因为只有有限条随机抽样数据;训练求的是这份数据的最优拟合。
先运行第20页,得到 。课件使用平均交叉熵,其梯度为 。从零参数开始,每轮先检查当前梯度,再更新参数。
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)
zeros 生成三个零参数。起初全部分数为零,因此每条预测概率都是 0.5。norm(...,2) 求梯度的欧氏长度。足够小就停止。本例初始平均梯度约为 ,步长 1 更新后 。这次更新把平均损失从约 0.69315 降至 0.67391。代码最后在最新参数处重算梯度范数。按本页设定运行,步长 1 用完 100 万次更新后,梯度范数约为 ,仍高于停止阈值 。下一页比较不同步长下需要多少轮。
横轴是迭代次数,右下角的 表示横轴标记还要乘一百万;纵轴是梯度范数,使用对数刻度。纵轴每下降两格,范数通常减少一百倍。
老师在课堂还展示了过大步长下的数值问题:sigmoid 可能非常接近 0 或 1,直接算 会出现无穷大。可先把损失改写到分数 上。由 得 ,同时 ,所以 。代入第6页并合并 的两项,得到 NumPy 的 np.logaddexp(0, z) 直接稳定计算 ,所以可以写成 np.mean(np.logaddexp(0, z) - y*z)。
课件从 开始。只要新的试探值还在下降,就把步长翻倍;遇到回升时,当前步长可作右端点。
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)
变量 previous 每次保存的是上一次试探点的函数值,不是一直保存 。程序用于实际数据时,再加上最大试探次数,便于处理沿该方向一直下降的情况。
确定区间以后,最直接的办法是均匀取很多个候选步长,全部算一遍,再选函数值最低的那个。这就是网格搜索。
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])
argmin 返回最小值所在的位置编号。真正的最小点约为 0.35173371,网格没有恰好取到它。把间距改成 0.001 可以更精细,但候选点数量也约增加十倍。网格法适合先找大概位置;若需要很高精度,逐步缩小区间更省计算。
图中左右红线是当前边界 0 和 0.5,中间红线在 0.25。蓝曲线是 。现在要在这个小区间里继续定位谷底。
只知道中点函数值低于两个端点,还不能判定最小点在它左边还是右边:谷底可能略偏左,也可能略偏右。这个例子里谷底在 0.25 右边,但算法不能靠“看起来像”决定。
改进办法是:在区间内部放两个有顺序的点 ,比较 与 。如果右点更低,就能排除左端的一部分;如果左点更低,就排除右端的一部分。下面的黄金分割法就是按这个原则不断缩小区间。
例如区间为 ,分别看 与 。两者在中点0.25的值都为0.0025,而且都低于各自两个端点;但一个谷底在中点左边0.2,另一个在右边0.3。仅凭“中点低于两端”,无法选择保留哪半边。
黄金分割法不仅要缩小区间,还希望旧的内部点能在新区间中继续使用。这样每轮只需要新计算一个函数值。
本页图中的小写 是线段长度,与后面代码中代表区间端点的 a、b 含义不同。设 是原区间长度,某次缩短后保留长度 。原来被舍掉的一段长度为 。看保留右侧的情况,旧右试探点距原右端就是 。当它成为新区间的左试探点时,距新右端的距离应为新区间长度乘以比例 。因此要让它保持原位置,需令 ,即 。
因此对于长度为 的区间,内部点放在距左端约 和 的位置。两点关于中点对称。每次舍去一端,剩余长度约为原长度的 0.618 倍。
代码先初始化黄金比例、两个内部点及函数值:
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)
例如区间 ,两内部点为 0.381966、0.427051,左点较低。执行后保留 ,旧 0.381966 成为新右内部点。外层条件 while b-a > tol 表示只要区间仍宽于容差,就继续缩。
与上一页对称。如果 g1 >= g2,保留右侧区间:
a = alpha1
alpha1 = alpha2
g1 = g2
alpha2 = a + phi*(b-a)
g2 = g(alpha2)
例如初始区间 ,因为 ,执行后左端点变为 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。
理解算法以后,可以直接让 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)
g 输入一个步长,返回一个目标值。method='golden' 选择黄金分割法;bracket 提供初始搜索信息。result.x 是最小点,约为 0.35173371;result.fun 是最小函数值,约为 0.82718403。这里的 bracket=(0,0.5) 不是强制边界,求解器可以继续扩展搜索。如果任务要求严格限制在指定区间,可用 minimize_scalar(g, bounds=(0, 0.5), method='bounded')。本例的最小点位于区间内部,两种方式都能找到它。
先运行第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
w_new 是候选参数,还没有覆盖当前 。z_new。logaddexp(0,z_new) 稳定地计算 ,返回当前候选步长对应的平均交叉熵。g,比较不同步长。result.x 约为 3.10831,result.fun 约为 0.65780;第22页固定步长 1 的对应损失约为 0.67391。第23页推导了这里的损失写法。每次调用 都会重新处理全部 1000 条数据,因此线搜索会增加每轮耗时。
取缩小比例 和下降参数 。课件把缩小比例写作 。先运行第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
value_now 是当前参数的平均损失,gradient @ gradient 是当前梯度各分量的平方和。它们在这一轮回溯中固定。具体算一轮:,当前 ,梯度为 4,。取 ,为便于手算,先试 ,新点 −2,目标 4,而参考值 ,不合格。缩到 0.5,新点 0、目标 0,参考值为 2,满足 ,接受。
零参数的平均损失为 ,平均梯度的平方范数约为 0.02303。每次用新的 算两列,并判断候选损失是否小于等于参考值。
| 步长 | 候选损失 | 参考值 | 判断 |
|---|---|---|---|
| 50 | 3.18091 | 0.40524 | 减半 |
| 25 | 1.60514 | 0.54919 | 减半 |
| 12.5 | 0.90648 | 0.62117 | 减半 |
| 6.25 | 0.69053 | 0.65716 | 减半 |
| 3.125 | 0.65780 | 0.67515 | 接受 |
最后一行的参考值来自 。这一轮共减半四次,更新只使用通过检查的 3.125。
蓝线是固定步长,橙线是精确线搜索,绿线是非精确线搜索。纵轴仍为梯度范数,横轴仍为外层迭代次数。
以梯度范数降到约 为例,图上精确和非精确线搜索大约在 4 万轮达到,固定步长大约在 11 万轮达到。按第40页的参数重复运行,梯度范数达到第22页的 停止阈值约需 4.33 万次更新。图中的横轴只计外层迭代,总耗时还取决于每轮评价多少次损失。
多维变量用位移 表示,记当前梯度 、Hessian 。二次近似是
实现时直接解 。若 正定且 ,则 ,所以 是下降方向,二次模型给它的完整步幅仍需要适合原函数。若 不正定,需先确认或修正方向,再决定沿它走多远。
Hessian怎样决定下一步:取 ,当前点为 。梯度 ,Hessian为 。解 就是解 、,所以位移为 ,新点为 。第二个方向的梯度大10倍,但曲率也大10倍;除去曲率影响后,这个方向同样只需移动1。普通梯度步若取步长0.1,会到 。
对于逻辑回归的损失总和,梯度已经是 。再对参数求一次导数:
本例有 1000 个样本、3 个参数,所以 为 , 为 ,最终 Hessian 只有 。梯度和 Hessian 若都除以 ,牛顿位移不变,因为用平均损失解的是 ,两边同乘 就回到 。
两条样本做一轮牛顿更新:取 、,从 开始。此时 ,所以 解 :第一式为 ,第二式为 。相减得 ,再得 ,因此 。两条样本的新分数为−2和2,正确标签概率都约为0.88080,损失总和从 降到约0.25386。
先运行第20页得到数据。下面的程序使用逐行加权来计算 ,计算结果与先创建矩阵 再乘 一致。
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))
expit 稳定地计算 sigmoid。weights[:,None] 把 1000 个权重变成一列,再分别乘到 的每一行上;结果就是 。例如第45页的小矩阵中,权重为 ,两行加权后得到 。课件的 1000 条数据做的是同一种广播运算。solve(H, gradient) 解 ,再从参数中减去这个位移。课件用 inv(H) @ gradient 直接表达同一公式。第一轮从零参数出发,,得到的更新后参数约为 。之后每轮重新计算概率、梯度和 Hessian,逐步接近最后的解。
右侧列表从迭代 0 的初始点开始,给出每次的损失总和梯度范数:
| 已完成更新次数 | 梯度范数 |
|---|---|
| 0 | 151.76568 |
| 1 | 41.67301 |
| 2 | 17.27175 |
| 3 | 7.58022 |
| 4 | 2.99918 |
| 5 | 0.82229 |
| 6 | 0.10801 |
| 7 | 0.003368 |
| 8 | 约 7.52×10⁻⁶ |
| 9 | 约 8.8×10⁻¹¹ |
九次更新后,参数约为 ,平均交叉熵约为 0.11811702,与前面的现成求解器相符。左图中的梯度下降需许多轮,右边牛顿法只用个位数到十轮左右,差别很明显。
这里的 Hessian 只有 。若有 个样本和 个参数,直接形成稠密的 要累加 个长度为 的内积,运算量约为 。矩阵占 个数,再直接解线性方程的运算量约为 。第46页省去的是 的对角矩阵,仍需计算和求解 的 Hessian。