我们现在寻找无向图的一个分解规则,对应于上述条件独立性检测。与之前一样,这涉及到将联合概率分布表示为在图的局部范围内的变量集合上定义的函数的乘积。于是,我们需要给出这种情形下,局部性的一个合适定义。

如果我们考虑两个结点,它们不存在链接,那么给定图中的所有其他结点,这两个结点一定是条件独立的。这是因为两个结点之间没有直接的路径,并且所有其他的路径都通过了观测的结点,因此这些路径都是被阻隔的。这个条件独立性可以表示为

其中表示所有变量去掉的集合。于是,联合概率分布的分解一定要让不出现在同一个因子中,从而让属于这个图的所有可能的概率分布都满足条件独立性质。

这将我们引向了一个图形的概念,团块(clique)。它被定义为图中结点的一个子集,使得在这个子集中的每对结点之间都存在链接。换句话说,团块中的结点集合是全连接的。此外,一个最大团块(maximal clique)是具有下面性质的团块:不可能将图中的任何一个其他的结点包含到这个团块中而不破坏团块的性质。图8.29说明了四个变量的无向图中的这些概念。

这个图中有五个具有两个结点的团块,即,还有两个最大团块。集合不是一个团块,因为在没有链接。

于是,我们可以将联合概率分布分解的因子定义为团块中变量的函数。事实上,我们可以考虑最大团块的函数而不失一般性,因为其他团块一定是最大团块的子集。因此,如果是一个最大团块,并我们在这个团块上定义了任意一个函数,那么定义在这些变量的一个子集上的其他因子都是冗余的。

让我们将团块记作,将团块中的变量的集合记作。这样,联合概率分布可以写成图的最大团块的势函数(potential function)的乘积的形式

这里,有时被称为划分函数(partition function),是一个归一化常数,等于

它确保了式(8.39)给出的概率分布被正确地归一化。通过只考虑满足的势函数,我们确保了。在式(8.40)中,我们假设由离散变量组成,但是这个框架也同样适用于连续变量,或两者结合的情形。此时,求和式被替换成恰当的求和与积分的组合。

注意,我们不把势函数的选择限制为具有具体的概率含义(例如边缘概率分布或者条件概率分布)的函数。这与有向图的情形相反。在有向图的情形中,每个因子表示对应变量以它的父结点为条件的条件概率分布。然而,在特殊情况下,例如无向图是通过有向图构建的情况,势 函数可能确实有这样的意义,正如我们将要看到的那样。

势函数的这一通用性产生的一个结果是它们的乘积通常没有被正确地标准化。于是,我们必须引入一个显式的标准化因子,由公式(8.40)给出。回忆一下,对于有向图的情形,由于分解后的每个作为因子的条件概率分布都被归一化了,因此联合概率分布会自动地被标准化。

标准化常数的存在是无向图的一个主要的缺点。如果我们的模型中有个离散结点,每个结点有个状态,那么标准化项的计算涉及到对个状态求和,因此(在最坏的情况下),计算量是模型大小的指数形式。对于参数学习来说,划分函数是必要的,因为划分函数是控制势函数的任意参数的函数。但是,对于局部条件概率分布的计算,划分函数是不需要的,因为条件概率是两个边缘概率的比值,当计算这个比值时,划分函数在分子和分母之间被消去了。类似地,对于计算局部边缘概率,我们可以计算未标准化的联合概率分布,然后在计算的最后阶段显式的标准化边缘概率。假设边缘概率只涉及到少量的变量,那么标准化系数的计算是可行的。

目前为止,我们基于简单的图划分,讨论了条件独立性的概念,并且我们提出了对联合概率分布的分解,来尝试对应条件独立的图结构。然而,我们并没有将条件独立性和无向图的分解形式化地联系起来。为了形式化地描述,我们需要把注意力限制于那些严格为正的势函数,即对于任意的的选择都永远不等于零也不取负值的势函数。给定这个限制,我们可以给出分解和条件独立之间的精确关系。

为了给出精确的关系,我们再次回到作为滤波器的图模型的概念中,对应于图8.25。考虑定义在固定变量集合上的所有可能的概率分布,其中这些变量对应于一个具体的无向图的节点。我们可以将定义为满足下面条件的概率分布的集合:从使用图划分的方法得到的图中可以读出条件独立性质,这个概率分布应该与这些条件独立性质相容。类似地,我们可以将定义为满足下面条件的概率分布的集合:可以表示为关于图中最大团块的分解的形式的概率分布,其中分解方式由式(8.39)给出。Hammersley-Clifford定理(Clifford, 1990)表明,集合是完全相同的。

由于我们的势函数被限制为严格大于零,因此将势函数表示为指数的形式更方便,即

其中被称为能量函数(energy function),指数表示被称为玻尔兹曼分布(Boltzmann distribution)。联合概率分布被定义为势函数的乘积,因此总的能量可以通过将每个最大团块的能量相加的方法得到。

与有向图的联合分布的因子不同,无向图中的势函数没有一个具体的概率意义。虽然这使得选择势函数具有更大的灵活性,因为没有归一化的限制,但是这确实产生了一个问题,即对于一个具体的应用来说,如何选择势函数。可以这样做:将势函数看成一种度量,它表示了局部变量的哪种配置优于其他的配置。具有相对高概率的全局配置对于各个团块的势函数的影响进行了很好的平衡。我们现在通过一个具体的例子来说明无向图的用处。

results matching ""

    No results matching ""