Concept Learning by Structured Examples - An Algebraic Approach

1. Introduction

Concept learning on sets of structural de­ scrip tions has become one of the most challenging problems in AI-research in the last decade /1/, /3/, /7/, /9/, /10/, /13/. /14/.

There is increasing success of programs that make use of domain-specific knowl­ edge like DENDRAL and METADENDRAL. But there remadn areas, where a priori knowl­ edge may be not or only partially avail­ abl e or the aquisition and application of knowledge would be difficult as in con­ structing rules from large sets of empir­ ical data.

On the other hand in order to leave the empirical stage and to establish theore­ ti ca l foundations AI has to discover gen­ eral principles and to find appropriate formalizations for them. Therefore uni­ fied mathematical models should be ap­ plied as far as possible.

There a re practical applications of con­ cep t or discrimination learning in which first the structures and training samples a re large, second the concepts may be disj unctive sets of subconcepts and third matching is complicated because of the existence of many isomorphic descriptions {alphabetic variants).

It is felt that in such cases well elabo­ r a ted general algorithms such as the in­ ductive generalization in the predicate calculus a~d even the version space meth­ od / 8/ would face problems of combina­ torial explosion. (Refinements of the predicate calculus-based methods are de­ veloped in our laboratory /5/ which, it is hoped, will overcome some of the dif­ ficulties in dealing with practical pro­ blems.)

In this paper first a new method of the description of structures is represented which is based on recent graph theoretic results in the detection of isomorphism /4/.

From descriptions being almost invariant under isomorphism feature vectors are for­ med describing the structures unambi­ guously. This enables us to use well known techniques of concept learning on feature vectors to solve or at least to reduce the complexity of the concept learning task. In particular we adopt a method of sequentially constructing deci­ sion trees representing the hypotheses in terms of discriminant descriptions of a possible multiclass problem.

The algorithm corresponds to a general­ to-specific depth-first search with re­ examination of past instances. As a first practical example a set of 89 chemical compounds with up to 15 nodes each is treated successfully.

In addition, our approach gives the possi­ bility of learning concepts defined by relations to other concepts (context), a problem which until now has not yet been a subject of AI-research.

2. Description of structures

Definition 2.1.

A structured object (briefly structure) is a relational algebra

with the set of eleme~tary_QQjects V~, th e set ofone-place relat1ons Pi, 1 = 1, ··· ,s 1 and the set of two-place relations Rj, J = 1, ··· ,s 2 (Higher order relations may be transformed into sets of two-place ones).

It is supposed that~ is represented in the memory by a labelled graph GE with the set of nodes N corresponding to the set of elementary objects VE by the bi­ Ject1on

Different maps d lead to isomorphic de­ scriptions (alphabetic variants). A node is labelled with all relations of which the elementary object corresponding to the node is an element. An arc is la­ belled . by the corresponding two-place re­ lations (fig. 1).

Fig. 1: Labelled graph describing an arch

Suppose a training sample S = { G , G , 1 2 ··· , GM} of descriptions of structures is given. Each combination (vector) of rela­ tions found in the training sample a co­ lour or new complex relation is ascribed (fig. 2).

u.1 lL 1 Fig. 2: Ascribing colours to nodes and arcs of fig. 1

Let U be the set of node colours and W the set of arc colours found in the trai­ ning sample. We refer to U and W as the set of elementar~ properties (feature vectors) of nodes and arcs respectively. Formally, we have the following defini­ tions:

Definition 2.2.

A description of a structure Lis a col­ oured graph GE = (N, Q, UE, WE, f, g)

with the set of nodes N, the set of arcs Q £ N x N a nd the colouring fun c tions

Definition 2 .3.

Two descriptions G and G' are isomorphic if there exist a bijective map d : N-N' with

(d(i), d(j)) E: Q',.......(i, j)E.Q

f(i) = f(d(i)) and g(i, j) ~

= g(d(i), d(j)).

An automorphism of G is an isomorphism onto itself.

Isomorphic graphs in the training sample are supposed to describe the same real structure L and to arise from using dif­ ferent coding strategies. (Therefore they must belong to the same class in the case of consistent training samples.) Identi­ fying isomorphic descriptions is especial ­ ly in practical applications a very impor­ tant task. As anovel approach to this pro­ blem in our system descriptions invariant under isomorphism are used in order to get efficient concept descriptions, matching and generalization possibilities. An in­ variant characterization of a structure would be the set of all n! descriptions generated from a description given in the training sample (or as test item to be matched) by permutations of the nodes. But this set is, in general, much too large.

(A normalization to a standard descrip­ tion by alphabetic ordering would hide similarities of structures which are used in the construction of efficient concept descriptions, see below.)

To reduce the number of descriptions ge­ nerated a method used in algorithms de­ tecting ~somorphism of graphs 141 was adopted.+)

Definition 2.4.

Two nodes i, j of a description G are (elementary) distinguishable iff f(i) I f(j), i.e. they have different colours.

By this definition a partition of the set of nodes into equivalence classes of equally coloured nodes

is induced, this partition being inva­ riant under isomorphism. The number of des c riptions is therefore reduced from n! to 'Jt'U card S ! · For example in fig. 2 UE. E u ' there are the equivalence classes S and S with cardS = 2 and card S =ul u2 u1 u2 = 1, i. e. 3! > 2! · 1!.

To reduce the number of descriptions further context dependent features of nodes and arcs are introduced.

Definition 2.5.

Let iE.N, (i, j)E.Q, then

nw(i) = card{j I g(i, j) = w}, wE.W,

is the number of neighbours of node i which can be reached by a w - coloured arc. For arcs similarly

(s,t)E.U x W or (s,t)E.W xU or (s,t) E.W x W is defined.

+)The authors would like to thank Dr. D. Potschke for many helpful theoretical discussions.

The ns t are the numbers of graphs of the foll owing trg k

resulting by reconstruction in the parti­ ally labelled graph of fig. 3.

Fig . 3 : Context dependent arc features The n ( i) 1 w ~ W can be ordered to get tow ge ther with the original colour f{i} a new (context dependent} feature vector (f(i}l n 1 n 2 1 ··· 1 n ) for every node i. 1 r Similarly one gets new feature vectors for a rcs {i 1 j}. These feature vectors can be used in lear­ ning concepts which are defined by con­ text (as most human concepts are!), i. e. when the membership of an object to a cla ss (concept) is defined by relations to o ther objec ts. In this case a training sampl e consists of a set of distinguished elementary~jects (nodes)_ together with str uc tures in which they are embedded and the class of the nodes {being positive or nega tive instances) depends on the exis­ tence of certain subgraphs in the embed­ ding structures. The theory is outlined in /12/ .

The step described in Def. 1.5. is done fo r all descriptions in the training sample and le~ds to new sets u(l) and w( 1 ) of node a nd arc colours respectively with new co louring functions f( 1 ) and g( 1 ) for each graph. (In a sequential learning t a sk t~e sets u< 1 >, w( 1 ) may be sequen­ tial ly updated.) Nodes i 1j which are not elementary distinguishable (definition 2 .4) may now become distinguishable by context i. e. f( 1 ) (i) 1 f( 1 )(j).

Example: The nodes 1 and 2 in fig. 2 not e lemen t a ry distinguishable become distin­ guishable by context if the asymmetric rela tion LEFTOF is added to arc (1 1 2 ~. Addi tionaily, the new features£ u< 1 , w( 1 ) a re easily computable graph characteristics, which can be used for the con­ cept learning task (see below).

Proposition 2.1. (1) The new partition of N according to U is equal or finer than the partition ac­ cording to U and the number of permuta­ tions may be further reduced. Proof: see /12/.

The step of def. 2.5. may be repeated and leads in that case after a finite number of iterations to stable f(i),s and g(i),s, thereby _getting_Rossibly exactly one de­ scription of 2:: (automorphism partition of the nodes /4/).

In practical cases and sequential lear­ ning tasks one would stop after a fixed number i of steps depending on the pro­ blem. Let the set of descriptions of L generated by the remaining permutations by c~i)

3. Transformation of graphs into feature vectors

Now we want to transform the graphs cfi) E. ofi) into linear representations (feature vectors) which can be easily handled by well elaborated algorithms of concept learning on sets of feature vec­ tors. First we represent all edges {j,k} of Gti} together with their adjacent nodes j,k by triples (wjk 1 uj, uk) of their col­ ours. If uj = uk then j and k belong to the same equivalence class and have to be distin guished by an additional number in order to save the full graph information (for instance the pair {1,2} in fi~. 2 has to be described by (w 1 (u , 1), (u 1 , 2})). All different tripl~s occurring in the training sample are construc­ ted (or sequentially updated} and enumer­ ated. These triples correspond to elemen­ tary propositions with the labels u,w indicating complex semantic features of case arguments and relations respectively.

Another possibility of defining features for the graph classification task con­ sists in choosing subgraphs of several orders (gestalt features). A method of selecting subgraphs and using them as tests to be built into decision tree­ classificators has been developed in our laboratory successfully and applied to practical problems /.11/·

A feature vector v( 1 } corresponding to a g raph �~i} E. ofi) is now defined as fol­

lows v(i)= (x1, ··· ,xr; y1, ··· ,ys; z1····~zt)

x . = 1 iff the node colour u . e. u{i}:Jccurs J J 1 times in

z = {1 iff triple j occurs in cJ:i) j 0 otherwise Let V~i) be the set of all vectors gener­ ated from all graphs Gt 1 ) in of 1 ). Theorem: The map L- V(i) is a bijec­ tion, i. e. the S€t vii) describes unam­ biguously the structure L. · The proof is given in /12/.

4. Concept learning

As an algorithm for concept learning a method of sequent1ally constructing hypo~ theses in form of dec1s1on trees 1s used, which is more appropr1ate to problems with large feature vectors, It 1s a gen­ eralization of human behav1our observed in learning concepts represented by pro­ positional functions /12/ and it is simi­ lar to the algorithm of learning discri­ mination nets for syllables described in /2/. It corresponds to a general-to-spe­ cific depth-first search with reexamina­ tion of past events. (Due to limited STM capacity human beings are keeping only one hypothesis per step in me~ory. This method is ~referred to a possible breath-first search since in case of large structures, large training samples, and disjunctive concepts the number of hypotheses to be pursued simultaneously would be probably to large even in the case of the lattice-theoretic approach used in /8/. In large samples it is also not easy to get initial clusters for dis­ junctive concepts.) Since the decision trees are built up serially by adding no more than one new test attribute (test node) per step to the tree, the set of attributes A= {v 1 , ... ,vn} constituting

the feature vectors is a priori reorderoo by some elementary discrimination measure known in pattern recognition. (In a more sophisticated approach this procedure is applied to each branch of the tree repre­ senting the current hypothesis.)

The algorithm can be defined in terms of simple data driven production rules. In the case of finite consistent training samplffi it can be proved /12/ that it re­ sults in a final hypothesis which matches all training instances correctly. In /12/ extensions to the case of inconsistent tr a ining samples, probabilistic decisions, and continuously varying attributes (al­ gorithmic construction of feature inter­ vals during learning) can also be found.

Generalization

First, one gets a simple generalization by means of the fact that the construction algorithm, in general, stops before all attributes are exhausted on each path. Second, irrelevant attributes in the tree (or conditionally irrelevant attributes in subtrees) may be contained leading t o symmetric branches which can be detected. An equivalence transformation of the tree is then performed using a calculus first described by McCARTHY /6/ for optimizing propositional functions in tree ·form. At ­ tributes being dependent on others already used on a certain path are also detected and eliminated thus getting additional rules describing feature dependenci es a nd the structure of the domain.

No~ let us consider the tree in fig. 4 which represents a hypothesis in a con­ cept learning problem on struct ures. A test node is labelled by a triple z , i. e . J

1f z exists in the structure to be matJ ched, the structure passes the 1-branch, if not 1t passes the 0-branch. Each path in the tree represents a subclass (sub­ concept) by a conjunction of the z . 's ( 1J

labelled branches) or their negations ( 0labelled branches), the whole concept be1ng the disjunction of all paths with terminal nodes labelled by the concept. (The extension of the formalism to multi­ class discrimination problemsis obvious.) Since the z . 's correspond to triples des­ cribing an ~rc together with its adjacent nodes, unambiguously identified "by their colours (possibly with additional numbers), the positive z . 'son a path can be combi­ ned into a sub~raph characterizing the concept (fig. 4). The negated z . 's on J

this path correspond to the "must not" conditions of /14/ i. e. they are forbid­ den in the substructure.

Generalization on node and edge features

Generalization on node and ed ge features may depend on th e place in the structure where the elementary object o r relation

1s embedded, therefore a priori given ge­ neralization hierarchies on elementary features may not be helpful. For instance, it may be irrelevant for the concept "arch" ( fig · 1 ) , whether the top object (and only this) is a brick or wedge. Therefore, generally, the system has to learn context dependent generalization hierarchies.

Irrelevant features of such kind lead to substructures in the trees constructed by our· algorithm having an "analogous" compo­ sition in the sense that the substructures can be made identical and merged by intro­ duc lng variables for corresponding con­ stituents ln corresponding triples. This proc edure is the tree-analogue of VERE's algori thm of inductive generalization in the predicate calculus /13/.

5. Experiments

To 1llustrate general issues and techni­ ques of our approach one particular con­ cep t learning problem, originally discus­ sed by WINSTON /14/ will be described. It involves the learning of how to identify simple classes of structures built of chil­ d ren's blocks. The task is to learn the concept of an arch, with a series of block st ructures being given, each labelled as either an arch or a non-arch. In compari­ sion with WINSTON~s world our sample is supplemented by additional structures. It consists of 10 or 11 elements (see fig. 5~

The described algorithm constructs com­ plex features to characterize allele­ ments of the training sample (see 2.). The decision tree approach selects only those tests from the set of the a priori reordered attributes that it needs to identify all training examples.

The results are illustrated in fig. 6. The decision tree resulting from the sam­ ple that does not contain the structure shown in fig. 5 b) is illustrated in fig. 6 a) . It contains only one node feature. The label '2' in the test of the decision tree means,· that there must be at least two nodes 'of that type' in a structure. The algorithm produces the decision tree shown in fig. 6 b), if the training sam­ ple contains additionally the structure shown in fig. 5 b). The selected arc fea­ ture (fig. 3) discriminates all arches from the non-arches. (Note the generali­ zation on the form of the top object.)

Our program is written entirely in FORTRAN and consists of about 3 000 exe­ cutable statements. It runs in 150 K bytes of memory on the BESM-6 computer.

6. ~cation

In pharmacology there is the problem to find atoms or groups of atoms (substruc­ tures) in chemical compounds necessary to evoke a specific biological activity. The knowledge of such substructures may be a starting point for the synthesis of new drugs.

As an example a training sample of 89 carboxamides the structural formulas of which were known was investigated. These compounds scaled by their biological ac­ tivity were divided into four classes. The structural formulas of the compounds were transformed into coloured graphs. Each atom or group of atoms is considered as a node in the graph, each type of bond as an edge.

Our &lgorithm described above was applied to this four-class problem. From 89 grap~ (objects) the computer generated by the permutation of some of them 103 descrip­ tions with altogether about 300 complex features(triples) including the context after the second iteration (see 2.). A disjunction of characteristic substruc­ tures was obtained for each class. Our results were confirmed by the empirical knowledge of chemists.

The central processor time needed on the BESM-6 was about 20 minutes.

7. Summary and conclusions

A concept learning system has been de­ scribed which is based on descriptions of structures invariant under isomorphism and transformation into feature vectors. The generalization ab1lities are demon­ strated in case of the blocks world ex­ ample.

The algorithm can treat training samples of about one hundred of relatively compl1cated structures in a reasonable time. Since the use of all possible features ( g raph properties) characterizing a structure would lead to combinatorial ex­ plosion, subsets of feature are extracted by a unified principle. Global character­ isti cs (subgraphs) relevant to the concept a re subsequently synthesized in the form of Boolean functions constituting the fi­ nal concept description. Complex or ele­ mentary features irrelevant to the con­ cep t and yet included in the final hy­ pothesis can be eliminated by a second­ ary generalization and optimization pro­ ced ure.

Acknowledgements

The duthors would l1ke to thank Dr. D. Potschke and Dr. G. St a nke for many help­ ful discussions. s. Doring and R. Muller are gratefully acknowledged for pro­ gramming parts of the system.

Reference

/1/ DIETTERICH, T. G.; MICHALSKY, R. S.: Learning and generalization .of character­ istic descriptions: evaluation criteria and comparative review of selected meth­ ods; In Proc. IJCAI-6, 1979.

/ 2/ FEIGENBAUM, E.: The simulation of ver­ bal learning behaviour; In Computers and Thought (E. FEI GENBAUM and J. FELDMAN, Eds.), New York 1963.

/3/ HAYES-ROTH, F.: Collected papers on the learning and recognition of struc­ tured patterns; Carnegie-Mellon Univ., 1975.

/4/ HINTEREGGER, J.: Ein verbessertes Ver­ fahren zur Feststellung der Isomorphie endlicher Graphen; Dissertation, Inns­ bruck 1976.

/5/ KADEN, F.: Zur Formalisierung induk­ tiver Schlusse uber strukturierten Objek­ ten ; ZKI-Informationen 3/80, Akademie der Wissenschaften der DDR, 1980

/6/ McCARTHY, J.: A basis for a mathema­ tical theory of computation; In Computer Pr og ramming and Formal Systems (P. BRAF­ FORD , D. HIRSHBERG, Eds.), Amsterdam 1963.

/7/ MICHALSKY, R. S.: Toward computer­

ai ded induction: a brief review of cur­ rently implemented AQVAL programs; In Proc. IJCAI-5, 1977.

/8/ MITCHELL, T. M.: Version spaces: an approa ch to concept learning; Ph. D. thesis, STAN-CS-711, Stanford 1978.

/9/ MITCHELL, T. M.: Analysis of ge neral ­ ization as a search problem; In Proc. IJCAI-6, 1979.

/10/ PLOTKIN, G. D.: A note on inductive gene ralization; In Machine Int el ligenc e 5 (B. MELTZER and D. MICHIE, Eds.), Ed in­ burgh 1970 .

/11/ SOBIK, F.; SOMMERFELD, E.: The pro­ gram CALG for classification of struc­ tured objects; Proc. 2 Int. Meeting on Artificial Intelligence, Leningrad-Repine , 1980 (to be published).

/12/ UNGER, S .; WYSOTZKI, F.: Lernfahige Klassifizierungssysteme; Akademie-Verlag Berlin 1981.

/13/ VERE, s. A.: Induction of concepts in the predicate calculus; In Prot. IJCAI-4, 1975.

/14/ WINSTON, P. H.: Learning structural descriptions from examples; Ph. D. thesis, MAC TR-76, Cambridge 1970.