9 papers
Longitudinal Brain Aging in Covariance Space: Temporally Calibrated Bayesian Inference for Adaptive Covariance Operators
Montserrat Fuentes, Yi Zhao
Functional brain aging is often characterized by differences between people of different ages, although aging unfolds within individuals. This distinction is especially important f…
Learning Distributions from Multiple Data Providers
Jon Kleinberg, Amin Saberi, Xizhi Tan +1
Motivated by learning from heterogeneous and overlapping data providers, we study a stylized model of distribution learning from restricted conditional samples. The goal is to lear…
Language Identification with Succinct Machine-Independent Traces
Moses Charikar, Jon Kleinberg, Chirag Pabbaraju
Motivated by the power of large language models, there has been renewed interest in the Gold-Angluin model of language identification in the limit, with an eye toward variants of t…
Globally Consistent Coloring Schemes for Language Identification
Moses Charikar, Jon Kleinberg, Chirag Pabbaraju
We study how little extra information is needed to make adversarial language learning possible. In Gold's model of language identification in the limit, a learner is given an enume…
On Language Generation in the Limit with Bounded Memory
Jon Kleinberg, Anay Mehrotra, Amin Saberi +1
We study language generation in the limit under bounded memory. In this task, a learner observes examples from an unknown target language one at a time and must eventually output o…
Mistake-Bounded Language Generation
Jon Kleinberg, Charlotte Peale, Omer Reingold
We investigate the learning task of language generation in the limit, but shift focus from the traditional time-of-last-mistake metric of a generator's success to a new notion of "…
Validity, Sparse Holes, and Breadth in Language Generation: Banach Density, Topology, and Geometry
Jon Kleinberg, Fan Wei
Language generation in the limit, rooted in work of Gold and Angluin and revived by Kleinberg and Mullainathan, studies generation under minimal assumptions: an adversary enumerate…
Language Generation and Identification From Partial Enumeration: Tight Density Bounds and Topological Characterizations
Jon Kleinberg, Fan Wei
The success of large language models (LLMs) has motivated formal theories of language generation and learning. We study the framework of \emph{language generation in the limit}, wh…
Density Measures for Language Generation
Jon Kleinberg, Fan Wei
The recent successes of large language models (LLMs) have led to a surge of theoretical research into language generation. A recent line of work proposes an abstract view, called l…