On the learnability and usage of acyclic probabilistic finite automata

摘要: We propose and analyze a distribution learning algorithm for subclass ofacyclic probalistic finite automata(APFA). This is characterized by certain distinguishability property of the automata's states. Though hardness results are known distributions generated general APFAs, we prove that our can efficiently learn APFAs consider. In particular, show KL-divergence between target source hypothesis be made arbitrarily small with high confidence in polynomial time. present two applications algorithm. first, how to model cursively written letters. The resulting models part complete cursive handwriting recognition system. second application demonstrate used build multiple-pronunciation spoken words. evaluate APFA-based pronunciation on labeled speech data. good performance (in terms log-likelihood obtained test data) achieved little time needed suggests might powerful alternative commonly probabilistic models.