Learning equivalence classes of Bayesian-network structures
Learning equivalence classes of Bayesian-network structures
复制标题
DOI：
10.1162/153244302760200696
复制
发表时间：
2002-06-01
影响因子：
6
通讯作者：
Chickering, DM
中科院分区：
文献类型：
--
作者：
Chickering, DM
如果可以用其中一种结构表示的分布集合与可以用另一种结构表示的分布集合相同，则称两个贝叶斯网络结构是等价的。许多用于从数据中学习贝叶斯网络结构的评分标准是分数等价的；也就是说，这些标准不区分等价的网络。在本文中，我们考虑将得分等价准则与启发式搜索算法相结合来执行模型选择或模型平均。我们认为，在网络结构的等价类中搜索通常是合适的，而不是在单个贝叶斯网络结构中搜索更常见的方法。我们描述了等价结构类的一种方便的图形表示，并引入了一组算子，这些算子可以通过搜索算法应用于该表示，以便在等价类之间移动。我们证明了我们的等价类算子可以局部评分，从而分享了为单个结构定义的传统算子的计算效率。我们的实验表明，使用我们的表示的贪婪模型选择算法在不增加任何额外时间开销的情况下产生比传统方法略高的评分结构，并且我们认为更复杂的搜索算法可能会受益更多。
Two Bayesian-network structures are said to be equivalent if the set of distributions that can be represented with one of those structures is identical to the set of distributions that can be represented with the other. Many scoring criteria that are used to learn Bayesian-network structures from data are score equivalent; that is, these criteria do not distinguish among networks that are equivalent. In this paper, we consider using a score equivalent criterion in conjunction with a heuristic search algorithm to perform model selection or model averaging. We argue that it is often appropriate to search among equivalence classes of network structures as opposed to the more common approach of searching among individual Bayesian-network structures. We describe a convenient graphical representation for an equivalence class of structures, and introduce a set of operators that can be applied to that representation by a search algorithm to move among equivalence classes. We show that our equivalence-class operators can be scored locally, and thus share the computational efficiency of traditional operators defined for individual structures. We show experimentally that a greedy model-selection algorithm using our representation yields slightly higher-scoring structures than the traditional approach without any additional time overhead, and we argue that more sophisticated search algorithms are likely to benefit much more.