Thursday, August 6, 2009

"Best In Class" Parsing for Conversational Interfaces

Several parsing techniques are available for Conversational Interfaces. Different approaches are used by different tools. For example, AIML (AI Markup Language) uses a process of substitution/reduction of common terms and phrases, and then works left-to-right interpreting each word, branching down a "trie" structure.

NLTK (Natural Language Tool Kit) helps you guess at the parts of speech, to attempt to derive semantics from user input. After determining the parts of speech, then you can attempt to parse Verb Phrases and Noun Phrases to determine the meaning of the sentence or question.

Amy Iris can use any available parsing routine. Our objective with Amy Iris is to build a plug-able interface, so that as new parsers are invented, they can be dropped in, and improve the Amy Iris tool.

Case Study: Municipal Conversational Interface
U
sing your knowledge base for parse scoring






My municipal Conversational Interface has a limited knowledge base for this specific application. Municipal Amy Iris has a limited set of knowledge, and needs to be able to interpret interactions from a limited domain, and provide the canned answer based on the interpretation of the input.

Say I start with 100 common questions, and write answers for those questions. Once I have my collection of questions, I can analyze those questions, to try to determine the significant words from them.

Let's work through a few examples:

Say I have a collection of potential questions that include:

A. "How do I report a pothole?"
B. "What day is garbage day?"


Note, no words are in common. My goal is to be able to analyze user input and determine which question from my knowledge base is closest to the user's input. So it's important to know which words are significant in my knowledge base. Further, I need an automated way to do this.

Ideally, I could take user input, and "score" it against each knowledge-base question, to guess which knowledge-base answer to provide. An exact match should produce a perfect score. But ideally, synonyms of "significant" words should also generate high scores.

My intuition tells me that "report" , "pothole", and "garbage" are more significant words than "what" and "how". Further, words not listed, such as "trash", "collection", "pickup", and "pick up", should score well with question B. How do we write a parsing algorithm to score each user input against the knowledge base?

Answer: To do basic parsing, analyze your question set. Collect the entire vocabulary of your question set, as well as synonyms (which can be pulled out of NLTK), and analyze which words in your vocabulary are most significant. Nouns and verbs will tend to be more significant than connector words, adverbs, and other words. Then it's not difficult to write a parsing program that knows that "garbage" and "trash" questions are more related than "pothole" and "trash" questions.


Once the basic parsing has been done, support words like "what", "how", "when" will become more important. Let's say we determine that the user input is a question related to garbage. Look at these variations, and imagine how we might parse them:


B. What day is garbage day?
C. When is trash pick up?

D. What can I throw in the garbage?

All three are "garbage" -type questions, but the two questions of the format "What ... garbage ..." (B & D) are asking different things, while the first two questions are asking almost the same thing (even though there's only one word in common: "is").

Ideally, a parsing scoring system would rank all "garbage"-related questions as similar (whether the word "garbage" or "trash" is used, and two time-related ("What day", "When") as more similar than comparing a time-related question to a non-time related item ("What day" compared to "What [implied garbage items]").

That doesn't seem too tough, does it? Here's how I did it with my simple municipal bot.

Goal:

My Conversational Interface should be able to accept a user's input, and parse it by running through the knowledge base, scoring each answer in the knowledge base. The highest score answer gets displayed to the user.

Further, certain thresholds should be met. If no answer's score exceeds the "did not understand" threshold, then a generic "I don't understand" message is displayed. And if no score exceeds a "pretty good answer" threshold, then maybe we respond with "I'm not sure what you are asking, but if you are asking this question, Q, then the answer is A." Otherwise, confidently give the answer with the highest score.

  1. Create a list of questions. I started with 55 questions.
  2. Create a list of answers to those questions. Word the answers so that they are mildly generic (so if the question is about city hall, the answer might provide the address and the hours). This is the beginning of your expandable knowledge base. Ultimately you'll have many more answers, and maybe even multiple questions that trigger each answer.
  3. Analyze the question list automatically, looking for "significant" words. My analysis parses each question, building a vocabulary. With 55 querstions, my conversational interface had a vocabulary of about 200 words. The more rare words and word combinations tell the difference between one question and another, so we want to identify those.
  4. Expand our vocabulary to define alternate ways to trigger the same answer. NLTK provides access to synonyms and other word data. Synonyms took my bot's vocabulary up to about 2000 words.
  5. Define a scoring algorithm. Generally speaking, the more unique words that you hit on, the higher the score. Connector words and common words should count for very little. Direct matches of rare words should count a lot. Synonym matches should be somewhere in between.

After all is said and done, I ended up with an analysis program and a stand-alone bot program.

The analysis program reads in a CSV file of my questions and answers (Knowledge base), analyzes the questions looking for uniqueness, queries NLTK (Natural Language Too Kit) for Synonyms, and prepares a scoring algorithm. Then it loops, prompting the user for input, and scores each Answer in the Knowledge Base, and dumps out the best answer.

Once my analysis program looked half-way decent, I dumped out the contents of several fields (vocabulary, synonyms, and knowledge base), and stripped down the analysis program to be just the stand-alone bot for you to play with.

Results? Not too bad. Definitely something for me to be able to work with. And something that you can play with, too.

Issues: Certain words just have too many meanings, and so I'll be experimenting with reducing their weight. For example, "Can I burn leaves?", the word "leaves" scores well with yard items, as well as with "departs", "exits" and other meanings.

Let me know if you have any brilliant ideas as to how to improve the parsing algorithm.



Links:

Municipal Amy Iris Web Interface - Try her out here. (remember, there are only 55 answers, so be kind!)

Pastie of the Analysis program - You need NLTK and a Spreadsheet of questions and answers, but you can create your own Conversational Interface with this. It allows you to test your conversational interface.

Pastie of a Stand Alone Municipal Bot - This is way cool. You can experiment with the data that I created by running the Analysis program, above. It's JUST the conversational interface, with the knowledge base hard-coded in the program (to minimize your set-up requirements).


Let me know what you think!

Friday, July 31, 2009

Observations of AIML

I'm currently using AIML as one of the foundations of Amy Iris' brain, particularly for the large body of work that Dr. Richard Wallace and others have done in creating English language reductions. The reductions allow the conversational interface to accept input in a variety of forms, and parse numerous inputs to be equivalent to the brain. Similar to how fraction reduction works - you can say the value of 0.5 in many ways as a fraction: 10 over 5, 6 over 3, 1 over 2. These should all reduce to the same value.

Wallace has created tens of thousands of patterns in AIML that can help interpret English input.

I like AIML, and it certainly was a breakthrough ten years ago. But I am experiencing some challenges with it.

Amy Iris has an architecture with the following four components:

  • Parsing
  • Knowledge Base
  • Context Management
  • User Interface
By separating these four components, I feel as if it will provide a plug-and-play architecture for future growth. If I can drop in a new "best in class" component, the overall product can be improved.

An issue I have with AIML in its current form is that the first three components are intertwined. The Parser and Knowledge Base are completely intertwined (to allow recursive calls that AIML refers to as "<srai>").

And I am currently thinking that standard "Alice-style" Context Management is just not as powerful as I'd like. AIML allows you to work with a couple of pre-defined Context variables (called "that" and "topic"). In addition, AIML allows you to set your own context variables. But context management seems to be one of the weakest links in Alice.

So I'm experimenting with the separation of the four functions with my AIML processor. Separation should permit "best in class" substitution of each component. Should be interesting to see how this goes.


Parsing with AIML

I thought it might help to try to explain for how AIML parses. If you load the ALICE brain into PyAIML or another AIML processor, it will build a giant parse tree (sometimes called a trie). At the root level, there are about 2900 branches (in ALICE), that are the choices for the first word of input. So if you type in the sentence "What time is it?, you will go down the "what" branch (which is one of those 2900 branches). Off of the node at the end of the "what" branch, there is a "time" branch. And off that node, there's a "is" branch, and off of that node is a "it" branch. Finally, there's an answer at the "it" node.

Of course there are some wildcard branches as well, which adds to the complexity.

The tree thins out as you go down. For example, there are only 240 branches off the "What" node. There are far less things that make sense (to ALICE and in general) as a second word (after "What"), than the number of first words. Admittedly, in common English, there are far more than 240 - since nearly any noun would work in that context. But in common conversation, a surprisingly few choices come up after the word "what" - more than 240 I'm sure, but significantly less than the entire English vocabulary.

This is a really nice way to organize the parse tree. My frustration is with the re-writes. If the user says "Do you know what time it is?", standard AIML definitions will reduce that to "What time it is", eliminating the part that says "Do you know", and parse the remainder*. So far, so good - the parser will use recursion to continue its work.

But in some of the templates, an answer will be embedded with a recursion. It works well for ALICE chatbot, but not for my purposes. I am looking for a separation of powers - don't mix the parsing function with the knowledge base function.




*It'd be more appropriate, I think, to reduce to "What time is it", as opposed to the current "What time it is". AIML definitions could be written to do this, but I don't believe that they are in the standard AIML (AAA) definitions.

Saturday, June 27, 2009

Homemade Python Container Object


I wrote what I think is a nifty piece of code, and thought I'd share it, and get some feedback. The problem I was struggling with was that I wanted a flexible container object that other developers could use for storage and retrieval of objects, without pre-defining the structure.

In other words, I wanted it to be possible to do something like this:
if o.chatperson.hometown.country == "Mexico":
o.chatperson.native_language = "Spanish"
else:
o.chatperson.native_language = "English"


The code above examines the country of the hometown of the person that Amy Iris is chatting with, and if it's Mexico, then set their native language to Spanish, otherwise it sets it to English.

So far, not hard. The catch was that I wanted to be able to create and query the objects and properties on the fly. Using typical Python classes, the "if" statement above would raise an error, unless you have o defined, and o has a property of chatperson, and o.chatperson has a property of hometown, and o.chatperson.hometown has a property of country. I'd rather it not raise an error, but instead, create the hierarchy of sub-properties as needed to complete the request.

My goal was to create a general purpose container object that would create sub-containers on the fly, so that such a query wouldn't fail, and more importantly, it would allow me to set "deeply nested" properties, without having to pre-define the entire hierarchical structure.

So if I define this class properly, and set up an instance o, I should be able to execute the line:
o.chatperson.native_language = "English"

without having to define o.chatperson in advance.

I want this statement to automatically add a property called chatperson if one doesn't already exist, and make it a container to hold the native_language property.

By setting up a container class (I called it "Box"), and having "o" an instance of that class, I should be able to execute that line of code. Upon execution, "o" will create the container "chatperson", which will allow you to set the property called native_language. All auto-magically.

I called my class a "Box" class (looking for a shorter name than Container). The other features that I wanted were:

  • properties and sub-properties would automatically be set up (as instances of Box), if they were queried or needed for an assignment.
  • I wanted to track all changes to any instance of the class at the highest level. So setting o.chatperson.native_language to "English" will also log that change into a list called o._changelog.
  • I wanted to be able to set and get properties by either the dotted notation (in an unquoted object name in my source code), or by string. So the property that I mentioned above could be accessed in a number of ways:

o.chatperson.hometown.country
o.chatperson.hometown.get_dotted("country")
o.chatperson.get_dotted("hometown.country")
o.get_dotted("chatperson.hometown.country")
o.chatperson.get_dotted("hometown").country
o.get_dotted("chatperson.hometown").country
o.get_dotted("chatperson").hometown.country
o.get_dotted("chatperson").hometown.get_dotted("country")


Likewise, o.set_dotted could be used to "deep set" a property (and all necessary parent container properties would automatically be built as needed). And o.del_dotted could be used to delete using a string to navigate down the object heirarchy.

So here's what I came up with. Feel free to use it or critique it:


class Box:
"""
Containers for Properties. This class will allow you to create instances
that contain properties and sub-properties.

It has an auto-create feature, so that if you use dotted notation and
reference properties and sub-properties that do not yet exist,
they are created automatically.

And you can create dotted-notation properties using variable names.

All changes are tracked in a _changelog list.

Examples:


>>> p1=Box(name="Chris",gender="male")
>>> p1
{'gender': 'male', 'name': 'Chris'}
>>> p2=Box(name="Joe",hometown="Cincinnati")
>>> p2
{'hometown': 'Cincinnati', 'name': 'Joe'}
>>> PeopleBox=Box(people=[p1,p2])
>>> PeopleBox
{'people': [{'gender': 'male', 'name': 'Chris'}, {'hometown': 'Cincinnati', 'name': 'Joe'}]}
>>> p2.contact_info.phone.home="513-555-1111" #auto-create contact_info.phone
>>> p2
{'hometown': 'Cincinnati', 'name': 'Joe', 'contact_info': {'phone': {'home': '513-555-1111'}}}
>>> p1.family_members=[p2,] #support list types
>>> p1
{'gender': 'male', 'name': 'Chris', 'family_members': [{'hometown': 'Cincinnati', 'name': 'Joe', 'contact_info': {'phone': {'home': '513-555-1111'}}}]}
>>> p1.family_members[0].contact_info.phone.mobile #access p2 through p2
{}
>>> p2.contact_info.phone.mobile="513-555-2222"
>>> p2
{'hometown': 'Cincinnati', 'name': 'Joe', 'contact_info': {'phone': {'mobile': '513-555-2222', 'home': '513-555-1111'}}}
>>> p1.family_members[0].contact_info.phone.mobile #access p2 through p1
'513-555-2222'
>>> p2.contact_info.phone.mobile='513-555-3333'
>>> p1.family_members[0].contact_info.phone.mobile #changes to p2 affect p1
'513-555-3333'
>>> properties="job.salary"
>>> p1.set_dotted(properties,120000) #can create properties whose dotted names are in an object
>>> p1.job.salary
120000
>>> p2._changelog #can see list of changes
[['setattr', 'contact_info.phone.home'], ['setattr', 'contact_info.phone.mobile'], ['setattr', 'contact_info.phone.mobile']]
>>> p2._all() #can see entire structure
{'name': 'Joe', 'contact_info': {'_top': '<pointer>', 'phone': {'_top': '<pointer>', 'home': '513-555-1111', 'mobile': '513-555-3333', '_name': 'contact_info.phone'}, '_name': 'contact_info'}, '_top': '<pointer>', 'hometown': 'Cincinnati', '_name': '', '_changelog': [['setattr', 'contact_info.phone.home'], ['setattr', 'contact_info.phone.mobile'], ['setattr', 'contact_info.phone.mobile']]}
"""


def __init__(self, **kwargs):
"""
Save any dictionary of keywords passed, into the container
"""
self.__dict__ = kwargs
_top=self.__dict__.setdefault("_top",self)
if id(_top) == id(self):
self.__dict__["_changelog"]=[]
self.__dict__["_name"]=""


def set_dotted(self,name,value):
"""
set a value, by passing a dot-notation property name and value
"""
parts=name.split(".",1)
if self.__dict__.get(parts[0],None).__class__ != Box:
_top = self.__dict__.get("_top",self)
_name = self._get_full_name(parts[0])
self.__dict__[parts[0]]=Box(_top=_top, _name=_name)
if len(parts)==1:
self.__setattr__(name, value)
else:
self.__dict__[parts[0]].set_dotted(parts[1],value)

def del_dotted(self,name):
"""
delete a property, by passing a dot-notation property name
"""
parts=name.split(".",1)
if len(parts)==1:
self.__delattr__(name)
else:
self.__dict__[parts[0]].del_dotted(parts[1])

def get_dotted(self,name):
"""
get a property, by passing a dot-notation property name
"""
parts=name.split(".",1)
if len(parts)==1:
return self.__dict__[name]
else:
return self.__dict__[parts[0]].get_dotted(parts[1])

def __getattr__(self, name):
if name[:2]!="__" or name[-2:]!="__": # skip the magic python ones.
_top = self.__dict__.get("_top",self)
_name = self._get_full_name(name)
self.__dict__[name]=Box(_top=_top, _name=_name) #auto-create
return self.__dict__[name]
else:
raise AttributeError, name

def __setattr__(self, name, value):
self.__dict__[name]=value
_name = self._get_full_name(name)
self.__dict__["_top"].__dict__["_changelog"].append(["setattr",_name,value])

def __delattr__(self, name):
del self.__dict__[name]
_name = self._get_full_name(name)
self.__dict__["_top"].__dict__["_changelog"].append(["delattr",_name])

def _get_full_name(self, name):
"""
determine full dot-notation name of the property
"""
_name = [self.__dict__["_name"]]
if len(_name[0])==0:
_name=[]
_name.append(name)
_name=".".join(_name)
return _name

def __repr__(self):
"""
simple representation, no hidden values
"""
temp={}
for (k,v) in self.__dict__.items():
if k not in ["_name","_changelog","_top"]:
temp[k]=v
return repr(temp)

def _all(self):
"""
return all values including hidden ones
"""
temp={}
for (k,v) in self.__dict__.items():
if k == "_top":
temp[k]="<pointer>"
elif v.__class__ == Box:
temp[k] = v._all()
else:
temp[k] = v
return temp


Sunday, June 21, 2009

Want 330 Worthless Followers?



Four months ago, @lifewithryan told me about accidentally getting unwanted followers simply by tweeting the wrong thing. I set up a test account to see how that might work. I sent out 2 stupid tweets, and got 330 followers over the four months.





This would be a fun contest! See how many followers you can get by sending out just one tweet, over seven days. Rules: you have to set up a new account, and send just one tweet, and then hop over to twittercounter and do a search on your new account so that you are tracked. (to prove it's your new account, you should probably tweet the name of the new account from your usual account.)

I got 330 followers in 4 months with 2 tweets. How many can you get in 7 days with just 1 tweet on a new account?


By the way, in case you are new to this blog, I should tell you that Amy Iris is an extensible bot that you can place on your website, like I have at the top of this blog post.

Talk to my bot! Type into the text box, above.

Friday, June 19, 2009

How Amy Iris knows where Best Buy is

Amy Iris is an extensible bot that you can place on your website, like this:



Feel free to talk to her, by typing into the text box above. If you ask her questions, she'll answer you. The cool thing is that we have designed her for extensibility, so that the internet community can make her smarter. As an example, I built a small code snippet to interface with the Best Buy Remix API so that you can ask her questions about where Best Buy stores are. Here's a picture of a dialog that I had with Amy Iris earlier today:




As you can see, I have asked Amy Iris a couple of different ways to tell me where various Best Buy stores are. This example could be extended for all of the Best Buy API calls (such as product lookups).

Here's the code that's part of the Bot's logic. One little 14-line code snippet, submitted to Amy Iris' brain, and she now is that much smarter.



# example of Best Buy Store Locator
import amyiris, re
from google.appengine.api import urlfetch
if ("best buy" in str(textin)) and ((' in ' in str(textin)) or
('near' in str(textin))):
fields = ['name','distance','address']
url = "http://api.remix.bestbuy.com/v1/stores(area(%s,50))?show="
url += ",".join(fields) + "&apiKey=amysremixkeygoeshere"
r = "The nearest Best Buy store to %s is the %s store, "+
"which is %s miles away, at %s."

vals = [re.search(r'\d'*5,str(textin)).group(0),] #grab the zip code
page = urlfetch.fetch(url%vals[0]).content #look up results based on zipcode
for tag in fields: #parse the xml
vals.append(re.search('<'+tag+'>(.*?)</'+
tag+'>',page, re.DOTALL).group(1))
say(r%tuple(vals),confidence=21 )


A quick code review reveals the tricks (and limitations) of this conversational parser. I scan for the words "best buy", " in ", and "near", and rely on a 5-digit zip code in a regex search (that is, r'\d'*5). And if I find all these, then the snippet will retrieve the information from the Best Buy web site and present it to the user in conversation form.

Imagine - it's now available on the web, on twitter, on your cell phone. And this is just one small look-up. Imagine what happens as people begin contributing similar code snippets over the years! Amy Iris will be brilliant!

Thursday, June 18, 2009

Integrating Amy Iris into your Website

Amy Iris is a community built bot. We have the tools and platform now, so that within a few years, collectively we can build a very smart conversational bot through user contributions. Wikipedia taught us the power of pooling very small contributions of a lot of people. We're trying to use a lot of Wikipedia's principles: Focus on making it free and easy to use and contribute.

Now you can put this widget onto your website!
Test it for me. Ask Amy Iris a question.



As a developer, why would you want to a conversational bot in your project? Smart bots can provide your users and customers with a better experience using your website. Check out Paypal's virtual assistant or any of the bots on chatbot.org, and you can see that bots provide a way to automate the mundane, provide better customer service, and save companies money.

One tool that we've created is a simple Amy Iris widget (above) that you can drop onto your website. In future blog posts, I'll show you how you can make this widget smarter and "application specific". But for now I'll just share the tool.

Here's the widget, and the code necessary to drop it onto your website. Go ahead, try it out. Talk to her! And let me know if this widget is working - I'm still testing it. She should "open a chat window" by expanding her blue box, if you talk to her. Thanks!




<script type="text/javascript">
var oldHistLength = history.length;
setInterval ("checkHistory()",130);
function checkHistory() {
if (oldHistLength != history.length) {
var o=document.getElementById("outerdivv");
o.style.height ="242px";
}
}
</script>

<div><div id='outerdivv' style="width:540px;
height:74px; overflow:hidden;
position:relative; border: none; ">
<iframe id='inneriframe'
src='http://chat.amyiris.com/widget/'
frameBorder='0' style="position:absolute;
top:0px; left:0px; width:1280px;
height:1200px; border: 1px solid #000000;">
</iframe></div></div>


Stupid Bot Tricks

We're over here trying to advance the field of artificial intelligence for the betterment of the world. And one of the stupid little things we've built is connecting Twitter to a stupid conversational bot. See, we believe that in eight short years, you'll be able to converse with a bot in 140 character bursts, and not be able to tell it's not human. But ya gotta start small. Baby steps.

So in the meantime, we offer this stupid bot.

All we ask is:
  1. Follow @amyiris
  2. Tweet "talk to @amyiris" (then she'll follow you)
  3. dm amyiris, and a bot will converse with you