×

The complexity of distinguishing Markov random fields. (English) Zbl 1159.68042

Goel, Ashish (ed.) et al., Approximation, randomization and combinatorial optimization. Algorithms and techniques. 11th international workshop, APPROX 2008, and 12th international workshop, RANDOM 2008, Boston, MA, USA, August 25–27, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-85362-6/pbk). Lecture Notes in Computer Science 5171, 331-342 (2008).
Summary: Markov random fields are often used to model high dimensional distributions in a number of applied areas. A number of recent papers have studied the problem of reconstructing a dependency graph of bounded degree from independent samples from the Markov random field. These results require observing samples of the distribution at all nodes of the graph. It was heuristically recognized that the problem of reconstructing the model where there are hidden variables (some of the variables are not observed) is much harder.
Here we prove that the problem of reconstructing bounded-degree models with hidden nodes is hard. Specifically, we show that unless \(\text{NP} = \text{RP}\),
– It is impossible to decide in randomized polynomial time if two models generate distributions whose statistical distance is at most 1/3 or at least 2/3.
– Given two generating models whose statistical distance is promised to be at least 1/3, and oracle access to independent samples from one of the models, it is impossible to decide in randomized polynomial time which of the two samples is consistent with the model.
The second problem remains hard even if the samples are generated efficiently, albeit under a stronger assumption.
For the entire collection see [Zbl 1149.68010].

MSC:

68W20 Randomized algorithms
60G60 Random fields
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI