Search

With the ongoing growth of the global network and information influx in today's increasingly connected world, more and more content becomes readily available in a plethora of different languages, dialects, unofficial and community languages. Considering the large amount of multilingual data which are typically unstructured but thematically aligned and comparable, there is a pressing need to build unsupervised algorithms which can deal with such multilingual data, and address the problems of meaning, translation and information retrieval in multilingual settings.The thesis has four major contributions in the research fields of data mining, natural language processing and information retrieval. First, we present and describe a full overview of the newly developed multilingual probabilistic topic modeling (MuPTM) framework for mining multilingual data. The framework is utilized to induce high-level language-independent representations of textual information (e.g., words, phrases and documents). Second, we propose a new statistical framework for inducing bilingual lexicons (i.e., addressing the problem of translation) from parallel data that is based on the novel paradigm of sub-corpora sampling. Third, we introduce a new statistical framework for modeling cross-lingual semantic similarity (i.e., addressing the problem of meaning) and inducing bilingual lexicons (i.e., the problem of translation) from comparable data. Here, we make a series of contributions to the field of (multilingual) natural language processing and its sub-field of distributional semantics by (i) proposing a series of MuPTM-based models of cross-lingual semantic similarity, (ii) designing an algorithm for detecting only highly reliable translation pairs from noisy multilingual environments, (iii) proposing a new language pair independent cross-lingual semantic space that relies on the concept of semantic word responding, (iv) presenting a new bootstrapping approach to cross-lingual semantic similarity and bilingual lexicon extraction, and (v) proposing a new context-sensitive framework for modeling semantic similarity. Fourth, we propose a new probabilistic framework for cross-lingual and monolingual information retrieval (i.e., tackling the problem of information retrieval) which relies on MuPTM-based text representations.All proposed models are unsupervised and language pair independent in their design. Consequently, that makes them potentially applicable to many language pairs. The proposed models have been evaluated with a variety of language pairs, and we show that they advance state-of-the-art in their respective fields. Due to their unsupervised and language pair independent nature, the presented models exhibit a solid potential for future research and other applications that deal with different official and unofficial languages, dialects and different idioms of the same language. nrpages: xxxvi+278 status: published

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

There are various approaches to gaining semantic understanding of video. Approaches include gaining a better understanding of the underlying video structure through video segmentation, summarizing the video to report the most salient events, identifying concept (persons/objects/scene) classes present, and identifying a sequence of actions that characterize events. A substantial portion of the thesis focuses on the segmentation of video into scenes, where each scene contains a central idea or theme which serves as a component of the greater narrative that constitutes the entire video. Once identified, scenes can be indexed for later retrieval, summarized for quicker access, or used as a reference point when browsing. A typical domain is news broadcast video segmentation.Video structural analysis is known as story segmentation when referring to the specific domain of news broadcast segmentation, or scene segmentation when the domain is unrestricted. Such structural analysis is typically content-based, that is the change between stories is identified by recognized change in context as one topic segues to another. Prior knowledge of the domain permits the inclusion of domain specific knowledge when performing the structural video analysis. Domain specific knowledge in news broadcast video segmentation may take the form of anchor detection, jingle, or speaker silence detection. In the literature, a variety of multi-modal cues contribute to the segmentation decision. However, features and techniques originating in text-only segmentation research have sometimes been neglected in video analysis. Part of the work presented in this thesis describes a supervised approach to the segmentation of news broadcast video using text features, in combination with typically used features from the audio and visual modalities, and investigates each individual features contribution. The thesis then focuses on scene segmentation, which is the segmentation of generic video without domain restriction. The problem is formulated as a segmentation task on long television broadcast of mixed Olympic games coverage with a duration of over 4 hours. The Olympic coverage consists of mixed sports, such that no sports specific detectors could be applied; and with visually similar and sequential races of the same sport without interruption where the goal is to isolate each race individually in the final segmentation. This requires a different approach in terms of feature selection, and the choice is made to develop an unsupervised method that is sufficiently robust to allow application in other domains. A summarization component applies labels to the ensuing scene segments by identifying persons present, salient key-words, and the type of sport by means of a classifier trained on Wikipedia articles. The next part of the thesis determines salient events within each scene, by performing temporal sequence analysis of the underlying shots via string kernels. In the context of the Olympic games, a swimming race may have underlying sequences corresponding to when swimmers line up prior to the race, actual swimming back and forth in lanes, the race conclusion and final times. The identification of such events immediately provides a deeper semantic understanding of the events taking place, but can also be used to identify similar event sequences in other video broadcasts in the same domain. Within the context of a video browser, stories and scenes are further analysed in other modules to create additional indexes for cross-referencing to identify scenes that discuss the same topic, share the same people, or have a common location. In this thesis, scenes are mined for common, semantically relevant event sequences which describe the overall scene. The work presented in this thesis on scene and story segmentation serves to partition a video into semantically coherent units which are a basic unit for browsing and retrieval. Substantive contributions are made on unsupervised semantic event detection for indexation and retrieval. The research was conducted in the context of the AMASS++ (Advanced Multimedia Alignment and Structured Summarization) research project, which had the goal of developing an advanced video archive browser and retrieval system as well as the recently launched research project on task-oriented search and content annotation for media production (TOSCA-MP). status: published