Alladi Ramakrishnan Hall

Probabilistic Chomsky hierarchy

Thomas F. Icard III

Stanford University, USA

Probabilistic generative processes have become a ubiquitous tool for knowledge representation in AI and cognitive science, encoding everything from an agent’s causal understanding to complex social reasoning. In many cases the models can be seen as probabilistic versions of familiar logical tools. In particular, we can identify a natural hierarchy of probabilistic processes, from finite-state (Hidden Markov models) to Turing-complete (expressive probabilistic programming languages), giving a probabilistic version of the familiar Chomsky hierarchy. We study this hierarchy, focusing on the classes of probability distributions definable at each
level. Some results are classical (e.g., following from early work by Schützenberger and others), while others are new, and some open questions remain. The goal of this project — still in progress — is to calibrate how much expressive power is appropriate for modeling various cognitive phenomena.