有向图模型

结构化概率模型使用图（在图论中 ‘‘结点’’ 是通过 ‘‘边’’ 来连接的）来表示随机变量之间的相互作用。每一个结点代表一个随机变量。每一条边代表一个直接相互作用。这些直接相互作用隐含着其他的间接相互作用，但是只有直接的相互作用会被显式地建模。有向图模型（directed graphical model）是一种结构化概率模型，也被称为 信念网络（belief network）或者 贝叶斯网络（Bayesian network）(Pearl, 1985)。之所以命名为有向图模型是因为所有的边都是有方向的，即从一个结点指向另一个结点。这个方向可以通过画一个箭头来表示。箭头所指的方向表示了这个随机变量的概率分布是由其他变量的概率分布所定义的。画一个从结点 a 到结点 b 的箭头表示了我们用一个条件分布来定义 b，而 a 是作为这个条件分布符号右边的一个变量。换句话说，b 的概率分布依赖于 a 的取值。

正式地说，变量 x 的有向概率模型是通过有向无环图 G（每个结点都是模型中的随机变量）和一系列 局部条件概率分布（local conditional probability distribution）p(xi| PaG(xi)) 来定义的，其中 PaG(xi) 表示结点 xi的所有父结点。x 的概率分布可以表示为

（1）

图1

说明: 描述接力赛例子的有向图模型。Alice 的完成时间 t0影响了 Bob 的完成时间 t1，因为Bob 只能在 Alice 完成比赛后才开始。类似的，Carol 也只会在 Bob 完成之后才开始，所以 Bob的完成时间 t1直接影响了 Carol 的完成时间 t2。

在接力赛的例子中，参考图 1，这意味着概率分布可以被表示为

（2）

这是我们看到的第一个结构化概率模型的实际例子。我们能够检查这样建模的计算开销，为了验证相比于非结构化建模，结构化建模为什么有那么多的优势。假设我们采用从第 0 分钟到第 10 分钟每 6 秒一块的方式离散化地表示时间。这使得 t0，t1和 t2都是一个有 100 个取值可能的离散变量。如果我们尝试着用一个表来表示 p(t0, t1, t2)，那么我们需要存储 999, 999 个值（100 个 t0的可能取值 × 100个 t1的可能取值 × 100 个 t2的可能取值减去 1，由于存在所有的概率之和为 1 的限制，所以其中有 1 个值的存储是多余的）。反之，如果我们用一个表来记录每一种条件概率分布，那么表中记录 t0的分布需要存储 99 个值，给定 t0情况下 t1的分布需要存储 9900 个值，给定 t1情况下 t2的分布也需要存储 9900 个值。加起来总共需要存储 19, 899 个值。这意味着使用有向图模型将参数的个数减少了超过 50 倍！

通常意义上说，对每个变量都能取 k 个值的 n 个变量建模，基于建表的方法需要的复杂度是 O(kn)，就像我们之前观察到的一样。现在假设我们用一个有向图模型来对这些变量建模。如果 m 代表图模型的单个条件概率分布中最大的变量数目（在条件符号的左右皆可），那么对这个有向模型建表的复杂度大致为 O(km)。只要我们在设计模型时使其满足 m ≪ n，那么复杂度就会被大大地减小。换一句话说，只要图中的每个变量都只有少量的父结点，那么这个分布就可以用较少的参数来表示。图结构上的一些限制条件，比如说要求这个图为一棵树，也可以保证一些操作（例如求一小部分变量的边缘或者条件分布）更加地高效。

决定哪些信息需要被包含在图中而哪些不需要是很重要的。如果变量之间可以被假设为是条件独立的，那么这个图可以包含这种简化假设。当然也存在其他类型的简化图模型的假设。例如，我们可以假设无论 Alice 的表现如何，Bob 总是跑得一样快（实际上，Alice 的表现很大概率会影响 Bob 的表现，这取决于 Bob 的性格，如果在之前的比赛中 Alice 跑得特别快，这有可能鼓励 Bob 更加努力并取得更好的成绩，当然这也有可能使得 Bob 过分自信或者变得懒惰）。那么 Alice 对 Bob 的唯一影响就是在计算 Bob 的完成时间时需要加上 Alice 的时间。这个假设使得我们所需要的参数量从 O(k2) 降到了 O(k)。然而，值得注意的是在这个假设下 t0和 t1仍然是直接相关的，因为 t1表示的是 Bob 完成时的时间，并不是他跑的总时间。这也意味着图中会有一个从 t0指向 t1的箭头。“Bob 的个人跑步时间相对于其他因素是独立的’’ 这个假设无法在 t0，t1，t2的图中被表示出来。反之，我们只能将这个关系表示在条件分布的定义中。这个条件分布不再是一个大小为 k × k − 1 的分别对应着t0，t1的表格，而是一个包含了 k − 1 个参数的略微复杂的公式。有向图模型的语法并不能对我们如何定义条件分布作出任何限制。它只定义了哪些变量可以作为其中的参数。