NASA/TM-1998-112239

@i _ i ̧

/_ -52

5/3 / _/_

Accelerated Training for Large Feedforward Neural

Networks

Slawomir W. Stepniewski and Charles C. Jorgensen

November 1998

https://ntrs.nasa.gov/search.jsp?R=19990008890 2018-05-11T17:13:38+00:00Z
The NASA STI Program Office... in Profile

Since its founding, NASA has been dedicated to the

advancement of aeronautics and space science. The

NASA Scientific and Technical Information (STI)

Program Office plays a key part in helping NASA

maintain this important role.

The NASA STI Program Office is operated by

Langley Research Center, the Lead Center for

NASA's scientific and technical information. The

NASA STI Program Office provides access to the

NASA STI Database, the largest collection of

aeronautical and space science STI in the world.

The Program Office is also NASA's institutional

mechanism for disseminating the results of its

research and development activities. These results

are published by NASA in the NASA STI Report

Series, which includes the following report types:

• TECHNICAL PUBLICATION. Reports of

completed research or a major significant phase

of research that present the results of NASA

programs and include extensive data or theoretical analysis. Includes compilations of significant

scientific and technical data and information

deemed to be of continuing reference value.

NASA's counterpart of peer-reviewed formal

professional papers but has less stringent

limitations on manuscript length and extent

of graphic presentations.

• TECHNICAL MEMORANDUM. Scientific and

technical findings that are preliminary or of

specialized interest, e.g., quick release reports,

working papers, and bibliographies that contain

minimal annotation. Does not contain extensive

analysis.

• CONTRACTOR REPORT. Scientific and

technical findings by NASA-sponsored

contractors and grantees.

• CONFERENCE PUBLICATION. Collected

papers from scientific and technical conferences, symposia, seminars, or other meetings

sponsored or cosponsored by NASA.

• SPECIAL PUBLICATION. Scientific, technical,

or historical information from NASA programs,

projects, and missions, often concerned with

subjects having substantial public interest.

• TECHNICAL TRANSLATION. Englishlanguage translations of foreign scientific and

technical material pertinent to NASA's mission.

Specialized services that complement the STI

Program Office's diverse offerings include creating

custom thesauri, building customized databases,

organizing and publishing research results.., even

providing videos.

For more information about the NASA STI

Program Office, see the following:

• Access the NASA STI Program Home Page at

hnp ://www.sti.nasa.gov

• E-mail your question via the Internet to

help@sti.nasa.gov

• Fax your question to the NASA Access Help

Desk at (301) 621-0134

• Telephone the NASA Access Help Desk at

(301) 621-0390

Write to:

NASA Access Help Desk

NASA Center for AeroSpace Information

7121 Standard Drive

Hanover, MD 21076-1320
NASA/TM-1998-112239

Accelerated Training for Large Feedforward Neural

Networks

Slawomir W. Stepniewski

Ames Research Center, Moffett Field, California

Charles C. Jorgensen

Ames Research Center, Moffett Field, California

National Aeronautics and

Space Administration

Ames Research Center

Moffett Field, California 94035-1000

November 1998
Available from:

NASA Center for AeroSpace Information

7121 Standard Drive

Hanover, MD 21076-1320

National Technical Information Service

5285 Port Royal Road

Springfield, VA 22161

_1 :If:
Accelerated Training for Large Feedforward Neural Networks

SLAWOMIR W. STEPNIEWSKI AND CHARLES C. JORGENSEN

Summary

In this paper we introduce a new training algorithm, the

scaled variable metric method. Our approach attempts to

increase the convergence rate of the modified variable

metric method. It is also combined with the RBackprop

algorithm, which computes the product of the matrix of

second derivatives (Hessian) with an arbitrary vector.

The RBackprop method allows us to avoid

computationally expensive, direct line searches. In

addition, it can be utilized in the new, "predictive"

updating technique of the inverse Hessian

approximation. We have used directional slope testing to

adjust the step size and found that this strategy works

exceptionally well in conjunction with the RBackprop

algorithm. Some supplementary, but nevertheless

important, enhancements to the basic training scheme

such as, improved adjustment of a scaling factor for the

variable metric update and computationally more

efficient procedure for updating the inverse Hessian

approximation are presented as well. We summarize by

comparing the scaled variable metric method with four

first- and second-order optimization algorithms,

including a very effective implementation of the

Levenberg-Marquardt method. Our tests indicate

promising computational speed gains of the new training

technique, particularly for large feedforward networks,

i.e., for problems where the training process may be the

most laborious.

1. Introduction

For some neural network applications requiring high

modeling/mapping accuracy, it may not be sufficient to

employ first order training methods based on the

gradient descent schemes with adjustable learning rates.

Although these training algorithms are relatively

inexpensive computationally, they could perform poorly,

because the search directions can partially overlap and

interfere with each other producing the undesirable

effect of impairing previous minimization efforts during

subsequent iterations (refs. 1 & 2). Moreover, for

problems with rapid changes of the objective function,

small variations in the step sizes may result in

considerably different gradient directions and even entire

search paths.

In optimization theory, several solutions have been

proposed to boost the effectiveness of consecutive

directional searches (ref. 1). Conjugate gradient methods

attempt to construct non-interfering directions based on a

steady quadratic model of the objective function and the

assumption of exact line searches along those search

directions. The more effective Newton and trust-region

methods rely on a more detailed quadratic model of the

merit function rederived at each iteration. A serious

drawback of these algorithms is the significant

computational overhead of obtaining the matrix of

second partial derivatives (Hessian) or its approximation.

Quasi-Newton (secant) training methods also utilize a

Hessian approximation or its inverse. The computational

efficiency of quasi-Newton methods comes from the fact

that a Hessian approximation is continuously built

during function minimization. The updating process is

substantially faster than computing a complete Hessian

matrix. However, the lack of precise knowledge of

second derivatives may have a negative impact on the

training convergence rate. In practice, the algorithm may

also be more susceptible to local minima and round-off

errors. It may be advantageous, nevertheless, to use

quasi-Newton methods for problems where other second

order algorithms are computationally too expensive and

gradient descent methods produce unsatisfactory results.

In this paper, we present a new variation of one quasiNewton method, the scaled variable metric (SVM)

method. The method appears to be quite competitive

with other leading training techniques. Our tests show

that for large neural networks having more than several

hundred weights, the SVM technique typically

outperforms standard variable metric algorithms in

convergence speed and in some cases it is also able to

produce the most accurate neural models.

2. Quasi-Newton Methods

Although quasi-Newton optimization algorithms are

most commonly understood as techniques to construct

successive Hessian approximations or their inverses,

many modem approaches view them primary as

strategies to choose a series of search directions. These

methods put less emphasis on the issue of convergence

to the true Hessian. The majority of quasi-Newton
optimizationalgorithmsutilizeformulaethatbuild

inverseHessianapproximations (denotedasmatrixD).

MethodsconstructingdirectHessianapproximations

(refs.3&4)areusedlessfrequently. Ouralgorithm

belongstothegroupofvariablemetricmethods, an

important subclassofquasi-Newton algorithmsthat

ensurepositivedefiniteness ofD.TheHuangformula

(refs.4& 5)definedby

D,., = D k + ADt = D k + p (K, AIt+ K2OrAgk).rAg '

(Z aw,+LD T,Ag,)T

O)

is a fairly general update for which the well-known

BFGS (Broyden-Fietcher-Goldfarb-Shanno) and DFP

(Davidon-Fletcher-Powell) formulae are special cases.

In (1) Awt = wk+_- Wkis the vector of weight corrections

and Agt denotes the corresponding gradient change.

The p parameter must be positive to preserve positive

definite property of Dk. The four other scalars K I, K2,

L_, and 1.2, can be chosen arbitrarily except for L ! = 0 and

L2 = 0 at the same time. Note that (1) allows Dk to be

unsymmetric. When updating I)_ using (1), at every

iteration the following condition is satisfied

Dk+lAgk = paw k (2)

An interesting property of the Huang update is that for

strictly quadratic error function E(w) with a positive

definite Hessian H = a2E/Ow2 and the initial matrix Do

chosen so (Do + D0r)/2 is also positive definite, the

series D k--->pH _ when p is constant (refs. 5 & 4). In

practice, most variable metric algorithms which utilize

(1) with p _ 1 do not preserve a constant p but rather

attempt to tune it on-line. Nevertheless, convergence to

pH _ is an appealing property and limiting frequent and

large changes of this scaling factor may be beneficial.

The Huang family of formulae offers an infinite number

of choices for its adjustable parameters with minimal

theoretical background as to how best set them

optimally. In fact, for the strictly quadratic error function

and exact line searches, the sequence of search directions

is independent of the particular choice of Kj,/(2, Lj, L2,

and constant p (ref. 4). However, for non-quadratic

functions and inexact line searches, different updating

formulas derived from (1) are not equivalent. In this

paper we consider the following choice for the K, and Li

(i =1, 2) parameters

T

1 Agk DkAg k 1

K I = 1 K 2 =--

/9 AwTAgk p

A +

Ll= gk DtAg_ T L_ =0

AwkAgk

(3)

Substituting (3) in (1) leads to the expression

D,+, = Dk+ AD k = D k + ---PAwkAw _ -

bk

1 "r r

-- (D, Ag,)(D, Ag,) + a,r,r,

(4)

which produces symmetric updates. In equation (4)

ak = AgrDkAgk, bk = Aw[Ag k and rk = Awk/b k -

DkAg_/ak are introduced for notational convenience.

Because (4) is very similar to the BFGS formula except

for the p scalar, this equation will be referred as the

extended or modified BFGS formula. Various authors

have tried to find the optimal setting for the p parameter

(see ref. 3 for a review). It is the paradigm proposed and

studied by Oren (ref. 6) which, in our view, offers an

elegant mathematical justification of how to assess the

useful range ofp values.

3. Convergence Acceleration

The idea that the convergence rate of the variable metric

methods could be controlled was originally suggested by

Oren and Luenberger in the context of the self-scaling

variable metric method (ref. 6). The concept is based on

the theorem, which considers the positive definite

quadratic form

1

i(x-x')'n(x-x')

(5)

with respect to (x - x') and an abstract optimization

algorithm which aims to find the stationary point x°.

It is assumed that the minimization method uses exact

linear searches along direction s t -- -Dkg k, where Dk is

assumed to be an arbitrary positive definite matrix and gk

is the gradient of (5) evaluated at xk. For any starting

point, the convergence rate of such an algorithm could

be bounded by the inequity (ref. 6)

F(xk+,) - F(x') < (_'(M_) - _] _

F(x_) - F(x') __'(M,) +

(6)

Tl I ii
where_(Mk)> 1 is the condition number defined as the

ratio of the largest eigenvalue of Mk to the smallest one.

The matrix Mk is given by the formula

M k = HV2DkH t/2 (7)

Clearly, the fastest convergence can be obtained for

Newton type algorithms when Dk = I'I-j. Then

_¢(Mk) = _¢(I) = 1 and the minimum is reached in only

one step. The performance of the simple steepest descent

method with exact line searches (D k= I) depends heavily

on the type of the objective function characterized by the

configuration of H eigenvalues (_(M_) = _¢(H)). When

these eigenvalues are significantly different, F(x) forms

a narrow "valley" and we may anticipate a poor

convergence rate. Other search strategies, such as

traditional variable metric methods, can increase (or

decrease) the convergence rate through the Dk matrix.

It is interesting to note, that for badly selected Dk it is

possible that _:(Mk) >> _¢(H) and our abstract

optimization algorithm may perform worse than the

steepest descent method.

Figure 1 illustrates changes in location of M_

eigenvalues after subtracting (D kAg k)(Dk Ag, )x/a k

in (4) then adding pAwkAw,/b_r and akr_rrk terms,

respectively. All initial eigenvalues/z i (i =1 ..... 5) are

either smaller or larger than p = 2 in the example. It is

easy to see from figure 1 that each extended BFGS

update (12) tends to move all eigenvalues of Mk but the

smallest one closer to each other. The parameter p

determines the value of smallest eigenvalue. Figure 1

shows that when the p scalar is constant, it behaves as an

"attractor" for other eigenvalues that will tend

monotonically (in a weak sense) to p in the subsequent

iterations. In DFP or BFGS formulae p = 1; if this

setting increases the condition number l¢(Mk), then the

convergence of the training method may suffer. One can

easily construct examples when all eigenvalues of the

initial matrix M o = Hl_DoHlrz = H (assuming Do = I) are

located away from ohe. Theh, agsigning p = 1 in update

(4) may cause convergence deterioration. It may then

take a considerable number of iterations for the M_

eigenvalues to gravitate to each other, so g(Mk) will

decrease and the optimization algorithm will recover its

speed.

4. Scaling Factor

In practice, the gain in performance from the correct

scaling factor Pk is accumulated throughout several

iterations. This makes it difficult to adjust Pk in an online fashion by observing the effects of the error

reduction in a short horizon. A proper setting of the Pk

parameter in (4), so the condition number r(M k) will

not increase, requires certain information about Mk

eigenvalues. Since the elements of M_ are not known,

similarly to (ref. 6) we use the Rayleigh quotient R(.)

to estimate the spread of eigenvalues. For a real and

/as Iz4 /_3 _u2 /zl

0 0.5 I 1.5 p=2

#5 /14 /z3 'u2 .u=

,0=2 4 6 8 lO 12

i

Mr+ z

Mk+l 0 0.5 'l 1.5 p:2 0 0=2 4 6 8 10 12

Figure 1. Plots tracking eigenvalue changes of the matrix Mk due to the repeatedly applied update (4). The "movement"

of the smallest eigenvalue of Mkis marked with the white squares.
symmetric matrix Mk, the Rayleigh quotient is defined

by Re(x) = xrMkx/xTx • The lower bound for the

largest eigenvalue of M_ is given by

max(]_,]) - R0(x), x _ 0

(8)

Similarly, we may try to estimate the upper bound of the

smallest eigenvalue of Mk using R l(x) = xrM_lx/xXx

min(]_,]) < e?'(x), x _ 0

(9)

Since D_ is positive definite and Mk = Htr2DkH la,

therefore, Pi > 0. This allows us to omit the absolute

value operators in (8) and (9). Re(x) and Rt(x) are equal

to the largest and smallest eigenvalues respectively,

when x is the associated eigenvector; in other cases

these estimators are less accurate. For certain vectors

x the Rayleigh quotients can be computed rather

inexpensively

,/2 ,Xg_b,ag, _ a_

(10)

_t H_,I_ Ag_Aw, b_ ---

AwrDk-_Aw_ Q (I1)

The scalar ck = AwXD;1Awk in (11) can be calculated

without inverting D k. Taking advantage of the

relationship Aw k = -a kDk gk used to compute weight

corrections (section 5) we can write

T -I T

ck = Aw kD_ Aw k = -akAw k gk (12)

In our training algorithm Pk is adjusted based on the

geometric average of (29) and (30), i.e.

(13)

Unfortunately, in some optimization problems estimator

(13) tends to vary rapidly. Many fluctuations of Pk may

be associated with the imperfect procedure of evaluating

this parameter rather than the real changes of the

eigenvalues and the error surface. In section 2 we

mentioned possible benefits of slowly varying p_ by

pointing out that for constant p, =p the convergence

D k ---> pH _ is achieved for the sequence of matrices

generated by the updating formula (4). In the SVM

algorithm, we suppress variations of 11Pkrather than

Pk by implementing a simple, low-pass filter using an

exponential average

p;' = rpk__t + (1 -- y)r Ckx/_'_k (14)

where 7 is the weighting factor (0 _<y< 1, typically,

3,= 0.9). The x scalar in (14) has heuristic roots and is

used to drive Pk slightly toward smaller values, which

have typically better convergence properties; in the SVM

algorithm we set x = 1.2.

Figure 2 displays changes of the scaling factor during the

training procedure. Apparently, in this case the rescaling

of the Dk matrix is not necessary during the very first

stages of training. However, as the training progresses

other values of Pk, different from 1.0, are more

appropriate.

20

10

0

0 200 4OO 60O 800 1000

Iterations

Figure 2. Changes of the scaling parameter l/p, during

training evaluated according to equation_4). Both

filtered values and raw estimates r_c /a are displayed.

5. Step Length Calculation

In the variable metric methods, the search direction is

determined from the equation s k = -Dkg k •Then, the

step length (_ and the weight correction Aw k = tXkSk

along a given ray are established. To avoid expensive

direct line searches, we compute oq, according to the

formula (refs. 7 & 8)

T

skgk

a k = - (15)

s:Hs k + _StS T _

for which the vector Hsk is evaluated using the

RBackprop algorithm (ref. 8). To achieve a more precise
stepsizeadjustment, the )l, parameter is continuously

tuned during the training process. This process is

performed differently from (ref. 7).

For a descent search direction and sufficiently large

value of 3', it should always be possible to find such an

ct k that (15) would lead to the error minimization.

However, this primary condition (E(wk+ _) < E(w k ) ) for

the step size to be accepted does not assure an efficient

training strategy. Under certain circumstances, the step

size defined by (15) may be either too small so the new

point is placed far before the minimum or too large; in

the latter case the algorithm overshoots the minimum

along the given ray producing negligible error reduction.

In both situations, the result is an unsatisfactory decrease

of the objective function. For positive curvature

(s_Hs k > 0) and E(w) represented along the search

direction by the function of one argument

E(ct k ) = E(w, + txks k) a simple criterion against too

long step size is (refs. 4 & 9)

E(ak) < E(0) + flakE'(0) = E(0)+ flakgTsk (16)

where fl (0 < fl -<0.5) ) is a fixed parameter. Setting fl

to the values smaller than 0.5 relaxes condition (l 6)

allowing longer steps to be taken. In our training

algorithm we use fl = 0.5.

The SVM algorithm attempts to take full advantage of

the presumed local quadratic nature of E(a k) by

reducing _, as much as possible. The value of 3' is

decreased by half on every iteration that satisfies (16).

When the condition is violated but the reduction in error

is achieved regardless, the new weight settings are

accepted and the value for 3' is increased (multiplied

by two) so in subsequent iterations the step length ctk

will tend to be smaller, Finally, in case of failure

(E(w_+) _>E(wk)), the value of 3' is increased more

rapidly (multiplied by four) resulting in shorter step sizes

a_ in the next attempts to minimize the error function.

In the special case when the denominator in (15) is not

positive, 3, is reset to the new value

(17)

This rather "desperate" act effectively reverses the

Hessian sign in the step length calculations. Resetting

3, according to (17) acts as a safeguard in rare situations

when the local information I-Is kand the current value of

3, does not provide reliable information on how much the

step size could be extended.

In our algorithm, the 3' parameter is bounded between

macheps _and 1016for a double precision

implementation. Violation of the upper constraint was

chosen to signal the failure to minimize E(w). It may

be possible that Dk is no longer positive definite due to

the round-off errors and the search direction is not a

descent one. In such a case, D kis reset to the identity

matrix and consequently, the new search direction

s_= -gk is selected.

Note that the training method described here does not

automatically reset Dk to the identity matrix every N

iterations as in the cyclic methods (N - total number

of weights). We argue that, for large optimization

problems, discarding previously acquired information

about the second derivatives in such predominant

fashion is often unnecessary. In our method, the Dk

matrix is reset when it is evident that its positive definite

property is lost, i.e., ak <_0. In addition, another test is

performed

> macheps

IIAw,ll211 g ll2 (18)

to avoid updating D k with two noisy vectors, Aw k and

Ag k . Note that (18) assures bk > 0. If condition (16) is

false, the D k update should be skipped. Furthermore,

when this situation is detected in several consecutive

iterations the Hessian approximation should be reset as

well.

6. Predictive Updating

In the basic quasi-Newton schemes, matrix Dk is always

updated after the actual step from w_ to w m is made.

Therefore, the choice of the search direction relies only

on previously acquired information, without precise

knowledge of what could be expected in the next step.

The RBackprop algorithm could be used to partially

compensate for this deficiency by probing desired

directions.

For floating point computations, the machine precision

(macheps) may be defined as the smallest value so 1.0 and

l.O+macheps have different representations in the computer

memory.
Rail

1

Table 1. Final training errors and average CPU time used to complete a single training task.

Method SVM

3.968e-03

4.248e-03

4.201e-03

4.299e-03

4.180e-03

LM

4.007e-03

4.]46e-03

4.286e-03

4.423e-03

3.987e-03

-8

9 3.762e-03 3.992e-03

I0 4.389e-03 4.477e-03

BFGS

5.325e-03

4.707e-03

BFGS

limited memory

RPROP

5.102e-03 6.606e-03

5.372e-03 6.691e-03

4.975e-03 5.347e-03

5.351e-03 5.706e-03

5.051e-03 5.157e-03

6.790e-03

6.702e-03

6.644e-03

4.065e-03 4.209e-03 5.170e-03 5.220e-03 7.147e-03

4.126e-03 3.991e-03 5.015e-03 5.297e-03 6.218e-03

3.906e-03 3.809e-03 5.123e-03 5.376e-03 .6.670e-03

200

14h 40 min

5.053e-03 5.391e-03 6.802e-03

5.269e-03 5A28e-03 6.667e-03

1000 1000 1000

26min 22min 5 mm

Iterations 1000

CPU time 25 rain

The idea of predictive updating is not complicated. A

search direction that is computed as in the traditional

variable metric algorithms serves as the first

approximation of the final search ray. Along this

direction, information about second derivatives is

collected using the RBackprop method. This information

is used to update the Dk matrix one more time before

calculating the final search direction.

The initial guess for the search direction is therefore

s k = -D_g k. In a small neighborhood of the current

point w,, the error function can be approximated by a

quadratic model

I T

E(wk) = c +bTwk +Tw_Hwt (19)

where b is such a vector that 3E(wD/Ow = b+Hwk and

c is constant. Operating on (19), for some suitable e and

Aw = est we can write

w=,,,÷_, ,,=,,,, (20)

Relationship (20) suggests that the Dt matrix may be

updated using ells k and es k in place of Ag and Aw in

the equation defining the extended BFGS formula. Note

that the e scalar will annihilate in this update. This yields

the new matrix Dr, which can used to compute the final

search direction _, = -Dkg_"

Employing a supplementary, predictive update of the

Dk matrix involves some risks when the error function is

highly non-quadratic. Our tests showed, however, a

positive impact of the predictive update in practical

problems. In the majority of tests, the convergence was

faster and the final results were better in comparison to

the method that used a single BFGS update per epoch.

Computer implementation of the predicative updating is

not complicated, as the additional program code is very

similar to the main loop in extended BFGS routine.

Moreover, since the network output and the gradient

were already evaluated for wk, the product I-Isk may be

obtained relatively inexpensively for any st (at the cost

of one additional feedforward and one backward pass)

using the RBackprop algorithm.

7. Efficient Update Implementation

It is not unusual for feedforward neural networks to

incorporate several hundred adjustable parameters. For

variable metric methods, this translates into increased

costs for periodic updating of the Dk matrix. In such

cases it may be worthwhile to convert (4) into a formula

that clearly looks like a rank two, symmetric update

D_+I UT VkVkx = Dk + us _ - (21)

and utilize it in the updating algorithm. In equation (21)

vectors vk and u_ are expressed by

DkAg k _[a_ + pkbk

, uk Awk _v k

vk = _]a_ + pkbk b_

(22)

Obviously, when updating the D k matrix, its symmetric

property should also be exploited to avoid redundant

calculations with respect to either lower or upper triangle

part. Below, pseudo code is presented for executing the

ill il 7
extended BFGS variable metric update. Using this

scheme requires three times less multiplications in the

main routine loop in comparison to the procedure which

implements (4) directly.

'v" = D * Ag;

a = AgT * vl

b = Aw r * Ag;

if (a > 0.0 AND

b > macheps * (Aw T * Aw) *

{

a = sqrt(a + ro * b);

v = V / a;

u = a / b * Aw - v;

for (i = 0; i < n; i++)

(

a = u[i] ;

b = v[i];

D[i] [i] += a * a - b * b;

for (j = i + i; j < n; j++)

{

D[j] [i] = (D[i] [j] += a*u[j]-b*v[j]);

)

)

}

(AO r * Ag))

8. Numerical Experiments

Numerical experiments have been carried out to test the

performance of the scaled variable metric method

against other selected training techniques which are

known to be effective and frequently used in practice.

The following four training algorithms were chosen for

the comparison: (i) Levenberg-Marquardt (LM)

algorithm with the predicted error reduction (ref. 9),

(ii) standard BFGS method (ref. 2), (iii) limited memory

BFGS (ref. 9), and (iv) RPROP (ref. 10). Both BFGS

methods employed Brent's line search (ref. 11). A

common updating routine of the Ok matrix was

implemented in the identical fashion in the SVM method

as in other variable metric algorithms. All numerical

tests were performed on a Pentium 200 MHz personal

computer.

The performance comparison of the SVM method was

experimentally verified by training ten, 12-18-16-6

feedforward neural networks (12 input sensors, 6

outputs, 640 weights) using 1373 preprocessed data

points acquired from the calibration process of a sixcomponent wind tunnel strain-gage. Each of the ten

training experiments used the same starting point for all

the algorithms. Figure 3 presents the convergence curves

of the five training algorithms. Clearly, the simplest

RPROP algorithm exhibited the lowest convergence

rate. The standard BFGS method and its limited memory

version demonstrated a better performance but the SVM

algorithm was superior to these techniques. On average,

our algorithm was able to reach the error level of the

standard BFGS method in 250-350 iterations. The

steepest convergence curve belonged to the LevenbergMarquardt algorithm. However, since the neural model

had multiple outputs, the Levenberg-Marquardt training

was substantially slower than other methods, requiring

14 hours and 40 minutes to iterate 200 epochs. The SVM

method (run for 1000 epochs) was able to surpass the

Levenberg-Marquardt results in most cases, requiring

only 25 minutes on average to complete training. The

RPROP method was the fastest training technique in our

comparison. It is important to note, however, that for the

given problem, the RPROP algorithm was least accurate

of all the methods under consideration, even when the

number of iterations was increased to 5000. In this case,

execution time was approximately 25 minutes.

10"1

10 "z

training error

(a) - Levenberg-Marquardt

(b) - SVM

(c) - limited memon/BFGS

(b) (d) - standard BFGS

/mm(c ) (e) - RPROP

(a)

0 200 400 600 800 1000

iterations

Figure 3. Convergence curves of different training

algorithms.

9. Conclusions

In this report, we have presented a new scaled variable

metric (SVM) method for training feedforward neural

networks. The SVM technique utilizes the RBackprop

algorithm (ref. 8) and the modified variable metric

update, derived as a subclass of the Huang family

formulae. The variable metric method is used to collect

information about second derivatives of the error

function with respect to network weights. It allows us to

construct a relatively efficient strategy for choosing the

sequence of search directions. The variable metric

update was extended by an additional parameter Pk,

which plays a fundamental role in attempts to accelerate

the convergence speed of the training procedure. We

have shown that a special case of the Huang updating

formulae can be efficiently combined with the
variablemetricalgorithm(ref.6)toformanefficient

trainingscheme. Wehavepresentedanewstrategyfor

settingthescalingfactor,whichemphasizes the

importanceoflimitingunnecessary fluctuationsofPk.

The RBackprop algorithm can be utilized in two ways:

it allows us to avoid expensive one directional line

searches, and it can be used in supplementary, predictive

updating of the D k matrix. Predictive updating acquires

information about second derivatives along the trial

search direction before committing to the final step

which can be chosen more precisely. In addition, matrix

D k may benefit from the predictive updates by being able

to track changes of the Hessian matrix faster. We have

employed a modified strategy for adjusting the

parameter in the step length calculations using

directional slope testing. We have found that this

technique works exceptionally well in conjunction with

the RBackprop algorithm. Finally, we have outlined a

computationally more efficient scheme for updating the

D_ matrix. This is a somewhat overlooked aspect of

many variable metric implementations but it becomes a

rather important issue when large neural networks are

being trained.

Numerical experiments provide evidence that the

theoretical background developed to estimate an

appropriate range of settings for the Pk scalar indeed

works in practice, although the same theory indicates

that acceleration may not always be possible. For some

problems, where Pk = 1 is a suitable choice, the standard

BFGS method may be superior. In practical situations,

however, the SVM algorithm may protect the variable

metric algorithm from being stuck. The method also has

the capacity to perform a continuous adjustment of the

Pk parameter rather than rescale the initial matrix Do only

once. Interestingly, in some cases the initial scaling of

the Do matrix is not necessary, but later adjustment of the

Pk parameter improves the training convergence.

It seems that information provided by the RBackprop

algorithm and inferred from gradient vectors may be

more efficiently utilized in choosing the sequence of

search directions when the p_ scalar is allowed to be

tuned on-line. Our experience with the SVM method is

that its efficiency becomes evident when the size of the

neural architecture increases and/or the difficulty

achieving low error arises, perhaps due to the highly

non-quadratic nature of the optimization problem.

References

Battiti, R., First- and second-order methods for

learning: between steepest descent and

Newton's method, Neural Computation, 4,

1992, pp. 141-166.

2. Bishop, C.M., Neural Netw.orks for Pattern

Recognition, Oxford University Press, 1995.

, Luksan, L., Computational experience with known

variable metric updates, Journal of

Optimization Theory and Applications, Vol. 83,

No. I, 1994, pp. 27-47.

4. Wolfe, M.A., Numerical Methods for Unconstrained

Optimization, Van Nostrad Reinhold, 1978.

, Huang, H.Y., Unified approach to quadratically

convergent algorithms for function

minimization, Journal of Optimization

Theory and Applications, Vol. 5, No. 6, 1970,

pp. 405-423.

. Oren, S.S., and Luenberger, D.G., Self-scaling

variable metric (SSVM) algorithms, Part I and II,

Management Science, Vol. 20, No. 5, 1974, pp.

845-874.

, Moller, M.F., A scaled conjugate gradient algorithm

for fast supervised learning, Neural Networks

Vol. 66, No. 4, 1993, pp. 525-533.

. Pearlmutter, B.A., Fast exact multiplication by the

Hessian, Neural Computation, 6 (1), 1994,

pp. 147-160.

9. Fletcher, R., Practical Methods of Optimization,

John Wiley & Sons, 1987.

10. Riedmiller, M., and Braun, H., A direct adaptive

method for faster backpropagation learning: the

RPROP algorithm, IEEE Int. Conf. Neural

Networks, San Francisco, 1993, pp. 586-591.

11. Press, W.H., Teukolsky, S.A., Vetterling, W.T., and

Flannery, B.P., Numerical Recipes in C- The

Art of Scientific Computing, 2nd ed., Cambridge

University Press, 1992.

7 I?
Form Approved

REPORT DOCUMENTATION PAGE OMB NO. 0704-0188

Public reporting burden for this collection of information is estimated to average 1 hour per response, including the time for reviewing instructions, searching existing data sources,

ather ng and maintaining the data needed and completing and reviewing the collection of information. Send comments regarding this burden estimate or any other aspect of this

collection of information, including suggest ORS for reducing this burden, to Washington Headquarters Services, Directorate for information Operations and Reports, 1215 Jefferson

Davis Highway, Suite 1204, Arlington, VA 22202-4302, and to the Office of Management and Budget, Paperwork Reduction Project (0704-0188), Washington, DC 20503

1. AGENCY USE ONLY (Leave blank) 2. REPORT DATE 3. REPORT TYPE AND' DATES COVERED

" November 1998 Technical Memorandum

4. TITLE AND SUBTITLE 5. FUNDING NUMBERS

Accelerated Training for Large Feedforward Neural Networks

6. AUTHOR(S)

Slawomir W. Stepniewski and Charles C. Jorgensen

7. PERFORMING ORGANIZATION NAME(S) AND ADDRESS(ES)

Ames Research Center

Moffett Field, CA 94035-1000

9. SPONSORING/MONITORING AGENCY NAME(S) AND ADDRESS(ES)

National Aeronautics and Space Administration

Washington, DC 20546-0001

RTOP 519-30-12

8. PERFORMING ORGANIZATION

REPORT NUMBER

A9812323

10. SPONSORING/MONITORING

AGENCY REPORT NUMBER

NAS A/TM- 1998-112239

11. SUPPLEMENTARY NOTES

Point of Contact: Charles Jorgensen, Ames Research Center, 269-1, Moffett Field, CA 94035-1000

(650) 604-6725

12a. DISTRIBUTION/AVAILABILITY STATEMENT

Unclassified-Unlimited

Subject Category - 59

Availability: NASA CASI (301) 621-0390

13. ABSTRACT (Max/mum 200 words)

12b. DISTRIBUTION CODE

Distribution: Standard

In this paper we introduce a new training algorithm, the scaled variable metric (SVM) method. Our approach attempts to

increase the convergence rate of the modified variable metric method. It is also combined with the RBackprop algorithm,

which computes the product of the matrix of second derivatives (Hessian) with an arbitrary vector. The RBackprop

method allows us to avoid computationally expensive, direct line searches. In addition, it can be utilized in the new,

"predictive" updating technique of the inverse Hessian approximation. We have used directional slope testing to adjust the

step size and found that this strategy works exceptionally well in conjunction with the Rbackprop algorithm. Some

supplementary, but nevertheless important enhancements to the basic training scheme such as improved setting of a

scaling factor for the variable metric update and computationally more efficient procedure for updating the inverse

Hessian approximation are presented as well. We summarize by comparing the SVM method with four first- and secondorder optimization algorithms including a very effective implementation of the Levenberg-Marquardt method. Our tests

indicate promising computational speed gains of the new training technique, particularly for large feedforward networks,

i.e., for problems where the training process may be the most laborious.

14. SUBJECTERMS

Neural networks, Training, Optimization, Quasi-Newton methods, Variable

metric methods

17. SECURITY CLASSIFICATION 18. SECURITY CLASSIFICATION

OF REPORT OF THIS PAGE

Unclassified Unclassified

NSN 7540-01-280-5500

19. SECURITY CLASSIFICATION

OF ABSTRACT

15. NUMBER OF PAGES

14

16. PRICE CODE

A03

20. LIMITATION OF ABSTRACI

Standard Form 298 (Rev. 2-89)

Prescribed by ANSI Std. Z39-18

298-102
Y1I Ii