贝叶斯网络

形式上，贝叶斯网络是一个有向无环图（DAG），其节点代表贝叶斯意义上的变量:它们可以是可观察量、潜在变量、未知参数或假设。边表示条件依赖关系；未连接的节点(没有路径将一个节点连接到另一个节点)表示彼此条件独立的变量。每个节点都与一个概率函数相关联，该函数将节点的父变量的一组特定值作为输入，并给出(作为输出)由节点表示的变量的概率(或概率分布，如果适用)。例如，如果   父节点代表    布尔变量则概率函数可以由以下表格表示   条目，每个条目对应一个   可能的父组合。类似的想法也可以应用于无向图，也可能是循环图，如马尔可夫网络。

两个事件会导致草被弄湿:主动洒水或下雨。雨水对喷洒器的使用有直接影响(即下雨时，喷洒器通常不起作用)。这种情况可以用贝叶斯网络建模(如图所示)。每个变量有两个可能的值，即T(真)和F(假)。

联合概率函数为:

其中，G =草湿(真/假),S =洒水喷头开启(真/假)，和R =下雨(真/假)。

该模型可以回答给定效果(所谓的逆概率)时存在原因的问题，例如“给定草是湿的，下雨的概率是多少？”通过使用条件概率公式并对所有控（Nuisance variable）求和:

利用联合概率函数的展开式   条件概率来自于条件概率表如图所示，我们可以计算分子和分母的和中的每一项。例如，

那么数值结果(由相关变量值下标)是

回答一个介入性的问题，例如“考虑到我们弄湿了草地，下雨的可能性有多大？”答案取决于干预后的联合分布函数

通过去除因子获得   来自干预前的分布。do运算符强制G的值为真。降雨的概率不受该动作的影响:

  。

要预测打开洒水装置的影响:

这个术语   移除，表明该动作影响草，但不影响雨。 考虑到未观察到的变量，这些预测可能不可行，就像大多数政策评估问题一样。行动的效果   然而，只要满足后门标准，仍然可以预测。^[1]它指出，如果一个集合Z可以观察到^[2](或阻塞)所有后门路径X到Y然后

  。

后门路径是以箭头指向X。满足后门标准的集合称为“足够”或“可接受”例如，集合Z = r可以用来预测S = T在G，因为r d-分隔(唯一的)后门路径S ⅲ r → G。然而，如果S没有观察到，没有其他集合d-分隔该路径和打开洒水装置的效果(S = T)在草地上(G)不能从被动观察中预测。在这种情况下P（G | 做(S = T))未被“识别”。这反映了这样一个事实，即由于缺乏干预数据，观察到的S和G是由于因果关系还是虚假的

(明显依赖于共同原因，r)中。(见辛普森悖论)

要确定一个因果关系是否可以从任意具有未观察变量的贝叶斯网络中识别，可以使用以下三个规则:做微积分”^[3]并测试是否所有做可以从该关系的表达式中移除项，从而确认期望的量可以从频率数据中估计。^[4]

如果联合分布中的依赖关系稀疏，使用贝叶斯网络可以在穷举概率表上节省大量内存。例如，一种将10个二值变量的条件概率存储为表的简单方法需要存储空间   价值观。如果没有变量的局部分布依赖于三个以上的父变量，贝叶斯网络表示最多存储   价值观。

贝叶斯网络的一个优点是，与完全联合分布相比，人类在直觉上更容易理解(一组稀疏的)直接依赖关系和局部分布。

贝叶斯网络执行三个主要推理任务:

3.1 推断未观察到的变量

因为贝叶斯网络是其变量及其关系的完整模型，所以它可以用来回答关于它们的概率查询。例如，网络可以用来更新变量子集的状态知识证据变量)被观察到。这个计算过程在后面的给定证据的变量分布称为概率推断。当为变量子集选择最小化一些预期损失函数(例如决策错误的概率)的值时，后验概率为检测应用提供了通用的充分统计量。因此，贝叶斯网络可以被认为是自动将贝叶斯定理应用于复杂问题的机制。

最常见的精确推理方法有:可变消除，它通过将总和分布在乘积上来逐个消除(通过积分或求和)未观察到的非查询变量；使用连接树算法传播，可缓存计算，以便可以一次查询许多变量，并且可以迅速传播新证据；递归条件和“与/或”搜索，允许时空权衡并且当使用足够的空间时匹配变量消除的效率。所有这些方法的复杂性在网络中呈指数级增长树宽。最常见的近似推理算法是重要性采样，随机的MCMC模拟，迷你桶消除，循环置信度传播, 广义置信度传播和变分法。

3.2 参数学习

为了充分指定贝叶斯网络，从而充分表示联合概率分布，有必要为每个节点指定X的概率分布为X以...为条件“x”s父母。的分布X有条件的父母可以有任何形式。通常使用离散或高斯分布，因为这简化了计算。有时只有分布的约束是已知的；然后可以使用最大熵原理来确定单个分布，即给定约束条件下具有最大熵的分布。(类似地，在动态贝叶斯网络的特定上下文中，隐藏状态时间演化的条件分布通常被指定为最大化隐含随机过程的熵率。)

这些条件分布通常包括未知的参数，必须通过数据进行估计，例如最大概似法接近。可能性的直接最大化后验概率)通常是复杂的。解决这个问题的经典方法是期望最大化算法它根据观察到的数据交替计算未观察变量的期望值，并假设先前计算的期望值是正确的，最大化完全可能性(或后验可能性)。在温和的规律性条件下，该过程收敛于参数的最大似然(或最大后验)值。

一种更完全的贝叶斯方法是将参数视为额外的未观察到的变量，并根据观察到的数据计算所有节点的完全后验分布，然后将参数积分出来。这种方法可能很昂贵，并且会导致大尺寸模型，使得经典的参数设置方法更容易处理。

3.3 结构学习

在最简单的情况下，贝叶斯网络由专家指定，然后用于执行推理。在其他应用中，定义网络的任务对人类来说太复杂了。在这种情况下，必须从数据中学习网络结构和局部分布的参数。

自动学习贝叶斯网络的图结构是机器学习中追求的挑战。基本思想可以追溯到Rebane和 Pearl 开发的恢复算法^[5]并且基于三节点DAG中允许的三种可能模式之间的区别:

前2个表示相同的依赖关系(   和   是独立给定的   )因此无法区分。然而，对撞机可以被唯一地识别，因为   和   是边缘独立的，所有其他对都是依赖的。因此，尽管骨骼(去掉箭头的图)这三个三元组是相同的，箭头的方向性是部分可识别的。同样的区别适用于以下情况   和   有共同的父母，除了必须首先满足这些父母的条件。已经开发了算法来系统地确定底层图的骨架，然后定向其方向性由观察到的条件独立性决定的所有箭头。^[6][6][7][8]

另一种结构学习方法使用基于优化的搜索。它需要一个打分函数和搜索策略。一个常见的评分函数是后验概率给定训练数据的结构，比如BIC或者说是BDeu。的时间要求穷举搜索返回一个最大化得分的结构是超指数变量的数量。局部搜索策略进行增量更改，旨在提高结构的得分。像这样的全局搜索算法马尔科夫蒙特卡洛可以避免被困在局部最小值。弗里德曼等人^[9][10]讨论如何在变量之间使用互信息，并找到一个最大化这一点的结构。他们通过将父候选集限制为k节点，并在其中进行详尽的搜索。

精确BN学习的一种特别快速的方法是将问题转换为优化问题，并使用整数规划求解。在求解过程中，无环性约束以切面的形式添加到整数规划中。^[11]这种方法可以处理多达100个变量的问题。

为了处理成千上万个变量的问题，需要一种不同的方法。一种是首先对一个排序进行采样，然后找到关于该排序的最佳BN结构。这意味着在可能排序的搜索空间上工作，这很方便，因为它比网络结构的空间小。然后对多个订单进行采样和评估。当变量数量巨大时，这种方法被证明是文献中最好的方法。^[12]

另一种方法是关注可分解模型的子类，极大似然估计(MLE)对其具有封闭形式。这样就有可能发现数百个变量的一致结构。^[13]

学习具有有限树宽的贝叶斯网络对于允许精确、易于处理的推理是必要的，因为最坏情况下推理复杂性在树宽k中是指数的(在指数时间假设下)。然而，作为图的全局属性，它大大增加了学习过程的难度。在这种情况下，使用 K树进行有效学习是可能的。^[14]

已知资料   和参数   ，简单的贝叶斯分析从先验概率开始(在前)   和似然函数   为了计算后验概率   。

通常是在前面   这又取决于其他参数   没有提到的可能性。所以，前一个   必须被可能性所取代   ，和一个先验   关于新引入的参数   这导致了后验概率

这是分层贝叶斯模型。

该过程可以重复；例如，参数   可能又取决于附加参数   这需要他们自己的优先权。最终，该过程必须终止，优先级不依赖于未提及的参数。

4.1 介绍性例子

给定测量的数量   每个都具有已知标准差的正态分布误差   ,

假设我们有兴趣估算   。一种方法是估计   使用最大似然方法；由于观测值是独立的，似然因子分解和最大似然估计是简单的

  。

然而，如果数量是相关的，那么例如个体   然后这种关系破坏了独立性，并提出了一个更复杂的模型，例如，

  ,

有不正确的先验   平坦的，   平的   。当...的时候   ，这是一个识别模型(即存在模型参数的唯一解)，以及个体的后验分布   倾向于移动，或者收缩远离最大似然估计，接近它们的共同均值。这收缩是分层贝叶斯模型中的典型行为。

4.2 对前科的限制

在分层模型中选择先验时需要注意一些问题，特别是在较高层次的标度变量上，例如变量   在这个例子中。通常的先验，如杰弗里斯先验通常不起作用，因为后验分布将不可归一化，并且通过最小化预期损失所做的估计将不被允许。

贝叶斯网络有几种等价的定义。对于以下内容，让G=(V,E)是一个有向无环图 (DAG)，并令X=(X_v)，v∣V是一组随机变量，索引为V。

5.1 因式分解定义

X是一个贝叶斯网络，关于G如果它的关节概率密度函数(相对于乘积度量)可以写为单个密度函数的乘积，条件是它们的父变量:^[15]

其中pa(v)是的父母的集合v(即那些直接指向的顶点v通过单个边缘)。

对于任意一组随机变量，联合分布中任意成员的概率可以使用链式法则条件概率来计算(给定的拓扑排序为X)如下所示:^[15]

使用上面的定义，这可以写成:

  对于每一个   哪一个是的父母   

这两个表达式的区别在于，给定其父变量的值，变量与其任何非后代的条件独立性。

5.2 当地马尔可夫性质

X是一个贝叶斯网络，关于G如果它满足当地马尔可夫性质:在给定父变量的情况下，每个变量与其非后代是条件独立的:^[16]

其中de(v)是后代的集合V \ de(v)是的非后代的集合v。

这可以用类似于第一个定义的术语来表示，如

  对于每一个   它不是的后代   对于每一个   哪一个是的父母   

父代集合是非子代集合的子集，因为图是无环的。

5.3 发展贝叶斯网络

开发贝叶斯网络通常从创建DAG开始G使得X满足当地马尔可夫性质在以下方面的要求G。有时这是一个因果 DAG。给定每个变量的父变量的条件概率分布G被评估。在许多情况下，特别是在变量是离散的情况下，如果X是这些条件分布的乘积X是一个贝叶斯网络，关于G。^[17]

5.4 马尔可夫毯

节点的马尔可夫毯是由它的父节点、子节点和其子节点的任何其他父节点组成的一组节点。马尔可夫毯使节点独立于网络的其余部分；一个节点的马尔可夫毯中变量的联合分布足以计算该节点的分布。X是一个贝叶斯网络，关于G如果给定其马尔可夫毯，每个节点都有条件地独立于网络中的所有其他节点。^[16]

d-分离

这个定义可以通过定义两个节点的“d”分隔来变得更通用，其中d代表方向。^[18][19]让P从节点开始追踪u到v。路径是两个节点之间的无环、无方向(即所有边缘方向都被忽略)的路径。然后P据说是d-由一组节点分隔Z如果下列任一条件成立:

• P包含(但不需要完全是)有向链，    或者    ，使得中间节点m在Z,
• P包含一个叉子，    ，使得中间节点m在Z，或
• P包含倒置的叉子(或碰撞器)，    ，使得中间节点m不在Z也没有后代m在Z。

节点u和v是d-由...分隔Z如果它们之间的所有轨迹d-分居了。如果u和v不是d-分离的，而是d-连接的。

X是一个贝叶斯网络，关于G如果，对于任意两个节点u,v(d ):

其中，Z是一套d-分离u和v。(马尔可夫毯是最小的节点集，它d-分隔节点v从所有其他节点。)

5.5 因果网络

虽然贝叶斯网络经常被用来表示因果关系，但情况不一定如此:有向边来自u到v不需要X_v有原因地依赖于X_u。这可以通过图上的贝叶斯网络来证明:

是等价的:也就是说，它们强加了完全相同的条件独立性要求。

因果网络是贝叶斯网络，要求关系是因果的。因果网络的附加语义指定如果一个节点X处于给定状态x(像这样写的动作(X = x))，则概率密度函数变为从的父节点切断链路得到的网络的概率密度函数。X到X，和设置X导致的价值x。^[20]使用这些语义，可以从干预前获得的数据预测外部干预的影响。

1990年，库珀在斯坦福大学从事大型生物信息学应用时，证明了贝叶斯网络中的精确推理是 NP难问题的。^[20]这一结果促进了对近似算法的研究，目的是开发一种易于处理的概率推理近似。1993年，达古姆和卢比证明了贝叶斯网络中概率推理近似复杂性的两个令人惊讶的结果。^[21]首先，他们证明了没有易于处理的确定性算法能够在绝对误差内近似概率推理 ɛ。其次，他们证明了在绝对误差范围内，没有易于处理的随机算法能够近似概率推理ɛ < 1/2置信概率大于1/2。

大约与此同时，罗斯证明了贝叶斯网络中的精确推理实际上是P-完全(因此和计算合取范式公式(CNF)的令人满意的赋值数量以及因子内的近似推理一样困难2^n1-ɛ每一个ɛ > 0，即使对于架构受限的贝叶斯网络，也是NP难的。^[22][23]

实际上，这些复杂性结果表明，尽管贝叶斯网络是人工智能和机器学习应用的丰富表示，但它们在大型现实世界应用中的使用需要受到拓扑结构约束(如朴素贝叶斯网络)或条件概率的限制。有界方差算法^[24]是贝叶斯网络中第一个可以证明的快速近似算法，能够在保证误差近似的情况下有效地近似概率推理。这种强大的算法需要对贝叶斯网络的条件概率进行较小的限制，使其远离零和一1/p(n)其中，p(n)是网络中节点数量的多项式n。

贝叶斯网络的著名软件包括:

• 只是另一个吉布斯采样器(JAGS)-winbug的开源替代方案。使用吉布斯采样。
• OpenBUGS -WinBUGS的开源开发。
• SPSS Modeler -商业软件，包括贝叶斯网络的实现。
• Stan(软件)斯坦是一个开源软件包，用于使用哈密顿蒙特卡罗(Hamiltonian Monte Carlo)的变体——不掉头采样器来获得贝叶斯推断。
• winbug -MCMC采样器的第一批计算实现之一。不再维护。

术语贝叶斯网络是由朱迪亚·珀尔在1985年创造的，旨在强调:^[25]

• 输入信息的通常主观性
• 依赖贝叶斯条件作为更新信息的基础
• 因果推理模式和证据推理模式的区别^[26]

20世纪80年代末，珀尔智能系统中的概率推理^[27]和Richard E. Neapolitan专家系统中的概率推理^[28]总结了它们的性质并将其确立为一个研究领域。

1. Pearl, Judea (2000). Causality: Models, Reasoning, and Inference. Cambridge University Press. ISBN 978-0-521-77362-1. OCLC 42291253.
2. "The Back-Door Criterion" (PDF). Retrieved 2014-09-18.
3. "d-Separation without Tears" (PDF). Retrieved 2014-09-18.
4. Pearl J (1994). "A Probabilistic Calculus of Actions". In Lopez de Mantaras R, Poole D. UAI'94 Proceedings of the Tenth international conference on Uncertainty in artificial intelligence. San Mateo CA: Morgan Kaufmann. pp. 454–462. arXiv:1302.6835. Bibcode:2013arXiv1302.6835P. ISBN 1-55860-332-8.
5. Shpitser I, Pearl J (2006). "Identification of Conditional Interventional Distributions". In Dechter R, Richardson TS. Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence. Corvallis, OR: AUAI Press. pp. 437–444. arXiv:1206.6876.
6. Rebane G, Pearl J (1987). "The Recovery of Causal Poly-trees from Statistical Data". Proceedings, 3rd Workshop on Uncertainty in AI. Seattle, WA. pp. 222–228. arXiv:1304.2736.
7. Spirtes P, Glymour C (1991). "An algorithm for fast recovery of sparse causal graphs" (PDF). Social Science Computer Review. 9 (1): 62–72. doi:10.1177/089443939100900106.
8. Spirtes P, Glymour CN, Scheines R (1993). Causation, Prediction, and Search (1st ed.). Springer-Verlag. ISBN 978-0-387-97979-3.
9. Verma T, Pearl J (1991). "Equivalence and synthesis of causal models". In Bonissone P, Henrion M, Kanal LN, Lemmer JF. UAI '90 Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence. Elsevier. pp. 255–270. ISBN 0-444-89264-8.
10. Friedman N, Geiger D, Goldszmidt M (November 1997). "Bayesian Network Classifiers". Machine Learning. 29 (2–3): 131–163. doi:10.1023/A:1007465528199.
11. Friedman N, Linial M, Nachman I, Pe'er D (August 2000). "Using Bayesian networks to analyze expression data". Journal of Computational Biology. 7 (3–4): 601–20. CiteSeerX 10.1.1.191.139. doi:10.1089/106652700750050961. PMID 11108481.
12. Cussens J (2011). "Bayesian network learning with cutting planes" (PDF). Proceedings of the 27th Conference Annual Conference on Uncertainty in Artificial Intelligence: 153–160.
13. Scanagatta M, de Campos CP, Corani G, Zaffalon M (2015). "Learning Bayesian Networks with Thousands of Variables". NIPS-15: Advances in Neural Information Processing Systems. 28. pp. 1855–1863.
14. Petitjean F, Webb GI, Nicholson AE (2013). Scaling log-linear analysis to high-dimensional data (PDF). International Conference on Data Mining. Dallas, TX, USA: IEEE.
15. M.Scanagatta、G. Corani、C. P. de Campos和M. Zaffalon。学习具有成千上万个变量的树宽有界贝叶斯网络。《NIPS-16:神经信息处理系统的进展》，29，2016年。
16. , p. 496.
17. , p. 499.
18. Neapolitan RE (2004). Learning Bayesian networks. Prentice Hall. ISBN 978-0-13-012534-7.
19. Geiger D, Verma T, Pearl J (1990). "Identifying independence in Bayesian Networks" (PDF). Networks. 20: 507–534. doi:10.1177/089443939100900106.
20. Richard Scheines, D-separation
21. Cooper GF (1990). "The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks" (PDF). Artificial Intelligence. 42 (2–3): 393–405. doi:10.1016/0004-3702(90)90060-d.
22. Dagum P, Luby M (1993). "Approximating probabilistic inference in Bayesian belief networks is NP-hard". Artificial Intelligence. 60 (1): 141–153. CiteSeerX 10.1.1.333.1586. doi:10.1016/0004-3702(93)90036-b.
23. D.罗斯，论近似推理的难度，IJCAI (1993)
24. D.罗斯，论近似推理的难度，人工智能(1996)
25. Dagum P, Luby M (1997). "An optimal approximation algorithm for Bayesian inference". Artificial Intelligence. 93 (1–2): 1–27. doi:10.1016/s0004-3702(97)00013-1.
26. Pearl J (1985). Bayesian Networks: A Model of Self-Activated Memory for Evidential Reasoning (UCLA Technical Report CSD-850017). Proceedings of the 7th Conference of the Cognitive Science Society, University of California, Irvine, CA. pp. 329–334. Retrieved 2009-05-01.
27. Bayes T, Price (1763). "An Essay towards solving a Problem in the Doctrine of Chances". Philosophical Transactions of the Royal Society. 53: 370–418. doi:10.1098/rstl.1763.0053.
28. Pearl J (1988-09-15). Probabilistic Reasoning in Intelligent Systems. San Francisco CA: Morgan Kaufmann. p. 1988. ISBN 978-1558604797.
29. Neapolitan RE (1989). Probabilistic reasoning in expert systems: theory and algorithms. Wiley. ISBN 978-0-471-61840-9.