Inference and minimization of hidden Markov chains

ABSTRACT

A hidden Markov chain (hmc) is a finite ergodic Markov chain in which each of the states is labelled 0 or 1. As the Markov chain moves through a random trajectory, the hmc emits a 0 or a 1 at each times step according to the label of the state just entered. The inference problem is to construct a mechanism which will emit 0's and 1's and which is equivalent to a given hmc in the sense of having identical long-term behavior. We define the inference problem in a learning setting in which an algorithm can query an oracle for the long-term probability of any binary string. We prove that inference is hard: any algorithm for inference must make exponentially many oracle calls. Our method is information-theoretic and does not depend on separation assumptions for any complexity classes. We show that the related discrimination problem is also hard, but that on a nontrivial subclass of hmc's there is a randomized algorithm for discrimination. Finally, we give a polynomial-time algorithm for reducing a hidden Markov chain to its minimal form, and from this there follows a new algorithm for equivalence of hmc's.

REFERENCES

• AW: Naoki Abe , Manfred K. Warmuth, On the Computational Complexity of Approximating Distributions by Probabilistic Automata, Machine Learning, v.9 n.2-3, p.205-260, July 1992 [doi>10.1007/BF00992677]
• AK*: R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovasz, and C. Rackoff, "Random walks, universal traversal sequences, and the complexity of maze problems," Proceedzngs of the ~Oth Annual IEEE Symposium on the Foundations of Computer Science (1979), 218-233.
• Ang87: Dana Angluin, Learning regular sets from queries and counterexamples, Information and Computation, v.75 n.2, p.87-106, November 1, 1987 [doi>10.1016/0890-5401(87)90052-6]
• Ang88: Dana Angluin, Queries and Concept Learning, Machine Learning, v.2 n.4, p.319-342, April 1988 [doi>10.1023/A:1022821128753]
• Ang89: D. Angluin, "Minimum consistent DFA problem is NP-complete," unpublished manuscript.
• Ch: H. Chernoff, "A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations," Annals of Mathematical Statistics 23 (1952), 493-507.
• Co: A. Cobham, "Stochastic automata with large state spaces and low rank," Linear Algebra and Its Applications 75 (1986), 57-66.
• CLR: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• ERV: W. Evans, S. Rajagopalan, and U. Vazirani, "Learning an unknown randomized algorithm from its behavior," to appear in Proceedings of the S~xth A CM Workshop on Computational Learmng Theory, 1993.
• Fe: W. Feller, An Introductwn to Probabzhty The. ory and Its Applications, 2 volumes, 2d ed., Wiley, 1957.
• Gi: E.J. Gilbert, "On the identifiability problem for functions of finite Markov chains," Annals of Mathematical Statistics 30 (1959), 688-697.
• G93a: David Gillman, Hidden Markov chains: convergence rates and the complexity of inference, Massachusetts Institute of Technology, Cambridge, MA, 1993
• Go: E.M. Gold, "System identification via state characterizaton," Automatica 8 (1972), 621- 636.
• Go78: E. M. Gold, "Complexity of automaton identification from given data," Information and Control 37 (1978), 302-320.
• Ha: D J. Hand, Discrimination and Classification, Wiley, 1981.
• IAK: H. Ito, S.-I. Amari, and K. Kobayashi, "Identifiability of hidden Markov information sources and their minimum degrees of freedom," IEEE Transaction on Information Theory 38 (1992), 324-333.
• LZ: J. Ziv and A. Lempel, "Compression of individual sequences via variable-rate coding," IEEE Transactzons on Informatwn Theory 24 No. 5 (1978), 530-536.
• LRS: S.E. Levinson, L.R. Rabiner, and M. M. Sondhi, "An introduction to the application of the theory of probabilistic functions of a Markov process to automatic speech recognition,'' The Bell System Technical Journal 62 (1983), 1035-1074.
• MZ89: N. Merhav and J. Ziv, "Estimating with partial statistics the parameters of ergodic finite Markov sources," IEEE Transactions on Information Theory 35 No. 2 (1989), 326-333.
• P: A. Paz, Introduction to Probabilistic Automata, 1971.
• PW: L. Pitt , M. K. Warmuth, The minimum consistent DFA problem cannot be approximated within and polynomial, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.421-432, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73048]
• R: S. Rudich, "Inferring the Structure ofa Markov Chain From Its Output,"Proceedings of the Twenty-Sizth IEEE Symposium on Foundations of Computer Science (1985), 321-326.
• Tz92a: Wen-Guey Tzeng, A polynomial-time algorithm for the equivalence of probabilistic automata, SIAM Journal on Computing, v.21 n.2, p.216-227, April 1992 [doi>10.1137/0221017]
• Tz92b: Wen-Guey Tzeng, Learning Probabilistic Automata and Markov Chains via Queries, Machine Learning, v.8 n.2, p.151-166, March 1992 [doi>10.1023/A:1022616503659]
• V84: L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
• WZ: A.D. Wyner and J. Ziv, "Classification with finite-memory," preprint - in preparation.
• Y: Kenji Yamanishi, Probably almost discriminative learning, Proceedings of the fifth annual workshop on Computational learning theory, p.164-171, July 27-29, 1992, Pittsburgh, Pennsylvania, United States [doi>10.1145/130385.130404]
• Zi: J. Ziv, "On classification with empirically observed statistics and universal data compression,'' IEEE Transactions on Information Theory 34 No. 2 (1988), 278-286.
• ZM: J. Ziv and N. Merhav, "Estimating the number of states of a finite-state source," IEEE Transactions on Information Theory 38 No. 1 (1992), 61-65.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

General Terms:
Algorithms, Theory, Verification