Learning probabilistic automata with variable memory length

Dana Ron, Yoram Singer, Naftali Tishby

Research output: Chapter in Book/Report/Conference proceedingConference contribution

51 Scopus citations

Abstract

We propose and analyze a distribution learning algorithm for variable memory length Markov processes. These processes can be described by a subclass of probabilistic finite automata which we name Probabilistic Finite Suffix Automata. The learning algorithm is motivated by real applications in man-machine interaction such as handwriting and speech recognition. Conventionally used fixed memory Markov and hidden Markov models have either severe practical or theoretical drawbacks. Though general hardness results are known for learning distributions generated by sources with similar structure, we prove that our algorithm can indeed efficiently learn distributions generated by our more restricted sources. In Particular, we show that the KL-divergence between the distribution generated by the target source and the distribution generated by our hypothesis can be made small with high confidence in polynomial time and sample complexity. We demonstrate the applicability of our algorithm by learning the structure of natural English text and using our hypothesis for the correction of corrupted text.

Original languageEnglish (US)
Title of host publicationProceedings of the 7th Annual Conference on Computational Learning Theory, COLT 1994
PublisherAssociation for Computing Machinery
Pages35-46
Number of pages12
ISBN (Electronic)0897916557
DOIs
StatePublished - Jul 16 1994
Externally publishedYes
Event7th Annual Conference on Computational Learning Theory, COLT 1994 - New Brunswick, United States
Duration: Jul 12 1994Jul 15 1994

Publication series

NameProceedings of the Annual ACM Conference on Computational Learning Theory
VolumePart F129415

Other

Other7th Annual Conference on Computational Learning Theory, COLT 1994
CountryUnited States
CityNew Brunswick
Period7/12/947/15/94

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'Learning probabilistic automata with variable memory length'. Together they form a unique fingerprint.

  • Cite this

    Ron, D., Singer, Y., & Tishby, N. (1994). Learning probabilistic automata with variable memory length. In Proceedings of the 7th Annual Conference on Computational Learning Theory, COLT 1994 (pp. 35-46). (Proceedings of the Annual ACM Conference on Computational Learning Theory; Vol. Part F129415). Association for Computing Machinery. https://doi.org/10.1145/180139.181006