关于修复随机性的更多内容

总结

让我们回顾一下最近几节课的内容：

假设我们有一个 doubles 的分布 p，以及一个从 double 映射到 double 的函数 f。我们经常需要回答的问题是：“当 f 接收来自分布 p 的样本时，其平均值是多少？”这个量被称为期望值。

最直接（或称“朴素”）的方法是：抽取大量样本，对这些样本应用函数 f，然后取平均值。这很简单！然而，如果存在“黑天鹅”事件——即那些很少被采样但一旦出现就会极大影响平均值的值——这种方法可能会出现问题。我们希望在不大幅增加样本数量的情况下，获得一个可靠的估计。

估算期望值的技术

我们发展了两种估算期望值的方法：

放弃采样，改用数值积分计算

• 使用数值积分方法计算两个面积：f(x) * p.Weight(x) 下的面积，以及 p.Weight(x) 下的面积（即分布 p 的归一化常数）。
• 两者的比值是对期望值的一个极其精确的估计。
• 但我们需要知道进行积分的区域范围。

使用重要性采样（Importance Sampling）

• 找到一个辅助分布 q，其权重在 f(x) * p.Weight(x) 值较大的区域也较大。
• 使用朴素算法来估算 x => f(x)*p.Weight(x)/q.Weight(x) 在 q 分布样本上的期望值。
• 这个结果与 f 关于分布 p 的期望值成正比。
• 我们还提供了一种通过从 q 中采样来估计比例常数的技术。

重要性采样的问题

重要性采样的主要问题是：如何找到一个好的辅助分布 q。我们讨论了一些技术：

• 如果你知道取值范围，可以使用该范围上的均匀分布。
• 对 p 进行拉伸和偏移，使得变换后的概率密度函数不再有“黑天鹅”，同时保持归一化常数不变。
• 使用梅特罗波利斯算法从 Abs(f * p) 构建一个辅助概率密度函数，但在实验中效果不佳。
• 如果我们知道感兴趣的区域，可以使用 VEGAS 算法。它先对子区域进行廉价、粗略的面积估计，再利用这些信息逐步优化一个分段均匀的辅助分布，使其聚焦于峰值区域，避开平坦区域。
• 然而，VEGAS 算法较为复杂，本课程未尝试实现。

思考题

你可能在最近几节课中一直在问自己：

如果数值积分是一种准确且高效的方式来估算 f 在分布 p 样本上的期望值，那为什么我们还要考虑采样呢？通常我们至少大致知道 f * p 有显著面积的范围，这样做有什么意义？

一个简单的数值积分算法只是将区间划分为若干等份（比如一千份），在每一点上计算 f * p，然后求平均。这看起来比采样要便宜又简单得多。难道我们这几节课都在浪费你的时间吗？为什么学术界投入如此多的研究精力去寻找估算期望值的技术？

本课程的核心目标是“修复随机”——因为 C# 内置的基础类库在表示概率方面功能较弱。我们始终从这样的视角出发：“我们希望在业务领域中拥有一个表示概率的对象，并用它来解决实际问题。”

“给定一个分布，函数 f 的期望值是多少？”这个问题在涉及概率的业务问题中非常自然。正如我们所见，可以通过数值积分模拟来回答这个问题。

但正如我们反复强调的：相等的事物彼此相等。反过来思考：假设我们的业务领域涉及解积分问题，而某个积分问题无法用数值积分高效求解，该怎么办？

• 我们可以用数值积分技术解决期望值问题。
• 我们也可以用采样技术解决期望值问题。
• 相等的事物彼此相等。
• 因此，我们可以用采样技术来解决积分问题。

这就是为何人们投入大量研究去探索期望值估算的原因：期望值就是函数 f(x) * p.Weight(x) 下的面积。如果我们能通过采样计算出这个期望值，那么我们就能在不使用数值积分的情况下，估算出该面积并解决积分问题！

我们之前提到“如果数值积分准确且廉价”，但现实中有很多场景下数值积分并不经济（尽管存在更复杂的高效算法，但本课程不予讨论）。

举个例子：现在我们把 f 从 Func<double, double> 推广为 Func<double, double, double>——即从二维点映射到实数的函数。换句话说，f 不再是一条曲线，而是一个三维空间中的曲面。

假设我们有一个这样的函数 f，希望求它在区域 $(0,0)$ 到 $(1,1)$ 上的体积。

我们可以用数值积分，但记住：在之前的例子中，我们将 0 到 1 的区间划分为一千个点。若在二维情况下以相同的精度 $0.001$ 进行积分，就需要评估一百万个点并求和。如果我们只能负担一千次计算，那么精度只能达到约 $0.03$。

如果函数在大多数点上都接近零，那么由于精度太低，我们对总面积的估计会非常糟糕。

现在我们换一种思路：采用一个二维概率分布。例如，使用标准连续均匀分布 IWeightedDistribution<(double, double)>。

我们在本课程中探讨的所有技术，在二维情况下同样适用！于是我们可以这样操作：

• 估算 f 在该分布样本上的平均值。
• 它等于 f(x,y) * p.Weight((x,y)) 下的体积。
• 但在我们关心的区域内，p.Weight((x,y)) 始终为 $1.0$，因为这是标准连续均匀分布。
• 因此，f 在分布 p 样本上的估计期望值，就是我们关心的体积的估计值。

这有什么帮助？

起初看似乎没有帮助。

无论是用数值积分取一千个点，还是从相同范围的均匀分布中采样一千个点，我们都是在计算一千个点的函数值并求平均。结果一样。

但这里有个关键技巧。

假设我们能找到一个辅助分布 q，它在 f(x,y) 体积较大的区域权重高，而在体积小的区域权重极低。

这时我们就可以使用重要性采样，得到更精确的期望值估计，从而更准确地估计所需体积——因为我们从 q 中采样的上千个点大多落在高体积区域。这将带来更好的估计！

现在进一步提高维度。假设我们有一个函数，输入三个 double，输出一个 double，希望求它在 $(0,0,0)$ 到 $(1,1,1)$ 区域内的超体积。

用数值积分的话，要么做十亿次计算（精度 $0.001$），要么只能做一千次，此时精度退化到 $0.1$。

每增加一个维度，数值积分的成本就可能上升千倍，或者成本不变但精度急剧下降，或者我们必须放弃简单算法，改用更智能的算法专门聚焦于高值区域。

而且情况还在恶化。

当你在四维空间中计算一个三维曲面的超体积时，函数为零的点会更多！高维空间中“空旷”的地方实在太多了。维度越高，越需要精准定位峰值区域，避免在平坦区域浪费计算资源。

练习：考虑一个边长为 $1$ 的 $n$ 维立方体。无论 $n$ 是多少，它的超体积始终为 $1$。

现在考虑一个内接的 $n$ 维立方体，边长为 $0.9$。

• 一维时（线段）：内线段占外线段的 $90\%$，因此外线段有 $10\%$ 的长度“靠近表面”。
• 二维时（正方形）：内正方形面积占外正方形的 $81\%$，因此外正方形有 $19\%$ 的面积“靠近表面”。

当维度达到多少时，外立方体的超体积中超过 $50\%$ 的部分“靠近表面”？

练习：再次考虑边长为 $1$ 的 $n$ 维立方体，以及其内切的 $n$ 维球体（圆内切于正方形，球内切于立方体，依此类推）。半径为 $\frac{1}{2}$。

• 圆面积是正方形面积的 $\frac{\pi}{4} \approx 79\%$。
• 球体积是立方体体积的 $\frac{\pi}{6} \approx 52\%$。
• 以此类推。

当 $n$ 取何值时，超球体的体积变为超立方体体积的 $1\%$？

在高维空间中，任何位于超立方体内部的形状，与靠近其表面的巨大超体积相比，都微不足道！

这意味着：如果你试图计算一个函数在超立方体内某处具有大值的区域的超体积，那么采样必须频繁命中这些高值区域。如果大部分时间都花在“边缘附近”这些值较小的地方，那么超过 $90\%$ 的采样都毫无意义。

这正是重要性采样如此有用的原因，也是我们投入大量精力研究如何寻找合适分布的原因。重要性采样使我们能够用合理的计算资源，数值求解多维积分问题。

现在你应该明白，我们之前说“VEGAS 算法是为了寻找重要性采样中的好辅助分布”其实是一种误导。VEGAS 确实能完成这项任务，但这不是它的设计初衷；它原本是为了解决多维积分问题。寻找好的辅助分布，只是它实现这一目标的方式。

练习：也许你能看出如何将我们在单个 double 分布上实现的算法扩展到 tuple of doubles 的分布上；本课程不会这么做，你可以自行尝试看看进展如何！

---

关于这个主题还有太多可讲的内容；有人毕生致力于此。但我们将在接下来的课程中总结全部工作，给出最终思考、已完成内容的回顾、一些本课程未涵盖的相关主题列表，以及我们学习过程中参考的部分文献和资料清单。