Maximum likelihood bounded tree-width Markov networks

被引：28

作者：

Srebro, N ^{[1
]}

机构：

[1] MIT, Dept Elect Engn & Comp Sci, Cambridge, MA 02139 USA

来源：

ARTIFICIAL INTELLIGENCE | 2003年 / 143卷 / 01期

关键词：

Markov networks; Markov random fields; undirected graphical models; entropy decomposition; hyper-trees; tree-width; hardness;

D O I：

10.1016/S0004-3702(02)00360-0

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

We study the problem of projecting a distribution onto (or finding a maximum likelihood distribution among) Markov networks of bounded tree-width. By casting it as the combinatorial optimization problem of finding a maximum weight hypertree, we prove that it is NP-hard to solve exactly and provide an approximation algorithm with a provable performance guarantee. (C) 2002 Elsevier Science B.V All rights reserved.

引用

页码：123 / 138

页数：16

共 16 条

[1]

Alon N., 1991, The Probabilistic Method

[2] Information geometry on hierarchy of probability distributions [J].

Amari, S .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2001, 47 (05) :1701-1711

[3]

[Anonymous], 1997, PROBABILISTIC REASON

[4]

BESAG J, 1974, P ROY STAT SOC SER B, P192

[5] A linear-time ie algorithm for finding three-decompositions of small treewidth [J].

Bodlaender, HL .

SIAM JOURNAL ON COMPUTING, 1996, 25 (06) :1305-1317

[6]

Chickering D.M., 1996, Learning Bayesian Networks is NPComplete, V112, P121, DOI DOI 10.1007/978-1-4612-2404-4_12

[7] APPROXIMATING DISCRETE PROBABILITY DISTRIBUTIONS WITH DEPENDENCE TREES [J].

CHOW, CK ;

LIU, CN .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1968, 14 (03) :462-+

[8]

Cover T. M., 2005, ELEM INF THEORY, DOI 10.1002/047174882X

[9]

Dasgupta S, 1999, UNCERTAINTY IN ARTIFICIAL INTELLIGENCE, PROCEEDINGS, P134

[10]

Hoffgen K.-U., 1993, Proceeding of the Sixth Annual ACM Conference on Computational Learning Theory, P77, DOI 10.1145/168304.168314

← 1 2 →