Beyond Façade: Pattern Matching for Natural Language Applications
March 15, 2011 Page 1 of 5
[Is the age of natural speech here? Telltale's Bruce Wilcox delves into techniques for natural language processing and contrasts AIML and Façade's approach against his own award-winning ChatScript, showing a path forward for word-based game technology.]
Understanding open-ended simple natural language (NL) requires huge amounts of knowledge and a variety of reasoning skills. And then there's dealing with bad spelling, bad grammar, and terse context-dependent input. No wonder games severely limit their use of NL.
But speech is a coming interface. It solves input issues on small devices as well as being more appropriate than a mouse or controller for some games. Those old text adventure games were a lot of fun even with extremely limited vocabulary and parsers. Google now provides free servers translating speech to text for web pages, so the focus will shift to using that text.
Scribblenauts accepts text nouns and adjectives in its latest puzzle game and Telltale Games has a planned product mixing nouns and verbs. In other words, full natural language games are only a matter of time. Bot Colony is currently attempting this and Façade already did so (sort of) five years ago.
In this paper I will look at successive refinements to NLP (natural language processing) as they apply to games, reviewing AIML, Façade, and ChatScript. I will cover how the state of the art has evolved from matching patterns of words to matching patterns of meaning.
This paper will make the following general points:
- Script syntax and semantics have a big impact on ease of content authoring.
- Matching sets of words instead of single words approximates matching meaning.
- The absence of words is as important as the presence.
- Wildcard matching (in place of parsing) should be reined in to reduce false positives.
Unrestricted NL input has existed for decades – chatbots like Eliza and A.L.I.C.E. (left). But the output is barely useful. It takes a lot of data to make any plausible approximation to natural language understanding. This places a premium on making it easy to author content.
A.L.I.C.E is written in AIML. AIML is a miserable system for authoring. As a programmer, I think of AIML as recursive self-modifying code at the assembly level of language processing -- in other words, a content creation and maintenance nightmare. And its pattern matching is feeble.
AIML is simple. You describe a category (what others call a rule) as a pattern of words and wildcards and what to do when the rule matches the current input. AIML's syntax is XML based, with a pattern (input) clause and a template (output) clause, like the rule below:
<pattern> I NEED HELP * </pattern>
<template>Can you ask for help in the form of a question?</template>
The pattern must cover the entire input of case-insensitive words; punctuation discarded. The wildcard * binds to any non-zero number of words, creating patterns matching many inputs.
Problems with authoring arise instantly. Matching the sequence I love you in all sentences requires four rules, and still can't match I really love you.
<pattern> I LOVE YOU </pattern>
<pattern> * I LOVE YOU </pattern>
<pattern> I LOVE YOU * </pattern>
<pattern> * I LOVE YOU * </pattern>
If only AIML wildcards matched 0 or more words, then a single pattern would do. You can make the above patterns match I really love you by adding in a wildcard between I and you, but then it would also accept sentences like I will never love you. Wildcards in AIML are inadequate.
The power of AIML lies in recursive substitution. It can submit input to itself using the <srai> tag and put the contents of * into the output using <star/>. The rules for mapping Can you please tell me what LINUX is right now to the question What is LINUX? might look like this:
<pattern> * RIGHT NOW <\pattern>
=> CAN YOU PLEASE TELL ME WHAT LINUX IS and then
<pattern> CAN YOU PLEASE * <\pattern>
<template> <srai> Please <star/></srai></template>
=> PLEASE TELL ME WHAT LINUX IS and then
<pattern> PLEASE TELL ME WHAT * <\pattern>
<template> <srai> TELL ME WHAT <star/></srai></template>
=> TELL ME WHAT LINUX IS and then
<pattern> TELL ME WHAT * IS <\pattern>
<template> <srai> WHAT IS <star/></srai></template>
=> WHAT IS LINUX and finally
<pattern> WHAT IS LINUX <\pattern>
<template> LINUX is an operating system. </template>
=> LINUX is an operating system.
AIML does everything this way. A.L.I.C.E. has 1300 rules merely to remove what it considers useless adverbs like really and accordingly in sentences.
AIML allows you to augment patterns in two ways. One is with a topic you can set on the output side and test on the pattern side. This prioritizes rules inside a matching topic over rules outside of it. So if the topic became set to "tasty breakfast food" then this rule would get priority.
<topic name="* breakfast *">
<pattern>I like fish</pattern>
<template> Do you like sushi? </template>
The problem with this is that you have to dedicate rules outside of this topic to set the topic name for you to match. How many rules you will need and how to craft them will be significant issues.
The other pattern augmentation mechanism is the that clause, which adds a pattern match on the last output sentence given by the system. Rules that match a that clause have priority over rules that don't. You can use that to script continuations based on expected reactions to your output.
<that> Do * sushi </that>
<template>I hate sushi</template>
This rule responds to a simple yes only if the last output was a "Do" question that ends in sushi.
With pattern augmentation, you can write some obscurely clever code. But obscure code is generally self-punishing and few people can write or read such code.
Implementing AIML is easy. All the data is precompiled into a tree structure and input is matched in a specific order against nodes of the tree, effectively walking a decision tree. The first matching node then executes its template, which may start up a new match or do something else.
AIML's basic mechanic is also its weakness. Recursively self-modifying input creates problems.
First, you can't glance at code, you have to read it and think about it. XML is not reader friendly. It's wordy, which is fine for a machine but hard on a human. Just consider the simple that rule about sushi above. You can't just look at it and know what it does. You have to think about it.
Second, you can't see a rule and know if it will match the input. You have to know all the prior transformations.
Because of this, writing and debugging become hard, and maintenance impossible.
AIML is clever and simple, and a good start for beginners writing simple bots. But after 15 years, A.L.I.C.E has a meager 120K rules. AIML depends on self-modifying the input, so if you don't know all the transformations available, you can't competently write new rules. And with AIML's simple wildcard, it's easy to get false positives (matches you don't want) and hard to write more discriminating patterns.
Still, A.L.I.C.E. is a top chatbot, coming in 2nd in the 2010 Loebner Competition.
Page 1 of 5