Second-order Learning Algorithm with
Squared Penalty Term

Kazumi Saito
Ryohei Nakano
NTT Communication Science Laboratories
2 Hikaridai, Seika-cho, Soraku-gun, Kyoto 619-02 Japan{saito,nakano}@cslab.kecl.ntt.jp

Abstract
This paper compares three penalty terms with respect to the eﬃciency of supervised learning, by using ﬁrst- and second-order learning algorithms. Our experiments showed that for a reasonably adequate penalty factor, the combination of the squared penalty term
and the second-order learning algorithm drastically improves theconvergence performance more than 20 times over the other combinations, at the same time bringing about a better generalization
performance.

1

INTRODUCTION

It has been found empirically that adding some penalty term to an objective function in the learning of neural networks can lead to signiﬁcant improvements in
network generalization. Such terms have been proposed on the basis of several
viewpoints such as weight-decay (Hinton, 1987), regularization (Poggio & Girosi,1990), function-smoothing (Bishop, 1995), weight-pruning (Hanson & Pratt, 1989;
Ishikawa, 1990), and Bayesian priors (MacKay, 1992; Williams, 1995). Some arecalculated by using simple arithmetic operations, while others utilize higher-orderderivatives. The most important evaluation criterion for these terms is how the generalization performance improves, but the learning eﬃciency is also an importantcriterion in large-scale practical problems; i.e., computationally demanding terms
are hardly applicable to such problems. Here, it is naturally conceivable that theeﬀects of penalty terms depend on learning algorithms; thus, we need comparativeevaluations.
This paper evaluates the eﬃciency of ﬁrst- and second-order learning algorithms

with three penalty terms. Section 2 explains the framework of the present learningand shows a second-order algorithm with the penalty terms. Section 3 shows experimental results for a regression problem, a graphical evaluation, and a penalty
factor determination using cross-validation.

2

LEARNING WITH PENALTY TERM

2.1

Framework

Let {(x1 , y1 ), · · · , (xm , ym )} be a set of examples, where xt denotes an n-dimensional
input vector and yt a target value corresponding to xt . In a three-layer neuralnetwork, let h be the number of hidden units, wj (j = 1, · · · , h) be the weightvector between all the input units and the hidden unit j, and w0 = (w00 , · · · , w0h )T
be the weight vector between all the hidden units and the output unit; wj0 means
a bias term and xt0 is set to 1. Note that aT denotes the transposed vector of a.
Hereafter, a vector consisting of all parameters, (w0T , · · · , whT )T , is simply expressedas Φ = (φ1 , · · · , φN )T , where N (= nh + 2h + 1) denotes the dimension of Φ. Then,the training error in the three-layer neural network can be deﬁned as follows:f (Φ) =



2
m 
h



1
yt − w00 +w0j σ(wjT xt ) ,


2
t=1

(1)

j=1

where σ(u) represents a sigmoidal function, σ(u) = 1/(1 + e−u ).
In this paper, we consider the following three penalty terms:NΩ1 (Φ) =

1 2
φk ,
2
k=1

Ω2 (Φ) =NN|φk |,Ω3 (Φ) =k=1

1  φ2k.
2
1 + φ2k(2)k=1Hereafter, Ω1 , Ω2 , and Ω3 are referred to as the squared (Hinton, 1987; MacKay,
1992), absolute (Ishikawa, 1990; Williams, 1995), and normalized (Hanson & Pratt,1989) penalty terms, respectively. Then, learning with one of these terms can bedeﬁned as the problem of minimizing the following objective function
Fi (Φ) = f (Φ) + µΩi (Φ),(3)

where µ is a penalty factor.
2.2

Second-order Algorithm with Penalty Term

In order to minimize the objective function, we employ a newly invented secondorder learning algorithm based on a quasi-Newton method, called BPQ (Saito &Nakano, 1997), where the descent direction, ∆Φ, is calculated on the basis of a partial BFGS update and a reasonably accurate step-length, λ, is eﬃciently calculated
as the minimal point of a second-order approximation. Here, the partial BFGS
update can be directly applied, while the step-length λ is evaluated as follows:
λ =−∇Fi (Φ)∆ΦT−∇Fi (Φ)∆ΦT
=
.
T
2
T
2
∆Φ ∇ Fi (Φ)∆Φ∆Φ ∇ f (Φ)∆Φ + µ∆ΦT ∇2 Ωi (Φ)∆Φ(4)

The quadratic form for the training error term, ∆ΦT ∇2 f (Φ)∆Φ, can be calculated eﬃciently with the computational complexity of N m + O(hm) by using theprocedure of BPQ, while those for penalty terms are calculated as follows:∆ΦT ∇2 Ω1 (Φ)∆Φ =N


∆φ2k ,∆ΦT ∇2 Ω2 (Φ)∆Φ = 0,

k=1

∆ΦT ∇2 Ω3 (Φ)∆Φ =N
(1 − 3φ2 )∆φ2k

k=1

(1 + φ2k )3

k

.

(5)

Note that, in the step-length calculation, ∆ΦT ∇2 Fi (Φ)∆Φ is basically assumed to
be positive. The three terms have a diﬀerent eﬀect on it, i.e., the squared penalty
term always adds a non-negative value; the absolute penalty term has no eﬀect; thenormalized penalty term may add a negative value if many weight values are larger
than 1/3. This indicates that the squared penalty term has a desirable feature.
Incidentally, we can employ other second-order learning algorithms such as SCG(Møller, 1993) or OSS (Battiti, 1992), but BPQ worked the most eﬃciently among
them in our own experience (Saito & Nakano, 1997).

3

EVALUATION BY EXPERIMENTS

3.1

Regression Problem
2

By using a regression problem for a function y = (1 − x + 2x2 )e−0.5x , the learning
performance of adding a penalty term was evaluated. In the experiment, a value ofx was randomly generated in the range of [−4, 4], and the corresponding value of y
was calculated from x; each value of y was corrupted by adding Gaussian noise witha mean of 0 and a standard deviation of 0.2. The total number of training examples
was set to 30. The number of hidden units was set to 5, where the initial values
for the weights between the input and hidden units were independently generated
according to a normal distribution with a mean of 0 and a standard deviation of
1; the initial values for the weights between the hidden and output units were set
to 0, but the bias value at the output unit was initially set to the average output
value of all training examples. The iteration was terminated when the gradientvector was suﬃciently small (i.e., ∇Fi (Φ)2 /N < 10−12 ) or the total processing
time exceeded 100 seconds. The penalty factor µ was changed from 20 to 2−19 bymultiplying by 2−1 ; trials were performed 20 times for each penalty factor.
Figure 1 shows the training examples, the true function, and a function obtained
after learning without a penalty term. We can see that such a learning over-ﬁtted
the training examples to some degree.
3.2

Evaluation using Second-order Algorithm

By using BPQ, an evaluation was made after adding each penalty term. Figure 2(a)compares the generalization performance, which was evaluated by using the average RMSE (root mean squared error) for a set of 5, 000 test examples. The best
possible RMSE level is 0.2 because each test example includes the same amount ofGaussian noise given to each training example. For each penalty term, the generalization performance was improved when µ was set adequately, but the normalized3true function
learning result

2
1
0
-4

-2

0

2

4

Figure 1: Learning problem
average RMSE
0.8

Ω2

0.6

CPU time (sec.)
100

Ω3

10

Ω3
without
penalty

without
penalty

0.4

1

Ω1

0.2
20

Ω2

Ω1

0.1
20
2-5
2-10
2-15
2-20 µ
2-5
2-10
2-15
2-20 µ(b) CPU time until convergence(a) Generalization performance

Figure 2: Comparison using second-order algorithm BPQ

penalty term was the most unstable among the three, because it frequently got
stuck in undesirable local minima. Figure 2(b) compares the processing time1 untilconvergence. In comparison to the learning without a penalty term, the squared
penalty term drastically decreased the processing time especially when µ was large,
while the absolute penalty term did not converge when µ was large; the normalized
penalty term generally required a larger processing time. Thus, only the squared
penalty term improved the convergence performance more than 2 ∼ 100 times,
keeping a better generalization performance for an adequate penalty factor.
3.3

Evaluation using First-order Algorithm

By using BP, a similar evaluation was made after adding each penalty term. Here,
we adopted Silva and Almeida’s learning rate adaptation rule (Silva & Almeida,1990), i.e., learning rate ηk for each weight φk is adjusted by the signs of two
successive gradient values2 . Figure 3(a) compares the generalization performanceand Figure 3(b) compares the processing time until convergence, where the average
processing time for the trials without a penalty term is not displayed because alltrials did not converge within 100 seconds. For each penalty term, the generalization
1

Our experiments were done on SUN S-4/20 computers.
The increasing and decreasing parameters were set to 1.1 and 1/1.1, respectively, as
recommended by (Silva & Almeida, 1990); if the value of the objective function increases,
all learning rates are halved until the value decreases.
2

average RMSE
0.8

0.6

Ω1
Ω2
Ω3

CPU time (sec.)
100

10

Ω1
Ω2
Ω3

without
penalty
1

0.4

0.1

0.2
20

2-5
2-10
2-15
2-20 µ(a) Generalization performance

20

2-5
2-10
2-15
2-20 µ(b) CPU time until convergence

Figure 3: Comparison using ﬁrst-order algorithm BP

performance was improved when µ was set adequately. Note that BP with thesquared penalty term Ω1 required more processing time than BPQ with Ω1 . As forthe normalized penalty term Ω3 , BP with Ω3 worked more stably than BPQ with
Ω3 . Incidentally, the generalization performance of BP without a penalty term wasbetter than that of BPQ without it; we predict that this is because the eﬀect ofearly stopping (Bishop, 1995) worked for BP. Actually, for the training examples,
the average RMSE of BP without a penalty term was 0.138, while that of BPQ
without it was 0.133.
3.4

Graphical Evaluation

In order to graphically examine the reasons why the eﬀect of the addition of eachpenalty term diﬀered, we designed a simple problem; that is, learning a functiony = σ(w1 x) + σ(w2 x), where only two weights, w1 and w2 , are adjustable. In thethree-layer network, the input and output layers consist of only one unit, while thehidden layer consists of two units. Note that the weights between the hidden units
and the output unit are ﬁxed at 1, there is no bias, and the activation functionof hidden units is assumed to be σ(x) = 1/(1 + exp(−x)). Each target value yt
was calculated from the corresponding input value xt ∈ {−0.2, −0.1, 0, 0.1, 0.2} bysetting (w1 , w2 ) = (1, 3).
Figure 4 shows the learning trajectories on error contour maps with respect to w1
and w2 during 100 iterations starting at (w1 , w2 ) = (−1, −3), where the penalty
factor µ was set to 0.1 or 0.01. Here, BPQ was used as a learning algorithm. The
contours for the squared penalty term form ovals, making BPQ learn easily. Whenµ = 0.1, the contours for the absolute penalty term form an almost square-likeshape, and the learning trajectories oscillate near the origin (w1 = w2 = 0), due tothe discontinuity of the gradient function. The contours for the normalized penalty
term form a valley, making BPQ’s learning more diﬃcult.
3.5

Determining Penalty Factor

In general, for a given problem, we cannot know an adequate penalty factor inadvance. Given a limited number of examples, we must ﬁnd a reasonably adequatew25Ω1 ( µ=0.1 )
1
0.5
0.1

w2
5

Ω2 ( µ=0.1 )
0.1

w2
5

0

0.1
0.05

0.05

0

Ω3 ( µ=0.1 )
0.1

0
0.5

-5
-5
w2
5

0

0.5
-5
-5
0
0
5 w1 -5
5 w1 -50
5 w1
w2 Ω2 ( µ=0.01 )w2 Ω3 ( µ=0.01 )Ω1 ( µ=0.01 )
5
5
0.1
0.1
0.05
0.1
0.1
0.05
0.05
0.05
0.5 0.1
0
0
0.5

-5
-5

0

5 w1

0.5
-5
-5

0

-5
5 w1 -50

5 w1

Figure 4: Graphical evaluation

penalty factor. The procedure of cross-validation (Stone, 1978) is adopted for thispurpose. Since we knew the combination of the squared penalty term Ω1 and thesecond-order algorithm BPQ works very eﬃciently, we performed experiments using
the above regression problem with exactly the same experimental conditions.
Figure 5 shows the experimental results, where the procedure of cross-validation
was implemented as a leave-one-out method, and the initial weight values for evaluating the cross-validation error were set as the learning results of the entire training
examples. Figure 5(a) compares the average generalization error and the averagecross-validation error. Although the cross-validation error was a pessimistic estimator of the generalization error, it showed the same tendency and was minimized at
almost the same penalty factor. Figure 5(b) shows the average processing time andits standard deviation; although the processing time includes the cross-validation
evaluation, we can see that the learning was performed quite eﬃciently.

4

CONCLUSION

This paper investigated the eﬃciency of supervised learning with each of threepenalty terms, by using ﬁrst- and second-order learning algorithms, BP and BPQ.
Our experiments showed that for a reasonably adequate penalty factor, the combination of the squared penalty term and the second-order algorithm drastically
improves the convergence performance about 20 times over the other combinations,
together with an improvement in the generalization performance. In the case ofother second-order learning algorithms such as SCG or OSS, similar results are possible because the main diﬀerence between BPQ and those other algorithms involves
only the learning eﬃciency. In the future, we plan to do further evaluations usinglarger-scale problems.

average RMSE
0.8

CPU time (sec.)100
cross-validation error

averagegeneralization error

s.d.

0.6

10

0.4

1

0.2
20

0.1
20
2-5
2-10
2-15
2-20 µ
2-5
2-10
2-15
2-20 µ(b) CPU time until convergence(a) Generalization performance

Figure 5: Learning result

References
Battiti, R. (1992) First- and second-order methods for learning between steepest
descent and Newton’s method. Neural Computation 4(2):141–166.
Bishop, C.M. (1995) Neural networks for pattern recognition. Clarendon Press.
Hanson, S.J. & Pratt, L. Y. (1989) Comparing biases for minimal network construction with back-propagation. In D. S. Touretzky (ed.), Advances in Neural
Processing Systems, Volume 1, pp. 177–185. San Mateo, CA: Morgan Kaufmann.
Hinton, G.E. (1987) Learning translation invariant recognition in massively parallel
networks. In J. W. de Bakker, A. J. Nijman and P. C. Treleaven (eds.), Proceedings
PARLE Conference on Parallel Architectures and Languages Europe, pp. 1–13.
Berlin: Springer-Verlag.
Ishikawa, M. (1990) A structural learning algorithm with forgetting of link weight.
Tech. Rep. TR-90-7, Electrotechnical Lab. Tsukuba-City, Japan.
MacKay, D.J.C. (1992) Bayesian interpolation. Neural Computation 4(3):415–447.
Møller, M.F. (1993) A scaled conjugate gradient algorithm for fast supervised learning. Neural Networks 6(4):525–533.
Poggio, T. & Girosi, F. (1990) Regularization algorithms for learning that are equivalent to multilayer networks. Science 247:978–982.
Saito, K. & Nakano, R. (1997) Partial BFGS update and eﬃcient step-length calculation for three-layer neural networks. Neural Computation 9(1):239–257 (in press).
Silva, F.M. & Almeida, L.B. (1990) Speeding up backpropagation. In R. Eckmiller(ed.), Advanced Neural Computers, pp. 151–160. Amsterdam: North–Holland.
Stone, M. (1978) Cross-validation: A review. Operationsforsch. Statist. Ser. Statistics B 9(1):111–147.
Williams, P.M. (1995) Bayesian regularization and pruning using a Laplace prior.
Neural Computation 7(1):117–143.