Application of Graph Rewriting to Natural Language Processing
1st Edition
Published on 28. March 2018
Book
Hardback
272 pages
978-1-78630-096-6 (ISBN)
Description
The paradigm of Graph Rewriting is used very little in the field of Natural Language Processing. But graphs are a natural way of representing the deep syntax and the semantics of natural languages. Deep syntax is an abstraction of syntactic dependencies towards semantics in the form of graphs and there is a compact way of representing the semantics in an underspecified logical framework also with graphs. Then, Graph Rewriting reconciles efficiency with linguistic readability for producing representations at some linguistic level by transformation of a neighbor level: from raw text to surface syntax, from surface syntax to deep syntax, from deep syntax to underspecified logical semantics and conversely.
More details
Language
English
Place of publication
London
United Kingdom
Target group
Professional and scholarly
Edition type
Annotated edition
Product notice
sewn/stitched
Cloth over boards
Dimensions
Height: 239 mm
Width: 166 mm
Thickness: 22 mm
Weight
545 gr
ISBN-13
978-1-78630-096-6 (9781786300966)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Other editions
Additional editions
Guillaume Bonfante | Bruno Guillaume | Guy Perrier
Application of Graph Rewriting to Natural Language Processing
E-Book
04/2018
1st Edition
Wiley
€139.99
Available for download
Guillaume Bonfante | Bruno Guillaume | Guy Perrier
Application of Graph Rewriting to Natural Language Processing
E-Book
04/2018
1st Edition
Wiley-Scrivener
€139.99
Available for download
Persons
Guillaume Bonfante is a senior lecturer at the University of Lorraine, France.
Bruno Guillaume is a researcher at Inria Nancy Grand-Est, France.
Guy Perrier is Professor Emeritus at the University of Lorraine, France.
Bruno Guillaume is a researcher at Inria Nancy Grand-Est, France.
Guy Perrier is Professor Emeritus at the University of Lorraine, France.
Content
Introduction ix
Chapter 1. Programming with Graphs 1
1.1. Creating a graph 2
1.2. Feature structures 5
1.3. Information searches 6
1.3.1. Access to nodes 7
1.3.2. Extracting edges 7
1.4. Recreating an order 9
1.5. Using patterns with the GREW library 11
1.5.1. Pattern syntax 13
1.5.2. Common pitfalls 16
1.6. Graph rewriting 20
1.6.1. Commands 22
1.6.2. From rules to strategies 24
1.6.3. Using lexicons 29
1.6.4. Packages 31
1.6.5. Common pitfalls 32
Chapter 2. Dependency Syntax: Surface Structure and Deep Structure 35
2.1. Dependencies versus constituents 36
2.2. Surface syntax: different types of syntactic dependency 42
2.2.1. Lexical word arguments 44
2.2.2. Modifiers 49
2.2.3. Multiword expressions 51
2.2.4. Coordination 53
2.2.5. Direction of dependencies between functional and lexical words 55
2.3. Deep syntax 58
2.3.1. Example 59
2.3.2. Subjects of infinitives, participles, coordinated verbs and adjectives 61
2.3.3. Neutralization of diatheses 61
2.3.4. Abstraction of focus and topicalization procedures 64
2.3.5. Deletion of functional words 66
2.3.6. Coordination in deep syntax 68
Chapter 3. Graph Rewriting and Transformation of Syntactic Annotations in a Corpus 71
3.1. Pattern matching in syntactically annotated corpora 72
3.1.1. Corpus correction 72
3.1.2. Searching for linguistic examples in a corpus 77
3.2. From surface syntax to deep syntax 79
3.2.1. Main steps in the SSQ_to_DSQ transformation 80
3.2.2. Lessons in good practice 83
3.2.3. The UD_to_AUD transformation system 90
3.2.4. Evaluation of the SSQ_to_DSQ and UD_to_AUD systems 91
3.3. Conversion between surface syntax formats 92
3.3.1. Differences between the SSQ and UD annotation schemes 92
3.3.2. The SSQ to UD format conversion system 98
3.3.3. The UD to SSQ format conversion system 100
Chapter 4. From Logic to Graphs for Semantic Representation 103
4.1. First order logic 104
4.1.1. Propositional logic 104
4.1.2. Formula syntax in FOL 106
4.1.3. Formula semantics in FOL 107
4.2. Abstract meaning representation (AMR) 108
4.2.1. General overview of AMR 109
4.2.2. Examples of phenomena modeled using AMR 113
4.3. Minimal recursion semantics, MRS 118
4.3.1. Relations between quantifier scopes 118
4.3.2. Why use an underspecified semantic representation? 120
4.3.3. The RMRS formalism 122
4.3.4. Examples of phenomenon modeling in MRS 133
4.3.5. From RMRS to DMRS 137
Chapter 5. Application of Graph Rewriting to Semantic Annotation in a Corpus 143
5.1. Main stages in the transformation process 144
5.1.1. Uniformization of deep syntax 144
5.1.2. Determination of nodes in the semantic graph 145
5.1.3. Central arguments of predicates 147
5.1.4. Non-core arguments of predicates 147
5.1.5. Final cleaning 148
5.2. Limitations of the current system 149
5.3. Lessons in good practice 150
5.3.1. Decomposing packages 150
5.3.2. Ordering packages 151
5.4. The DSQ_to_DMRS conversion system 154
5.4.1. Modifiers 154
5.4.2. Determiners 156
Chapter 6. Parsing Using Graph Rewriting 159
6.1. The Cocke-Kasami-Younger parsing strategy 160
6.1.1. Introductory example 160
6.1.2. The parsing algorithm 163
6.1.3. Start with non-ambiguous compositions 164
6.1.4. Revising provisional choices once all information is available 165
6.2. Reducing syntactic ambiguity 169
6.2.1. Determining the subject of a verb 170
6.2.2. Attaching complements found on the right of their governors 172
6.2.3. Attaching other complements 176
6.2.4. Realizing interrogatives and conjunctive and relative subordinates 179
6.3. Description of the POS_to_SSQ rule system 180
6.4. Evaluation of the parser 185
Chapter 7. Graphs, Patterns and Rewriting 187
7.1. Graphs 189
7.2. Graph morphism 192
7.3. Patterns 195
7.3.1. Pattern decomposition in a graph 198
7.4. Graph transformations 198
7.4.1. Operations on graphs 199
7.4.2. Command language 200
7.5. Graph rewriting system 202
7.5.1. Semantics of rewriting 205
7.5.2. Rule uniformity 206
7.6. Strategies 206
Chapter 8. Analysis of Graph Rewriting 209
8.1. Variations in rewriting 212
8.1.1. Label changes 213
8.1.2. Addition and deletion of edges 214
8.1.3. Node deletion 215
8.1.4. Global edge shifts 215
8.2. What can and cannot be computed 217
8.3. The problem of termination 220
8.3.1. Node and edge weights 221
8.3.2. Proof of the termination theorem 224
8.4. Confluence and verification of confluence 229
Appendix 237
Bibliography 241
Index 247
Chapter 1. Programming with Graphs 1
1.1. Creating a graph 2
1.2. Feature structures 5
1.3. Information searches 6
1.3.1. Access to nodes 7
1.3.2. Extracting edges 7
1.4. Recreating an order 9
1.5. Using patterns with the GREW library 11
1.5.1. Pattern syntax 13
1.5.2. Common pitfalls 16
1.6. Graph rewriting 20
1.6.1. Commands 22
1.6.2. From rules to strategies 24
1.6.3. Using lexicons 29
1.6.4. Packages 31
1.6.5. Common pitfalls 32
Chapter 2. Dependency Syntax: Surface Structure and Deep Structure 35
2.1. Dependencies versus constituents 36
2.2. Surface syntax: different types of syntactic dependency 42
2.2.1. Lexical word arguments 44
2.2.2. Modifiers 49
2.2.3. Multiword expressions 51
2.2.4. Coordination 53
2.2.5. Direction of dependencies between functional and lexical words 55
2.3. Deep syntax 58
2.3.1. Example 59
2.3.2. Subjects of infinitives, participles, coordinated verbs and adjectives 61
2.3.3. Neutralization of diatheses 61
2.3.4. Abstraction of focus and topicalization procedures 64
2.3.5. Deletion of functional words 66
2.3.6. Coordination in deep syntax 68
Chapter 3. Graph Rewriting and Transformation of Syntactic Annotations in a Corpus 71
3.1. Pattern matching in syntactically annotated corpora 72
3.1.1. Corpus correction 72
3.1.2. Searching for linguistic examples in a corpus 77
3.2. From surface syntax to deep syntax 79
3.2.1. Main steps in the SSQ_to_DSQ transformation 80
3.2.2. Lessons in good practice 83
3.2.3. The UD_to_AUD transformation system 90
3.2.4. Evaluation of the SSQ_to_DSQ and UD_to_AUD systems 91
3.3. Conversion between surface syntax formats 92
3.3.1. Differences between the SSQ and UD annotation schemes 92
3.3.2. The SSQ to UD format conversion system 98
3.3.3. The UD to SSQ format conversion system 100
Chapter 4. From Logic to Graphs for Semantic Representation 103
4.1. First order logic 104
4.1.1. Propositional logic 104
4.1.2. Formula syntax in FOL 106
4.1.3. Formula semantics in FOL 107
4.2. Abstract meaning representation (AMR) 108
4.2.1. General overview of AMR 109
4.2.2. Examples of phenomena modeled using AMR 113
4.3. Minimal recursion semantics, MRS 118
4.3.1. Relations between quantifier scopes 118
4.3.2. Why use an underspecified semantic representation? 120
4.3.3. The RMRS formalism 122
4.3.4. Examples of phenomenon modeling in MRS 133
4.3.5. From RMRS to DMRS 137
Chapter 5. Application of Graph Rewriting to Semantic Annotation in a Corpus 143
5.1. Main stages in the transformation process 144
5.1.1. Uniformization of deep syntax 144
5.1.2. Determination of nodes in the semantic graph 145
5.1.3. Central arguments of predicates 147
5.1.4. Non-core arguments of predicates 147
5.1.5. Final cleaning 148
5.2. Limitations of the current system 149
5.3. Lessons in good practice 150
5.3.1. Decomposing packages 150
5.3.2. Ordering packages 151
5.4. The DSQ_to_DMRS conversion system 154
5.4.1. Modifiers 154
5.4.2. Determiners 156
Chapter 6. Parsing Using Graph Rewriting 159
6.1. The Cocke-Kasami-Younger parsing strategy 160
6.1.1. Introductory example 160
6.1.2. The parsing algorithm 163
6.1.3. Start with non-ambiguous compositions 164
6.1.4. Revising provisional choices once all information is available 165
6.2. Reducing syntactic ambiguity 169
6.2.1. Determining the subject of a verb 170
6.2.2. Attaching complements found on the right of their governors 172
6.2.3. Attaching other complements 176
6.2.4. Realizing interrogatives and conjunctive and relative subordinates 179
6.3. Description of the POS_to_SSQ rule system 180
6.4. Evaluation of the parser 185
Chapter 7. Graphs, Patterns and Rewriting 187
7.1. Graphs 189
7.2. Graph morphism 192
7.3. Patterns 195
7.3.1. Pattern decomposition in a graph 198
7.4. Graph transformations 198
7.4.1. Operations on graphs 199
7.4.2. Command language 200
7.5. Graph rewriting system 202
7.5.1. Semantics of rewriting 205
7.5.2. Rule uniformity 206
7.6. Strategies 206
Chapter 8. Analysis of Graph Rewriting 209
8.1. Variations in rewriting 212
8.1.1. Label changes 213
8.1.2. Addition and deletion of edges 214
8.1.3. Node deletion 215
8.1.4. Global edge shifts 215
8.2. What can and cannot be computed 217
8.3. The problem of termination 220
8.3.1. Node and edge weights 221
8.3.2. Proof of the termination theorem 224
8.4. Confluence and verification of confluence 229
Appendix 237
Bibliography 241
Index 247