Natural Language Parsing Systems

ISBN-13: 9783642830327 / Angielski / Miękka / 2011 / 367 str.

Leonard Bolc

Opis

Up to now there has been no scientific publication on natural lan guage research that presents a broad and complex description of the current problems of parsing in the context of Artificial Intelli gence. However, there are many interesting results from this domain appearing mainly in numerous articles published in pro fessional journals. In view of this situation, the objective of this book is to enable scientists from different countries to present the results of their research on natural language parsing in the form of more detailed papers than would be possible in professional jour nals. This book thus provides a collection of studies written by well known scientists whose earlier publications have greatly contributed to the development of research on natural language parsing. Jaime G. Carbonell and Philip J. Hayes present in their paper "Robust Parsing Using Multiple Construction-Specific Strategies" two small experimental parsers, implemented to illustrate the advantages of a multi-strategy approach to parsers, with strategies selected according to the type of construction being parsed at any given time. This presentation is followed by the description of a parsing algorithm, integrating some of the best features of the two smaller parsers, including case-frame instantiation and partial pat tern-matching strategies."

Spis treści

Robust Parsing Using Multiple Construction-Specific Strategies.- 1 Introduction.- 2 Construction-Specific Flexible Parsing.- 2.1 Problems with a Rigid Uniform Grammar.- 2.2 The Need for Case Constructions.- 3 The Representation of Ambiguity and Focused Interaction.- 3.1 Focused Error Recovery.- 3.2 Representing Case-Filler Ambiguity.- 3.3 Representing Structural Ambiguity.- 4 Limited-Domain Language Definition.- 4.1 Compiling Descriptions into Linear Patterns.- 4.2 Direct Interpretation of Case Descriptions.- 5 Parsing Data Base Queries and Updates.- 5.1 The Non-Uniformity Problem.- 5.2 Unifying Update and Query Representations.- 5.3 Benefits of the Construction-Specific Approach.- 6 The CASPAR Parser.- 6.1 The Two CASPAR Strategies.- 6.2 Error-Tolerant Parsing.- 6.3 The CASPAR Algorithm.- 7 The DYPAR Parser.- 7.1 The Objectives of the DYPAR Approach.- 7.2 Parsing Strategies in DYPAR.- 7.3 A Sample DYPAR Dialogue.- 8 Combining the Strengths of CASPAR and DYPAR.- 8.1 A Multi-Strategy Algorithm.- 8.2 Flexible Error-Recovery Mechanisms.- 8.3 Advantages of the Multi-Strategy Approach.- 8.4 A Review of Principal Parsing Strategies.- 9 Conclusion.- References.- Parsing with Logical Variables.- 1 Introduction.- 2 Definite Clause Grammars.- 2.1 The DCG Notation.- 2.2 Interpreting DCG Rules as Definite Clauses.- 2.3 An Example in More Detail.- 3 Comparing DC and ATN Grammars.- 4 Replacing ATN Registers with ATN Variables.- 5 Conclusions.- References.- Knowledge-Based Parsing.- 1 Introduction.- 1.1 Overview.- 1.2 Fundamental Assumptions.- 1.3 Declarative Knowledge Representation in an Integrated Knowledge Base.- 1.4 System Overview.- 1.5 Knowledge Representation Techniques.- 1.6 Core Knowledge and the Kernel Language.- 1.7 Metalanguage Conventions and Symbols.- 2 Core Knowledge and Representations.- 2.1 Uniform Representation and Intensional Constructs.- 2.2 Predefined Categories, Objects, Relations, Functions.- 2.2.1 Predefined Categories.- 2.2.2 Predefined Objects.- 2.2.3 Predefined Relations.- 2.2.4 Predefined Functions.- 2.3 The Reading Function.- 2.4 The Representational Mapping.- 2.4.1 Introduction.- 2.4.2 Base Cases.- 2.4.3 Propositions and Structured Objects.- 2.4.4 Participants in Propositions or Relations; Components of Structured Objects.- 2.5 Kernel Language.- 2.5.1 Predefined Terms.- 2.5.2 Syntactic Rewrite Rules.- 2.5.3 Semantic Rewrite Rules.- 2.6 Use in Language Processing.- 3 Increasing the System’s Language Capability Through Its Language Capability.- 3.1 Motivation.- 3.2 Defining More-General Rule Forms.- 3.3 Parsing Strategy.- 3.4 Interpretation of the Input Rule Statement.- 4 Language Use-Mention Distinction.- 5 Summary.- Appendix: Chronological Summary of Input to the System as Presented in This Chapter.- References.- Using Declarative Knowledge for Understanding Natural Language.- 1 Introduction.- 2 The Knowledge.- 2.1 Lexicographic Knowledge.- 2.1.1 The Words.- 2.1.2 The Ending Sequences.- 2.1.3 The Conjugations.- 2.2 Syntactic Knowledge.- 2.2.1 Syntactic Markers.- 2.2.2 Graphs.- 2.2.3 The “Traits”.- 2.2.4 The Agreement Rules.- 2.2.5 The Conjunctions.- 2.2.6 Comparison Between This Formalism and ATN Grammars.- 2.3 The Semantic Knowledge.- 2.3.1 The Pattern Part of a Meaning.- 2.3.2 The Action Part of a Meaning.- 2.3.3 Meaning of the Symbols Which Are Not Words.- 2.4 Pragmatic Knowledge.- 3 The Interpreter.- 3.1 An Interpreter for Lexicographic Knowledge.- 3.2 The Main Interpreter.- 3.2.1 Building the Structure.- 3.2.2 Using the Graphs Representing the Conjunctions.- 3.2.3 Achieving the Building of the Structure.- 3.2.4 Pruning the Structure.- 3.3 The Interpreter of Pragmatic Knowledge.- 3.4 The Implementation.- 4 Discussion.- 5 Conclusion.- References.- Weighted Parsing.- 1 The Need for Weighting.- 2 A Digression: Regulation Processes.- 3 Aspects of System Control.- 4 Types of Weighting.- 4.1 Endogenous Weighting.- 4.2 Exogenous Weighting.- 4.2.1 Absolute Exogenous Weighting.- 4.2.2 Relative Exogenous Weighting.- 5 The Application of Weighting in an MT-System.- 6 Examples of the Application of Weighting.- 6.1 Weights in the Control Structure.- 6.1.1 Production Systems.- 6.2 Weights in Linguistic Structures.- 6.3 Learning Systems.- 7 Computation of Weights.- 7.1 Weights and Sublanguage.- 7.2 Weights and Partial Parsers.- 8 Evaluation of Weights.- References.- A Distributed Word-Based Approach to Parsing.- 1 Introduction.- 2 Background Motivations.- 2.1 Linguistics.- 2.2 Psychology.- 2.3 Computer Science.- 3 The Parsing System.- 3.1 Model Organization.- 3.2 Control Mechanisms: Expert Suspension and Resumption.- 3.2.1 Restart Demons.- 3.2.2 Timeouts.- 3.3 Message and Memory Objects: Expert Interaction Data.- 3.3.1 Control Signals.- 3.3.2 Concept Structures.- 3.3.3 Signal and Concept Filters.- 3.4 Word Expert Structure.- 4 Example: “The man throws in the towel”.- 5 Word Expert Definition.- 5.1 Overview of Expert Functions.- 5.2 Lexical Interaction Language.- 5.2.1 AWAIT.- 5.2.2 PEEKW and READW.- 5.2.3 SEND.- 5.3 Sense Discrimination Language.- 5.3.1 Syntax and Control Signals.- 5.3.2 Semantics and Concept Structures.- 5.3.3 Questions About Incoming Messages.- 5.3.4 Control Flow.- 5.4 Memory Interaction.- 5.4.1 Interaction Requirements.- 5.4.2 VIEW.- 5.4.3 BINDC.- 6 Summary and Conclusions.- References.- Parsing by Means of Uppsala Chart Processor (UCP).- 1 Introduction.- 2 Background.- 2.1 General Syntactic Processor.- 2.2 The Development of the Chart.- 2.2.1 The Chart and Morphographemic Rewriting.- 2.2.2 The Chart and Dictionary Search.- 2.2.3 The Chart and Syntactic Analysis.- 2.3 The Active Chart.- 3 Uppsala Chart Processor.- 3.1 The Format of the Grammatical Descriptions.- 3.2 Dictionary Search.- 3.2.1 Influencing the Dictionary Search Process.- 3.3 Morphological Analysis.- 3.3.1 Predictive Segmentation into Tentative Morphs.- 3.3.2 The Application of Morphotactic Rules.- 3.3.3 Derivational Analysis.- 3.4 Syntactic Analysis.- 3.4.1 The Analysis of a Clause.- 3.4.2 The Infinitive Clause.- 3.4.3 Coordinated Expressions.- 3.4.4 Rule-Driven and Data-Driven Processing.- 3.5 A Summary of the UCP Formalism.- 3.5.1 The Linguistic Operators.- 3.6 Implementation.- 4 Applications.- 4.1 A General Parser for Swedish.- 4.2 Medical Text Comprehension.- 4.3 A Morphological Analyzer for Automatic Keyword Indexing.- 5 Summary of Experience with UCP.- References.- Preliminary Analysis of a Breadth-First Parsing Algorithm: Theoretical and Experimental Results.- 1 An Introduction to Chart Parsing.- 1.1 Enumeration Order.- 1.1.1 Depth-First vs. Breadth-First.- 1.1.2 Top-Down vs. Bottom-Up.- 1.2 N-ary Branching.- 1.3 Dotted-Grammars and ATN States.- 1.4 Example with Dotted-Rules.- 2 Taking Advantage of Restricted Grammars.- 2.1 Time n2 Grammars.- 2.1.1 Grammar ‘aAa’: an Example of Bounded Direct Ambiguity.- 2.2 ‘Grammar AA’: an Example of Unbounded Direct Ambiguity.- 2.3 Examples from Psycholinguistic Literature.- 2.3.1 Noun-Noun Modification.- 2.3.2 Prepositional Phrase Attachment and Conjunction.- 2.3.3 Reduced Relative Clauses.- 2.4 Taking Advantage of Bounded Direct Ambiguity.- 2.5 Time n Grammars.- 2.5.1 Taking Advantage of Useless Phrases.- 2.6 Representation Issues.- 2.6.1 Diagonal Entries.- 2.7 Compilation vs. Interpretation.- 3 Transformations and Lexical Rules.- 3.1 Features.- 3.1.1 Overriding Features in Exceptional Cases.- 3.1.2 Representation of Features.- 3.1.3 The Features in EQSP.- 3.1.4 Transformational Context.- 3.1.5 Adjunct Contexts.- 3.2 NP-Movement.- 3.3 Wh-Movement.- 3.3.1 Gazdar’s Formulation of Wh-Movement.- 3.3.2 Wh-Movement in EQSP.- 3.3.3 Adjacent Filler-Gaps: a Special Case.- 3.3.4 Complement Clauses, Relative Clauses, and Questions.- 3.4 Conjunction.- 3.4.1 The General Mechanism.- 3.4.2 Idiosyncratic Cases.- 3.4.3 Conjunction and the Size of the Grammar.- 4 Experimental Results.- 4.1 A Comparison of the LADDER and MALHOTRA Corpuses.- 4.2 Synthetic Sentences.- 4.2.1 Catalan Numbers.- 4.2.2 Fibonacci Numbers.- 4.2.3 Worst Case for Number of Parses.- 4.3 Analysis of CPU Time.- 5 Conclusion.- Appendix I Results with the MALHOTRA Corpus.- Appendix II Results with the LADDER-TODS Collection.- References.- Syntax Directed Translation in the Natural Language Information System PLIDIS.- 1 Some Notation and Basic Definitions.- 1.1 Notation.- 1.2 Trees.- 2 Tree Directed Grammars.- 2.1 Structural Constraints.- 2.2 Tree Directed Grammars.- 3 Tree Transducers.- 3.1 Top-Down Tree Transducers.- 3.2 Some Extensions of yT-Transducers.- 4 Tree Directed Grammars and Tree Transducers.- 4.1 Downward Oriented Tree Directed Grammars.- 4.2 Loop-Free and Linear Restricted TDGs.- References.