«EPISODIC MEMORY MODEL FOR EMBODIED CONVERSATIONAL AGENTS by MIGUEL ELVIR B. S. University of Central Florida, 2006 A thesis submitted in partial ...»
EPISODIC MEMORY MODEL FOR EMBODIED CONVERSATIONAL AGENTS
B. S. University of Central Florida, 2006
A thesis submitted in partial fulfillment of the requirements
for the degree of Master of Science
in the School of Electrical Engineering and Computer Science
in the College of Engineering and Computer Science
at the University of Central Florida
Summer Term © 2010 Miguel Elvir ii ABSTRACT Embodied Conversational Agents (ECA) form part of a range of virtual characters whose intended purpose include engaging in natural conversations with human users. While works in literature are ripe with descriptions of attempts at producing viable ECA architectures, few authors have addressed the role of episodic memory models in conversational agents. This form of memory, which provides a sense of autobiographic record-keeping in humans, has only recently been peripherally integrated into dialog management tools for ECAs. In our work, we propose to take a closer look at the shared characteristics of episodic memory models in recent examples from the field. Additionally, we propose several enhancements to these existing models through a unified episodic memory model for ECA’s. As part of our research into episodic memory models, we present a process for determining the prevalent contexts in the conversations obtained from the aforementioned interactions. The process presented demonstrates the use of statistical and machine learning services, as well as Natural Language Processing techniques to extract relevant snippets from conversations. Finally, mechanisms to store, retrieve, and recall episodes from previous conversations are discussed. A primary contribution of this research is in the context of contemporary memory models for conversational agents and cognitive architectures. To the best of our knowledge, this is the first attempt at providing a comparative summary of existing works. As implementations of ECAs become more complex and encompass more realistic conversation engines, we expect that episodic memory models will continue to evolve and further enhance the naturalness of conversations.
iii To my family, friends, and to those whose invaluable support guided me… iv
ACKNOWLEDGMENTSIn the course of developing the research material that this thesis represents, I have discovered that successful projects often involve the contributions of several individuals playing overlapping and supportive roles. Thus, I would be remiss not to recognize these individuals and mention the manner of their contribution. On the academic side, this document could perhaps not have been produced without the constant mentoring of my adviser and editor-in-chief, Dr.
Avelino J. Gonzalez, as well as Dr. Ronald DeMara. Both of their insights into the novel topics presented herein where of significant value. Of similar value is the support of their research team, my current colleagues, whose help extends beyond allowing me to recognize architectural requirements and served as encouragement throughout the writing. Several individuals at the National Science Foundation, namely Dr. Alexander Schwarzkopf, Rita Rodriguez, and Dr. Babu DasGupta provided a wealth of perspective towards the role our research plays in the real world.
Similarly, this work couldn’t have taken off as it did without the support and strength obtained from God and my family.
There are undoubtedly a myriad of contributors that in one way or another shaped the outcome of this research and who have not been mentioned. Their importance is well worth recognizing, and it is my hope that they find a bit of themselves in the ensuing work.
LIST OF FIGURES
LIST OF TABLES
LIST OF EQUATIONS
CHAPTER 1 INTRODUCTION
1.1. Research Motivation
1.2. Alan Turing and the Turing Test
1.3. From ELIZA to Chatterbots
1.3.1. Chatterbots from the Loebner Period
1.3.2. An Assessment of Loebner Period Chatbots and Beginnings of ECAs
1.4. Dialog Systems and Embodied Conversational Agents
1.4.1. Early History of ECAs
1.4.2. Issues in Managing Multimodal Interaction for ECAs
1.4.3. Issues in Collecting and Mining Information for Use in Memory
1.5. Memory in Cognitive Architectures
1.5.1. The BDI Framework
1.5.2. Memory in BDI
1.5.3. SOAR Cognitive Architecture
1.5.4. Memory in SOAR
1.6.1. Thesis Organization
CHAPTER 2 RELATED WORKS IN DIALOG-BASED EPISODIC MEMORY
2.1. Introduction to Episodic Memory in Cognitive Architectures
2.2. Review of A Conversational Agent as a Museum Guide
2.2.1. The Role of Memory in Max
2.3. Sergeant Blackwell, Sergeant Star, and Hassan
2.3.1. Cognitive Architecture and Design
2.3.2. The Role of Memory in Sergeant Blackwell, Sergeant Star, and Hassan
2.4. H. C. Andersen Review
2.4.1. Cognitive Architecture and Design
2.4.2. The Role of Memory in HCA
2.5. Episodic Memory in Cognitive Architectures of ECAs
vi CHAPTER 3 PROBLEM DEFINITION
3.1. General Problem
3.2. Specific Problem
CHAPTER 4 EPISODIC MEMORY PROTOTYPE
4.1. Memory Model: Centralized vs. Decentralized Memory
4.2. System Architecture: Pipeline Approach
4.3. Capturing the Conversation
4.4. Filtering and Storing Conversational Memories
4.4.1. Storing Raw Data
4.4.2. Managing Episodic Memories
4.5. Episodic Memory Structures
4.5.1. Conversational Structures
4.5.2. Dialog Tables
4.5.3. User Information
4.5.4. Conversational Log
4.5.5. Contextualized Records
4.5.6. Dialogue Topics
4.5.7. Using the Relationships Between Dialog Tables for Gisting
4.5.8. Perfect Memory vs. Forgetting
4.6. Retrieving Episodic Memories
4.7. Accessing Episodic Memory
4.7.1. Classes and Interfaces in the Memory Client
4.8. Analysis Services
4.9. Comparison to Existing Works
CHAPTER 5 PROTOTYPE EVALUATION AND HYPOTHESES TESTING
5.1. Experiment One
5.1.1. Video Conversations
5.2. Experiment One Hypothesis
5.3. Experiment One Results
5.3.1. Distribution Analysis
5.4. Experiment Two
5.5. Experiment Two Hypothesis
5.6. Experiment Two Results
5.7. Experiment Three
5.8. Experiment Three Hypothesis
5.9. Experiment Three Results
5.10. Gisting Results
5.11. Multi-modal and Real-Time Measurements
5.12. Summary of Experimentation Results
CHAPTER 6 CONCLUSIONS AND FUTURE WORK
6.1. Summary of Implementation and Results
6.3. Suggestions for Future Work
APPENDIX A: ISBISTER AND DOYLE’S ECA TAXONOMY
APPENDIX B: GISTING ALGORITHM PSEUDOCODE
APPENDIX C: PROJECT FEEDBACK FORM
APPENDIX D: EXPERIMENT TWO FEEDBACK
APPENDIX E: EXPERIMENT TWO TRANSCRIPTS
APPENDIX F: EXPERIMENT THREE TRANSCRIPTS
APPENDIX G: GISTED TOPICS FROM EXPERIMENTS TWO AND THREE
APPENDIX H: IRB APPROVAL LETTER
LIST OF REFERENCES
LIST OF FIGURESFigure 1 - Timeline of chatterbot development with overlay of Whitby's first three phases and the current Loebner period, corresponding to Whitby’s Phase IV.
Figure 2 - Rea's architecture as described by Cassell et al. (2000)
Figure 3 - BDI model as perceived by (Chong et al., 2007) and adapted from (Guerra-Hernández et al., 2005)
Figure 4 - Soar memory architecture (Nuxoll & Laird, 2007)
Figure 5 - Max's deliberative component and the framework for memory-system interaction (Kopp et al., 2005)
Figure 6 - Hassan's architecture for language components. (Traum et al., 2008)
Figure 7 - HCA's system architecture, as seen in (Bernsen & Dybkjær, 2004)
Figure 8 - HCA's character module, as seen in Bernsen et al. (2004)
Figure 9 - Episodes are centralized (3rd from left) while knowledge bases are decentralized in Max. (Kopp et al., 2005)
Figure 10 - Episodic memory architecture stack with four core components.
Figure 11 - Sample points of origin for information gathered from a conversation.
Figure 12 - The episodic memory architecture acquires conversation data by using memory interfaces (highlighted)
Figure 13 – Block diagram of algorithm and system operation.
Figure 14 – Pseudocode for method sp_InsertNewPhrase to initialize the service input stage.... 81 Figure 15 – Pseudocode for method XmlGetComplexPhrasesFromEpisodeSegment.................83 Figure 16 – Pseudocode for method GetComplexPhrases
Figure 17 - Tree representation of a sentence parsed and grouped by clause depth.
Figure 18 - Entity Relationship Diagram (ERD) for contextual knowledge in episodic memory.
Figure 19 - Initial set of facts contained in a new user's user model (autobiographical data)....... 96 Figure 20 - Relationships between dialogue and dialogue context tables.
Figure 21 - Sample dynamic context structure which describes an episode segment................ 100 Figure 22 - Client used to test episodic memory architecture.
Figure 23 - Class diagram for episodic memory client utility.
Figure 24 - Structure of episode summary returned by XmlGetEpisodeSummary.
Figure 25 - Chronological presentation of episode summaries.
Figure 26 - Sample XML structure returned by XmlGetEpisodeInformation.
Figure 27 - GUI developed for Experiment One
Figure 28 – Initial percentage-based histogram and distribution fits for user responses............ 125 Figure 29 – Noise set normality test using the Anderson-Darling test. Normality is rejected in the noise set case
Figure 30 – Topics set normality test using the Anderson-Darling approach. Normality is rejected in the Topics set case.
Figure 31 – Categorization of user responses as “mostly agree” (10) or “less likely to agree” (0) for the Noise set and Topics set.
Figure 32 - Chatbot GUI developed to test Experiment Two
ix Figure 33 – Comparison of user feedback for questions 1-8. Q9 represents the value assigned to the relevance of the topics gisted during the conversation.
Figure 34 – Visual representation of relationships between conversations in episodic memory.
LIST OF TABLESTable 1 - Disciplines related to ECA research. Adapted from Isbister and Doyle (2002)............14 Table 2 - Criteria for success for the ECA taxonomy by Isbister and Doyle (2002).
Table 3 - Sample evaluation techniques for ECAs according to Isbister and Doyle (2002).........15 Table 4 - Description of memory implementations in various cognitive architectures and frameworks, as presented by Chong et al. (2007)
Table 5 - Roles of dynamic memory models in Max's memory model
Table 6 - Term and topic extraction case study.
Table 7 - Topical key phrases extracted from two 2.5 minute video interviews.
Table 8 – Statistics for topical phrases of user given values.
Table 9 – Statistics for noise phrases of user given values.
Table 10 – Feedback questions and rating scale used for Experiment Two
Table 11 – Turns, Duration, Turns to Tasks, and Cues for Experiment Two
Table 12 – Turns, Duration, and Turns to Tasks for Experiment Three
Table 13 – Total keyphrases gisted per user conversation compared to the total turns.............. 139 Table 14 – Top phrases gisted from Experiments Two and Three.
Table 15 – TF*IDF distances and edge weights between Experiments Two and Three episodes.
Table 16 – Average response times of the conversation participants in Experiment Three....... 145 Table 17 – Raw data from user feedback to Questions 1-9 in Experiment Two
LIST OF EQUATIONSEquation 1
Conversational memory, in this discussion, refers to the representation and storage of knowledge acquired through a multiparty conversation. More generally, it is a form of episodic memory, which is introduced in future sections. Intelligent systems in the form of virtual characters that engage in conversation with humans through spoken interactions are often referred to as Embodied Conversational Agents (ECAs). These agents attempt to anthropomorphize, or make human-like, the discourses between computers and humans. One critical cognitive faculty frequently overlooked in the development of dialog components when implementing ECAs is the ability to use and exploit episodic memory.
This form of memory, which provides a sense of autobiographic record-keeping in humans, also presents a valuable opportunity to create more realistic interactions in current and future conversations for ECAs. In our work, we take a closer look at the shared characteristics of episodic memory models in recent examples from the field. Additionally, we present several enhancements to these existing models through a unified episodic memory model for ECA’s.
While various types of memory exist in Artificial Intelligence (AI), we focus on the issues pertaining to knowledge acquired through conversation. The sections to follow stage the motivation for our research and a topical background for understanding conversational memory.