This is the website of the NASSLLI 2022 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.
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.
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.
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.
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.
See also Chapter 5 of Szymanik 2016 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 2019, “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 2021, “Monotone Quantifiers Emerge via Iterated Learning”
- van de Pol, Lodder, van Maanen, Steinert-Threlkeld, and Szymanik 2022, “Quantifiers satisfying semantic universals have shorter minimal description length”
- Steinert-Threlkeld 2020, “An explanation of the veridical uniformity universal”
- Steinert-Threlkeld and Szymanik 2020, “Ease of learning explains semantic universals”
- Geurts et al. 2009, “Scalar quantifiers: Logic, acquisition, and processing”