Learning (Complex) Structural Descriptions from Examples

SUMMARY

We present a formalization of an intuitively sound s trategy for learning a description from examples within a partition examples are grouped according t o greatest resemblances and examples not in the same subse t show a maximum of differences.

I . INTRODUCTION

WINSTON [ 4.1 has demonstrated the importance of the near-miss concept in a context of learning descrip­ tions from examples. His methodology is practical when a few simple scenes are dealt with. We have extended it to include numerous complex examples.

The definition of the near miss concept [3 4] will be summarized in section 3. '

A problem arises from the fact that a large number of near-misses can be obtained which do not convey the same type of information. Our experience shows tha t at least three types of near-misses must be introduced : highly ambiguous, ambiguous and discriminant near-misses, each conveying a diffe­ rent type of information. A second problem concerns

the building of a structural description when several examples of several concepts are given, i.e. there are so many possible descriptions that a choi­ ce must be made of the most suitable as a recogni­ tion.d~vice. This leads us to define "promising" part1t1ons of a set of examples. Given a set of examples, the description will be a tree recursively constructed by the rule : divide the set into its most promising partitions. An example of our metho­ d~ logy is given below. This example is actually too s 1mple . for the ~ystem and must be considered only as an 1llustrat1on of the definitions we propose.

2. EXAMPLES

Given 3 concepts, each of them illustrated by only one example

Each labelled stroke is one element part of the example.

* ~12 ~

The first step consists of defining the reference s troke : e.g, that ~hich is most centrally located, or that which conta1ns other element, or possibly that which is directly above the central stroke.

LEARNING (COMPLEX) STRUCTURAL DESCRIPTIONS FROM EXAMPLES

REGINE LOISEL, YVES KODRATOFF

G.R.22 du C.N.R.S., Institut de Programmation, Tour 55-65 4 Place Jussieu 75230 Paris Cedex 05 France

This choice is very important as the whole process depends on it, but an explanation of the reasons underlying the choice is not within the scope of this paper.

Once a referenc~ or "most important" stroke has been chosen, its relationshi~with the other stro­ kes are computed using rules very similar to those usually used in formal descriptions [ I, 21. For example, in ''Man" M the relationship between I and 2 is expressed by : 1(1,0,0,-1)2, meaning that, a) I and 2 are tangent, b) I and 2 are not inside each other, c) I and 2 have their centers on the same vertical axis, d) I is directly below 2. Here I is the first stroke, (1,0,0,-1) is the relation­ shipbetween I and 2,2 is the second stroke. The only important point about this description is that i~ is already a generalization of the description s1nce, for example, relationships between 3 and 5 will never be looked for. '

We thus obtain a list of sublists which is a des­ cription of these three examples (this has to be accepted by the reader) :

M ((I (I , 0, 0, -I) 2) , (I (3, 0, -I , -5) 3) , (I (3, 0, I , -5) 4) , (1(3,0,-5,1)5,(1(3,0,5,1)6))

B ((2(2,4,-1,0} I), (2(3,0,-5,1)3), (2(3,0,5,1)4), (2(5,0,1,-5)5). (2(0,0,1,5)6). (2(0,0,4,3)7). (2(0,0,5,1 )8). (2(0,0,5,1)9). (2(0,0,-5,3) 10}. (2(0,0,-5,1) II), (2(0,0,-4,1) 12)).

T ((1(1,0,1,-1)2) ,(1(1,0,-5,-1)3),(1(1,0,-5,-1) 4),(1(1,0,5,-1}5),(1(0,0,4,-3)6),(1(0,0,0,-1)7), (1(0,0,-4,-3)8))

3. NEAR-MISSES

Given that MI,B2 and Tl are considered as reference strokes of the 3 concepts, the definition of a near-miss is :

If two sublists of two different examples refer to a stroke of the same importance and if the relation­ ships match except for one and only one of their elements, then the conjunction of the two relation­ ships is a near-miss between the two examples. For example, considering the lists of M and T the s~blists (1(1,0,0,-1)2) and (1(1,0,5,-1)5) ' constltute a near-miss : central (I 0 0 -1/1 0 5 -1) since they both refer to the centrai ~t;oke ~nd ' ' their relationship matches except for one of its values.

Let El and E2 be two examples. Let rl a relation­ ship of El which constitutes a near-miss with a relationship r2 of E2.

A near-miss is highly ambiguous when rl also be­ longs to E2 and r2 also belongs to El.

For example, central (3,0,5,1/3,0,-5,1) is highly ambiguous .

A near-miss is ambiguous when rl also belongs to E2 or (exclusive or) r2 also be longs to El.

For example, central (3,0,5, 1/0,0,5, I) is ambiguous. A near-miss is discriminant when rl does not belong t o E2 an r2 does not be long to El.

For example central (3,0,1,-5/5,0,1,-5) is discrimi­ nant. From the data given in section 2, it follows tha t : near-misses between M and B are

hi ghly ambiguous : (3,0,5, 1/3,0,-5, I) ambiguous : (3,0,5, 1/0,0,5, I) : (3,0,-5, 1/0,0,-5, I) separating : (3,0, I ,-5/5,0, I ,-5) near-misses between M and T are : di scriminant (l,0,0,-1/1,0,5,-1): (l,0,0,-1/1,0, -5,-1), (I,0,0,-1/0,0,0,-1) nea r-misses between B and T are

discriminant : (0,0,4,3/0,0,4,-3) ;(0,0,-4,1/0,0, -4,-3)

4. DEFINITIONS

4. I. Relationships between two examples Ei and Ej : Ei and Ej are highly comparable if there exists at least one separat1ng near-m1ss and one highly ambi­ guous near-miss between them.

Ei and Ej are comparable_ if there exists no highly ambiguous near-miss between them and there exist at least one separable near-miss and one ambiguous near-miss beween them.

Ei and Ej are seearable if there exists no highly ambiguous or amb1guous near-miss between them and there exists at least one separating near-miss bet­ ween them.

4.2. Relationships between one example Ei and a set of examples A : Ei does not belong to A. Example : Ei = T,A = {M,B}

Let IAI be the number of examples in A - High Ambiguity Value of Ei relative to A HAVA(Ei) =number of examples of A highly compa-

rable to Ei divided by IAI

- Ambiguity Value of Ei relative to A : AVA(Ei) = HAVA(Ei)+(number of examples of A compa­ raole to Ei + number of exam~les of A belonging to the same concept as Ei)/ !AI

- Discrimination power of Ei relative to A : SA(Ei) = AVA(Ei)+ number of examples of A separable from Ei/ IAI

4.3. Relationships between two disjoint sets of examples A and B :

Definitions are those of section 4.2 except that all examples of B must be summed over, for each Ei belonging to B.

5. MOST PROMISING PARTITION OF A SET

1. Partition of a set A by a near-mis s n : n is defined by the rela t ionshi ps rl and r2. Let X be the subset of A which contains all the examples to which rl or (non-exclusive or) r 2 belong. Let X' be the subset A-X.

The partition (X,X') is the partition of A by n.

5. 2 . Indexes of ambiguity and dis crimination powe r of a se t A of examples :

the def initions of section 4. I are computed f or all element pairs of A. Let II All be the number of element pairs of A. ·

- High Ambiguity Index of A :

HAl(A) = number o f highly comparable exampll' pair s of A/ II AII

Exampl e : HAI({ M B U) = I /3

- Ambiguity Index of 'A, :

AI(A) = HAI(A)+(number of comparable pairs of A +number of pairs belonging to the same concept)/ II All

Example: AI({~,B,T}) = 1/3

- Discrimination Index of A :

SI(A) = IA(A) + number of discriminabl e pairs of A/II All

Example: SI({M,B,T}) =I

5.3. Definition of a most prom1s1ng partition Let nl ... np be the near-misses of the example pairs of A. We obtain p partitions of A by nl ... np. Let(X,X') and (Y,Y') be two of these partitions. (X,X') is considered more promising than (Y,Y') when :

SI(X) > SI(Y) ifeqthen SI(X') > SI(Y') ifeqthen

HAVX(X') < BAVY(Y') ifeqthen AVX(X') < AVY(Y')

ifeqthen HAI(X) > HAI(Y) ifeqthen HAI(X') > HAI(Y') ifeqthen

AI(X) > AI(Y) ifeqthen Al(X') > AI(Y') ifeqthen I XI > I Yl

where the operator ifeqthen means : if the prece­ ding values are equal then ...

Example :Let us consider nl=(3,0,5,1/3,0,-5, I) which creates the partition PI : X= li,B, X'=T, and n2=(1, 0 ,0,- 1/I, 0 ,5,-I) which creates P2 : Y=li,T,

Y'=B. SI(X)=SI(Y)=SI(X')=SI(Y')=1 HAV (X')=O, HAV (Y')=I/2 . It follows that PI is mor~ promising than P2.

6. CONCLUSION

Comments on the intu1t1ve meaning of the most promising partition : whil e ambiguous and discri­ minant near-misses both emphasize di fferences and resemblance s between two examples, their respec tive ~roportions of information relative t o resemblance vs. information relative to differ ences are not the same. Therefore, ambiguous and discriminant near­ misses do not convey the same type of information. The role of the above de fined indexes is t o express this difference-resemblance play among examples. This means that ou r structural de scription will be built as fo llows . We first try to find discrimina­ ble se ts (and thei r associated near-misses) . ~1en we have severa l discriminable partit ions, we choose among them by minimizine the ambiguit y be tween the two subset s of the partition. If a choice still remains, we maximize the ambiguity of each of the subsets. The last t est simply tells which one has the greatest number of elements verifying the given near-miss .

This means that we want to keep together exampl es which a r e discriminable as long as possible.

In fact, we describe our work as a formalization of this sound strategy.

BIBLIOGRAPHIE

1. T.G. DIETTERICH, R.S. MICHALSKI Learning and generalization of characteristic descriptions : evaluation criteria and compara­ tive review of selected methods Proc IJCAI 79 Tokyo 1979 pp 223-231
2. N. S. FU Syntactic methods in pattern recognition. Aca­ demic Press (1974)
3. Y. KODRATOFF Non statistical learning to analyse scenes by the use of ·the "near-miss" concept. Proc 4th IJCPR Kyoto (1979) pp 384-386
4. P.H. WINSTON Learning Structural descriptions from examples Ph. D. Thesis MIT(I970).

No te added in proof.

Using a quite different description than the above one, but using the same near-miss definition and our "most promising partition" concept, we 'lery recently built an efficient recognition tree for a very dif­ ferent probl em, namely the carcinogenic power of big che~ical molecules.