Decision Trees For Optimizing Pattern - Matching Algorithms in Production Systems

1. INTR:lDUCI'ION

(C B a J are negative conditions in R2) :

R1 { (A(B C X)) (D x) (x F y) (E F y)} -+ ···

R2 { (A(B C x)) I (D x) (x F y) (B F y)-(C B oJ} -+ ···

R3 { (A ( x F y)) (H x) (x F z)} -+

R4 { (A(B Fa ) ) (B F y) (z C B)} -+

R5 { (A(x B)) (x C B)}-+

Only 11 among the 17 conditions of this example a re distinct. In order to find which conditions match a given datum, it is sufficient to discriminate between these 11 conditions, since by assumption WM does not contain unnecessary data. The following decision tree achieves that discrimination

Pattern-matching is a fundamental technique in AI, but it remains a very costly operation and the main factor in the computational inefficiency of many systems, particularily Production Systems (PSs) to which the following discussion is restricted, (see [1,8) for overviews and main definitions of PSs). According to experimental data (2,5), the interpre­ ter of some PSs spends 90 to 98 \ of its time in the matching task.

A straight-forward pattern-matcher tests at each cycle the conditions of each production rule indivi­ dually against all the data of the working memo~ (WM). Taking advantage of 1) the matchings found in the previous interpreter cycle, and 2) the occurence of identical or similar condition eleMents in more than one production rule, improved algorithms were designed using either a partitionning and filtering technique (5,7), or more successfully a matching network technique (2,4). But even this last approach suffers from some inefficiencies and leaves room for substantial improvements mainly because 1) the resul­ ting algorithm cannot avoid redundant computations (a data element may have more than one path in the network), and 2) it relies on a network arbitrarily designed .

2. COMPILING PRJDUCI'ION RULES CONDITIOOS

The pattern-matching method herein developed compi­ les the set of production-rules conditions into an optimized decision tree. The nodes of this tree are tests (i . e., evaluation of characteristic features) t o be performed on the data modified in WM at each cycle, the leaves are pointers to stacks containing all data actually matching a given condition . The me­ thod applies to any PS of the OPS type (3). We first r es tri ct segment variables (representing lis t frag­ ments of undefined length) to tails of sublists, and ass ume that any datum in the WM matches necessa­ rily some condition of the system.

Let us consider as an example the following 5 produc­ tion rules (only rules antecedents are given ; x,y,z, are variables ; ~is a segment variable ; (D x) and At the beginning of each cy~le, the interpreter traverses the tree with each modified datum in WM (entering and leaving data), computing at each tree node a feature and taking the branch corresponding to the value found. If for example datum d=(A(B C(U V vi))) is crossing the tree, the root node <!hi) computes the length of d at the highest ievel, and selects the branch labelled by the number found, namely 2. The next node (<1>) extracts the 1st subelement of d, finds atom 'A' and takes the left branCh. The fOllowing node (<2.2>) extracts the 2nd element of the 2nd subelement and takes the branch labeled bythe result 'C'. This will lead to a leaf containing the only condition matching d.

Note that some branches are labelled "else" : these are to be selected when the value computed by the node does not correspond to any of its other branch labels. Leaves which contain more than one conditi on correspond to overlapping cases : for example, any datum matching (B F x) also matches (x F y).

Two kinds of features are considered : those which compute the length of a list or a sublist, and those which extract an atom from some specified positd:an. The 1st step in compiling a set of production-rules conditions into a decision tree consists in enumera­ ting all features of these 2 types relevant for the data at hand. An identification table which plots these features values v.s. the set of conditions, and from which non discriminating features are dele· t ed , is then constructed.

For the previous example, the table is as rollows (with 1 - 1 and 1 ~ 1 denoting undefined and variable feature values, respectively)

The algorithm which generates the decision tree starts by selecting among the features which are de­ fined everywhere an "efficient" feature f as the root of the tree. From this root, a branch is drawn for each of the possible values of f including an "else" branch if f has~ in its ra.~. For each branch the algorithm associates a subtable of the identification table containing the subset of conditions correspon­ ding to the label of the branch and the features dis­ criminating these conditions. It then proceeds re~ cursi~ely at each branch using the associated sub­ table . The recursion stops if sdme subtable has an empty set of features : the corresponding branch ends with a leaf containing the subtable conditions.

It is easy to show that 1) in any path from the root to a leaf of the resulting tree, a feature will not be evaluated more than once ; and 2) any datum matching some condition element has one and only one path in this tree, such a path ends with a leaf con­ taining all the matched conditions. Thus the deci­ sion tree achieves a complete discrimination with no redundant testing. Moreover the efficiency of a de­ cision tree pattern-matcher may be optimized. Tree optimization is a very well knCMn problem. The pre­ vious algorithm gives only an approximate solution, whose goodness depends on the rule used for feature selection. As an example of such a rule, one may chose the feature with minimum number of variable values ( 4> ) in its ra.~, and break ties by taking the feature with the range of maximal cardiuality. If the evaluation cost of each feature is known, an c -admissible heuristic search is a feasible ap­ proach : for any given c~ 0 it wi 11 generate an c -optimal decision tree. This approach can even handle features whose evaluation costs depend on what has been previously evaluated.

Notice that the 2 classes of features considered here for qesigning a decision tree may be extended to other features (e.g. maximal depth or flattened length of a list). This will improve the tree effi­ ciency in some cases, but will always increase the compiling time.

For most systems, the assumption that any datum in WM necessarily matches some condition is not a very restrictive hypothesis, since a new datum is not an external input but rather has been geQerated by some rule consequent. One may ·check out once for all the data generated by each rule,together with the data in the initial state of the W/4. In systems where this is not possible, the decision tree method is still appli­ cable with a slight modification:verification nodes must be added just above some leaves for resjecting or confirming a candidate datum. A tree with verifi­ cation nodes can also be used to handle external input data.

Providing another s .l ight extension, the method de­ veloped here remains applicable to systems where segment variables are only restricted to be at most one per sublist : features extracting atoms from su­ blist in the reverse order must be considered. Thus, for example, the condition (Ap B)) is characterized by: <1> = , and<2.-1 ,.=B.

3. PRODOCTIQN RULES INSTANTIATION

The decision tree enables us to identify at each cycle the conditions matching entering or laaving data in WM. A stack is associated with each condi­ tion. An entering/leaving datum is added to/deleted from the stacks of its matching conditions. Modified stacks may imply changes in the validity of the pro­ duction rules containing the corresponding conditions. If the entire conflict set is required at each cycle, production-rule instantiation is mainly the Cartesian product of the concerned stacks with consistent va­ riable bindings. Computation may be reduced by look­ ing for groups of conditions common to many rules. Some refinements can be made to the basic method developed in (2].

More significant improvements are achieved in the rules instantiation task if, instead of generating the complete conflict set, one anticipates on the conflict resolution. It is fairly easy to check if some desired rule Ri is valid and to generate its instantiation which uses the most recent data (top of Ri 1 s conditions stacks).

4 · a:>NCLUS I ON

In a system containing I PM I production rules with JCI distinct conditions, a straightforward pattern­ matcher has a time complexity of 0( ~M lx ~M I>· Both, the filtering technique (5] and the network matching technique (2] have a worst case complexity linear in I PH I or in I C I' and independant of I WM I· The de­ cision tree approach inherits this independancy. If each node in the decision tree is implemented as a search tree, the number of operations performed to match a datum is proportional to the sum, over the features measured, of the logarithm of the number of their branches. Assuming that the decision tree has a number of leaves linear in I cl, in a favorable case one or few features discriminate completely all the conditions, and the complexity is of O(Log 1cp. Implementing each node as a hash table can even improve the best performance to a constant complexity, but this will not ameliorate the worst case in which the decision tree would have only binary features , In such a tree the averaje path length (over all binary trees) is of 0 ( lc 1/2).

In summary, the method proposed here leads to a completely discriminating pattern-matcher which exempts from any further matching, as needed by the filtering technique (5,7). Because of its tree structure, this matching algorithm avoids the redun­ dant computations encountP.red by the network matching method (2), and has a sub-linear time complexity. Taking into account the tree optimiza­ tion possibilities, the expected performances of the method developed seems more promising.

Aa<NOWLEDGEMENTS

The author wishes to thank R.P. Sobek for construc­ tive discussions, and implementation and testing of these ideas. Dr. M. Georgeff's referee comments were helpful and greatly appreciated.