Discovering Classification Rules Using variable-Valued Logic System VL1

Introduction

Paper 1 introduced a concept of a variable- valued logic (VL) system and defined a particular VL system called VL 1 . One of the basic assumptions underlying the con cept of a VL system is that every proposition (called a VL formula) and all the variables in the p r oposition (used to represent any objects , e. g ., other propositions) are allowed to accept their own nwnber of trut h- values which are p r oblem- and semantics- dependent . From the viewpoint of formal logic , the concept of a VL system is an extension of the concept of a many -valued logic system.

One of the applications of the VL 1 system is that it can be used as an inductive system which when supplied with 'numerical names ' of objects , their attributes, relations between the objects or their pa rts , etc . , can infer a description of objects or object classes , which is simplest in a well- defined sense , and also which is a generalization of the input information .

Important features of VL 1 are that the formulas of the system have very simple interpretation and can be very easily handled and evaluated by a general purpose computer (and , as well , by a human) , especially using parallel or parallel - sequential techniques . Also , the system is well suited for classification problems which are intrinsically nonlinear .

The paper presents a set- theoretic definition of the classification problem and then discusses an appl icat ion of the system VL 1 to the synt hesis of minimal classi f ication rules under various cost functionals . Two examples are given .

Statement of the Classification Problem

Let (1 denote a non- empty set of physical o r abstract objects , called the universe of objects . Let R denote a finite non - empty ( f.n . ) set , called the un i ve rse of represent ations of the object s o t ~. Let K denote a f.n . set of subsets of (1, called the family o f object classes :

K . E 2~ are called object classes and J are specified as :

Accepting notation:

Thus , for each object o E (1 there exists at least one object class containing it . Index j of class K . is called the numerical name of K . . The set J inde~ing classes K . : J J

is called the family of numerical class ~·

In general , t he index j can assume not only num­ erical values but non - numerical names given to classes Kj , and then J is called the family of class ~·

As an example , consider the unive r se of objects , ¢, to be a group of peopl e . The unive r se of represen­ tations , R, can be , e . g., a set of pictures or voice records of these people ; a set of their fingerprints ; numerical data describing thei r height , sex , hair color, medical test results , and so on ; a set of statements characterizing each individual , and , also , a set ­ theoretical sum of any two or more of the previ ous sets. The family of class names , J, can be , e . g ., the set of the names of people in the group or a set of lists with names of those who a r e short with blue eyes , fat or bald , have M. Sc . or Ph . D. degrees , etc . (In the second example , sets of class n ames may not be disjoint . Though the usual tendency is to classify objects into disjoint cl asses , the case of not- disjoint classes is also , in general , of interest . )

Let:

• T denote a r elation between ~ and 1', called the r eferen ce r elation : *

• p denote a relation between P and R , called the representation relation :

• oc: denote a r elation between R and J, called the cl assifi cation relation :

In the p r esent paper we will restrict our selves only to the case where K consists of di sjoint sets and T and IC are funct i ons :

(that is , there exists only one class r elated to any

* By i : S 1 - s 2 , where s 1 and S are sets , is meant that .Q. is a relatlon between sl an~ s2 (that is , . .Q. =<S ,S , GR.> , G ~ s 1 xS ) . Ana. by i(s ) , s E S , ls rreant t~e set o1- elements from s 2 which a r e ret ate d by R. to s .

object and any representation). Figure 1 presents schematically relations T , p, and K.

If t is a relation between sets B 1 and S 2 :

then by Ex(t) we denote an expression for t , which is a formula consisting of variables (whose values depend on elerrents of S 1 ) , and different operations (e . g., logical , arithrre'Eic, control), such that for any s E s 1 , Ex(t) computes elements of s 2 related by relatJ.on t to element s .

Suppose that for semantical restrictions (e.g., because a mathematical formula cannot deal directly with physical objects) or practical reasons (e.g., because sets ¢ and/ or R are too large) it is not feasible to specify relations i: and p completely and to determine expressions for them. Suppose , however , that T and p are specified for some subsets ¢ ,; ~ and R ~ R such that ¢ is the union of non- empty disjoint sets ¢ 1 , ¢ 2 , ... , ¢m:

and R is the union of non- empty disjoint sets Rl , R2 '' ·· ' Rm:

such that for every o E ¢ . , there i s in R . at least onerE p (o) . LetT and g denote restrictions of 't and p :

Set R is called a disjoint representation of the set¢. If it is not req_uired that sets R. must be disjoint (for a certain R there may not e'1cist a dis ­ joint representation of¢) , then R is called a non­ disjoint representation of ¢ .

A non-disjoint representation does not allow to cl assify objects without error . In such a case the following approaches can be taken :

l . Evaluate probability densities f (r) of object with representation r being from cl~s K ., j =l ,2 , ... ,m and then construct decision rules which ,Je . g., give the minimum expected error (such methods are studied in statistical pattern recognition 2 ' 3 ) ·

2 . Extend the universe of representations R, or seek a new R such that it will provide a disjoint represen­ tation . (A general tendency here should be to seek an R such that sets R . are not only dis joint but form in R ' cl usters '--one ~r mo r e per class . ) Such a repre ­ sentation R is ~led---compact or clustered.

In the paper we are concerned only with the second approach and, therefore , statistical methods will not be considered.

Let K denote a function:

such that the .composite relation p o K is eq_ual to T:

Note that in order to satisfy (17) , function K has to have appropriate values only for elements of R f R, and, therefore, there can be many functions of type

(16) which satisfy (17) . Each of them has the property that p o K is eq_ual to T for objects o E f/ , and for objects o ~ ¢ may or may not be eq_ual to T.

Definition: An expression Ex(K) is called a classifi­ cation rule for the set ¢ based on R into J, or briefly, a classification rule cfl0 , R~.

Some of the types of problems which arise are:

l. How , given T and p , to determine a classification rule C((J, R, J ) which (a) involves operations from some specified set, (b) is minimal under an assurred cost functional, or, generally, satisfies certain criteria.

2 . How , given a classification rule c(¢, R , J ) , to estimate its performance for objects o ~ ¢ and/or representations r ~ R (assuming that T can be specified for some additional objects).

3. How, given T and p, to determine a set of opera­ tions , such that classification rules involving all or some of these operations can be made very simple (in a specified sense) .

4. How, given(} and T, to specify a universe R which will provide a disjoint (or clustered) representation and will permit construction of very simple classifica­ tion rules .

In the paper, we consider a problem of type l, where the universe of representations R is assumed to be a set of vectors with discrete components , and classification rules are formulas of a variable- valued logic system VL 1 . Also, on the basis of a concrete example , we discuss a problem of type 4.

The Variable - Valued Logic System VL 1

Definition of VL 1

The variable- valued logic system, VL 1 , which will be used here to construct classification rules, was introduced in papel. For completeness we will include here its formal definition (slightly modified) .

The variable- valued logic system VL 1 is an ordered q_uintuple:

where

X is a f.n . set of input variables

whose domains, called input or independent ~ sets, are f . n . sets , respectively:

where Hi = {0 , 1,2 , ... ,)\i}' i =l,2, ... ,n , Ili --a natural number .

Y consists of one output variable y , whose domain is a f.n. set called output or dependent ~set:

(Constants in H represent truth- values which may be taken by statements (formulas) in the system.)

S is the set of ll improper symbols:

RF is a set of formation or syntactic rules which define well-formed formulas ( wffs) in the system ( VL 1 formulas ) :

1. A primitive constant from H standing alone is a wff .

2 . A form [xi#cl, where i dl , 2 , ... , n} , # d =,i } , c--a sequence of elements of H. separated by 1 , 1 or 1 : 1 and ordered by relation <,lis a wff.

3. If V, V 1 and V 2 are wffs or names* of VL 1 formulas, then (V), .., (v), \1\ v 2 (written also as v 1 v 2 ) , v 1 v v 2 are also wffs.

4. If v 1 is a wff or a name* of a VL 1 formula or a single variable x. and v 2 is a wff or a name* of a VL 1 formula or sequen~e c or its name* than [V 1 #V 2 ), # d =,i } , is also a wff .

Forms the former the simple of x .. [x. #c) and [V 1 #V ) are called selectors; fofm is also cal fed a simple selector . In selector [xi#c), c is called the reference l

If 1 # 1 is 1 = 1 then the r eference is called inclusive ; otherwise , exclusive . The reference is said to be in extended form and called an extended reference if all the constants in it are separated only by 1 , 1 · The reference is said to be in compressed form and called a compressed reference if in the extended reference, every maximal (under inclusion) sequence of consecutive constants of length at least three is replaced by a form 1 c 1 : c 2 1 where c 1 , c 2 are the first and last constants of The sequence , respectively.

RI is a set of interpretation rules which assign to any wff V a value v{V}E H, depending on values of the variables x 1 , x 2 , ... , xn :

1 . The value v{c} of a constant c, c E H, is c , which is denoted v{c} = c.

where x.=c (x. ic ) is satisfied if the value of the variabl~ x. i~ (is not) one of the elements in the sequence c7 If two elements in c are separated by 1 : 1 , then the relation is also satisfied if the value of x. is (is not) between the above two elements . The sele~tor [x.#c) is said to be satisfied if x.#c. l l

where the meaning of # and the definition of a selector being satisfied is the same as in 2 .

V V V is called the sum (or disjunction) of vl ana v2 . 2

*. Thi~ is an ~ddi tion to the previous definition gl ven ln paper .

7 . In the evaluation of a VL 1 formula , 1\ has higher priority than V

8. Parenthesis ) have their usual meaning , i.e., they denote a part of a formula which is to be evaluated as a whole.

The following is an example of a VL 1 formula and its interpretation:

The formula ( 19) is assigned the value 4 (briefly , has value 4) if x 1 accepts value between (inclusively) a-­ and 4 , or value 7; and x 2 accepts value which is neither 0 nor 5 . The formula has value 2 if the p revious condition does not hold and x 3 accepts value 0 . The formula has value 1 i f both of the previous conditions do not hold and x 5 accepts value between 0 and 4 . If none of the above conditions hold , the formuJ.a has value 0 .

Event Space as a Universe of Representations

The interpretation r ules R assign to any VL 1 formula a value from the set H aepending on the values of variables x 1 , x , ... , x, taken from sets H 1 , H;:>, ... , H . Tflus , theninterpretation rules interpret VL 1 !formulas as expressions of a function:

The functions of the type (20) are called VL funct i ons . The set H 1 xH 2 x ... xH, H.={O ,l, ... ,)l. } ,i=l,2 , ... ,n, incl~des all possible sgquefices of valu~s of input variables and is called the universe of events or the event space . The event space is denoted by E(h 1 , h 2 , ... , h ),where* h . = c(H.) = 11 . + 1, or , briefly , by E. nThe functi6n f inl( 20) ~an then be denoted as:

The elements of an event space E, vectors ( ~,~ ·· . . , xn), where ti is a value of the variable xi; :ici c H., are called events and denoted by ej , j = 0 ,1,2 , ..· j , wh~re ~ = h-1, h = c(E) = h 1 h 2 ... hn. Thus , we can wrlte:

It is assumed that values of the index by a one - to- one function: are given

specified by the expression:

y(e) is called the number of the event e . the number of the event e ;-c2-;3,~in E(5 , 4 ,2 , 5) is: For example , the space

Assuming that the domainS' of variables in the formula (19) have cardinalities : c(H 1 ) = 8, c(H 2 ) = 6,

* c(S), where S is a set, denotes the cardinality of S.

c(H) = 2, c(H 4 ) = 2, c(H) 5 and the cardinality of~. c(H) = 5, the formuia is interpreted as an expression of a function:

In order to use VL 1 formulas as classification rules, the representations of objects should be in the form of vectors )'hose components are discrete varia­ bles. Thus, if some variables used to characterize objects are continuous, their ranges of variabilities should be resolved into dis crete units . The nwnber of these units should be selected as the minimum which provides sufficient accuracy (to facilitate computa­ tions) and can be different for each variable .

Minimal VL 1 Formulas

In general, there can be a large nwnber of VL formulas which express a given VL function . Theretore, a problem arises of how to construct a formula , which is minimal under an assumed cost (or optimality) functional.

Cost functionals are usually stated as a linear function of certain parameters multiplied by weights being real numbers. Such functionals can, however, be inconvenient from the computational, and, as well, the application viewpoint (they require multiplication and addition operations, which can be a disadvantage when a large set is searched, and it is often difficult to state weights which reflect well the intuition, usually guiding a designer of the functional). There­ fore, in program AQVAL/1 (see next section) a func ­ tional A measuring minimality of VL 1 formulas was assumed to be in a different form, namely:

where: a - list, called attribute list, is a vector a= (a 1 ,~, ·.. ,aR.)' where the a. denote single- or many- valued attnbutes used to ~haracterize DVL 1 formulas; T- list, called a tolerance list, is a vector T = (T 1 ,T 2 , ..· ,TR. )' where 0 <'t:· <1, i=l,2, ·.. , R- , and the T. are called tolerance§ for attributes a . . 1 -- 1

A DVL 1 formula V is said t o be a minimal DVL 1 expression for f under functional A iff :

a.(V),a . (V.) denote the val ue of the attribute a. 1 1

fBr formula V and V. , respectively Vj, j=i,2,3, ··. are all p5ssible irredundan~DVL 1 , expressions for f

~ denotes a relation called the lexicographic order with tolerance T , defined as ----

or ..·..··...

or . . . . . . . . . . . .. · · . . . . . and al!. (Vj ) - al!. (v);> Tl!.

Note that if T = (0,0, ... ,0), then <::denotes the lexicographic order in the usual sense . In this case, A will be specified just as A= <a- list>. The · - list allow:s: a designer to 'soften' the rigid attribute priorities assumed in the a - list .

To specify a functional A one selects a set of attributes, puts them in the desirable priority order in the a- list, and sets values for tolerances in the T- list. Thus, the functional is very simple to f o rmu­ late, as well as t o evaluate, and also it seems t o be well fitted to human intuition in many applications .

AQVAL/1

A PL/1 program, called* AQVAL/1, has been developed at the University of Illinois for the synthesis and minimization of VL 1 formulas . It is a complex program and its descript1on and theoretical background goes beyond the scope of the present paper. 5

AQVAL/1 accepts the specification of the VL function (whose VL 1 expression is to be synthesized and minimized) in one of the three forms:

2 . By sets similar t o those in 1, but with events specified not as sequences of input variables, but by tgeir numbers (24), i.e., values y(e) :

3. By a disjunctive s i mple VL 1 f ormula** (DVL 1 ) expressing f (in this case the program is supposed to simplify according to the assumed functional, if possible, the given DVL 1 ).

As a result, AQVAL/1 produces a quasi - minimal DVL 1 f ormula (which is minimal or approximately minima]) under a functional A (26) , where attributes a. in the a - list can be chosen from seven presently implemented attributes. Among them there are attributes such as:

1. t(V) - the number of terms in V,

z ( x. ) is the cost (specified in the i nput dat a ) of detil!rmining the value of variable x. ; and variables x. , i£1, are those, among all x 1 ,~· ·· .i specified in thil! input data, which actually appear innthe output VL 1 f ormula.

4. g(V) -the ' degree of generalization' defined as:

• The name AQVAL/1 was derived from 'Algorithm A~ applied for the synthesis of Variable - Valued Logic formulas' . The algorithm Aq which provides a-very 4 simple and efficient s olution to covering problems · 5 has been used as the basis f or VL 1 formula synthesis .
• ** A DVL 1 f ormula is a sum of simple terms,where a simple term is a product of a constant (from H) and one or more simple selectors .

L --the set of events which satisf'y* the J!, - th term in K the sequence of terms in V with the constant k

(This attribute was designed to capture the 'size ' of generalization resulting from the formula. as compared to 'true facts '--events specified in the lnput data.)

VL Formulas as Classification Rules (Examples) -1

In this chapter we illustrate, by two examples , an application of the VL system to the synthesis of classification rules. 1 The examples are very simple; their purpose is to provide an insight into the principles, rather than to investigate the boundaries of application possibilities;

Example l

Suppose there is given a set of eight objects, as shown in Figure 2 , and it is known (relation T) that those denoted~ belong to the class with numerical name 1 (briefly-; class 1), and those denoted ~O to class 0 .

The probl em is to find the simplest (in some specified sense) rule , which characterizes objects of class 1 as opposed to objects of class 0 .

(To make the problem clearly understood, suppose that objects were.mixed up. The rule, which is to be found , could then be used to r estore the original classification with the minimum cost -- according to some cost functional.)

In order to apply the VL system to this problem, all objects should be describ~d by sequences of values of certain variables , that is , by events or event sets of some event space E(h ,h , ... ,h ) . Then the problem becomes that of finding 1 a ?1 exp~ession for a function l

such that f(e) = 0 ,1 fore £ R 0 , R 1 , r espectively, where:

0 ,1 - represent classes 0 and 1, respectively

R 0 ,R 1 - are event sets representing objects of ¢ 0 and ¢ 2 , respectively.

Suppose that some specialized procedures have been developed which can identify in the objects such com­ ponents as rectangles, triangles , trapezoids , circles, and ellipses .

A simple description of every object could then be by specifying how many times each s uch component appears in every object . Let us accept , as a first trial, this kind of description as object representa­ tions .

L t X be variables associated with e xl, x,_, , ... , 5 each component:

and let values of x. = i -1, 2 , ... , 5 , denote numbers of times a given compo~ent appears in an object. To be able to describe in this way any object in ¢ 1 and ¢ 0 ' it is sufficient to assume :

Thus, relating our probl em to the definitio~ of a classification rule, the event set E(2 , 3 ,2 , 3 ,2) lS considered as the univers'e of representations R, set ¢ U ¢ can be considered as P or¢) . Let r(¢ 0 ) and r{¢ ) ~enote sets of events which are descriptlons of obje~ts o £ ¢ and o £ ¢ , respectively. We have 0 1

r(¢ 0 )={ (0,1 ,1,2 ,o) ,(1,0,0,1,1), (1 , 1 , 0 ,2 ,o) , (o ,2 ,o ,2 ,1)

Event (1,1 , 0 ,2 , 0) appears in both r(¢ 0 ) and T(¢ 1 ). Since this is the only event representing object 3 in ¢ and ob,j ect 3 in ¢ , therefore , there does not exist a 0 disjoint representiti on R = R 0 U R 1 , R 0 n R 1 = <P · where R c. r(¢ ) and R 1 ~ r((.7 1 ) and each object of ¢ 0 and ¢ ga;;- at 2east one r epresentation in R 0 and R 1 , respe~ti vely .

Consequently, there does not exist a classifica­ tion rule based on R whi·ch can distinguish between object 3 in 1/ 0 and object 3 in ¢ 1 .

To avoid misclassification, let us introduce a new object class called undecidable object class and give the numerical name 2 to it . This class can be charac­ ter ized as : 'a class of objects which are equivalent in the universe of representations' . Let R 0 , R 1 , and R denote event sets: R = r(l/ 0 )"{e* } , JS. = r(¢ 1 )'\.{e*} , R 2 = {ell} where e * = (1,1,0, 2 , 0).

Figure 3 presents the GLD* representation of the space E(2 , 3 , 2 , 3 , 2) and sets R 0 , R 1 , and R 2 . Cells in the diagram which correspond to events of R 0 , R 1 , and R are marked by 0 ,1,2 , respectively. The Cliagram is s~lf-explanato?{ ; for the formal definition of GLD and details consult .

Let f be a function

such that f(e) = 0,1 , 2 fore£ R 0 , R 1 , R 2 , r espectively (i.e., fore f R U R U R 2 the value of f is not restricted) . Le~ us aetermine a classification rule for¢ U ¢ based on R into .J = {0 ,1,2} as a VL 1 formu:l:a ex£ressing f, briefly , a VL 1 expre~sion for f. A VL expression for f minimal under functlonal: 1

where t - number of terms , z - number of different variables s - number of selectors 1 (that is, an expres­ sion which has the minimum number of terms , the minimum number of different variables for that number of terms, and the minimum number of selectors for that number of terms and variables) determined using the GLD representation of the function f , is:

Figure 3 shows the sets of cells which correspond to terms of the formula . The formula gives a rule: If an object has one rectangle and one triangle , then it belongs to undecidable class ; if it has 0 or 2 triangles and 0 ellipses , or 1 triangle and 1 ellipse , then it belon s to class 1· if none of the revious conditions holds, then it belongs to class 0 . Note that the formula involves only three variables x 1 , x 2 , and x'i out of five, i.e ., requires :rreasuring only the numbe1' of rectangles , triangles, and ellipses.) The formula has a disadvantage that it cannot classify correctly all objects and also seems to be rather complicate d.

* 'GLD ' stands f or Generalized Logic Diagram7 which is a planar model · of a ;pace E(hl'. :-. ,hn ) --;-

Let us now try to extend the universe of representations to obtain a disjoint representation of objects. An obvious way to do so seems to also include in the object descriptions information about spacial relationships between object parts. Suppose that the specialized procedures not only can na:rre the object parts , but also can determine binary relations such as 'on the left of ', 'contains ' , ' on top of ' between adjacent object components. New variables have, therefore , to be introduced. Let x 6 , x 7 , and x 8 be variables such that: ~ and x 7 represent ~he left and right ele:rrents (object components), respectively, in a binary relation which relates any two adjacent components . Their domains , H 6 and H 7 , are sets of numerical na:rres of all object components which can be distinguished and uniquely named in any object: H 6 = H 7 = {0,1, ... , 7}, where 0 represents a rectangle, 1 - a triangle or a left triangle if there are two triangles , 2 - a right triangle if there are two triangles, 3 - a trapezoid, 4 - a circle , 5 - a left or upper circle if there are two circles, 6 - the right or lower circle if there are two circles, 7 - an ellipse; ~represents binary relations between the values. of x 6 and x.., if these values are names of adjacent component~ in an object . Its domain , H 8 , cqnsists of numerical names of those relations (from a universe of relations which specialized procedures can detect) , which actually appear between adjacent components in any object: H = {O,l ,2,3}1 where 0 represents 'none of the rela~ions holds ', 1 - 'on the left of ' , 2 - 'contains' , 3 - 'on top of ' .

Let us see if there exists a disjoint representa­ tion of the objects, if they are represented ~by relations which exist between object components , that is, by vectors (x 6 ,~ , x 8 ), xh t H 6 , x £ H , and i 8 £ H 8 . These vectors can 15e treate~ as Jvents of tlie space ~(8,8,4) . We have ·:

The table show9 that events* of set E = { e3::> ,e4l,e63 ,elb3,el85} (see right side of the table) appear in both sets r(¢ 0 ) and r(¢ 1 ) . However , as opposed to the previous situation, each object has now more than one representation . Therefore , by removing events of E from r(¢ 0 ) and r(¢ ) , we can obtain a disjoint representahon: R = E 1 U R 0 where

To find a classif_ication rule (for¢ U ¢ 0 based on R into J = { 0 ,1}) , we have to determine an expression for a function :

such that f(e) = 0 ,1 if e £ R 0 , R 1 , respectively .

The VL 1 expression for f , minimal under the functional:

* Recall that j in eJ is the event number y(e) as defined by (24) .

where t - number of terms, and g - the degree of generalization ( 30) , found using the GLD representation of f, is:

Assuming the functional <t,g> means that we want to minimize the number of 'rules' which are needed to classify objects (terms in a formula), and also , with secondary priority, we require a minimal 'degree of generalization ' resulting from these rules).

It can be observed in Table 1 that the event e = (2,3,3), which is the only event which satisfies the second term of (38), can be removed from r(~ 1 ) and the resulting representation R will still be a disjoint representation of objects. Therefore, the formula:

(which is the also a classification rule .

Comparing ( 38) and ( 39) we can say that ( 38) , though more complicated (in sense of functional <t>), gives additional information , which , if appropriately used, may speed up the classification process .

Let us now assume as a cost functional the functional:

where s is the number of selectors and z the number of different variables . Assuming this functional means that we want to obtain possibly simply description (in the sense of <t,s , z>) while permitting a greater generalization which may arise from it . Two minimal VL 1 expressions for f under <t , s , z> (assuming that does not include the event (2 , 3 , 3)) exist:

(41) gives a rule: (since x 6 was of two) circles to class 0. 2 gives a similar rule: if , in a given object , there are two circles not contained in anything, then it belongs to class 1 , otherwise to class 0.

Considering all of the above formal l y found rules, it seems that they are close to what a human intuition could support as classification rules . Also, comparing (38,39) with (41,42) , it seems that the measure of the 'degree of generalization ' , specified by g, is relevant.

Since the obtained rules classify all objects correctly , there is no need to consider descriptions which use all eight variables .

Example 2

Figure 4 shows two sets of small 'pictures', R and R , which represent certain objects from two classes, 0 1 and 0, respectively . These 'pictures ' are gra~hical nota~ions of vectors (x 1 ~ , ... , x~), where var1. ables xi, 1.=1 ,2 , ... ,9 , correspond to p cture elements as shown below:

Domains of variables are H. = {0,1 ,2 , 3}. Elements of H. are graphically fepresented by different shaaows given to picture elements (as shown in the lower part of Figure 4) . Sets R 1 and R 0 are disjoint, thus , R = R 0 U R 1 is a disjoint representa­ tion of objects . The universe of representations is here E(4 , 4,4,4 ,4 , 4 , 4 , 4 , 4) or briefly E(4 t 9) .

The problem is to find a classification rule based on R into set {0 , 1}, which is the mini~l according to some assumed functional.

A classification rule based on R into { 0 , 1} is an expression for a function

such that f(e) = 0 , 1 fore £ R 0 , R 1 , r espectively . We will seek a classification rule by synthesizing a VL 1 expression for that function. As a cost functional let us assume the functional:

Program AQVAL/1 has been applied to this problem and produced the following quasi -minimal formula under the functional A:

[ x 2 r! l ][ x 5 =1 ,2 ][ x 6 r!o Hx 9 r! l] V

Figur e 5 shows a graphical representat ion of individual terms in ( 45) . · means that the cor­ responding variable (in order to satisfY the approp­ riate sel ector) should have value equal to 2 or 3; rn means that the variable should have value not equal to 0 ; * denotes i rrelevant var iables; the meaning of the other cells is anal ogous .

As we can see , the formula depends in toto on f i ve variables out 9_! nine . ·

It can be of int erest to compare this solution with results obtained by other approaches to the above problem.

The following four results were generously supplied by Mr. T. J. Mueller (result A) and Professor E. Gagliardo (results B, C, and D) of the University of Oregon .

A. Veto Logic Events e = (x · ~· · .. , x 9 )£ R 1 U R 0 are transl ate d into 28-component b~nary vectors y(e) = (yl,y2, ... ,y28) :

yly2y3 y4y5y6 .

Value s of x. are represented by sequences of values of three (bina}y) variables y.: ~

Variable y 28 is an additional variable; i ts value was set to 1.

Three weight vectors w 1 , w 2 , and w 3 were obtained to classifY events from R 1 and R 0 using 'veto' logic:

~ . 09119226 . 20518258 . 20797055 . 09119226 . 32965925 . 05887045 . 18238452 . 34197097 .07118216 -0 . 126 3020 4 -0 . 01231172 . 04390515 . 15958645 . 36476904 . 23076862 - 0.01231172 . 19287087 . 11229935 . 07622697 .19021729 . 24908774 . 07888054 . 17007280 . 15006271 . 21301535 . 30420761 . 22628967 - 1. 38314514

w2 . 00619241 - 0 . 31318312 - 0 . 14690878 - 0 . 11284473 .19284432 . 06243012 . 12295022 . 23401563 . 04876485 - 0 . 08035204 - 0 . 31748333 - 0 . 03525636 . 06682540 .02656893 . 02825318 - 0 . 01803480 . 21287293 . 17750369 - 0.21053121 - 0 . 25610102 . 4293359 4 - 0 . 23097723 - 0 . 33619246 - 0. 15 315 384 . 22063670 - 0 . 15504604 - 0 . 07623962 . 30564728

w3 . 03820991 - 0 . 26958540 - 0. 13027307 . 03551099 . 41790432 . 32208080 . 01177088 . 15927806 - 0 . 07017755 - 0.02458453 - 0 .13115018 . 09446748 . 21284891 . 08009393 . 06640317 . 139 312 34 . 40701055 .272055ll - 0 . 06775921 - 0.23897380 . 41658o97 . 02731614 - 0 . 07375359 . 01180357 . 09723179 - 0.07507694 . 01503365 - 0.50908121

An object , represented by vector y(e), is classified as a menfr:>er of class 1 if:

otherwise as a menfr:>er of class 0 .

B. Sequential Boolean Expression Events e £ R 1 U R 0 are represented in a similar way as in 'Veto Logic', except that variable y 28 is not used; that is , they are represented by vectors y(e) = (y 1 ,y 2 , . . . ,y 27 ) · The following result was obtained by human calculations (after a few hours of work) .

An object, represented by vector y(e), is classified as a member of: class 1 , if y 3 = 1, class 0 , if y iG = 0 where variable y 39 is gomputed from the follOWing Boolean equations.

C. Sequential Boolean Expression (Another Version) This result :B similar to one in B, except that it was obtained by a computer program.9 An object , represen­ t ed by ve ctor y(e), is classified as a member of: class 1 , if y = 1, class 0 , if y = 0 where variable y 39 is comput~a from the following3iloolean equations:

D. Sign- of-Polynomial Solution This result was also obtained by a computer program9 . It uses similar (as in the second and third examples) representation of events e by vectors y(e) = (y~ ,y 2 , ... ,y 27 ) , except that yi take values 1 and - 1 (instead of 1 and 0) .

• An object, represented by vector y(e) is classified as a member of: class 1 , if y 29 = - 1 , class 0 , if y 2 = l,where variable y 29 is computed from the folli!2ing expressions:

• It can be worth noting that results in all examples require measuring different numbers of original variables: all 9 variables , 6 variables , 8 variables, and 8 variables , respectively.

Concluding Remarks

1. Presented concepts and the classification method are of general applicability . They can be especially useful in solving deterministic classifi­ cation problems which are : --intrinsically nonlinear (e.g., when each class is represented by a number of independent 1 clusters 1 i n a representation space) or - -when variables are measured on nominal scale (i . e. , values of variables are labels ( 1 numerical names 1 ) of certain independent objects and , therefore , arithmetic relationships between these values have no meaning) or ordinal scale (only order of variable values has me~ing) . Thus , they can be applied beyond the area of applicability of conventional methods , such as linear (or nonlinear) discrimination techniques or statistical methods .
2. 2 . The method automatically detects and reduces redundant variables .
3. Classification rules in the form of VL 1 expressions are very easy to interpret by humans and at the same time very convenient to evaluate by computers (especially using parallel or parallel­ sequential techniques) .
4. 4 . Although the synthesis of minimal VL 1 expressions is a complex combinatorial problem, experimental results from program AQVAL/1 prove that the execution time and memory requirements in solving 1 average size 1 problems are quite acceptable .
5. 5 . It is also worth noting that the method can be extended to cover the case of not completely

specified events , i . e ., when some measurements are missing (what is a common situation in applications), and , also , that the classification rules (obtained based. on some given data) can be easily modified if new information is given which is contradictive to the rule.