DASE 7113 · 课程精讲

无约束最优条件

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

逐页目录 · 共 18 页
  1. 这讲要解决什么:怎样认出最优解
  2. 最优性条件:把“最好”变成可以检查的等式
  3. 为什么先学凸问题
  4. 一维充分性:导数为零为什么一定最小
  5. 一维必要性:最小点为什么导数为零
  6. 完整例题:先对 x 求最小值,再证明不等式
  7. 多维版本:把导数换成梯度
  8. 二元二次函数:从求导一直算到最小值
  9. 线性回归:训练的是参数
  10. 曲线也可以是线性回归
  11. 先加工输入,再做参数的加权和
  12. 把拟合问题写成最小二乘
  13. 矩阵形式与梯度:每一步怎么来的
  14. 令梯度为零,得到正规方程
  15. 编程练习:生成含噪声的二次数据并拟合
  16. 解释结果:为什么系数和真实值不同
  17. 提高阶数:代码只需增加特征列
  18. 高阶拟合结果:训练误差降低意味着什么
原第 1 页

这讲要解决什么:怎样认出最优解

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

这一讲研究无约束优化:变量可以在整个实数空间里取值,我们要把目标函数降到最低。比如选择一条拟合直线的斜率和截距,让预测误差最小。

先学一个判断办法:当目标函数可微而且凸时,梯度等于零,就找到了全局最小点。然后把这个办法用于线性回归,推导出参数的计算公式,最后用含噪声的数据练习。

原第 2 页

最优性条件:把“最好”变成可以检查的等式

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

假设你声称某个点 x* 最好,我们需要一个能检查的数学条件。星号表示“最优候选”,不是乘法。

  1. 原问题是最小化 f(x)。它问:所有允许的点里面,哪个点的目标值最小?
  2. gi(x)≤0 表示第 i 条不等式限制,hi(x)=0 表示第 i 条等式限制;没有这些限制时,就是无约束问题。
  3. 理想的条件要能双向判断:最优解一定满足它;满足它的点也一定最优。这叫充要条件,英文是 if and only if。

例如最小化 f(x)=(x−3)2:解是 x*=3,而 f′(x)=2(x−3)。检查 f′(x)=0,得到的也正是 x=3。这一讲要解释为什么在凸问题里可以这样做。

原第 3 页

为什么先学凸问题

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

最优性条件是否好用,取决于问题的结构。凸问题的关键好处:局部找不到下降方向时,就已经到了全局最低处。

课件的凸规划形式是:目标 f 为凸函数,不等式函数 gi 为凸函数,等式函数 hi 为仿射函数,也就是 aiTx+bi。例如仿射等式 x1+x2=1 的解是一条直线;凸函数的等式 x2−1=0 只允许 −1,1,两点间的中点 0 不满足等式,因此可行集不凸。

先用一维图像理解区别:f(x)=x2 是向上开的碗,导数为零的位置就是碗底;f(x)=−x2 也在零点导数为零,但那是最高点。所以“导数等于零”必须连同“函数凸”一起使用。

原第 4 页

一维充分性:导数为零为什么一定最小

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

设 f:R→R 可微且凸。我们先证明:如果 f′(x*)=0,那么 x* 是全局最小点。

  1. 凸函数位于任一切线的上方,所以对任意 x,都有 f(x)≥f(x*)+f′(x*)(x−x*). 右边就是在 x* 处画出的切线的高度。固定 x,取连接 x* 到 x 的一点 x*+t(x−x*),其中 0<t<1。凸性给出 f(x*+t(x−x*))≤(1−t)f(x*)+tf(x). 移项并除以正数 t,得到 f(x*+t(x−x*))−f(x*)t≤f(x)−f(x*). 令 t→0+,左边趋于 f′(x*)(x−x*),这就得到切线下界。
  2. 把 f′(x*)=0 代进去,乘积项消失,得到 f(x)≥f(x*)+0·(x−x*)=f(x*).
  3. 这句话对所有 x 成立,因此别处没有更小的函数值,x* 就是全局最小点。

用 f(x)=(x−3)2 检查:f′(3)=0,切线就是水平线 y=0,整个函数图像都在这条线之上。

原第 5 页

一维必要性:最小点为什么导数为零

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

现在反过来证明:如果可微函数在无约束点 x* 取得最小值,那么 f′(x*)=0。这里要仔细看分母的正负。

  1. 因为 x* 最小,邻近点满足 f(x)−f(x*)≥0。
  2. 从右侧靠近时,x−x*>0。因此差商 f(x)−f(x*)x−x*≥0,取极限得到右导数非负。
  3. 从左侧靠近时,x−x*<0。同一个非负分子除以负数,差商非正,所以左导数非正。
  4. 函数可微意味着左右导数相同。这个共同数既要 ≥0,又要 ≤0,只能等于零。

上一页证明“导数零推出最优”,这一页证明“最优推出导数零”,合起来就是:可微无约束凸函数,最优当且仅当导数为零。

用小数跟一次:取 f(x)=(x−3)2,最低点是3。右边取3.1,差商为 (0.01−0)/0.1=0.1;左边取2.9,差商为 (0.01−0)/(−0.1)=−0.1。距离缩到0.01时,两边变成0.01和−0.01;继续靠近,两边都趋向0。这就是“右边非负、左边非正,且必须相等”的具体过程。

原第 6 页

完整例题:先对 x 求最小值,再证明不等式

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

题目给定 a>0,定义 f(x)=a(ex+a)−x=aex+a2−x,要求证明 f(x)>2loga+1.5。这里 a 是固定参数,先把 x 当成唯一变量;log 表示自然对数。

  1. 确认凸性。f′(x)=aex−1,f″(x)=aex>0. 因为 a>0、ex>0,函数严格凸。
  2. 令一阶导数为零。aex*=1⇒ex*=1/a⇒x*=−loga.
  3. 代回函数。f(x)≥f(−loga)=a(1/a+a)+loga=1+a2+loga.
  4. 还差最后一步。将这个下界减去题目要的右边:1+a2+loga−(2loga+1.5)=a2−loga−0.5. 设 q(a)=a2−loga−0.5,则 q′(a)=2a−1/a。它在 a=1/2 时为零,而 q″(a)=2+1/a2>0,所以 q(a)≥q(1/2)=12log2>0.

于是 f(x)≥1+a2+loga>2loga+1.5,完成证明。严格“大于”来自最后这个差值始终为正。

原第 7 页

多维版本:把导数换成梯度

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

当 x=(x1,…,xn)T 有多个分量时,梯度就是把所有偏导数排成一列:

∇f(x)=[∂f/∂x1⋮∂f/∂xn].

对于可微凸函数 f:Rn→R,有 x* 全局最优⟺∇f(x*)=0. 右边的零是一个零向量,意思是每一个偏导数都等于零。

  1. 多维凸函数的切平面下界为 f(x)≥f(x*)+∇f(x*)T(x−x*)。
  2. 若梯度为零,内积项为零,仍得到 f(x)≥f(x*)。
  3. 反过来,若 x* 是最小点,就固定其他坐标,只看第 j 个坐标。写成一维函数 hj(t)=f(x*+tej),其中 ej 是第 j 个分量为 1、其余为 0 的向量。hj 在 t=0 处最小,按第5页得到 hj′(0)=0。这恰好就是 ∂f∂xj(x*)=0,对每个 j 都成立。

实际解题顺序:先确认凸性,再写梯度,再解“每个分量等于零”的方程组。

两个变量的小例子:令 f(x1,x2)=(x1−1)2+(x2+2)2,则 ∇f=(2(x1−1),2(x2+2))T。在 (0,0),梯度为 (−2,4)T:增加一点 x1 会下降,减少一点 x2 也会下降。令两个分量分别为零,得到 x1=1,x2=−2,此时两个平方都为零。梯度零向量表示两个坐标方向都已经到位。

原第 8 页

二元二次函数:从求导一直算到最小值

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

题目是 f(x1,x2)=2x12+4x1x2+5x22−8x1−6x2+10。先检查能否使用梯度零条件。

  1. 分别求偏导:∇f=[4x1+4x2−84x1+10x2−6],H=∇2f=[44410].
  2. Hessian H 由梯度再求一次偏导得到,例如右下角是 ∂(4x1+10x2−6)/∂x2=10。对任何非零向量 u=(u1,u2)T,uTHu=4u12+8u1u2+10u22=4(u1+u2)2+6u22>0. 两个平方同时为零只会出现在 u=(0,0)T,所以 H 正定,f 严格凸。也可用主子式判断,左上角为 4>0,行列式为 4·10−42=24>0。
  3. 令梯度两个分量都为零:4x1+4x2=8,4x1+10x2=6. 第二式减第一式得到 6x2=−2,因此 x2=−1/3。
  4. 将它代回 x1+x2=2,得到 x1=7/3。
  5. 代回原函数:f(7/3,−1/3)=98−28+59−563+2+10=53.

所以唯一最小点是 x*=(7/3,−1/3)T,最小值为 5/3。正定性不仅保证这是全局最小点,还保证没有第二个最小点。

原第 9 页

线性回归:训练的是参数

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

图里的每个点 (xi,yi) 是一条数据:xi 是输入,yi 是对应的实际输出。我们用 y^i=β0+β1xi 预测输出。

  1. β0 是截距,控制整条线向上或向下移动。
  2. β1 是斜率,输入增加一个单位时,预测值增加 β1 个单位。
  3. 训练时数据 xi,yi 固定,我们改变的是 β0,β1。

比如参数取 (β0,β1)=(3,2),输入 x=4 的预测就是 3+2×4=11。如果真实输出为 10,残差为 11−10=1,平方误差为 1。

线性回归中的“线性”,看的是模型对参数 β 是否线性。这里每个参数只乘上一个固定特征,然后相加。

原第 10 页

曲线也可以是线性回归

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

本页把直线换成 y^=β0+β1x+β2x2。图像是一条弯曲的抛物线,它仍属于线性回归。

  1. 对每个训练输入 xi,先算出三个固定数:1,xi,xi2。
  2. 模型就是参数与这三个数的加权和:β0·1+β1xi+β2xi2。
  3. 没有 β12、β1β2 或 eβ1 这样的参数非线性,所以它对 β 仍然线性。

输入为 2 时,特征是 (1,2,4);若参数为 (3,−2,1),预测值是 3−4+4=3。平方的是输入,不是待训练参数。

原第 11 页

先加工输入,再做参数的加权和

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

原始输入有四个分量 x1,x2,x3,x4。课件把它们加工成六个特征:

ϕ(x)=(x1,x12,logx2,x3,x3x4,x4)T.

然后模型写成 y^=βTϕ(x)。ϕ 读作 phi,表示特征变换。计算特征时 x 已知,因此这六个数对参数而言都是常数。

  1. 先得到原始输入,例如 (2,e,3,4)。
  2. 逐项算特征:ϕ(x)=(2,4,1,3,12,4)T。因为 loge=1,3×4=12。这里的对数要求 x2>0。
  3. 再乘参数并相加:y^=2β1+4β2+β3+3β4+12β5+4β6。

所以“输入经过非线性变换”和“参数线性”可以同时成立。这就是多项式回归、对数特征和交互特征仍能使用线性回归求解方法的原因。

原第 12 页

把拟合问题写成最小二乘

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

有 n 个样本,每个样本有 m 个特征,模型预测是 y^i=β0+∑j=1mβjxij。下标 i 表示第几个样本,j 表示第几个特征。

残差是“预测减真实”:ri=y^i−yi。平方后相加得到损失:

l(β)=∑i=1n(β0+β1xi1+⋯+βmxim−yi)2.
  1. 选一组参数 β。
  2. 对每条数据计算预测值,再减去该条真实值。
  3. 把每个残差平方,最后求和。
  4. 改变 β,直到这个总和最小。这就叫最小二乘。

比如两条数据为 (0,1),(1,3),取 β0=1,β1=2,预测分别为 1、3,两项误差均为零,总损失也为零。真实数据含噪声时,通常无法让所有残差同时为零。

原第 13 页

矩阵形式与梯度:每一步怎么来的

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

把每条数据放成设计矩阵 X 的一行,并在第一列放 1:

X=[1x11⋯x1m⋮⋮⋮1xn1⋯xnm],β=[β0⋮βm],y=[y1⋮yn].

X 的形状是 n×(m+1),β 是 (m+1)×1,所以 Xβ 正好得到 n 个预测值。

  1. 残差向量为 r=Xβ−y。平方和就是 rTr。
  2. 展开乘法:l=(Xβ−y)T(Xβ−y)=βTXTXβ−2yTXβ+yTy. 中间两项是相同的标量,所以合成负两倍。
  3. 先对第 j 个参数求导。记 Xi0=1,则 ri=∑k=0mXikβk−yi,其中只有 Xijβj 随 βj 变化。链式法则给出 ∂l∂βj=∑i=1n∂(ri2)∂ri∂ri∂βj=2∑i=1nriXij. XT 的第 j 行由 X 的第 j 列组成,与 r 做内积就是上面的和。因此把各参数的偏导排成一列,得到 ∇l=2XTr=2XT(Xβ−y)。
  4. 对这个梯度的第 j 项再对 βk 求导。Xij 固定,只有 ri 随参数变化,因此 Hjk=∂∂βk(2∑i=1nXijri)=2∑i=1nXijXik. 这正是 2XTX 的第 j,k 项,也就是 ∇2l=2XTX。
  5. 对任意向量 v,vT(2XTX)v=2‖Xv‖22≥0。所以 Hessian 半正定,最小二乘损失为凸函数。

只用两条数据跟算:取 X=[1011]、y=(1,3)T,从 β=(0,0)T 开始。预测为 (0,0)T,残差为 (−1,−3)T,所以 ∇l=2[1101][−1−3]=[−8−6]. 截距列把两条残差相加;斜率列把残差分别乘输入0和1再相加。沿负梯度取步长0.05,参数变为 (0.4,0.3)T,预测为 (0.4,0.7)T,误差平方和从10降到 0.62+2.32=5.65。

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

令梯度为零,得到正规方程

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

已经知道损失凸,现在可以用梯度零条件求最优参数:

2XT(Xβ*−y)=0⇒XTXβ*=XTy.

这叫正规方程。当 X 的列线性无关时,XTX 可逆,于是

β*=(XTX)−1XTy.
  1. 还是用数据 (0,1),(1,3):X=[1011],y=(1,3)T。
  2. 计算 XTX=[2111],XTy=(4,3)T。
  3. 因此 2β0+β1=4,β0+β1=3。两式相减得 β0=1,再得 β1=2。

如果特征列重复,例如 X=[1111]、y=(2,2)T,两条预测都等于 β0+β1。只要两项之和为 2,损失就是零,例如 (2,0)T 和 (1,1)T 都是最优解。这时 XTX=[2222] 的两行相同,无法求逆。写程序可直接用 np.linalg.lstsq(X, y, rcond=None) 求最小二乘,避免显式求逆;返回值的第一项就是参数。

对应课堂录音Week07 Part01 00:00:00–00:05:18Week07 Part01 00:12:56–00:18:19
原第 15 页

编程练习:生成含噪声的二次数据并拟合

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

课件生成 10 条数据,真实关系是 y=x2−2x+3,再加入随机噪声。下面这段可以直接运行:

import numpy as np
np.random.seed(0)
x = np.linspace(-10, 10, 10)
y = x**2 - 2*x + 3
y = y + np.random.normal(0, 10, size=x.shape)
X = np.column_stack((np.ones_like(x), x, x**2))
beta = np.linalg.lstsq(X, y, rcond=None)[0]
y_hat = X @ beta
mse = np.mean((y_hat - y)**2)
print(beta)
print(mse)
  1. seed(0) 固定随机序列,重复运行得到相同数据。
  2. linspace(-10, 10, 10) 在 −10 到 10 之间等间隔取 10 个输入。
  3. normal(0, 10, ...) 生成均值为 0、标准差为 10 的噪声;这里 10 是标准差,方差为 100。
  4. column_stack 把常数、一次、二次三列拼成 10×3 的 X。
  5. lstsq 找到平方误差和最小的三个系数,@ 代表矩阵乘法。
  6. MSE 是平均平方误差:先平方每个残差,再对 10 项取平均,即平方和除以 10。

把一行数据对回代码:第一个输入是−10,真实输出为 (−10)2−2(−10)+3=123,加上本次噪声约17.64052,观测成为140.64052。设计矩阵这一行是 (1,−10,100);用未舍入的拟合参数做点积,得到该条预测 β0+(−10)β1+100β2≈137.89105。残差约为 137.89105−140.64052=−2.74947,平方后约 7.55960。X @ beta 一次算出10条预测,MSE 就是包括这项在内的10个平方残差取平均。

上两页最小化的是平方和,本页最后报告的是均方误差。样本数 n=10 固定,除以同一个正数会改变误差的数值,最优参数仍是同一组。

对应课堂录音Week07 Part01 00:08:53–00:12:54
原第 16 页

解释结果:为什么系数和真实值不同

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

运行上一页代码,按“常数项、一次项、二次项”的顺序得到

β≈(10.48013,−2.76561,0.99755)T,MSE≈69.63581.

所以拟合曲线是 y^=10.48013−2.76561x+0.99755x2。课件按“二次项、一次项、常数项”打印,因此写成约 1.00、−2.77、10.48;两种写法表示同一条曲线。

  1. 真实系数为 (3,−2,1),但观测值已经加了噪声。
  2. 最小二乘要贴近的是这 10 个含噪声的观测点,并不会自动知道生成它们的真实参数。
  3. 因此估计系数会偏离真实值。二次项约 0.998 接近 1,截距约 10.48 与 3 的差则较明显。
  4. MSE 约 69.64 表示平均平方残差。若想用原来的输出单位理解,可开平方,RMSE 约为 69.63581=8.345。

把拟合曲线和真实关系放在同一个输入上看。当输入为 0 时,真实值为 3,拟合值约为 10.48,两条曲线在这里相差约 7.48。

对应课堂录音Week07 Part01 00:08:53–00:12:54
原第 17 页

提高阶数:代码只需增加特征列

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

二次模型用 (1,x,x2),三次模型用 (1,x,x2,x3),九次模型用到 x9。各阶模型仍然对参数线性,所以都能调用同一个最小二乘求解器。

for degree in range(2, 10):
    X = np.column_stack([x**j for j in range(degree + 1)])
    beta = np.linalg.lstsq(X, y, rcond=None)[0]
    mse = np.mean((X @ beta - y)**2)
    print(degree, mse)
  1. range(2, 10) 依次产生 2、3、…、9,不包含 10。
  2. range(degree + 1) 产生从 0 到当前阶数的幂。x0=1,所以常数列也包含了。
  3. [x**j for j in ...] 是列表推导式:先生成每个幂次的整列,再拼在一起。
  4. 若 degree=3,X 有 10 行、4 列,参数也有 4 个。求解、预测和计算误差的步骤全部沿用。

把输入暂时缩成 x=(2,3)、阶数取2,列表 [x**j for j in range(3)] 依次生成 (1,1)、(2,3)、(4,9)。column_stack 再把它们拼成 [124139]:每一列是一种幂次,每一行对应一个样本。

对应课堂录音Week07 Part01 00:08:53–00:12:54Week07 Part01 00:12:56–00:18:19
原第 18 页

高阶拟合结果:训练误差降低意味着什么

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

继续使用相同 10 条含噪声数据,得到以下训练 MSE:

多项式阶数训练 MSE
269.63581
364.87556
458.06207
543.69879
635.29209
729.69206
817.00380
9约 0
  1. 阶数升高时,模型包含原先的低阶模型:把新增系数设为零,就能恢复旧模型。因此精确最小化后的训练误差不会增大。
  2. 九次多项式有 10 个系数,数据有 10 个不同输入,可以插值穿过全部 10 个点。程序里的极小非零误差来自浮点计算。
  3. 但这些点里有噪声。穿过每个点,也会把噪声的起伏拟合进去,点与点之间可能出现明显摆动。
  4. 我们真正关心的是新输入的预测。因此用另一些数据计算测试误差,才能判断提高阶数是否有帮助。
跟算:训练 MSE 接近零,输入为 9 时预测多少?

输入 x=9 位于两个训练输入约 7.78 与 10 之间,本次训练没有用到它。生成数据的无噪声公式给出 92−2(9)+3=66。把第17页循环里的各阶 β 与特征 (90,91,…,9degree) 做点积,得到二次模型约为 66.39,九次模型约为 159.63。九次训练 MSE 约为 0,在这个新输入上的绝对误差却约为 93.63。

在第17页循环中追加 print(np.array([9.0**j for j in range(degree + 1)]) @ beta) 可以复算。