Validating Concepts from Automated Acquisition Systems

I. Introduction

The main problem with the use of production rules to represent knowledge is the determination of the relevant features of the domain. Production system knowledge consists or rules of the form:

IF features [p f2 , fi are present in a situation THEN opply action A

The features f i must be provided to the system for recogni tion of a situation as relevant for the firing of rules, However, an enumeration of all relevant features is a very difficult task. Therefore, it is desirable .and sometimes necessary to use inductive methods for establishing relevant features of the domain.

Chess is an excellent domain for experiments in concept acquisition. Chess players use a large vocabulary of domain concepts which is accessible in chess books and by psychological experiments. A grandmaster has a large library of chunks in LTM that is used to encode a chess position and in this way, reduces the uncertainty. It has been estimated that some ten thousands of chunks are necessary to explain the performance of master players [6].

A convenient method for measuring the amount of information reduction by chunking is the use of the binary question experiments. Jongman [2] proposed a method in which a chess player is allowed to ask questions about a chess position he hss to reconstruct, that can be answered with only 'yes' or 'no'. The number of questions necessary to reconstruct the position correctly gives a good estimate of the information content of chess positions. Strong players (above 2200 Elo rating) require between 50 and 80 bits to reconstruct a position. For weaker players this amount may grow to above 100, depending on the type of position.

between instances that completely satisfy that pattern and ci ·

This concept is similar to that of projected sparseness as defined by Michalski and Stepp [3].

A relevance list is a list of functions that maps keys onto a set of attributes that are relevant to form a pattern. It consists of

elements of the following form:

Keys are salient attributes of an event description. A relevance list is supplied by a domain expert to constrain patterns to

"meaningful" ones.

A nilpattern is an <attribute,value> pair with a satisfaction factor higher than some threshold value. Nilpatterns can be detected by calculating f 8 (a . ) for all i, which are in fact all patterns consisting of one attribute. Events determined by nilpatterns with a threshold value equal to that of a single instance form the projected event space.

B. The induction algorithms.

The intention of an induction algorithm is to generate patterns with a satisfaction factor above a certain threshold, using the attributes defined in the relevance list. This involves a search through a tangled hierarchy of three levels depth: the keys in the relevance list, attributes attached to each key and the nilpatterns of each attribute. As the algorithm uses a backtracking search for the attributes, the order of attributes in the relevance list is important. This implies that the most important attributes should be listed first. If no patterns are generated with the first attributes, no patterns containing the next attributes in the list will be considered. For the experiments reported in this paper, a permutation algorithm was used in which the order of the attributes is not important. All possible combinations of attributes in the relevance list, that include the key attribute, will be tried. The advantage of the permutation algorithm is that no relevant patterns will be missed because of

ordering errors.

C. Implementation

The program, named CCAS (Chess Concept Acquisition System), is written in C-Prolog, running on a VAX 11-750 under UNIX. It consists of

four basic components:

1. Nilpattern generator

Nilpatterns are the basic building blocks of chess concepts. They have to be generated from the set of given instances before the induction process can begin. Generating all nilpatterns, required 104 CPU seconds. Nilpatterns are represented as a functor with two arguments. The first argument is the attribute name, and the second is an ordered list of values, the first value having the largest satisfaction. factor. An example of the generated nilpatterns for the white king:

nilpattern(wK,[g1,h1,h2]).

2. The satisfaction factor calculator

Both the nilpattern generator and the induction program rely on satisfaction factors of patterns. Efficient calculation of satisfaction factors is therefore important for the overall performance of the program. Using Prolog's unification for matching, the calculation of satisfaction factors is considerably faster than using other matching strategies. Calculating the satisfaction factor of a pattern with 10 instantiated attributes takes about 150 msec for a database containing 54 instances.

3. The induction program

The generation of all patterns for a relevance list with six attributes attached to a key takes about 150 CPU seconds for each key. Execution times grow exponentially with the number of arguments. For this reason, it is recommended to use many keys with lesser attributes, rather than to look for patterns with many attributes. This strategy is well suited for the domain of chess, but could be a constraint for other domains.

4. Binary question generators

Chess concepts induced by CCAS are operationally defined as valid if they reduce the information content of a chess position. Although the validity of generated concepts can be appreciated by a domain expert, the program also facilitates techniques for quantitative evaluation of the output. It includes a binary question generator that is able to reconstruct a chess position by asking questions about piece-square relationships. It uses nil patterns for question generation.

III. RESULTS

Using the following relevance list

rel(bK,[bkR,bkB,bep,bfp,bgp,bhp]). rel(wK,[wkR,wkN,wep,wfp,wgp,whp]). rel(bdp,[bap,bbp,bcp,bqB,bqR]). rel(bdp,[bcp,bep,wcp,wdp,wep,wfp]).

rel(wbp,[wap,wcp,wqR,wqN,wqB,wkB]).

and 54 instances taken from 21st move positions in a chess book ([7] games 25 to 75), the system generated 275 patterns. The number of attributes per pattern varies from 1, the nilpattern of the key, to 7, the key and all attributes in the relevance list. The most important patterns are the most specific ones, i.e. the patterns using the largest number of attributes. For each key in the relevance list, there is at least one such pattern. Most other patterns are subsets of these

most specific ones.

The binary question experiment was tried for two types of positions, those included in the list of instances, and others that are similar, but not included. The program achieves a reconstruction performance of 1001 for positions included in the instances, using an average of about 60 questions. For chess positions not included in the list of instances 1001 reconstruction is not guaranteed but often reached, within the same average number of questions. These tests indicate that the system performs on the level of expert chess players.

IV. DISCUSSION

The concept acquisition system, described in this paper, is an attempt to fill a gap in the current spectrum of automated acquisition systems. The problem addressed in this project cannot be approached by any of the existing methods. In fact, generating concepts for the description of chess positions is something that is presupposed by existing learning programs such as ID3 [8] and CLEAR [4]. Taxonomic classification programs such as CLUSTER [3] that determine hierarchies of subcategories within a collection of objects are more closely related to the problem of concept acquisition but still not suited. All rule induction programs require a set of relevant attributes to describe the domain objects. But the construction of relevant attributes for representing instances is a difficult task itself.

The patterns generated by the program can very well be considered as concepts. They are human-intelligible and some even have terms attached to them that are used in the vocabulary of domain experts, such as kings fianchetto.

ACKNOWLEDGEMENTS

This work was carried out during a three­ month visit at the Turing Institute [1]. Financial support was provided by the Belgian NFWO and the ICIWO. I would like to express my thanks to Prof. F. Vandamme of the University of Ghent, and to Prof. Donald Michie, Mr John Roycroft and Dr Tim Niblett of the Turing Institute, for their helpful suggestions.