Algorithms for Learning Logical Formulas

1. OUTLINE OF THE METHOD

We consider a set of objects, called the training set. This set is described by several "describers", which are questions (or binary varia­ bles) with a value for every object.

Let us take one of these describers and call it the "variable to forecast". The a~m of the method presented here is to find a combination of the others describers identical to the variable to

forecast.

The method we propose consist on the iteration of an algorithm made of 3 modules : expansion, se­ lection, compression.

Expansion step consist on combining each couple of describers with a logical operator, in

order to obtain a new set of describers.

Selection consists on eliminating the descri­ bers which are not "similar" enough to the variable to forecast.

Compression step then classifies the descri­ bers according to their similarities, and summarizes We shall now describe each of these parts.

2. EXPANSION

This step consist on combining each couple of describers. Then, the operator must be associative, so that the combinations of 3 or more describers are nothing but successive· 2 by 2 combinations. On the other hand, the permutation of 0 and 1 ("true" and "false") must not disturb the result of

expansion.

These constraints suggest two possible opera­ tors : the logical conjunction "and", and the logi­ cal equivalence "id".

With the conjunction, 4 describers are built for each couple of initial describers :

a and b ; (non a) and b ; a and (non b) ; (non a) and (non b).

After that, we have to check the consistency, i . e. if (d) is in on formula, then (non d) is not in another one.

For the logical equivalence, we have the following properties :

a i d b = (non a) i d (non b) ; (non a) i d b = a i d (non b) = non (a i d b) .

According the remarks made at the beginning of this paragraph, it is only necessary to build "a id b".

It is easy to check the fitting of these opera­ tors with the constraints described at the beginning of this paragraph.

3. SELECTION

The aim of the selection step is to compare a describer to the variable to forecast, in order to select the describers which can be frucfully expan­ ded again. The most natural way of comparison between 2 binary variables is to look at the list (NOD N01 N10 N11) of the co-occurence frequencies for the different values of the variables, i.e . of the describer to be selected and the variable to forecast.

Several criteria are then possible for the se­ lection. We consider here two kinds : overlapping criteria and information theor-y criteria.

An overlapping means that the describer has one value for at least a part of the objectsfrom one class and the other value for at most a part of the objects of the other class. The corresponding thresholds are given by the user.

The Information Theory criteria are different of the previous one, in the sense that they are not used in the same way. They are information measure­ ments on the describers, which are then ordered according this measure, and the k best ones are selected, for a value k which is choosen by the user.

Several criteria are possible. For instance, we can use the Kullback's divergence, the Mahalano­ bis distance or the contingency-khi 2 criterion.

4. COMPRESSION

This step consists on summarizing the set of the selected describers, regarding their inter correlations, which are measured by a given func­ tion.

Then, we have to perform an automatic clus­ tering of the describers into k groups.

4.1. Optimization of a clustering

In this paragraph, we state the problem of optimizing, for a given criterion, a k-class clus­ tering. As we previously noticed, we suppose that a distance has been chosen to measure the decorre­ lation between the describers.

Then, the criterion to optimize is the sum of the distances of the describer i to the descri­ bers which are in the same class. Let D(i j) be the sum of distances between describer i and the describers belonging to class j. Let j (i) be the class which contains describer i. Let us state

W (i ) = D ( i j ( i ) ) - min ( D ( i j) j = 1, k) W (i 0) = rna x ( W (i ) i = 1 , ... ) D(iO jO) =min (D(iO j) j=1,k)

Then, the algorithm deletes iO from its class and appends it to the class jO.

This procedure is repeated until the obtained classification is invariant, i.e. W(i)=O for all the describers. This algorithm is actually a local optimization one, because we can easily proof that the criterion W(iO) is descreasing at each step.

The initial clustering may be randomly chosen, or given by the user. We shall now use the later possibility to define a strategy for compression.

4.2. The compression algorithm

An interesting aspect of the previous algo­ rithm is that it works even if one class is empty. This remark suggests a strategy for compression, which needs only to input the maximum number of classes.

The algorithm starts with a one-class clus­ tering. Obviously, the value of the criterion is zero in this case.

When the best (k-1)-class clustering has been found by the algorithm we described in the previous paragraph, an empty class is created and we look for the best k-class classification.

The algorithm stops when k is the given maximum value nmc. We can notice that, if the sum of intra­ class distances is zero for k < nmc, then the (nmc-k) other classes will remain empty.

Once we have obtained the desired classification, each class is summarized by one (or a small number) of its elements. We shall describe this point in the following paragraph.

4.3. Summary of a compression

The summary of a compression must depend upon the chosen distance. The purpose of the distance is to compare 2 describers. Then, it will be defi­ ned with the list of co-occurences of values of the describers (NOO,N01,N10,N11).

In the case of the equivalence distance min (NOO+N11,N01+N10), we can choose any element of each cluster, because they are supposed to be logi­ cally equivalent, except for a few objects.

In the case of the comparability distance min (NOO,N01,N10,N11), the characteristic of the ele­ ments of the same cluster is to be comparable to each other, except for a small number of objects. This kind of relationship may be summarized by ordering the describers, and then using a dicho­ tomic decision tree to compress.

Then, this kind of compression can be viewed as an "unfolding" (dimensionality reduction) of the training set, and we studied it in some pre­ vious works [ 7].

5. END CRITERION

As the aim is to find a formula which is, on the training set, logically comparable to the va­ riable to forecast, there are several ways of stopping conveniently the algorithm :

• -maximum number of iterations (it is careful)
• emptiness of the describers list (it may happen after a bad choice of the selection parameters)
• one (or several)of the built describers is sufficiently correlated to the variable to forecast.

These criteria are applied in the previous order. We can add some more, in order to detect the case when it is useless to continue. For ins­ tance, if the describers list remains identical after a new expansion, selection and compression ("stability" criterion), it is clear that further iterations will give the same result.

6. GENERALIZATION BY "RULE STORMING"

The generalization consists on decision making outside the training set. Then, the logical rules built with the previous algorithm can be considered as "opinions" about the training set, each orebeing related to the choice of a particular describer as variable to forecast.

The generalization itself consist on perfor­ ming a "rule storming" on these opinions. Let us summarize this idea. According Michalski [5], a general ization is a filter (in the topological sense) on the space of objects.

l.et w be an object and OP(i) the i-th opinion . Then, OP( i,w) is the new object produced by applying the rule OP(i) tow. Several cases are possible :

OP(i,w) = w (at least on the training set).

OP(i ,w) w', then OP (i ,w') = OP(i ,w)

OP(i ,w) =~(the rule is not applicable).

Then, the filter is :

V(i) = {w} U (U OP(i ,w)

V ( p) = { w} U ( U OP ( i , V ( p-1))) .

The rule storminq i s then made by a vote at a given level of this filter.

An advantage of this technique is that we actually build a topology, then we need not a dis­ crimination problem to generalize.

7. RESULTS AND DISCUSSION

Thi s technique has been tested on real problems : learning of animal behavior, control problems on nuclear plants, forecasting earthquakes, learning meta-rules for expert systems, decision making in psychology.

In all these applications, only a few (3 to 5) iterations of the expansion-selection-compression were necessary to find the rules. For the generali­ zation, the good decision was made at level V(1) or V(2), but never more.

8. CONCLUSION

The algorithm that we presented in this paper in a first draft of a tool for learning problems. We work now on its enhancement and integration in a complete learning system. We think that the pre­ sented results show reasonable efficiency and compu­ ting costs. The theoretical background can be found in the field of non classical Logic [1], more preci­ sely non distributive logics.