证明贝叶斯网络必须是无环的

机器算法验证 贝叶斯网络
2022-04-08 16:42:31

我正在努力证明贝叶斯网络必须是无环的。谁能帮我证明这一点?我试图通过构建循环图并显示概率分布的一些矛盾来证明。但它无处可去

4个回答

通过创建循环图,您不会发现任何矛盾。并不是说贝叶斯网络(或者我听说它们称为条件独立网络,因为除了条件独立规则之外,它们与贝叶斯主义没有任何关系)“必须是非循环的”。我们假设它们是非循环的以获得某些属性并简化概率的计算。事实上,如果我们放松非循环限制以及有向限制,我们会得到一个更通用的模型,称为马尔可夫网络。

贝叶斯网络可以看作是一种数据结构,它为以分解的方式紧凑地表示联合分布提供了骨架。对于任何有效的联合分布,应满足两个限制条件:

1)分布中的所有概率都应该是非负的;
2) 所有的概率总和为 1。

通常,图由分解的顺序和分布的独立结构中假设的条件独立性决定。由于我们正在处理一个无效的贝叶斯网络,我们不需要遵循这个过程,我们可以设计许多反例来验证分布的总和不是 1。例如,假设我们有这样一个超过三个的图二进制变量:
在此处输入图像描述

我们可以很容易地获得联合分布:在所有种可能性中,至少有两种是 1: 23P(a0,b0,c0)=P(a0|c0)P(b0|a0)P(c0|b0)=1
P(a1,b1,c1)=P(a1|c1)P(b1|a1)P(c1|b1)=1

,所以分布无效(说明循环贝叶斯网络无效)。A,B,CP(A,B,C)2>1

如果我们删除图中的任何一个方向并相应地调整 CPT 中的参数,我们可以发现联合分布是有效的。

恐怕尼克的回答可能不完整。

BN 必须是非循环的,以保证它们的潜在概率分布被归一化为 1。很容易证明这是这种情况,从没有父节点的顶点开始(必须存在,否则图将包含一个循环) 并将其边缘化,然后重复该过程,直到所有顶点都被考虑在内。

如果图有一个循环并且也很容易找到反例,则不再保证是这种情况。考虑循环图,其中每个父级的值完全决定其子级的值,例如如果我们现在对所有可能状态的联合分布求和,那么类型的所有状态的联合概率为 1,所有其他状态的概率为 0。显然,多个状态的和"ones" 大于一。ABCp(B=x|A=x)=1(A,B,C)(x,x,x)

当然,这个论点仅适用于平稳分布,我认为这是 OP 问题的前提。

贝叶斯网络被定义为 DAG(有向无环图),您无法证明定义。看看这个解释