当前位置：首页 > news >正文

广义矩估计随机近似中公式(2d)的推导

news 2025/8/15 10:40:38

公式（2d）的推导
在这里插入图片描述

这涉及到GMM估计中权重矩阵的最优性条件，我将从理论和算法两个层面完整解析：

1. 理论层面：最优权重矩阵的条件

在GMM框架下，渐近最优权重矩阵确实是矩条件的协方差矩阵的逆：
$W_{\text{opt}} = \Omega^{-1} = \left( \mathbb{E}[g_i(\beta_*)g_i(\beta_*)'] \right)^{-1}$
为什么？

Hansen (1982) 证明：当 $\Omega^{-1}$ 时，GMM估计量达到半参数效率界（最小渐近方差）。
直观理解： $Ω−1\Omega^{-1}$ 对高方差的矩条件赋予低权重，实现统计意义上的最优加权。

2. 算法层面：为什么使用 $(E[zizi′])−1(\mathbb{E}[z_i z_i'])^{-1}$ ？

在线性工具变量回归中（模型： $yi=xi′β+uiy_i = x_i'\beta + u_i$ ， $E[uizi]=0\mathbb{E}[u_i z_i] = 0$ ）：

矩条件： $gi(β)=zi(yi−xi′β)=ziuig_i(\beta) = z_i (y_i - x_i'\beta) = z_i u_i$
矩条件协方差： $Ω=E[gigi′]=E[ui2zizi′]\Omega = \mathbb{E}[g_i g_i'] = \mathbb{E}[u_i^2 z_i z_i']$

关键假设：同方差性

若满足同方差（ $E[ui2∣zi]=σ2\mathbb{E}[u_i^2 | z_i] = \sigma^2$ ），则：
$\Omega = \mathbb{E}[u_i^2 z_i z_i'] = \sigma^2 \mathbb{E}[z_i z_i'] = \sigma^2 Q$
此时：
$W_{\text{opt}} = \Omega^{-1} = \frac{1}{\sigma^2} Q^{-1}$
→ $Q^{-1}$ 与 $Ω−1\Omega^{-1}$ 仅差常数倍，不影响估计效率。

算法选择 $Q^{-1}$ 的原因

计算可行性：
- $\mathbb{E}[z_i z_i']$ 可直接从数据估计（无需未知参数 $β\beta$ ）。
- $Ω=E[ui2zizi′]\Omega = \mathbb{E}[u_i^2 z_i z_i']$ 依赖 $ui=yi−xi′βu_i = y_i - x_i'\beta$ （需已知 $β\beta$ ），形成循环依赖。
在线实现：
- $Q$ 的在线逆可通过 SMW 高效更新（如 (2c)-(2d)）。
- $Ω\Omega$ 的在线估计需同时拟合 $β\beta$ 和残差 $u^i2\hat{u}_i^2$ ，计算复杂且不稳定。
统计性质：
- 即使存在异方差，使用 $Q^{-1}$ 仍能保证一致性（只是非效率最优）。
- 在线算法可通过两阶段更新逼近 $Ω−1\Omega^{-1}$ （见下文改进方案）。

3. SGMM 的实际处理

在您提到的算法中：

第一阶段（默认操作）：
使用 $Wi=(En[zizi′])−1W_i = (\mathbb{E}_n[z_i z_i'])^{-1}$ 作为初始权重，计算初步估计 $β~\tilde{\beta}$ 。
第二阶段（效率提升）：
1. 用 $β~\tilde{\beta}$ 计算残差 $u^i=yi−xi′β~\hat{u}_i = y_i - x_i'\tilde{\beta}$ 。
2. 估计 $Ω^=1n∑u^i2zizi′\hat{\Omega} = \frac{1}{n} \sum \hat{u}_i^2 z_i z_i'$ 。
3. 设 $W=Ω^−1W = \hat{\Omega}^{-1}$ 重新估计 $β\beta$ 。

但在在线场景中：

第二阶段需存储所有历史数据计算 $Ω^\hat{\Omega}$ ，违背流式处理原则。
因此算法选择 $Q^{-1}$ 是效率与计算代价的权衡。

4. 如何在线逼近最优权重 $Ω−1\Omega^{-1}$ ？

方案 1：残差加权 SMW（需额外存储）

用 $Q^{-1}$ 估计初始 $β~n\tilde{\beta}_n$ 。
计算残差 $u^i\hat{u}_i$ 并在线更新：
$Ω^i=i−1iΩ^i−1+1iu^i2zizi′ \hat{\Omega}_i = \frac{i-1}{i} \hat{\Omega}_{i-1} + \frac{1}{i} \hat{u}_i^2 z_i z_i'$
用 SMW 更新 $Wi=Ω^i−1W_i = \hat{\Omega}_i^{-1}$ （需修改 (2c)-(2d)）。

缺陷：需存储所有 ${u^i,zi}\{\hat{u}_i, z_i\}$ 或牺牲实时性。

方案 2：随机加权（本文算法选择）

在 (2d) 中隐式使用 $Q^{-1}$ 作为权重。
通过 Polyak 平均 $βˉn\bar{\beta}_n$ 降低方差，逼近最优效率。
理论保证：即使非最优权重， $βˉn\bar{\beta}_n$ 仍渐近正态：
$\sqrt{n} (\bar{\beta}_n - \beta_*) \xrightarrow{d} N(0, \Sigma)$
其中 $Σ\Sigma$ 可能大于最优方差，但一致性保持。

结论：为什么算法如此设计？

可行性优先：
$Q^{-1}$ 可在线高效计算， $Ω−1\Omega^{-1}$ 则不能。
一致性保障：
即使非最优权重，GMM 仍保持一致性。
计算-效率权衡：
在线场景下，Polyak 平均部分补偿权重非最优的方差损失。
扩展性：
若需更高效率，可周期性重构 $Ω^−1\hat{\Omega}^{-1}$ （牺牲部分实时性）。

✅ 总结：使用 $(E[zizi′])−1(\mathbb{E}[z_i z_i'])^{-1}$ 不是理论最优解，但是流数据约束下的最优可行解。它体现了在线算法的核心哲学——在统计效率与计算可行性间寻求平衡。

重新回答：公式 (2c) 和 (2d) 的完整解析

1. 为什么需要 (2c) 和 (2d)？

在 SGMM 算法中，权重矩阵 $W_i$ 的核心作用是：

统计功能：逼近最优权重 $(\mathbb{E}[z_i z_i'])^{-1}$ （工具变量协方差矩阵的逆）
算法功能：在 (2a) 中缩放梯度方向，加速收敛：
$\beta_i = \beta_{i-1} - \gamma_i \underbrace{(\Phi_{i-1}' W_{i-1} \Phi_{i-1})^\dagger \Phi_{i-1}' W_{i-1}}_{\text{缩放矩阵}} g_i(\beta_{i-1})$
若直接计算 $Wi=(1n∑zizi′)−1W_i = (\frac{1}{n} \sum z_i z_i')^{-1}$ ，需 $O(d_g^3)$ 时间，无法满足在线学习需求。
(2c)-(2d) 通过 SMW 公式将计算复杂度降至 $O(d_g^2)$ ，实现高效在线更新。

2. 为什么对 $W$ 求逆（而非矩条件协方差逆）？

理论最优性要求：
真正的最优权重应为矩条件协方差逆 $Ω−1=(E[gigi′])−1\Omega^{-1} = (\mathbb{E}[g_i g_i'])^{-1}$ 。
算法可行性妥协：
$Ω=E[ui2zizi′]\Omega = \mathbb{E}[u_i^2 z_i z_i']$ 依赖残差 $ui=yi−xi′βu_i = y_i - x_i'\beta$ （未知），无法直接在线估计。
次优但可行的选择：
当满足同方差假设（ $E[ui2∣zi]=σ2\mathbb{E}[u_i^2 | z_i] = \sigma^2$ ）时：
$\Omega = \sigma^2 \mathbb{E}[z_i z_i'] \implies \Omega^{-1} \propto (\mathbb{E}[z_i z_i'])^{-1}$
此时 $Wi=(1n∑zizi′)−1W_i = (\frac{1}{n} \sum z_i z_i')^{-1}$ 是理论最优的可行近似。

3. 不用 SMW 的常规更新方法

步骤 1：递归更新协方差矩阵

$Q_i = \frac{n_0 + i - 1}{n_0 + i} Q_{i-1} + \frac{1}{n_0 + i} z_i z_i'$

计算成本：矩阵加法 $O(d_g^2)$

步骤 2：显式求逆

$W_i = Q_i^{-1}$

计算成本： $O(d_g^3)$ （如 LU 分解）
内存需求：存储历史 ${z_i\}$ 或完整矩阵 $Q_i$ （ $O(d_g^2)$ ）

缺陷：
当工具变量维度 $d_g = 100$ 时，单次求逆需 $10^6$ 次浮点运算，无法满足高吞吐流数据需求。

4. SMW 求逆的推导与实现

理论基础：Sherman-Morrison-Woodbury 公式

对秩-1 更新 $A + u v^{'}$ ，其逆矩阵为：
$uv')^{-1} = A^{-1} - \frac{A^{-1} uv' A^{-1}}{1 + v' A^{-1} u}$

关键优势：将矩阵求逆转化为标量运算（分母 $1 + v' A^{-1} u$ ）

在 SGMM 中的具体应用

识别秩-1 结构：
将协方差更新改写为：
$Q_i = \underbrace{\frac{n_0 + i - 1}{n_0 + i} Q_{i-1}}_{A} + \underbrace{z_i}_{u} \underbrace{z_i'}_{v'} \cdot \frac{1}{n_0 + i}$
代入 SMW 公式：
$W_i = \left( A + c \cdot uv' \right)^{-1} = A^{-1} - \frac{c \cdot A^{-1} u v' A^{-1}}{1 + c \cdot v' A^{-1} u}$
其中 $\frac{1}{n_0 + i}$ .
逐步化简：
- 计算 $A^{-1}$ ：
  $A^{-1} = \frac{n_0 + i}{n_0 + i - 1} W_{i-1}$
- 计算标量项：
  $A^{-1} u = z_i' \left( \frac{n_0 + i}{n_0 + i - 1} W_{i-1} \right) z_i$
- 定义核心标量 $m_i$ （公式 2c）：
  $m_i = n_0 + i - 1 + z_i' W_{i-1} z_i$
  使得：
  $\cdot v' A^{-1} u = \frac{m_i}{n_0 + i - 1}$
- 最终形式（公式 2d）：
  $W_i = \frac{n_0 + i}{n_0 + i - 1} W_{i-1} \left( I - \frac{1}{m_i} z_i z_i' W_{i-1} \right)$

5. 为什么 SMW 是革命性的？

方法	计算复杂度	内存需求	在线适应性
直接求逆	$O(d_g^3)$	$O(d_g^2)$	差
SMW 更新	$O(d_g^2)$	$O(d_g^2)$	优

计算示例：
若 $d_g = 200$ ，单次更新节省计算量：
$\frac{200^3}{200^2} = 200 \text{ 倍}$
统计意义：
$m_i$ 动态调整权重（ $m_i$ 越大，新样本权重越低），增强数值稳定性。

总结：SMW 在 SGMM 中的核心价值

数学等价性：
严格满足 $Wi=(1n∑zizi′)−1W_i = (\frac{1}{n} \sum z_i z_i')^{-1}$ ，无近似误差。
在线可行性：
每步更新仅需矩阵-向量乘法（ $O(d_g^2)$ ），适合高维流数据。
统计鲁棒性：
通过 $m_i = n_0 + i - 1 + z_i' W_{i-1} z_i$ 实现自适应加权：
- $z_i' W_{i-1} z_i$ 是当前样本的马氏距离，自动抑制异常值影响。
架构统一性：
与 (2b) 的递归平均、 (2e) 的 Polyak 平均协同，构成完整的在线优化框架。

最终结论：
(2c)-(2d) 不是可选项，而是大规模流式 GMM 的必然选择。它通过数学等价变换（SMW 公式），将理论上的不可能（在线求逆）转化为可能，是统计学与计算科学的完美结合。

严格推导：从 SMW 公式到 (2d) 的完整过程

已知条件

协方差矩阵递归式：
$Q_i = \frac{n_0 + i - 1}{n_0 + i} Q_{i-1} + \frac{1}{n_0 + i} z_i z_i'$
SMW 公式（秩-1 更新求逆）：
$uv')^{-1} = A^{-1} - \frac{A^{-1} uv' A^{-1}}{1 + v' A^{-1} u}$
变量替换：
$\frac{n_0 + i - 1}{n_0 + i} Q_{i-1}, \quad u = z_i, \quad v = z_i, \quad c = \frac{1}{n_0 + i}$
即：
$Q_i = A + c \cdot uv'$

步骤 1：计算 $A^{-1}$

$A^{-1} = \left( \frac{n_0 + i - 1}{n_0 + i} Q_{i-1} \right)^{-1} = \frac{n_0 + i}{n_0 + i - 1} Q_{i-1}^{-1} = \frac{n_0 + i}{n_0 + i - 1} W_{i-1}$

步骤 2：计算标量项 $v' A^{-1} u$

$A^{-1} u = z_i' \left( \frac{n_0 + i}{n_0 + i - 1} W_{i-1} \right) z_i = \frac{n_0 + i}{n_0 + i - 1} \cdot \underbrace{z_i' W_{i-1} z_i}_{\text{标量}}$

步骤 3：定义 $m_i$ （公式 2c）

$m_i = n_0 + i - 1 + z_i' W_{i-1} z_i$
目的：将分母转化为 $m_i$ 的表达式：
$\cdot v' A^{-1} u = 1 + \frac{1}{n_0 + i} \cdot \frac{n_0 + i}{n_0 + i - 1} \cdot (z_i' W_{i-1} z_i) = \frac{n_0 + i - 1 + z_i' W_{i-1} z_i}{n_0 + i - 1} = \frac{m_i}{n_0 + i - 1}$

步骤 4：展开分子项 $A^{-1} u v' A^{-1}$

$A^{-1} u v' A^{-1} = \left( \frac{n_0 + i}{n_0 + i - 1} W_{i-1} \right) z_i z_i' \left( \frac{n_0 + i}{n_0 + i - 1} W_{i-1} \right) = \left( \frac{n_0 + i}{n_0 + i - 1} \right)^2 W_{i-1} z_i z_i' W_{i-1}$

步骤 5：代入 SMW 公式

$W_i = A^{-1} - \frac{c \cdot A^{-1} u v' A^{-1}}{1 + c \cdot v' A^{-1} u} = \frac{n_0 + i}{n_0 + i - 1} W_{i-1} - \frac{ \frac{1}{n_0 + i} \cdot \left( \frac{n_0 + i}{n_0 + i - 1} \right)^2 W_{i-1} z_i z_i' W_{i-1} }{ \frac{m_i}{n_0 + i - 1} }$

步骤 6：化简分式

$\text{分式} = \frac{ \frac{1}{n_0 + i} \cdot \frac{(n_0 + i)^2}{(n_0 + i - 1)^2} W_{i-1} z_i z_i' W_{i-1} }{ \frac{m_i}{n_0 + i - 1} } = \frac{n_0 + i}{(n_0 + i - 1)^2} \cdot \frac{n_0 + i - 1}{m_i} W_{i-1} z_i z_i' W_{i-1} = \frac{n_0 + i}{(n_0 + i - 1) m_i} W_{i-1} z_i z_i' W_{i-1}$

步骤 7：合并表达式

$W_i = \frac{n_0 + i}{n_0 + i - 1} W_{i-1} - \frac{n_0 + i}{(n_0 + i - 1) m_i} W_{i-1} z_i z_i' W_{i-1}$

步骤 8：提取公因子（关键步骤）

$W_i = \frac{n_0 + i}{n_0 + i - 1} W_{i-1} \left( I - \frac{1}{m_i} z_i z_i' W_{i-1} \right)$

推导验证

1. 维度一致性检查

$Wi−1∈Rdg×dgW_{i-1} \in \mathbb{R}^{d_g \times d_g}$
$zizi′∈Rdg×dgz_i z_i' \in \mathbb{R}^{d_g \times d_g}$
$zizi′Wi−1∈Rdg×dgz_i z_i' W_{i-1} \in \mathbb{R}^{d_g \times d_g}$
括号内 $\frac{1}{m_i} z_i z_i' W_{i-1}$ 是 $dg×dgd_g \times d_g$ 矩阵
→ 维度匹配，公式成立。

2. 数值稳定性验证

当 $z_i = 0$ 时：
$m_i = n_0 + i - 1 \implies W_i = \frac{n_0 + i}{n_0 + i - 1} W_{i-1} \left( I - 0 \right) = \frac{n_0 + i}{n_0 + i - 1} W_{i-1}$
与协方差矩阵缩放一致（新增零样本不改变方向）。

为什么必须如此设计？

数学必要性：
只有通过 $m_i$ 的定义，才能将 SMW 公式中的复杂分式压缩为标量运算。
计算优化：
原始 SMW 需计算 $A^{-1} u$ （ $O(d_g^2)$ ）和 $v' A^{-1} u$ （ $O(d_g^2)$ ），而 (2c)-(2d) 通过预计算 $m_i$ 将额外开销降至 $O(d_g)$ 。
统计解释：
$m_i$ 的物理意义是有效样本量：
- $n_0 + i - 1$ ：历史累积信息
- $z_i' W_{i-1} z_i$ ：当前样本的相对影响力（马氏距离）

结论

(2c)-(2d) 是数学精确性与计算效率的完美结合：

数学等价：严格满足 $W_i = Q_i^{-1}$ ，无近似误差。
在线可行：每步更新仅需：
- 1 次矩阵-向量乘（ $z_i' W_{i-1} z_i$ ， $O(d_g^2)$ ）
- 1 次外积（ $z_i z_i'$ ， $O(d_g^2)$ ）
- 1 次矩阵乘法（ $Wi−1⋅(zizi′)W_{i-1} \cdot (z_i z_i')$ ， $O(d_g^3)$ 但可优化为 $O(d_g^2)$ ）
统计鲁棒：通过 $m_i$ 实现自适应加权，抑制异常值影响。