Search

I present a simple algorithm for enumerating the trees generated by a Context Free Grammar (CFG). The algorithm uses a pairing function to form a bijection between CFG derivations and natural numbers, so that trees can be uniquely decoded from counting. This provides a general way to number expressions in natural logical languages, and potentially can be extended to other combinatorial problems. I also show how this algorithm may be generalized to more general forms of derivation, including analogs of Lempel-Ziv coding on trees.

Language models demonstrate both quantitative improvement and new qualitative capabilities with increasing scale. Despite their potentially transformative impact, these new capabilities are as yet poorly characterized. In order to inform future research, prepare for disruptive new model capabilities, and ameliorate socially harmful effects, it is vital that we understand the present and near-future capabilities and limitations of language models. To address this challenge, we introduce the Beyond the Imitation Game benchmark (BIG-bench). BIG-bench currently consists of 204 tasks, contributed by 450 authors across 132 institutions. Task topics are diverse, drawing problems from linguistics, childhood development, math, common-sense reasoning, biology, physics, social bias, software development, and beyond. BIG-bench focuses on tasks that are believed to be beyond the capabilities of current language models. We evaluate the behavior of OpenAI's GPT models, Google-internal dense transformer architectures, and Switch-style sparse transformers on BIG-bench, across model sizes spanning millions to hundreds of billions of parameters. In addition, a team of human expert raters performed all tasks in order to provide a strong baseline. Findings include: model performance and calibration both improve with scale, but are poor in absolute terms (and when compared with rater performance); performance is remarkably similar across model classes, though with benefits from sparsity; tasks that improve gradually and predictably commonly involve a large knowledge or memorization component, whereas tasks that exhibit "breakthrough" behavior at a critical scale often involve multiple steps or components, or brittle metrics; social bias typically increases with scale in settings with ambiguous context, but this can be improved with prompting., 27 pages, 17 figures + references and appendices, repo: https://github.com/google/BIG-bench

Supplemental material, sj-pdf-1-pss-10.1177_09567976211034502 for Exact Number Concepts Are Limited to the Verbal Count Range by Benjamin Pitt, Edward Gibson and Steven T. Piantadosi in Psychological Science

The widespread success of large language models (LLMs) has been met with skepticism that they possess anything like human concepts or meanings. Contrary to claims that LLMs possess no meaning whatsoever, we argue that they likely capture important aspects of meaning, and moreover work in a way that approximates a compelling account of human cognition in which meaning arises from conceptual role. Because conceptual role is defined by the relationships between internal representational states, meaning cannot be determined from a model's architecture, training data, or objective function, but only by examination of how its internal states relate to each other. This approach may clarify why and how LLMs are so successful and suggest how they can be made more human-like.

Supplemental material, sj-pdf-1-pss-10.1177_09567976211034502 for Exact Number Concepts Are Limited to the Verbal Count Range by Benjamin Pitt, Edward Gibson and Steven T. Piantadosi in Psychological Science

This work was supported by the National Science Foundation Graduate Research Fellowship Programme grant no. DGE-1419118 to S.E.K., and NSF 2000759 from the Division of Research on Learning in Formal and Informal Settings (DRL) to S.T.P., the Austrian Science Fund (FWF project no. P33928_B) to F.R., the Alfred P. Sloan Foundation Fellowship grant no. 220020300 to J.F.C., National Institutes of Health grant no. R01 HD085996 to J.F.C. and S.T.P. and the James S. McDonnell Foundation. The ability to represent approximate quantities appears to be phylogenetically widespread, but the selective pressures and proximate mechanisms favouring this ability remain unknown. We analysed quantity discrimination data from 672 subjects across 33 bird and mammal species, using a novel Bayesian model that combined phylogenetic regression with a model of number psychophysics and random effect components. This allowed us to combine data from 49 studies and calculate the Weber fraction (a measure of quantity representation precision) for each species. We then examined which cognitive, socioecological and biological factors were related to variance in Weber fraction. We found contributions of phylogeny to quantity discrimination performance across taxa. Of the neural, socioecological and general cognitive factors we tested, cortical neuron density and domain-general cognition were the strongest predictors of Weber fraction, controlling for phylogeny. Our study is a new demonstration of evolutionary constraints on cognition, as well as of a relation between species-specific neuron density and a particular cognitive ability. This article is part of the theme issue 'Systems neuroscience through the lens of evolutionary theory'. Publisher PDF

Data sources for meta-analysis by species and additional figures.

Machine learning has made major advances in categorizing objects in images, yet the best algorithms miss important aspects of how people learn and think about categories. People can learn richer concepts from fewer examples, including causal models that explain how members of a category are formed. Here, we explore the limits of this human ability to infer causal "programs" -- latent generating processes with nontrivial algorithmic properties -- from one, two, or three visual examples. People were asked to extrapolate the programs in several ways, for both classifying and generating new examples. As a theory of these inductive abilities, we present a Bayesian program learning model that searches the space of programs for the best explanation of the observations. Although variable, people's judgments are broadly consistent with the model and inconsistent with several alternatives, including a pre-trained deep neural network for object recognition, indicating that people can learn and reason with rich algorithmic abstractions from sparse input data., Comment: In press at "Computational Brain & Behavior"

We introduce theory-neutral estimates of the amount of information learners know about how language works. We provide estimates at several levels of linguistic analysis: phonemes, wordforms, lexical semantics, word frequency and syntax. Our best guess is that the average English-speaking adult has learned 12.5 million bits of information, the majority of which is lexical semantics. Interestingly, very little of this information is syntactic, even in our upper bound analyses. Generally, our results suggest that learners possess remarkable inferential mechanisms capable of extracting, on average, nearly 2000 bits of information about how language works each day for 18 years.

Recently, Ferrer i Cancho and Moscoso del Prado Martin [arXiv:1209.1751] argued that an observed linear relationship between word length and average surprisal (Piantadosi, Tily, & Gibson, 2011) is not evidence for communicative efficiency in human language. We discuss several shortcomings of their approach and critique: their model critically rests on inaccurate assumptions, is incapable of explaining key surprisal patterns in language, and is incompatible with recent behavioral results. More generally, we argue that statistical models must not critically rely on assumptions that are incompatible with the real system under study., 8 pages

In acquiring number words, children exhibit a qualitative leap in which they transition from understanding a few number words, to possessing a rich system of interrelated numerical concepts. We present a computational framework for understanding this inductive leap as the consequence of statistical inference over a sufficiently powerful representational system. We provide an implemented model that is powerful enough to learn number word meanings and other related conceptual systems from naturalistic data. The model shows that bootstrapping can be made computationally and philosophically well-founded as a theory of number learning. Our approach demonstrates how learners may combine core cognitive operations to build sophisticated representations during the course of development, and how this process explains observed developmental patterns in number word learning., United States. Air Force Office of Scientific Research (Grant FA9550-07-1-0075)