Tài liệu A vietnamese text based conversational agent

A Vietnamese Text-based Conversational Agent Nguyen Quoc Dai 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 November 2011 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 substantial 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, November 23rd , 2011 Signed ........................................................................ i ABSTRACT The first step that a question answering system must perform is to transform an input question into an intermediate representation. Most published works so far use rule-based approaches to realize this transformation in question answering systems. Nevertheless, in existing rule-based approaches, manually creating the rules is error-prone and expensive in time and effort. In this thesis, we focus on introducing a rule-based approach that offers an intuitive way to create compact rules for extracting intermediate representation of input questions. Experimental results are promising where our system achieves reasonable performance and demonstrate that it is straightforward to adapt to new domains and languages. More importantly, this thesis introduces a Vietnamese text-based conversational agent architecture on specific knowledge domain which is integrated in a question answering system. When the question answering system fails to provide answers to user input, our conversational agent can step in to interact with users to provide answers to users. Experimental results are promising where our Vietnamese text-based conversational agent achieves positive feedback in a study conducted in the university academic regulation domain. Publications: ? Dai Quoc Nguyen, Dat Quoc Nguyen and Son Bao Pham. A Vietnamese Text-based Conversational Agent. In Proc. of The 25th International Conference on Industrial, Engineering & Other Applications of Applied Intelligent Systems (IEA/AIE 2012), Springer-Verlag LNAI, pp. 699-708. ? Dai Quoc Nguyen, Dat Quoc Nguyen and Son Bao Pham. A Semantic Approach for Question Analysis. In Proc. of The 25th International Conference on Industrial, Engineering & Other Applications of Applied Intelligent Systems (IEA/AIE 2012), Springer-Verlag LNAI, pp. 156-165. ? Dat Quoc Nguyen, Dai Quoc Nguyen and Son Bao Pham. Systematic Knowledge Acquisition for Question Analysis. In Proc. of the 8th International Conference on Recent Advances in Natural Language Processing (RANLP 2011), ACL Anthology, pp. 406-412. ii iii ? Dai Quoc Nguyen, Dat Quoc Nguyen, Khoi Trong Ma and Son Bao Pham. Automatic Ontology Construction from Vietnamese text. In Proceedings of the 7th International Conference on Natural Language Processing and Knowledge Engineering (NLPKE’11), IEEE, pp. 485-488. ? Dat Quoc Nguyen, Dai Quoc Nguyen, Son Bao Pham and Dang Duc Pham. Ripple Down Rules for Part-Of-Speech Tagging. In Proc. of 12th International Conference on Intelligent Text Processing and Computational Linguistics (CICLING 2011), Springer-Verlag LNCS, part I, pp. 190-201. ? Dai Quoc Nguyen, Dat Quoc Nguyen and Son Bao Pham. A Vietnamese question answering system. In Proceedings of the 2009 International Conference on Knowledge and Systems Engineering (KSE 2009) , IEEE CS, pp. 26–32. 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 younger brother, Nguyen Quoc Dat, 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 sincerely acknowledge the Vietnam National University, Hanoi, Toshiba Foundation Scholarship, and especially Dr. Pham Bao Son for supporting 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! iv To my family ♥ v Table of Contents 1 Introduction 1.1 A Semantic Approach for Question Analysis . . . . . . . . . . . . . . 1.2 A Vietnamese Text-based Conversational Agent . . . . . . . . . . . . 1.3 Thesis Organisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 2 3 2 Literature review 2.1 Text-based conversational agents . . . . . . 2.1.1 Using keywords for pattern matching 2.1.2 Using the sentence similarity measure for pattern matching . . . . . . . . . 2.2 FrameScript Scripting Language . . . . . . . 2.3 Question answering systems . . . . . . . . . 4 4 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 . . . . . . . . . . . . . . 9 . . . . . . . . . . . . . . 12 3 Our Question Answering System Architecture 3.1 Vietnamese Question Answering System . . . . . . . . . . . . . . 3.1.1 Natural language question analysis component . . . . . . . 3.1.1.1 Intermediate representation of an input question 3.1.1.2 Question analysis . . . . . . . . . . . . . . . . . . 3.1.2 Answer retrieval component . . . . . . . . . . . . . . . . . 3.2 Using FrameScript for question analysis . . . . . . . . . . . . . . . 3.2.1 Preprocessing module . . . . . . . . . . . . . . . . . . . . . 3.2.2 Syntactic analysis module . . . . . . . . . . . . . . . . . . 3.2.3 Semantic analysis module . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 15 16 16 17 18 19 19 20 22 4 Text-based Conversational Agent for Vietnamese 24 4.1 Overview of architecture . . . . . . . . . . . . . . . . . . . . . . . . . 24 4.2 Determining separate contexts . . . . . . . . . . . . . . . . . . . . . . 25 4.3 Identifying hierarchical contexts . . . . . . . . . . . . . . . . . . . . . 27 vi TABLE OF CONTENTS vii 5 Evaluation and Discussion 5.1 Experimental results for Vietnamese text-based conversational agent . . . . . . . . . . . . 5.2 Question Analysis for English . . . . . . . . . . . . . . . . . . . . . . 5.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 6 Conclusion 34 A Scripting patterns for English question analysis 36 B Definitions of question-class types 38 C Definitions of question-structures 40 29 31 33 List of Figures 2.1 2.2 O’Shea et al.’s conversational agent framework. . . . . . . . . . . . . 7 Aqualog’s architecture. . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.1 3.2 Architecture of our question answering system. . . . . . . . . . . . . . 16 Architecture of the natural language question analysis component using FrameScript. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 4.1 Architecture of our Vietnamese text-based conversational agent. . . . 25 viii List of Tables 4.1 4.2 4.3 4.4 Script examples of “subjects” . . . . . . . Transformations between contexts . . . . Order of transformation rules . . . . . . Ordered transformation between contexts . . . . 26 27 28 28 5.1 5.2 5.3 5.4 5.5 5.6 5.7 List of transformations among contexts . . . . . . . . . . . . . . . . . Unsatisfying analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . The satisfied degree of students . . . . . . . . . . . . . . . . . . . . . Number of rules corresponding with each question-structure type . . . Number of rules with conditional responses . . . . . . . . . . . . . . . Number of questions corresponding with each question-structure type Error results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 30 31 31 32 32 32 ix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . List of Abbreviations CA QA IR IE GATE JAPE NLIDB POS NLP GUI Conversational Agent Question Answering Information Retrieval Information Extraction General Architecture for Text Engineering Java Annotation Patterns Engine Natural Language Interface to DataBase Part-of-Speech Natural Language Processing Graphic User Interface x Chapter 1 Introduction 1.1 A Semantic Approach for Question Analysis The goal of question answering systems is to give answers to the user’s questions instead of ranked lists of related documents as used by most current search engines (Hirschman and Gaizauskas, 2001). 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. For the task of translating a natural language question into an explicit intermediate representation of the complexity in question answering systems, most published works so far use rule-based approach to the best of our knowledge. Some question answering systems such as (Lopez et al., 2007; Phan and Nguyen, 2010) manually defined a list of sequence rule structures to analyze questions. However, in these rule-based approaches, manually creating the rules is error-prone and expensive in time and effort. In this thesis, we present an approach to return an intermediate representation of question via FrameScript scripting language (McGill et al., 2003). Natural language questions will be transformed into intermediate representation elements which include the construction type of question, question class, keywords in question and semantic constraints between them. Framescript allows users to intuitively write rules to directly extract the output tuple. 1 2 1.2 Chapter 1. Introduction A Vietnamese Text-based Conversational Agent A text-based conversational agent is a program allowing the conversational interactions between human and machine by using natural language through text. The text-based conversational agent uses scripts organized into contexts comprising hierarchically constructed rules. The rules consist of patterns and associated responses, where the input is matched based on patterns and the corresponding responses are sent to user as output. We focus on the analysis of input text in building a conversational agent. Recently, the input analysis over user’s statements have been developed following two main approaches: using keywords (ELIZA (Weizenbaum, 1983), ALICE (Wallace, 2001), ProBot (Sammut, 2001)) and using similarity measures (O’Shea et al., 2010; Graesser et al., 2004; Traum, 2006) for pattern matching. The approaches using keywords usually utilize a scripting language to match the input statements, while the other approaches measure the similarity between the statements and patterns from the agent’s scripts. In this thesis, we introduce a Vietnamese text-based conversational agent architecture on a specific knowledge domain. Our system aims to direct the user’s statement into an appropriate context. The contexts are structured in a hierarchy of scripts consisting of rules in FrameScript language (McGill et al., 2003). In addition, our text-based conversational agent was constructed to integrate in a Vietnamese question answering system. Our conversational agent provides not only information related to user’s statement but also provides necessary knowledge to support our question answering system when it is unable to find an answer. The knowledge domain we used to build our text-based conversational agent is the academic regulation at Vietnam National University, Hanoi (VNU). The academic regulation book helps students to know the course programs, the regulation of examinations, the discipline at VNU... However, most students don’t prefer reading the academic regulation book. Therefore, our contribution creates an interaction channel to offer the necessary information to students. Once students give their statements that they are interested in the academic regulation, our text-based conversational agent responses these statements by providing the related information in detail. Furthermore, our conversation agent also interacts with students by offering the option to ask if students want to know other information. 1.3. Thesis Organisation 1.3 3 Thesis Organisation This dissertation consists of 6 chapters. In chapter 2, we provide some literature reviews and describe our Vietnamese question answering system architecture, in which we present a method for converting a natural language question into an intermediate representation, in chapter 3. We propose our Vietnamese text-based conversational agent architecture in chapter 4. We describe our experiments and discussions in chapter 5, and conclusion will be presented in chapter 6. Chapter 2 Literature review In this chapter, we review related works using text-based approaches for conversational agent (CA). Section 2.1 describes the approaches constructing rules to match user’s natural language utterances in the ways of using keywords (in section 2.1.1) and using a sentence similarity measure (in section 2.1.2). In addition, section 2.2 covers the basic knowledge background about FrameScript scripting language that we have been working on, while section 2.3 presents reviews about the question answering systems driving specific-domains. 2.1 Text-based conversational agents 2.1.1 Using keywords for pattern matching ELIZA (Weizenbaum, 1983) was one of the earliest text-based conversational agents based on a simple pattern matching by using the identification of keywords from user’s statement. Then ELIZA transforms the user’s statement to an appropriate rule and generates output response. The procedure that ELIZA responds to an user input to give an appropriate output consists of five steps. • Identify the important keywords appearing in user’s statement. • Define some minimal context within which selected keyword occurs. • Determine an appropriate transformation rule. • Generate the responses when the input text contained no keywords. 4 2.1. Text-based conversational agents 5 • Provide a facilitate editing for scripts on the script writing level. Transformation rules are used to serve decomposing a data string according to certain criteria and reassembling a decomposed string according to certain assembly specifications. Therefore, the input are analyzed based on the decomposition rules triggered by keywords, and responses are generated against the reassembly rules associated with selected decomposition rules. For example, encountering the input sentence: “It seems that you like me” this sentence is decomposed into the four parts: (1) It seems that (2) you by using the decomposition rule: (3) like (4) me (0 YOU 1 ME) The associated response might then be: “What makes you think I like you” by using the reassembly rule: (WHAT MAKES YOU THINK I 3 YOU) An integer 0 in the decomposition rule will match more words and a non-zero integer “n” appearing in a decomposition rules indicates that exactly “n” words will be matched, while an integer 3 in the above reassembly rule shows that the third part of the decomposed sentence is inserted in its place to reply the input sentence. If each word is defined in a dictionary of keywords by scanning an input sentence from left to right, then only decomposition rules containing that keyword need to be tried. An ELIZA script consists mainly of a set of list structures as following: (K ((D1 ) (R1, 1 ) (R1, 2 ) ... (R1, m1 )) ((D2 ) (R2, 1 ) (R2, 2 ) ... (R2, m2 )) . . . ((Dn ) (Rn, 1 ) (Rn, 2 ) ... (Rn, mn ))) where K is the keyword, Di the ith decomposition rule associated with K and Ri, j the j th reassembly rule associated with the ith decomposition rule. Any number of decomposition rules may be associated with a given keyword and any number of reassembly rules with any specific decomposition rule since having no predetermined ordering limitations. 6 Chapter 2. Literature review ALICE (Wallace, 2001) is a text-based conversational agent as chat robot utilizing an XML language called Artificial Intelligence Markup Language (AIML). AIML files consist of category tags representing rules; each category tag contains a pair of pattern and template tag. The entire category is stored in a tree. The system searches the pattern according with an user input by using depth-first search in the tree, and produces the appropriate template as a response. For example, a category below: DO YOU KNOW WHO * IS? AIML uses the * wild-card character in creating patterns to match any non-zero number of words. When an input matched this pattern, the portion bound to the * wild-card may be placed into the response with the markup. This above category reduces any input of the form “Do you know who X is?” to “Who is X”. AIML allows two types of optional context called “that” and “topic”. The that tag appearing inside the category matches the robot’s previous utterance, while the topic tag occurring outside the category indicates a group of categories together and the topic may be set inside any template. Observing a sample topic, like: YES DO YOU LIKE ROMANTIC MOVIES YES DO YOU LIKE ACTION MOVIES When the client says yes, the program must discover the robot’s previous utterance. If the robot asked “Do you like romantic movies?”, the response sent to reply is “What is your favourite romantic movie?”. AIML is clever and simple, and easy for implementation and a good start for beginners writing simple bots. However, it is difficult to write and debug more 2.1. Text-based conversational agents 7 discriminating patterns, and it is very hard to know all the transformations available because AIML depends on self-modifying the input. Sammut (Sammut, 2001) presented a text-based CA called ProBot that is able to extract data from users. ProBot’s scripts are typically organized into hierarchical contexts consisting of a number of organized rules to handle unexpected inputs. Concurrently, McGill et al. (McGill et al., 2003) derived from ProBot’s scripts (Sammut, 2001) build the rule system in FrameScript scripting language (in section 2.2). FrameScript (McGill et al., 2003) provides for the rapid prototyping of conversational interfaces and simplifies the writing of scripts. 2.1.2 Using the sentence similarity measure for pattern matching O’Shea et al. (O’Shea et al., 2008, 2010) proposed a text-based conversational agent framework (shown in figure 2.1) using semantic analysis. All patterns in scripts are the natural language sentences. The pattern matching uses a sentence similarity measure (Li et al., 2006) to calculate the similarity between sentences from scripts and user input. The highest ranked sentence is selected and its associated response is sent as output. Figure 2.1: O’Shea et al.’s conversational agent framework. Scripts used in framework consist of contexts relating to a specific topic of conversation. Each context contains one or more rules, and each rule uses “s” to represent 8 Chapter 2. Literature review a natural language sentence and “r” to represent a response statement. For example, considering a following rule: s: I’m a student r: Which university do you study? With a user’s statement: “I am a master student” or “I am a phd student” This input and the natural language sentences from the scripts are received in order to send the sentence similarity measure. Then sentence similarity measure calculates a firing strength for each sentence pair to rank the sentences. In this above example, the highest ranked sentence selected is “I’m a student” and its associated response sent to user is “Which university do you study?”. The advantages of using a sentence similarity measure for pattern-matching is that rule structures are simplified and reduced in size and complexity. By contrast, this approach can’t retrieve some information from an input to insert into response like using keywords for presented section 2.1.1. Graesser et al. (Graesser et al., 2004) presented a conversational agent called AUTOTUTOR matching input statements in the use of Latent Semantic Analysis. Traum (Traum, 2006) adapted the effective question answering characters (Leuski et al., 2006) to build a conversational agent also employing Latent Semantic Analysis for pattern matching.