Advertisement

The Complexity of Distinguishing Markov Random Fields

  • Andrej Bogdanov
  • Elchanan Mossel
  • Salil Vadhan
  • Andrej Bogdanov
    • 1
  • Elchanan Mossel
    • 2
  • Salil Vadhan
    • 3
  1. 1.Institute for Theoretical Computer ScienceTsinghua University 
  2. 2.Dept. of Statistics and Dept. of Computer SciencesU.C. Berkeley 
  3. 3.School of Engineering and Applied SciencesHarvard University 
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 5171)

Abstract

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 NP = 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.

Download to read the full conference paper text

References

  1. 1.
    Friedman, N.: Infering cellular networks using probalistic graphical models. Science (2004)Google Scholar
  2. 2.
    Kasif, S.: Bayes networks and graphical models in computational molecular biology and bioinformatics, survey of recent research (2007), http://genomics10.bu.edu/bioinformatics/kasif/bayes-net.html
  3. 3.
    Felsenstein, J.: Inferring Phylogenies. Sinauer, New York (2004)Google Scholar
  4. 4.
    Semple, C., Steel, M.: Phylogenetics. Mathematics and its Applications series, vol. 22. Oxford University Press, Oxford (2003)MATHGoogle Scholar
  5. 5.
    Erdös, P.L., Steel, M.A., Székely, L.A., Warnow, T.A.: A few logs suffice to build (almost) all trees (part 1). Random Structures Algorithms 14(2), 153–184 (1999)MATHCrossRefMathSciNetGoogle Scholar
  6. 6.
    Mossel, E.: Distorted metrics on trees and phylogenetic forests. IEEE Computational Biology and Bioinformatics 4, 108–116 (2007)CrossRefGoogle Scholar
  7. 7.
    Daskalakis, C., Mossel, E., Roch, S.: Optimal phylogenetic reconstruction. In: Proceedings of the thirty-eighth annual ACM symposium on Theory of computing (STOC 2006), pp. 159–168 (2006)Google Scholar
  8. 8.
    Abbeel, P., Koller, D., Ng, A.Y.: Learning factor graphs in polynomial time and sampling complexity. Journal of Machine Learning Research 7, 1743–1788 (2006)MathSciNetGoogle Scholar
  9. 9.
    Bresler, G., Mossel, E., Sly, A.: Reconstruction of Markov random fields from samples: Some easy observations and algorithms. These proceedings (2008), http://front.math.ucdavis.edu/0712.1402
  10. 10.
    Wainwright, M.J., Ravikumar, P., Lafferty, J.D.: High dimensional graphical model selection using ℓ1-regularized logistic regression. In: Proceedings of the NIPS (2006)Google Scholar
  11. 11.
    Sinclair, A.: Algorithms for Random Generation and Counting: A Markov chain Approach. In: Progress in Theoretical Computer Science. Birkhäuser, Basel (1993)Google Scholar
  12. 12.
    Luby, M., Vigoda, E.: Fast convergence of the Glauber dynamics for sampling independent sets. Random Struct. Algorithms 15(3–4), 229–241 (1999)MATHCrossRefMathSciNetGoogle Scholar
  13. 13.
    Jerrum, M., Valiant, L.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform distribution. Theor. Comput. Sci. 43, 169–188 (1986)MATHCrossRefMathSciNetGoogle Scholar
  14. 14.
    Goldreich, O.: On promise problems: a survey. In: Goldreich, O., Rosenberg, A.L., Selman, A.L. (eds.) Theoretical Computer Science. LNCS, vol. 3895, pp. 254–290. Springer, Heidelberg (2006)CrossRefGoogle Scholar
  15. 15.
    Even, S., Selman, A.L., Yacobi, Y.: The complexity of promise problems with applications to public-key cryptography. Information and Control 61, 159–173 (1984)MATHCrossRefMathSciNetGoogle Scholar
  16. 16.
    Goldreich, O.: Foundations of cryptography (Basic tools). Cambridge University Press, Cambridge (2001)MATHGoogle Scholar
  17. 17.
    Håstad, J., Impagliazzo, R., Levin, L.A., Luby, M.: A pseudorandom generator from any one-way function. SIAM Journal on Computing 28(4), 1364–1396 (1999)MATHCrossRefMathSciNetGoogle Scholar
  18. 18.
    Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity, or All languages in NP have zero-knowledge proof systems. Journal of the Association for Computing Machinery 38(3), 691–729 (1991)MATHMathSciNetGoogle Scholar
  19. 19.
    Impagliazzo, R., Yung, M.: Direct minimum-knowledge computations (extended abstract). In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 40–51. Springer, Heidelberg (1988)Google Scholar
  20. 20.
    Ben-Or, M., Goldreich, O., Goldwasser, S., Håstad, J., Kilian, J., Micali, S., Rogaway, P.: Everything provable is provable in zero-knowledge. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 37–56. Springer, Heidelberg (1990)Google Scholar
  21. 21.
    Ostrovsky, R., Wigderson, A.: One-way functions are essential for non-trivial zero knowledge. In: Proc. 2nd Israel Symp. on Theory of Computing and Systems, pp. 3–17. IEEE Computer Society Press, Los Alamitos (1993)CrossRefGoogle Scholar
  22. 22.
    Sahai, A., Vadhan, S.: A complete problem for statistical zero knowledge. Journal of the ACM 50(2), 196–249 (2003)CrossRefMathSciNetGoogle Scholar
  23. 23.
    Babai, L., Moran, S.: Arthur-Merlin games: A randomized proof system and a hierarchy of complexity classes. Journal of Computer and System Sciences 36, 254–276 (1988)MATHCrossRefMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2008

Personalised recommendations

We use cookies to personalise content and ads, to provide social media features and to analyse our traffic. We also share information about your use of our site with our social media, advertising and analytics partners in accordance with our Privacy Statement. You can manage your preferences in Manage Cookies.

Close
OK
Manage Cookies