Trends in Parsing Technology (eBook)

Trends in Parsing Technology (eBook)

Computer parsing technology, which breaks down complex linguistic structures into their constituent parts, is a key research area in the automatic processing of human language. This volume is a collection of contributions from leading researchers in the field of natural language processing technology, each of whom detail their recent work which includes new techniques as well as results. The book presents an overview of the state of the art in current research into parsing technologies, focusing on three important themes: dependency parsing, domain adaptation, and deep parsing. The technology, which has a variety of practical uses, is especially concerned with the methods, tools and software that can be used to parse automatically. Applications include extracting information from free text or speech, question answering, speech recognition and comprehension, recommender systems, machine translation, and automatic summarization. New developments in the area of parsing technology are thus widely applicable, and researchers and professionals from a number of fields will find the material here required reading. As well as the other four volumes on parsing technology in this series this book has a breadth of coverage that makes it suitable both as an overview of the field for graduate students, and as a reference for established researchers in computational linguistics, artificial intelligence, computer science, language engineering, information science, and cognitive science. It will also be of interest to designers, developers, and advanced users of natural language processing systems, including applications such as spoken dialogue, text mining, multimodal human-computer interaction, and semantic web technology.

---

Inhaltsangabe

1;Contents;6 2;Contributors;8 3;1 Current Trends in Parsing Technology ;11 3.1;1.1 Introduction;11 3.2;1.2 Current Trends in Parsing Research;12 3.2.1;1.2.1 Parsing with Dependencies;12 3.2.2;1.2.2 Reducing Supervision;13 3.2.3;1.2.3 Latent Variables;14 3.3;1.3 Tour of the Volume;14 3.3.1;1.3.1 Cross-Cutting Threads;15 3.3.2;1.3.2 The Chapters in Short;16 3.4;1.4 The Future of Parsing and Parsing Technologies;21 3.5;References;23 4;2 Single Malt or Blended? A Study in Multilingual Parser Optimization ;28 4.1;2.1 Introduction;28 4.2;2.2 Data-Driven Dependency Parsing;29 4.2.1;2.2.1 Dependency Graph;29 4.2.2;2.2.2 MaltParser;30 4.2.3;2.2.3 Pseudo-Projective Parsing;32 4.2.4;2.2.4 Parser Combination;32 4.3;2.3 The CoNLL Shared Task 2007;33 4.4;2.4 The Single Malt Parser;34 4.4.1;2.4.1 Parsing Algorithm;35 4.4.2;2.4.2 Feature Model;36 4.4.3;2.4.3 Learning Algorithm;37 4.5;2.5 The Blended Parser;38 4.6;2.6 Results and Discussion;39 4.7;2.7 Conclusion;40 4.8;References;41 5;3 A Latent Variable Model for Generative Dependency Parsing;43 5.1;3.1 Introduction;43 5.2;3.2 The Latent Variable Architecture;45 5.2.1;3.2.1 Incremental Sigmoid Belief Networks;45 5.2.2;3.2.2 Modeling Structures with ISBNs;46 5.2.3;3.2.3 Approximating ISBNs;47 5.2.4;3.2.4 Learning;47 5.3;3.3 The Dependency Parsing Algorithm;48 5.4;3.4 An ISBN for Dependency Parsing;50 5.5;3.5 Searching for the Best Tree;52 5.6;3.6 Empirical Evaluation;53 5.6.1;3.6.1 Experimental Setup for the CoNLL-2006 Data;53 5.6.2;3.6.2 Discussion of Results on the CoNLL-2006 Data;55 5.6.3;3.6.3 The CoNLL-2007 Experiments;57 5.7;3.7 Related Work;59 5.8;3.8 Conclusions;60 5.9;References;61 6;4 Dependency Parsing and Domain Adaptation with Data-Driven LR Models and Parser Ensembles ;64 6.1;4.1 Introduction;64 6.2;4.2 A Data-Driven Probabilistic LR Approach for Dependency Parsing;66 6.2.1;4.2.1 Dependency Parsing with a Data-Driven Variant of the LR Algorithm;67 6.2.2;4.2.2 A Probabilistic LR Model for Dependency Parsing;67 6.3;4.3 Multilingual Parsing Experiments;68 6.3.1;4.3.1 Classifier Features;69 6.4;4.4 Domain Adaptation Experiments;70 6.5;4.5 Analysis and Discussion;71 6.6;4.6 Conclusion;72 6.7;References;73 7;5 Dependency Parsing Using Global Features ;76 7.1;5.1 Introduction;76 7.2;5.2 Unlabeled Dependency Parsing Using Global Features;76 7.2.1;5.2.1 Probabilistic Model;77 7.2.2;5.2.2 Decoding with Gibbs Sampling;79 7.2.3;5.2.3 Parameter Estimation;81 7.2.4;5.2.4 Local Features;82 7.2.5;5.2.5 Global Features;83 7.3;5.3 Dependency Relation Labeling;85 7.3.1;5.3.1 Model;85 7.3.2;5.3.2 Features;85 7.4;5.4 Experiments;85 7.4.1;5.4.1 Experiments on the CoNLL 2007 Shared Task Dataset;86 7.4.2;5.4.2 Experiments on the CoNLL-X Shared Task Dataset;87 7.4.3;5.4.3 Experiments on the WSJ Corpus;88 7.5;5.5 Related Work;90 7.6;5.6 Conclusion;91 7.7;References;91 8;6 Dependency Parsing with Second-Order Feature Maps and Annotated Semantic Information;94 8.1;6.1 Introduction;94 8.2;6.2 Dependency Parsing;95 8.3;6.3 A Shift-Reduce Parser;96 8.3.1;6.3.1 Parsing Algorithm;96 8.3.2;6.3.2 Features;98 8.3.3;6.3.3 Learning a Parsing Model with the Perceptron;98 8.3.4;6.3.4 Higher-Order Feature Spaces;99 8.4;6.4 Semantic Features;101 8.4.1;6.4.1 BBN Entity Corpus;101 8.4.2;6.4.2 Corpus Pre-processing;104 8.4.3;6.4.3 Semantic Tagger;104 8.5;6.5 Parsing Experiments;105 8.5.1;6.5.1 Data and Setup;105 8.5.2;6.5.2 Results for 2nd-Order Models;105 8.5.3;6.5.3 Results for Models with Semantic Features;107 8.5.4;6.5.4 Remarks on Efficiency;107 8.6;6.6 Conclusion;108 8.7;References;109 9;7 Strictly Lexicalised Dependency Parsing;112 9.1;7.1 Introduction;112 9.2;7.2 A Probabilistic Dependency Parsing Model;113 9.3;7.3 Similarity-Based Smoothing;117 9.3.1;7.3.1 Distributional Word Similarity;117 9.3.2;7.3.2 Similarity Measures;117 9.3.3;7.3.3 Similarity-Based Smoothing;118 9.4;7.4 Similarity-Based Smoothing in Dependency Parsing;119 9.5;7.5 Dependency Parsing Algorithms;120 9.6;7.6 Experimental Results;122 9.7;7.7 Related Work;124 9.8;7.8 Contributions;125 9.9;7.9 Conclusion;125 9.10;References;125 10;8 Favor Short Dependencies: Parsing with Soft and Hard Constraints on Dependency Length;128 10.1;8.1 Introduction;128 10.2;8.2 Short Dependencies in Langugage;129 10.3;8.3 Soft Constraints on Dependency Length;130 10.3.1;8.3.1 Grammar Formalism;130 10.3.2;8.3.2 Baseline Models;131 10.3.3;8.3.3 Length-Sensitive Models;132 10.3.4;8.3.4 Parsing Algorithm;132 10.3.5;8.3.5 A Note on Word Senses;134 10.3.6;8.3.6 Probabilistic Parsing;135 10.3.7;8.3.7 A Note on Lattice Parsing;136 10.4;8.4 Experiments with Soft Constraints;140 10.5;8.5 Hard Dependency-Length Constraints;142 10.5.1;8.5.1 Vine Grammars;142 10.5.2;8.5.2 Feasible Parsing;143 10.6;8.6 Experiments with Hard Constraints;149 10.6.1;8.6.1 Finer-Grained Hard Constraints;149 10.7;8.7 Related Work;151 10.8;8.8 Future Work;153 10.9;8.9 Conclusion;154 10.10;References;155 11;9 Corrective Dependency Parsing ;158 11.1;9.1 Introduction;158 11.2;9.2 Syntactic Dependency Trees;160 11.3;9.3 Dependency Parsing Techniques ;161 11.3.1;9.3.1 Constituency Parsing for Dependency Trees ;161 11.3.2;9.3.2 Dependency Parsing;163 11.3.3;9.3.3 Dependency Errors;163 11.4;9.4 Corrective Modeling ;164 11.4.1;9.4.1 Maximum Entropy Estimation;165 11.4.2;9.4.2 Proposed Model ;167 11.4.3;9.4.3 Related Work;167 11.5;9.5 Empirical Results ;168 11.5.1;9.5.1 Constituency-Based Corrective Models;169 11.5.2;9.5.2 Dependency-Based Parsing;171 11.5.3;9.5.3 Characterization of Corrective Decisions;172 11.6;9.6 Conclusion;172 11.7;References;173 12;10 Inducing Lexicalised PCFGs with Latent Heads ;175 12.1;10.1 Introduction;175 12.2;10.2 Head Lexicalization;176 12.3;10.3 Latent-Head Models;180 12.3.1;10.3.1 Head-Lexicalized CFGs with Latent Heads;180 12.3.2;10.3.2 Unsupervised Estimation of Head-Lexicalized CFGswith Latent Heads;181 12.4;10.4 Experiments;182 12.4.1;10.4.1 Data and Parameters;182 12.4.2;10.4.2 Empirical Results;183 12.4.3;10.4.3 Latent Heads;184 12.5;10.5 Discussion;184 12.6;10.6 Conclusion;187 12.7;10.7 Further Reading;187 12.8;References;187 13;11 Self-Trained Bilexical Preferences to Improve Disambiguation Accuracy ;189 13.1;11.1 Motivation;189 13.2;11.2 Previous Research;190 13.3;11.3 Background: Alpino Parser;191 13.3.1;11.3.1 Grammar and Lexicon;191 13.3.2;11.3.2 Parser;192 13.3.3;11.3.3 Maximum Entropy Disambiguation Model;192 13.3.4;11.3.4 Dependency Structures;193 13.3.5;11.3.5 Named Dependency Relations;194 13.3.6;11.3.6 Evaluation;194 13.3.7;11.3.7 Parsed Corpora;196 13.4;11.4 Bilexical Preferences;196 13.4.1;11.4.1 Association Score;196 13.4.2;11.4.2 Extending Pairs;199 13.4.3;11.4.3 Using Association Scores as Features;200 13.5;11.5 Experiments;202 13.6;11.6 Conclusion and Outlook;203 13.7;References;205 14;12 Are Very Large Context-Free Grammars Tractable? ;207 14.1;12.1 Introduction;207 14.2;12.2 Preliminaries;208 14.2.1;12.2.1 Context-Free Grammars;208 14.2.2;12.2.2 Finite-State Automata;210 14.2.3;12.2.3 Input Strings and Input DAGs;211 14.2.4;12.2.4 The Make-a-Reduced-Grammar Algorithm;212 14.3;12.3 Filtering Strategies;212 14.3.1;12.3.1 Gold Strategy: g-Filter;213 14.3.2;12.3.2 Basic Filtering Strategy: b-Filter;214 14.3.3;12.3.3 Adjacent Filtering Strategy: a-Filter;214 14.3.4;12.3.4 Dynamic Set Automaton Filtering Strategy: d-Filter;218 14.4;12.4 Experiments;219 14.4.1;12.4.1 Grammars and Corpus;219 14.4.2;12.4.2 Precision Results;222 14.4.3;12.4.3 Parsing Time and Best Filter;223 14.5;12.5 Conclusion;226 14.6;References;227 15;13 Efficiency in Unification-Based N-Best Parsing;229 15.1;13.1 Background and Motivation;229 15.2;13.2 Overall Set-Up;230 15.3;13.3 Interleaving Parsing and Ranking;233 15.4;13.4 Selective Unpacking;234 15.5;13.5 Generalizing the Algorithm;236 15.6;13.6 Failure Caching and Propagation;238 15.7;13.7 Empirical Results;239 15.8;13.8 Discussion;243 15.9;13.9 Conclusions and Future Work;245 15.10;References;246 16;14 HPSG Parsing with a Supertagger ;248 16.1;14.1 Introduction;248 16.2;14.2 HPSG and Probabilistic Models;250 16.3;14.3 Probabilistic HPSG with a Supertagger;252 16.4;14.4 Experiments;254 16.4.1;14.4.1 Implementation;254 16.4.2;14.4.2 Evaluation;255 16.4.3;14.4.3 Discussion;257 16.4.4;14.4.4 Evaluation of Supertaggers;258 16.5;14.5 Conclusion;259 16.6;References;260 17;15 Evaluating the Impact of Re-training a Lexical Disambiguation Model on Domain Adaptation of an HPSG Parser;262 17.1;15.1 Introduction;262 17.2;15.2 An HPSG Parser;263 17.3;15.3 Re-training of a Disambiguation Model of Lexical Entry Assignments;266 17.4;15.4 Experiments with the GENIA Corpus;267 17.4.1;15.4.1 Experimental Settings;268 17.4.2;15.4.2 Exploring Naive or Existing Approaches;270 17.4.3;15.4.3 Impact of Re-training a Lexical Disambiguation Model;271 17.4.4;15.4.4 Effectiveness of Combining Lexical and Syntactic Disambiguation Models;272 17.4.5;15.4.5 Error Analysis;272 17.5;15.5 Experiments with the Brown Corpus;274 17.5.1;15.5.1 Brown Corpus;274 17.5.2;15.5.2 Evaluation of Portability of Our Method;275 17.6;15.6 Related Work;277 17.7;15.7 Conclusions;278 17.8;References;278 18;16 Semi-supervised Training of a Statistical Parser from Unlabeled Partially-Bracketed Data ;281 18.1;16.1 Introduction;281 18.2;16.2 The Parsing System;283 18.2.1;16.2.1 The Parse Selection Model;283 18.3;16.3 Training Data;284 18.3.1;16.3.1 Derivation Consistency;284 18.3.2;16.3.2 The Susanne Treebank and Baseline Training Data;284 18.3.3;16.3.3 The WSJ PTB Training Data;285 18.3.4;16.3.4 The DepBank Test Data;285 18.4;16.4 The Evaluation Scheme;286 18.4.1;16.4.1 Wilcoxon Signed Ranks Test;287 18.5;16.5 Training from Unlabeled Bracketings;287 18.5.1;16.5.1 Confidence-Based Approaches;288 18.5.2;16.5.2 EM;289 18.6;16.6 Tuning to a New Domain;292 18.7;16.7 Conclusions;293 18.8;References;294 19;Index;296