The Anatomy of A. L. I. C. E

16.Graphmaster

When n is a node in the graph and w is a word, G(n, w) is either undefined, or returns the value of a successor node m in the graph. The graph is a rooted, directed tree. The set S_n = {w :  m | G(n, w) = m} is the set of words forming the branches from the node n. If r is the root, S_r is a collection of all the first words in the set of patterns.

In this way, the Graphmaster accumulates common pattern prefixes along pathways from the root, achieving considerable compression compared to a linear array of all the patterns.

A convenient metaphor for the Graphmaster is the file system. The file pathname is like the AIML pattern path. The templates are like text files at the end of the path. To put it more simply, patterns are folders, templates are files.

17.Matching

We can define the matching process formally as:

Match(n, h) :- if h > k return true; else if  m = G(n, _) and j in [h+1..k+1] | Match(m, j), return true; else if  m = G(n, w_j) and Match(m, h+1) return true; else if Exists m = G(n, *) and  j in [h+1..k+1] | Match(m, j), return true; else return false; The first case defines the boundary condition: 0. If there are no more words in the input, the match was successful.

The heart of the algorithm consists of three cases:

1. Does the node contain the key “_”? If so, search the subgraph rooted at the child node linked by “_.” Try all remaining suffixes of the input to see if one matches. If no match was found, ask

2. Does the node contain the key w_h, the jth word in the input sentence? If so, search the subgraph linked by w_h, using the tail of the input w_h+1,…,w_k

. If no match was found, ask

3. Does the node contain the key “*”? If so, search the subgraph rooted at the child node linked by “*.” Try all remaining suffixes of the input to see if one matches. If no match was found, return false.

The actual matching program needs to be a little bit more complex. It must not only return true or false, but also the template from the matching terminal node. An efficiency gain may be obtained by storing the tree height (maximum number of links to a terminal node) at each node. The tree height may be compared with the number of remaining words, pruning branches of the search when exploring suffixes following

“*” or “_” nodes.

Note that:

0. At every node, the “_” wildcard has highest priority, an atomic word second priority, and the “*” wildcard has the lowest priority.

1. The patterns need not be ordered alphabetically. They are partially ordered so that “_” comes before any word, and “*” comes after any word.

2. The matching is word-by-word, not category-by-category.

3. The algorithm combines the input pattern, the pattern and pattern into a single sentence or path, such as: “PATTERN THAT TOPIC.” The Graphmaster treats the symbols and just like ordinary words. The patterns PATTERN, THAT and TOPIC may all contain multiple wildcards.

4. The matching algorithm is a highly restricted form of depth-first search, also known as backtracking.

5. For pedagogical purposes, one can explain the algorithm by removing the wildcards and considering match steps (2) only. The wildcards may be introduced one at a time, first “*” and then “_.” It is also simpler to explain the algorithm first using input patterns only, and then subsequently develop the explanation of the path including and .

18.Targeting

The second style of AIML content creation is based on a backward-looking log file analysis. In its simplest form, the botmaster may read the logged conversations and take note of “incorrect replies” in the dialogue, and then write new categories for those queries. More generally, every input that matches a pattern with a wildcard is an opportunity to create a new, more specific pattern and its associated template.

The backward looking approach is justified by Zipf’s Law, basically because if one client utters a sentence, there is a nonzero probability that another client will utter the same thing later. Applying Zipf’s law to the log file, we identify the most commonly uttered sentences first.

Targeting is a special case of the backward-looking strategy. The perfect targeting algorithm has not yet been developed. Meanwhile, we rely on heuristics to select targets from the activated categories.

The ALICE brain, at the time of this writing, contains about 41,000 categories. In any given run of the server however, typically only a few thousand of those categories are activated. Potentially every activated category with at least one wildcard in the input pattern, that pattern, or topic pattern, is a source of targets. If more than one input activated some category, then each of those inputs potentially forms a new target. The first step in targeting is to save all the activated categories and the inputs that activated them.

If the matched pattern ends with a wild card, the suggested new pattern is generated as follows. Suppose the pattern consists of [w_1,w_2,..w_h,*], a sequence of h words followed by a wildcard. Let the input be [w_1, w_2,...,w_k] where k > h. The new pattern [w_1,...,w_h,w_h+1,*] is formed by extending the original pattern by one word from the input. If the input is the same length as the original pattern, i.e. k+1=h, then the synthesized pattern [w₁,...,w_k] contains no wildcard.

The targeting software may include a GUI for

browsing the targets. The program displays the original matched category, the matching input data, a proposed new pattern, and a text area to input the new template. The botmaster may choose to delete, skip or complete the target category.