Daniel Marcu

AAAI Conference 2018 Conference Paper

Learning Interpretable Spatial Operations in a Rich 3D Blocks World

• Yonatan Bisk
• Kevin Shih
• Yejin Choi
• Daniel Marcu

In this paper, we study the problem of mapping natural language instructions to complex spatial actions in a 3D blocks world. We first introduce a new dataset that pairs complex 3D spatial operations to rich natural language descriptions that require complex spatial and pragmatic interpretations such as “mirroring”, “twisting”, and “balancing”. This dataset, built on the simulation environment of Bisk, Yuret, and Marcu (2016), attains language that is significantly richer and more complex, while also doubling the size of the original dataset in the 2D environment with 100 new world configurations and 250,000 tokens. In addition, we propose a new neural architecture that achieves competitive results while automatically discovering an inventory of interpretable spatial operations (Figure 5).

AAAI Conference 2017 Conference Paper

Progressive Prediction of Student Performance in College Programs

• Jie Xu
• Yuli Han
• Daniel Marcu
• Mihaela van der Schaar

Accurately predicting students’ future performance based on their tracked academic records in college programs is crucial for effectively carrying out necessary pedagogical interventions to ensure students’ on-time graduation. Although there is a rich literature on predicting student performance in solving problems and studying courses using data-driven approaches, predicting student performance in completing college programs is much less studied and faces new challenges, mainly due to the diversity of courses selected by students and the requirement of continuous tracking and incorporation of students’ evolving progresses. In this paper, we develop a novel algorithm that enables progressive prediction of students’ performance by adapting ensemble learning techniques and utilizing education-specific domain knowledge. We prove its prediction performance guarantee and show its performance improvement against benchmark algorithms on a real-world student dataset from UCLA.

AAAI Conference 2016 Conference Paper

Extracting Biomolecular Interactions Using Semantic Parsing of Biomedical Text

• Sahil Garg
• Aram Galstyan
• Ulf Hermjakob
• Daniel Marcu

We advance the state of the art in biomolecular interaction extraction with three contributions: (i) We show that deep, Abstract Meaning Representations (AMR) significantly improve the accuracy of a biomolecular interaction extraction system when compared to a baseline that relies solely on surfaceand syntax-based features; (ii) In contrast with previous approaches that infer relations on a sentence-by-sentence basis, we expand our framework to enable consistent predictions over sets of sentences (documents); (iii) We further modify and expand a graph kernel learning framework to enable concurrent exploitation of automatically induced AMR (semantic) and dependency structure (syntactic) representations. Our experiments show that our approach yields interaction extraction systems that are more robust in environments where there is a significant mismatch between training and test conditions.

JMLR Journal 2005 Journal Article

A Bayesian Model for Supervised Clustering with the Dirichlet Process Prior

• Hal Daumé III
• Daniel Marcu

We develop a Bayesian framework for tackling the supervised clustering problem, the generic problem encountered in tasks such as reference matching, coreference resolution, identity uncertainty and record linkage. Our clustering model is based on the Dirichlet process prior, which enables us to define distributions over the countably infinite sets that naturally arise in this problem. We add supervision to our model by positing the existence of a set of unobserved random variables (we call these "reference types") that are generic across all clusters. Inference in our framework, which requires integrating over infinitely many parameters, is solved using Markov chain Monte Carlo techniques. We present algorithms for both conjugate and non-conjugate priors. We present a simple---but general---parameterization of our model based on a Gaussian assumption. We evaluate this model on one artificial task and three real-world tasks, comparing it against both unsupervised and state-of-the-art supervised algorithms. Our results show that our model is able to outperform other models across a variety of tasks and performance metrics. [abs] [ pdf ][ bib ] &copy JMLR 2005. ( edit, beta )

ICML Conference 2005 Conference Paper

Learning as search optimization: approximate large margin methods for structured prediction

• Hal Daumé III
• Daniel Marcu

AIJ Journal 2004 Journal Article

Fast and optimal decoding for machine translation

• Ulrich Germann
• Michael Jahr
• Kevin Knight
• Daniel Marcu
• Kenji Yamada

A good decoding algorithm is critical to the success of any statistical machine translation system. The decoder's job is to find the translation that is most likely according to a set of previously learned parameters (and a formula for combining them). Since the space of possible translations is extremely large, typical decoding algorithms are only able to examine a portion of it, thus risking to miss good solutions. Unfortunately, examining more of the space leads to unacceptably slow decodings. In this paper, we compare the speed and output quality of a traditional stack-based decoding algorithm with two new decoders: a fast but non-optimal greedy decoder and a slow but optimal decoder that treats decoding as an integer-programming optimization problem.

AIJ Journal 2002 Journal Article

Summarization beyond sentence extraction: A probabilistic approach to sentence compression

• Kevin Knight
• Daniel Marcu

When humans produce summaries of documents, they do not simply extract sentences and concatenate them. Rather, they create new sentences that are grammatical, that cohere with one another, and that capture the most salient pieces of information in the original document. Given that large collections of text/abstract pairs are available online, it is now possible to envision algorithms that are trained to mimic this process. In this paper, we focus on sentence compression, a simpler version of this larger challenge. We aim to achieve two goals simultaneously: our compressions should be grammatical, and they should retain the most important pieces of information. These two goals can conflict. We devise both a noisy-channel and a decision-tree approach to the problem, and we evaluate results against manual compressions and a simple baseline.

AAAI Conference 1997 Conference Paper

From Local to Global Coherence: A Bottom-Up Approach to Text Planning

• Daniel Marcu

We present a new, data-driven approach to text planning, which can be used not only to map full knowledge pools into natural language texts, but also to generate texts that satisfy multiple, high-level communicative goals. The approach explains how global coherence can be achieved by exploiting the local coherence constraints of rhetorical relations. The local constraints were derived from a corpus analysis. All current flexible approaches to text planning that assume that the abstract structure of text is a tree-like structure are, esentially, top-down approaches. Some of them define plan operators and exploit hierarchical planning techniques (Hovy 1993; Moore and Paris 1993; Moore and Swartout 1991; Cawsey 1991; Maybury 1992) and partial-order planning techniques (Young and Moore 1994). Others assume that plans are hierarchically organized sets of frames that can be derived through a top-down expansion process (Nirenburg et al. 1989; Meteer 1992). And the recursive application of schemata (McKeown 1985) can be thought of as a top-down expansion process as well. One of the major strengths of all these approaches is that, given a high-level communicative goal, they can interleave the task of text planning and content selection, and produce different texts for different knowledge bases and users (McKeown 1985; Paris 1991; McCoy and Cheng 1991; Moore and Swartout 1991). Unfortunately, this strength is also a major weakness, because top-down and schema-based approaches are inadequate when the highlevel communicative goal boils down to “tell everything that is in this knowledge base or everything that is in this chosen subset”. The reason for this inadequacy is that these approaches cannot ensure that all the knowledge that makes up a knowledge pool will be eventually mapped into the leaves of the resulting text plan: after building a partial text plan, which encodes a certain amount of the information found in the initial knowledge pool, it is highly possible that the information that is still unrealized will satisfy none of the active communicative goals. In fact, because the plan construction is plan-operator- or schema-step-driven, Copyright @ 1997, American Association for Artificial Intelligence (www. ai. org). AU rights reserved. top-down approaches cannot even predict what amount of the initial knowledge pool will be mapped into text when a certain communicative goal is chosen. The only way to find a text plan that is maximal with respect to the amount of knowledge that is mapped into text is to quantify over all possible high-level communicative goals and over all plans that can be built starting from them, but this is unreasonable. Given that most natural language generation (NLG) systems employ a pipeline architecture in which content determination and text planning are treated as separate processes (Reiter 1994), we believe that it is critical to provide a flexible solution to the problem of mapping a full knowledge base (or any of its chosen subsets) into text. Previous research in text planning has addressed this issue only for text genres in which the ordering of sentences is very rigid (geographical descriptions (Carbone11 and Collins 1973), stories (Schank and Abelson 1977), and fables (Meehan 1977)) has assumed that text plans can be assimilated with linear sequences of textual units (Mann and Moore 1981; Zukerman and McConachy 1993), or has employed very restricted sets of rhetorical relations (Zukerman and Mc- Conachy 1993). Unfortunately, the linear structure of text plans is not sophisticated enough for managing satisfactorily a whole collection of linguistic phenomena such as focus, reference, and intentions, which are characterized adequately by tree-like text plans (Hovy 1993; Moore and Paris 1993; Moore and Swartout 1991; Cawsey 1991; Paris 1991; McCoy and Cheng 1991). In this paper we provide a bottom-up, data-driven solution for the text planning problem that implements the full collection of rhetorical relations that was proposed by Mann and Thompson (1988) and that accommodates the hierarchical structure of discourse. The algorithms that we propose not only map a knowledge pool into text plans whose leaves subsume all the information given in the knowledge pool, but can also ensure that the resulting plans satisfy multiple high-level communicative goals. RDun

ECAI Conference 1996 Conference Paper

A Formal and Computational Characterization of Pragmatic Infelicities

• Daniel Marcu
• Graeme Hirst

AAAI Conference 1996 Conference Paper

Building Up Rhetorical Structure Trees

• Daniel Marcu

I use the distinction between the nuclei and the satellites that pertain to discourse relations to introduce a compositionality criterion for discourse trees. I provide a first-order formalization of rhetorical structure trees and, on its basis, I derive an algorithm that constructs all the valid rhetorical trees that can be associated with a given discourse.