Maximum likelihood bounded tree-width Markov networks (Q1853683)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1857177
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Maximum likelihood bounded tree-width Markov networks |
scientific article; zbMATH DE number 1857177 |
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
0.8433488011360168
0 references
0.8433488011360168
0 references
0.7705607414245605
0 references
0.7667891383171082
0 references
0.7522162199020386
0 references
