Application of Methods of Adaptive Learning to the Problem of Automatic Decision Making Under Conditions of a Priori Uncertainty

APPLICATION OP METHODS OP ADAPTIVE LEARRmG TO mE PHOBLEM 01!' AUTOMATIC DIX:ISION IIAKDG UNDER THE C<BDITIONS

OP A.PRIORI URCERTAINTY

V.K. Akhutin, K.O. lotte, G.K. Kotler, A.Y. Rats Research centre ot biological and medical cybernetics. Leningrad, USSR

Abstngt

The paper deals with the adaptive approach to decision making as applied to the problema ot biological and medical cybernetics characterised by a priori Wlcertain ty. A number ot algorithms is suggested which, being baaed on the analisis ot apoateriorJ information yield the most adequate decision rule to a specific problem. The learning is achieved b.1 the stochastic approximation method and by means ot the correction ot the decision rule structure The methods discussed have been realized on a computer and used in a cybernetic medical centre.

Introductign

fhe basic difficulties ot the artificial intelligence aimulation in biological and medical applications are connected with problem ot choosing ot techniques and algorithms ot decision making. fhese problema are characterised by a lack of aprior,y information which prevetns the use of the clasaical techniques of the theor,r of automatic decision making. A way out may be found in the application of the ideas of adaptive learning. Let us consider the formal approach to the problem.

Let tn, ~}and t A.~} - two measurable space, i.e. the observation space and the decision space, respectiveli. OnR a finite family ~ ot probability mea~es is given. Based on a certain rule~ probability P..,C·> is built which is a measurable image from 5l to {A , .11: J · w"fl. being fixed then P..,C·> is a probability measure on (A,-'}. In caae the family <.5> is tully defined the conatruction of the decision rule 8 is clear. When, however, the family has undefined parameters, the decision rule will have the same degree ot Wlcertainty, to be specified with the accomulation of observation data.

AftRii[' ZC!Jf:r ~ lJ1t. est1metign p typction porameters

Let the probability measure on (A ,.i'J is built by the procedure of the potential function method. As is well known [1] there are two realisation of potential function method, i.e. the perceptron and the computer ones. The perceptron realisation deals with a ~stem of basic tunction!Jti:[~Cw),w&Sl, id,ll, ... J ,while the computer realisation deals with a potential tunc tion K cw,. w~> , which is a symmetrical kernal on Q l( n and is connected with the system j(0U) through the relation

It ;flw) is any fWlction on S?. , approximated using observation w6.Sl. and c,.{c,,cz, .J parameter vector, then the condition for choosing the system ~(w) is the nearness of f ( uJ) to its approximation

The procedure of the tunc tion approximation when using computer realisationis as follows

" where 't(f.f") -is a certain fWlction of two variables;

Xn -is a nonnegative sequence, such as

The lack ofapriori information on the family fil prevents the use of the re­ commendations in (1] for the construction of a suitable potential function.

However, one may restrictm oneself to a certain parametrs family ,;rc.~ , having the necessary properites. It is, for example, the families of unimodal tunc tiona of distance in Q. , such as

.fM.wa)- the distance in Q · In this case the best potential fUnction construction is reduce to the estimation of the parameter o<. , optimal in a certain sense. Let t~e decision set

~ constists of two elements and the approximated tunction J(w}satisfied the relation

Then fWlc tional

c~ be defined, where

Obviously, I~lw) has the following properties a " .

j.(w)- the functional from (1) obtained , with the potential function.92-.(<.{."!r) and satisfying the condition samilar to ( 2) ·

Io~(w)'O, if ~Jiw) ~ ~"f..,(w) i.e. when the decision is~wrong

I .... (w}·O, it ti..f-J(wJ=,U,..J .. (wJ i.e. when the decision is correct.

The optimal value of 01. will be defined b7 the conditione of the functional minimum

The Kiter-Wolfowits procedure can be used here

where - are the non-negative sequence satief7ing the condi tiona

It instead of this we use regression equation the

then the solution is given b7 the Robbins-Monro procedure

where

Por a more precise acco\.Ul t taken of local properties of the observation space Sl the family ot subsets A,. {Ai i. .. ( ... ] can be defined, such as

Then ol can be considered as the function of two variables denoting

It is only natural to suppose ci.ii ; IXjL and changing the learning aim ()), to estimate sequentiall7 the ~etrical parameters matrix A{NJ<N}b7 (4) or (5).

Usually the procedure of decision making ends with the construction of the probability measure Pv.~ ( D ) on the decision space and with the choice of the decision De. ~ with the maximum value Pw<J>) · However, in concrete problems this condition is insufficient. It becomes necessary to introduce the threshold fWlction T ~ T(w/ and the decision 6 (w) will be accepted if

and otherwise rejected. Actually, if a certain measurable partition ~ ,such as -f

then the introduction of the threshold is eqeivalent to the introduction of a subset A· e. A. , such as

and of a corre~onding additional decision D"=oiA a.e. refusal of decision making.

The introduction of the threshold f\.Ulction is similar to the threshold Q'Stem in (2], where the algor! thm tor searching such e7stem is given based on the gradient searching of optimum of &n7 convex criterion. Below the algorithm is suggested for the determination of thresholds,different from that of [2].

The algorithm suggested is connected with a definete correlation between the number of errors of the first and second t7pes for the accepted decision.

It is clear baaed on the analieia ot a verified sample of elements we S'l' the true decision Do ·S. (vJJ is known. Suppose baaing on the observation we Sl: the hypothisie on the clecision making Dfwlwas suggested, and tor arbi trar,y .D - n·

Let the error of the first type for the rule (6) be the event

and the error of the second type the event

Consider a certain decision b·(w) and cletermine for itthe value of the threshold. Por the decision J>*the upper threshold be

and the lower threshold tor the decision D · be

Thus substitution in the right part ot the inequal1t7 (6) ot r~ .. will lead to the fact that will be no errore of the first t7pe and the substitution T~·will lead to the tact that be no errors of the second t7pe.

The properties witl obviOUfl7 hold true tor &n7 t,. T»· and t ~ T11.. ·

~

N~~(t) : o when t < r;. and it is decreasing fUnction when t > r,'1. N.D. (t):. 0 when t >Tj. and 1 t ia increasing function when t ~ r;.

Assuming the set sr not larger then countable,define the function of waste N;. (t) equal to the number of errors · ot the first t7pe for the set Sl' depending of the threshold value and ";. {t.J equal to the number of errors of the second type. These f\.Ulctions are characterised by the following propertiesa

I · Let Q.P .. and QD. 1a the decreasing functions, which are the waste of the tiret and secons t1pe errore when dealing with the decision D.. · The total waste tor the rule n· when the threshold value T (n·) ~ t is

then the threshold value T b· will follow from Q D" (T.J>·) = ,.,;., Q»· (t}

The area where the minimum is searc~ed, is determined the following. It T». <- T ~· , then

t e. cr; ·. T.iJ)

Then the threahold,value T»· ~tb· chosen any of TJ>· e (Tz,·. Tz,"·), it T ;. < T.z~·, then taking T.l>· external to the interval (T}., T:·) we shall obtain an increase in the number ot errors of one type without the decrease in the number of errors of the other type.

~e thresholds thus determined are equal to those in [2], it

Applicatiops

The adaptive learning techniques suggested above have been realized as algoritma and routines tor the computer ODRA-1204 and have been used in the research centre of the biological and medical cybernetics in Leningrad in the desing of the cybernetical medical centre.

Rtftnpa

• I, Alsepw~ M.A. ,J:pue~ 3~·1bsosoap A.M. lle!OA no!eB~BUX ~ B !eop .. O~_ri8BIUI ll8mU. H.a.yxa, II. ~a. II., 1970.
• EilxoBoBd M · .n., BDseBOBd A.A. KB6epse~ec··e c·o!eMB B ue~e. Hapa, II. , 1971.
• ). J.-R. Barra Notions tondamentales de statistique mathematique BOKOD, Paris, 1971
• Badu c. Chitti, Chan Wah-Chun A note on potential function algorithm ·Int.J.Control' 1971 1 Bo 1),199-200
• 7ord N.L.,Batchelor B.b.,Nilkins B.R. Learning 1n potential function classifier ·Electron. Lett.' 1970, 6-25,826-828