直接采样算法

14.5.1 直接采样算法

任何采样算法中最基本的要素是根据已知概率分布生成样本。例如，一个无偏差硬币可以被认为是一个随机变量Coin，其可能取值为heads, tails（分别表示硬币正面或者背面朝上——译者注），先验概率是P(Coin) = 0.5, 0.5。根据这个分布进行采样的过程其实就跟抛硬币一模一样：它以概率0.5返回heads，以概率0.5返回tails。给定了一个[0, 1]区间上的随机数发生器，要对任何单变量的分布进行采样都是一件非常简单的事情（参见习题14.9）。

对于贝叶斯网络而言，最简单种类的随机采样过程是对没有与之关联的证据的网络事件进行采样。其思想是按照拓扑次序依次对每个变量进行采样。被采样变量值的概率分布依赖于父节点已得到的赋值。算法如图 14.12 所示。我们可以把其在图 14.11（a）中的网络上的操作过程表示出来，假设次序为[Cloudy, Sprinkler, Rain, WetGrass]：

（1）根据P(Cloudy) = 0.5, 0.5 对Cloudy进行采样，假设返回true。

（2）根据P(Sprinkler|Cloudy = true) = 0.1, 0.9 对Sprinkler进行采样，假设返回false。

（3）根据P(Rain|Cloudy = true) = 0.8, 0.2 对Rain进行采样，假设返回true。

（4）根据P(WetGrass|Sprinkler = false, Rain = true) = 0.9, 0.1 对WetGrass进行采样，假设返回true。

这样，PRIOR-SAMPLE返回事件[true,false,true,true]。

很容易证明PRIOR-SAMPLE生成的样本服从网络所指定的先验联合概率分布。首先，令SPS(x1,…,xn)为由PRIOR-SAMPLE生成的特定事件的概率。只要观察采样过程，我们就会得到：

因为每个采样步骤都只依赖于父节点的取值。这个表达式看起来眼熟，因为它也就是按照贝叶斯网络对联合概率分布的表示而得到的该事件的概率，如公式（14.1）所述。因此我们有

SPS(x1, …, xn) = P(x1, …, xn)

这个简单事实使我们可以利用采样非常容易地回答问题。

图14.12 根据贝叶斯网络生成事件的一个采样算法

在任何采样方法中，都是通过对实际生成的样本进行计数来计算答案的。假设总共有N个样本，令N (x1, …, xn)为特定事件x1, …, xn发生的频率。我们期望这个频率在极限情况下能够收敛到根据采样概率得到的它的期望值：

例如，考虑前面生成的事件[true, false, true, true]，这个事件的采样概率应该是：

SPS(true,false,true,true)=0.5×0.9×0.8×0.9=0.324

因此，在N的大量样本极限下（N趋近于无穷大），我们期望有32.4％的样本是这个事件。

在后文中，只要我们使用约等于符号（“≈”），我们要表达的就是这个含义——也就是说，估计概率在大量样本极限下成为精确值。这样的估计被称为一致的（consistent）。例如，可以为不完全指定事件x1, …, xm的概率产生一个一致估计，其中m ≤ n，如下所示：

也就是说，可以用采样过程中生成的、能与不完全指定事件相匹配的完整事件所占的比例来估计该事件的概率。例如，假设我们从草坪喷灌网络生成了1000个样本，其中511个样本满足Rain=true，那么下雨的估计概率，记作(Rain=true)，就等于0.511。

一、贝叶斯网络中的拒绝采样算法

拒绝采样算法（rejection sampling）是一类由一个易于采样的分布出发，为一个难以直接采样的分布产生采样样本的通用算法。在其最简单的形式中，它可以被用于计算条件概率——也就是，确定P(X|e)。拒绝采样算法REJECTION-SAMPLING如图14.13所示。首先，它根据网络指定的先验概率分布生成采样样本。然后，它拒绝所有与证据不匹配的样本。最后通过在剩余样本中对事件X = x的出现频繁程度计数从而得到估计概率(X=x|e)。

图14.13 贝叶斯网络中回答给定证据下的查询的拒绝采样算法

令(X|e)为算法返回的估计概率分布。根据算法的定义我们得到

根据公式（14.5），它相当于

也就是说，拒绝采样产生了真实概率的一致估计。

继续图14.11（a）中的例子，假设我们希望通过100个样本来估计P(Rain|Sprinkler=true)。在我们所生成的这100个采样样本中，假设有73个样本满足Sprinkler=false，因此被拒绝，同时有27个满足Sprinkler=true；其中8个满足Rain=true，19个满足Rain=false。因此，

P(Rain|Sprinkler=true)≈ NORMALIZE(8,19)=0.296,0.704。

真实的答案是0.3, 0.7。当收集到更多的样本时，估计值应该收敛到真实概率。在每个概率的估计中，估计误差的标准差正比于1/，其中n是在估计中所用到的采样样本数。

拒绝采样算法存在的最大问题是，它拒绝了太多的样本！随着证据变量个数的增多，与证据 e 相一致的样本在所有样本中所占的比例呈指数级下降，所以对于复杂问题这种方法是完全不可用的。

注意拒绝采样方法与直接根据现实世界对条件概率进行估计的过程非常相似。例如，要估计 P(Rain|RedSkyAtNight = true)（晚上出现红色天空时，第二天下雨的概率分布——译者注），我们可以简单地对前一天晚上观察到红色天空后下雨的频度计数——而忽略天空不红的那些夜晚。（这里，真实世界本身扮演了采样生成算法的角色）。显然，如果天空很少发红，这个过程可能要花很长时间，而这就是拒绝采样方法的弱点。

二、似然加权

似然加权（likelihood weighting）只生成与证据e一致的事件，从而避免拒绝采样算法的低效率。我们从描述算法的工作机理开始，然后说明其工作的正确性——也就是，产生一致估计概率。

LIKELIHOOD-WEIGHTING（参见图 14.14）算法固定证据变量 E 的值，只对证据以外的其余变量 X和Y进行采样。这保证了生成的每个采样样本都与证据一致。然而，并非所有的事件的地位都相等。在对查询变量的分布进行计数之前，把根据证据得到的事件的似然作为每个事件的权值，这个权值通过每个证据变量在给定其父节点取值下的条件概率的乘积进行度量。直观地看，其中不太可能出现证据的事件应该给予较低的权值。

图14.14 用于贝叶斯网络推理的似然加权算法

现在我们将算法应用于图14.11（a）中所示的网络，求解查询P(Rain|Sprinkler=true,WetGrass=true)。过程是这样的：首先，将权值w设为1.0。然后生成一个事件：

（1）对P(Cloudy) = 0.5, 0.5 进行采样；假设返回true。

（2）Sprinkler是证据变量，其取值为true。因此我们设置

w ← w × P(Sprinkler = true|Cloudy = true) = 0.1

（3）对P(Rain|Cloudy = true) = 0.8, 0.2 进行采样；假设返回true。

（4）WetGrass是证据变量，其取值为true。因此我们设置

w←w × P(WetGrass=true|Sprinkler=true)=0.099。

这里WEIGHTED-SAMPLE返回权值为0.099的事件[true,true,true,true]，它将被计入Rain=true中去。这个事件的权值很低，因为它所描述的是多云的天气，而在这样一种天气下是不太可能使用喷灌装置的。

为了理解为什么似然加权可行，我们从检查WEIGHTED-SAMPLE的采样分布SWS开始。记住证据变量E的值固定为e。我们将把证据以外的其它变量记作Z，即Z = {X} ∪ Y。给定其父节点的值后，算法对Z中的每一个变量进行采样：

注意到Parents(Zi)可能同时包含隐变量和证据变量。和先验分布P(z)不同的是，分布SWS给予证据某种特别的关注：每个Zi的采样值会受到Zi祖先节点中的证据的影响。另一方面，SWS对证据的考虑要少于对真实的后验概率P(z|e) 的考虑，因为每个Zi的采样值都忽略了Zi非祖先节点中的证据变量。[16]

似然权值w补偿了真实采样分布与期望采样分布之间的差距。对一个由z和e组成的给定样本x而言，它的权值等于每个证据变量在给定其父节点条件下（部分或者全部包含在Zi中）的似然的乘积：

将公式（14.6）和公式（14.7）相乘，我们发现一个样本的加权概率具有特别方便的形式：

因为这两个乘积覆盖了网络中的所有节点，允许我们使用公式（14.1）计算联合概率分布。

现在要证明似然加权估计的一致性就非常容易了。对于X的任一特定取值x，其估计后验概率可以计算如下：

因此，似然加权返回一致估计。

由于在似然加权中使用了产生的所有样本，它的效率比拒绝采样算法要高很多。然而，当证据变量的个数增加时它仍然要承受大幅度的性能下降。因为大多数的样本权值都非常低，导致在加权估计中起主导作用的只是那些所占比例很小的、与证据相符合的似然程度不是非常小的样本。当证据变量出现在变量次序中比较靠后的位置时这个问题尤其严重，因为在这种情况下采样样本将是与证据所暗示的现实之间相似度很小的一种模拟。