ML Anthology

Maximum Likelihood Bounded Tree-Width Markov Networks

Nathan Srebro
UAI 2001 pp. 504-511
doi:10.1016/S0004-3702(02)00360-0 /uai/2001/srebro2001uai-maximum/

Abstract

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.

PDF UAI Semantic Scholar

Cite

Text

Srebro. "Maximum Likelihood Bounded Tree-Width Markov Networks." Conference on Uncertainty in Artificial Intelligence, 2001. doi:10.1016/S0004-3702(02)00360-0

Markdown

[Srebro. "Maximum Likelihood Bounded Tree-Width Markov Networks." Conference on Uncertainty in Artificial Intelligence, 2001.](https://mlanthology.org/uai/2001/srebro2001uai-maximum/) doi:10.1016/S0004-3702(02)00360-0

BibTeX

@inproceedings{srebro2001uai-maximum,
  title     = {{Maximum Likelihood Bounded Tree-Width Markov Networks}},
  author    = {Srebro, Nathan},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year      = {2001},
  pages     = {504-511},
  doi       = {10.1016/S0004-3702(02)00360-0},
  url       = {https://mlanthology.org/uai/2001/srebro2001uai-maximum/}
}