Learning Concept Descriptions from Examples with Errors

1. Introduction

While the maJonty of the AI work on learning concentrates in error free domains, there is an acknowledged need for learning techniques directed towards noisy data [Dietterich and Michalski, 1983], [Mitchell, 1982]. A problem of a major importance in learning from data with errors is the choice of the preference criterion for ranking competing descriptions. The criteria such as maximum likelihood, minimum error, or minimum estimated entropy which are generally used for inference from noisy data, suffice for inferring simple parametric models, but are not well suited to learning in rich spaces of symbolic descriptions used in AI. These criteria minimize the discrepancy between a description and the training observations. If the language used to form descriptions is sufficiently rich to express the training data, such criteria will rank a description that exactly matches the training observations as better or equal to any other description. For example, if the space of descriptions includes predicate calculus expressions, a concept A represented in the training set by three instances, whose parameter "length" assumes values 4.6, 5.2, and 5.7, might generate a description: (/ength(A) - 4.6 OR length(A) - 5.2 OR /ength(A) - 5.7). Any errors in the training data will be represented in such an overspecified description along with possible regularities. A version of this problem known as the "curse of dimensionality" appears even with simple vector models when the number of dimensions is not specified, [Kana), 1974].

One way of preventing the inference process from generating overspecified descriptions is to include some measure of description complexity in the preference criterion, to bias it towards simple descriptions. This idea is well known in philosophy of science (Occam's razor), and various measures of complexity (or simplicity) were proposed in AI literature [Michalski and Stepp, 1983], [Michalski, 1983], [Mitchell, 1980], [Buchanan and Mitchell, 19781. A specific question is the trade-off between the complexity of a description and the discrepancy with data. A criterion objectively combining these two measures by relating both to Kolmogorov's complexity [Kolmogorov, 1968], was introduced in [Segen, 1980] and called minimal representation criterion.

In this paper we apply the minimal representation criterion to

·

LEARNING CONCEPT DESCRIPTIONS FROM EXAMPLES WITH ERRORS

Jakub Segen

AT&T Bell Laboratories, Holmdel, N.J . 07733

derive general rules for learning concept descriptions from noisy training data. These rules can be used to learn symbolic descriptors, such as logic formulas, as well as parametric models. In Section 2 of this paper we summarize the minimal representation criterion, in Section 3 we apply it to derive selection rules for two types of descriptors: concept specific descriptors and globally useful system descriptors, and to decide which descriptors should be used with default values. In Section 4 we show how to apply both types of descriptors to classify instances using bottom-up and top-down strategies.

2. Minimal Representation Criterion

Consider the problem of finding a program for a Turing machine, to generate a given finite sequence of observations. While there are infinitely many programs for any such sequence, it seems reasonable to chose the shortest program since it represents the least commitment and minimum redundancy. If we treat a program to be a randomly generated binary sequence with O's and I 's having equal probability, then the shortest program is also the most probable one. The problem of selecting a probability model P (y) from a sequence of observations y" - Yl>Y2·····Y· can be recast as a case of the above problem by establishing an isomorphism between the class of probability distributions and a subset of programs for a Turing machine [Segen, 19801. Selecting the shortest program in this subset corresponds to finding a probability distribution minimizing the expression

where S (P (y)) is the number of bits needed to specify the probability distribution P (y) . All the logarithms used in this paper are in the base 2. The above criterion for estimating the probability distribution has been called the minimal representation criterion . Its main difference from the maximum likelihood criterion (equivalent to seeking a minimum of -logP(y") ) comes from the term S(P(y)) , which is a measure of a complexity of the specification of the probability distribution P (y) . Including it in the criterion in effect penalizes more complex distributions.

Properties of the minimal representation criterion were treated formally in [Segen, 19801. It has been applied to discover patterns in a continuous signal and in a symbol sequence, and to such problems as selecting the number of clusters.

3. Choosing Concept Descriptors

The problem of selecting a single descriptor for each concept can be stated as follows: Given is a training set T, consisting of a set of instances X 1 ,X 2 · · · Xk and a concept assignment for each of the instances: Xk-+C; . Also given is a space F of functions, which we call descriptor functions or descriptors, defined on the domain of instances. A descriptor can be any computable function with a probability distribution defined on its range of values. For each of the concepts CI>C2 . ·. Cm we want to select a descriptor fE F that is most helpful in deciding whether an instance with unknown concept assignment should be assigned to this concept.

We approach the descriptor selection indirectly, as a problem of estimating the conditional probability P (C1 IX) while its form is restricted to:

Descriptor selection is a part of the task of finding the estimate of this form, for which we will use the minimal representation criterion. If the instances and their concept assignments in the training set are independent, we can write the logarithm of the probability of the concept assignments given in the training set T as

where X1 1,Xi2 · · · X1· <O are the instances assigned to concept C1· Choice of the best descriptor for a given concept C1 can be treated as a single concept problem. In this case:

Using Bayes's formula, equation (4) can be written as:

where

Applying the minimal representation criterion, we should minimize:

with respect to f, P (j (X) I C;), P (j (X) 1-C;) and P (C1) . Selection of the best descriptor is a part of the minimization task. Computation of S (P) for parametric probability models was discussed in [Segen, 19801. Evaluation of S {j) is based on a representation of the descriptor. For example, if a descriptor is a concatenation of k primitive operations, we need S{j) - (k+l)*log(n+l) bits to express it, where n is the number of primitive operations available. The best descriptor can be found by searching the space F in order of increasing descriptor complexity, and this search will always terminate [Segen, 19801. If descriptors are binary valued then (6) is minimized for each descriptor by replacing probabilities in (5) with corresponding frequencies, which makes the learning of logic formulas particularly simple.

A descriptor f that results in a higher value of Q(T,P(T)) than a "no descriptor" case, i.e. the case when P (C1 IX) - P (C1), will not be selected even if there are no other competing descriptors. We will call such a descriptor not informative with respect to C; . The best estimate of its conditional probability P (j (x) I C1) is the P (j (x)) , which can be used as a default distribution for C1·

Once the best single descriptor for a concept is found we can search for additional descriptors to form a conjunctive description . If descriptors f 1J 2 · · · !k are independent for C; and C_1 we can write:

' Using this form in (4) to compute P (T) we can search for descriptors incrementally, i.e., having found descriptors f 1J 2, .. .f. we can find a descriptor fv+l minimizing the criterion while using the previously found distributions for f 1J 2 ·· .f ·. This process terminates when an addition of another descriptor does not decrease the value of Q (T ,P (T)) . Notice, that we do not assume that all descriptors are independent, but search for the best set of descriptors using (7) as a constraint. Also, the inconsistency pointed out in [Pendault, Zucker, and Muresan, 1981) does not appear since there are only two disjoint sets.

Descriptors selected in the above process are useful for a specific concept and we call them c-descriptors. In addition we can search for globally useful descriptors that discriminate among many concepts at once. They will be called system descriptors or s -descriptors . System descriptors can be selected and rated using the expression (I) with:

Here we include the conditional probabilities for all the concepts, so descriptors are rated according to their average discriminating power. We can select and order some number, or all informative s­ descriptors. All the s-descriptors that are informative with respect to a concept C1 will form a set SD1· This set along with the values of P (j I C;) can be considered a probabilistic version of frame.

4. Using Descriptors to Classify Instances

A direct approach to classifying an unlabeled instance is to compute the probability P (C1 IX) for every known concept using c­ descriptors, and select the concept with the highest probability. However, if there are many concepts this strategy can be expensive. In such a case, we can use a data-driven search based on s-descriptors to select quickly several most likely concepts, and then evaluate only the c-descriptors of the selected concepts. Let f " fl , .. .. fk be the results of applying any k s-descriptors to the instance X. We can roughly evaluate the probability P(C11/1J 2, ··· fk) by assuming their conditional independence.

We do not need to normalize the right hand side, since we are interested only in order imposed by the probability, not its absolute value. This proportion will not be affected if the right hand side is divided by P{j1)*P{j2)* ... *P(jk) , for all i (this value is not equal to P(j1J 2, ··· fk) , since we assume only conditional, and not marginal independence) .

P(j, IC;) Now, since p (j ,) - I by default when the s-descriptor f, is not a member of the set SD1, we can eliminate all such factors from the product. Also, the order imposed by the above proportion will be preserved if we take a logarithm of the right hand side. We will call the result an evidence towards the concept C1 based on the facts f 1 f2, ... fk.

The evidence provides the same ordering of concepts as the probability but its much less expensive to compute, since evaluation of a descriptor changes the evidence only for a subset of all concepts. This subset is known a priori for each descriptor and it can be much smaller than the set of all concepts known to the system. Therefore, we can provide links from each s-descriptor to the affected concepts and update only the evidence for these concepts after evaluating the descriptor. An expression similar to (II), but without the above feature, was presented in [Charniak, 19831. The decision for switching from evidence accumulation to evaluating s-descriptors can come in two ways: either evidence for some concept reaches a given threshold, or after evaluating some number of s-descriptors the concepts are sorted and tested in order of decreasing evidence.

If the range of a descriptor f m is a small set of discrete values Vml> vm2, ··· , we can set a weighted link from each outcome vm1 to each concept C1 for which f m is informative, with the weight of the link equal to log(P(vmdC1) I P(vm1)). A firing outcome simply adds link weights to the evidence of corresponding concepts. Such an organization clearly resembles models of neural nets, and it can be carried out in a parallel architecture such as Thistle [Fahlman, Hinton, and Sejnowski, 1983].

5. Concluding Remarks

The methods proposed here for learning of descriptors apply to both parametric models and logic formulas. They are particularly simple for predicate descriptors since their probability can be estimated as frequency. While we have not discussed domain specific descriptor generators, many of the generation schemes presented in AI literature [Dietterich and Michalski, 1983] [Cohen and Feigenbaum, 1982], [Michalski, 1983] are compatible with the methods of this paper. A side result that might become important for large systems is the automatic assignment of a default status to some descriptors. The most important direction for future work lies in developing incremental learning strategies, needed for both time and storage efficiency.