随机逼近
字数 2201 2025-11-02 11:44:13

随机逼近

随机逼近是一种用于在随机环境中寻找函数根或极值的迭代方法。当目标函数无法直接观测，只能通过带有噪声的测量值来估计时，该方法尤其有用。

1. 基本思想与问题设定
想象一个场景：我们想找到一个未知函数 \(h(\theta)\) 的根，即满足 \(h(\theta) = 0\) 的参数 \(\theta\)。然而，我们无法直接计算 \(h(\theta)\)，每次我们选择一个参数 \(\theta_n\) 进行试验时，我们只能观测到一个带有噪声的测量值 \(Y_n = h(\theta_n) + \epsilon_n\)，其中 \(\epsilon_n\) 是随机噪声。随机逼近的目标就是设计一个迭代序列 \(\{\theta_n\}\)，使得它能在这种嘈杂的观测下收敛到真正的根 \(\theta^*\)。

2. 核心算法：Robbins-Monro 算法
这是随机逼近领域最开创性的工作。其迭代格式如下：

\[\theta_{n+1} = \theta_n - a_n Y_n \]

这里：

  • \(\theta_n\) 是第 \(n\) 步迭代的参数估计值。
  • \(Y_n\) 是在 \(\theta_n\) 处观测到的带有噪声的函数值。
  • \(a_n\) 是一个正的步长序列。

工作原理的直观解释：

  • 方向：观测值 \(Y_n\) 提供了关于函数 \(h(\theta_n)\) 符号的信息。如果 \(h(\theta_n) > 0\)（即使有噪声，我们观测到的 \(Y_n\) 也大概率是正的），我们希望减小 \(\theta\) 以接近根，因此迭代中减去一个正数。反之亦然。
  • 步长：步长序列 \(a_n\) 的选择至关重要。它必须满足两个条件：
  1. \(a_n \to 0\)：这确保了迭代的“方差”最终会消失，算法不会因为噪声而永远震荡。步长逐渐减小，使过程最终稳定下来。
  2. \(\sum_{n=1}^{\infty} a_n = \infty\)：这确保了迭代有足够的“能量”到达真解，即使初始估计离得很远。如果步长衰减太快（如 \(a_n = 1/n^2\)），迭代可能在到达根之前就停止了。

3. 算法的收敛性
在一定的正则性条件下（例如，函数 \(h(\theta)\) 是光滑的、穿过根时是递增的，噪声 \(\epsilon_n\) 是零均值且条件方差有界），Robbins-Monro 算法能以概率 1 收敛到根 \(\theta^*\)，即 \(P(\lim_{n\to\infty} \theta_n = \theta^*) = 1\)。这种收敛性被称为“几乎必然收敛”。

4. 推广：Kiefer-Wolfowitz 算法（用于随机优化）
Robbins-Monro 算法解决的是找函数根的问题。如果我们面临的是随机优化问题：最小化一个期望目标函数 \(F(\theta) = E[f(\theta, \xi)]\)，其中 \(\xi\) 是随机变量，我们无法直接获得 \(F(\theta)\) 或其梯度，只能通过采样得到带有噪声的函数值。Kiefer-Wolfowitz 算法将随机逼近的思想应用于此。

  • 核心思想：用有限差分来近似梯度。
  • 迭代格式：

\[ \theta_{n+1} = \theta_n - a_n \hat{g}_n \]

其中，梯度估计量 \(\hat{g}_n\) 通过对称差分计算：

\[ \hat{g}_n = \frac{f(\theta_n + c_n, \xi_n^{(1)}) - f(\theta_n - c_n, \xi_n^{(2)})}{2c_n} \]

这里，\(c_n\) 是另一个趋于零的序列（差分间隔），\(\xi_n^{(1)}\) 和 \(\xi_n^{(2)}\) 是独立的随机样本。这个估计量的期望值近似于真实的梯度 \(\nabla F(\theta_n)\)，偏差会随着 \(c_n \to 0\) 而消失。

5. 与现代随机梯度下降的联系
随机逼近是随机梯度下降（SGD） 的理论基石。在机器学习中，我们最小化经验风险 \(F(\theta) = \frac{1}{N} \sum_{i=1}^N L(\theta; x_i, y_i)\)。当 \(N\) 极大时，精确计算梯度代价高昂。SGD 在每一步随机抽取一个样本（或一小批样本）\(i_n\)，并用其梯度作为真实梯度的带噪声估计：

\[\theta_{n+1} = \theta_n - a_n \nabla L(\theta_n; i_n) \]

这完全符合随机逼近的框架：这里的“噪声”源于用单个样本的梯度去估计全体样本的平均梯度。因此，随机逼近的理论为SGD的收敛性提供了严格的数学保证。

总结
随机逼近提供了一套强大的数学工具，用于在只能获得带噪声反馈的随机环境中进行根查找和优化。从经典的Robbins-Monro算法到现代的大规模机器学习中的SGD，其核心思想都是通过精心设计的递减步长，巧妙地平衡“搜索新区域”和“衰减噪声影响”，从而确保迭代过程能够稳健地收敛到目标解。

随机逼近 随机逼近是一种用于在随机环境中寻找函数根或极值的迭代方法。当目标函数无法直接观测，只能通过带有噪声的测量值来估计时，该方法尤其有用。 1. 基本思想与问题设定 想象一个场景：我们想找到一个未知函数 \( h(\theta) \) 的根，即满足 \( h(\theta) = 0 \) 的参数 \(\theta\)。然而，我们无法直接计算 \( h(\theta) \)，每次我们选择一个参数 \(\theta_ n\) 进行试验时，我们只能观测到一个带有噪声的测量值 \( Y_ n = h(\theta_ n) + \epsilon_ n \)，其中 \(\epsilon_ n\) 是随机噪声。随机逼近的目标就是设计一个迭代序列 \(\{\theta_ n\}\)，使得它能在这种嘈杂的观测下收敛到真正的根 \(\theta^* \)。 2. 核心算法：Robbins-Monro 算法 这是随机逼近领域最开创性的工作。其迭代格式如下： \[ \theta_ {n+1} = \theta_ n - a_ n Y_ n \] 这里： \(\theta_ n\) 是第 \(n\) 步迭代的参数估计值。 \(Y_ n\) 是在 \(\theta_ n\) 处观测到的带有噪声的函数值。 \(a_ n\) 是一个正的步长序列。 工作原理的直观解释 ： 方向 ：观测值 \(Y_ n\) 提供了关于函数 \(h(\theta_ n)\) 符号的信息。如果 \(h(\theta_ n) > 0\)（即使有噪声，我们观测到的 \(Y_ n\) 也大概率是正的），我们希望减小 \(\theta\) 以接近根，因此迭代中减去一个正数。反之亦然。 步长 ：步长序列 \(a_ n\) 的选择至关重要。它必须满足两个条件： \(a_ n \to 0\)：这确保了迭代的“方差”最终会消失，算法不会因为噪声而永远震荡。步长逐渐减小，使过程最终稳定下来。 \(\sum_ {n=1}^{\infty} a_ n = \infty\)：这确保了迭代有足够的“能量”到达真解，即使初始估计离得很远。如果步长衰减太快（如 \(a_ n = 1/n^2\)），迭代可能在到达根之前就停止了。 3. 算法的收敛性 在一定的正则性条件下（例如，函数 \(h(\theta)\) 是光滑的、穿过根时是递增的，噪声 \(\epsilon_ n\) 是零均值且条件方差有界），Robbins-Monro 算法能以概率 1 收敛到根 \(\theta^ \)，即 \(P(\lim_ {n\to\infty} \theta_ n = \theta^ ) = 1\)。这种收敛性被称为“几乎必然收敛”。 4. 推广：Kiefer-Wolfowitz 算法（用于随机优化） Robbins-Monro 算法解决的是找函数根的问题。如果我们面临的是 随机优化问题 ：最小化一个期望目标函数 \(F(\theta) = E[ f(\theta, \xi) ]\)，其中 \(\xi\) 是随机变量，我们无法直接获得 \(F(\theta)\) 或其梯度，只能通过采样得到带有噪声的函数值。Kiefer-Wolfowitz 算法将随机逼近的思想应用于此。 核心思想 ：用有限差分来近似梯度。 迭代格式 ： \[ \theta_ {n+1} = \theta_ n - a_ n \hat{g}_ n \] 其中，梯度估计量 \(\hat{g}_ n\) 通过对称差分计算： \[ \hat{g}_ n = \frac{f(\theta_ n + c_ n, \xi_ n^{(1)}) - f(\theta_ n - c_ n, \xi_ n^{(2)})}{2c_ n} \] 这里，\(c_ n\) 是另一个趋于零的序列（差分间隔），\(\xi_ n^{(1)}\) 和 \(\xi_ n^{(2)}\) 是独立的随机样本。这个估计量的期望值近似于真实的梯度 \(\nabla F(\theta_ n)\)，偏差会随着 \(c_ n \to 0\) 而消失。 5. 与现代随机梯度下降的联系 随机逼近是 随机梯度下降（SGD） 的理论基石。在机器学习中，我们最小化经验风险 \(F(\theta) = \frac{1}{N} \sum_ {i=1}^N L(\theta; x_ i, y_ i)\)。当 \(N\) 极大时，精确计算梯度代价高昂。SGD 在每一步随机抽取一个样本（或一小批样本）\(i_ n\)，并用其梯度作为真实梯度的带噪声估计： \[ \theta_ {n+1} = \theta_ n - a_ n \nabla L(\theta_ n; i_ n) \] 这完全符合随机逼近的框架：这里的“噪声”源于用单个样本的梯度去估计全体样本的平均梯度。因此，随机逼近的理论为SGD的收敛性提供了严格的数学保证。 总结 随机逼近提供了一套强大的数学工具，用于在只能获得带噪声反馈的随机环境中进行根查找和优化。从经典的Robbins-Monro算法到现代的大规模机器学习中的SGD，其核心思想都是通过精心设计的递减步长，巧妙地平衡“搜索新区域”和“衰减噪声影响”，从而确保迭代过程能够稳健地收敛到目标解。