--- title: "Learning of Abstractions from Structural Descriptions of Pictures" authors: - "Pierre E. Bonzon" doi: "" url: "https://ijcai.org/proceedings/1979/22" pdf: "https://ijcai.org/proceedings/1979/0022.pdf" venue: "Proceedings of the Sixth International Joint Conference on Artificial Intelligence" year: 1979 pages: "" track: "" keywords: --- # Learning of Abstractions from Structural Descriptions of Pictures Pierre E. Bonzon *Proceedings of the Sixth International Joint Conference on Artificial Intelligence*. ## Abstract The acquisition of concepts induced by structural descriptions of pictures is discussed and a representation scheme is presented which allows the construction of various abstractions based on different points of views and their storage in a simulated associative memory. ## Full text ## ABSTRACT The acquisition of concepts induced by structural descriptions of pictures is discussed and a representation scheme is presented which allows the construction of various abstractions based on different points of views and their storage in a simulated associative memory. ## INTRODUCTION In order to introduce the material contained in this paper, we will follow the views and termi­ nology used by Hayes-Roth and McDermott in their recent war~ /1/, /2/ : "Concepts are pattern temptates 1 events which match a concept are recognized as belonging to the class delimited by that concept, (,,,) The machine learning problem with which we are con­ cerned can be stated in the following way : gi­ ven a collection of concepts (,,,) and a way of describing events in terms of their structu­ re, construct a machine which is able to indu­ ce additional concepts (,,,) from training da­ ta, " (/1/, p, 156) From there, they identify three distinct pro­ blems 1 - ll the description problem, as~ing for a "formal scheme for describing complex events ·which facilitates the generation of abstrac­ tions" - 2) the comparison problem, i.e, the problem of finding commonalities between two examples of the same concept or abstraction - 3) the storage problem, i.e, the problem of storing discovered abstractions in such a way that tney could be used as temptates for recognition of events, and as ~nowledge re­ presentations to be improved by learning, learning being viewed here "as a continual process of ~nowledge expansion, that is, as the acquisition, in adaption to training ex­ periences, of higher-order, more complex and more elaborate ~nowledge structures", We propose in this paper a different solution to each of these problems, our approach being moti­ vated by a rather divergent view on the moda l i­ ties of ~nowledge expansion, ## TWO POSSIBLE APPROACHES FOR KNOWLEDGE EXPANSION The approach ta~en by Hayes-Roth and McDermott is, in their own wording, to improve the preci­ sion of the ~nowledge representations by lear­ ning, if new instances of the same concept are provided, More precisely, according to the ex­ ample they give, they first construct an initial (actually too narrow) concept by listing all common properties of two selected events, and then refine it (actually extend it) by removing some commonalities not found in a third event, and so on : this amount to first retaining all constituents as potential properties of a con­ cept and then gradually discarding some of them. The matching involved in recognition is then a partial matching, On the other hand, the approach we have ta~en consists of isolating first basic con~tituents, and classifying them according to various points of views, thus defining basic concepts in diffe­ rent contextsJ a global concept is then construc­ ted by combining basic concepts into more elabo­ rate, higher-order concepts, and so on, until gradually all constituents have been ta~en into account : the matching involved is thus a ~ plate matching, dissimilarities being removed by means of equivalence classes, or subconcepts, A consequence of our approach is that learning cannot be considered as an autonomous process, but must necessarily interfere with a complemen­ tary tutoring process, providing the frame for ## LEARNING OF ABSTRACTIONS FROM STRUCTURAL DESCRIPTIONS OF PICTURES P. BONZON - University of Lausanne - Switzerland the differentiation of contexts, classification of constituents and the naming of concepts. This will be first illustrated by means of a simple example of a teaching session conducted on our interactive graphic system. ## Example 1 In a first step, the teacher will be asked to draw simple connected patterns (i.e. basic cons­ tituents), and to provide the appropriate names for equivalence classes, thus defining basic concepts by extension: ![Image](https://ijcai.org/proceedings/1979/fulltext/22/image_000000_af8045637d5736f5b354b925f057da6be9fe47091c42d833ba10aa9445d95d5a.png) In a second step, he can draw pictures with more complex structures (i.e. single or multiple events, or instances of higher-order concepts), together with concept names; ![Image](https://ijcai.org/proceedings/1979/fulltext/22/image_000001_e176caf1bc1e5f9ad75b6a48fd3ded2ce010d01c3cef8e81ca3ecbf1473b4c8c.png) A definition by generalization of the correspon­ ding concepts will be constructed by substitu­ ting basic concept names for occurences of sim­ ple connected patterns (first level of abstrac­ tion). To verify that these concepts have been learned, the teacher can then draw pictures, as­ king for recognition: ![Image](https://ijcai.org/proceedings/1979/fulltext/22/image_000002_f6ad2b8a7f65f1c0c61952be990fc228850afd8f40d50f194bd0e06929f8b4c6.png) The learning process could go on in two diffe­ rent directions 1 - first by drawing more and more complex pictu­ res, for example introducing body configura­ tions with heads, arms and legs, leading to higher levels of abstraction - secondly by defining alternate basic concepts (i.e. different equivalence classes of the same patterns) for analyzing the same pictu­ res, thus implicitely refering to another context or frame of intentionality and achie­ ving various levels of differential abstrac­ tion ![Image](https://ijcai.org/proceedings/1979/fulltext/22/image_000003_28bb8414869a9b17c6106c92c1f1c1ec428e3e5baa6c99fff40e528e0ce18b78.png) The solutions to the three problems mentionned above will be now reviewed in detail. ## THE DESCRIPTION PROBLEM The interface between the teacher (human opera­ tor) and the learning system (computer program) is a graphic tablet together with a display. A fairly complex software analyzes line drawings and identifies simple connected patterns such as those presented in the above examples. This pri­ mary capability of the learning system could be viewed as a pure sensorial perception. In order to obtain a satisfactory structural description, a few more primitive perceptual capabilities are required. Our present (rather incomplete) system allows for the determination of the relative po­ sition of simple connected patterns using the three binary relations ABOVE, LEFT, and SURROUND. The structural description resulting from this perception is given in the form of a binary tree, the perceptual tree, where basic concept names have been substituted for any of their instances (i.e. a first level of abstraction has been per­ formed) ![Image](https://ijcai.org/proceedings/1979/fulltext/22/image_000004_4d139c906053f9fa1f84b38ad65e96ccc65f676fa189ae6901be91bac6ce63fe.png) It is noteworthy that this description.in con­ trast to that in /1/, is not parameterized, the identification of each constituent being taken into account by its position in the binary tree. ## THE STORAGE PROBLEM The solution to the storage problem, which in Hayes-Roth and McDermott terminology refers to the way of representing abstractions or concepts, will be presented n~xt to allow for an easy treatment of the comparison problem. The purpose of classifying constituents into multiple equivalence classes, is to allow for the recognition of events in various contexts, A workable knowledge representation can thus be obtained by a mere reshaping of perceptual trees, grouping multiple concept definitions based on the same point of view into a ternary tree, each such tree representing a context. More precisely, each perceptual tree is first rewritten as a list in postfix order, and then imbedded in a binary search tree where leading common sublists are factorized (or shared) for economical memory storage and quick access, The appropriate concept name is then attached to the queue of each list in a so-called naming node. The resulting structure forms a context tree. Leading sublists can be used to define subcon­ cepts by inserting naming nodes, which have then to be jumped over. ![Image](https://ijcai.org/proceedings/1979/fulltext/22/image_000005_bb9f5c8b593637bda6e892f42b0ecf91c1a96c22c75b0bcc7d57566a1f47db9d.png) ## THE COMPARISON PROBLEM With the type of knowledge representation just described, finding commonalities and recognizing events becomes equivalent to retrieving, in con­ text trees, concepts whose definitions match subtrees of perceptual trees. More precisely, recognition of a event given by its perceptual tree will be conducted by succes­ sive reductions : each subtree (of a given per­ ceptual tree) matching a concept's definition will be replaced by the name of that concept; if the perceptual tree eventually reduces to a uni ­ que naming node, a global concept will thus be identified. Knowledge expansion, on the other hand, is achie­ ved by the insertion in postfix order, into ap­ propriate context trees, of reduced, but unre­ cognized, perceptual trees. The reduction algorithm itself consists of three imbedded recursive procedures : the most inner procedure is the classical recursive version of binary search with insertion using a sentinel, modified to jump over naming nodes; the second inner procedure traverses subtrees of perceptual trees in postfix order, each node being in turn searched for at a given level in a context tree: this amounts to attempting a partial match on subtrees; the outer pro·cedure traverses percep­ tual trees in postfix order, attempting a par­ tial match at each node, i.e. on each subtree. ## EXPERIMENTS PERFORMED WITH THE SYSTEM This system has been used primarly in an experi­ ment involving the learning of chinese charac­ ters /3/. The range of candidates (a subset of 70 characters based on SO basic patterns have been selected) was imp:osed by the limited percep­ tual power of the system. On a configuration involving a CDC CYBER 73 com­ puter, a character abstraction or recognition takes from less to 0,1 to 0,5 sec depending on the character's complexity. ## References 1. // Hayes-Roth, F,, and McDermott, J., Knowled - ge Acquisition from Structural Descriptions, Proc, 5th IJCAI, 1 (19771, 356-382 / 2. / Hayes-Roth, F., and McDermott, J., An Inter- ference Matching Technique for Inducing Abstractions, CACM 21,5 (May 1978), 401- 410 / 3. / Tran Van Nam, Syntactic Pattern Recogni- tion, A General System for Description of Handprinted Text Written on a Graphic Ta- blet, PH,D Thesis, Swiss Fad, Inst. of Techn, (EPFL Lausanne 1978)