“贝叶斯网络”的版本间的差异
（→编者推荐） |
|||
| 第480行： | 第480行： | ||
=== 课程推荐 === | === 课程推荐 === | ||
| − | |||
| − | |||
[[File:图模型的介绍.jpeg|400px| thumb |right| [https://campus.swarma.org/course/1579 因果科学与Causal AI读书会第二季]]] | [[File:图模型的介绍.jpeg|400px| thumb |right| [https://campus.swarma.org/course/1579 因果科学与Causal AI读书会第二季]]] | ||
| 第496行： | 第494行： | ||
| − | === | + | === 其他参考资料 === |
| + | |||
| + | ==== 文章总结 ==== | ||
| + | |||
| + | [https://mp.weixin.qq.com/s/mOdTI0gR9rsRyX4fz3mYNA 因果科学入门读什么书？Y. Bengio博士候选人的研读路径推荐] | ||
| + | |||
| + | [https://mp.weixin.qq.com/s/TtYsTyyGEX7U1ZOSl-lsPw 前沿综述：因果推断与因果性学习研究进展] | ||
| + | |||
| + | [https://mp.weixin.qq.com/s/W6PIE211TavEgg_s3adDdg 因果表征学习最新综述：连接因果科学和机器学习的桥梁] | ||
| + | |||
| + | [https://mp.weixin.qq.com/s/pRgLZFJpbgmAyI7LgOnHug 历时3个月，全球32位讲者，共同讲述因果科学与Causal AI的全景框架！] | ||
| + | |||
| + | [https://mp.weixin.qq.com/s/f-rI5W6tc6qOzthbzK4oAw 崔鹏：稳定学习——挖掘因果推理和机器学习的共同基础] | ||
| + | |||
| + | [https://mp.weixin.qq.com/s/l-05jRYabGI-JoXedU-PLA 因果科学：连接统计学、机器学习与自动推理的新兴交叉领域] | ||
| + | |||
| + | [https://mp.weixin.qq.com/s/ZOUeF_HEFneYVi2BPe8LFg 因果观念新革命？万字长文，解读复杂系统背后的暗因果] | ||
| + | |||
| + | [https://mp.weixin.qq.com/s/dVxgHcQAz_VjT-HDa2fXgg 周晓华：因果推断的数学基础和在医学中的应用] | ||
| + | |||
| + | ==== 相关路径 ==== | ||
| + | * [https://pattern.swarma.org/path?id=99 因果科学与Casual AI读书会必读参考文献列表]，这个是根据读书会中解读的论文，做的一个分类和筛选，方便大家梳理整个框架和内容。 | ||
| + | * [https://pattern.swarma.org/path?id=9 因果推断方法概述],这个路径对因果在哲学方面的探讨，以及因果在机器学习方面应用的分析。 | ||
| + | * [https://pattern.swarma.org/path?id=90 因果科学和 Causal AI入门路径]，这条路径解释了因果科学是什么以及它的发展脉络。此路径将分为三个部分进行展开，第一部分是因果科学的基本定义及其哲学基础，第二部分是统计领域中的因果推断，第三个部分是机器学习中的因果（Causal AI）。 | ||
| + | * [https://pattern.swarma.org/path?id=28 复杂网络动力学系统重构文献]，这个路径是张江老师梳理了网络动力学重构问题，描述了动力学建模的常用方法和模型，并介绍了一些经典且重要的论文，这也是复杂系统自动建模读书会的主要论文来源，所以大部分都有解读视频。 | ||
| + | * [https://pattern.swarma.org/path?id=114 因果纠缠集智年会——因果推荐系统分论坛]关于因果推荐系统的参考文献和主要嘉宾介绍，来源是集智俱乐部的因果纠缠年会。 | ||
| − | |||
2021年4月12日 (一) 00:50的版本
贝叶斯网络 Bayesian network（BN）、信念网络 belief network、决策网络 decision network、贝叶斯模型 Bayes(ian) model或概率有向无环图模型 probabilistic directed acyclic graphical model是一种概率图模型（一种统计模型），它通过有向无环图无环图 directed acyclic graph（DAG）表示一组随机变量及其条件依赖关系。贝叶斯网络是一种理想的分析工具，用来预测一个事件的发生是由已知原因中的哪一个（些）引起的。例如，贝叶斯网络可以表示疾病和症状之间的概率关系。在给定症状的情况下，该网络可用于计算各种疾病出现的概率。
贝叶斯网络有多种变体。用来建模序列变量（例如，语音信号或蛋白质序列）的贝叶斯网络被称为动态贝叶斯网络 dynamic Bayesian network。贝叶斯网络可以进一步扩展，用来表示和解决在不确定性因素下的决策问题，这种扩展称为影响图 influence diagram。现在已有高效的算法学习出贝叶斯网络的结构，并通过贝叶斯网络做推理。
图模型
在形式上，贝叶斯网络是有向无环图 Directed acyclic graph（DAG），其节点表示随机变量（其概率为贝叶斯概率）； 它们可以是可观测量变量、隐变量、未知参数或假设。图中的边表示条件依赖；未连接（没有路径连接一个节点到另一个节点）的节点表示彼此之间条件独立。每个节点都与一个概率函数 Probability function 节点相关联，该函数把所有父节点代表的变量值作为输入，并给出该节点表示的随机变量的概率（或概率分布）。例如，如果 [math]\displaystyle{ m }[/math] 父节点表示 [math]\displaystyle{ m }[/math] 布尔变量，那么概率函数可以用一个包含[math]\displaystyle{ 2^m }[/math]行的表格表示，每一行代表一种（父节点）变量值的组合，以及对应的子节点变量的概率值。类似的想法可以应用于有环无向图，如马尔可夫网络 Markov network。
举例
草地变得湿润，可能有两种原因：主动洒水或者下雨。雨对洒水车的使用有直接的影响（也就是说，当下雨时，洒水车通常是不工作的）。这种情况可以用贝叶斯网络来模拟（如右图所示）。每个变量有两个可能的值，T (表示真)和 F (表示假)。
对应的联合概率函数 Joint probability distribution是:
- [math]\displaystyle{ \Pr(G,S,R)=\Pr(G\mid S,R) \Pr(S\mid R)\Pr(R) }[/math]
其中G表示“草地湿了（是/否）”，S表示“洒水器打开（是/否）”，R表示“下雨（是/否）”。
这个模型可以回答在给定一个结果的情况下一个原因是否存在的问题，比如“给定草是湿的，下雨的概率是多少? ”通过使用条件概率公式并对所有干扰变量 nuisance variable的求和:
- [math]\displaystyle{ \Pr(R=T\mid G=T) =\frac{\Pr(G=T,R=T)}{\Pr(G=T)} = \frac{\sum_{S \in \{T, F\}}\Pr(G=T, S,R=T)}{\sum_{S, R \in \{T, F\}} \Pr(G=T,S,R)} }[/math]
展开概率函数[math]\displaystyle{ \Pr(G,S,R) }[/math] ，并使用图中列出的条件概率，我们可以算出分子和分母中的各个项。比如说,
- [math]\displaystyle{ \begin{align} \Pr(G=T, S=T,R=T) & = \Pr(G=T\mid S=T,R=T)\Pr(S=T\mid R=T)\Pr(R=T) \\ & = 0.99 \times 0.01 \times 0.2 \\ & = 0.00198. \end{align} }[/math]
算出来的结果是
- [math]\displaystyle{ \Pr(R=T\mid G=T) = \frac{ 0.00198_{TTT} + 0.1584_{TFT} }{ 0.00198_{TTT} + 0.288_{TTF} + 0.1584_{TFT} + 0.0_{TFF} } = \frac{891}{2491}\approx 35.77 \%. }[/math]
这个模型还回答干预性的问题，比如“现在我们把草弄湿了，那么下雨的可能性有多大? ”答案取决于干预后的联合分布函数：
- [math]\displaystyle{ \Pr(S,R\mid\text{do}(G=T)) = \Pr(S\mid R) \Pr(R) }[/math]
该分布通过从干预前的分布中去除因子[math]\displaystyle{ \Pr(G\mid S,R) }[/math]得到，其中do算子强行使 G 的值为真。演算后可知下雨的可能性不受此干预的影响:
- [math]\displaystyle{ \Pr(R\mid\text{do}(G=T)) = \Pr(R). }[/math]
现在再预测开启洒水装置的影响:
- [math]\displaystyle{ \Pr(R,G\mid\text{do}(S=T)) = \Pr(R)\Pr(G\mid R,S=T) }[/math]
移除[math]\displaystyle{ \Pr(S=T\mid R) }[/math] 这个项表明这种行为影响的是草，而不是雨。
考虑到未观测变量，这些预测可能并不可行，就像大多数策略评估问题一样。但是，只要满足后门准则，仍然可以预测 [math]\displaystyle{ \text{do}(x) }[/math]的效果。[1][2] 如果一组观察到的变量Z能d-分隔(或阻塞)[3]从 X 到 Y 的所有"后门路径 back-door path，则有
- [math]\displaystyle{ \Pr(Y,Z\mid\text{do}(x)) = \frac{\Pr(Y,Z,X=x)}{\Pr(X=x\mid Z)}. }[/math]
后门路径是一条箭头指向X的路径。满足后门标准的（观测变量）集合称为“充分的”或“有效的”。例如，集合 Z = R 能有效地预测 S = T 对 G 的影响，因为 R d-分隔了(仅有的)后门路径 S ← R → G。但是，如果 S 没有被观测到，没有其他观测变量集合来 d-分隔这条路径，那就不能从观测数据中预测到“喷头被打开”(S = T)对于草地G的影响。在这种情况下，P(G | do(S = T))就没有被“识别”。这反映了一个事实：在缺乏干预性数据的情况下无法确认观察到的 S 和 G 之间的依赖关系是不是一种因果关系(可能由共同原因引起的强相关，比如辛普森悖论)。
（由共同原因引起的明显依赖关系，r)。(见辛普森悖论 Simpson's paradox）
为了确定一个因果关系是否可以从一个含有未观测变量的贝叶斯网络中识别出来，我们可以使用“ do-演算”[1][4] 的三个规则来检验是否所有的 do 项都可以从这个关系的表达式中去掉，从而确认所需的量可以从数据中估计出来。[5]
如果依赖关系在联合分布中是稀疏的（变量间依赖较少，即对应的图模型里的边较少），那么相对于存储一张完整的概率表，使用贝叶斯网络可以节省相当多的内存。例如，将10个二值变量的条件概率存储为一个表的，需要存储[math]\displaystyle{ 2^{10} = 1024 }[/math] 个值。而在每个变量最多依赖3个父变量的情况下，使用贝叶斯网络表示最多只存储[math]\displaystyle{ 10\cdot2^3 = 80 }[/math]个值。
相比于完全版的联合概率分布，理解（一组稀疏的）直接的变量间依赖关系和局部的概率分布对于人类来说要更加直观易懂。这正是贝叶斯网络的一个优点。
推理与学习
贝叶斯网络的推理和学习主要包含三个任务:
推断未观测变量
因为贝叶斯网络是变量及其关系的完整模型，所以它可以用来回答关于变量的概率问题。例如，当网络中某些变量被观测到时，也就是其确切值已知的情况下，我们可以更新对网络中其他未观测变量的认知。这种给定一些证据，然后计算的变量的后验概率的过程被称为概率推理 probabilistic inference。有时我们需要为某些变量赋值的同时最小化期望损失，此时后验概率为一些检测应用，例如检测决策错误的概率，提供了一个通用且充分的统计量。因此，贝叶斯网络可以被看作是一种应用贝叶斯定理解决复杂问题的自动化机制。
最常用的精确推理方法有: 变量消除法，即通过积分或求和的方式将未观察到的非查询变量逐一消除；团树传播算法，它将计算过程缓存，可以同时查询多个变量，并快速传播新的证据； 递归条件化 AND/OR 搜索法，它考虑了时间和空间取舍，并且在使用足够的空间时拥有与变量消除法相比拟的时间效率。所有这些方法的复杂度都随网络树宽的增长呈指数级上升。而最常见的近似推理算法有重要性抽样法 importance sampling、随机 MCMC 模拟法 Markov chain Monte Carlo、小桶消去法 、循环置信传播法 loopy belief propagation、广义置信传播法 generalized belief propagation和变分法 variational Bayes。
参数学习
为了获得一个完整的贝叶斯网络，从而获得一个完整的联合概率分布，需要详知道每个节点 X 的条件概率分布。X 的条件概率分布可以有各种各样的形式，最长见到、用到的分布是离散分布或高斯分布，因为计算简便。有时我们只知道一个分布应该符合哪些约束条件。此时可以使用最大熵原理来确定一个分布，即给定约束条件下熵最大的分布。类似地，在动态贝叶斯网络B的特定上下文中，隐变量的条件分布通常也被认为是能最大化其随机过程的熵率的那一个分布。
通常这些条件分布包括未知的参数，必须从数据中估计出来，例如，使用最大似然估计 maximum likelihood。给定未观测的变量，直接进行最大化似然（或后验概率）往往是很复杂的。这个问题的一个经典解决方案是EM算法。它利用观测数据计算出未观测变量的期望值，并假设先前计算的期望值是正确的，然后最大化完全似然（或后验），求期望和最大化两个步骤交替迭代进行。在某些条件下，这个过程能收敛于待估计参数的最大似然值（或最大后验值）。
一个更彻底的贝叶斯估计方法是将参数视为附加的未观测变量，并根据观测数据计算包含所有节点的完整后验概率分布，然后积分出参数。这种方法可能代价高昂，并得出一个大规模的模型，但能使经典的参数估计方法更易于处理。
结构学习
在最简单的情况下，一个贝叶斯网络可以有领域专家人工构建，然后用它来执行推理。在其他应用程序中，构建网络的任务对于人类来说过于复杂。这种情况就必须从数据中学习网络结构和各个变量的局部分布。
自动化学习出贝叶斯网络的图形结构是机器学习领域的一个挑战。其基本思想可以追溯到由 Rebane 和 Pearl 提出的恢复算法。[6]该算法的基础是三节点有向无环图中的三种可能模式:
| Pattern | Model |
|---|---|
| Chain | [math]\displaystyle{ X \rightarrow Y \rightarrow Z }[/math] |
| Fork | [math]\displaystyle{ X \leftarrow Y \rightarrow Z }[/math] |
| Collider | [math]\displaystyle{ X \rightarrow Y \leftarrow Z }[/math] |
前2个种模式表示的依赖关系是相同的（在给定[math]\displaystyle{ Y }[/math] 时，[math]\displaystyle{ X }[/math] 和[math]\displaystyle{ Z }[/math]是独立的），因此无法区分。然而，第三种模式确实可以被识别的，因为[math]\displaystyle{ X }[/math] 和[math]\displaystyle{ Z }[/math]是边际独立的，而其他所有变量对都是依赖的。因此，虽然这三个节点的连接方式和前两种模式相同，但这种模式中箭头的方向是部分可识别的。当[math]\displaystyle{ X }[/math] 和[math]\displaystyle{ Z }[/math]有着共同的父母时，这种不同也能被识别。这个算法已经发展到能系统地确定图的框架，然后由从数据中观察到的条件独立性确定所有箭头的方向。[1][7][8][9]
另一种结构学习的方法是基于优化的搜索。它需要一个评分函数和一个搜索策略。一个常见的评分函数是给定训练数据的结构的后验概率 posterior probability，比如 BIC 或 BDeu。穷举搜索可以获得能最大化得分函数的结构，但其时间要求随变量数增长呈超指数增长。局部搜索策略则进行增量改变，一步步迭代式改进结构的得分。像马尔可夫链蒙特卡洛这样的全局搜索算法可以避免陷入局部最优。 Friedman 等人[10][11] 认为可以使用变量之间的互信息，并找到一个讷讷感最大化互信息的结构，方法是通过将候选的父选节点集限制为k个节点并在其中进行穷尽式搜索。
一个特别快速精确学习出贝叶斯网络的方法是把问题转化为一个最优化问题，并使用整数规划 integer program (IP)解决它。以切平面 Cutting-plane method的形式求解整数规划问题时，在整数规划中加入了不规则性约束，[12]这种方法可以处理多达100个变量的问题。
处理成千上万个变量的问题时，则要用到不同的方。一种方法是采样出一个节点的（拓扑）排序，然后根据这种排序找到最优的网络结构。这意味着搜索工作只需要在包含可能排序的空间中进行，这比整个网络结构的搜索空间小，因而更加方便。可以进行多次采样和评估，这种方法在现有文献中已被证明在变量数量巨大的情况下是最佳的。[13]
另一种方法是将重点放在具有可分解模型的子类上，其最大似然估计具有封闭形式。这样就有可能为数百个变量发现一致的结构。[14]
学习树宽有限的贝叶斯网络对于精确的，可追溯的推理是必要的，因为最坏情况下的推理复杂度也只是树宽 k 的指数级（在指数时间假设下）。然而，作为图表的全局属性，它大大增加了学习过程的难度。在这种情况下，可以使用 K 树进行有效的学习。[15]
统计学简介
给定观测数据[math]\displaystyle{ x\,\! }[/math] 和模型参数 [math]\displaystyle{ \theta }[/math]，一个简单的贝叶斯分析任务就是用已知的先验概率[math]\displaystyle{ p(\theta) }[/math]和似然 [math]\displaystyle{ p(x\mid\theta) }[/math]，计算出后验概率[math]\displaystyle{ p(\theta\mid x) \propto p(x\mid\theta)p(\theta) }[/math]。
通常，先验概率[math]\displaystyle{ \theta }[/math]又依赖于并没有在似然中出现的参数[math]\displaystyle{ \varphi }[/math]，因此，必须用似然[math]\displaystyle{ p(\theta\mid \varphi) }[/math]代替先验概率[math]\displaystyle{ p(\theta) }[/math]，且需要用到新引入的参数[math]\displaystyle{ \varphi }[/math]的先验概率[math]\displaystyle{ p(\varphi) }[/math]。如此一来，新的后验概率就变成了
- [math]\displaystyle{ p(\theta,\varphi\mid x) \propto p(x\mid\theta)p(\theta\mid\varphi)p(\varphi). }[/math]
这是 层次贝叶斯模型 hierarchical Bayes model最简单的例子。
这个过程可能会一直重复。例如，参数[math]\displaystyle{ \varphi }[/math]可能依次依赖于其他参数 [math]\displaystyle{ \psi\,\! }[/math]，这就又需要[math]\displaystyle{ \psi\,\! }[/math]的先验概率。最终，这个层次化嵌套的过程必须终止，亦即某参数的先验概率不依赖于其他参数。
工业级案例
给定观测到的一组测量数据[math]\displaystyle{ x_1,\dots,x_n\,\! }[/math]，每个数据点的误差都服从标准差 standard deviation为[math]\displaystyle{ \sigma\,\! }[/math]的正态分布 Normal distribution：
- [math]\displaystyle{ x_i \sim N(\theta_i, \sigma^2) }[/math]
假设我们想要估计[math]\displaystyle{ \theta_i }[/math]，一种方法是使用最大似然法。由于每个观测值是独立的，似然分解和最大似然估计很简单：
- [math]\displaystyle{ \theta_i = x_i. }[/math]
然而，如果每个数据点相关的，例如每个[math]\displaystyle{ \theta_i }[/math]本身就是从一个潜在的分布中采样出来的出来的，那么这就破坏了独立性，并意味着要用到一个更复杂的模型，例如:
- [math]\displaystyle{ x_i \sim N(\theta_i,\sigma^2), }[/math]
- [math]\displaystyle{ \theta_i\sim N(\varphi, \tau^2), }[/math]
其中[math]\displaystyle{ \varphi\sim\text{flat} }[/math], [math]\displaystyle{ \tau\sim\text{flat} \in (0,\infty) }[/math]是不准确的先验概率。这是一个确定的模型(即，模型参数存在唯一解)，且每个[math]\displaystyle{ \theta_i }[/math]的后验分布会在最大似然估计中被移除，或者说收缩，换成了他们的均值。这种“收缩”是层次贝叶斯模型中的典型处理方法。
先验概率的约束条件
在层次结构模型中选择先验分布时需要特别注意，尤其是身处高层次的变量，比如上述例子中的变量 [math]\displaystyle{ \tau\,\! }[/math] 。常用的的先验分布，例如Jeffreys先验往往不起作用，因为后验概率不是正规化的，而最小化预期损失得出的估计通常也无效。
定义与概念
贝叶斯网络现在有好几个等价的定义，在下文的介绍中我们用到两个符号设 G = (V,E)是一个有向无环图，再设X = (Xv), v ∈ V为一组随机变量。
因子分解定义
若一组随机变量X的联合概率分布函数可以写成由几个单独的条件概率函数的乘积，则X是关于图G的贝叶斯网络:
- [math]\displaystyle{ p (x) = \prod_{v \in V} p \left(x_v \,\big|\, x_{\operatorname{pa}(v)} \right) }[/math]
其中 pa(v)是 v的父变量的集合（即，这些顶点通过一条边直接指向v）。
对于任何一组随机变量，他们各种取值组合的联合概率都可以通过使用链式规则(给定一个 X 的拓扑排序)从条件概率中计算出来，如下所示:
- [math]\displaystyle{ \operatorname P(X_1=x_1, \ldots, X_n=x_n) = \prod_{v=1}^n \operatorname P \left(X_v=x_v \mid X_{v+1}=x_{v+1}, \ldots, X_n=x_n \right) }[/math]
使用上面贝叶斯网络的定义，还可以写成这样:
- [math]\displaystyle{ \operatorname P(X_1=x_1, \ldots, X_n=x_n) = \prod_{v=1}^n \operatorname P (X_v=x_v \mid X_j=x_j \text{ for each } X_j\, \text{ that is a parent of } X_v\, ) }[/math]
这两个表达式之间的区别是：给定父变量值，所有变量与他们的非后代变量条件独立。
局部马尔可夫性
若一组随机变量X满足局部马尔可夫性 local Markov property，即每个变量在给定父变量的情况下，条件独立于所有非后代变量，则称 X是关于 G 的一个贝叶斯网络: :
- [math]\displaystyle{ X_v \perp\!\!\!\perp X_{V \,\smallsetminus\, \operatorname{de}(v)} \mid X_{\operatorname{pa}(v)} \quad\text{for all }v \in V }[/math]
其中 de(v)是节点v的后代集合，V \ de(v)是节点v的非后代集合。
这可以用类似于第一个定义的术语来表示，如
- [math]\displaystyle{ \begin{align} & \operatorname P(X_v=x_v \mid X_i=x_i \text{ for each } X_i \text{ that is not a descendant of } X_v\, ) \\[6pt] = {} & P(X_v=x_v \mid X_j=x_j \text{ for each } X_j \text{ that is a parent of } X_v\, ) \end{align} }[/math]
因为贝叶斯网络是非循环的 acyclic，所以每个节点的父节点集同时也是该节点的是非后代节点集的一个子集。
生成一个贝叶斯网络
生成一个贝叶斯网络通常从创建一个有向无环图G开始，然后使图G里的随机变量X满足的局部马尔可夫性。有时这个图同时还是一个因果图。接下来，图里的每一个随机变量的概率分布都要被估计出来。在许多情况下，特别是在变量都是离散的情况下，如果 X 的联合分布是这些单个随机变量的条件分布的乘积，那么 X 就是 G 的贝叶斯网络。.[16]
马尔科夫毯
一个节点的马尔可夫毯 Markov blanket是由其父节点、其子节点和其子节点的所有其他父节点组成的节点集。一个节点的马尔可夫毯可以使该节点独立于网络的其余部分。一个节点的马尔可夫毯中所有变量的联合分布是计算该节点分布的一个充分条件。如果网络中的每个节点再给定其马尔可夫毯的情况下，条件地独立于网络中的所有其他节点，那么 X 就是 G 的贝叶斯网络。
d-分隔
使用d-分隔的概念，贝叶斯网络的定义可以更加通用，其中 d 代表有向的。[17][18] 我们首先定义一条轨迹的d-分隔的线索，然后我们再定义两个节点间的d-分隔。
设 P 是从节点 u 到节点 v 的轨迹。轨迹是一条两个节点之间的无环、无向的(即所有边方向被忽略)的路径。如果下列任何一个条件成立，则称 P 被一组节点 Z 分隔:
- P包含一条有向链[math]\displaystyle{ u \cdots \leftarrow m \leftarrow \cdots v }[/math] or [math]\displaystyle{ u \cdots \rightarrow m \rightarrow \cdots v }[/math], 其中间节点m属于点集Z，
- P包含一个分叉[math]\displaystyle{ u \cdots \leftarrow m \rightarrow \cdots v }[/math], 其中间节点m位于“Z”中，或
- P包含一个倒叉（或称对撞），[math]\displaystyle{ u \cdots \rightarrow m \leftarrow \cdots v }[/math]，其中间节点m不在Z中，在Z中也没有m的后代节点。
如果节点 u 和 v 之间的所有轨迹都是d-分隔的，则称节点 u 和 v 被 Z 分开。如果 'u 和 v 不是d-分隔的，则称它们是 d-连通的。
我们称X是G的贝叶斯网络，当对于图G中任意两个节点 u，v满足:
- [math]\displaystyle{ X_u \perp\!\!\!\perp X_v \mid X_Z }[/math]
其中 Z 是一个将 u 和 v进行了 d-分隔的集合(马尔可夫毯其实就是将节点 v 与其他所有节点d-分隔的最小节点集合)。
因果网络
虽然贝叶斯网络经常被用来表示因果关系，但这种情形并不是必须的: 从 u 到 v 的有向边并不意味着 Xv一定是Xu导致的结果。下面这两个贝叶斯网络是等价的:
- [math]\displaystyle{ a \rightarrow b \rightarrow c \qquad \text{and} \qquad a \leftarrow b \leftarrow c }[/math]
也就是说，它们表示的条件独立要求完全相同。
当一个贝叶斯网络中的节点关系全都是因果关系时，这网络才能被称为时因果网络。因果网络还规定，如果一个节点 X再被干预的情况下变成了状态 x （写作do(X = x)） ，那么概率密度函数就会发生改变，表示成一个从 X 的父节点到 X的链接被切断的网络，并将变量X的值设置为x。利用这些规则，我们可以在真正实施外部干预前，就能从数据中预测到实施干预后会产生的影响。
推理复杂度与近似算法
1990年，Cooper在斯坦福大学研究大规模生物信息学应用时，证明了贝叶斯网络中的精确推理是NP-hard[19]（NP难问题，NP 是指非确定性多项式 non-deterministic polynomial）。这个结果促进了近似算法的研究，目的是开发出一种易于处理的近似方法来进行概率推理。1993年，Dagum 和 Luby 证明了贝叶斯网络中近似概率推理复杂度的两个令人惊讶的结果。[20]首先，他们证明了任何易于处理的确定性近似概率推断算法的绝对误差都不可能小于1/2。其次，他们证明了没有任何易于处理的随机化的近似概率推断算法可以在置信度大于1 / 2的情况下，误差小于1 / 2。
与此同时，Roth 证明了贝叶斯网络中的精确推理实际上是 #P-完全的（因此就像计数使得一个合取范式表达式 conjunctive normal form（CNF) formula为真的赋值的数量一样困难）。即使对于受限结构的贝叶斯网络来说，在对于任意ɛ > 0，2n1−ɛ 的近似推理也是 NP-hard的。[21][22]
实际上，这些复杂性结果表明，虽然贝叶斯网络在人工智能和机器学习应用中是一种强大的表示，但它们在大型实际应用中需要对拓扑结构施加约束(如朴素贝叶斯网络)或对条件概率施加约束。有界方差算法 Bounded variance algorithm [23]是贝叶斯网络中第一个被证明在保证误差的情况下还能进行快速近似概率推理的算法。这个强大的算法需要对贝叶斯网络的条件概率进行细微的限制，使其处于[0 + 1/p(n), 1 - p(n)]的区间内 ，其中p(n)是网络中节点数n的任意多项式。
软件
著名的贝叶斯网络软件包括:
- Just another Gibbs sampler (JAGS) WinBUGS的开源替代品。使用了吉布斯采样。
- OpenBUGS –WinBUGS的开源版本。
- SPSS Modeler –一个包括了贝叶斯网络实现的商业软件。
- Stan (software) – stan是一个开源软件包，用于使用No-U-Turn取样器（NUTS），[24] 是汉密尔顿蒙特卡洛方法的一个变体。
- PyMC3 – 一个python库，它实现了一个能用来表示贝叶斯网络的微型语言，以及各种采样器（包括No-U-Turn取样器）。
- WinBUGS –马尔可夫链蒙特卡罗采样器最早的实现之一，但这个软件已经不再维护。
历史
1985年，朱迪亚·珀尔 Judea Pearl创造了贝叶斯网络一词来强调:
- 输入信息通常是主观的
- 依赖贝叶斯条件作为信息更新的基础
- 因果推理和相关推理是有区别的[25]
20世纪80年代后期， Pearl的《智能系统中的概率推理 Probabilistic Reasoning in Intelligent Systems》[26]和Neapolitan的《专家系统中的概率推理 Probabilistic Reasoning in Expert Systems》[27] 总结了它们的性质，并将它们确立为一个研究领域。
另见
注释 Notes
- ↑ 1.0 1.1 1.2 Pearl, Judea (2000). Causality: Models, Reasoning, and Inference. Cambridge University Press. ISBN 978-0-521-77362-1. OCLC 42291253.
- ↑ "The Back-Door Criterion" (PDF). Retrieved 2014-09-18.
- ↑ "d-Separation without Tears" (PDF). Retrieved 2014-09-18.
- ↑ Pearl J (1994). Lopez de Mantaras R, Poole D (eds.). A Probabilistic Calculus of Actions. San Mateo CA: Morgan Kaufmann. pp. 454–462. arXiv:1302.6835. Bibcode:2013arXiv1302.6835P. ISBN 1-55860-332-8.
{{cite conference}}: Unknown parameter|booktitle=ignored (help) - ↑ "Identification of Conditional Interventional Distributions". Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence. Corvallis, OR: AUAI Press. 2006. pp. 437–444. arXiv:1206.6876.
- ↑ "The Recovery of Causal Poly-trees from Statistical Data". Proceedings, 3rd Workshop on Uncertainty in AI. Seattle, WA. 1987. pp. 222–228. arXiv:1304.2736.
- ↑ 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.
- ↑ Spirtes, Peter; Glymour, Clark N.; Scheines, Richard (1993). Causation, Prediction, and Search (1st ed.). Springer-Verlag. ISBN 978-0-387-97979-3.
- ↑ Verma T, Pearl J (1991). Bonissone P, Henrion M, Kanal LN, Lemmer JF (eds.). Equivalence and synthesis of causal models. Elsevier. pp. 255–270. ISBN 0-444-89264-8.
{{cite conference}}: Unknown parameter|booktitle=ignored (help) - ↑ Friedman, Nir; Geiger, Dan; Goldszmidt, Moises (November 1997). "Bayesian Network Classifiers". Machine Learning. 29 (2–3): 131–163. doi:10.1023/A:1007465528199.
{{cite journal}}: Unknown parameter|name-list-format=ignored (help) - ↑ 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.
- ↑ Cussens, James (2011). "Bayesian network learning with cutting planes" (PDF). Proceedings of the 27th Conference Annual Conference on Uncertainty in Artificial Intelligence: 153–160. arXiv:1202.3713. Bibcode:2012arXiv1202.3713C.
{{cite journal}}: Unknown parameter|name-list-format=ignored (help) - ↑ "Learning Bayesian Networks with Thousands of Variables". NIPS-15: Advances in Neural Information Processing Systems. 28. 2015. pp. 1855–1863. https://papers.nips.cc/paper/5803-learning-bayesian-networks-with-thousands-of-variables.
- ↑ 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.
- ↑ M. Scanagatta, G. Corani, C. P. de Campos, and M. Zaffalon. Learning Treewidth-Bounded Bayesian Networks with Thousands of Variables. In NIPS-16: Advances in Neural Information Processing Systems 29, 2016.
- ↑ Neapolitan, Richard E. (2004). Learning Bayesian networks. Prentice Hall. ISBN 978-0-13-012534-7.
- ↑ Geiger, Dan; Verma, Thomas; Pearl, Judea (1990). "Identifying independence in Bayesian Networks" (PDF). Networks. 20: 507–534. doi:10.1177/089443939100900106.
{{cite journal}}: Unknown parameter|name-list-format=ignored (help) - ↑ Richard Scheines, D-separation
- ↑ Cooper, Gregory F. (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.
- ↑ 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.
- ↑ D. Roth, On the hardness of approximate reasoning, IJCAI (1993)
- ↑ D. Roth, On the hardness of approximate reasoning, Artificial Intelligence (1996)
- ↑ Dagum P, Luby M (1997). "An optimal approximation algorithm for Bayesian inference". Artificial Intelligence. 93 (1–2): 1–27. CiteSeerX 10.1.1.36.7946. doi:10.1016/s0004-3702(97)00013-1. Archived from the original on 2017-07-06. Retrieved 2015-12-19.
- ↑ Hoffman, Matthew D.; Gelman, Andrew (2011). "The No-U-Turn Sampler: Adaptively Setting Path Lengths in Hamiltonian Monte Carlo". arXiv:1111.4246. Bibcode:2011arXiv1111.4246H.
- ↑ 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.
- ↑ Probabilistic Reasoning in Intelligent Systems. San Francisco CA: Morgan Kaufmann. 1988-09-15. pp. 1988. ISBN 978-1558604797.
- ↑ Neapolitan, Richard E. (1989). Probabilistic reasoning in expert systems: theory and algorithms. Wiley. ISBN 978-0-471-61840-9.
参考文献 References
- Ben Gal, Irad (2007). "Bayesian Networks" (PDF). In Ruggeri, Fabrizio; Kennett, Ron S.; Faltin, Frederick W (eds.). Encyclopedia of Statistics in Quality and Reliability. John Wiley & Sons. doi:10.1002/9780470061572.eqr089. ISBN 978-0-470-01861-3.
{{cite encyclopedia}}: Unknown parameter|name-list-format=ignored (help)
- Bertsch McGrayne, Sharon. The Theory That Would not Die. New Haven: Yale University Press. https://archive.org/details/theorythatwouldn0000mcgr.
- Borgelt, Christian; Kruse, Rudolf (March 2002). Graphical Models: Methods for Data Analysis and Mining. Chichester, UK: Wiley. ISBN 978-0-470-84337-6. http://fuzzy.cs.uni-magdeburg.de/books/gm/.
- Borsuk, Mark Edward (2008). "Ecological informatics: Bayesian networks". In Jørgensen, Sven Erik; Fath, Brian (eds.). Encyclopedia of Ecology. Elsevier. ISBN 978-0-444-52033-3.
{{cite encyclopedia}}: Unknown parameter|name-list-format=ignored (help)
- Castillo, Enrique; Gutiérrez, José Manuel; Hadi, Ali S. (1997). "Learning Bayesian Networks". Expert Systems and Probabilistic Network Models. Monographs in computer science. New York: Springer-Verlag. pp. 481–528. ISBN 978-0-387-94858-4.
- Comley, Joshua W.; Dowe, David L. (June 2003). "General Bayesian networks and asymmetric languages". Proceedings of the 2nd Hawaii International Conference on Statistics and Related Fields.
{{cite journal}}: Unknown parameter|name-list-format=ignored (help)
- Comley, Joshua W.; Dowe, David L. (2005). "Minimum Message Length and Generalized Bayesian Nets with Asymmetric Languages". In Grünwald, Peter D.; Myung, In Jae; Pitt, Mark A.. Advances in Minimum Description Length: Theory and Applications. Neural information processing series. Cambridge, Massachusetts: Bradford Books (MIT Press). April 2005. pp. 265–294. ISBN 978-0-262-07262-5. http://www.csse.monash.edu.au/~dld/David.Dowe.publications.html#ComleyDowe2005. (This paper puts decision trees in internal nodes of Bayes networks using Minimum Message Length (MML).
- Darwiche, Adnan (2009). Modeling and Reasoning with Bayesian Networks. Cambridge University Press. ISBN 978-0521884389. http://www.cambridge.org/9780521884389.
- Dowe, David L. (2011-05-31). "Hybrid Bayesian network graphical models, statistical consistency, invariance and uniqueness" (in en). Philosophy of Statistics. Elsevier. ISBN 9780080930961. http://www.csse.monash.edu.au/~dld/Publications/2010/Dowe2010_MML_HandbookPhilSci_Vol7_HandbookPhilStat_MML+hybridBayesianNetworkGraphicalModels+StatisticalConsistency+InvarianceAndUniqueness_pp901-982.pdf.
- Fenton, Norman; Neil, Martin E. (November 2007). "Managing Risk in the Modern World: Applications of Bayesian Networks". A Knowledge Transfer Report from the London Mathematical Society and the Knowledge Transfer Network for Industrial Mathematics.. London (England): London Mathematical Society. http://www.agenarisk.com/resources/apps_bayesian_networks.pdf.
- Fenton, Norman; Neil, Martin E. (July 23, 2004). "Combining evidence in risk analysis using Bayesian Networks" (PDF). Safety Critical Systems Club Newsletter. Vol. 13, no. 4. Newcastle upon Tyne, England. pp. 8–13. Archived from the original (PDF) on 2007-09-27.
{{cite news}}: Unknown parameter|name-list-format=ignored (help)
- Gelman, Andrew; Carlin, John B; Stern, Hal S; Rubin, Donald B (2003). "Part II: Fundamentals of Bayesian Data Analysis: Ch.5 Hierarchical models". Bayesian Data Analysis. CRC Press. pp. 120–. ISBN 978-1-58488-388-3.
- Heckerman, David (March 1, 1995). "Tutorial on Learning with Bayesian Networks". In Jordan, Michael Irwin. Learning in Graphical Models. Adaptive Computation and Machine Learning. Cambridge, Massachusetts: MIT Press. 1998. pp. 301–354. ISBN 978-0-262-60032-3. http://research.microsoft.com/research/pubs/view.aspx?msr_tr_id=MSR-TR-95-06.
- 也显示为Heckerman, David (March 1997). "Bayesian Networks for Data Mining". Data Mining and Knowledge Discovery. 1 (1): 79–119. doi:10.1023/A:1009730122752.
- Jensen, Finn V; Nielsen, Thomas D. (June 6, 2007). Bayesian Networks and Decision Graphs. Information Science and Statistics series (2nd ed.). New York: Springer-Verlag. ISBN 978-0-387-68281-5.
- Karimi, Kamran; Hamilton, Howard J. (2000). "Finding temporal relations: Causal bayesian networks vs. C4. 5" (PDF). Twelfth International Symposium on Methodologies for Intelligent Systems.
{{cite journal}}: Unknown parameter|name-list-format=ignored (help)
- Korb, Kevin B.; Nicholson, Ann E. (December 2010). Bayesian Artificial Intelligence. CRC Computer Science & Data Analysis (2nd ed.). Chapman & Hall (CRC Press). doi:10.1007/s10044-004-0214-5. ISBN 978-1-58488-387-6.
- Lunn D, Spiegelhalter D, Thomas A, Best N (November 2009). "The BUGS project: Evolution, critique and future directions". Statistics in Medicine. 28 (25): 3049–67. doi:10.1002/sim.3680. PMID 19630097.
- Neil M, Fenton N, Tailor M (August 2005). Greenberg, Michael R. (ed.). "Using Bayesian networks to model expected and unexpected operational losses" (PDF). Risk Analysis. 25 (4): 963–72. doi:10.1111/j.1539-6924.2005.00641.x. PMID 16268944.
- Pearl, Judea (September 1986). "Fusion, propagation, and structuring in belief networks". Artificial Intelligence. 29 (3): 241–288. doi:10.1016/0004-3702(86)90072-X.
{{cite journal}}: Unknown parameter|name-list-format=ignored (help)
- Pearl, Judea (1988). Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Representation and Reasoning Series (2nd printing ed.). San Francisco, California: Morgan Kaufmann. ISBN 978-0-934613-73-6.
- Pearl, Judea; Russell, Stuart (November 2002). "Bayesian Networks". In Arbib, Michael A.. Handbook of Brain Theory and Neural Networks. Cambridge, Massachusetts: Bradford Books (MIT Press). pp. 157–160. ISBN 978-0-262-01197-6.
- Zhang, Nevin Lianwen; Poole, David (May 1994). "A simple approach to Bayesian network computations" (PDF). Proceedings of the Tenth Biennial Canadian Artificial Intelligence Conference (AI-94).: 171–178.
{{cite journal}}: Unknown parameter|name-list-format=ignored (help) This paper presents variable elimination for belief networks.
延伸阅读
- Conrady, Stefan; Jouffe, Lionel (2015-07-01). Bayesian Networks and BayesiaLab – A practical introduction for researchers. Franklin, Tennessee: Bayesian USA. ISBN 978-0-9965333-0-0.
- Charniak, Eugene (Winter 1991). "Bayesian networks without tears" (PDF). AI Magazine.
{{cite web}}: Unknown parameter|name-list-format=ignored (help)
- Kruse, Rudolf; Borgelt, Christian; Klawonn, Frank; Moewes, Christian; Steinbrecher, Matthias; Held, Pascal (2013). Computational Intelligence A Methodological Introduction. London: Springer-Verlag. ISBN 978-1-4471-5012-1.
- Borgelt, Christian; Steinbrecher, Matthias; Kruse, Rudolf (2009). Graphical Models – Representations for Learning, Reasoning and Data Mining (Second ed.). Chichester: Wiley. ISBN 978-0-470-74956-2.
外部链接
- A hierarchical Bayes Model for handling sample heterogeneity in classification problems, provides a classification model taking into consideration the uncertainty associated with measuring replicate samples.
- Hierarchical Naive Bayes Model for handling sample uncertainty, shows how to perform classification and learning with continuous and discrete variables with replicated measurements.
编者推荐
课程推荐
因果科学读书会第一季
本次读书会由集智俱乐部社区成员龚鹤扬、高亦斌和郭瑞东等人共同发起，从2020年8月26日到2021年1月2日，共有崔鹏、周晓华等老师同学在内的32位讲者，分享了32个不同的主题，B站人气累积10万+，来自海内外不同高校或者企业的一线科研工作者273名，因果读书会借助集体智慧，在100多天的时间里，撬动了数十万人次的共同参与，形成了一场因果科学风暴！
因果科学与Causal AI读书会第二季
因果科学读书会的第二季将会从基础的部分介绍图模型，以及更多跟图模型拓展相关，解释因果性的文章。读书会期间将会精读三本因果科学方向的优秀书籍，并共同完成书籍中的思考题。
其他参考资料
文章总结
因果科学入门读什么书？Y. Bengio博士候选人的研读路径推荐
历时3个月，全球32位讲者，共同讲述因果科学与Causal AI的全景框架！
相关路径
- 因果科学与Casual AI读书会必读参考文献列表，这个是根据读书会中解读的论文，做的一个分类和筛选，方便大家梳理整个框架和内容。
- 因果推断方法概述,这个路径对因果在哲学方面的探讨，以及因果在机器学习方面应用的分析。
- 因果科学和 Causal AI入门路径，这条路径解释了因果科学是什么以及它的发展脉络。此路径将分为三个部分进行展开，第一部分是因果科学的基本定义及其哲学基础，第二部分是统计领域中的因果推断，第三个部分是机器学习中的因果（Causal AI）。
- 复杂网络动力学系统重构文献，这个路径是张江老师梳理了网络动力学重构问题，描述了动力学建模的常用方法和模型，并介绍了一些经典且重要的论文，这也是复杂系统自动建模读书会的主要论文来源，所以大部分都有解读视频。
- 因果纠缠集智年会——因果推荐系统分论坛关于因果推荐系统的参考文献和主要嘉宾介绍，来源是集智俱乐部的因果纠缠年会。
本中文词条由水流心不竞翻译，Ricky审校，薄荷欢迎在讨论页面留言。
本词条内容源自公开资料，遵守 CC3.0协议。