Probabilistic languages from n-gram models differ from connected PCFGs
Contributions to the hierarchy of probabilistic languages
Formal Languages and Automata TheoryComputation and Language
Summary
This paper looks at two ways to mathematically describe how languages can be generated with probabilities: n-gram models and probabilistic context-free grammars (PCFGs). The authors show that everything created by an n-gram model can also be made by some PCFG, but the reverse is not true. They introduce a special kind of PCFG where every rule connecting parts has a positive chance of being used, and they prove that n-gram models can't exactly produce the languages these special PCFGs generate. This helps clarify the hierarchy and limits between these common probabilistic language models.
What this means in practice
- •For language model designers: Decide which probabilistic model type fits a target language based on the proven differences between n-gram and fully connected PCFG-generated languages.
- •For speech recognition developers: Avoid over-relying on fully connected PCFGs when simpler n-gram models suffice, based on the separation shown in generating probabilistic languages.
A theory result. No direct application yet.
Authors
Lothar Sebastian Krapp, Remo Nitschke
Abstract
We reconsider the theory of probabilistic formal languages generated by n-gram models and by probabilistic context-free grammars (PCFGs). The expected hierarchy of probabilistic grammars is established by proving that every probabilistic language generated by an n-gram model is also generated by some PCFG, while some probabilistic languages generated by PCFGs cannot be generated by any $n$-gram model. We introduce the notion of fully connected PCFGs, namely PCFGs in Chomsky normal form where every production rule only involving non-terminals has non-zero probability. Our main result shows that any probabilistic language generated by an $n$-gram model differs from any probabilistic language generated by a fully connected PCFG. Therefore, the class of probabilistic languages generated by $n$-gram models is not a subset of the class generated by fully connected PCFGs.