Learnability of Quantifiers (ESSLLI ’19)

This is the website od ESSLLI 2019 class Learnability of Quantifiers taught by  Shane Steinert-Threlkeld and Jakub Szymanik.

After giving an introduction to generalized quantifier theory, this course surveys a number of approaches to learning such quantifiers. We will look at attempts from formal language theory, from developmental psychology, and from contemporary machine learning. Each approach will be assessed through the lens of explaining semantic universals: why do natural languages only express certain types of generalized quantifiers? Students will be exposed to the application of mathematical and computational methods to natural language semantics in order to explain the fundamental properties of meanings cross-linguistically.

Motivation and description:

Generalized quantifier theory studies the semantics of quantifier expressions, like, `every’, `some’, `most’, ‘infinitely many’, `uncountably many’, etc. The classical version was developed in the 1980s, at the interface of linguistics, mathematics, and philosophy. In logic, generalized quantifiers are often defined as classes of models. For instance, the quantifier `infinitely many’ may be defined as a class of all infinite models. Equivalently, in linguistics, generalized quantifiers are formally treated as relations between subset of the universe. For example, in the sentence `Most of the students are smart’, quantifier `most’ is a binary relation between the set of students and the set of smart people. The sentence is true if and only if the cardinality of the set of smart students is greater than the cardinality of the set of students who are not smart. Generalized quantifiers turned out to be one of the crucial notions in the development of formal semantics but also logic, theoretical computer science, and philosophy.


It turns out, however, that only a very limited subset of the mathematically possible generalized quantifiers are expressed in any natural language.  One would like an explanation of this fact: why do we only find particular kinds of quantifiers in all languages? This course will assess the idea that the quantifiers we find in natural language are the ones that are easier to learn.

Tentative outline:

Day 1: Generalized quantifiers. In the first lecture, we will introduce the notion of generalized quantifier. We will discuss different variants of its definition and show their equivalence. While doing that we will also introduce basic preliminary notions from logic and model theory as well as give a brief history of the development of generalized quantifier theory.  We will also discuss the issue of quantifier universals: monotonicity properties, conservativity, topic neutrality, and the like. We will mention linguistic and logical motivation for these as well as raise the question of explaining the universals in terms of learnability.

SLIDES

Chapter 3 of Szymanik 2016

Day 2: Computational representations of quantifiers. In this lecture, we will show how to think about quantifiers as computational problems. We will learn how quantifiers and their properties can be encoded as finite strings over a vocabulary. Those computational representations will form a basis for quantifier learnability models to be presented in the following lectures.

SLIDES

Chapter 4 of Szymanik 2016

Day 3: Machine learning for quantifiers, I. In the first part of this lecture, we will consider two approaches to the learnability of quantifiers that leverage the computational representations: formal learning theory and Bayesian grammar induction. We will briefly explain how neither has found a role for semantic universals to play. The bulk of this day will be a hands-on introduction to another modeling framework, namely neural networks. We will walk through the basic concepts of building a network, training it on some data, and best practices, with an eye towards applications to quantifiers. Students will also be given code to experiment with on their own.

SLIDES
Neural network tutorial

Day 4: Machine learning for quantifiers, II.  In this lecture, we will show how different types of artificial neural networks (incl. recurrent ones) can be trained to learn the meanings of quantifiers.  We will also present results showing that quantifiers satisfying the semantic universals introduced on Day 1 are easier to learn by such models. After presenting similar results for domains beyond quantifiers (responsive predicates and color terms), we will briefly discuss how these concepts from machine learning relate to other formal measures of the complexity of quantifiers.

SLIDES

Day 5: Developmental psychology and unification. In the final lecture, we will canvas some recent experimental results on quantifier learnability (e.g. Hunter and Lidz 2012, Katsos 2016). Among others, we will discuss to what extent the general definitions of “semantic complexity” that has been introduced in the previous lectures fit what we know about quantifier acquisition. Finally, we will conclude by highlighting the many open problems and areas for the future development of the learnability of quantifiers.

SLIDES

See also Chapter 5 of Szymanik for some results connecting cognition and logic of GQs.

Expected level and prerequisites

This is a short introductory monographic course and as such it will advantage students who are familiar with some basic logic and computability theory. The course is planned to be self-contained and self-explanatory; reading the suggested bibliography prior to the course is not expected of the participants.

References:

For an encyclopedia article see Westerståhl 2008 in Stanford Encyclopedia of Philosophy. For a survey of classical results we recommend: Keenan & Westerståhl 2011. Peters & Westerståhl 2006 is a thorough handbook treatment focused on definability questions and their applications in model theory and linguistics. Szymanik 2016 surveys much of the work connecting generalized quantifier theory to theoretical computer science and cognitive science.  For more computer science results consult, e.g., Makowsky & Pnueli 1995, and Immerman 1995.

Papers to be discussed include, but are not limited to:

  • Steinert-Threlkeld and Szymanik 2018, “Learnability and Semantic Universals”
  • Hunter and Lidz 2012, “Conservativity and learnability of determiners”
  • Van Benthem 1986, “Semantic Automata”
  • Piantadosi, Tenenbaum, and Goodman 2012,  “Modeling the acquisition of quantifier semantics: a case study in function word learnability”
  • Carcassi, Steinert-Threlkeld, and Szymanik 2019, “The emergence of monotone quantifiers via iterated learning”
  • van de Pol, Steinert-Threlkeld, and Szymanik 2019, “Complexity and learnability in the explanation of semantic universals”
  • Geurts et al. 2009, “Scalar quantifiers: Logic, acquisition, and processing”