基于概率图的最小独立图算法研究

摘要

作为概率论与图论相结合的产物，图模型提供了将先验知识结合到数据发掘过程中的方法，并可将问题域中的概率依赖关系定性地表示为拓扑结构。统计学、模式识别、机器学习、信息论等领域中许多经典的多变量概率模型都可看作是图模型的特例。 到目前为止，大多数的论文研究了不同解释下的独立性，也有一部分研究了分割不同解释下的链图模型。但是目前没有给出不同解释下链图最小独立图的算法。本文的主要贡献是给出概率图模型不同模型在给定一个变量次序的情况下的最小独立图算法。 为了研究有向图和无向图模型不能解决的一些特定的条件独立性结构，将有向图模型与无向图模型相结合，建立一种既有有向边又有无向边的链图模型。在己知贝叶斯网上的最小独立图算法的基础上，利用图模型独立性关系，分别研究了MVR解释、LWF解释和AMP解释三种表示下链图模型的有效迹算法和独立图算法，最终得到不同定义下图模型的最小独立图。 链图的条件独立性随给定变量次序的变化而变化。研究了有向图上的最小独立性并将其扩充到链图上，给定链图的一个变量次序，从而得到与给定目标次序一致的最小独立图，并给出了得到该最小独立图的算法。介绍了算法的应用并讨论了其复杂度和研究前景。

目录

第一个书签之前