65.9K
CodeProject 正在变化。 阅读更多。
Home

置信网络推理

hzhou
starIconstarIconstarIconstarIconstarIcon

5.00/5 (21投票s)

2002年12月7日

7分钟阅读

viewsIcon

173038

downloadIcon

2016

C# 实现的用于置信网络推理的桶消除算法。

摘要

置信网络是进行概率推理的强大工具。在本文中，我将演示一个用C#实现的桶消除算法，用于在置信网络中进行推理。

引言

置信网络，也称为贝叶斯网络或图模型，是一个图，其中具有条件概率表 (CPT) 的节点代表随机变量，连接节点的链接或箭头代表影响。请参见图 1 示例。

图 1 湿草置信网络。P(X=T) 可以通过 1-P(X=F) 获得。

在数学上，置信网络等同于联合概率分布。它为我们提供了一种对感兴趣的变量集之间的概率关系进行建模的自然方式。由于其概率性质，置信网络在编码不确定知识方面非常有用。一旦我们有了网络，我们就可以从中进行推理，无论是诊断性的（从结果到原因）、因果性的（从原因到结果）还是混合性的。然后，我们可以基于推理结果做出决策或建议。这就是置信网络在人工智能中的应用方式。

置信网络是一个在理论和应用上都非常丰富的探索领域。然而，由于篇幅有限，本文将不作详细讨论。取而代之的是，我将通过一个简单的例子来讲解，而不提供证明。希望本文能让你对置信网络的工作方式有所了解。如果你有兴趣，可以参考 [1] 这样的教科书，或在互联网上搜索教程。

推理

条件概率，例如，P(A|B,C)，表示在事件 B 和 C 已知的情况下事件 A 发生的概率。联合概率 P(A, B) 表示事件 A 和 B 同时发生的概率。根据概率演算的乘积规则，联合概率可以分解为先验概率和条件概率的乘积，

P(A, B) = P(A|B)P(B),          (1)

其中 P(B) 称为先验概率或无条件概率。

推理的任务是计算一组查询变量在给定一些证据变量的情况下，其条件概率 P(查询 | 证据)。考虑图 1 中的置信网络，如果我们想知道在草是湿的情况下，阴天（不阴天）的概率，我们将计算 P( cloudy=0 | wetGrass=1 )。通过重新排列公式 (1)，我们得到

P(c=0 | w=1) = P(c=0, w=1)/P(w=1).        (2)

要计算 P(w=1)，我们必须包含 W 节点父节点的影响，这在置信网络中由箭头表示。W 节点有两个父节点 S 和 R。W 的父节点也受其父节点的影响。重复此过程直到达到先验概率，得到

P(w=1) = ∑s,rP(s,r)P(w=1|s,r) = ∑c,s,rP(c)P(s|c)P(r|c)P(w=1|s,r).     (3)

以类似的方式计算 P(c=0, w=1)，我们得到

P(c=0 | w=1) = P(c=0)∑s,rP(s|c=0)P(r|c=0)P(w=1|s,r)/P(w=1).    (4)

现在，等式右侧的所有概率都在置信网络的 CPT 中明确定义了。

桶消除算法

从上面的例子可以看出，进行推理就是计算联合概率 (P(w=1) 可以视为 *联合* 的特例)。如果我们有一个计算联合概率 P(c,s,r,w) 的算法，我们就可以在置信网络中进行任何推理。

我们重写 (3) 式为

P(w=1) = ∑cP(c)∑sP(s|c)∑rP(r|c)P(w=1|s,r).   (5)

桶消除算法 [2]（或更一般的变量消除算法）的思想是将求和分布到乘积上。从 (5) 式的最内层（最右边）开始，

P(w=1) = ∑cP(c)∑sP(s|c)∑rP(r|c)λw(s,r)    where λw(s,r)=P(w=1|s,r)
       = ∑cP(c)∑sP(s|c)λr(c,s)    where λr(c,s)=∑rP(r|c)λw(s,r)
       = ∑cP(c)λs(c)    where λs(c)=∑sP(s|c)λr(c,s)
       = λc,         (6)

现在该节点被替换为桶 λ，其中包含相应节点的 CPT 和子桶。计算过程按相反的顺序进行。它从最外层的节点，即根节点开始。如果一个节点是证据或查询，我们使用提供的数值；否则，我们对所有可能值进行求和。然后该过程可以递归地实现。

实现

实现具有如图 2 所示的静态结构。下载的源代码是一个简化版本。它只适用于二元节点，即节点只取 0 和 1 两个值。我还删除了所有异常控制，如 try-catch 和 assert，并删除了所有优化，尽管其中一些是显而易见的和直接的。目的是使代码更易于阅读。一旦你理解了代码，调整代码应该不难。

图 2 置信网络类的静态结构

节点在 XML 文件中定义。下载文件包含两个文件，*BN_WetGrass.xml* 和 *BN_Alarm.xml*，两者都取自 [1]。它们具有完全不同的拓扑结构。你可以设计自己的节点。请记住，节点的顺序很重要，任何节点的父节点必须在该节点之前定义。方法 BNet::Build("nodes.xml") 从 XML 文件加载节点，然后用这些节点创建一个置信网络。

要进行推理，可以执行以下操作：

BNet net = new BNet();
net.Build(“bn_wetGrass.xml”);
BNInference infer = new BElim(net)
double pr = infer.GetBelief(“sprinkler=1; cloudy=0”, “WetGrass=0; Rain=1”);

桶在 BElim::PrepareBucket() 中初始化。仔细阅读示例公式 (6) 后，你会发现每个桶不仅需要其对应节点的父节点作为输入，还需要其子桶请求的节点作为输入。

算法的核心在 BElim::Sum(int id, int para) 中，如下面的片段所示：

protected double Sum(int node_id, int para)
{
    // skipped ... 
    double pr = 0.0;

    foreach(int value in theNode.Range)
    {
        if( theNode.IsEvidence && theNode.Evidence != value )
            continue;

        double tmpPr = theNode.CPT;

        foreach(Bucket nxtBuck in theBuck.childBuckets)
        {
            int next_para = 0;
            foreach(BNode node in nxtBuck.parentNodes)
            {
                //calculate next_para; 
            }
            tmpPr *= Sum(nxtBuck.id, next_para);
        }
        pr += tmpPr;
    }
    return pr;
}

这里我们利用了二元节点。整数 para 用作一个大小为 32 的位数组。它允许我们对其进行位运算，从而使代码更高效、更紧凑。求和遍历所有可能的值，除非节点有提供的值。然后它考虑来自其子桶的贡献。要调用子桶的贡献，求和必须提供参数，并让下一个桶知道哪个节点具有什么值等。我将不再深入，因为这些内容通过代码比通过文字更容易解释。

使用置信网络

WetGrass 网络非常简单，但已经显示出一些微妙之处。例如，我们可以计算在草是湿的情况下喷水器工作的概率。我们得到 P( sprinkler=1 | wetGrass=1 ) = 0.43。这个推理是诊断性的，因为它从结果告诉我们原因。另一方面，如果我们知道正在下雨或没有下雨，那么 P( sprinkler=1 | wetGrass=1; rain=1 ) = 0.19，或 P(sprinkler=1 | wetGrass=1; rain=0 ) = 1.0。您可以看到下雨的额外信息改变了 sprinkler=1 的概率，尽管喷水器和下雨并没有直接相互影响。这种效应称为 *解释消除*。即其中一个的出现使得另一个不太可能，即使它们是独立的。

你可以尝试使用代码，尝试对 WetGrass 和 Alarm 网络进行不同的推理。你可能会或不会感到惊讶。推理并不总是直观的。你的常识可能并不总是正确的。

编码注意事项

使用 C# 的原因是我想学习它。我将 C# 用作更好的 C++，而不是更好的“更好的”C :)。作为一个长期的 C++ 程序员，我花了些时间才习惯于在不考虑哪里放 delete 的情况下使用 new。唯一让我困扰的是 ArrayList。在我看来，声明中无法指定类型；类型是在你向其中添加项时即时确定的。这可能是一个很好的特性。但是，如果我们想将设计与实现分开，它可能会引起问题，我们必须依赖注释来提醒实现者列表包含的项的类型。也许我在这里遗漏了什么。

代码是用 Emacs 编辑器编辑的，并由 C# SDK 的 *csc.exe* 编译，该 SDK 是从 Microsoft 网站下载的。Emacs 编辑器限制了我编写更好的 UI。

参考文献

  1. S. Russell 和 P. Norvig。“人工智能：一种现代方法”。Prentice Hall。1995
  2. R. Dechter。“桶消除：概率推理的统一框架”，收录于“图模型学习”。MIT出版社。1998。编辑 M. I. Jordan。
© . All rights reserved.