Concept Decomposition as a Method of Concept Formation

CON CEPT DECO~POSITION AS A METHOD OF CONCEPT FORMATION

ComPuter S c i e n'c e Department , U n i v e r s i t y o f Sou t h we s t ern Lou i s i an a

Edwin Towster Lafayette, Louisiana 70504

Conc e Pt formaticn is a simple form of i nd uctive inference over a small set of attri butes known in advance [2]. The at tri butes are sufficient to describe all ob jects in some univers e of interest. A concept can be re garced as a function that partitions these objects into two categories, the "positive instances" and the "negative instances" o f the concept. Concept · formation takes place when a concept is reconstructed from a training set of some of its positive and negative instances. We have coded a concept formation algorithm using a method of functional decomposition [1]. Our approach operates under the philosophy that the attributes of a concept formation prob lem carry information that suffices to identify the instance classifications ("positive" or "negative") and that all add itional i nformation c~rried by the attributes is to oe consider.ed "excess information". The excess information carried by any subset of attributes can be detected by forming a decomposition table with rows based en the subset of attri butes and cclumns based on the remaining attributes. The excess information can then be removed by re-ceding the old attributes in the subset into new attributes that d istinguish only concept information.

Re-ceding also transforms the problem into a new problem of smaller size, by reducing the number cf instances and by d iscar d in g attributes that become irrelevant after re-ceding. Eventually the problem is reduced to a single attribute containing only conc~pt information. This attri bute must then be the concept itself or its complement. In either case, the discovered concept can then be described in terms of the ori g inal attributes by working backwards through the co de transformations that have occurred. In ductive inference can take place because the decomposition tables operate successfully even when many instance classifications are unknown. The prob ability of error is reduced, and the total processing time is also reduced, if the subset of given attributes under examination is kept as small as possible during each iteration.

The r~-coding of the attributes in the subset is expressed as a definition of each new attribute ir terms of the ol d attributes of the subset. These definitions describe ~parts~ that are relevant to the concept solution.

Figure 1 (dashed lin!"> shows a learning curve when this method of concept formation is applied to the concept of ~parity~ for eight binary attributes. This problem is difficult in a sense defined in [3]. The diagonal line in the figure shows the ~guess curve~ that would be obtained by a concept former that correctly learns all of the instances in the training set and randomly guesses at the remaining instance classifications. Each ~part" pro duced during the solution of the parity problem on eight attributes defines a single new attribute as the parity function for two old attributes.

Figure 1 <solid line) shows a learning curve for a "compare" concept of seven attributes. The integer represente d by the first three (binary) attributes is compared with the integer represented by the last three (binary) attributes. Comparison is according to the remaining <ternary) attribut~, which takes the values ~c", "=", and ">". Some of the "parts" produced for the "compare" problem express comparison relationships between individual digits of the integers. These relationships are discovered as a normal by-product of concept decomposition.

REfERENCES

1. Ashenhurst, R.L. "The Decomposition of Switching Functions", in The Annals of the Computation Laboratory of Harvard University, Vol. 29, Harvard Univ. Press, 1959.
2. Hunt, E.a., Marin, J., and Stone, P.J. ~~Q~tim~o1~ io logu~1igo, Academic Press, New York, 1966.
3. Minsky, M. and Papert, S. f~C,~Q1CQQ~, MIT Press, 1969.