VIETNAM NATIONAL UNIVERSITY, HANOI UNIVERSITY OF ENGINEERING AND TECHNOLOGY -------- NGUYEN QUOC DAT RIPPLE DOWN RULES FOR QUESTION ANALYSIS Major: Computer Science Code: 60 48 01 MASTER THESIS Supervised by: Dr. Pham Bao Son Hanoi - 2011 1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Ripple Down Rules for Question Analysis Nguyen Quoc Dat Faculty of Information Technology University of Engineering and Technology Vietnam National University, Hanoi Supervised by Dr. Pham Bao Son A thesis submitted in fulfillment of the requirements for the degree of Master of Science in Computer Science August 2011 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com ORIGINALITY STATEMENT ‘I hereby declare that this submission is my own work and to the best of my knowledge it contains no materials previously published or written by another person, or substan- tial proportions of material which have been accepted for the award of any other degree or diploma at University of Engineering and Technology (UET/Coltech) or any other educational institution, except where due acknowledgement is made in the thesis. Any contribution made to the research by others, with whom I have worked at UET/Coltech or elsewhere, is explicitly acknowledged in the thesis.
I also declare that the intellectual content of this thesis is the product of my own work, except to the extent that assistance from others in the project’s design and conception or in style, presentation and linguistic expression is acknowledged.’ Hanoi, August 23rd , 2011 Signed. i LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com ABSTRACT For the task of turning a natural language question into an explicit intermediate representation of the complexity in question answering systems, all published works so far use rule-based approach to the best of our knowledge. We believe that it is because of the complexity of the representation and the variety of question types and also there are no publicly available corpora of a decent size. In these rule-based approaches, the process of creating rules is not discussed.
It is clear that manually creating the rules in an ad-hoc manner is very expensive and error-prone. This thesis firstly describes an ad-hoc method to convert Vietnamese natural language questions into intermediate representation elements over semantic annotations via grammar rules. Importantly, this thesis focuses on proposing a language independent approach on the process of creating those rules manually, in a way that consistency between rules is maintained and the effort to create a new rule is independent of the size of the current rule set. Experimental results are promising to show that our language independent approach is easy to adapt for a new domain and a new language.
Publications: ? Dat Quoc Nguyen, Dai Quoc Nguyen and Son Bao Pham. Systematic Knowledge Acquisition for Question Analysis. of the 8th International Conference on Recent Advances in Natural Language Processing (RANLP 2011). ? Dat Quoc Nguyen, Dai Quoc Nguyen, Son Bao Pham and Dang Duc Pham.
Ripple Down Rules for Part-Of-Speech Tagging. of 12th International Conference on Intelligent Text Process- ing and Computational Linguistics (CICLING 2011), Springer-Verlag LNCS, part I, pp. ? Dai Quoc Nguyen, Dat Quoc Nguyen and Son Bao Pham. A Vietnamese question answering system.
of the 2009 International Conference on Knowledge and Systems Engineering (KSE 2009), IEEE CS, pp. ii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com ACKNOWLEDGEMENTS First and foremost, I would like to express my deepest gratitude to my supervisor, Dr. Pham Bao Son, for his patient guidance and continuous support throughout the years. He always appears when I need help, and responds to queries so helpfully and promptly.
I would like to give my honest appreciation to my brother, Nguyen Quoc Dai, for his great support. I would like to specially thank Prof. Bui The Duy and my colleagues for their help through my time at Human Machine Interaction Laboratory, UET/Coltech. I would also like to thank my friend, Nguyen Le Trang, for her kindly help.
I sincerely acknowledge the Vietnam National University, Hanoi, NAFOSTED Viet- nam, Toshiba Foundation Scholarship, and especially Dr. Pham Bao Son for sup- porting finance to my master study. Finally, this thesis would not have been possible without the support and love of my mother and my father. Thank you! iii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com To my family ♥ iv LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Table of Contents 1 Introduction 1 2 Literature review 3 2.1 Question analysis in question answering systems .2 Pattern-matching based analysis .3 Syntactic-based analysis .4 Semantic-based analysis .5 Annotation-based question analysis in question answering sys- tems .1 Information Extraction in GATE .3 Single Classification Ripple Down Rules.
19 3 Our Question Answering System Architecture 20 3.3 Syntactic analysis module .1 Noun phrases detection .2 Question-phrases detection .4 Semantic analysis module .5 Answer retrieval component. 29 4 Systematic Knowledge Acquisition for Question Analysis 30 v LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com vi TABLE OF CONTENTS 4.1 Recall Intermediate Representation of an input question .3 Knowledge Acquisition Process .1 Question Analysis for Vietnamese .2 Question Analysis for English. 39 6 Conclusion 41 A Definitions of question-class types 43 B Definitions of question-structures 45 C Intermediate Representation Elements of English questions 48 D Embedding Java code in JAPE 59 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com List of Figures 2.1 Parse tree of question “ which rock contains magnesium? ” .2 The syntactic-semantic tree example.5 A set of Token annotations in GATE.1 Architecture of our question answering system.2 An example of intermediate representation element.3 An example of redefining the TokenVn annotation.5 QU-E-L-MC and QUTerm annotations.6 Relation between phrases.1 Question analyzer’s GUI.2 Question processing component to create the intermediate representa- tion of question “trường đại học Công Nghệ có bao nhiêu sinh viên?”(“how many students are there in the College of Technology?”).1 Question-structure of Definition.2 Question-structure of UnknTerm.3 Question-structure of UnknRel.4 Question-structure of Normal.5 Question-structure of Affirm.6 Question-structure of ThreeTerm.7 Question-structure of Affirm_3Term.8 Question-structure of And. 52 vii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com viii LIST OF FIGURES C.9 Question-structure of And (2).10 Question-structure of And (3).11 Question-structure of And (4).12 Question-structure of Or.13 Question-structure of Clause.14 Question-structure of Clause (2).
58 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com List of Tables 2.1 JAPE grammar for identifying Vietnamese noun phrases .1 Number of exception rules in layers in our SCRDR KB .2 Number of rules corresponding with each question-structure type in the knowledge base for Vietnamese .3 Number of correctly analyzed questions .5 Number of exception rules in layers in our English SCRDR KB .6 Number of rules corresponding with each question-structure type in the knowledge base for English. 40 ix LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com List of Abbreviations IR Information Retrieval GATE General Architecture for Text Engineering JAPE Java Annotation Patterns Engine ANNIE A New-Nearly Information Extraction RDR Ripple Down Rules SCRDR Single Classification Ripple Down Rules QC Question Classification SVM Support Vector Machine SRW Semantically Related Words NLIDB Natural Language Interface to DataBase POS Part-of-Speech NLP Natural Language Processing LHS Left-hand-side RHS Right-hand-side GUI Graphic User Interface x LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chapter 1 Introduction The rocketed growth of online information available that is accessible to human users requires more support from advanced information retrieval (IR) technologies to catch the expected information. This brings new challenges to build IR systems especially like search engine, and question answering systems. While almost current search engines return ranked lists of related documents corresponding with each user’s query (in our case, a query referring to a question), and the user have to scan these documents to obtain desired information.
The goal of question answering systems is to give extract answers in exploiting advantage of natural language processing to the user’s questions without scanning any document. Natural language question analysis component is the first component in any question answering systems. This component creates an intermediate representa- tion of the input question, which is expressed in natural language, to be utilized in the rest of the system. For the task of translating a natural language question into an explicit intermediate representation of the complexity in question answer- ing systems, all published works so far use rule-based approach to the best of our knowledge.
In existing rule-based approaches, because of the complexity of the rep- resentation and the variety of question structure types, manually creating the rules in an ad-hoc manner is very expensive and error-prone in taking a lot of time and effort. For example, many rule-based approaches such as the approach to handle English questions described in Aqualog (Lopez et al., 2007), the one to process Vietnamese questions presented in (Phan and Nguyen, 2010),. manually defined a list of sequence pattern structures to analyze questions. As rules are created in an ad-hoc manner, these approaches share common difficulties in managing interaction 1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
Introduction between rules and keeping consistency among them. In this thesis, we firstly introduce an ad-hoc approach to process Vietnamese natural questions in natural language analysis component. Natural language ques- tions will be transformed into intermediate representation elements which include construction of question, class of question, keywords in question and semantic con- straints between them through processes such as preprocessing, syntactic analysis and semantic analysis over semantic annotations via JAPE grammar rules on GATE framework (Cunningham et al. More importantly, we focus on presenting a language independent approach uti- lizing Ripple Down Rules (Compton and Jansen, 1988, 1990; Richards, 2009) knowl- edge acquisition methodology to acquire rules in a systematic manner where con- sistency between rules is maintained while avoiding unintended interaction among rules.
This dissertation consists of 6 chapters. In second chapter, we provide some lit- erature reviews and describe our overall system architecture, in which we present our method to process Vietnamese questions, in chapter 3. We propose our language independent knowledge acquisition approach in chapter 4. We describe our experi- ments for both Vietnamese and English in chapter 5.
Discussion and conclusion will be presented in chapter 6. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chapter 2 Literature review In this chapter, we review related work using rule-based approaches for question analysis in question answering systems driving specific-domains.1 describe approaches that analyze natural language questions in the ways of using patter- matching (in section 2.2), syntactic-based (in section 2.3), semantic-based (in section 2.4, and annotation-based (in section 2. In addition, section 2.3 covers basic knowledge background about Ripple Down Rules (RDR), while section 2.2 presents GATE framework and its JAPE grammar that we have been working on.1 Question analysis in question answering systems Kinds of question answering systems range from close-domain systems (aiming to answer questions in a specific domain) to open-domain systems (aiming to answer all of asked questions). In our experiment, the open-domain systems focus on re- trieving and ranking related documents corresponding with the input, while the close-domain systems focus on analysis natural language questions to extract reli- able terms.
Therefore, our related works come from reviewing rule-based question analysis approaches in specific domain driven ones. Natural language question analysis component is the first component in any question answering systems. This component creates an intermediate representation of the input question, which is expressed in natural language, to be utilized in the rest of the system. The basis of the question parser is question classification.
3 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Literature review Subsequently, natural language questions analysis techniques are used to identify keywords and semantic relations in input questions.1 Question classification Question Classification (QC) can be defined as the task of mapping a given question to one of k classes based on the possible types of the answers (Li and Roth, 2002). This classification provides semantic constraints based on the expected answers (Li and Roth, 2006). The approach applied in early QC systems to identify question-class is based on original regular expression model (Li, 2002).