1700537600
百面机器学习：算法工程师带你去面试 [:1700532217]
1700537601
百面机器学习：算法工程师带你去面试 06 贝叶斯网络的采样
1700537602
1700537603
1700537604
1700537605
场景描述
1700537606
1700537607
概率图模型经常被用来描述多个随机变量的联合概率分布。贝叶斯网络，又称信念网络或有向无环图模型。它是一种概率图模型，利用有向无环图来刻画一组随机变量之间的条件概率分布关系。图8.9是贝叶斯网络的一个经典例子，用来刻画Cloudy、Sprinkler、Rain、WetGrass等变量之间的条件分布关系。
1700537608
1700537609
1700537610
1700537611
1700537612
图8.9 贝叶斯网络
1700537613
1700537614
知识点
1700537615
1700537616
概率图模型，条件概率，采样
1700537617
1700537618
问题 如何对贝叶斯网络进行采样？如果只需要考虑一部分变量的边缘分布，如何采样？如果网络中含有观测变量，又该如何采样？
1700537619
1700537620
难度：★★★☆☆
1700537621
1700537622
分析与解答
1700537623
1700537624
对一个没有观测变量的贝叶斯网络进行采样，最简单的方法是祖先采样（Ancestral Sampling），它的核心思想是根据有向图的顺序，先对祖先节点进行采样，只有当某个节点的所有父节点都已完成采样，才对该节点进行采样。以场景描述中的图8.9为例，先对Cloudy变量进行采样，然后再对Sprinkler和Rain变量进行采样，最后对WetGrass变量采样，如图8.10所示（图中绿色表示变量取值为True，红色表示取值为False）。根据贝叶斯网络的全概率公式
1700537625
1700537626
1700537627
1700537628
1700537629
（8.20）
1700537630
1700537631
可以看出祖先采样得到的样本服从贝叶斯网络的联合概率分布。
1700537632
1700537633
1700537634
1700537635
1700537636
图8.10 祖先采样示例图
1700537637
1700537638
如果只需要对贝叶斯网络中一部分随机变量的边缘分布进行采样，可以用祖先采样先对全部随机变量进行采样，然后直接忽视那些不需要的变量的采样值即可。由图可见，如果需要对边缘分布p(Rain)进行采样，先用祖先采样得到全部变量的一个样本，如（Cloudy=T，Sprinkler=F，Rain=T，WetGrass=T），然后忽略掉无关变量，直接把这个样本看成是Cloudy=T即可。
1700537639
1700537640
接下来考虑含有观测变量的贝叶斯网络的采样，如图8.11所示。网络中有观测变量（Sprikler=T，WetGrass=T）（观测变量用斜线阴影表示），又该如何采样呢？最直接的方法是逻辑采样，还是利用祖先采样得到所有变量的取值。如果这个样本在观测变量上的采样值与实际观测值相同，则接受，否则拒绝，重新采样。这种方法的缺点是采样效率可能会非常低，随着观测变量个数的增加、每个变量状态数目的上升，逻辑采样法的采样效率急剧下降，实际中基本不可用。
1700537641
1700537642
1700537643
1700537644
1700537645
图8.11 含有观测变量的贝叶斯网络
1700537646
1700537647
因此，在实际应用中，可以参考重要性采样的思想，不再对观测变量进行采样，只对非观测变量采样，但是最终得到的样本需要赋一个重要性权值：
1700537648
1700537649
