The Technology Case
(sec. 3 of 4)

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