Training for Extremum Determination of Function of Variables Measured in Names Scale

TRAINlNG FOR EXTREMUM DETERMINATION OF FUNCTION OF VARIABLES MEASURED

IN NAJJES SCALE

G.S.Lbov

Laboratory of Pattern Recognition, Institute of Mathematics, Siberian Division, USSR Academy of Sciences, u.s.s.R.

ABSTRACT

In this paper an algorithm is given for extremum search of an unknown func­ tion l'r X') when the space of variables taking discrete values is not a metric one. Function values are obtained expe­ rimentally.

The given algorithm is based on the idea of adaptive random search. This al­ gorithm has been used for the solution of a number of practical problems for choosing an effective subsystem of de­ pendent l'~atures in pattern recognition. It is intended for solving problems which do not correspond to know prob­ lems of discrete pro[ ramming.

§ 1. Formulating of problem

This paper deals with the following problem: there is a set of n variables X~' x2 ' ... J xl ' .. . , xn. Everyone of those takes the finite set of values X t = ,'.!t'z 1 , .. . , Xzg , .. . , xz /. ) · Here, variables are ./ L-L quantities measured in a names scale (1) In other words, everyone of these value sets is the list of some object names. i.e. the space constructed by these va­

riables is not a metric one.

Let us form the set of n elements X'= ( !t-' 1 , ... , -X't' . . , xn) taking one element from each set. The number of different '7 sets is equal to AI== 17 C · · For everyi·/ t one of these element sets one can determine J:'tX!)- the quality criterion value of this set. It is required to find such a set ~*= (.!t' 1 ~ , xt.~ , !:{';; J in order for P ( x ) to take the extreme va­ lue. Thus formulated. the problem can be solved only with a method involving com­ plete sorting, generally speaking. As a rule, it is impossible to carry out the complete sorting because of the great number of variants .1\-/ and the considerable cost of carrying out the experiment. However. it is possible to sort only a limited number r of diffe­ rent variants ( i ....:....:.. N) . In this case, if there are no assumptions of function class restrictions, one can use any al­ gorithm for function extremum search.

In this paper an algorithm based on

the idea of adaptive random search is given. This idea is the follo~~ng: orga­ nization of subsequent tests depends on the results of previous ones. Tbis pro­ cedure is the training for extremum de­ termination of the function. For that the number of tests is broken up into a number of groups

and the following assumption is used for testing the (1./'-t- I) -th group: for any pair of values {zr;h X'· !} of variable X ·P' l . l the probability p 'r'f.'{.l:' =x·1::>-P'"" 1 f:t> ..,!t' .. l t,B t) I L)" l J even if one set x including :t' · is L/'J better (according to criterion J'(x) than any set :v including xzr · The difference between these probabilities is greater the more is tbe relative

number of tests carried out by the given moment of search Tests of the (<.P+ f) -th group are carried out in order to include the va­ lue :r-~ of variable X . propor;ional to the probability P · <~'!'{ !t'~ = :ri J which is changed as the search is carried out. At the beginning of the search, if there is no a priori information for prefering one value Xi to another, the probabi­ lities of choice of these values are sup posed to be equal to / !

The Greater the number of tests the more "careful" must be the extremum search and the larGer the problem class solving.

This problem does not correspond to knO\',n problems of discrete programming.

The problem of choosing the most effective subsystem of dependent featu­ res in pattern recognition is an example of such problems for whose solution the algorithm stated below is supposed to

be used.

Really, here the set of all possible variants is that of all solutions of including either feature in an effec­ tive subsystem. The variable X . takes ' two val ·.1es: the i-th feature is included in the feature subsystem or not. In this case, the variant number is equal N-=2rz.

A summary of discrepancies connec­ ted with both feature measure and recog­ nition errors c~~ be used, for instance,

as the criterion F ( X') ·

The other example of such problems is that of technological process optimi­ zation if there are variables measured

in the names scale.

The adaptive random search idea has been used for algorithm (3 )for the choice of m features from n (.N'== Crn). n This algorithm nas been an effective one for solution of a number of prac­ tical problems in pattern recognition, medicine, geoloeY, sociology, psycholo­ gy, economics.

§ 2. Algorithm description.

Let us introduce the following de­

finitions:

1. Space of positions.

Let us denote it by ~ · The space of positions is constructed by variables ~, . X 2 · . .. , z, , . :C n corresponding to those X 1 , X 2 , .. , Xi, . . , X n · Variable zi takes one of the integer values {I, 2. ·}, , m.:} which we na!lle posi­ tions. The number of positions mz. is equal to that of variable values X . in z.. a £iven moment of search ( l7lt ~ ti ) ·

After carrying out every experi - ment group, a one-to-one correspondence is established between the positions of variable ~i. and the values of vari­ able Xz. · For that, the best set -:r rzj) including the value .z> l 1 , the best set X (! 2 } including the value :r!t. 2 and so on are fixed. Putting in order sets ~ (t 1 J, ~ ( l 2 j. .. , ~ rim) by the criterion we thereby put in order the variable values Xi · The variable value for which the best result by criterion J',.~) is obtained is compared to the best po­ sition, the value for which the next result by quantity is obtained - to the second one and so on.

As the search is carried out,the num­ ber of variable values xi used is de­ creased by excluding variable values of less scope. The choice of number mt will

be considered below.

2. Set of transforming vectors. Let us denote it by o( - ( 0( 1 , . . , dp ····dn). Vector cXi = ( O(tt ' c<z 2 , ., 0(-l_fi , ., CXtf'i ) estab­ lishes a correspondence oetween values of variable Xi and positions of va­ riable Zt · The component of this vec­ tor ()(I._} is the value which takes the ~ -th position in a given moment of search.

At the beginning of the search, if there is no a priori information of pre­ ference of one variable value to another the vector is

Since the vectors set is renewed after carrying out each group of expe - riments, denote it by c< (if' .

1. Matrix of recommendations -8 ( !1::: This matrix is a set of recommendations in a space of positions for carrying out a ~ -th group experiments.

( <I'/ for L = 1 , 2, · · · n; 5 = 1 , 2, · · · t · ;

G ( 'f'. 4. Matrix of planning It is obt ained from matrix .B ( Y:' using a set of vectors. Matrix of planning is

for t.=1,2, ··· n; t: 1 2 .. w~, ., = · · · · · ...

1. Function of "confidence" P · This function is introduced as a quanti­ tative measure of preference of one va­ lue to another

for L =1,2, ··· n; .J = 1,2, ··· ~t; where P:J ( 6z , mi) is a probability of vari able value Xi which is occupying the j5 -th position in given moment of search with the value ~/. The choice of parameter 6-i will be considered be­ low.

The function of "confidence" is given in a space of positions.

Proceeding from the assumption des­ cribed in §1 the function ~ ( 6 z: , m i) might have the following properties:

1. at the beginning of search if there is no a priori information of pre­ ference of one variable value to another

1. function pfl r6i' m i) must de­ crease steadily when the number of the position increases.
2. by increasin~ the relative num­ ber of experiments carried out, the fun­ ction of "confidence" must increase at the first positions at the expense of those vdth Greater numbers.

In our case we have used the funct i on 1 / ZJ= 6+ 1 , (f -r 6 Z) 2 w!lich is given in paper (4) ·

For any value of parameter 6 from interval ( O,o.o )

Function of "confidence" is given

The function (1) has all properties for­ mulated above. Really, if 6i-o then all of :7Zt positions of variable :Lt. have equal value for the function of "confi­ dence" - _!_ , If 6i :::> 0 then function m· .:J$ ( 6z I m:) is steadily decreasing ·.·ihen the number of position is increa - sing. If parameter 6z. is increasing as the number of experiments is storing then the values of variable Xr.· occupy­ in[ the first positions will be more prefered.

Since the function of "confidence" depends on the group number of experi­ ments carried out, we denote it by P '~ '6 ) tl 'Z 1171i.

· No-.v, if the number of experiments corresponding to either value JC . is done l. in proportion to the function of "confidence" value then the number of experi­ ments ·uill be stored; the more perspec­ tive variable values xf ' ~Y.z ' ... · xi, . I X n. will be included by further search. The number of exneriments ~ ·,- :,.f) for the - l.r variable value keeping the ;8 -th position is done equal to the nearest inte­ ger from Z ,·f.,P,.f) ~(~4. 17Zz) i.e.

At every stage of search a one-toone correspondence is established ween points of space Z constructed bet­ by variables ::t 1 , .:C 2 1 . , ::t'.i , 1 :t.n. and space X constructed by variables _x;,X2 · ,Xz, .. x.;. This correspondence is done by means of the vec t or set c( r~,t?J. Therefore, if ill space ;,( the set of t ( I.,P+f) points is chosen in correspondence with the dis­ tribution law given by the function of "confidence" and if condition (2) is sa­ tisfied then in space )( set of points which also satisfies equation (2) will correspond to that set. Hence, we obtain point sets in space Z (matrixes lJ J~. lJ rii'J rRJ) ., , .. . , !3 before carrying out experiments. It is necessary to input in ECM only the following data: the number of variables TZ , the number of values for all of the variables f 1 , ~, . , ~z, .. , ~n. and the number of experiments r .

Let us describe the procedure for . . . lJ (f) lJ r.ZJ (<'/ { ~) obta~n~ng matr~xes , , ... , B, ... , E . At first, it is necessary to determine the function of "confidence" ~ rii'J( 6z", ?Tli) using formula (1). We give coefficient

6z.· and the number of positions nzL the following way: the entropy for variable zz:" is calculated by means of the knov.n correlation

Then the entropy for whole space of positions is determined. This entropy is equal to the sum of those for each vari­ able, since the choice of positions of every coordinate is done independently, i.e.

The magnitude H W/ is a quanti - tative measure of our lack of knowledge of which of the AI possible variants corresponds to the best value of crite­ rion !'/X) · At the begirming of the search if there is no a priori informa - tion of preference of one value of a variable to another, this equal to entropy is

Let us denote the relative number of ex--r ~ periments carried out b7 ~~ = 7

the mumber o! experiments reaaining b~ 7" = i- t ~ . Let us require that the entropy should decrease steadily to zero as ~~ is increasing to one. For that, }/ (I/'' " f O) the !unction · - {09.11~ + H where

is introduced.

The quantity Q is on a logari th­ mic basis. Parameter k determines the adaptation deGree, The less k is, the less is the deGree of adaptation. This parameter value must be chosen froc the interval (-2, 2) in order 0~ -~Y'~ 1.

If the quantity 'L ~ is changing from 0 to 1 then At,P is changing from -H roJ ' ~' 1 to a , entropy }/ ' ' is decreasing steadily from g lO.' to o.

The condition on which the choice of concrete v alue of the parameter k depends will be ci ven belov: .

After carryint; out :- t,P tests the entropy is decreasing in coz:parison with , r j .,t'_' the ir.i tial one i n fJ.-oT times. We consider that the entropy for each vari­ able is also decreasin6 , i.e.

Then

that and Let us H iii'J z. (5): ·~· equate entropy Jl' ('6z, mz ) and defining by correlations (3)

Nov:, we determine the number of positions m 1 · For t hat, the maximum num­ ber of the position for which one can choose even one test from the remained number of those 7' Y' is determined. This number is determined thus: at first, we suppose m z = t'z. and from equation

the coefficient value 6z is determinea. Let us denote it by 6zma..X!. I:£ Hr/6. . r v; t m .::zx mz ) ~ Hz. , then mi is supposed to be equal to t'z' - I · A new value m z is tested in the same way. This proce­ dure is repeated until the inequality is fulfilled

The number l7Z i is the first one m for which the inequality (7) is fulfilled.

If the number nz, is defined, then the coefficient !z is determined from eq ua ti on ( 6) w:i th the method of di choto­ my.

v:hen 6l and ml have been determi-,. ned, one can compute probabilities ~~ ( 6z. . mz ) for_}= 1, 2 .. , mz using expression ( 1).

Further, the numbe r 't ,Y.,. f/ tests included in the (..,t'+i) -th t;roup is deter­ mined. It must be such a number so tha t one can reculate the values of every va­ riable X z. by the quantity J:' when the results of experiments ;;. ;_; , . , '; ·. are obtained. The number 't ( if'+l) mus t be as small as possible in order to car­ ry search as "carefully" as possible. For that, we require tha t the value of variable which in a siver: moment of search is occupyinL the last position should be included in a test only one time. From that

. {!/'~ {!, \'!here OK-') t z ·) is the nearest integer from p · ?6. m . 1· mt '" , z. .

( ~ .. f) The test number 'Zl.fi ,.J- -~ .. ,mz,!.-l, .. ,n, is determined by means of expression (2).

Then, the set of z_{ ll'.- -t) points in n - dimensional space of positions is chosen in correspondence with distribution law given by function of "confidence". The choice of these points is done so that the number of points cor­ responding to the fl -th position of va­ riable 'Z: t.) should be equal to X z. · Co­ ordinates of these points are represen­ ted as matrix B ( II'+/) of ( Z Wd)~:>z) di-

mension.

The procedure for obtaining matrix 3 : "'"" 11 · t d 1 t . Th ' ~ s repea e severa ~mes. e matrix to which corresponds the least n~ber of coinciding lines (coinciding points) is chosen from those obtained. If the relative number of coinciding li­ nes exceeds a threshold then the degree of adaptation is decreased (value of pa­ rame ter k is decreased beginning with !( = 2 ) and the process of obtaining . !3 .' f) D f2 ) D (~) , d matr~xes , ~ , . . , a ~s repeate from the very be r inninG·

If k is decreasing to -2 and one can not obtain all mat rixes 13 r; !3 r;J , !3 (~ then we output matrixes obtained and the

n~mber of tests not distributed.

Further experimental planning in­ volved the conversion of macrix 3 tif',' to {] . - ~, by means of vec tors C\ (~) s e t and . ·'<I'' rene·.·!al ~ ' · on base of results obt ained .z:, _.; , , .Z:, 4 · l'he procedure . <r ·~ for obt aining matrix 0 ' · can be done wi thout using a computer.

R::!:FBRENCES

1. Cynnec n., 3~HeC n~. OCHOBhl Teop~M l13r.le pe H>~l1 . C0. "ncl1xonorl14eCKHe l1311.epeH!1R", :.locr<Ba , ~3,n. "MMp", I%7 r.
2. ~opCyr A.A .· ~H H Ke1!bWT e~H ~ . D . nl1cKpeT­ HOe nporpaM~MpOB8HMe. ~OC KBa, 113!.
3. "HayKa", !969 r.
4. R6oB r.c. B~cop a¢¢eKTMBHo~ c11creM~ 33Bl1C~Mb!X npl13H8KOB. 11 Bb1411C1IMTeJI:b­ H~e CMCTeMbl 11 , B~n.!9, HOBOCl16MpCK, !965.
5. EycneHKO H.n., Wpe~,nep D.A. Mero.n CTa­ TMCTHqecKMX MCnb!TaHM~. MOCKBa, ¢M,
6. !96!.