Browsing by Subject "Natural language processing (Computer science)"

Now showing 1 - 6 of 6

Flexible semantic matching of rich knowledge structures
(2006) Yeh, Peter Zei-Chan; Porter, Bruce, 1956-
Many AI tasks require matching two knowledge representations to determine whether (and how) they match. For example, rule based classification requires matching rule antecedents with working memory; knowledge based information retrieval requires matching queries with an ontology; and discourse understanding requires matching the speaker's utterances with background knowledge to build a coherent model of what was said. Solving this matching problem is difficult because similar information can be expressed in very different ways. Existing solutions use either syntactic measures, such as maximum common subgraph, or shallow semantics, such as taxonomic knowledge. These solutions, however, overlook many mismatches between representations - adversely affecting performance. Our goal is to improve the performance of existing semantic matchers. Our solution is to augment these matchers with transformation rules that achieve broad coverage. To achieve this coverage, we built a library of transformations based on: 1) a domain independent upper ontology and 2) a recurring pattern called "Transfers Thru". We systematically enumerated all valid instantiations of this pattern, and the result was a comprehensive library of about 200 transformations. We evaluated our matcher by applying it to several different tasks including course-of-action critiquing, information retrieval, discourse understanding, and sense disambiguation and semantic role labeling. In each case, we found that our matcher significantly improved matching and outperformed the state-of-the-art systems for each specific task.
Integrating top-down and bottom-up approaches in inductive logic programming: applications in natural language processing and relational data mining
(2003) Tang, Lap Poon Rupert; Mooney, Raymond J. (Raymond Joseph)
Inductive Logic Programming (ILP) is the intersection of Machine Learning and Logic Programming in which the learner’s hypothesis space is the set of logic programs. There are two major ILP approaches: top-down and bottom-up. The former searches the hypothesis space from general to specific while the latter the other way round. Integrating both approaches has been demonstrated to be more effective. Integrated ILP systems were previously developed for two tasks: learning semantic parsers (Chillin), and mining relational data (Progol). Two new integrated ILP systems for these tasks that overcome limitations of existing methods will be presented. Cocktail is a new ILP algorithm for inducing semantic parsers. For this task, two features of a parse state, functional structure and context, provide important information for disambiguation. A bottom-up approach is more suitable for learning the former, while top-down is better for the latter. By allowing both approaches to induce program clauses and choosing the best combination of their results, Cocktail learns more effective parsers. Experimental results on learning natural-language interfaces for two databases demonstrate that it learns more accurate parsers than Chillin, the previous best method for this task. Beth is a new integrated ILP algorithm for relational data mining. The Inverse Entailment approach to ILP, implemented in the Progol and Aleph systems, starts with the construction of a bottom clause, the most specific hypothesis covering a seed example. When mining relational data with a large number of background facts, the bottom clause becomes intractably large, making learning very inefficient. A top-down approach heuristically guides the construction of clauses without building a bottom clause; however, it wastes time exploring clauses that cover no positive examples. By using a top-down approach to heuristically guide the construction of generalizations of a bottom clause, Beth combines the strength of both approaches. Learning patterns for detecting potential terrorist activity is a current challenge problem for relational data mining. Experimental results on artificial data for this task with over half a million facts show that Beth is significantly more efficient at discovering such patterns than Aleph and m-Foil, two leading ILP systems.
Learning for information extraction: from named entity recognition and disambiguation to relation extraction
(2007-08) Bunescu, Razvan Constantin, 1975-; Mooney, Raymond J. (Raymond Joseph)
Information Extraction, the task of locating textual mentions of specific types of entities and their relationships, aims at representing the information contained in text documents in a structured format that is more amenable to applications in data mining, question answering, or the semantic web. The goal of our research is to design information extraction models that obtain improved performance by exploiting types of evidence that have not been explored in previous approaches. Since designing an extraction system through introspection by a domain expert is a laborious and time consuming process, the focus of this thesis will be on methods that automatically induce an extraction model by training on a dataset of manually labeled examples. Named Entity Recognition is an information extraction task that is concerned with finding textual mentions of entities that belong to a predefined set of categories. We approach this task as a phrase classification problem, in which candidate phrases from the same document are collectively classified. Global correlations between candidate entities are captured in a model built using the expressive framework of Relational Markov Networks. Additionally, we propose a novel tractable approach to phrase classification for named entity recognition based on a special Junction Tree representation. Classifying entity mentions into a predefined set of categories achieves only a partial disambiguation of the names. This is further refined in the task of Named Entity Disambiguation, where names need to be linked to their actual denotations. In our research, we use Wikipedia as a repository of named entities and propose a ranking approach to disambiguation that exploits learned correlations between words from the name context and categories from the Wikipedia taxonomy. Relation Extraction refers to finding relevant relationships between entities mentioned in text documents. Our approaches to this information extraction task differ in the type and the amount of supervision required. We first propose two relation extraction methods that are trained on documents in which sentences are manually annotated for the required relationships. In the first method, the extraction patterns correspond to sequences of words and word classes anchored at two entity names occurring in the same sentence. These are used as implicit features in a generalized subsequence kernel, with weights computed through training of Support Vector Machines. In the second approach, the implicit extraction features are focused on the shortest path between the two entities in the word-word dependency graph of the sentence. Finally, in a significant departure from previous learning approaches to relation extraction, we propose reducing the amount of required supervision to only a handful of pairs of entities known to exhibit or not exhibit the desired relationship. Each pair is associated with a bag of sentences extracted automatically from a very large corpus. We extend the subsequence kernel to handle this weaker form of supervision, and describe a method for weighting features in order to focus on those correlated with the target relation rather than with the individual entities. The resulting Multiple Instance Learning approach offers a competitive alternative to previous relation extraction methods, at a significantly reduced cost in human supervision.
Learning for semantic parsing and natural language generation using statistical machine translation techniques
(2007) Wong, Yuk Wah, 1979-; Mooney, Raymond J. (Raymond Joseph)
One of the main goals of natural language processing (NLP) is to build au- tomated systems that can understand and generate human lanugages. This goal has so far remained elusive. Existing hand-crafted systems can provide in-depth anal- ysis of domain sub-languages, but are often notoriously fragile and costly to build. Existing machine-learned systems are considerably more robust, but are limited to relatively shallow NLP tasks. In this thesis, we present novel statistical methods for robust natural lan- guage understanding and generation. We focus on two important sub-tasks, seman- tic parsing and tactical generation. The key idea is that both tasks can be treated as the translation between natural languages and formal meaning representation lan- guages, and therefore, can be performed using state-of-the-art statistical machine translation techniques. Specifically, we use a technique called synchronous pars- ing, which has been extensively used in syntax-based machine translation, as the unifying framework for semantic parsing and tactical generation. The parsing and generation algorithms learn all of their linguistic knowledge from annotated cor- pora, and can handle natural-language sentences that are conceptually complex. A nice feature of our algorithms is that the semantic parsers and tactical gen- erators share the same learned synchronous grammars. Moreover, charts are used as the unifying language-processing architecture for efficient parsing and generation. Therefore, the generators are said to be the inverse of the parsers, an elegant prop- erty that has been widely advocated. Furthermore, we show that our parsers and generators can handle formal meaning representation languages containing logical variables, including predicate logic. Our basic semantic parsing algorithm is called WASP. Most of the other parsing and generation algorithms presented in this thesis are extensions of WASP or its inverse. We demonstrate the effectiveness of our parsing and generation al- gorithms by performing experiments in two real-world, restricted domains. Ex- perimental results show that our algorithms are more robust and accurate than the currently best systems that require similar supervision. Our work is also the first attempt to use the same automatically-learned grammar for both parsing and gen- eration. Unlike previous systems that require manually-constructed grammars and lexicons, our systems require much less knowledge engineering and can be easily ported to other languages and domains.
Learning for semantic parsing with kernels under various forms of supervision
(2007) Kate, Rohit Jaivant, 1978-; Mooney, Raymond J. (Raymond Joseph)
Semantic parsing involves deep semantic analysis that maps natural language sentences to their formal executable meaning representations. This is a challenging problem and is critical for developing computing systems that understand natural language input. This thesis presents a new machine learning approach for semantic parsing based on string-kernel-based classification. It takes natural language sentences paired with their formal meaning representations as training data. For every production in the formal language grammar, a Support-Vector Machine (SVM) classifier is trained using string similarity as the kernel. Meaning representations for novel natural language sentences are obtained by finding the most probable semantic parse using these classi- fiers. This method does not use any hard-matching rules and unlike previous and other recent methods, does not use grammar rules for natural language, probabilistic or otherwise, which makes it more robust to noisy input. Besides being robust, this approach is also flexible and able to learn under a wide range of supervision, from extra to weaker forms of supervision. It can easily utilize extra supervision given in the form of syntactic parse trees for natural language sentences by using a syntactic tree kernel instead of a string kernel. Its learning algorithm can also take advantage of detailed supervision provided in the form of semantically augmented parse trees. A simple extension using transductive SVMs enables the system to do semi-supervised learning and improve its performance utilizing unannotated sentences which are usually easily available. Another extension involving EM-like retraining makes the system capable of learning under ambiguous supervision in which the correct meaning representation for each sentence is not explicitly given, but instead a set of possible meaning representations is given. This weaker and more general form of supervision is better representative of a natural training environment for a language-learning system requiring minimal human supervision. For a semantic parser to work well, conformity between natural language and meaning representation grammar is necessary. However meaning representation grammars are typically designed to best suit the application which will use the meaning representations with little consideration for how well they correspond to natural language semantics. We present approaches to automatically transform meaning representation grammars to make them more compatible with natural language semantics and hence more suitable for learning semantic parsers. Finally, we also show that ensembles of different semantic parser learning systems can obtain the best overall performance.
Text mining with information extraction
(2004) Nahm, Un Yong; Mooney, Raymond J. (Raymond Joseph)