有向无环图

有向无环图是图论的重要概念，我们将首先介绍图的概念和定义，随后介绍有向图，再逐渐引至有向无环图（DAG）。值得一提的是，当DAG用于指代模型时一般指向贝叶斯网络。

一个图G是顶点V的有限集合以及边E的多重集（每个连接两个不一定不同的顶点），在这里我们表示为G=V ∪ E，即V和E的并集，而没有写作其一般表示G=( V, E)。 图G=V ∪ E的大小由|E|表示的边缘（edge）确定， G的顺序是用| V |表示的顶点数。 下图给出了一些简单的示例：

而有向图（diagraph）D是一组顶点V，连同弧（arc）的多重集A表示的，写作D=V ∪ A。

弧被表示为有序的顶点对，例如，a=(x,y)，其中x是a的尾部，y是a的头部，而a则从尾部x到头部y。 A_v^+， A_v^- 分别表示从v出发或链接到v的集合。 因此我们可以用A_v = A_v^v ∪ A_v^- 来表示从v出发或链接到v的弧的集合。顶点v∈V的入边数量（in-degree）id(v)= d(v)^- 是 以v为头的弧。 类似地，对于任何v∈V，出边数量（out-degree） od(v)= d(v)^+是以v作为尾部的弧的数量。

对于每一个有向图，以下性质明显成立：

下图给出了一个具有弧a=(x,y)，b=(y,x)，...，的有向图示例。

接下来我们需要引入环的概念。

我们定义开放路径（open trial）为一条没有顶点遍历多次（所有顶点都不相同）的路径。 在路径P（v_0，v_n）中，顶点v_1, ... , v_{n-1}被称为P（v_0，v_n）的内部顶点。 如果除了v_0 = v_n外，其他所有的顶点都不相同，并且它包含至少一个边，则我们称其为一个环，也即是闭合路径（closed trail）的定义。

下图给出了一些简单示例：

而一个图G或有向图D如果不包含（循）环（cycle），则称它为无环图（acyclic）。 一个无环图G被称为森林（forest），而只有一个组成部分的森林被称为树。

因此，我们可以很清晰的看到有向无环图（DAG）的定义为：有向无环图是没有环的有向图。

[图片及描述来源：Fleischner, H. (2016). Algorithms in Graph Theory.  URL：https://www.dbai.tuwien.ac.at/staff/kronegger/misc/AlgorithmsInGraphTheory_Script.pdf]

基本的图模型可以大致分为两个类别：贝叶斯网络 (Bayesian Network) 和马尔可夫随机场 (Markov Random Field)。贝叶斯网络是一种有向无环图模型，它采用有向无环图 (Directed Acyclic Graph) 来表达因果关系，马尔可夫随机场则采用无向图 (Undirected Graph) 来表达变量间的相互作用。这种结构上的区别导致了它们在建模和推断方面的一系列微妙的差异。

贝叶斯网络的一个典型案例是所谓的「学生网络（student network）」，它看起来像是这样：

这个图描述了某个学生注册某个大学课程的设定。该图中有 5 个随机变量：

• 课程的难度（Difficulty）：可取两个值，0 表示低难度，1 表示高难度
• 学生的智力水平（Intelligence）：可取两个值，0 表示不聪明，1 表示聪明
• 学生的评级（Grade）：可取三个值，1 表示差，2 表示中，3 表示优
• 学生的 SAT 成绩（SAT）：可取两个值，0 表示低分，1 表示高分
• 在完成该课程后学生从教授那里所得到的推荐信的质量（Letter）：可取两个值，0 表示推荐信不好，1 表示推荐信很好

该图中的边编码了这些变量之间的依赖关系。

• 学生的 Grade 取决于课程的 Difficulty 和学生的 Intelligence；
• 而 Grade 又反过来决定了学生能否从教授那里得到一份好的 Letter；
• 另外，学生的 Intelligence 除了会影响他们的 Grade，还会影响他们的 SAT 分数。

注意其中箭头的方向表示了因果关系——Intelligence 会影响 SAT 分数，但 SAT 不会影响 Intelligence。

Difficulty 和 Intelligence 的 条件概率分布（CPD） 非常简单，因为这些变量并不依赖于其它任何变量。基本而言，这两个表格编码了这两个变量取值为 0 和 1 的概率。你可能已经注意到，每个表格中的值的总和都必须为 1。

接下来看看 SAT 的 CPD。其每一行都对应于其父节点（Intelligence）可以取的值，每一列对应于 SAT 可以取的值。每个单元格都有条件概率 p(SAT=s|Intelligence=i)，也就是说：给定 Intelligence 的值为 i，则其为 SAT 的值为 s 的概率。

比如，我们可以看到 p(SAT=s¹|Intelligence=i¹) 是 0.8。也就是说，如果该学生的智力水平高，那么他的 SAT 分数也很高的概率是 0.8。而 p(SAT=s⁰|Intelligence=i¹) 则表示如果该学生的智力水平高，那么 SAT 分数很低的概率是 0.2。

注意，每一行中的值的总和为 1。这是当然而然的，因为当 Intelligence=i¹ 时，SAT 只能是 s⁰ 和 s¹ 中的一个，所以两个概率之和必定为 1。类似地，Letter 的 CPD 编码了条件概率 p(Letter=l|Grade=g)。因为 Grade 可以取 3 个值，所以这个表格有 3 行。

有了上面的知识，Grade 的 CPD 就很容易理解了。因为它有两个父节点，所以它的条件概率是这种形式：p(Grade=g|Difficulty=d,SAT=s)，即当 Difficulty 为 d 且 SAT 为 s 时 Grade 为 g 的概率。这个表格的每一行都对应于一对 Difficulty 和 Intelligence 值。同样，每一行的值的总和为 1。

[图片及描述来源：读懂概率图：你需要从基本概念和参数估计开始| 机器之心 ]

2. 发展历史

描述

由于DAG能够很好的表示复杂多变量系统，基于其的模型一直很受欢迎，特别是贝叶斯网络。这一由Pearl在1985年针对主观的输入信息依靠贝叶斯条件作为更新信息的基础而提出来的模型简洁优雅，但由于其模拟的独立性仅在某些情况下存在（条件独立），Craig Boutilier和Nir Friedman等学者提出了一种类似于（和基于）有向分离（D-separation）的算法，用于确定这种独立性在给定网络中何时存在。1997年David Maxwell Chickering等学者提出对贝叶斯网络进行改进，允许依赖关系具有局部结构，使得节点不需要明确依赖其父项的所有值组合。这些研究推动了Nir Friedman等学者专注于贝叶斯网络中特定于上下文的独立性（Context-specific independencies），其可以明显降低网络模型的参数维度并导致对依赖结构（dependence structure）的更具表达性的解释。2006年Tsamardinos等人将本地学习（local learning），基于约束和搜索与分数技术（ constraint-based， search-and-score techniques）与贝叶斯网络结合，提出了MMHC（Max-Min Hill-Climbing）算法。

主要事件

3. 发展分析

瓶颈

有向图只能描述变量间的因果关系，不能用来模拟变量间的相关关系；此外，DAG模型是离散的，若节点过多，即事件种类太多，会使计算代价过高。

未来发展方向

DAG模型的一个发展方向是非参数化，非参数化方法是一种更为灵活的建模方式——非参数化模型的大小（比如节点的数量）可以随着数据的变化而变化。而非参数化模型又可以被用于特征学习，如基于Hierarchical Beta Process来学习不定数量的特征。

Contributor: Yuanyuan Li