A Collective Of Algorithms

L.A. Rastrigin Institute of Electronics and Computing Technique, Academy of Sciences, R.B. Erenshtein Riga Medical Institute

Riga,Latvian SSR,USSR

A concept of a collective of algo­ rithms ia propoeed,which solve problema from the described aet of problema. In this case the efficiency of the collecti­ ve solution over the whole set appears to be higher than the best algorithm of the collective. Examples of the work of the collective of algorithms are given when solving problema of pattern recognition root determination.

In the typical problema of the beha­ viour synthesis, of the choice for the optimal solution, of the selecting the best plan ect., the difficulty as a rule arises in the choice of the beat algo­ rithm (in the definite sense) for the problem solution from the available set of algorithms. In such situation the in­ vention of a new algorithm is not ex­ pedient and in any case it is not econo­ mical.

~iving beings can effectively solve this problem and in typical situation they behave by combining algorithms al­ ready known to them. Let us formali·e a problem.

Consider the following rather widely spread situation. Let some set (finite or infinite) of problems nf one type{XJ, i=1,2, ··· is given. These problema are coded by n parameters x 1 ,.~.,x so, that each problem in the space R isnrepresen­ ted by the point X=(x 1 , ··· ,xn), and the whole aet of problems forms a region Q (XiEQ ,i·1,2, ··· ).

Let also a finite set of algorithms {A} · {A 1 , ··· , AL} for solving problems X E Q be giv~n. Eacn of these algorithms A (l· =1, ··· ,L) solves or does not solve 1 the problem x1· The efficiency of solution is determina~ed by some given critarion Q, which to the pair Xi and A 1 relates the q number:

which characterizes the algorithm A 1 when xi. the perfcrmance of solving the problem

Let us give examples of the problems of such kind. The pattern recognition problem, where X is a farticular pattern recognition problem, {A is a set of re­ cognition algorithms, e.g., Bayes method, method of potential functions, method of perceptron etc., q is a probability that recognition is correct.The root determi­ nation problem where X is a particular function the root of which is to be determined, ~} is a set of algorithms for determin1ng the root, e.g., methods of tangents, of chords, of dichotomy etc.,q is the number of iteration for convergen­ ce into £-point of a root.The problem of the search optimisation where X is a situation set in the course of optimiza­ tion,{A} is a set of the search algo­ rithms, e.g., gradient method,random se­ arch method etc., q is mean increment of a function to be optimized or the number of unsuccessful ateps.

The choice of the optimal algorithm for solving the problem Xi,thus, reduses to solving the extremum problem:

where Aj is the best from the available algoritams for solving the problem Xi.

It is expedient for solving the set problem to consider the use of the me­ thods of collective decision making ~.2~ Usually we mean by this or that fom of the voting algorithm. To realise the ool­ lective solution we ought to aolve the problem by using each of the available algorithms A 1 ,A 2 , ··· ,AL (i.e.to·aake enu­ meration), and then by means of some procedure to generalize the individual solutiona in the collective. The aain shortcoming of the voting algorithms is first of all the potential yossibility of arising an Arrow paradox~] ,which is known in the collective solution theory, or nontransitivity paradox. This paradox arises due to contradition of individual preferences and then it is impossible to work out a generalized solution. Another shortcoming of the voting procedures is that we are not sure that the solution made by tpe algorithm, separately taken from the{At, in the sense of criterion Q, better then the collective solution.

On the other hand the solving of the optimization problem (2) is associ­ ated with solving the problem X only once, which makes senseless futh~r choi­ ce of the optimum algorithm because the problem is already solved. That is why the problem of constructing the func­ tion j=f(X), determining the number of the optimum algorithm j for the solu­ tion of the problem X, should be solved without full enumeration.

The approach proposed in the paper allows to eliminate the mentioned short­ comings of the voting and the enumerati­ on algorithms, although it belongs to algorithms for the collective decision making,but in the more wide sense.

The basis of the approach proposed is the s~estion that in the space of problems R there are compact preferen­ ces regions of algorithms A 1 ,A 2 , .·· ,A~· The preference region B of the algori~ Ai consists of those pr~blems xi, in the c~urse of the solution of which the gi­ ven algorithm extremes the given effici­ ency criterion (1):

j·1, ··· ,L.

In the course of solving the parti­ cular problem X preference is given to that algorithm from the set A, to the preference re§ion of which this problem in the spaceR belongs(J-5):

Such approach reminds very much of ~ "dictatorial" one, which is known in the theory of the collective decision making and which, as it is known, has no nontransitivity paradox[2]. Bach prefe­ rence region, however, baa its own "dic­ tator", that is why the approach remains collective. It was shown experimentally (3-5], that such way of choice, on the average,allows to aolve the problem bet­ ter than the best of the competitive al­ gorithms of the set {A}.

It is evident that to realise such approach it is necessary to learn to construct the estimates of the algorithm preference regions and assign the new problem X to one of these regions.Por this it is expedient to use the known learning algorithms [6,7].

In the paper as the learning algo­ rithms modifications of the algorithms of the potential function~]and the Pix­ Hodges algorithm [7]are proposed.The ba­ sis of any laerning algorithm "with the teacher" is the training sequence, which ahould consist of problems which are re­ presentatives of each preference region (3). To form it one ahould use the alre­ ady solved problema, i.e. "the experi­ ence" of the algorithms from the set {A} · Let us consider in brief each of the le­ arning algorithms.

To realise the method of potential functions 6 one should in each point of the training sequence,i.e. for each problem Xk,k=1, ··· ,l, a charge g1kis set, which form around it the potentiAI sur­ face of the following type:

p:o1, ··· ,L,

~lk is the attenuation factor of the po~ential function; JD(X,Xk) is a dis­ tance (in the wide sence) between the problem X and the problem X of the training sequence in the spacekRn.

Puther for the given particular problem X and each algorithm A 1 ,A 1 e {A}, a summary potential is construete~:

and for solving the problem X an algo­ rithm with the number j is selected,for which

The meaning of the Pix-Hodges algo­ rithm is as follows. Por each newly set problem X in the apace of the problems Rn there are m the most similar problems from the ones already solved. The "aimi­ liarity" can be evaluated by the value of the Euclidean distance:

The preference in the solving of the problem X is given to the algorithm which extremizes criterion Q in the most of these m problems.

To illustrate the above statements we consider a series of experiments.

lhe pattern recggnition problem

This problem appears to be the most relevant for the use of the approach proposed. The case is that there is no necessiAY to specially form the problem space R ,auch space is the property spa­ ce. Each object in this space represents a narrow recognition problem.As for cri­ terion Q,it was said above that it means a correct recognition of the given obj­ ects.

Experiments were done by using both the model and the real recognition prob­ lems. As the model problem, the problem of recognizing two classes,the deviding surface between which is no~linear, was considened. The dimensionality of the space R was equal to two. As the compe­ titive algorithms two linear decision rules A and A were chosen. The volume of the 1 trainifig sequence was equal to 100,for the checking 10 000 realizations were examined. As the learning algorithm in all the recognition problems solved the method for potential functions was chosen.

The table 1 gives the values of the probabilities of the recognition error by using each of the rules,the collecti­ ve of the rules and the method of po­ tential functions.

It follows from the table that the proposed approach is advantageous both as to each of the algorithms and as to the known algorithms of potential fun­ ctions. The analogous conclusion can be done also from the following experiment.

A problem of recognizing accident situations in the electric and energetic system is set. The accident situation in the electric and energetic system happens most frequently due to redistribution on the power flow over the transmission li­ nes,the accident flow of the active power exceeding the admissible level of the transmissive capacity of the given trans­ mission line. The property space consists of 6 measurements,the volume of the trai­ ning sequence is ·equal to 100, for che­ ki~ 330 realizations are examined. A set {A} consisted of 6 linear decision rules. in the table 2 the results of this prob­ lem solving by a series of conventional algorithms and by the mentioned collec­ tive of rules are given.

The third experiment considers the case when elements of the set {A} are not formalized. This case c·rresponds to the collective of specialists, in this example it is an artificially formed con­ silium. The organized con&ilium was sol­ ving the problem of recognizing the myo­ cardial infarction using ECG. The table 3 gives the results of the work of each of the specialists as well as the quality of solution obtained by means of the propo­ sed approach and the voting algorithm.

It is evidently seen that the given approach is advantageous compared with the voting algorithm.

tb· problem gt tho tunctign rggt dotorqd­ nation

This problem is set in the following w~. A set {A} is given, which consists of four elements: A 1 is a dichotomy meth­ od, A is a method of chords, A is an itera~ive method, A 4 is a tangent)method. The problem spaceR consists of the mea­ surments of the function values with the definite values of an argument. The di­ mensionality of this space was equal to 5. For learning and checking a special prog­ ramme generated functions of one class. The training sequence consisted of 100 realizations, checking one of .250 re­ alizations, As the criterion Q the number of search steps was chosen. The decision as to what algorithm to prefer was made by using the Fix-Hodges method. The num­ ber m was found which give the possibili­ ty to lessen the mean number of steps ta­ ken by this algorithm for searching roots of the checking functions, i.e.to improve the quality of its performance. Table 4 gives the results of the experiments.

Table 4.

The results of experiments allow one to made a conclusion that the approach proposed is universal. It is evidently that the main difficulties associated with its applicabi!ity concerns the form­ ing of the space R , which is adequate to the problem to be solved.

The approach proposed can be used to solve problems of the pattern recognition, of optimization,of optimum eontrol,etc.On the other hand it can be used as a model for understanding the processes of selec­ ting the behaviour of organisms in the typical situations. In this case the way of investigation is obvious- it is neces­ sary to describe the space of problema R~ which are being solved by the organia~ single out a set of the behaviour algo­ rithms {A} and according to observation of the behaviour in different situations, i.e. in solving problems from the set{X}, to single out "the competence" region of each behaviour algorithm A 1 · If th~ae re­ gions do not intersect, then it is reaso­ nable to suppose that the living being in selecting the behaviour realizes the al­ gorithm described above.

Bibliograp!q

• 1.R.Duncan Luce and Howard Raiffa. Games and Decisions. ,New York, Wiley &.son~~t1957.
• 2.G.T.Guibaud.Les theories de l'intereat general et le problema logique de l'ag­ gregation.,"Economie Appliquoe", N4,Pa­ ris Publications de l·Universite Fran­ cois,1952.

• ).L.A.Rastrigin,R.H.Erenshtein. Learning o~ a collective of solving rules. "Adaptive Systems",v.4.,Riga,Zinatne, 1974, (Jiua)
• 4.L.A.Rastrigin,R.H.Erenshtein. A collec­ tive o~ solving rules aa an e~~ective recognition algorithm. Materials o~ VI Allunion meeting on managemen~ prob. lems,v.1.,Moscow,Nauka,1974,(Rus)
• 5.L.A.Rastrigin,R.H.Erenshtein. On a me­ thod of collective decision making.Ma­ terials of VII Allunion simposium on cybernetics. Tbilisi, 1974.(Rus)
• ~M.A.Iserman,E.K.Braverman,L.I.Rozonoer The method o~ potential ~unctions in maschine learning theor,y.Koscow,Nauka, 1970, (Rus)
• 7.V.N.Vapnik,A.J.CherTonenkis. The theo­ ry o~ pattern recognition.Moscow,Nauka, 1974, (Rus)