Structured Machine Learning for Mapping Natural Language to Spatial Ontologies (Gestructureerd machinaal leren voor het omzetten van natuurlijke taal naar ruimtelijke ontologieën) : Structured Machine Learning for Mapping Natural Language to Spatial Ontologies

Natural language understanding is one of the fundamental goals of artificial intelligence. An essential function of natural language is to talk about the location, and translocation of objects in space. Understanding spatial language is important in many applications such as geographical information systems, human computer interaction, the provision of navigational instructions to robots, visualization or text-to-scene conversion, etc.Due to the complexity of spatial primitives and notions, and the challenges of designing ontologies for formal spatial representation, the extraction of the spatial information from natural language still has to be placed in a well-defined framework. Machine learning has not systematically been applied to the task, and no established corpora are available. In this thesis I study the problem from cognitive, linguistics and computational points of view, with a primary focus on establishing a supervised machine learning framework.This thesis makes five main research contributions. The first is the design of a spatial annotation scheme to bridge between natural language and formal spatial representations. In this scheme the universal and commonly accepted cognitive spatial notions and multiple well-known qualitative spatial reasoning models are applied.The second is the definition of a novel computational linguistic task that utilizes the annotation scheme to map natural language to spatial ontologies. For this task I have built rich annotated corpora and an evaluation scheme.The third is a detailed investigation of the linguistic features and structural characteristics of spatial language that aid the use of machine learning in extracting spatial roles and relations from annotated data. The learning methods used are discriminative graphical models and statistical relational learning.The fourth is the proposal of a unified structured output learning model for ontologies. The ontology components are learnt while taking into account the ontological constraints and linguistic dependencies among the components. The ontology includes roles and relations, and multiple formal semantic types. The fifth is the proposal of an efficient inference approach based upon constraint optimization. It can deal with a large number of variables and constraints, and makes building a global structured learning model for ontology population, feasible. To test the approach I have performed an empirical investigation using my spatial ontology.The application of my proposed unified learning model for ontology population is not limited to the extraction of spatial semantics, it could be used to populate any ontology. I argue therefore that this work is an important step towards automatically describing text with semantic labels that form a structured ontological representation of the content. Contents Abstract ix List of Symbols xiii Abbreviations xv Contents xvii List of Figures xxv List of Tables xxvii Prologue 1 1 Introduction 3 1.1 Spatial Information Extraction from Natural Language . . . . . 3 1.2 Motivation ............................. 4 1.3 Context............................... 5 1.4 Challenges and Research Questions................ 6 1.5 Contributions of the Thesis .................... 8 1.6 Outline of the Thesis........................ 9 2 Foundations 13 2.1 Structured Machine Learning ................... 13 2.1.1 General Framework .................... 15 2.1.2 Conditional Random Fields ................ 16 2.1.3 Structured Support Vector Machines . . . . . . . . 20 2.1.4 Structured Perceptron-based Model . . .. . . . . . 22 2.1.5 Constrained Conditional Models . . . . . . . . . . . 23 2.1.6 Relational Learning .................... 24 2.1.7 ApproximateInference................... 26 2.2 Natural Language Processing ................... 28 2.2.1 Morphological and Lexical Analysis . . . . . 28 2.2.2 Syntactic Analysis ..................... 29 2.2.3 Semantic Analysis ...................... 31 2.3 Ontologies.............................. 34 2.3.1 Ontology Components................... 34 2.3.2 Meaning Representation via Mapping to Ontologies . . 35 2.3.3 Space in Ontology ..................... 36 I Spatial Information Extraction 37 Outline 39 3 Spatial Annotation Scheme 41 3.1 Annotation Scheme: Foundation and Motivation . . . . . . . . 42 3.1.1 Holistic Spatial Semantics................. 42 3.1.2 Qualitative Spatial Representation . . . . . . . . . . . . 43 3.1.3 The Gap between Natural Language and Formal Models 46 3.2 Annotation Scheme: Relational Representation . . . . . . . . . 3.2.1 Annotation Approach ................... 3.2.2 Simple Descriptions .................... 3.2.3 Complex Descriptions ................... 3.2.4 Adding a Temporal Dimension .............. 3.3 Data Resources........................... 3.3.1 Corpus Collection ..................... 3.3.2 Other Linguistic Resources ................ 3.4 Related Work............................ 3.5 Conclusion ............................. 4 Task Definition: from Language to Spatial Ontologies 4.1 Two Layers of Semantics...................... 4.2 Task Definition as Ontology Population . . . . . . . . . . . . . 4.2.1 Spatial Role Labeling(SpRL)............... 4.2.2 Spatial Qualitative Labeling (SpQL) . . . . . . . . . . . 4.3 Constraints and Features for the Machine Learning Models 4.3.1 Constraints ......................... 4.3.2 Features........................... 4.4 Evaluation Methodology...................... 4.5 Conclusion ............................. II Spatial Role Labeling Outline 5 Graphical Models 5.1 Spatial Role Labeling ....................... 84 5.2 Problem Statement......................... 86 5.3 Approach .............................. 88 5.3.1 Learning Spatial Indicators ................ 90 5.3.2 Trajector and Landmark Classification . . . . . . . . . . . 91 5.3.3 Learning Spatial Relations without a Priori Spatial Indicator Classification................... 5.3.4 Linear-Chain Model .................... 5.3.5 Skip-chain Model with Preposition Template . . . . . . 5.4 Experimental Study ........................ 5.4.1 Datasets........................... 5.4.2 Preposition Disambiguation................ 5.4.3 Extraction of Trajector and Landmark . . . . . . . . . . 5.4.4 Whole Relation Extraction ................ 5.4.5 Experimental Feature Analysis . . . . . . . . . . . . . . 5.4.6 Cross-domain Evaluation ................. 5.4.7 ErrorAnalysis ....................... 5.5 RelatedWork............................ 5.6 Conclusions ............................. Relational Learning 6.1 Relational Problem Statement................... 6.1.1 Relational Representation and Learning in kLog . . . . 6.1.2 Representing SpRL in kLog................ 6.2 Spatial Relation Extraction .................... 6.2.1 Problem Formulation I: Triplet Classification . . . . . . 6.2.2 Problem Formulation II: Relational Sequence Tagging . 6.3 Experiments............................. 6.3.1 Triplet Classification I................... 130 6.3.2 Sequence Tagging for Relation Extraction II . . . . . . . 133 6.3.3 Experimental Analysis................... 134 6.4 Related Work............................ 135 6.5 Conclusion ............................. 136 III Structured Learning: from Language to Spatial Ontologies 137 Outline 139 7 Structured Learning for Ontology Population 141 7.1 Link-And-LabelModel....................... 142 7.1.1 InputSpace......................... 143 7.1.2 OutputSpace........................ 144 7.1.3 Connecting Input and Output Spaces . . . . . . . . . . 145 7.1.4 Component Based Loss .................. 148 7.2 Global Training and Prediction .................. 149 7.2.1 Globality and Violating Examples . . . . . . . . . . . . .151 7.2.2 Communicative Inference ................. 153 7.2.3 Decomposed Training(DecL)............... 154 7.2.4 Decomposition in Relational Domains . . . . . . . . . . 157 7.2.5 Decomposition in Pipeline Models . . . . . . . . . . . . 157 7.3 Related Work............................ 158 7.4 Conclusion ............................. 160 8 Mapping Natural Language to Spatial Ontologies 163 8.1 ModelSpecification......................... 164 8.1.1 Input Space......................... 164 8.1.2 Output Space........................ 164 8.1.3 Joint Feature Mapping and the Main Objective Function 167 8.1.4 Component Based Loss ...................171 Local-Global Training and Prediction Models . . . . . . . . . . 173 Experimental Results and Analysis................ 176 8.3.1 SpRL ............................ 177 8.3.2 SpQLGivenSpRL..................... 187 8.3.3 End-to-EndSpRL-SpQL.................. 192 Related Work............................ 199 Conclusion ............................. 200 Epilogue 201 9 Conclusion and Future Work 203 9.1 Conclusion ............................. 203 9.1.1 Additional Note on Various Learning Frameworks . . . 207 9.2 Future Directions.......................... 210 9.2.1 Domain Portability..................... 210 9.2.2 Relational Learning and Efficient Inference . . . . . . . 210 9.2.3 Extended Applications....................211 9.2.4 Spatial Ontology .......................211 9.2.5 Spatial Reasoning ......................211 Bibliography 213 Curriculum Vitae 229 Publication List 231 nrpages: 233 status: published