Posts Tagged ‘artificial intelligence’

Improving Chatbot Accuracy -Draft

Sunday, April 12th, 2009
This entry is part 5 of 13 in the series The State of Chatbots

Researchers have employed a variety of methods to improve their chatbot’s accuracy. Most current chatbots use a dialog management module and knowledge base and rules, which they use with templates to match user input. Improving chatbot accuracy may be accomplished through expanding the chatbot knowledge base, improving upon the standard rule-based conversation method for chatbots, or using alternative methods to the standard chatbot rule-based conversation method.

Expanding a knowledge base from which a chatbot may learn can improve accuracy. A drawback to creation of chatbot knowledge bases is that it is usually accomplished through hand coding, or hard-coding, which is time and labor intensive (?). The time taken to program, test and refine a chatbot’s knowledge base can be extensive. Furthermore, hard-coding the rules into a knowledge base may be restricted by the style and ability of the programmer. However, if chatbots could be programmed to learn from an established knowledge base themselves, it would reduce the time needed to create large knowledge bases for the chatbot and potentially improve accuracy of responses given to the user.

One researcher has automated chatbot learning by using language modeling to train chatbots in three different languages (Abu Shawar & Atwell, 2005). The authors created a model of a language to build a corresponding chatbot, and through a java application they translated text-based corpora into AIML. They approached the problem using two different machine learning techniques: first word and the most significant word approaches. Armed with this solution, they retrained their Alicebot with transcripts from human dialog, they compared human and chatbot to human and human dialog. A frequency list was built (words listed most utterances), patterns (the number of times this word appears with another word) and templates were established, and patterns and templates were rearranged to build AIML files. The authors concluded that this machine learning approach based on transcripts of human dialog, enabled their chatbot to converse in different styles and languages.

Another researcher used autonomic knowledge base creation and machine learning approaches to increase the efficiency of building their chatbot knowledge database. They presented an approach for extracting a chatbot knowledge base using <thread-title, reply> pairs for a new knowledge base from a corpora (an online discussion forum) (Huang, Zhou, & Yang, 2007). They normalized and cleaned the corpora by removing irrelevant replies, used humans to rate the training set, and employed author identity to grade the quality of a reply. The researchers applied a machine learning approach to a specific domain of large repositories of archived threads and reply records from online discussion forums. Their results showed that they were able to extract 2,000 pairs in two minutes. Given the speed of their results, the authors considered their approach to constructing a knowledge base for a chatbot to be superior to the by-hand” approach.

Yet another researcher has also focused on automatic chatbot knowledge base creation (Wu, Wang, Weisheng, & Li, 2008). They used a classification model based on rough-set assembly theory to process incomplete data, as applied to a system model data analysis on a controlled set. This  data analysis was coupled to ensemble machine learning algorithms, and was based on related replies and IR-related replies. The authors also concluded that their approach of automatic acquisition of the knowledge for a chatbot was effective.

Others have tried to improve the current rule-based approach to learning for chatbots (Pilato, Vassallo, Augello, Vasile, & Gaglio, 2005). The researchers used latent semantic analysis (LSA) to attempt to predict replies in conversations with humans. They built their chatbots on Alicebot’s software, generating one generic and three domain specific chatbots. Their corpora was 850 documents from the Internet to create the knowledge base. They used LSA to generate algorithms that analyzed the corpora and placed it into a matrix which in turn constituted the knowledge base. Upon interaction with a user, the first interactions would be directed towards the general knowledge (generic) chatbot which had the index” for what the other domain-specific chatbots contained within their knowledge base. This generic chatbot would direct the user to each domain-specific chatbot as deemed appropriate (rules as programmed by the developers). The user then interacted with the domain-specific chatbot until its limit of knowledge was reached, and by default, the user  was then directed back to the generic chatbot. The authors concluded that the LSA allowed them to overcome restrictions of the traditional chatbot rule-based approach.

Recently, some chatbot researchers have deviated from using the standard rule-based conversation approach used by most standard chatbots. For example, one approach involves the automatic generation of a trivial dialog phrase database through the use of genetic algorithms (Montero & Araki, 2007). They evaluated the phrase database for correctness using N-gram analysis to generate statistical data, which was then analyzed to observe the system’s performance. The authors approach is different from traditional AIML rule-based natural language interfaces in that they used phrases and associations. They acknowledge that creating a hand-crafted knowledge base (a dialog corpus) is highly time-consuming and difficult. They generated pairs of phrases, applying fitness function of a genetic algorithm which indicated a well-generated phrase, then evaluated to see if it was acceptable phrase. They used a ratio of acceptable phrases divided by well-generated phrases.

Another deviation from the standard rule-based conversation approach is the use of “semantic-driven interaction in an intelligent system that uses natural language dialog to explain concepts” (Pirrone, Pilato, Rizzo, & Russo, 2007). By means of a 3-tier system, their study attempted to utilize Latent Semantic Analysis (LSA) to cluster documents in a vector space (creating relationships between different words within that vector) (Pirrone). The architecture contained business, presentation and data tiers that consisted of two main parts: an assessment component and supply component. The researchers used the CYC knowledge base in this application to integrate the ontology with other parts of their application. The authors believe that their ontology helped to create relationships (context) and the vectors as a self-organizing map. They considered their approach to  improve the efficiency of their chatbot.

One group has deviated from the standard rule-based approach by combining an expanded knowledge base with machine learning and a neural network (Sing, Fung, Wong, & Depickere, 2007). They crafted an artificial intelligent neural network identity (AINI) based on understanding and reasoning of natural language, rather than being based on pattern-matching like other chatbots. AINI is especially unique since it uses a top-down natural language query in a multi-layered natural language query engine. It uses an AIML engine, natural language understanding and reasoning, FAQ metadata and a spellchecker in a three-tier layered architecture with a mySQL back-end. AINI can parse input, which goes into a natural language reasoning module where sentences are separated into words. Keywords are then chosen and a document retrieval from the Web (Internet) is executed. Information is extracted from the Web, answers are ranked using advanced reasoning, and a requisite response is given. The authors concluded that their agent performed comparably to ELIZA and  ALICE using this new methodology. Given that their chatbot uses a different approach to the rule-based pattern matching used by ELIZA and ALICE, it is understandable that they would compare the performance of their chatbot to these common chatbots. However, the authors plan to improve their chatbot performance further by adding more machine learning algorithms and expanding the chatbot’s knowledge base. Their expectation is that their chatbot’s performance would surpass that of ELIZA and ALICE.

Improving Human-Like Qualities of Chatbots -Draft

Saturday, April 11th, 2009
This entry is part 4 of 13 in the series The State of Chatbots

Some researchers are designing chatbots with the intent of integrating more natural human-like interactions (De Angeli & Brahnam, 2008). Specifically, the developer may program certain responses that would sacrifice accuracy, but confer more human-like traits (Sing et al., 2006). For example, if a chatbot is presented with a math problem it could wait, as if to imitate thinking about the problem, or even give the wrong answer. This could be interpreted by the user as a human trait (failing or making a mistake), but in reality, it is a trick built into the programming. Researchers have attempted to add a sense of humor, through the use of self-contained jokes to their version of the chatbot ALICE (De Boni, Richardson, & Hurling, 2008). One could envision a scenario where a user would ask a question and the chatbot would reply: Jim, I’m not a machine, Im a doctor!”, I’m on my break, come back later.” or Are you sure you want me to check for this, I know its a waste of time”, which gives a jocular feel to the conversation.

Attempts to improve human-like characteristics include personality matching and relationship maintenance (De Boni et al., 2008; Abbatista, Degemmmis, Licchelli, Lops, Semeraro, & Zambetta, 2002). One researcher used shallow parsing and statistical natural language processing methods to change the style of interaction of their chatbot according to personality matching deboni08. For example, the chatbot could take on a submissive role when the user is portraying a dominate one. However, the authors found that users’ feelings were mixed about the chatbot using this style of interaction. Two different groups have developed chatbots that build upon previous interactions with the same user (De Boni et al., 2008; Abbatista et al., 2002). If a chatbot could incorporate the ability to recognize” a logged-in user and interact accordingly, the chatbot would be seen to be engaging in relationship maintenance (Abbatista et al., 2002). The chatbot would use a stored user profile and make recommendations in a proactive fashion (Abbatista et al., 2002). Both studies found that familiarity with a user did produce a more positive view of the chatbot’s interaction with that user.

Improving the chatbot’s ability to shift conversational topics is another approach to improving its human-like quality. Chat between humans is dynamic and a single utterance can become the focus of conversation (Montero – Enhancing computer). Another subsequent utterance (considered a catastrophe) may change the topic subject and the focus of the conversation would shift. One study attempted to model human chat by modeling relating utterances and changing topics more naturally (Montero & Araki, 2005). Based on ALICE, the chatbot database had categories to match patterns (user input and a template for chatbot reply). The authors programmed the chatbot to ask a question if it did not know a reply, trying to smoothly shift topic. Their methods included using a Data mining tool called KeyGraph to identify relationships between terms in a document, in particular, co-occurrence relationships of both high-probability and low-probability events. Utterances were broken down into words, visual results showed clusters of interrelated sentences, and links showed the shift in topics during chat. The researchers added critical categories by making the chatbot interject intelligent questions. Finally, they tested their chatbot’s performance by having one user interact with their chatbot, after which the user then gave an opinion of their conversation with the chatbot. Their results showed that the user rated the experience as better after adding the ability for the chatbot to shift topics. Although the study results were subjective, using this type of modeling could be a viable approach for a chatbot to control conversation flow.

Another attempt to add a proactive conversational element to a chatbot used a mixed-initiative interaction (L’Abbate et al., 2005). A mixed initiative refers to a exible interaction strategy where each participant can contribute to task what it does best. The agent can show initiative in conversation by introducing a change in conversation  flow to improve believability. This approach was tested in Virtual Insurance Risk Management (VIRMA), an on-line risk management tool. Keeping with the rule-based approach, they were able to create user profiles and reduce the number of question and answer options. They tested the tool by having the users interact with the Risk Manager Online (RMO) user interface. From their results, the authors concluded that their approach enabled the conversations to be more domain specific, and improved the quality of the human-chatbot interaction.

Therefore, using approaches such as programming a chatbot to mimic human behavior like humor or shift conversations in certain situations, and adding conversation memory to the chatbot design, may confer more humanity to a chatbot. Perhaps combining a number of these tricks could increase the feeling of communicating with a human conversationalist.

Building Better Chatbots -Draft

Saturday, April 11th, 2009
This entry is part 3 of 13 in the series The State of Chatbots

The major goal of building a better chatbot is to improve its interactions with humans. A wide variety of techniques including developing different architectures, incorporating quirks or tricks, or using different machine learning approaches have been used to improve either chatbot accuracy or human-like qualities. First, some ways that researchers are trying to improve human-like qualities of chatbots will be discussed, followed by some methods that researchers are trying to improve the accuracy of chatbots.

How do Humans View Chatbots? -Draft

Saturday, April 11th, 2009
This entry is part 2 of 13 in the series The State of Chatbots

Since chatbots have moved into the public realm, there has been interest in evaluating how users interact with chatbots. For example, after analyzing conversations with the chatbot jabberwacky, one study found that the topics and style of conversations were broad (De Angeli & Brahnam, 2008). Users displayed different attitudes ranging from nice to nasty and derogatory. It was often found that users switched style and personalities during conversation with the chatbot. In one experiment, users were found to continue to abuse chatbots longer than they would abuse another human. Some of the reactions did not appear driven by specific reasons.

Other studies have found specific reasons for user disenchantment with chatbots. Another researcher conducted an observational study with an ELIZA-style chatbot, using a systematic, but subjective evaluation (Kirakowski, O’Donnell, & Yiu, 2007). Fourteen college students interacted with the chatbot for 3 minutes, after which participants were given a copy of their conversation transcript and were asked to identify unnatural examples. Essentially, they evaluated the human-chatbot interaction as compared to human-human interaction, and identified general differences in interaction and speci c discrepancies. “Maintenance of themes, failure to respond to a question, appropriately responding to social cues (questions), use of formal or colloquial language, greetings and personality, offers a cue, phrases delivered at inappropriate times, damage control.” (Kirakowski et al., 2007). Other users may find a tool unsatisfactory because it did not answer questions accurately (Abu Shawar & Atwell, 2005).

The specific reasons cited in these studies provide a focus for researchers to address their efforts to improve human and chatbot interaction. The following section presents different ways in which developers are attempting to built better chatbots.

Rule-Based Conversation -Draft

Saturday, April 11th, 2009
This entry is part 1 of 13 in the series The State of Chatbots

The majority of current chatbots use a rule-based approach to interact with the user. In order to imitate human conversations, developers use a linguistic model combined with computational algorithms to build chatbots. Depending on the chatbot, rules can be based on simple textual pattern matching or complicated rules based on inference mechanisms (De Angeli & Brahnam, 2008).

Chatbots analyze input and sends is to a dialog manager, which enables the chatbot to provide contextual information back to user. \Generally behind such dialog managers lies a complex-rich rule-based system.” (Gandhe & Traum, 2007). Chatbots view utterances as a sequence of tokens (divided up sentences) and methods are applied to these tokens such as random bot, nearest context, segmented-nearest context, and segmented-random. Random bot replies with a random utterance from a list of replies (Gandhe & Traum, 2007). Nearest context chatbots possess local coherence and so do not choose a random reply but choose a reply using a vector space model that has the nearest context to the current ongoing dialog. Segmented-nearest context chatbots try to use the broader context of the dialog as well as local coherence. Segmented-random chatbots use only global coherence so keeps coherence, but selects an utterance randomly that matches the context.

Pattern matching in chatbots means that they determine the most relevant keywords extracted from the last phrase inputted by the user and generate responses according to \if-then-else” rules (Zdravkova, 2000). Their ability can be enhanced by repeating slightly modiffed replies, and including statements that define the direction of the conversation with the user (Zdravkova, 2000).

AIML files contain the rules for chatbots (A.L.I.C.E. foundation website, 2009). The language AIML (first used with ALICE), is an extension of XML. AIML allows the use of categories and topics, and has iterative capabilities and logic functionality (Shawar et al., 2007). It consists of data objects made up of units called topics and categories. Categories are the lowest-level and are rules for pattern matching (user input and template to generate a response). Topics are optional and are a top-level unit with a related set of categories.

Natural Language Processing -Draft

Saturday, April 11th, 2009
This entry is part 8 of 13 in the series The State of Chatbots

Chatbots need to effectively process natural language. Since starting around the 1960′s, natural language processing (NLP) research has had slow progress until the 1990′s (Lester, Branting, & Mott, 2004). NLP research has been greatly enhanced by development of large corpora of tagged text, as well as by development of better statistical machine learning and other empirical techniques of extracting information from these corpora (Lester et al., 2004). Accordingly, chatbots are now able to more effectively process natural language.

The following are three general steps of chatbot Natural Language Processing according to (Lester et al., 2004):

  1. The First step entails breaking down the utterances (statement). This syntactic analysis separates the statement into parts of speech (noun, verb,etc) using tagging and parsing to define the different parts of the text. There are different approaches to syntactic analysis, and vary greatly according to the type of language and corpora used.
  2. The second step entails reference resolution which involves a discourse analysis of the utterance to create meaningful relationships. For example, this step would resolve the equivalent relationship of the word I” with the word ME”. After relationships are created, a new string would be crafted from the resolution process.
  3. The third step happens when the result of the string is passed to a dialog manager for further processing. An example would be comparing the string (pattern matching) and determine if it is equal or not to another string.

Share This

  • RobertWhetsel.com is a BLOG by a computer scientist who works for a Think Tank specializing in Information Assurance planning and policy for the DoD. He is the founder of the Open Business Foundation, and the former CEO for RavenSong Open Technologies in Frederick, Maryland. E-mail him at rwhetsel@ravensong.com.
  • Series

  • Cloud Tag