Windows 0.3

In the year 2001, there is no HAL 9000. Instead, there are a growing number of software packages that attempt to do some part of what Arthur Clarke / Stanley Kubrick envisioned in the book and film of the same name, most of which go by the label "chatter bot", "virtual representative", "virtual person", "smart bot", or some similar variant. Here I'll be calling them all "bot software", disregarding the fact that "bot" usually applies to a broader range of software than just conversational programs.

Many people claim that this bot software has real business applications in customer service, distance learning, and so on. A number of companies have been built in hopes of capturing a piece of a still infant market for bot software.

Most of today's bot software is proprietary, meaning that its source code is closed, its methods layered over with some attempts at legal protection (patents, etc.), and its use restricted to those who agree to pay license fees that are usually very large, and that are usually followed up by hefty professional services fees.

Only a few bot software packages are free or open source, and only one has had the participation of over 300 developers around the world. That one is A.L.I.C.E., today known as the Alicebot engine and AIML technologies. Alicebot/AIML is released under the GNU General Public License, the same license used by Linux, and the truest of "open source" licenses in that it construes a particular meaning of "free" that has to do not with price, but with access and liberty. (See www.fsf.org.)

Alicebot/AIML is to [insert proprietary bot software] as Linux 0.01 would have been to Windows 0.3. Of course, when Linux 0.01 was released (1991), Windows 3.0 was already out, introducing such marvels as the use of more than 640Kb of RAM; and of course, no one but an inner circle at Microsoft ever saw such a thing as "Windows 0.3" (if there was such a thing).

But there are two points to this analogy:

1. Alicebot/AIML is already more advanced than any commercial bot software.
2. Commercial bot software already faces the same uphill fight against the market forces of free/open source software that Microsoft did not begin to face seriously until its own software had advanced significantly beyond an embryonic stage (say, around 1999 when Red Hat went public and Windows 2000 was released).

Add to that that most commercial attempts to sell proprietary bot software are struggling to stay alive, and that the list of Alicebot/AIML companies is growing. Below I'll go into some detail to explain why you don't need--and shouldn't choose--proprietary bot software if you are planning to begin using bot software in your company. This argument is divided into three parts:

• The Historical Case
• The Technology Case
• The Business Case

Feel free to skip around.

The Historical Case

A bit of a history lesson is in order. Some bot software companies try to place themselves in an historical timeline that usually starts with Joseph Weizenbaum's ELIZA. They provide a story something along these lines: ELIZA was a primitive attempt at conversational AI that sparked imagination, but mostly relied upon a few simple "tricks"--and since then, some geniuses have been locked away in an unmarked building working up a true revolution in 'artificial intelligence', which just so happens to have landed on the doorstep of [company name].

The idea is supposed to be that ELIZA whetted the world's appetite for talking computers, but that the approach used wasn't serious enough, and that it took a few more decades for "real" NLP (natural language processing) to fill in the missing pieces and make today's bots able to carry on remarkable conversations, sell products to customers, remember web site visitors, teach about subjects, give financial advice, and so on.

But the fact is that the development of what most people call "real" NLP and the development of bots have mostly proceeded along different lines. "Real" NLP as it's understood in the academic world goes deep into problems of linguistics that are still poorly understood. Most of the work that has been done in conventional NLP has not translated into something that can be used for making a machine carry on a better conversation. In fact, from the point of view of academia, the software that's advertised as conversational bot software mostly relies on "outdated" ideas that were discredited almost as soon as they were introduced.

Richard Wallace is the only (former) academic who makes a serious case for the legitimacy of the approach used in ELIZA, and has also demonstrated the possibility for expanding on that approach to produce results that match what people are looking for in bot technologies. Commercial companies using closed software generally use talk of patents and advanced secretive technologies as marketing tools to mask the truth--that they too are relying on an approach that is also heavily based on the original ideas of ELIZA.

In reality, it's the conventional NLP approach that is stuck. Any professional linguist will tell you that for as many advances as the study of language has made, it has encountered as many profound setbacks. Most conventional NLP approaches rely upon fitting actual speech to a meta-model of "meaning" and communication. Briefly, for instance:

"I took my kid to school yesterday."

might be illustrated as:

The sentence is broken down into components based on their "syntactic" function. This syntactic analysis is meant to serve as a framework for understanding the "semantics" (meaning) of the sentence. A machine needs to know things like:

• "took" is the simple past tense form of "to take"
• "I" refers to the speaker of the sentence
• "my" refers to something that belongs to the speaker of the sentence
• "kid" can mean many things, among which is a "child"
• A child is a young person
• "my kid" probably indicates that the speaker is the "parent" of the child
• "parent" can mean many things, among which is a person who is somehow responsible for another person, possibly including that other person's upbringing, birth, etc.
• "school" is a place where people learn
• "to take" someone "to school" means to arrange for the transportation of that someone to the school and to accompany them (i.e., "to take" alone is ambiguous)

And so on. There are many theoretical approaches to filling out the details in this fashion. Many approaches take a starting point like this, and rely, at some level, on several important resources:

• a "lexicon" of words that describes their different forms and possible positions in a "sentence"
• a "corpus" of semantic information about different combinations of lexical items and the relationships of those combinations to other combinations
• an engine that can apply a lexicon to a sentence and identify all possible interpretations of the sentence's syntactic structure
• an engine that can apply a semantic corpus to a series of syntactic & morphological ("word shape") parses and identify the most likely interpretation of the semantic intent of that sentence

And in fact the notion of what constitutes a "sentence" is also poorly understood, believe it or not, leading some people to speak of "utterances" rather than sentences.

It's also clear that even a good analysis of a sentence in isolation is relatively useless, leading to the need for "pragmatics", in which the analysis attempts to locate the meaning of an utterance within its "layers of context". The notion of "context" is also poorly understood, and at its best in computer NLP is treated as a sort of giant static network of "meanings", often called an "ontology".

There are a huge number of theories of NLP that follow an approach that looks something like this. None of these approaches have a complete set of tools that can handle real text generated by humans, to consistently produce an accurate analysis with which most people would agree.

There are also approaches that try to minimize the number of a priori rules, and rely instead on "learning" techniques based on statistical analyses of large bodies of text. Neural networks, fuzzy logic, genetic algorithms and other approaches are essentially statistically-oriented techniques that try to remove some of the manual labor from statistical analysis by introducing a "black box" that iteratively builds rules, often hidden from human users, based on feedback about the analysis from human controllers and/or "heuristics" that serve as non-absolute guides to analysis.

Aside from the fact that no approach fully satisfies its own stated aims within whatever constraints on language and goals for analysis are set, almost all approaches suffer from an inability to "explain" the workings of more than a handful of human languages with the same set of rules. And virtually no approach can do more than acknowledge that even a single given language, say English, is used in countless "standard" ways and evolves continuously as it is used.

One only needs to begin a web search on "natural language processing" to understand that the amount of research into this topic is immense, and that no approach has a legitimate claim on being the best. The history of linguistics is rife with fierce battles among academics whose entire careers have been staked on establishing the authority of one approach over others--none has met with success (see Randy Allen Harris's The Linguistics Wars for a great read on this topic).

Suffice it to say that the academic debate and research struggle forges ahead vigorously, but that none of its output has proven commercially viable.

Perhaps the most spectacular failure has been the CYC project, initiated by Doug Lenat in 1984 and beneficiary of millions of dollars of government research money and private and institutional investment. CYC (now housed under a company called Cycorp), was and is a project with the aim of building a giant knowledge base full of "common sense", with the idea that this would someday enable machine understanding of texts. Lenat has been telling journalists (and presumably his investors) for years that CYC is mere months away from being able to understand simple texts like TIME magazine. So far quite a lot of money has been spent, and the giant knowledge base continues to grow, but despite its intricacy (some might say beauty), its commercial use is still beyond reach, and its theoretical base lags behind the academic research front, itself still light-years away from success.

Know this: the commercial bot companies may borrow bits and pieces from conventional NLP, but by and large they are every bit as ELIZA as ELIZA. As ELIZA relies on pattern-matching and simple string manipulation, so too do all "proprietary" offerings at their core.

The Technology Case

Given all that, you might still reasonably assume that behind locked doors some innovation has taken place, funded by visionary investors and executed by brilliant developers, that justifies offering a proprietary bot technology at license prices in the hundreds of thousands or millions of dollars (US).

You might reasonably assume that, but you would be wrong.

A.L.I.C.E. has been around since 1995, before most of the current crop of commercial bot companies even began. Richard Wallace is very forthright in describing his invention of A.L.I.C.E. as based directly on insights learned from ELIZA and its various successors. As the original documentation for A.L.I.C.E. shows, A.L.I.C.E. was an evolutionary step that modularized the simple string manipulation and memory techniques used by ELIZA and allowed the rule base to be easily extended to perform one of a limited set of operations on a client input, producing an output that incorporated information (1) already in the bot's knowledge base, (2) "learned" from the client, and (3) derived from context.

Nothing was ever hidden in the A.L.I.C.E. approach, and given the timeline and the fact that A.L.I.C.E. was always under the GNU GPL, one might make a reasonable case that the bulk of the approaches used by proprietary bot technologies probably violate copyright. Fortunately for vendors of proprietary bot technologies, the aim of Wallace's use of the GPL was never to lay claim to personal proprietorship of the approaches used in A.L.I.C.E., but rather to encourage innovation by opening up the project to as many participants as possible.

Based purely on interactions with online demonstrations (and customer implementations) of bots produced by proprietary vendors, one may very reasonably challenge any claim of technological superiority of proprietary technologies over Alicebot/AIML (or any other free/open source bot technology).

You don't have to believe me, of course--try it for yourself. Here are some things to watch for:

• Can you "trip up" the bot using sentences that reveal its primary reliance on keywords?

  For example, try asking a bot a question that uses two or more important words, like: "What is the difference between natural language processing and professional cosmetology?" These are the answers I got from several bots online:

  answer	Bot Name	Vendor	Company Using It	URL
  "I'm not sure what you are asking me. Part of my brain is a proprietary natural language processing engine. I hope that helps answer your question."	Julia	Virtual Personalities, Inc.	Virtual Personalities, Inc.	vperson.com
  "Natural Language refers to a computer's ability to understand the things a human says, without the human having to talk using special codes like programming languages."	Nicole	NativeMinds, Inc.	NativeMinds, Inc.	nativeminds.com
  "I am sorry, I did not understand your question. Below are some topics that people often ask about. You may also try rephrasing your question."	Hank	NativeMinds, Inc.	The Coca-Cola Company	www.cocacola.com
  "'Natural language' is what you speak and hear all day."	Karl	Kiwilogic.com AG	Kiwilogic.com AG	www.kiwilogic.com
  "I'm not quite sure what you mean."	Liam	Kiwilogic.com AG	Loewe AG	loewe.de
  "It is just computer software trying to understand and generate human language."	Luci	Artificial Life, Inc.	Artificial Life, Inc.	www.artificial- life.com
  "I do not have an answer for you. But in the meantime, let's move on. And let me ask you, which type of financial goal are you considering the most: retirement; estate planning; college; or other?"	Janet	Artificial Life, Inc.	Pioneer Investments	pioneerfunds.com

  A.L.I.C.E. herself answers that question, "Aren't they the same?"

  What you should notice about all of the responses from the proprietary bots is that they either (a) pick out one key word/phrase ("natural language processing") and provide a quick description of NLP, ignoring the rest, or (b) flat-out admit that they don't know the answer, and try to steer the conversation to topics they do know. In no case do they even acknowledge that you've asked about the difference between two things, although that certainly doesn't need a grammatical parser to detect.

  The only difference in A.L.I.C.E.'s response is that her knowledge base contains the pattern "WHAT IS THE DIFFERENCE BETWEEN *" and the witty come-back "Aren't they the same?"--basically a gamble on either amusing the client or occasionally hitting the right answer when someone tries to trick the bot by asking what the difference is between two things that are, in fact, the same.

• How well does the bot really remember the thread of your conversation? Many bots will ask your name, and incorporate this into future responses. Some bots also attempt to identify the "topic" of conversation, and a few will be able to tell you what the topic is when you ask about it (although even this is rare).

  Just remember that asking your name, or any other piece of information, and storing it in a variable for later use doesn't constitute "understanding" what's going on in any sophisticated sense, nor is it the basis for "reasoning" in any sense of the word. Many companies try to pass off tricks like this as a kind of "memory" or "knowledge of context".

• How well does the bot really understand "anaphora"? Anaphora are references to previously-named things. In English, pronouns like "he", "she", "it", and so on usually refer to previously named people or things. Some bot companies will pretend that their software can really identify the target of an anaphoric reference. But such claims can be proven false, and can easily be shown to be keyword-based as well. You need only pursue a dialog a few turns to show that a bot really has no clue what you're talking about, beyond a rudimentary index of the "current topic".

You can try all the tricks you want; some of them will get you witty answers, a few will even be answered "correctly" (until you twist the trick a bit more), and most will just get you a plain stupid answer. It's probably also worth pointing out that any of the bot companies that are still functioning and happen to come across this article may improve their response to the example question above.

The point is that the Alicebot/AIML technology set is no more or less sophisticated in its ability to handle these kinds of tricks than any proprietary technology. That's because answering "trick questions", depending on whom you ask, (a) depends on solving deep NLP problems that are still plaguing us, (b) just depends on a good "botmaster" who reviews conversation logs and continually improves the knowledge base so that the bot answers the question better the second time around, or (c) is plain impossible.

The A.L.I.C.E. theory is that (b) is the best answer for now, and that this is perfectly adequate for most realistic uses of bots. That might sound like a cop-out, but it's honest. It's more honest than any claims of sophisticated "reasoning" or "discourse management" capabilities that proprietary vendors might make. As Wallace says, trick questions (and there are entire corpuses of these in any standard linguistics text), "reveal the ambiguity of language and the limits of an ALICE-style approach (though not these particular examples, of course, ALICE already knows about them)."

So proprietary vendors tend to shy away from emphasizing their claims of NLP superiority any more than they feel they must in justifying the "sophistication" (and consequent high price) of their technology. Any company that decides to invest in bot technology and goes through a process of technical due diligence in comparing bot companies to one another will quickly get into a discussion of more run-of-the-mill issues that apply to implementing any technology in a web environment (or otherwise high-use situation): things like scalability, integration capabilities, and the development infrastructure behind the software itself.

Scalability: as of this writing, the Alicebot/AIML technology set as a whole hasn't undergone any massive testing for load handling, fault tolerance, and so on. But the "Graphmaster", which lies at the heart of the Alicebot engine, does have a mathematically demonstrable scaling factor. Wallace explains it as follows:

The Graphmaster is a directed tree graph, with a root node, and pathways from the root to the terminal nodes. The terminal nodes contain maps to the <template>, <filename> and potentially other properties of the category. Each terminal node is one category, and the number of terminal nodes equals the number of categories.

The basic efficiency of the Graphmaster comes from the observation that, given a sample of sentences of natural language, the branching factor for the first word is large (around 2000 in our case), but the average branching factor for subsequent words of a sentence decreases rapidly (e.g. 2000,3,2,1,1,1,...) So the tree for natural language sentences is shallow, but wide. This observation does not depend on whether the basic tokens are words, or letters (I've implemented both types of Graphmasters), or whether the input set of sentences is a corpus of New York Times text, the Bible, a collection of e-mail bodies, or the Pattern set of A.L.I.C.E.'s brain.

We have actually plotted a collection of Graphmasters for the ALICE brain. The pictures are quite beautiful. See http://alicebot.org/documentation/gallery.

If the number of categories is N and the average pattern length is M, the memory required to store them in an array (as in program B) is O(MN). But the Graphmaster compresses common prefixes together, so requires much less than MN.

[About "Big O" notation: In general O(f(n)) means there exists constants k and c such that for every input problem larger than cn, the computation takes less than k*f(n) steps. O(1) means that the time is constant and does not depend on n.]

Consider the case of an "atomic" pattern (no wildcards). The time to match an input to that pattern depends only on the path length from the root to the corresponding terminal node. This takes, on average, M steps, irrespective of the number N of categories. This is why we say that matching in the Graphmaster is O(1). At least one of our competitors advertises a matching algorithm that is at best O(log N). [As an exercise--prove that the time to match even with wildcards does not depend on N.]

The Graphmaster is implemented elegantly with the Java Collections Library. Essentially each node is a map, called a Nodemapper, which takes a given node, the next word in a sentence, and returns the next node down the path, or null. In practical terms, the recognition time is around 10ms, no matter how many categories are loaded, up to the limit of memory. The response time can be slower because of chains and