Maximum likelihood bounded tree-width Markov networks (Q1853683)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Maximum likelihood bounded tree-width Markov networks |
scientific article |
Statements
Maximum likelihood bounded tree-width Markov networks (English)
0 references
22 January 2003
0 references
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.
0 references
Markov networks
0 references
Markov random fields
0 references
undirected graphical models
0 references
entropy decomposition
0 references
hyper-trees
0 references
tree-width
0 references
hardness
0 references
