Calibrating generative models: The probabilistic Chomsky–Schützenberger hierarchy

• Published in: Journal of mathematical psychology 2020-04, Vol.95, p.102308, Article 102308
• Main Author: Icard, Thomas F.
• Format: Article
• Language: English
• Subjects: Analytic hierarchy; Chomsky hierarchy; Generative models; Probabilistic computation
• ISSN: 0022-2496; 1096-0880
• DOI: 10.1016/j.jmp.2019.102308

A probabilistic Chomsky–Schützenberger hierarchy of grammars is introduced and studied, with the aim of understanding the expressive power of generative models. We offer characterizations of the distributions definable at each level of the hierarchy, including probabilistic regular, context-free, (linear) indexed, context-sensitive, and unrestricted grammars, each corresponding to familiar probabilistic machine classes. Special attention is given to distributions on (unary notations for) positive integers. Unlike in the classical case where the ”semi-linear” languages all collapse into the regular languages, using analytic tools adapted from the classical setting we show there is no collapse in the probabilistic hierarchy: more distributions become definable at each level. We also address related issues such as closure under probabilistic conditioning. [Display omitted] •Probabilistic Chomsky–Schützenberger hierarchy, calibrating generative models.•Correspondence with analytical hierarchy of probability generating functions.•Equivalence between probabilistic programs and computably enumerable semi-measures.•Closure results for Bayesian conditioning•Repercussions for common psychological and program induction approaches.