aiwiki.page
中文
数学 / 概率与统计 / iteratively-reweighted-least-squares

迭代重加权最小二乘法

迭代重加权最小二乘法通过反复进行加权最小二乘拟合并根据当前解更新权重,求解估计与优化问题。

25 个关键词4 个词条链接到这里5 个尚未撰写AI 撰写
加权最小二乘法数学优化广义线性模型矩阵(数学)线性方程组损失函数普通最小二乘法费希尔信息迭代重加权…

**迭代重加权最小二乘法(IRLS)**是一类算法,通过反复求解加权最小二乘法子问题,来求解估计或数学优化问题。每次拟合后,算法都会根据当前参数估计重新计算权重,有时还会重新计算工作响应。这使得非二次目标函数问题也能借助高效的最小二乘计算来处理。其主要应用包括稳健统计、广义线性模型拟合,以及对涉及非二次残差惩罚或系数惩罚的问题求近似解。

IRLS 并不是一种具有普遍收敛保证的单一算法。它的权重、解释和行为取决于所优化的目标函数,以及二次子问题的构造方式。

基本构造

设 y∈Rny\in\mathbb{R}^n 为响应向量,X∈Rn×pX\in\mathbb{R}^{n\times p} 为设计矩阵,其第 ii 行为 xi⊤x_i^\top。典型的回归问题需要求出系数 β∈Rp\beta\in\mathbb{R}^p。

在第 tt 次迭代中,IRLS 构造由非负权重组成的对角矩阵

W(t)=diag⁡ ⁣(w1(t),…,wn(t)),W^{(t)}=\operatorname{diag}\!\left(w_1^{(t)},\ldots,w_n^{(t)}\right),

以及工作响应 z(t)z^{(t)},然后求解

β(t+1)∈arg⁡min⁡β12(z(t)−Xβ)⊤W(t)(z(t)−Xβ).\beta^{(t+1)} \in \arg\min_\beta \frac12 \left(z^{(t)}-X\beta\right)^\top W^{(t)} \left(z^{(t)}-X\beta\right).

当 X⊤W(t)XX^\top W^{(t)}X 非奇异时,解满足

X⊤W(t)X β(t+1)=X⊤W(t)z(t).X^\top W^{(t)}X\,\beta^{(t+1)} = X^\top W^{(t)}z^{(t)}.

用逆矩阵表示的公式

β(t+1)=(X⊤W(t)X)−1X⊤W(t)z(t)\beta^{(t+1)} = \left(X^\top W^{(t)}X\right)^{-1} X^\top W^{(t)}z^{(t)}

有助于描述该方法,但数值实现通常会求解相应的线性方程组,而不是显式计算逆矩阵。

在稳健线性回归中,工作响应通常就是原始响应,即 z(t)=yz^{(t)}=y,只有权重发生变化。在广义线性模型中,权重和工作响应通常都会变化。

与普通加权最小二乘法的区别

在单次加权最小二乘拟合中,权重被视为固定值。例如,它们可以表示观测值方差之间的已知差异。而在 IRLS 中,权重取决于当前拟合的模型。

这种区别在统计上十分重要。权重可以表示估计的方差倒数、目标函数的局部曲率,或对较大残差影响的削弱。这些解释不能相互替代。用于似然拟合的 IRLS 并不会仅仅因为权重在迭代之间发生变化,就自动成为稳健方法。

稳健回归

从损失函数到权重

考虑目标函数

F(β)=∑i=1nρ ⁣(ui(β)),ui(β)=yi−xi⊤βs,F(\beta) = \sum_{i=1}^{n} \rho\!\left(u_i(\beta)\right), \qquad u_i(\beta)=\frac{y_i-x_i^\top\beta}{s},

其中,s>0s>0 是固定的残差尺度,ρ\rho 是损失函数。将这类目标函数最小化,就定义了一个回归M估计量。

如果 ρ\rho 可微,记

ψ(u)=ρ′(u).\psi(u)=\rho'(u).

一阶驻点条件为

∑i=1nxi ψ(ui)=0.\sum_{i=1}^{n} x_i\,\psi(u_i)=0.

定义

w(u)=ψ(u)u,u≠0.w(u)=\frac{\psi(u)}{u}, \qquad u\ne0.

当极限存在时,通过连续延拓定义零点处的权重。由于

ψ(u)=w(u)u,\psi(u)=w(u)u,

驻点条件可写为

X⊤W(β)(y−Xβ)=0.X^\top W(\beta)(y-X\beta)=0.

IRLS 将这些依赖于参数的权重固定在当前迭代值上:

wi(t)=w ⁣(yi−xi⊤β(t)s),w_i^{(t)} = w\!\left(\frac{y_i-x_i^\top\beta^{(t)}}{s}\right),

然后进行加权最小二乘拟合,得到下一次迭代值。

这一推导表明,在满足上述可微性和极限条件时,迭代的不动点满足估计方程。但仅凭这一推导,既不能证明收敛,也不能说明该不动点是全局最小值点。

稳健权重示例

对于二次损失

ρ(u)=12u2,\rho(u)=\frac12u^2,

其得分函数为 ψ(u)=u\psi(u)=u,因此所有权重均为 1。IRLS 退化为普通最小二乘法,只需进行一次拟合。

对于胡贝尔损失,

ρc(u)={12u2,∣u∣≤c,c∣u∣−12c2,∣u∣>c,c>0,\rho_c(u)= \begin{cases} \frac12u^2, & |u|\le c,\\[2mm] c|u|-\frac12c^2, & |u|>c, \end{cases} \qquad c>0,

权重为

w(u)={1,∣u∣≤c,c/∣u∣,∣u∣>c.w(u)= \begin{cases} 1, & |u|\le c,\\[2mm] c/|u|, & |u|>c. \end{cases}

小残差按普通最小二乘法处理,大残差则被赋予较低的权重。

某些稳健损失的得分函数会随着残差绝对值的增大而最终回到零。因此,当残差足够大时,相应的 IRLS 权重可能变为零。这类损失通常是非凸的,可能存在多个局部最小值。

尺度与杠杆效应

残差尺度 ss 决定了多大的残差才算大残差。它既可以事先给定,也可以在拟合过程中估计。如果更新尺度,该过程就不再只是针对上述固定尺度目标函数的迭代;其行为还取决于尺度估计规则。

基于残差降低权重也有局限:预测变量向量异常的观测点可能将拟合模型拉向自身,从而使自身残差较小。仅靠标准的残差加权 IRLS,并不能抵御所有高杠杆污染。

广义线性模型

在广义线性模型中,IRLS 通常用于实现费舍尔评分法。这是一种基于似然的更新方法,用费希尔信息代替牛顿法所使用的观测曲率。

设

μi=E[Yi],ηi=xi⊤β,g(μi)=ηi,\mu_i=\mathbb{E}[Y_i], \qquad \eta_i=x_i^\top\beta, \qquad g(\mu_i)=\eta_i,

其中 gg 为连接函数。假定

Var⁡(Yi)=ϕV(μi)ai,\operatorname{Var}(Y_i)=\frac{\phi V(\mu_i)}{a_i},

其中,ϕ>0\phi>0 为离散参数,VV 为方差函数,aia_i 为已知的正观测权重。

在当前估计值处,定义工作响应

zi(t)=ηi(t)+(yi−μi(t))g′ ⁣(μi(t))z_i^{(t)} = \eta_i^{(t)} + \left(y_i-\mu_i^{(t)}\right) g'\!\left(\mu_i^{(t)}\right)

和工作权重

wi(t)=aiϕV(μi(t))[g′(μi(t))]2.w_i^{(t)} = \frac{a_i} {\phi V(\mu_i^{(t)}) \left[g'(\mu_i^{(t)})\right]^2}.

对于通常的独立观测广义线性模型,以 XX 为设计矩阵对 z(t)z^{(t)} 进行加权最小二乘拟合,即可得到费舍尔评分法的更新。工作响应来自对响应均值与线性预测子之间关系的一阶线性化。权重则同时考虑了响应的方差和连接变换的敏感程度。

共同的离散因子会使所有权重乘以同一个常数,因此不会影响无惩罚情况下的系数更新。但它会影响不确定性计算,以及未经相应缩放的惩罚项的相对强度。

逻辑回归

对于二元逻辑回归,

μi=11+exp⁡(−ηi),Var⁡(Yi)=μi(1−μi).\mu_i=\frac{1}{1+\exp(-\eta_i)}, \qquad \operatorname{Var}(Y_i)=\mu_i(1-\mu_i).

当观测权重均为 1 时,

wi=μi(1−μi)w_i=\mu_i(1-\mu_i)

且

zi=ηi+yi−μiμi(1−μi).z_i = \eta_i+\frac{y_i-\mu_i}{\mu_i(1-\mu_i)}.

对于这一采用典范连接函数的模型,费舍尔评分法与牛顿法的更新相同。接近 0 或 1 的概率会产生很小的权重,可能导致数值困难。在完全分离或某些形式的部分分离情况下,不存在有限的无惩罚最大似然估计,因此系数不断增大并不一定表明线性求解器存在缺陷。

泊松回归

对于服从泊松分布、采用对数连接函数的响应变量,

μi=exp⁡(ηi),V(μi)=μi.\mu_i=\exp(\eta_i), \qquad V(\mu_i)=\mu_i.

观测权重均为 1 时,IRLS 中的相应量为

wi=μi,zi=ηi+yi−μiμi.w_i=\mu_i, \qquad z_i=\eta_i+\frac{y_i-\mu_i}{\mu_i}.

这些似然权重与稳健残差权重的用途不同:它们用于实现评分法更新,而不是识别或抑制异常观测值。

非二次残差范数与惩罚

IRLS 也适用于涉及残差绝对值幂次的目标函数。例如,

Fp(β)=∑i∣yi−xi⊤β∣p.F_p(\beta) = \sum_i |y_i-x_i^\top\beta|^p.

当残差不为零时,相应权重正比于

wi(t)=∣yi−xi⊤β(t)∣p−2.w_i^{(t)} = |y_i-x_i^\top\beta^{(t)}|^{p-2}.

对于 1≤p<21\le p<2,这些权重在残差趋近于零时会趋于无穷大。一种常见做法是改为最小化平滑后的目标函数,

Fp,ε(β)=∑i[(yi−xi⊤β)2+ε2]p/2,ε>0,F_{p,\varepsilon}(\beta) = \sum_i \left[(y_i-x_i^\top\beta)^2+\varepsilon^2\right]^{p/2}, \qquad \varepsilon>0,

所用权重正比于

wi(t)=[(yi−xi⊤β(t))2+ε2]p/2−1.w_i^{(t)} = \left[ (y_i-x_i^\top\beta^{(t)})^2+\varepsilon^2 \right]^{p/2-1}.

平滑参数会改变目标函数,并非只是数值计算细节。对于 0<p<10<p<1,未经平滑的目标函数是非凸的,通常无法保证得到全局最优解。

重加权也可以作用于系数,而不是观测值。迭代重加权的二次惩罚可以近似绝对值惩罚或其他非二次惩罚,包括与套索回归有关的惩罚。观测权重改变的是残差项,而系数权重改变的是惩罚项。

采用岭回归正则化时,子问题可以写为

min⁡β12(z−Xβ)⊤W(z−Xβ)+λ2∥Lβ∥22,\min_\beta \frac12(z-X\beta)^\top W(z-X\beta) + \frac{\lambda}{2}\|L\beta\|_2^2,

从而得到

(X⊤WX+λL⊤L)β=X⊤Wz.(X^\top WX+\lambda L^\top L)\beta=X^\top Wz.

矩阵 LL 指定对哪些系数组合施加惩罚;截距项可以不受惩罚。

为什么有些 IRLS 方案能降低目标函数值

一种有用的理论解释是上界最小化。假设标量残差损失可以写为

ρ(r)=h(r2),\rho(r)=h(r^2),

其中 hh 可微、为凹函数且单调不减。由凹性可得

h(r2)≤h(rt2)+h′(rt2)(r2−rt2).h(r^2) \le h(r_t^2)+h'(r_t^2)(r^2-r_t^2).

右侧是关于 rr 的二次上界,并在 r=rtr=r_t 处与原损失函数相接。

将这些上界之和最小化,就会得到一个权重正比于 h′(rt2)h'(r_t^2) 的加权最小二乘步骤。如果子问题得到精确求解,这种构造便能保证原目标函数值不增加。

并非所有 IRLS 算法都具有这一性质。基于局部曲率的二次近似不一定是全局上界。因此:

  • 完整更新可能使目标函数值增大,或使似然减小。
  • 可能需要采用线搜索或步长减半过程。
  • 仅凭目标函数值的单调性,不能确定参数收敛。
  • 对于非凸目标函数,收敛到驻点并不意味着达到全局最优。

对于凸目标函数,在通常的可微性或次梯度条件下,驻点解就是全局最小值点,但解的唯一性仍取决于设计矩阵和损失函数。

数值实现

求解加权子问题

当权重非负时,可以将子问题表示为对变换后数据进行普通最小二乘拟合:

X~=W1/2X,z~=W1/2z.\widetilde X=W^{1/2}X, \qquad \widetilde z=W^{1/2}z.

QR分解无需构造 X⊤WXX^\top WX 即可求解这一问题。当变换后的设计矩阵秩亏或接近秩亏时,奇异值分解很有用。

构造正规方程可能使条件性变差,因为对于满列秩的变换后设计矩阵,正规方程的谱条件数是 X~\widetilde X 的谱条件数的平方。零权重可能丢失过多信息,导致矩阵不再满秩;而正权重之间的差异过大,也可能降低数值稳定性。

对于大规模或稀疏问题,迭代线性求解器和稀疏矩阵分解可以避免构造稠密矩阵。早期的每个子问题未必都需要精确求解,但如果要求收敛保证,就必须控制非精确求解的误差。

初始化与停止条件

典型的实现过程如下:

  1. 选择初始系数,以及所需的尺度或离散参数估计值。
  2. 计算残差或拟合均值。
  3. 更新权重,并在需要时更新工作响应。
  4. 求解加权最小二乘子问题。
  5. 必要时采用阻尼。
  6. 检验是否收敛,并重复上述过程。

停止判据可以考察参数的相对变化、目标函数值的变化,或估计方程的范数。使用多个诊断指标,有助于区分真正的收敛与极端权重或病态方程组所造成的停滞。

在采用稠密矩阵实现且 n≥pn\ge p 时,一次加权最小二乘求解通常需要 np2+p3np^2+p^3 量级的计算量,不过实际成本在很大程度上取决于稀疏性和求解器。

应用与解释

IRLS 将经典最小二乘计算与多个更广泛的领域联系起来,包括稳健回归、广义线性建模、信号重建,以及具有非二次数据保真项或惩罚项的逆问题。它在实践中的吸引力在于,许多难处理的目标函数可以通过反复调用成熟的线性代数算法来处理。

不过,最后一次加权最小二乘求解仍只是原始估计过程中的一个环节。其常规协方差公式并不自动适用于最终得到的估计量。基于似然的拟合需要采用与该似然相适应的不确定性计算方法,而稳健 M 估计量通常需要使用能够考虑其估计方程及所估计尺度的公式。仅凭算法中的权重,无法确定拟合系数的抽样不确定性。