6.2-罗宾斯-门罗算法
6.2 罗宾斯-门罗算法(Robbins-Monro)¶
随机近似是指解决寻根(方程求解)或优化问题的一大类随机迭代算法[24]。与许多其他寻根算法如基于梯度的算法(梯度上升或梯度下降)等优化方法中，随机近似具有显著优势：它无需目标函数或其导数的解析表达式。
罗宾斯-门罗(Robbins-Monro，RM)算法是随机近似领域的一项开创性工作 [24-27]。如第\(6.4\)节所示，著名的随机梯度下降算法就是RM算法的一种特殊形式。接下来我们将介绍RM算法的细节。
假设我们想找出方程的根
其中\(w\in\mathbb{R}\)是未知变量，\(g:\mathbb{R} \rightarrow \mathbb{R}\)是一个函数。许多问题都可以表述为寻根问题。例如，如果\(J(w)\)是一个需要优化的目标函数，那么这个优化问题可以转换为求解\(g(w)=\nabla_wJ(w)=0.\)。此外，\(g(w) = c\)(其中\(c\)是一个常数)这样的方程也可以通过将\(g(w)-c\)改写为一个新函数而转换为上述方程。
Note
梯度等于\(0\)是\(J(w)\)达到最大或最小的一个必要条件。
如果已知\(g\)的表达式或其导数，就可以使用许多算法。然而，我们面临的问题是函数\(g\)的表达式可能是未知的。例如，函数可以用人工神经网络来表示，而人工神经网络的结构和参数都是未知的。此外，我们只能获得\(g(w)\)的噪声观测值：
其中\(\eta\in\mathbb{R}\)是观测误差，可能是高斯误差，也可能不是。总之，这是一个黑盒系统，只有输入\(w\)和噪声观测值\(\tilde{g}(w,\eta)\)是已知的(见图\(6.2\))。我们的目标是利用\(w\)和\(\tilde{g}\)求解\(g(w) = 0\)。
图\(6.2\)：由\(w\)和\(\tilde{g}\)求解 \(g(w) = 0\)问题的示意图。
能求解\(g(w) = 0\)的 RM 算法是
其中，\(w_k\)是第\(k\)个根估计值，\(\tilde{g}(w_k, \eta_k)\)是第\(k\)个噪声观测值，\(a_k\)是正系数。可以看出，RM 算法不需要关于函数的任何信息。它只需要输入和输出。
图\(6.3\)：RM 算法示例。
为了说明RM算法，请看一个\(g(w) = w^3 - 5\)的例子。真根为\(5^{1/3} ≈ 1.71\)。现在，假设我们只能观察到输入\(w\)和输出 \(\tilde{g}(w) = g(w) + \eta\)，其中\(\eta\)为\(i.i.d.\)，服从均值为\(0\),标准差为\(1\)的标准正态分布，初始猜测为 \(w_1 = 0\)，系数为\(a_k = 1/k\)。\(w_k\)的变化过程如图\(6.3\)所示。即使观测结果受到噪声\(\eta_k\)的干扰，估计值\(w_k\)仍然可以收敛到真正的根值。需要注意的是，必须正确选择初始猜测\(w_1\)，以确保\(g(w) = w^3 - 5\)这一特定函数的收敛性。在下面的小节中，我们将介绍 RM 算法收敛于任何初始猜测的条件。
6.2.1 收敛特性¶
为什么\((6.5)\)中的 RM 算法可以找到\(g(w) = 0\)的根？接下来我们用一个例子来说明这个想法，然后进行严格的收敛性分析。
请看图\(6.4\)所示的例子。在这个例子中，\(g(w) = tanh(w-1)\)。\(g(w) = 0\)的真根是\(w^∗ = 1\)。我们应用 RM 算法，\(w_1 = 3，a_k = 1/k\)。为了更好地说明收敛的原因，我们只需设置\(\eta_k ≡ 0\)，因此，\(\tilde{g} (w_k, \eta_k) = g(w_k)\)。这种情况下的RM算法为\(w_{k+1} = w_k -a_k g(w_k)\)。由RM算法生成的\({w_k}\)如图\(6.4\)所示。可以看出，\(w_k\)趋近于真正的根\(w^∗ = 1\)。
图\(6.4\)：说明RM算法收敛性的示例。
这个简单的例子可以说明RM算法收敛的原因。
- 当\(w_k>w^*\)时，我们有\(g(w_k)>0\)，此时，\(w_{k+1}=w_k-a_kg(w_k)<w_k\)。如果\(|a_k g(w_k)|\)足够小，我们有\(w^*<w_{k+1}<w_k\)。因此，\(w_{k+1}\)比\(w_k\)更接近于\(w^*\)。
- 当\(w_k<w^*\)时，我们有\(g(w_k)<0\)，此时，\(w_{k+1}=w_k-a_kg(w_k)>w_k\)。如果\(|a_k g(w_k)|\)足够小，我们有\(w^*>w_{k+1}>w_k\)。因此，\(w_{k+1}\)比\(w_k\)更接近于\(w^*\)。
无论哪种情况，\(w_{k+1}\)都比\(w_k\)更接近\(w^∗\)。因此，直观地说，\(w_k\)趋近于 \(w^∗\)。
上面的例子很简单，因为观测误差被假定为零。若存在随机观测误差，其收敛性分析将变得非平凡。下面给出了一个严格的收敛结果。
Info
定理6.1. (罗宾斯-门罗定理)。在\((6.5)\)中的罗宾斯-门罗算法中，如果满足
-
\(0<c_{1}\leq\nabla_{w}g(w)\leq c_{2}\;for\;all\;w\);
-
\(\sum_{k=1}^{\infty}a_{k}=\infty \; and\; \sum_{k=1}^{\infty}a_{k}^{2}<\infty\);
-
\(\mathbb{E}[\eta_{k}|\mathcal{H}_{k}]=0\; and\; \mathbb{E}[\eta_{k}^{2}|\mathcal{H}_{k}]<\infty\);
在这里,\(\mathcal{H}_{k}=\{w_{k},w_{k-1},\ldots\}\),那么\(w_k\)几乎肯定会收敛到满足\(g(w^∗) = 0\)的根 \(w^∗\)。
Note
almost surely收敛。
我们将该定理的证明放到第\(6.3.3\)节。本定理依赖于附录\(B\)中介绍的几乎肯定收敛的概念。
定理\(6.1\)中的三个条件解释如下。
-
在第一个条件中，\(0<c_{1}\leq\nabla_{w}g(w)\)表示\(g(w)\)是一个单调递增函数。这个条件确保了\(g(w) = 0\)的根存在且唯一。如果\(g(w)\)是单调递减函数，我们只需将\(-g(w)\)视为单调递增的新函数即可。
在应用中，我们可以将目标函数为\(J(w)\)的优化问题表述为寻根问题：\(g(w)=\nabla_{w}J(w) = 0\)。在这种情况下，\(g(w)\)单调递增的条件表明 \(J(w)\)是凸的，这是优化问题中通常采用的假设。
不等式\(\nabla_{w}g(w)\leq c_2\)表示\(g(w)\)的梯度有有界。例如，\(g(w) = tanh(w - 1)\)满足这一条件，但\(g(w) = w^3 - 5\)不满足这一条件。
-
关于\(\{a_k\}\)的第二个条件很有趣。我们在强化学习算法中经常看到类似的条件。特别地，条件\(\sum_{k=1}^{\infty} a_k^2 < \infty\)意味着\(\lim_{n \to \infty} \sum_{k=1}^{n} a_k^2\)是有上界的。这要求\(a_k\)随着\(k \to \infty\)收敛于零。条件\(\sum_{k=1}^{\infty} a_k = \infty\)意味着\(\lim_{n \to \infty} \sum_{k=1}^{n} a_k\)是无限大的。它要求\(a_k\)不应该收敛于零得太快。这些条件有着有趣的性质，稍后会详细分析。
-
第三个条件是温和的。它不要求观测误差\(\eta_k\)是高斯分布的。常见的特例是\(\{\eta_k\}\)是一个独立同分布的随机序列，满足\(\mathbb{E}[\eta_k] = 0\)和\(\mathbb{E}[\eta_k^2] < \infty\)。在这种情况下，第三个条件是成立的，因为\(\eta_k\)与\(\mathcal{H}_k\)独立，因此我们有\(\mathbb{E}[\eta_k|\mathcal{H}_k] = \mathbb{E}[\eta_k] = 0\)和\(\mathbb{E}[\eta_k^2|\mathcal{H}_k] = \mathbb{E}[\eta_k^2]\)。
接下来，我们将更仔细地研究关于系数\({ak}\)的第二个条件。
-
为什么第二个条件对RM算法的收敛很重要？
这个问题自然可以在我们稍后对上述定理进行严格证明时找到答案。在此，我们想提供一些具有洞察力的直觉。
首先，\(\sum_{k=1}^{\infty} a_k^2 < \infty\)表示当\(k \to \infty\)，有\(a_k \to 0\)。为什么这个条件重要？假设观测值\(\tilde{g}(w_k, \eta_k)\) 总是有界的。由于
\[w_{k+1} - w_k = -a_k g(w_k, \eta_k),\]如果\(a_k \to 0\)，那么\(a_k \tilde{g}(w_k, \eta_k) \to 0\)，因此\(w_{k+1} - w_k \to 0\)，这表明当\(k \to \infty\)时，\(w_{k+1}\)和\(w_k\)会互相接近。如果\(a_k\)不收敛，则 \(w_k\)可能在\(k \to \infty\)时波动。
其次，\(\sum_{k=1}^{\infty} a_k = \infty\)表示\(a_k\)不应该收敛得太快。为什么这个条件重要？总结方程两边\(w_2-w_1=a_1\tilde{g}(w_1,\eta_1)\),\(w_3-w_2=-a_2\tilde{g}(w_2,\eta_2)\)，\(w_4-w_3=-a_3\tilde{g}(w_3,\eta_3)\)得到
\[w_1 - w_\infty = \sum_{k=1}^{\infty} a_k g(w_k, \eta_k)。\]如果\(\sum_{k=1}^{\infty} a_k < \infty\)，则 \(|\sum_{k=1}^{\infty} a_k g(w_k, \eta_k)|\) 也是有界的。令\(b\)表示一个有限的上界，使得
\[|w_1 - w_\infty| = \left|\sum_{k=1}^{\infty} a_k g(w_k, \eta_k)\right| \leq b.\tag{6.6}\]如果初始猜测\(w_1\)远离真实解\(w^*\)，使得\(|w_1 - w^*| > b\)，则根据式\((6.6)\)，不可能得到\(w_\infty = w^*\)。这表明RM算法在这种情况下无法找到真实解\(w^*\)。因此，条件\(\sum_{k=1}^{\infty} a_k = \infty\)是确保在任意初始猜测条件下收敛的必要条件。
-
哪些序列满足\(\sum_{k=1}^{\infty} a_k = \infty\)和\(\sum_{k=1}^{\infty} a_k^2 < \infty\)？
一个典型的序列是
\[a_k = \frac{1}{k}.\]一方面，有
\[\lim_{n \to \infty} \left( \sum_{k=1}^{n} \frac{1}{k} - \ln n \right) = \kappa,\]其中\(\kappa \approx 0.577\)被称为欧拉-马歇罗尼常数(或欧拉常数)[28]。由于\(\lim_{n \to \infty} \ln n = \infty\)，我们有
\[\sum_{k=1}^{\infty} \frac{1}{k} = \infty.\]事实上，\(H_n = \sum_{k=1}^{n} \frac{1}{k}\)被称为微积分中的调和级数。另一方面，有
\[\sum_{k=1}^{\infty} \frac{1}{k^2} = \frac{\pi^2}{6} < \infty.\]找到\(\sum_{k=1}^{\infty} \frac{1}{k^2}\)的值被称为巴塞尔问题[30]。
总之，序列 \(\{a_k = 1/k\}\) 满足定理\(6.1\)中的第二个条件。值得注意的是，稍微修改一下，例如\(a_k = 1/(k+1)\)或\(a_k = c_k/k\)，其中\(c_k\)是有界的，也能保持这个条件。
在RM算法中，\(a_k\)通常被选作一个足够小的常数，在许多情况下，尽管第二个条件不再被满足，因为\(\sum_{k=1}^{\infty} a_k^2 = \infty\)而不是\(\sum_{k=1}^{\infty} a_k^2 < \infty\)，算法仍然能以某种方式收敛[24,1.5节]。此外，\(g(x) = x^3 - 5\)作为图\(6.3\)中的例子，虽然不满足第二个条件，但RM算法仍然可以找到根（如果初始猜测足够好）。
Note
如果\(a_k=1/k\)，当\(k\)比较大时，后面的数据所起到的作用就非常小了，所以希望未来的数据仍然可以有用，就让\(a_k\)趋近于一个非常小的数而非\(0\)。
6.2.2 在期望值估计问题中的应用¶
接下来，我们运用罗宾斯-门罗定理来分析均值估计问题，该问题已在第\(6.1\)节中讨论过。回顾
这是均值估计算法\((6.4)\)。当\(a_k = 1/k\)时，我们可以得到\(w_{k+1}\)的解析表达式，即\(w_{k+1} = \frac{1}{k} \sum_{i=1}^{k} x_i\)。然而，当给定一般的\(a_k\)时，我们无法获得解析表达式。在当时，这个算法的收敛性无法得到证明。但我们现在可以证明，在这种情况下，该算法是一个特殊的RM算法，因此其收敛性自然跟随。
特别地，定义一个函数为
原始问题是求\(\mathbb{E}[X]\)的值。这个问题被表述为求解\(g(w) = 0\)的根。给定一个\(w\)的值，噪声观测值为\(\tilde{g}(w, \eta) = w - x,\)其中\(x\)是\(X\)的一个样本。注意\(\tilde{g}\)可以写为
其中\(\eta \doteq \mathbb{E}[X] - x\)。
RM算法求解该问题的更新公式为
这正是\((6.4)\)中的算法。因此，根据定理\(6.1\)，它保证\(w_k\)几乎必然收敛于\(\mathbb{E}[X]\)，且\(\sum_{k=1}^{\infty} a_k = \infty\)，\(\sum_{k=1}^{\infty} a_k^2 < \infty\)，并且\(\{x_k\}\)是独立同分布的。值得注意的是，收敛的性质不依赖于\(X\)的分布。