Learning Technique and the Stochastic Approximation Method

1. Introduction

One of the main aims of contemporary theo­ ry of adaptive,learning and se~f-learning systems is the unification of the prob­ lems of adaptation,learning and self-lear­ ning from one point of view,i.e.the de­ termination of the appropriate mathema­ tical technique which would be able to solve as large a class of problems as possible.Theoretically it seems that the theory of stochastic approximation could solve this problem 9-f't ·

In the learning problem of dividing input situations into n classes,it is p~­ sible in a deterministic case to consider the learning-as is known· -as an approxi­ mation of the function,which divides two disjoint classes.Let this decision func­ t i on be written as

where ·x is an !-dimensional vector and y is a quantity showing the class to which a pattern belongs.In the stochastic for­ mulation of the problem where the condi­ tion of disjoint classes is not required, y can be taken as the probability that x belongs to one class and 1-y is the pro­ bability that x belongs to another class. The function f in equationCl)can be ap­ proximated by the finite expansion

where ·~ is an n-dimensional vector of coefficients, ¢ cl)is an n-dimensional vee­ tor of ·linear independent functi~mand T stands for transposition.Let Pc~ ) be an unknown probability 1ensity function of the observed vector x.A measure of the approximation of j(1J thro·ugh 'fc1> can be provided by the mean value of any strictly convex functionF with argumentrf<1J·-'{cl>). Then we can write the measure of the ap-

LEARNING TECHNIQUE AND THE STOCHASTIC APPROXIMATION METHOD

Fridrich Sloboda and Jaroslav Fogel Institute for Engineering Cybernetics Slovak Academy of Sciences,Bratislava DubravskA cesta, Czechoslovakia

proximation in the form of

where X is the space of all observed vec­ tors 1 .The best approximation corres­ ponds to such a choice of vector c that j c?) attains its minimum.This problem can be solved by the stochastic approximatim method where the influence of noise can also be considered.

The practical use of the stochastic approximation method as a mathematical technique for learning,self-learning, and adaptation depends on the speed of con­ vergence of the methods used.This paper deals with this problem.From the prac­ tical point of view,the solution of ex­ tremumsearching problems has great sig­ nificance.The stochastic approximation methods,as methods of s equential itera­ tions in the case of extremum-searching problems,exploit various forms of the iterative gradient method.Asymptotic be­ haviour and the speed of convergence we­ re observed by many authors for various modifications of this method.A common feature of all these algorithms of gra­ dient methods an all these modific ations did not,however,change.This is a way in which information is gained during the iterative process.The way of gaining in­ formation,the structure of the informa­ tion and its interconnection provide the basic clue to the construction of the new algorithms and are also the criterion of quality.If there is not suffi~ient info~ mation to make the next step in the ite­ rative scheme,then additional information must be gained by experimental interim steps.From this point of view,those al­ gorithms are important which do not need experimental steps before the next step can be made.The stability of used algo­ rithms against noise depends directly on the structure of gained information and its interconnection.Not every algorithm which solves the problem in the determi­ nistic case is stable against noise. Many control processes can be described only through the mathematical models ~ sessing some uncertainties in the form of a set of random variables with un­ known probabilistic descriptions.

In this paper we describe an algo­ rithm which has the above mentioned pro­ perties;i.e~it does not use experimental steps and information is gained by steps during the iterative process,and it sol­ ves the extremu·-searching problem in the presence of noise.

2. Stochastic approximation methods

The first methods of stochastic approxi­ mation were the algorithms of Robbins an Monro" ,Blum 3 ,-r ,Kiefer and Wolfowitz .t for finding the zero point of the func­ tion or the extremum of the one-dimen­ sional function in the presence of noise. A generalization for multidimensional functions was made later by Blum~ and these results were unified by Dvoretzky', whose results we shall use.As the speed of convergence of the method given by Ro­ bbins and Monro depends on the type of function,often this speed is not satisfa~ tory from the practical point of view.

We shall use the two following ways of accelerating the convergence.Let ~~> be a fixed but unknown function,which has a unique root X.=~ · Let z is a random va­ riable with distribution function f./(1/t.) , which depends on the real parameter l! The Hobbins-Monro procedure is defined for searching the zero point of regresion function

as a sequence f.t.,~ given by relation

where {aJ is a sequence of positive constants such that

FabianT gives the modification of the algorithm which makes it posseble to ac­ celerate the convergence to within cer­ tain limit~ of the probability density function f(X/9) · This limitation for the probability density function results from the condition that the regresion function ~<~ corresponding to the random variable · :t = ~'{"' 2 should satisfy

as was shown by Avedjan 4 5 ·

The other method of accelerating ~ convergence of the Stochastic approxima­ tion metho1 was given by Kesten& .The i~ea behind this method is that if the expression ~(.r .. -x .. _,) retains its signam, then the value of ~ in the algorithm does not decrease /as it does in the algorithm of Robbins and Monro/~but remains unchan­ ged until the first change of signum.On the condition that a. ... is a nonincreasing sequence,Kesten shows the convergence of this algorithm with probability one.The advantage of this algorithm lies in the fact that,until the iterative process reaches the domain of its extremum,the algorithm retains a greater value of step an~ so decreases the influence of noise, as this is indirectly dependent on the value of the step, i.e., the greater the va­ lue of the step the smaller the influence of the random component.Kesten examined the possibility at a lao utili~ in~ this idea also for the algorithm of Kieffer-Wolfo­ witz in order to find the extremum of the re­ gression function.Kesten shows the con­ vergence of this algorithm only with an additional strong condition for sequence C~.Instead of the original condition c~~o, the condition ~;~a~. is essential.And so, in this case,x~in general does not have to converge to the point in which the regression function achieves its extre­ mum.This leads to two opposing demands:

on one hand,the condition of con­ vergence itself,i.e.that the value of should be as low as possible;on the other hand,the question of the speed of conver­ gence,because,the greater the value of the smaller the influence of noise. Obviously,this is valid only so long as the algorithm does not achieve its extre­ mum domain.The idea behind these algo­ rithms for extremum-searching of the k-dimensional function is the way of de­ termination of the gradient.Up to now used standard method for searching the gradient is a static one and the gradient is determined using the experimental steps.In the case of stochastic approxi­ mation the symmetric gradient is the most suitable,and this needs 2k experimental steps for the determination of direction of the gradient.Further,it will be given the algorithm which creates a sequential process during which the gradient is searched without using the experimental steps.This sequential multidimensional search algorithm creates a sequential process of k onedimensional search algo­ rithms. This algorithm tbes not have the above drawbacks and its speed of conver­ gence is better than the speed of conver­ gence of the above-mentioned modifica­ tions.

3. Multidimensional stochastic approximation method

Let fZC~ll be a vell-defined family of random variables with unimodal regres­ sion function1r4which achieves its maxi­ mum at the point;,. fi .Let f~ be k-dimensio­ nal Euclidean space. If X· (K, , ..· ,tAJ E Et then we denote its norm as 11111 .Let ~&~) be a probability density function which satisfies the condition

where ~ will be defined latter. Let -;rc;>= 1<"kh S" ,where JfK) is an un­ known co·tinuous fuction,possessing con­ tinuous-partial llerivativives of. the first order,and o is a random noise Let

.

'-,: 1.2, .. ,i<

where A,B are constants.

Theorem /of Dvoretzky/ 8

Let .X,., 1 ( "1V be non-negative numbers defined for ,_.1,2 .. , .. ;which satisfy the condi­ tions

Letf~lbe Borel measurable vector map~gs which satisfy the condition

Let x 1 ,.tt;,. be random variables and let the following sequence be defined as

Then,if the following conditions are sa­ tisfied .

where C. denotes a mathematical expecta­ tion, the sequence fX~1converges with pro­ bability one and in the mean square to ~ i.e.

Proof:

To prove the convergence X: ... in [i< space it is sufficient to prove the convergence of every component of vector~ .... ; (<'::C::.~ ... <~).

Let us define the algorithm

where ~ is changing cyclically from 1 to /<. and

Let

To find an extremum of a function is formally equal to finding the roots of its derivative.Thus instead of equa­ tion (f.f) we can write

where -1, is changing cyclically f rom ../ to 1< and

where

Let .

('2.2.)

Let us denote

and

where ({,~ satisfy the condition (1f).

Therefore from equation(i<:J)we obtain

Let us denote

which represents the deterministic part of the algorithm,and

is the stochastic component. Then the equation(i'J)can be written

for ;_=,2 "' and

No~ we prove that conditions of nvoretz­ ky s theorem are satisfied for every

3.1. Stochastic part

It must be proved that the following con­ ditions are satisfied .for our algorithm:

.for )., ·.: 1,2-, ... ,i<.,

If the noise makes a sequence of indepen­ dent random variables,then we can write

Now we denote the sum of t~e right side of the above equation as 5wfor every i=.t, ... ,Jc.

-Z. The mathematical expectation o.f ~is the error dispersion which,according to the assumption,is limited

Then

and this sum is finite then and only then, when

for every .Z"' f, z., ... K/ which is satisfied in accordance with llie assumption.

3.2. Deterministic part

Let us consider a family of functions

(2-i)

which results from the fact that the function is continuous and unimodal. Let us denote

then

and

for ever/'E:,,;, .·. ,t I %'tv: 1 1<~ it from Cauchy-Bolzano'"~criterion.( follows

Thus the conditions of the theorem are satisfied.

(ZJ Let o<.('V be the maximum overstepping of the zero point in the ""'-11. step for .C:-t~ parameter.

Then we can write

According to the assumption for flV/;11'-c we can write that

Let us now denote

As ;;......_ ~ '~ 1 .= 0 the assumptions

i~'B+ 11{) -=X:: 1

·""'~()IC.) t-

of the theorem are fulfilled.

As we can see from the above -~;,.,...; ~ = ~

and thus .~ tli(x..~, .· · · 1 x~~ -:: 'i(~, .,., 'lJ-c:..)

where<{)-<.,::£{}.

(:J a

a

Up to now we have assumed that the function ~ (-(~ 1 .. · 1 );:. ) has only one extremum on an arbitrary straight line.The algo­ rithm is not limited only to this class of functions,but satisfies also the class of functions which have more than one extremum on this straight line.This re­ sults from the unimodality of the func­ tion.The algorithm is shown in fig.l, f. (OJ f~) ,,, ,,.) 2 d where the ~.equencez"'.";i:3:1 ... ,i:1j3,.; .. } correspon s to those :t:i/ in which· the corresponding partial derivative changes its signum.

The conditions given forfa .. Jare sa­ tisfied by the harmonic sequence f ~ti--l or f c;.,.,., ~ 1 c_ = cor2~t .

and also by Kesten& sequence which is constructed with the help of harmonic sequence according to the following de­ finition,as the sequence[ol~whose terms are

Using Kesten's sequence, the convergence is accelerated and we avoid the diffi­ culties which occured in part 2.In the domain of the extremum,the value of the step does not affect the noise leTel

and then only the law of large num­ bers is valid.Therefore,in the domain of the extremum,Kesten's sequence does not accelerate the convergence,and it is better to use the harmonic sequence,i.e., to lessen the value of the step as qui~­ ly as possible.This modification gives better results than other modifications.

4. Coclusion

The above-mentioned method of stochastic approximation accelerates the convergen» and therefore has an influence on the qur lity of learning.This method satisfies the condition so-called "An ideal sto­ chastic approximation",i.&,stepa of large value are used far from the extremum; and the nearer the extremum,the smaller the step becomes.The fact that this me­ thod does not use the experimental steps means that,in this case,the convergence is accelerated and the method gives con­ siderable better results than other me­ thods.The method was used in pattern re­ cognition for disjoint classes.

• Fig.l. The multidimtnlional search algo­ rithm

Bibliography:

1. H.Robbins,S.Monro, "A Stochastic Ap­ proximation Method" A.M.S.22/1951/ pp.400-407
2. J.Kifer,J.Wolfowitz, "Stochastic Esti­ mation of the Maximum of a Regres­ sion Function"A.M.S. 23 /1952/, pp.462-466
3. J.R.Blum, "Approximation Methods which Convergence with Probability One" A.M.S. 25 /1954/,pp.382-386
4. J .R.Blum, "Multidimensional Stochastic Approximation Methods" A.M.S. 25 /1954/,pp.463-483
5. V.Fabian, "Stochastic Approximation M~ thods" Cech.Mat.Zurn. 10/85/ No.1, /1960/,pp.123-158 .
6. H.Kesten, "Accelerated Stochastic Ap­ proximation" A.M.S. 29/1958/ pp.41-59
7. V.Dupac, "0 Kiefer-Wolfowitzove Appro­ ximacni Metode" Cas.Pest.Mat. 82/1957/,pp.47-75
8. A.Dvoretzky, "On Stochastic Approxi­ mation"Proc.of the Third Berkeley Symposium on Math.Statistics and Probability,Vol.l,Berkeley,l956 pp.39-55
9. D.J.Wilde,. "Optimum Seeking Methods", Prentice Hall,l964
10. Z.Cypkin, "Adaptation,Learning and Self-learning in Control Systems" Third Congress of IFAC,London 1966
11. F.Rosenblatt, "Principles of Neuro­ dynamics Perception and the Theocy of Brain Mechanisms" Spartan Books, Washington D.C.l961
12. Aizerman,Braverman,Rozonoer, "Vero­ iatnostnaia Zadaca Ob Obucenii Automatov Raspoznavaniu Klasov i Metod Potencialnych Funkcii".Au­ tomatika i Telemechanika,Moskva, T.25,No.9,1964
13. Z.Cypkin, "A vse ze suscestvuet li teoria sinteza optimalnych adap­ tivnych sistem?"Automatika i Te­ lemechanika,No.1,1968,Moskva
14. I.Stratonovic, "Suscestvuet teoria sinteza optimalnych adaptivnych, samoobucaiuscichsa samonastraiva­ vaiuscichsa sistem?"Automatika i Telemechanika,No.l,l968,Moskva
15. E.D.Avedian, "K odnoj modifikacii algoritma Robbinsa i Monro",Auto­ matika i Telemechanika,No.4,1967