David Leo Wright Hall

@inproceedings{durrett2013entity,
  author = {Greg Durrett and David Hall and Dan Klein},
  title = {Entity-Level Coreference Features via Belief Propagation},
  year = {2013}, 
  booktitle = {ACL}
}

Effectively incorporating entity-level information has long been a goal of designers of coreference systems. Unlike previous approaches which use sieves or pipelines, we formulate a purely probabilistic discriminative model combining traditional pairwise features and new entity-level constraints on the agreement of latent properties. Using belief propagation, we can efficiently perform joint inference over a whole document. We show that information obtained from unsupervised clustering can be an effective entity-level feature, and incorporating this via our propagation mechanism results in gains of up to 1.1% on the CoNLL shared task evaluation metrics over a baseline coreference system.

@inproceedings{chang2013dating,
  author = {Will Chang and David Hall and Chundra Cathcart andAndrew Garrett },
  title = {Dating Proto-Indo-European: A revised computational analysis supports the steppe hypothesis},
  year = {2013}, 
  booktitle = {International Conference on Historical Linguistics}
}

There are two hypotheses regarding the origin of the Indo-European language family. The Steppe Hypothesis is favored by linguists and many archaelogists. The other is the Anatolian hypothesis, which was proposed by Renfrew. This latter hypothesis enjoys the support of computational methods for dating languages, to the consternation of most historical linguists. We identify a number of mismatches between the data and the models used so far, and show that by fixing these inconsistencies, we wind up with a chronology that strongly favors the Steppe Hypothesis.

@inproceedings{hall2013imba,
  author = {David Hall and Aloni Cohen and David Burkett and and Dan Klein},
  title = {Faster Optimal Planning with Partial-Order Pruning},
  year = {2013}, 
  booktitle = {ICAPS}
}

When planning problems have many kinds of resources or high concurrency, each optimal state has exponentially many minor variants, some of which are “better” than others. Standard methods like A* cannot effectively exploit these minor relative differences, and therefore must explore many redundant, clearly suboptimal plans. We describe a new optimal search algorithm for planning that leverages a partial order relation between states. Under suitable conditions, states that are dominated by other states with respect to this order can be pruned while provably maintaining optimality. We also describe a simple method for automatically discovering compatible partial orders in both serial and concurrent domains. In our experiments we find that more than 90% of search states can be pruned in some domains.

@article{Bouchard-C\^ot\'e11022013,
author = {Bouchard-C\^ot\'e, Alexandre and Hall, David and Griffiths, Thomas L. and Klein, Dan}, 
title = {Automated reconstruction of ancient languages using probabilistic models of sound change},
year = {2013}, 
doi = {10.1073/pnas.1204678110}, 
abstract =, 
URL = {http://www.pnas.org/content/early/2013/02/05/1204678110.abstract}, 
eprint = {http://www.pnas.org/content/early/2013/02/05/1204678110.full.pdf+html}, 
journal = {Proceedings of the National Academy of Sciences} 
}

One of the oldest problems in linguistics is reconstructing the words that appeared in the protolanguages from which modern languages evolved. Identifying the forms of these ancient languages makes it possible to evaluate proposals about the nature of language change and to draw inferences about human history. Protolanguages are typically reconstructed using a painstaking manual process known as the comparative method. We present a family of probabilistic models of sound change as well as algorithms for performing inference in these models. The resulting system automatically and accurately reconstructs protolanguages from modern languages. We apply this system to 637 Austronesian languages, providing an accurate, large-scale automatic reconstruction of a set of protolanguages. Over 85% of the system’s reconstructions are within one character of the manual reconstruction provided by a linguist specializing in Austronesian languages. Being able to automatically reconstruct large numbers of languages provides a useful way to quantitatively explore hypotheses about the factors determining which sounds in a language are likely to change over time. We demonstrate this by showing that the reconstructed Austronesian protolanguages provide compelling support for a hypothesis about the relationship between the function of a sound and its probability of changing that was first proposed in 1955.

@inproceedings{hall12epic,
  title = {Training Factored PCFGs with Expectation Propagation},
  author = {David Hall and Dan Klein},
  booktitle = {EMNLP},
  year = {2012}
}
    

PCFGs can grow exponentially as additional annotations are added to an initially simple base grammar. We present an approach where multiple annotations coexist, but in a factored manner that avoids this combinatorial explosion. Our method works with linguistically-motivated annotations, induced latent structure, lexicalization, or any mix of the three. We use a structured expectation propagation algorithm that makes use of the factored structure in two ways. First, by partitioning the factors, it speeds up parsing exponentially over the unfactored approach. Second, it minimizes the redundancy of the factors during training, improving accuracy over an independent approach. Using purely latent variable annotations, we can efficiently train and parse with up to 8 latent bits per symbol, achieving F1 scores up to 88.4 on the Penn Treebank while using two orders of magnitudes fewer parameters compared to the na\"ive approach. Combining latent, lexicalized, and unlexicalized annotations, our best parser gets 89.4 F1 on all sentences from section 23 of the Penn Treebank.

@inproceedings{kummerfeld12analysis,
  title = {Parser Showdown at the Wall Street Corral: An Empirical Investigation of Error Types in Parser Output},
  author = {Jonathan K. Kummerfeld and David Hall and James R. Curran and Dan Klein},
  booktitle = {EMNLP},
  year = {2012}
}
    

Constituency parser performance is primarily interpreted through a single metric, F-score on WSJ section 23, that conveys no linguistic information regarding the remaining errors. We classify errors within a set of linguistically meaningful types using tree transformations that repair groups of errors together. We use this analysis to answer a range of questions about parser behaviour, including what linguistic constructions are difficult for state- of-the-art parsers, what types of errors are being resolved by rerankers, and what types are introduced when parsing out-of-domain text.

@inproceedings{burkett11imba,
  title = {Iterative Monotonically Bounded A*},
  author = {David Burkett and David Hall and Dan Klein},
  booktitle = {AAAI},
  year = {2011}
}
    

Informed search algorithms such as A* use heuristics to focus exploration on states with low total path cost. To the extent that heuristics underestimate forward costs, a wider cost radius of suboptimal states will be explored. For many weighted graphs, however, a small distance in terms of cost may encompass a large fraction of the unweighted graph. We present a new informed search algorithm, Iterative Monotonically Bounded A* (IMBA*), which first proves that no optimal paths exist in a bounded cut of the graph before considering larger cuts. We prove that IMBA* has the same optimality and completeness guarantees as A* and, in a non-uniform pathfinding application, we empirically demonstrate substantial speed improvements over classic A*.

@inproceedings{hall11largescale,
  title = {Large-Scale Cognate Recovery},
  author = {David Hall and Dan Klein},
  booktitle = {Empirical Methods in Natural Language Processing (EMNLP)},
  year = {2011}
}
    

We present a system for the large scale induction of cognate groups. Our model explains the evolution of cognates as a sequence of mutations and innovations along a phylogeny. On the task of identifying cognates from over 21,000 words in 218 different languages from the Oceanic language family, our model achieves a cluster purity score over 91%, while maintaining pairwise recall over 62%.

@inproceedings{hall10cognates,
  title = {Finding Cognates using Phylogenies},
  author = {David Hall and Dan Klein},
  booktitle = {Association for Computational Linguistics (ACL)},
  year = {2010}
}
    

We automate the comparative method from historical linguistics by modeling the evolution of words from a source language through their phylogenetic tree. Using this model, we can automatically identify words which are cognate with one another. We also introduce mechanisms for making inference over string-valued random variables more tractable.