Beyond Word N-Grams

Proceedings of the Fourth Bar-Ilan Symposium on Foundations of Artificial Intelligence

Volume

Proceedings of the Fourth Bar-Ilan Symposium on Foundations of Artificial Intelligence

Contents

We describe, analyze, and experimentally evaluate a new probabilistic model for word-sequence prediction in natural languages, based on prediction su~ix trees (PSTs). By using efficient data structures, we extend the notion of PST to unbounded vocabularies. We also show how to use a Bayesian approach based on recursive priors over all possible PSTs to efficiently maintain tree mixtures. These mixtures have provably and practically better performance than almost any single model. Finally, we evaluate the model on several corpora. The low perplexity achieved by relatively small PST mixture models suggests that they may be an advantageous alternative, both theoretically and practically, to the widely used n-gram models.