Three Dependency-and-Boundary Models for Grammar Induction

Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 688–698, Jeju Island, Korea, 12–14 July 2012. c⃝2012 Association for Computational Linguistics Three Dependency-and-Boundary Models for Grammar Induction Valentin I. Spitkovsky Stanford University and Google Inc. valentin@cs.stanford.edu Hiyan Alshawi Google Inc., Mountain View, CA, 94043 hiyan@google.com Daniel Jurafsky Stanford University, Stanford, CA, 94305 jurafsky@stanford.edu Abstract We present a new family of models for unsu- pervised parsing, Dependency and Boundary models, that use cues at constituent bound- aries to inform head-outward dependency tree generation. We build on three intuitions that are explicit in phrase-structure grammars but only implicit in standard dependency formu- lations: (i) Distributions of words that oc- cur at sentence boundaries — such as English determiners — resemble constituent edges. (ii) Punctuation at sentence boundaries fur- ther helps distinguish full sentences from fragments like headlines and titles, allow- ing us to model grammatical differences be- tween complete and incomplete sentences. (iii) Sentence-internal punctuation boundaries help with longer-distance dependencies, since punctuation correlates with constituent edges. Our models induce state-of-the-art depen- dency grammars for many languages without special knowledge of optimal input sentence lengths or biased, manually-tuned initializers. 1 Introduction Natural language is ripe with all manner of bound- aries at the surface level that align with hierarchical syntactic structure. From the significance of func- tion words (Berant et al., 2006) and punctuation marks (Seginer, 2007; Ponvert et al., 2010) as sepa- rators between constituents in longer sentences — to the importance of isolated words in children’s early vocabulary acquisition (Brent and Siskind, 2001) — word boundaries play a crucial role in language learning. We will show that boundary information can also be useful in dependency grammar induc- tion models, which traditionally focus on head rather than fringe words (Carroll and Charniak, 1992). DT NN VBZ IN DT NN [The check] is in [the mail]. � �� � Subject � �� � Object Figure 1: A partial analysis of our running example. Consider the example in Figure 1. Because the determiner (DT) appears at the left edge of the sen- tence, it should be possible to learn that determiners may generally be present at left edges of phrases. This information could then be used to correctly parse the sentence-internal determiner in the mail. Similarly, the fact that the noun head (NN) of the ob- ject the mail appears at the right edge of the sentence could help identify the noun check as the right edge of the subject NP. As with jigsaw puzzles, working inwards from boundaries helps determine sentence- internal structures of both noun phrases, neither of which would be quite so clear if viewed separately. Furthermore, properties of noun-phrase edges are partially shared with prepositional- and verb-phrase units that contain these nouns. Because typical head- driven grammars model valence separately for each class of head, however, they cannot see that the left fringe boundary, The check, of the verb-phrase is shared with its daughter’s, check. Neither of these insights is …

Content truncated to 500 words