Profiting from Mark-Up: Hyper-Text Annotations for Guided Parsing

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 1278–1287, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics Profiting from Mark-Up: Hyper-Text Annotations for Guided Parsing Valentin I. Spitkovsky Computer Science Department Stanford University and Google Inc. valentin@google.com Daniel Jurafsky Departments of Linguistics and Computer Science, Stanford University jurafsky@stanford.edu Hiyan Alshawi Google Inc. hiyan@google.com Abstract We show how web mark-up can be used to improve unsupervised dependency pars- ing. Starting from raw bracketings of four common HTML tags (anchors, bold, ital- ics and underlines), we refine approximate partial phrase boundaries to yield accurate parsing constraints. Conversion proce- dures fall out of our linguistic analysis of a newly available million-word hyper-text corpus. We demonstrate that derived con- straints aid grammar induction by training Klein and Manning’s Dependency Model with Valence (DMV) on this data set: pars- ing accuracy on Section 23 (all sentences) of the Wall Street Journal corpus jumps to 50.4%, beating previous state-of-the- art by more than 5%. Web-scale exper- iments show that the DMV, perhaps be- cause it is unlexicalized, does not benefit from orders of magnitude more annotated but noisier data. Our model, trained on a single blog, generalizes to 53.3% accuracy out-of-domain, against the Brown corpus — nearly 10% higher than the previous published best. The fact that web mark-up strongly correlates with syntactic structure may have broad applicability in NLP. 1 Introduction Unsupervised learning of hierarchical syntactic structure from free-form natural language text is a hard problem whose eventual solution promises to benefit applications ranging from question an- swering to speech recognition and machine trans- lation. A restricted version of this problem that tar- gets dependencies and assumes partial annotation — sentence boundaries and part-of-speech (POS) tagging — has received much attention. Klein and Manning (2004) were the first to beat a sim- ple parsing heuristic, the right-branching baseline; today’s state-of-the-art systems (Headden et al., 2009; Cohen and Smith, 2009; Spitkovsky et al., 2010a) are rooted in their Dependency Model with Valence (DMV), still trained using variants of EM. Pereira and Schabes (1992) outlined three ma- jor problems with classic EM, applied to a related problem, constituent parsing. They extended clas- sic inside-outside re-estimation (Baker, 1979) to respect any bracketing constraints included with a training corpus. This conditioning on partial parses addressed all three problems, leading to: (i) linguistically reasonable constituent boundaries and induced grammars more likely to agree with qualitative judgments of sentence structure, which is underdetermined by unannotated text; (ii) fewer iterations needed to reach a good grammar, coun- tering convergence properties that sharply deterio- rate with the number of non-terminal symbols, due to a proliferation of local maxima; and (iii) better (in the best case, linear) time complexity per it- eration, versus running time that is ordinarily cu- bic in both sentence length and the total num- ber of non-terminals, rendering sufficiently large grammars computationally impractical. Their al- gorithm sometimes found good solutions from bracketed corpora but not from raw text, sup- porting the view that …

Content truncated to 500 words