Hypothesis of Simplicity in Pattern Recognition

HYPOTHESIS OF SIMPLlCITY IN

PA~TERN RECOGNITION

Zagoruyko N.G. & Samokhvalov K.F.

Laboratory of Pattern Recognition Institute of Mathematics Siberian Division USSR Academy of Sciences U.S.S.R.

ABSTRACT

This pa~er deals with the problem of constructing a general method for pattern recognition. It is proposed to realize this method based on a hypothe­ sis of simplicity which is formulated in an appropriate manner. The proposed method is illustrated with an example.

Introduct i on

In this paper the problem of pat­ tern recognition i.s considered as that of determining a method for predicting future empirical results based on in­ vestigation of only preliminary infor­ mation of an object and phenomena which are in previous experiments (in trai­ ning sam )le). Solution of the problem stated, in principle, depends on the acceptance of a natural-scientific hy­ pothesis that already has been mentioned in the literature (1). We assume th.,t such a natural-scientific hypothesis, in appropriate way, must explain the historical fact that mathematically simpler natural-scientific theories, as a rule, are more preferable as methods of predicting future experimental facts. The concern of this paper is how one can use the conception of simplicity fo­ rmulated only on intuitive level for the solution of pattern recognition problems.

§1. Training sample in given feature space

Let us define more exactly the no­ tions"feature"and "feature space". A:rry feature is determined wholly by a choice of empirical procedure for its measure­ ment. A measurement procedure is a compa­ rison of the measuring object with some set X of standards. The comparison is

determined by a finite set of empirical operations F:{/ 1 , . . · , f 1 } and empirical relations P= { p 1 , . . . , p,} on a set of sta­ ndards. Relative to these operations and relations the measuring object must be­ have in the same way as one of the stan­ dards. Let us introduce the following definition: the feature{.!} is a class of all algebraic systems isomorphic to that.T=<X; F; P >in which domain X is a set of standards, r and p are col­ lection of empirical operations and re­ lations on this set, correpondingly.

For example, the feature "weight" is a class of all algebraic systems isomorphic to that < W; 8 ; ...L.. ), where W is an accounting set of standards (wei­ ghts), operation E) is that of obtain­ ing any standard by putting together on a pan two different standards, relation

...L. is "not heavier than" (3).

Since an abstract class of algebra­ ic system is quite characterized by any of its representatives including a sys­ tem in which the domain is a set of num­ bers, operations and relations - suita­ ble numerical operations and relations, then one can describe, for instance, the feature "weight" as a class of all alge­ braic systems isomorphic to a numeric al one <N; +; 6:), where AI is a set of numbers, operation + is an arittmetical oneration of natural numbers, ad­ di ti.on, and the relation 6 is "not greater than". For all this, we ·nust not forget, however, that it is possible to consider the system < N; + ; £::: > as representation of the feature "weight" if and only if this system is isomor­ phic to the empirical one < W; <t>;.....:: ) ·

If it is known of some object 2 only that one can perform measurements of its feature {X } , then it is evi­ dent that thls object does not differ fr·om some standar:i ~~ which is an ele­ ment of domain X of the correspon­ ding algebraic system.

Let us choose this standard z~ · For ~ system isomorphic to that with the chosen ele:nent, X 1 = <x: :x 2 · F; P > is eqni valent to wri t'..ng: "the ob j e:::t 2 takes v::1lue !! 1 for feat ure {.l}". Given, for instance, th<.:t the object 2 weighs 2 kg, one can write as an algebraic sys­ tem isomorphic to that u;= <W. -'..~~ . Q;..L...), where the obj ect 2 kg belongs to the set \V of weight staniar·is .

i1ow, let us assume we are 3iven a fin i te set of featur;: s {1 ,},, {1} .. , {Jj corresponding to e~pirical ~ lr,ebraic -:ys :· e:~s

· e sh ·1ll na!:le e. cl '.'ss of all ~ lr;eb­ r :ic sys t ems iso·~ or~hic to ~n n-basic one (2) (It } .

.X = ' X { : ~ : P, : . ; X n. . Pn. > for an n'-di:nensional feature space {I 1 "JJ.

'!-e re, as in the one-limensional case, instead of an object with known values of n. fe nture s , one can consider a class of all sys~ems iso·:-,orphic to ( .'l l :J. - 1 X .x r P· r ... rp > 2 - \ , f ' f2 I f I f ' · ' ' f1 l ..A. f\ 2 t ' fl I fl

"'h·:: realizations set {J~} of a tra ininr;

sample of power M generates the same newer set of abstract classes of algeb­ ~aic systems {{ 1;;' J} , ~: !, ... , M It is called a training sample for ~ patterns if the set {{.t/'")hs broken up into ~ classes of equfvalence for the given feature space {:X 1 "'}.

§2. Scheme of general theory of recognition for the given feature space

~·he problem of recognition in gene­ ral can be formulated thus: the training sample represents the following ~ clas­ ses of equivalence: ·)

The 1-st class of equivalence:

The k-th class of equivalence:

Recognizing object y is given by the system

It is required, proceeding from the pro­ perties of algebraic systems of training sample and control realization ·r , to predict which of ~ classes of equivalen­ ce (patterns) system Jr 1 belongs to. As has been stated earlier, exclusively logical methods for this problem soluti­ on are not sufficient ones.

It is necessary to introduce an additional assumption which we postulate as the following many-stage process, considering it as an implicit formula­ t i on of the hypothesis of simnlicity.

·)Here and further, instead of an abst­ ract class of algebraic systems we mean any concrete representative of the class

At the first stage it is possible to consider the class of systems of equ­ al complexity corresponding to minimum permissible level of complexity which is determined as stated below. If it is not successful in obtainine a solution, then class of systems having the next higher level of complexity is considered, and so on ~til the first solution is ob­ tained. The choice of solution on each stage consists in th8 following: at first, systems which are homomorphous images of a system :X 11 are chosen from systems class of relevant comple­ xity. Let us denote the collection of such systems by Hom.!!,.

Realization ~ belongs to the i-th class of equivalence (pattern) if two

conditions are fulfilled:

1). There is a system () i in the collection Hom~~ which is a homomorph­ ous image even if for only one system from the i-th class of equivalence and there is none for any system of another class of equivalence.

2).Among the members rema1n1ng of H~m1ythere is no system (}i which with respect to the J-class of equivalence behaves the same way as (}i - to the

i-th one ( i~j).

Now, we only need to break up the set 0 of all non-isomorphic finite sys­ tems of a given signature <xJ;;P.; ... ;x,.,F,.; P,. > into levels by complexity in order to provide a description of this process. Let us compare to each finite n-basic system = {Q) Q a sequence of nu~bers <X,. O,lH·· : (Q) { 1 s,· m 11 , .,mrt,; X.,, 0, ftt 1 , ... ,!,.,_;tnn,r· , m,.,) in which every member of kind x~~is the ({}) I power of domain X, , every member of kind mil is the nu~ber of places of re­

lat ; on p 1 l P 1 and every member of kind e . is the number of places of ope­ ; 1 ration ~· £ f'.

Breaking up a set { {}} into levels by its complexity is accomplished thus: for any system 0, , 0.1 from { Q } , the system 1.;:, is less than (or equal to) the system Q.t by complexity if and . . fl. _ =toJ{:IQ,I)e.:: only 1f the quant1 ty ' { (1,)- x1 x1 . ... .. .. d./a·'/fs:f (x/~'t:· . .. (X to,~m,t,~ · x flu,,~ ( . ro,J}Ltt.,-1 ·('"' fO,J)t"'f~1(X"'ra,i~,.,· 1(J= fO,}J m.,.~~ ~ X,. .. ... .X~ -+ 1 r ..,. ~ . is less than (or equal to) the quantity V:(O:.J=-X}~' (X/Q:.J',·/ . · (~r(}:.~~s/ 1 + (x/()t 1 l mt.: ... .. t (.X ta:) m,,, .. ... + Xn.(Q:.j ,( x:fl:.)f,., ... " ··- + rx" Ui:.l/"· .. ·1 (X~ ft1:.1J"'"' (X=. {ti~/) lnllt.ll. ·I,. J '~' · n. I -t .. . + n.

It is evii.ent that the set { Q} is well ordered with relation "less (or equal) by comnlexity"; therefore, it makes sense to use a many-stage process cor­ responding to sequential consideration of complexity levels of systems from jQ}, beginning with the minimum one.

Exami) le.

Let .{ 1} be a one-dimensional fea­ ture space whose representative is a one basic numerical algebraic system, that is algebra.!=</1,.2 , ... j ; + > · Let us as­ sume that a training sample for two patterns is represented by two one-ele­ ment sets { 3} and I 2 \ · Now, we deter­ mine to which of these two patterns the

number 5 bel~ngs.

In the feature space I~} the trai­ ning sample is represented by two sys­

tems:

These systems have only two onera­ tions: the binary one of addition+ and the zero-ary one of element choice. The minimum power of '1omain is equal to 1. Thus, the minimum level of complexity containing one system tl{=<{a. }; a{J/J 1 > where ~IJ..J is the binary o;:,eration on set {a}:~ (J.) (a.. Q.): a. is determined in the cln.ss.

'i'he class Hom 1 5 also includes only one alge.bra [) 1 at this stage. It is evident that (}f is a homomorphous image of both :I.J and 1.t systems, there­ fore , the first one of the two conditi­ ons mentioned above i s not fulfilled anJ there is no solution at this stage.

The second stage corresnonds t o the next larger complexity leve 1 v;hich is given if the jomain consists of two ele­ ments a. and ! .

The co~Dlexity level at t his stage ~bnsists of eight non-isomorphic systems

Here , the binar-J . o:--er:;tions of "ad­ dition" f r.:J on set j a, b} are p;i ven by t~e following table.

TA3LE 1.

Which of these eight systems gene­ n te the class HPm .Z s ?

Using known t heorems for generating elements, it is easily to nrove the class Hom.~={~,R; J · In the same way one can be convinced that Q 1 is a homomor­ phous image of both .1J. and .rJ which contradicts condition stated above in the rule of decision acceptance. The system Q 1 is a homomorphous image only of system XJ , which pcrmi ts us to ac­ cept a one-to-one decision: 5 belongs to pattern r J}

We have given this example to em­ phasize that this process can be used, in some cases, in a feature space corre­ sponding to infinite algebraic systems. However, we can not guarantee its use for any feature space. Nevertheless, since an adequate theory of measurement must not refer to infinite algebraic systems from an empirical viewpoint, the stated above restriction on use of this process has no importance in principle.

Conclusions.

In our paper we have intended to show the possibility of constructing an universal method of pattern recognition based on the hypothesis of simplicity. Questions concerning the practical reali­ zation of t hi s method have not been con­ sidered here because there, apparently, is not at present an elaborate enough theory of measurement which excludes re­ ferences to infinity.

R E F E R E N C E S

1. 8aropy~Ko H.r., CauoxaanoB K.~.np~po13 npo6neMY paCIT03HBBO H~R 06pB30B, 11 Bbt\l l~ CJI~Ten:DHYe CHCTet.!bl 11 , HOBOCI!- 6v.pcK, BYU.36, 1969.
2. nJioTK~H E.H. rpynny ~ BTOWOp~V.3~0B 3n­ re6p3ll\lCCKl1X c1:cTeM. "HsyKa", M., 1966.
3. Cynnec n., 3~He C L~ . 0CHOBhl TeOpHV. . ~3r.tepeH!i::. CO. "Dc~rxoJiort1qecKl1e ~a­ rAepeHirfR" ,MocKBa, ~3~ . " rA~p", I967.