ON THE LEARNABILITY AND USAGE OF ACYCLIC PROBABILISTIC FINITE AUTOMATA

We propose and analyze a distribution learning algorithm for a subclas s of acyclic probalistic finite automata (APFA). This subclass is char acterized by a certain distinguishability property of the automata's s tates. Though hardness results are known for learning distributions ge nerated by general APFAs, we prove that our algorithm can efficiently learn distributions generated by the subclass of APFAs we consider. In particular, we show that the KL-divergence between the distribution g enerated by the target source and the distribution generated by our hy pothesis can be made arbitrarily small with high confidence in polynom ial time. We present two applications of our algorithm. In the first, we show how to model cursively written letters. The resulting models a re part of a complete cursive handwriting recognition system. In the s econd application we demonstrate how APFAs can be used to build multip le-pronunciation models for spoken words. We evaluate the APFA-based p ronunciation models on labeled speech data. The good performance (in t erms of the log-likelihood obtained on test data ) achieved by the APF As and the little time needed for learning suggests that the learning algorithm of APFAs might be a powerful alternative to commonly used pr obabilistic models. (C) 1998 Academic Press.