Learning to Sample from Censored Markov Random Fields
Abstract
We study the problem of learning Censored Markov Random Fields (abbreviated CMRFs), which are Markov Random Fields where some of the nodes are censored (i.e. not observed). We assume the CMRF is high temperature but, crucially, make no assumption about its structure. This makes structure learning impossible. Nevertheless we introduce a new definition, which we call learning to sample, that circumvents this obstacle. We give an algorithm that can learn to sample from a distribution within $\epsilon n$ earthmover distance of the target distribution for any $\epsilon > 0$. We obtain stronger results when we additionally assume high girth, as well as computational lower bounds showing that these are essentially optimal.
Cite
Text
Moitra et al. "Learning to Sample from Censored Markov Random Fields." Conference on Learning Theory, 2021.Markdown
[Moitra et al. "Learning to Sample from Censored Markov Random Fields." Conference on Learning Theory, 2021.](https://mlanthology.org/colt/2021/moitra2021colt-learning/)BibTeX
@inproceedings{moitra2021colt-learning,
title = {{Learning to Sample from Censored Markov Random Fields}},
author = {Moitra, Ankur and Mossel, Elchanan and Sandon, Colin P},
booktitle = {Conference on Learning Theory},
year = {2021},
pages = {3419-3451},
volume = {134},
url = {https://mlanthology.org/colt/2021/moitra2021colt-learning/}
}