Efficient Pruning of Probabilistic Automata

Franck Thollard (1) , Baptiste Jeudy (1)

1 LHC - Laboratoire Hubert Curien

Applications of probabilistic grammatical inference are limited due to time and space consuming constraints. In statistical language modeling, for example, large corpora are now available and lead to managing automata with millions of states. We propose in this article a method for pruning automata (when restricted to tree based structures) which is not only efficient (sub-quadratic) but that allows to dramatically reduce the size of the automaton with a small impact on the underlying distribution. Results are evaluated on a language modeling task.

Domaines: Intelligence artificielle [cs.AI]

Franck Thollard, Baptiste Jeudy. Efficient Pruning of Probabilistic Automata. Structural and Statistical Pattern Recognition, Dec 2008, Orlando, United States. pp.65-75. ⟨ujm-00322818⟩