时间戳

首页 > 解决方案 > 从离散概率分布算法中采样

algorithm - 从离散概率分布算法中采样

问题描述

我正在解决 Sedgewick 书中的一项任务：

编写一个带有构造函数的类 Sample ，该构造函数将双精度值的数组 p[] 作为参数并支持以下两个操作： random() — 返回一个索引 i，概率为 p[i]/T（其中 T 是总和p[] 中的数字）

我认为有一个简单的解决方案：将所有边界值存储在数组中并找到低于随机样本的第一个值，例如，我们有 (value, weight) 对：(1, 10.0), (2, 20.0), (3, 10.0), (4, 10.0)。我们将其转换为(1, 0.0), (2, 10.0), (3, 30.0), (4, 40)，采样随机值[0-50]（例如35），发现>30，所以答案是'3'。

但是书中有一个建议：

使用一个完整的二叉树，其中每个节点都有隐含的权重 p[i]。在每个节点中存储其子树中所有节点的累积权重。要生成随机索引，请在 0 和 T 之间选择一个随机数，并使用累积权重来确定要探索的子树的哪个分支。

我在 github 上看到了这个解决方案：https ://github.com/reneargento/algorithms-sedgewick-wayne/blob/master/src/chapter2/section4/Exercise35_Sampling.java

但我不明白它为什么起作用：我们将有一些树，而不是表示范围，它们将具有像 (3, 10), (4, 10) 这样的节点，如何搜索与随机样本“最近”的节点将有助于找到一个正确的节点？

标签： algorithm

解决方案

你的想法是在正确的轨道上，但并不完全在那里。你想做逆变换采样。您正在考虑的逐步函数是给定离散分布的逆累积密度函数 (cdf)。更传统的做法是在区间 [0..1) 上使用 X 轴上的搜索值来编写它。1、2、3 和 4 的权重分别为 1/5、2/5、1/5、1/5。您希望将区间分割成这种大小的片段，并将这些区间映射到它们各自的值：

[0   .. 1/5) ->  1   // Note interval widths are 1/5,2/5,1/5,1/5 as desired.
[1/5 .. 3/5) ->  2
[3/5 .. 4/5) ->  3
[4/5 ..   1) ->  4

正如您所说，将间隔的顶部及其值存储在数组中就足够了。在 C 中，

struct IntervalTop {
  double r;
  int value;
} cdf[] = {{.2, 1}, {.6, 2}, {.8, 3}, {1.0, 4}};

现在在 [0..1) 中生成一个随机值并查找相应的子区间以确定该值。例如，0.1 在第一个区间，所以返回 1。0.7 在第三个区间，所以返回 3。对于初学者来说，简单的线性搜索可以正常工作：

double r = ... // Compute random double 0.0 <= r < 1.0 .
for (int i = 0; ; ++i)
  if (cdf[i].r > r) 
     return cdf[i].value;

但是这样一来，搜索时间就会随着间隔的数量而增加。

提高性能的一个简单方法是用二分搜索替换循环。然后搜索时间随着间隔数的对数增长。

但塞奇威克希望你更努力地工作，大概是为了学习。

他的提议也有运行时间 O(log(n))，但它更复杂。他说使用完整的二叉搜索树。每个节点包含值、权重 (w) 以及以该节点为根的子树中所有权重 (t) 的总和。所以对于这个问题，...

                  ____3(w=1/5,t=1)____
                 /                     \
        2(w=2/5,t=3/5)           4 (w=1/5,t=1/5)
        /
1(w=1/5,t=1/5)

实际上，您不需要算法的权重（这就是 S 说它们是“隐式”的原因），但是将它们包括在这里可以更容易地看到正在发生的事情。

如上所述，您将在 [0..1) 中生成一个随机数 r，但在这里您将使用 r 的值作为指导来搜索树。

您将通过查看 tree.t、tree.left.t 和 tree.right.t（丢失的孩子相当于 .t 值为零）并使用这些值做出与二进制相同的决定来做到这一点搜索会在上面。

我会在这里停下来，这样你的乐趣就不会被破坏。

推荐阅读