随机变量的变换的Robbins-Monro算法与Kiefer-Wolfowitz算法
字数 3843 2025-12-17 18:55:10

随机变量的变换的Robbins-Monro算法与Kiefer-Wolfowitz算法

我们开始讲解随机优化与统计估计中的一个重要方法——随机逼近。其核心在于通过随机观测数据，逐步逼近一个无法直接计算的目标值（如方程的根、函数的极值点）。我们将聚焦于两个奠基性算法：Robbins-Monro算法和Kiefer-Wolfowitz算法。

第一步：问题背景与核心思想

想象一个实际问题：我们想找到一个参数 \(\theta\)，使得某个函数 \(M(\theta)\) 的值为零，即 \(M(\theta) = 0\)。但 \(M(\theta)\) 的精确形式未知，我们无法直接求解方程。我们唯一能做的，是在任意给定的点 \(\theta\) 处，进行实验或观测，得到一个带有随机噪声的观测值 \(Y(\theta)\)。这个观测值是“有偏的”，其期望值正好是我们想找的函数：\(\mathbb{E}[Y(\theta)] = M(\theta)\)。

  • 例子：在工厂调整某个工艺参数 \(\theta\)（如温度），目标是使产品平均硬度达到某个标准值 \(\alpha\)。我们无法知道“参数-平均硬度”的确切函数 \(M(\theta)\)，但每次设定一个温度 \(\theta_n\)，生产一件产品，测得其硬度 \(Y_n\)。\(\mathbb{E}[Y_n] = M(\theta_n)\)。我们的目标是找到 \(\theta^*\) 使得 \(M(\theta^*) = \alpha\)。这可以转化为求 \(M(\theta) - \alpha = 0\) 的根。

随机逼近的核心思想是：从一个初始猜测 \(\theta_1\) 开始，迭代更新。

  1. 在第 \(n\) 步，我们在当前点 \(\theta_n\) 处进行观测，得到 \(Y_n(\theta_n)\)。
  2. 根据观测结果与目标（是求根还是求极值）的偏差，对参数 \(\theta_n\) 进行一个小的调整，得到 \(\theta_{n+1}\)。
  3. 调整的幅度（称为“步长”）会随着迭代逐步减小，以确保最终收敛。

Robbins-Monro (RM) 算法和 Kiefer-Wolfowitz (KW) 算法是这一思想的具体实现，分别针对“求根”和“求极值”两类问题。

第二步：Robbins-Monro 算法（求解回归方程的根）

  • 精确问题：找到唯一的 \(\theta^*\)，使得 \(M(\theta^*) = 0\)。其中 \(M(\theta) = \mathbb{E}[Y(\theta)]\)。
  • 假设条件：
  1. \(M(\theta)\) 在 \(\theta^*\) 附近是连续的。
  2. 当 \(\theta < \theta^*\) 时，\(M(\theta) < 0\)；当 \(\theta > \theta^*\) 时，\(M(\theta) > 0\)（即 \(M(\theta)\) 是 \(\theta\) 的增函数，且穿越零点）。
  3. 观测噪声的方差有界：\(\mathbb{E}[(Y(\theta) - M(\theta))^2] \leq \sigma^2 < \infty\)。
  • 算法迭代公式：

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

这里 \(Y_n(\theta_n)\) 是在 \(\theta_n\) 处带有噪声的观测值（即对 \(M(\theta_n)\) 的估计）。

  • 关键部件——步长序列 \(\{a_n\}\)：
    步长 \(a_n\) 必须是正数，且满足两个经典条件以确保收敛：

\[ \sum_{n=1}^{\infty} a_n = \infty \quad \text{和} \quad \sum_{n=1}^{\infty} a_n^2 < \infty \]

  • \(\sum a_n = \infty\)：保证算法有足够的“能量”走遍整个参数空间，最终到达 \(\theta^*\)，无论起点多远。
  • \(\sum a_n^2 < \infty\)：保证随机噪声的累积方差是有限的，从而噪声的影响能被逐步抑制，算法最终稳定下来。
    常用的选择是 \(a_n = c / n\)，其中 \(c > 0\) 是一个常数。
  • 直观理解：观测值 \(Y_n\) 可以看作是对 \(M(\theta_n)\) 的一个有噪声估计。如果 \(M(\theta_n) > 0\)，我们希望减小 \(\theta\) 以接近零点，所以用负的步长（\(-a_n Y_n\)）。反之亦然。迭代过程是一个带噪声的“梯度下降”（这里梯度方向由 \(Y_n\) 的符号引导），步长逐渐减小，使得更新越来越精细。

第三步：Kiefer-Wolfowitz 算法（求解回归函数的极值点）

  • 精确问题：找到函数 \(L(\theta) = \mathbb{E}[Z(\theta)]\) 的极小值点（或极大值点）。我们无法直接计算 \(L(\theta)\) 或其导数，只能观测到带有噪声的函数值 \(Z(\theta)\)。
  • 核心技巧——有限差分估计梯度：
    因为我们无法直接观测梯度 \(L'(\theta)\)，KW算法用一个对称的有限差分来近似：

\[ \text{梯度估计} \approx \frac{Z(\theta + c_n) - Z(\theta - c_n)}{2c_n} \]

这里 \(c_n > 0\) 是另一个趋于0的序列，称为“差分间隔”。

  • 算法迭代公式（一维情况）：

\[ \theta_{n+1} = \theta_n - a_n \left( \frac{Z_n^+ - Z_n^-}{2c_n} \right) \]

其中 \(Z_n^+\) 是在 \(\theta_n + c_n\) 处的观测值，\(Z_n^-\) 是在 \(\theta_n - c_n\) 处的观测值。两者独立或条件不相关。

  • 关键序列的选择：
    除了步长序列 \(\{a_n\}\) 需要满足与RM算法相同的两个条件外，差分间隔序列 \(\{c_n\}\) 也需要满足：

\[ c_n \rightarrow 0, \quad \sum_{n=1}^{\infty} a_n c_n < \infty, \quad \text{且} \quad \sum_{n=1}^{\infty} (a_n / c_n)^2 < \infty \]

常见的选择是 \(a_n = c / n\)， \(c_n = d / n^{\gamma}\)，其中 \(0 < \gamma < 1/2\)。例如 \(a_n = 1/n\)， \(c_n = 1/n^{1/3}\)。

  • \(c_n \rightarrow 0\)：确保梯度估计是渐近无偏的（当 \(n\) 很大时，差分近似导数更精确）。
    • 另外两个条件是为了控制由有限差分近似和观测噪声共同引入的误差方差。
  • 直观理解：算法用两个观测点的函数值之差除以距离，来近似当前位置的梯度方向。然后沿着这个近似梯度的反方向（因为是求极小）更新参数。它本质上是一个随机梯度下降的雏形，只不过梯度是通过函数值差分估计的。

第四步：算法的收敛性与联系

  • 收敛性：在适当的假设下（包括之前提到的单调性、噪声条件、步长与差分间隔条件），可以证明两个算法都能以概率1收敛到目标点 \(\theta^*\)，即 \(\theta_n \overset{a.s.}{\longrightarrow} \theta^*\)。
  • 渐近分布：更进一步，可以证明归一化的估计误差 \(\sqrt{n} (\theta_n - \theta^*)\) 服从一个正态分布（渐近正态性）。对于RM算法，其渐近方差与 \(a_n\) 的选择以及噪声方差有关。对于KW算法，其渐近方差不仅取决于噪声，还受限于 \(c_n\) 的选择，通常比RM算法的方差大，因为引入了额外的近似误差。
  • 联系与拓展：
  1. RM算法可以看作是寻找梯度为零的点，所以和KW算法在优化问题上是相通的。现代随机梯度下降 (SGD) 可以被视为RM算法的一个特例或推广，其中 \(Y_n\) 直接是目标函数在随机样本上的梯度估计，而不是通过有限差分获得。
    2. KW算法是多变量优化的基础。在多维情况下，需要对每个分量分别进行对称差分来估计梯度向量。
    3. 这两个算法奠定了随机优化和在线学习的理论基础。在许多机器学习和大规模统计问题中，目标函数定义为大量数据上的期望，直接计算精确梯度代价高昂，通过随机采样（或观测）来估计梯度并迭代更新，正是RM/KW思想的核心。

总结来说，Robbins-Monro和Kiefer-Wolfowitz算法提供了一套强大的、基于数据的迭代框架，用于在仅能获得带噪声的函数值或梯度观测的情况下，求解方程的根或函数的极值点。它们将确定性的迭代求解过程与随机噪声的统计性质相结合，其步长衰减的设计是确保收敛的关键，并对后续的随机优化算法产生了深远影响。

随机变量的变换的Robbins-Monro算法与Kiefer-Wolfowitz算法 我们开始讲解随机优化与统计估计中的一个重要方法——随机逼近。其核心在于通过随机观测数据，逐步逼近一个无法直接计算的目标值（如方程的根、函数的极值点）。我们将聚焦于两个奠基性算法：Robbins-Monro算法和Kiefer-Wolfowitz算法。 第一步：问题背景与核心思想 想象一个实际问题：我们想找到一个参数 \(\theta\)，使得某个函数 \(M(\theta)\) 的值为零，即 \(M(\theta) = 0\)。但 \(M(\theta)\) 的精确形式未知，我们无法直接求解方程。我们唯一能做的，是在任意给定的点 \(\theta\) 处，进行实验或观测，得到一个带有随机噪声的观测值 \(Y(\theta)\)。这个观测值是“有偏的”，其期望值正好是我们想找的函数：\(\mathbb{E}[ Y(\theta) ] = M(\theta)\)。 例子 ：在工厂调整某个工艺参数 \(\theta\)（如温度），目标是使产品平均硬度达到某个标准值 \(\alpha\)。我们无法知道“参数-平均硬度”的确切函数 \(M(\theta)\)，但每次设定一个温度 \(\theta_ n\)，生产一件产品，测得其硬度 \(Y_ n\)。\(\mathbb{E}[ Y_ n] = M(\theta_ n)\)。我们的目标是找到 \(\theta^ \) 使得 \(M(\theta^ ) = \alpha\)。这可以转化为求 \(M(\theta) - \alpha = 0\) 的根。 随机逼近的核心思想是：从一个初始猜测 \(\theta_ 1\) 开始，迭代更新。 在第 \(n\) 步，我们在当前点 \(\theta_ n\) 处进行观测，得到 \(Y_ n(\theta_ n)\)。 根据观测结果与目标（是求根还是求极值）的偏差，对参数 \(\theta_ n\) 进行一个小的调整，得到 \(\theta_ {n+1}\)。 调整的幅度（称为“步长”）会随着迭代逐步减小，以确保最终收敛。 Robbins-Monro (RM) 算法和 Kiefer-Wolfowitz (KW) 算法是这一思想的具体实现，分别针对“求根”和“求极值”两类问题。 第二步：Robbins-Monro 算法（求解回归方程的根） 精确问题 ：找到唯一的 \(\theta^ \)，使得 \(M(\theta^ ) = 0\)。其中 \(M(\theta) = \mathbb{E}[ Y(\theta) ]\)。 假设条件 ： \(M(\theta)\) 在 \(\theta^* \) 附近是连续的。 当 \(\theta < \theta^ \) 时，\(M(\theta) < 0\)；当 \(\theta > \theta^ \) 时，\(M(\theta) > 0\)（即 \(M(\theta)\) 是 \(\theta\) 的增函数，且穿越零点）。 观测噪声的方差有界：\(\mathbb{E}[ (Y(\theta) - M(\theta))^2] \leq \sigma^2 < \infty\)。 算法迭代公式 ： \[ \theta_ {n+1} = \theta_ n - a_ n Y_ n(\theta_ n) \] 这里 \(Y_ n(\theta_ n)\) 是在 \(\theta_ n\) 处带有噪声的观测值（即对 \(M(\theta_ n)\) 的估计）。 关键部件——步长序列 \(\{a_ n\}\) ： 步长 \(a_ n\) 必须是正数，且满足两个经典条件以确保收敛： \[ \sum_ {n=1}^{\infty} a_ n = \infty \quad \text{和} \quad \sum_ {n=1}^{\infty} a_ n^2 < \infty \] \(\sum a_ n = \infty\)：保证算法有足够的“能量”走遍整个参数空间，最终到达 \(\theta^* \)，无论起点多远。 \(\sum a_ n^2 < \infty\)：保证随机噪声的累积方差是有限的，从而噪声的影响能被逐步抑制，算法最终稳定下来。 常用的选择是 \(a_ n = c / n\)，其中 \(c > 0\) 是一个常数。 直观理解 ：观测值 \(Y_ n\) 可以看作是对 \(M(\theta_ n)\) 的一个有噪声估计。如果 \(M(\theta_ n) > 0\)，我们希望减小 \(\theta\) 以接近零点，所以用负的步长（\(-a_ n Y_ n\)）。反之亦然。迭代过程是一个带噪声的“梯度下降”（这里梯度方向由 \(Y_ n\) 的符号引导），步长逐渐减小，使得更新越来越精细。 第三步：Kiefer-Wolfowitz 算法（求解回归函数的极值点） 精确问题 ：找到函数 \(L(\theta) = \mathbb{E}[ Z(\theta) ]\) 的极小值点（或极大值点）。我们无法直接计算 \(L(\theta)\) 或其导数，只能观测到带有噪声的函数值 \(Z(\theta)\)。 核心技巧——有限差分估计梯度 ： 因为我们无法直接观测梯度 \(L'(\theta)\)，KW算法用一个对称的有限差分来近似： \[ \text{梯度估计} \approx \frac{Z(\theta + c_ n) - Z(\theta - c_ n)}{2c_ n} \] 这里 \(c_ n > 0\) 是另一个趋于0的序列，称为“差分间隔”。 算法迭代公式（一维情况） ： \[ \theta_ {n+1} = \theta_ n - a_ n \left( \frac{Z_ n^+ - Z_ n^-}{2c_ n} \right) \] 其中 \(Z_ n^+\) 是在 \(\theta_ n + c_ n\) 处的观测值，\(Z_ n^-\) 是在 \(\theta_ n - c_ n\) 处的观测值。两者独立或条件不相关。 关键序列的选择 ： 除了步长序列 \(\{a_ n\}\) 需要满足与RM算法相同的两个条件外，差分间隔序列 \(\{c_ n\}\) 也需要满足： \[ c_ n \rightarrow 0, \quad \sum_ {n=1}^{\infty} a_ n c_ n < \infty, \quad \text{且} \quad \sum_ {n=1}^{\infty} (a_ n / c_ n)^2 < \infty \] 常见的选择是 \(a_ n = c / n\)， \(c_ n = d / n^{\gamma}\)，其中 \(0 < \gamma < 1/2\)。例如 \(a_ n = 1/n\)， \(c_ n = 1/n^{1/3}\)。 \(c_ n \rightarrow 0\)：确保梯度估计是渐近无偏的（当 \(n\) 很大时，差分近似导数更精确）。 另外两个条件是为了控制由有限差分近似和观测噪声共同引入的误差方差。 直观理解 ：算法用两个观测点的函数值之差除以距离，来近似当前位置的梯度方向。然后沿着这个近似梯度的反方向（因为是求极小）更新参数。它本质上是一个 随机梯度下降 的雏形，只不过梯度是通过函数值差分估计的。 第四步：算法的收敛性与联系 收敛性 ：在适当的假设下（包括之前提到的单调性、噪声条件、步长与差分间隔条件），可以证明两个算法都能以概率1收敛到目标点 \(\theta^ \)，即 \(\theta_ n \overset{a.s.}{\longrightarrow} \theta^ \)。 渐近分布 ：更进一步，可以证明归一化的估计误差 \(\sqrt{n} (\theta_ n - \theta^* )\) 服从一个正态分布（渐近正态性）。对于RM算法，其渐近方差与 \(a_ n\) 的选择以及噪声方差有关。对于KW算法，其渐近方差不仅取决于噪声，还受限于 \(c_ n\) 的选择，通常比RM算法的方差大，因为引入了额外的近似误差。 联系与拓展 ： RM算法可以看作是寻找梯度为零的点，所以和KW算法在优化问题上是相通的。现代 随机梯度下降 (SGD) 可以被视为RM算法的一个特例或推广，其中 \(Y_ n\) 直接是目标函数在随机样本上的梯度估计，而不是通过有限差分获得。 KW算法是多变量优化的基础。在多维情况下，需要对每个分量分别进行对称差分来估计梯度向量。 这两个算法奠定了 随机优化 和 在线学习 的理论基础。在许多机器学习和大规模统计问题中，目标函数定义为大量数据上的期望，直接计算精确梯度代价高昂，通过随机采样（或观测）来估计梯度并迭代更新，正是RM/KW思想的核心。 总结来说，Robbins-Monro和Kiefer-Wolfowitz算法提供了一套强大的、基于数据的迭代框架，用于在仅能获得带噪声的函数值或梯度观测的情况下，求解方程的根或函数的极值点。它们将确定性的迭代求解过程与随机噪声的统计性质相结合，其步长衰减的设计是确保收敛的关键，并对后续的随机优化算法产生了深远影响。