Learning discrete decomposable graphical models via constraint optimization
Learning discrete decomposable graphical models via constraint optimization
复制标题
通过约束优化学习离散可分解图模型
作者：
T. Janhunen;M. Gebser;J. Rintanen;Henrik J. Nyman;J. Pensar;J. Corander
统计模型学习问题传统上是使用启发式贪婪优化或随机模拟（例如Markov Chain Monte Carlo或模拟退火）解决的。最近，人们对使用组合搜索方法（包括基于计算逻辑的方法）引起了人们的兴趣。这些方法中的一些特别有吸引力，因为它们也可以成功地证明解决方案的全球最优性，而随机算法仅保证在极限上保证最佳性。在这里，我们改进并概括了一种最近引入的基于约束的方法，用于学习无向图形模型。新方法将完美的消除顺序与解决方案修剪的各种策略相结合，并在时间和记忆复杂性方面具有巨大的改进。我们还表明，该方法能够有效地处理更一般的模型，称为分层/标记的图形模型，这些模型具有天文学更大的模型空间。
Statistical model learning problems are traditionally solved using either heuristic greedy optimization or stochastic simulation, such as Markov chain Monte Carlo or simulated annealing. Recently, there has been an increasing interest in the use of combinatorial search methods, including those based on computational logic. Some of these methods are particularly attractive since they can also be successful in proving the global optimality of solutions, in contrast to stochastic algorithms that only guarantee optimality at the limit. Here we improve and generalize a recently introduced constraint-based method for learning undirected graphical models. The new method combines perfect elimination orderings with various strategies for solution pruning and offers a dramatic improvement both in terms of time and memory complexity. We also show that the method is capable of efficiently handling a more general class of models, called stratified/labeled graphical models, which have an astronomically larger model space.