Papers for

language model designers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Probabilistic languages from n-gram models differ from connected PCFGs

Contributions to the hierarchy of probabilistic languages

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.

Sun 20 SeptFormal Languages and Automata TheoryComputation and Language

The gist

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.

Open → 2609.23567v1