It Depends on the Translation: Unsupervised Dependency Parsing via Word Alignment

Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 1214–1222, MIT, Massachusetts, USA, 9-11 October 2010. c⃝2010 Association for Computational Linguistics It Depends on the Translation: Unsupervised Dependency Parsing via Word Alignment Samuel Brody Dept. of Biomedical Informatics Columbia University samuel.brody@dbmi.columbia.edu Abstract We reveal a previously unnoticed connection between dependency parsing and statistical machine translation (SMT), by formulating the dependency parsing task as a problem of word alignment. Furthermore, we show that two well known models for these respective tasks (DMV and the IBM models) share com- mon modeling assumptions. This motivates us to develop an alignment-based framework for unsupervised dependency parsing. The frame- work (which will be made publicly available) is flexible, modular and easy to extend. Us- ing this framework, we implement several al- gorithms based on the IBM alignment mod- els, which prove surprisingly effective on the dependency parsing task, and demonstrate the potential of the alignment-based approach. 1 Introduction Both statistical machine translation (SMT) and un- supervised dependency parsing have seen a surge of interest in recent years, as the need for large scale data processing has increased. The problems ad- dressed by each of the fields seem quite different at first glance. However, in this paper, we reveal a strong connection between them and show that the problem of dependency parsing can be formulated as one of word alignment within the sentence. Fur- thermore, we show that the two models that are ar- guably the most influential in their respective fields, the IBM models 1-3 (Brown et al., 1993) and Klein and Manning’s (2004) Dependency Model with Va- lence (DMV), share a common set of modeling as- sumptions. Based on this connection, we develop a frame- work which uses an alignment-based approach for unsupervised dependency parsing. The framework is flexible and modular, and allows us to explore dif- ferent modeling assumptions. We demonstrate these properties and the merit of the alignment-based pars- ing approach by implementing several dependency parsing algorithms based on the IBM alignment models and evaluating their performance on the task. Although the algorithms are not competitive with state-of-the-art systems, they outperform the right- branching baseline and approach the performance of DMV. This is especially surprising when we con- sider that the IBM models were not originally de- signed for the task. These results are encourag- ing and indicate that the alignment-based approach could serve as the basis for competitive dependency parsing systems, much as DMV did. This paper offers two main contributions. First, by revealing the connection between the two tasks, we introduce a new approach to dependency pars- ing, and open the way for use of SMT alignment re- sources and tools for parsing. Our experiments with the IBM models demonstrate the potential of this ap- proach and provide a strong motivation for further development. The second contribution is a publicly- available framework for exploring new alignment models. The framework uses Gibbs sampling tech- niques and includes our sampling-based implemen- tations of the IBM models (see Section …

Content truncated to 500 words