Publications (65)
Automating the Analysis of Parsing Algorithms (and other Dynamic Programs)
Tim Vieira, Ryan Cotterell, Jason Eisner
Much algorithmic research in NLP aims to efficiently manipulate rich formal structures. An algorithm designer typically seeks to provide guarantees about their proposed algorithm -…
Probabilistic Typology: Deep Generative Models of Vowel Inventories
Ryan Cotterell, Jason Eisner
Linguistic typology studies the range of structures present in human language. The main goal of the field is to discover which sets of possible phenomena are universal, and which a…
LLMs in the Imaginarium: Tool Learning through Simulated Trial and Error
Boshi Wang, Hao Fang, Jason Eisner +2
Tools are essential for large language models (LLMs) to acquire up-to-date information and take consequential actions in external environments. Existing work on tool-augmented LLMs…
Efficient Semiring-Weighted Earley Parsing
Andreas Opedal, Ran Zmigrod, Tim Vieira +2
This paper provides a reference description, in the form of a deduction system, of Earley's (1970) context-free parsing algorithm with various speed-ups. Our presentation includes…
Do Androids Know They're Only Dreaming of Electric Sheep?
Sky CH-Wang, Benjamin Van Durme, Jason Eisner +1
We design probes trained on the internal representations of a transformer language model to predict its hallucinatory behavior on three grounded generation tasks. To train the prob…
On the Intersection of Context-Free and Regular Languages
Clemente Pasti, Andreas Opedal, Tiago Pimentel +3
The Bar-Hillel construction is a classic result in formal language theory. It shows, by a simple construction, that the intersection of a context-free language and a regular langua…
Task-Oriented Dialogue as Dataflow Synthesis
Semantic Machines, Jacob Andreas, John Bufe +43
We describe an approach to task-oriented dialogue in which dialogue state is represented as a dataflow graph. A dialogue agent maps each user utterance to a program that extends th…
Non-Programmers Can Label Programs Indirectly via Active Examples: A Case Study with Text-to-SQL
Ruiqi Zhong, Charlie Snell, Dan Klein +1
Can non-programmers annotate natural language utterances with complex programs that represent their meaning? We introduce APEL, a framework in which non-programmers select among ca…
When More Data Hurts: A Troubling Quirk in Developing Broad-Coverage Natural Language Understanding Systems
Elias Stengel-Eskin, Emmanouil Antonios Platanios, Adam Pauls +5
In natural language understanding (NLU) production systems, users' evolving needs necessitate the addition of new features over time, indexed by new symbols added to the meaning re…
Specializing Word Embeddings (for Parsing) by Information Bottleneck
Xiang Lisa Li, Jason Eisner
Pre-trained word embeddings like ELMo and BERT contain rich syntactic and semantic information, resulting in state-of-the-art performance on various tasks. We propose a very fast v…
CoNLL-SIGMORPHON 2017 Shared Task: Universal Morphological Reinflection in 52 Languages
Ryan Cotterell, Christo Kirov, John Sylak-Glassman +8
The CoNLL-SIGMORPHON 2017 shared task on supervised morphological generation required systems to be trained and tested in each of 52 typologically diverse languages. In sub-task 1,…
Spell Once, Summon Anywhere: A Two-Level Open-Vocabulary Language Model
Sabrina J. Mielke, Jason Eisner
We show how the spellings of known words can help us deal with unknown words in open-vocabulary NLP tasks. The method we propose can be used to extend any closed-vocabulary generat…
On the Diachronic Stability of Irregularity in Inflectional Morphology
Ryan Cotterell, Christo Kirov, Mans Hulden +1
Many languages' inflectional morphological systems are replete with irregulars, i.e., words that do not seem to follow standard inflectional rules. In this work, we quantitatively…
Algorithms for Acyclic Weighted Finite-State Automata with Failure Arcs
Anej Svete, Benjamin Dayan, Tim Vieira +2
Weighted finite-state automata (WSFAs) are commonly used in NLP. Failure transitions are a useful extension for compactly representing backoffs or interpolation in -gram models…
Efficient Normal-Form Parsing for Combinatory Categorial Grammar
Jason Eisner
Under categorial grammars that have powerful rules like composition, a simple n-word sentence can have exponentially many parses. Generating all parses is inefficient and obscures…
A Deep Generative Model of Vowel Formant Typology
Ryan Cotterell, Jason Eisner
What makes some types of languages more probable than others? For instance, we know that almost all spoken languages contain the vowel phoneme /i/; why should that be? The field of…
Autoregressive Modeling with Lookahead Attention
Li Du, Hongyuan Mei, Jason Eisner
To predict the next token, autoregressive models ordinarily examine the past. Could they also benefit from also examining hypothetical futures? We consider a novel Transformer-base…
Fine-Grained Prediction of Syntactic Typology: Discovering Latent Structure with Supervised Learning
Dingquan Wang, Jason Eisner
We show how to predict the basic word-order facts of a novel language given only a corpus of part-of-speech (POS) sequences. We predict how often direct objects follow their verbs,…
Structure-Aware Path Inference for Neural Finite State Transducers
Weiting Tan, Chu-cheng Lin, Jason Eisner
Neural finite-state transducers (NFSTs) form an expressive family of neurosymbolic sequence transduction models. An NFST models each string pair as having been generated by a laten…
The Neural Hawkes Process: A Neurally Self-Modulating Multivariate Point Process
Hongyuan Mei, Jason Eisner
Many events occur in the world. Some event types are stochastically excited or inhibited---in the sense of having their probabilities elevated or decreased---by patterns in the seq…
Fine-Tuning LLMs with Fine-Grained Human Feedback on Text Spans
Sky CH-Wang, Justin Svegliato, Helen Appel +1
We present a method and dataset for fine-tuning language models with preference supervision using feedback-driven improvement chains. Given a model response, an annotator provides…
Noise-Contrastive Estimation for Multivariate Point Processes
Hongyuan Mei, Tom Wan, Jason Eisner
The log-likelihood of a generative model often involves both positive and negative terms. For a temporal multivariate point process, the negative term sums over all the possible ev…
Learning How to Ask: Querying LMs with Mixtures of Soft Prompts
Guanghui Qin, Jason Eisner
Natural-language prompts have recently been used to coax pretrained language models into performing other AI tasks, using a fill-in-the-blank paradigm (Petroni et al., 2019) or a f…
Unsupervised Disambiguation of Syncretism in Inflected Lexicons
Ryan Cotterell, Christo Kirov, Sabrina J. Mielke +1
Lexical ambiguity makes it difficult to compute various useful statistics of a corpus. A given word form might represent any of several morphological feature bundles. One can, howe…
The Whole Truth and Nothing But the Truth: Faithful and Controllable Dialogue Response Generation with Dataflow Transduction and Constrained Decoding
Hao Fang, Anusha Balakrishnan, Harsh Jhamtani +7
In a real-world dialogue system, generated text must be truthful and informative while remaining fluent and adhering to a prescribed style. Satisfying these constraints simultaneou…
LLM-Rubric: A Multidimensional, Calibrated Approach to Automated Evaluation of Natural Language Texts
Helia Hashemi, Jason Eisner, Corby Rosset +2
This paper introduces a framework for the automated evaluation of natural language texts. A manually constructed rubric describes how to assess multiple dimensions of interest. To…
Principled Gradient-based Markov Chain Monte Carlo for Text Generation
Li Du, Afra Amini, Lucas Torroba Hennigen +4
Recent papers have demonstrated the possibility of energy-based text generation by adapting gradient-based sampling algorithms, a paradigm of MCMC algorithms that promises fast con…
Limitations of Autoregressive Models and Their Alternatives
Chu-Cheng Lin, Aaron Jaech, Xin Li +2
Standard autoregressive language models perform only polynomial-time computation to compute the probability of the next symbol. While this is attractive, it means they cannot model…
A Glitch in the Matrix? Locating and Detecting Language Model Grounding with Fakepedia
Giovanni Monea, Maxime Peyrard, Martin Josifoski +6
Large language models (LLMs) have an impressive ability to draw on novel information supplied in their context. Yet the mechanisms underlying this contextual grounding remain unkno…
A Generative Model for Punctuation in Dependency Trees
Xiang Lisa Li, Dingquan Wang, Jason Eisner
Treebanks traditionally treat punctuation marks as ordinary words, but linguists have suggested that a tree's "true" punctuation marks are not observed (Nunberg, 1990). These laten…
Are All Languages Equally Hard to Language-Model?
Ryan Cotterell, Sabrina J. Mielke, Jason Eisner +1
For general modeling methods applied to diverse languages, a natural question is: how well should we expect our models to work on languages with differing typological profiles? In…
Searching for More Efficient Dynamic Programs
Tim Vieira, Ryan Cotterell, Jason Eisner
Computational models of human language often involve combinatorial problems. For instance, a probabilistic parser may marginalize over exponentially many trees to make predictions.…
What Kind of Language Is Hard to Language-Model?
Sabrina J. Mielke, Ryan Cotterell, Kyle Gorman +2
How language-agnostic are current state-of-the-art NLP tools? Are there some types of language that are easier to model with current methods? In prior work (Cotterell et al., 2018)…
Finite-State Phonology: Proceedings of the 5th Workshop of the ACL Special Interest Group in Computational Phonology (SIGPHON)
Jason Eisner, Lauri Karttunen, Alain Theriault
Home page of the workshop proceedings, with pointers to the individually archived papers. Includes front matter from the printed version of the proceedings.
Interpreting User Requests in the Context of Natural Language Standing Instructions
Nikita Moghe, Patrick Xia, Jacob Andreas +3
Users of natural language interfaces, generally powered by Large Language Models (LLMs),often must repeat their preferences each time they make a similar request. We describe an ap…
Imputing Missing Events in Continuous-Time Event Streams
Hongyuan Mei, Guanghui Qin, Jason Eisner
Events in the world may be caused by other, unobserved events. We consider sequences of events in continuous time. Given a probability model of complete sequences, we propose parti…
SCREWS: A Modular Framework for Reasoning with Revisions
Kumar Shridhar, Harsh Jhamtani, Hao Fang +3
Large language models (LLMs) can improve their accuracy on various tasks through iteratively refining and revising their output based on feedback. We observe that these revisions c…
Approximation-Aware Dependency Parsing by Belief Propagation
Matthew R. Gormley, Mark Dredze, Jason Eisner
We show how to train the fast dependency parser of Smith and Eisner (2008) for improved accuracy. This parser can consider higher-order interactions among edges while retaining O(n…
Easy and Hard Constraint Ranking in OT: Algorithms and Complexity
Jason Eisner
We consider the problem of ranking a set of OT constraints in a manner consistent with data. We speed up Tesar and Smolensky's RCD algorithm to be linear on the number of constrain…
The Galactic Dependencies Treebanks: Getting More Data by Synthesizing New Languages
Dingquan Wang, Jason Eisner
We release Galactic Dependencies 1.0---a large set of synthetic languages not found on Earth, but annotated in Universal Dependencies format. This new resource aims to provide trai…
A Corpus for Large-Scale Phonetic Typology
Elizabeth Salesky, Eleanor Chodroff, Tiago Pimentel +4
A major hurdle in data-driven research on typology is having sufficient data in many languages to draw meaningful conclusions. We present VoxClamantis v1.0, the first large-scale c…
LLMs Know More About Numbers than They Can Say
Fengting Yuchi, Li Du, Jason Eisner
Although state-of-the-art LLMs can solve math problems, we find that they make errors on numerical comparisons with mixed notation: "Which is larger, or ?" T…
Evaluation of Logic Programs with Built-Ins and Aggregation: A Calculus for Bag Relations
Matthew Francis-Landau, Tim Vieira, Jason Eisner
We present a scheme for translating logic programs, which may use aggregation and arithmetic, into algebraic expressions that denote bag relations over ground terms of the Herbrand…
On the Complexity and Typology of Inflectional Morphological Systems
Ryan Cotterell, Christo Kirov, Mans Hulden +1
We quantify the linguistic complexity of different languages' morphological systems. We verify that there is an empirical trade-off between paradigm size and irregularity: a langua…
Transformer Embeddings of Irregularly Spaced Events and Their Participants
Chenghao Yang, Hongyuan Mei, Jason Eisner
The neural Hawkes process (Mei & Eisner, 2017) is a generative model of irregularly spaced sequences of discrete events. To handle complex domains with many event types, Mei et al.…
MICE for CATs: Model-Internal Confidence Estimation for Calibrating Agents with Tools
Nishant Subramani, Jason Eisner, Justin Svegliato +3
Tool-using agents that act in the world need to be both useful and safe. Well-calibrated model confidences can be used to weigh the risk versus reward of potential actions, but pri…
Toward Interactive Dictation
Belinda Z. Li, Jason Eisner, Adam Pauls +1
Voice dictation is an increasingly important text input modality. Existing systems that allow both dictation and editing-by-voice restrict their command language to flat templates…
Accelerating Language Model Workflows with Prompt Choreography
TJ Bai, Jason Eisner
Large language models are increasingly deployed in multi-agent workflows. We introduce Prompt Choreography, a framework that efficiently executes LLM workflows by maintaining a dyn…
BenchCLAMP: A Benchmark for Evaluating Language Models on Syntactic and Semantic Parsing
Subhro Roy, Sam Thomson, Tongfei Chen +4
Recent work has shown that generation from a prompted or fine-tuned language model can perform well at semantic parsing when the output is constrained to be a valid semantic repres…
Privacy-Preserving Domain Adaptation of Semantic Parsers
Fatemehsadat Mireshghallah, Yu Su, Tatsunori Hashimoto +2
Task-oriented dialogue systems often assist users with personal or confidential matters. For this reason, the developers of such a system are generally prohibited from observing ac…
Constrained Language Models Yield Few-Shot Semantic Parsers
Richard Shin, Christopher H. Lin, Sam Thomson +7
We explore the use of large pretrained language models as few-shot semantic parsers. The goal in semantic parsing is to generate a structured meaning representation given a natural…
Neural Particle Smoothing for Sampling from Conditional Sequence Models
Chu-Cheng Lin, Jason Eisner
We introduce neural particle smoothing, a sequential Monte Carlo method for sampling annotations of an input string from a given probability model. In contrast to conventional part…
UniMorph 2.0: Universal Morphology
Christo Kirov, Ryan Cotterell, John Sylak-Glassman +10
The Universal Morphology UniMorph project is a collaborative effort to improve how NLP handles complex morphology across the world's languages. The project releases annotated morph…
Syntactic and Semantic Control of Large Language Models via Sequential Monte Carlo
João Loula, Benjamin LeBrun, Li Du +12
A wide range of LM applications require generating text that conforms to syntactic or semantic constraints. Imposing such constraints can be naturally framed as probabilistic condi…
Learning to Retrieve Iteratively for In-Context Learning
Yunmo Chen, Tongfei Chen, Harsh Jhamtani +4
We introduce iterative retrieval, a novel framework that empowers retrievers to make iterative decisions through policy optimization. Finding an optimal portfolio of retrieved item…
Contrastive Decoding: Open-ended Text Generation as Optimization
Xiang Lisa Li, Ari Holtzman, Daniel Fried +5
Given a language model (LM), maximum probability is a poor decoding objective for open-ended generation, because it produces short and repetitive text. On the other hand, sampling…
An Empirical Comparison of Probability Models for Dependency Grammar
Jason Eisner
This technical report is an appendix to Eisner (1996): it gives superior experimental results that were reported only in the talk version of that paper. Eisner (1996) trained three…
Neural Datalog Through Time: Informed Temporal Modeling via Logical Specification
Hongyuan Mei, Guanghui Qin, Minjie Xu +1
Learning how to predict future events from patterns of past events is difficult when the set of possible event types is large. Training an unrestricted neural model might overfit t…
The CoNLL--SIGMORPHON 2018 Shared Task: Universal Morphological Reinflection
Ryan Cotterell, Christo Kirov, John Sylak-Glassman +10
The CoNLL--SIGMORPHON 2018 shared task on supervised learning of morphological generation featured data sets from 103 typologically diverse languages. Apart from extending the numb…
Contextualization of Morphological Inflection
Ekaterina Vylomova, Ryan Cotterell, Timothy Baldwin +2
Critical to natural language generation is the production of correctly inflected text. In this paper, we isolate the task of predicting a fully inflected sentence from its partiall…
Fast Controlled Generation from Language Models with Adaptive Weighted Rejection Sampling
Benjamin Lipkin, Benjamin LeBrun, Jacob Hoover Vigly +9
The dominant approach to generating from language models subject to some constraint is locally constrained decoding (LCD), incrementally sampling tokens at each time step such that…
Let's Think Var-by-Var: Large Language Models Enable Ad Hoc Probabilistic Reasoning
Shepard Xia, Brian Lu, Jason Eisner
A hallmark of intelligence is the ability to flesh out underspecified situations using "common sense." We propose to extract that common sense from large language models (LLMs), in…
A Measure-Theoretic Characterization of Tight Language Models
Li Du, Lucas Torroba Hennigen, Tiago Pimentel +3
Language modeling, a central task in natural language processing, involves estimating a probability distribution over strings. In most cases, the estimated distribution sums to 1 o…
Three New Probabilistic Models for Dependency Parsing: An Exploration
Jason Eisner
After presenting a novel O(n^3) parsing algorithm for dependency grammar, we develop three contrasting ways to stochasticize it. We propose (a) a lexical affinity model where words…
Decision-Oriented Dialogue for Human-AI Collaboration
Jessy Lin, Nicholas Tomlin, Jacob Andreas +1
We describe a class of tasks called decision-oriented dialogues, in which AI assistants such as large language models (LMs) must collaborate with one or more humans via natural lan…