数理解析研究所講究録1098 巻 1999 年 23-41

23

可積分系によるニューラルネットワークの学習の解析

Learning in neural networks and an integrable system
福水健次
理化学研究所

Kenji Fukumizu
The Institute of Physical and Chemical Research (RIKEN)-mail: fuku@brain.riken.go.jp$\mathrm{E}$

Abstract
This paper investigates the dynamics of batch learning of multilayer neural networks in the asymptotic case where the number of training data is much larger than
the number of parameters. First, we present experimental results on the behavior in
the steepest descent learning of multilayer perceptrons and three-layer linear neuralnetworks. We see in these results that strong overtraining, which is the increase ofgeneralization error in training, occurs if the model has surplus hidden units to realize
the target function. Next, to analyze overtraining from the theoretical viewpoint, weanalyze the steepest descent learning equation of a three-layer linear neural network,and theoretically show that a network with surplus hidden units presents overtraining.
From this theoretical analysis, we can see that overtraining is not a feature observedin the final stage of learning, but it occurs in an intermediate time interval.

1

Introduction

This paper discusses the dynamics of batch learning in neural networks. Multilayer
networks like multilayer perceptrons have been extensively used in many engineering applications, in hope that their nonlinear structure inspired by biological neural networks
shows a variety of advantages. However, nonlinearity causes weaknesses also. For the
training of a neural network, for example, a numerical optimization method like the error back-propagation (Rumelhart et al., 1986) must be used to find the optimal weightand bias parameters. It is very important from the practical and theoretical viewpoints
to elucidate the dynamical behavior of a network in training. Especially, the empiricalerror, the objective function of minimization, and the generalization error, the difference
between the target function and its estimate, are of much interest in many researches.
However, the property of such learning rules have not been clarified completely becauseof its complex nonlinearity.
In this paper, we focus on overtraining (Amari, 1996) as a typical behavior of learning
in multilayer networks. Overtraining is the increase of the generalization error after some

24

IIIUU

$\langle$$\mathrm{U}\mathrm{U}\mathrm{l}1\ovalbox{\tt\small REJECT} 1$

UI 1R1 $a$ UUII$J$

Figure 1: Overtraining in batch learning. The empirical error decreases during iterative training,
while the generalization increases after some time point.

time point in learning (Fig.1). Although the empirical error is a decreasing functionin principle, it does not ensure the decrease of the generalization error defined by only
finite number of training examples. Overtraining is not only of theoretical interest but ofpractical importance, because we should use an early stopping technique if overtraining
really exists.
There has been a controversy about the existence of overtraining. Some practitioners
assert that overtraining often happens and propose early stopping methods. Amari etal. (1996) analyze overtraining theoretically and conclude that the effect of overtraining
is much smaller than what is believed by practitioners. Their analysis is true if theparameter approaches to the global minimum of the empirical error following the statistical
asymptotic theory (Crame’r, 1946). However, the usual asymptotic theory cannot beapplied in overrealizable cases, where the model has surplus hidden units to realize thetarget function (Fukumizu, 1996; Fbkumizu, 1997). Possibility of an overrealizable target
is a common property of multilayer models, and the existence of overtraining in such cases
has still been an open problem.
There have been other studies related to overtraining. Baldi and Chauvin (Baldi &Chauvin, 1991) theoretically analyze the generalization error of two-layer linear networks
estimating the identity function from noisy data. Although they show overtraining phenomena under several assumptions, their analysis is very limited in that the overtraining
can be observed only when the variance of the noise in the training sample is different fromthat of the validation sample. In researches from the viewpoint of statistical mechanics,
overtraining is sometimes used for a different meaning. They observe the increase of thegeneralization error in online learning when the number of data is smaller than the number

25

of parameters, and call it overtraining.
The main purpose of this paper is to discuss overtraining of multilayer networks inconnection with overrealizability. We investigate two models: one is multilayer perceptrons
with the sigmoidal activation function, and the other is linear neural networks, which we
introduce for the simplicity of analysis. Through experimental results of these models, we
can conjecture that overtraining occurs for overrealizable targets. We theoretically verify
this conjecture in linear neural networks.
This paper is organized as follows. Section II gives basic definitions and terminology.
Section III shows experimental results concerning overtraining of multilayer perceptrons
and linear neural networks. In Section IV, we theoretically show the existence of overtraining in overrealizable cases of linear neural networks. Section V includes concluding
remarks.

2

Preliminaries

2.1

Framework of statistical learning

In this section, we present basic definitions and terminologies used in this paper. A feedforward neural network model can be defined by a parametric family of maps $\{f(x;\theta)\}$, where is an input vector and 9 is a parameter vector. The three-layer
fromtonetwork model with $H$ hidden units is defined by$\mathbb{R}^{L}$$\mathbb{R}^{M}$$x$$f^{i}(_{X;} \theta)=j=1\sum Hw_{ij\varphi}(_{k=1}\sum^{L}u_{jkk}x+\zeta_{j})+\eta_{i}$whereis a function fromtion
if the sigmoidal function$\theta=$$\varphi(t)$,(1)$(1\leq i\leq M)$, and an activation functo . We call a three-layer network a multilayer perceptron,$(w_{11}, \ldots, w_{MH}, \eta_{1}, \ldots , \eta_{M}, u_{11}, \ldots, u_{HL}, \zeta_{1}, \ldots , \zeta_{H})$$\mathbb{R}$$\mathbb{R}$(2)$\varphi(t)=\frac{1}{1+e^{-t}}$

is used for the activation function.
We use such a model for regression problems, assuming that an output of the target
system is observed with a measurement noise. A sample $(x, y)$ from the target system
satisfies$y=f(X)+v$ ,(3)where $f(x)$ is the target function which is unknown to a learner, and is a random vector
for theas its variance-covariance matrix. We writewith as its mean and
$v$

$0$

$\sigma^{2}I_{M}$$I_{M}$

26

unit matrix. An input vector is generated randomly with its probability density
function $q(x)$ , which is unknown to a learner. ’baining data $\{(x^{(\nu)}, y)(\nu)|\mathcal{U}=1, \ldots , N\}$. The parameter 9
are independent samples from the joint distribution of $q(x)$ and$f(x)$
so that a neural network
is estimated based on the training data without knowing$f(x)$.
can give a good estimate of the target function
We discuss the least square error (LSE) estimator. The objective of training is to findthe parameter that minimizes the following empirical error:$M\cross M$$x$$\mathrm{e}\mathrm{q}.(3)$$\mathrm{E}_{emp}(\theta)\equiv\sum_{\nu=1}||yNf(\nu)-(X(\nu)\theta);||^{2}$.

(4)

Generally, it is very difficult to solve the LSE estimator analytically if the model is nonlinear. Some numerical optimization method is needed to obtain an approximation. One
widely-used method is the steepest descent method, which iteratively updates the param. The
eter vector 9 in the steepest descent direction of the error surface defined bylearning rule is given by$\mathrm{E}_{emp}(\theta)$$\theta(t+1)=\theta(t)-\beta\frac{\partial \mathrm{E}_{emp}(\mathit{9}(t))}{\partial\theta}$,(5)where $\beta>0$ is a learning constant. In this paper, we discuss only batch learning, in which
we calculate the gradient using all the training data. There are many researches on online
learning, in which the parameter is always updated for a newly generated data (Heskes&
Kappen, 1991).
The performance of a network is often evaluated by the generalization error, which
represents the average error between the target function and its estimate. More precisely,
it is defined by.

(6)$\mathrm{E}_{gen}(\mathit{9})\equiv\int||f(x;\theta)-f(x)||2q(x)dX$

It is easy to see$\int\int||y-f(X;\mathit{9})||2p(y|X)q(X)dydx=M\sigma^{2}+\mathrm{E}_{gen}$,(7)

where $p(y|x)$ is the density function of the conditional probability of given . Since thewhen $N$ goes to
empirical error divided by $N$ approaches to the left hand side of
infinity, the rninimization of the empirical error roughly approximates the minimization of
the generalization error. However, they are not exactly the same, and the decrease of theempirical error during learning does not ensure the decrease of the generalization error. It
is extremely important to elucidate the dynamical behavior of the generalization error. A
error as a function of time is called a learning
curve showing the$y$$\mathrm{e}\mathrm{q}.(7)$$\mathrm{e}\mathrm{m}\mathrm{p}\mathrm{i}\mathrm{r}\mathrm{i}\mathrm{c}\mathrm{a}\mathrm{l}/\mathrm{g}\mathrm{e}\mathrm{n}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{z}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$curve.

$x$

27

TargetModel

Figure 2: Illustration of an overrealizable case.
In our theoretical discussion, we consider the case where $f(x)$ is perfectly realized by
the prepared model; that is, there is a true parametersuch that $f(x;\mathit{9}0)=f(x)$ .
Assume that the model has $H$ hidden units. If the target function $f(x)$ is realized bya network with a smaller number of hidden units than $H$ , we call it overrealizable (seeFig.2). Otherwise, we call it regular. We focus on the difference of dynamical behaviors
between these two cases.
$\theta_{0}$2.2Linear neural networks

We introduce the three-layer linear neural network model as the simplest multilayer
model whose theoretical analysis is possible. We must be very careful in discussing experimental results on learning of a multilayer perceptron especially in an overrealizable case.
In such a case, around the global minimum there exists a high-dimensional subvariety on
which
is very close to the minimum (Fukumizu, 1997). The convergence of learning
is much slower than the convergence in regular cases because the gradient is very small
around this subvariety. In addition, of course, learning with a gradient method suffers fromlocal minima, which is a common problem to all nonlinear models. We cannot exclude
their effects, and this often makes derived conclusions obscure. On the other hand, thetheoretical analysis of linear neural networks is possible (Baldi&Hornik, 1995; Fukumizu,
1997), and the dynamical behavior of the generalization error is analyzed in Section 4.
A linear neural network has the identity function for the activation function. In thispaper, we do not use the bias terms and in linear neural networks for simplicity. Thus,$\mathrm{E}_{emp}$$\eta$$\zeta$28

a linear neural network is defined by(8)$f(x;A, B)=BAx$ ,where is a $H\cross L$ matrix and $B$ is a $M\cross H$ matrix. We assume $H\leq L$ and $H\leq M$
the assumption
throughout this paper. Although the function $f(x;A, B)$ is linear,, but is thetoon $H$ , the model is not equal to the set of all the linear maps fromset of the linear maps of rank no greater than $H$ . Then, it is not equivalent to the usual
matrix). In this sense, the three-layer
linear regression model $f(x;c)=Cx$ ( $C$ :linear neural network model is the simplest multilayer model.
$A$$\mathrm{h}\mathrm{o}\mathrm{m}$$\mathbb{R}^{M}$$\mathbb{R}^{L}$$M\mathrm{x}L$3

Learning curves–experimental study-

In this section, we experimentally investigate the generalization error of multilayer perceptrons and linear neural networks to see their actual behaviors, emphasizing on overtraining.
in multilayer perceptron leads the well-known
The steepest descent method
1986),
which is given byerror back-propagation rule (Rumelhart,$(\mathrm{e}\mathrm{q}.(5))$,$w_{ij}(t+1)$$=$$w_{ij}(t)+ \beta\sum_{\nu}N=1i\delta^{(\nu)}(t)s_{j}^{(}(\nu)t)$$\eta_{i}(t+1)$$=$$\eta_{i}(t)+\beta\sum^{N}\nu=1\delta^{()}i\nu(t)$$u_{jk()}t+1$$=$$u_{jk}(t)+ \beta\sum^{N}\nu=1^{\sum w_{ij}\delta_{i}}i=M1(\nu)(t)_{S_{j}}(\nu)(t)(1-S(\nu)(jt))Xk(\nu)$$\zeta_{j}(t+1)$$=$$\zeta_{j(t)+\beta\sum\sum_{i1}}\nu=N1M=wij\delta_{i}(\nu)(t)_{S_{j}}(\nu)(t)(1-s_{j}(\nu)(t))$

,
,

,

(9)

where
$\delta_{i}^{(\nu)}(t)=yi(\nu)-f_{i}(X)(\nu;\mathit{9}(t))$,$s_{j}^{(\nu)}(t)=s( \sum_{k=1}^{L(}u_{j}k(t)X_{k}+\zeta j(\nu)t))$

.

(10)

To avoid the problems discussed in Section 2.2 as much as possible, we adopt the following
configuration in our experiments. The model in use has 1 input unit, 2 hidden units, and1 output unit. For a fixed set of training examples, 30 different values are tried for an
initial parameter vector. We select the trial that gives the least empirical error after 500000
iterations. Figure 3 shows the average of generalization errors over 30 different simulations
changing the set of training data. It shows clear overtraining in the overrealizable case. On
the other hand, the learning curve in the regular case shows no meaningful overtraining.
It is known that the LSE estimator of the linear neural network model can be analyticallysolvable (Baldi&Hornik, 1995). Although it is practically absurd, of course, to use thesteepest descent method, our interest is not only the optimal estimator but the dynamics
of learning. Therefore, we perform the steepest descent learning of linear neural networks

29

Figure 3: Average learning curves of MLP. The input samples are independent samples from. The total, and the output samples include the observation noise subject tonumber of training data is 100. The constant zero function is used for the overrealizable targetfunction, and $f(x)=s(x+1)+s(x-1)$ is used for the regular target. The dotted line shows thetheoretical expectation of the generalization error of the LSE estimator when the target function
is regular and the usual asymptotic theory is applicable.
$N(\mathrm{O}, 10^{-4})$$N(\mathrm{O}, 4)$here. For the training data of a linear neural network, we use the notations;

$X=$

,

$\mathrm{Y}=$ .

(11)

The empirical error can be written by$\mathrm{E}_{emp}=\mathrm{b}[(\mathrm{Y}-xA\tau B^{\tau})T(Y-XATB\tau)]$

(12)

.

The learning rule of a linear neural network is given by$A(t+1)$$=A(t)+\beta\{B^{T}Y^{\tau\tau}X-BBAX^{\tau}X\}$$B(t+1)$$=B(t)+\beta\{\mathrm{Y}\tau XAT-BAx\tau xAT\}$

$\{$

,

(13)

.

are saddle
It is also known that all the critical points but the global minimum of
points (Baldi&Hornik, 1995). Therefore, if we theoretically consider a continuous-timelearning equation, it converges to the global minimum for almost all initial conditions.
Figure 4 shows the average of learning curves for 100 simulations with various training
data from the same probability. The number of input units, hidden units, and output
units of the model are 5, 3, and 5 respectively. All the overrealizable cases show clear
overtraining. while the regular case does not show meaningful overtraining. We can also
see that overtraining is stronger when the rank of the target is smaller.
$\mathrm{E}_{emp}$

30

Figure 4: Average learning curves of linear neural networks. The input samples are independent
samples from $N(0, I_{5})$ , and the output samples include the observation noise subject to $N(0,10^{-2})$ .
The total number of training data is 100. The dotted line shows the theoretical expectation of thegeneralization error of the LSE estimator for the regular target.
From these results, we can conjecture that there is an essential difference in the dynamics of learning between regular and overrealizable cases, and overtraining is a universal
property of the latter cases. If we use a good stopping criterion, the multilayer networks
may have an advantage over conventional linear models, in that the degrade of the generalization error by redundant parameters is not so critical as conventional linear models.
Such overtraining in overrealizable cases has not been explained theoretically yet. In thenext section, we theoretically verify the result in linear neural networks by obtaining thesolution of the steepest descent learning equation.

31

4

Solvable dynamics of learning in linear neural networks

To verify the existence of overtraining in linear neural networks, we analyze the continuoustime differential equation instead of the discrete-time learning rule. Although the behaviorof the continuous one and the discrete one are not identical, they show very similar qualitative behaviors in computer simulations. We further approximate the differential equation
to derive a solvable one. This approximation also affects the solution quantitatively. However, we can see in experiments that similar the original one and the approximated one
show similar properties in their learning curves, and we can show the existence of overtraining in overrealizable cases.

4.1

Solution of. learning dynamics

In the rest of the paper, we put the following assumptions;(a) $H\leq L=M$ ,(b) $f(x)=B0A0X$ ,(c)$\mathrm{E}[xx^{T}]=\tau^{2}I_{L}$,(d) $A(0)A(0)^{\tau}=B(0)^{\tau_{B(}}\mathrm{o})$ ,(e) The rank of$A(\mathrm{O})$(or, equivalently under (d), the rank of$B(\mathrm{O})$) is $H$ .

Under these assumptions,and $B$ are $L\cross H$ matrixes. The parameterization of a linear
neural network has
dimensional redundancy by the multiplication of $H\cross H$ nonsingularmatrix from the left of and its inverse from the right of . The initial condition (d)does not restrict possible initialization, since it reduces this redundancy with $\frac{1}{2}H(H+1)$
restrictions. The assumption (e) is important in the following discussion. If the rank of(or) is less than $H$ , the final state of the variables changes, while we do notdiscuss it in this paper.
If we divide the output as$A^{T}$$H^{2}$$A$$A(\mathrm{O})$$B$$B(\mathrm{O})$

,

(14)

$\mathrm{Y}=XA_{00}^{\tau_{B^{\tau}V}}+$the differential equation of the steepest descent learning is given by$\lrcorner\dot{4}$$=\beta(B\tau B_{0}A_{0}X\tau x+B^{T}V\tau x-B\tau BAX\tau x)$$\{$$\dot{B}$$=\beta(B_{00}Ax^{T\tau}xA+V^{T}XA^{\tau}-BAX^{T}XA\tau)$

.

,

(15)

This is a nonlinear differential equation which has the terms of the third order. Let$Z_{O}:= \frac{1}{\sigma}V^{\tau}X(XTx)^{-1}/2$ . It is easy to see thatis independent of $X$ , and that all theelements ofare mutually independent and subject to. We decompose $X^{T}X$ as$Z_{O}$$Z_{O}$$N(\mathrm{O}, 1)$$X^{T}X=\tau^{2}NI_{L}+\tau^{2\sqrt{N}z_{I}}$

,

(16)

32

are subject towhere the off-diagonal elements of$N$subject to $N(0,2)$ if goes to infinity. Let$Z_{I}$$N(\mathrm{O}, 1)$

and the diagonal elements are$F=B_{0}A_{0}+ \frac{1}{\sqrt{N}}(B_{0}A_{0}Z_{I}+\frac{\sigma}{\tau}Z_{O})$

.

(17)

We neglect the order $O(\sqrt{N})$ in the nonlinear terms to derive a solvable equation, andbyapproximate$\mathrm{e}\mathrm{q}.(15)$$I\dot{4}$$=\beta\tau^{2}NBTF-\beta \mathcal{T}2NB^{T}BA$$\dot{B}$$=\beta\tau^{2\tau}NFA-\beta_{\mathcal{T}N}2BAA^{\tau}$$\{$

is a good approximation of the original
We further put an assumption:$\mathrm{E}\mathrm{q}.(18)$$\mathrm{e}\mathrm{q}.(15)$

,

(18)

.

if $N$ is very large.

(f) The rank of $B(0)+FA(0)^{T}$ is $H$ .

This assumption is a technical one, which is used to prove overtraining. The assumption(f) is almost always satisfied if the initial condition is independent of $F$ .
and the assumption (d).
We have $AA^{T}=B^{T}B$ because of the fact
$2L\crossH$matrixIf we introduce$\frac{d}{dt}(AA^{T})=\frac{d}{dt}(B^{T}B)$$R=$ ,(19)

then, $R$ satisfies the differential equation,$\frac{dR}{dt}=\beta\tau^{2}NSR-\frac{\beta\tau^{2}N}{2}RR^{T}R$

where

$S=$

.

(20)

This is very sinilar to Oja’s learning equation (Oja, 1989; Yan et al., 1994), or the generalized Rayleigh quotient (Helmke&Moore, 1994), which is known to be a solvable nonlinear
differential equation (Yan et al., 1994).
is to derive the differential equation on $RR^{T}$ :The key fact to solve$\mathrm{e}\mathrm{q}.(20)$.

$\frac{d}{dt}(RR^{T})=\beta\tau^{2}NsRR^{\tau}+\beta_{\mathcal{T}^{2}N}RR\tau s-\beta \mathcal{T}^{2T}N(RR)2$(21)

This is a matrix Riccati differential equation and well-known to be solvable. We have thefollowingis full. Then, the Riccati differential equation
Theorem 1. Assume that the rank of(21) has a unique solution for all $t\geq 0$ , and the solution is given by$R(\mathrm{O})$$R(t)R^{T}(t)=e^{\beta\tau^{2}N}Rst( \mathrm{o})[I_{H}+\frac{1}{2}R(\mathrm{o})T\{e^{\beta_{\mathcal{T}^{2}N}t}S-1\beta \mathcal{T}NSt-se-1\}S2R(\mathrm{o})]^{-1}R(0)^{T\beta t}e\tau N2S$

(22)

.

33

For the proof, see Sasagawa (1982) and Yan et al. (1994). Using this theorem, we easily
obtain the following theorem in the same manner as Yan et al. (1994, Theorem 2.1).
Theorem 2. Assume that the rank ofis full. Then, the differential equation (20)has a unique solution for all $t\geq 0$ , and the solution is expressed as$R(\mathrm{O})$$R(t)$$=$$e^{\beta_{\mathcal{T}^{2}}NS}tR( \mathrm{o})[I_{H}+\frac{1}{2}R(0)^{\tau}\{e\tau\beta 2Ns_{S^{-}}t1\beta\tau^{2}Nst-se-1\}R(0)]^{-\frac{1}{2}}U(t)$,(23)

where $U(t)$ is a $H\cross H$ orthogonal matrix.

4.2

Dynamical behavior of the generalization error

In this subsection, we write
for the set of realassumption (c), the generalization error is written as$M(l\cross n;\mathbb{R})$$l\cross n$$\mathrm{E}_{gen}=\tau^{2}\mathrm{b}[(BA-B0A_{0})(BA-B0^{A_{0})^{\tau}}]$It is easy to see that the derivative of$\frac{d}{dt}\mathrm{E}_{gen}=\beta\tau^{4}N$$\mathrm{E}_{gen}$matrixes. Using the

.

(24)

is

{Tr $[(F-BA)A^{\tau}A(BA-B_{0^{A0}})^{\tau}]+\mathrm{n}[BB^{\tau_{()(}T}F-BABA-B0^{A_{0})}]$ }(25)

Note that a transform of the input or output vectors by an orthogonal matrix does notchange the generalization error. Therefore, using the singular value decomposition ofis diagonal;
we can assume without loss of generality that
$B_{0}A_{0}$$B_{0^{A}0_{)}}$$B_{0}A_{0=}$ ,$\Lambda^{(0)}=$ ,

(26)

, and
.
where is the rank ofare the singular values of
$H$
.
if
equal
The target function is overrealizable and only if
The rank isto or less than$r<H$ .
We employ the singular value decomposition of $F$ ,$\lambda_{1}^{(0)}\geq\cdots\geq\lambda_{r}^{(0)}>0$$B_{0}A_{0}$$r$$B_{0}A_{0}$$r$$F=W\Lambda U^{T}$

In this equation,$U$

and $W$ are

$L$

.

(27)

dimensional orthogonal matrixes, and$\Lambda=$ ,

(28)

34

where

are the singular values of . We assume that$F$$\lambda_{1}\geq\lambda_{2}\geq\cdots\lambda_{L}\geq 0$$\lambda_{1}>\lambda_{2}>\cdots>$. This is satisfied almost surely because of the stochastic noise in $F$ . We write, forsimplicity,$\lambda_{L}>0$

(29)

,

$F=B_{0}A_{0}+\mathcal{E}Z$

where
(g)

$\epsilon=\frac{1}{\sqrt{N}}$. We further put an assumption:$\lambda_{r}^{(0)}>>\epsilon$and$1\gg\epsilon$.

The above assumption asserts that the number of data is large enough to discriminate
and the stochastic deviation from zero. We say is of the constant order if
between.
It is known that a small perturbation of a matrix causes a perturbation of the sameorder to the singular values (see Bartia, 1997, Section III, for example). The diagonal
matrix A is decomposed as$\lambda_{r}^{(0)}$$a$$a>>\epsilon$$\Lambda=$ ,

(30)

where

$\Lambda_{1}==$

,

(31)

$\epsilon\tilde{\Lambda}_{2}==$ ,(32)$\epsilon\tilde{\Lambda}_{3}==$ .

(33)

Note that the normalized singular values
The purpose of this subsection is to show that$\overline{\lambda}_{j}(r+1\leq j\leq L)$

are of the constant order.
(34)$\frac{d}{dt}\mathrm{E}_{gen}>0$

if $r<H$ (overrealizable) and$t$satisfies$\frac{1}{\beta\tau^{2\sqrt{N}}(\tilde{\lambda}_{H}-\tilde{\lambda}H+1)}<<t<<\frac{\log\sqrt{N}}{\beta\tau^{2}\sqrt{N}(\tilde{\lambda}H-\tilde{\lambda}H+1)}$

.

(35)

35

If this is proved, it means the existence of overtraining in overrealizable cases. Before
entering into the details, we give an intuitive description of what happens in the learning
process of a network (Fukumizu, 1998). The final state of the solution can be written by$W\Lambda^{\frac{1}{2}}\Lambda^{\frac{1}{2}}U^{T}$

.

(36)

This can be considered as the projection of A to the first $H$ eigenspaces. We can deducethat the solution is also approximately considered to be a projection of A tofrom
$H$exponentially. An important point is
a dimensional subspace, which converges tothat the convergence speed of the first components and the rest are different if $r<H$ .
The order of the former is roughly $o(e^{-aNt})$ and the latter is $o(e^{-b\sqrt{N}t})$ for some constantand . When the slow dynamics of the latter is the leading factor, the subspace of the
projection is approximately$\mathrm{e}\mathrm{q}.(22)$$I_{H}$

$r$

$a$

$b$

$\Pi=(_{0}^{I_{r}}0$$o(e^{-})I_{Hr)}\mathrm{o}-\sqrt{N}t$

.

(37)

It is easy to see the shrinkage of the components corresponding to $H-r$ redundant pa. This suppresses the effect of stochastic
rameters in the projection
noise and makes a better estimation than the final one.
Let us start the theoretical verification with the singular value decompositions to simplify. We have$\Lambda^{-\frac{1}{2}}\Pi(\Pi\tau\Pi)-1_{\Pi}\tau_{\Lambda^{-}}\frac{1}{2}$$\mathrm{e}\mathrm{q}.(25)$$S=\Phi\Phi^{T}$ ,(38). From the assumption (d), the singular value decomposition ofwhere
has the following form;$\Phi=\frac{1}{\sqrt{2}}(_{W-W}^{UU})$$R(\mathrm{O})$$R(0)=\Theta J\Gamma G^{\tau}$

,

(39)

where

$J=$ , and $\Gamma=$ .

$\Theta=$ ,(40)

The matrixes $P,$ and are $L,$ , and $H$ dimensional orthogonal matrixes respectively.
Because of the assumption (e), is invertible. Using these decompositions, $RR^{T}$ can be
$Q$

$L$

$G$

$\Gamma$36

rewritten as$RR^{T}=\Phi(e^{\beta\tau_{0}^{2}N}0\Lambda te^{-\beta N\Lambda}\tau^{2}t)\Phi^{T}\Theta J$$\cross[\Gamma^{-2}+\frac{1}{2}J\tau\ominus\tau_{\Phi\{}-\}\Phi^{T}\ominus J]^{-1}$$\mathrm{x}J^{T}\ominus T\Phi(e^{\beta\tau_{0}^{2}}0N\Lambda te^{-\beta_{\mathcal{T}N}}2\Lambda t)\Phi^{T}$. (41)

Let $C=(U^{T}P+W^{T}Q)$ and $D=(U^{\tau_{P-W}\tau}Q)$ . Decompose these two matrixes as$C=$ , $D=$ ,where$C_{H},$ $D_{H}\in M(H\cross H;\mathbb{R})$, and$C_{3},$$D_{3}\in M((L-H)\cross H;\mathbb{R})$(42). Then, we have$\Phi^{T}\Theta J=\frac{1}{\sqrt{2}}$ ,(43). Sincewhereis invertible. If we introducetion (f) assures that

$B(0)+FA(0)^{T}=Q(_{\mathit{0}}^{\mathrm{r}})G^{T}+W\Lambda U\tau P(_{\mathit{0}}\Gamma)c^{\tau_{7}}$$\Lambda_{H}=(_{0}^{\Lambda_{1}}\Lambda_{2}0)$

the assump-$C_{H}$$K=$$\mathrm{e}\mathrm{q}.(41)$(44)

can be rewritten as$RR^{T}=2\Phi(_{0}^{\Lambda^{\frac{1}{2}}}$$\sqrt{-1}\Lambda^{\frac{1}{2}\mathrm{I}^{K}\Psi}0-1KT(_{0}^{\Lambda^{\frac{1}{2}}}$$\sqrt{-1}\Lambda^{\frac{1}{2})}0\Phi^{T}$

,

(45)

where
$\Psi=K^{\tau_{K+\Lambda}\frac{1}{H2}\beta N\Lambda_{H}}e^{-}\tau 2tC_{H}^{\tau}\Gamma-2CHe-\beta\tau^{2}N\Lambda H{}^{t}\Lambda^{\frac{1}{H2}}$$+e^{-2\beta_{\mathcal{T}^{2}N}H}+ \Lambda t\Lambda e-\beta \mathcal{T}N2\Lambda_{H}{}^{t}C\frac{1}{H2}-1Tc3\tau\Lambda-1\mathit{0}3C_{H}-1\beta\tau N2\Lambda H{}^{t}\Lambda H3\frac{1}{H2}e^{-}$$- \Lambda^{\frac{1}{H2}}e-\beta_{\mathcal{T}}2N\Lambda_{H}tC_{H}-1T-1-D^{\tau_{\Lambda D_{H}C_{H}{}^{t}\Lambda}}HH\frac{1}{H2}1-e\beta\tau^{2}N\Lambda H$.

$-\Lambda^{\frac{1}{H2}}e-\beta_{\mathcal{T}^{2}}N\Lambda HtC_{H}^{-}1^{T\frac{1}{H2}}D_{3}T\Lambda^{-}1DC_{H}^{-}1-33e{}^{t}\Lambda\beta \mathcal{T}^{2}N\Lambda H$

(46)

37

Note that $K\Psi^{-1}K^{T}$ is exponentially close to the orthogonal projection onto the subspacespanned by the.first $H$ components.
In the matrix $K$ , the $(H+1, H)$ -component has the slowest order in the convergence,. Hereafter, we assume that there is a time
and the order isinterval such that the value of this component is very small but sufficiently larger than ;that is,$\exp\{-\beta\tau^{2\sqrt{N}-}(\tilde{\lambda}H\tilde{\lambda}H+1)t\}$$\epsilon$$\epsilon<<\exp\{-\beta_{\mathcal{T}}2\sqrt{N}(\tilde{\lambda}_{H}-\tilde{\lambda}H+1)t\}<<1$

.

(47)

. We consider the main part of $K\Psi^{-1}K^{T}$ ,This is equivalent to the condition ofneglecting terms of faster convergence.
The matrix $K$ can be further decomposed as$\mathrm{e}\mathrm{q}.(35)$

$K==$

,

(48)

$K_{41}\in M((L-H)\cross r;\mathbb{R}),$$K_{42}\in M((L-H)\cross(H-r)),$
,
where
, and
is equal to or fasterand $K_{32}\in M(H\cross(H-r))$ . The convergence of.
assumethat
We further
than the order of$K_{31}\in M(H\mathrm{x}r;\mathbb{R})$$K_{22},$$K_{21},$$K_{21},$$K_{3}$$K_{41}$$\exp\{-\beta_{\mathcal{T}N}2(\lambda r-\epsilon\tilde{\lambda}r+1)t\}$$\exp\{-\beta\tau^{2}N(\lambda r-\epsilon\tilde{\lambda}_{r}+1)t\}<<\epsilon^{\frac{3}{2}}\exp\{-2\beta\tau 2_{\sqrt{N}()t}\tilde{\lambda}_{H}-\tilde{\lambda}H+1\}$(49). This assumption is naturally satisfied under the condition
holds in the interval ofof
if $N$ is sufficiently large, since it is equivalent to$\mathrm{e}\mathrm{q}.(47)$$\mathrm{e}\mathrm{q}.(35)$$t>> \frac{\frac{3}{2}\log^{\sqrt{N}}}{\beta_{\mathcal{T}^{2}N}\{\lambda r+\frac{1}{\sqrt{N}}(\tilde{\lambda}H-\tilde{\lambda}r+1+\tilde{\lambda}_{H+1})\}}$

.

(50)

an approximation up to the leading order of each component in
Hereafter, wematrixes. Then, the solution can be rewritten as$\mathrm{u}\mathrm{s}\mathrm{e}\sim \mathrm{f}\mathrm{o}\mathrm{r}$$RR^{T}$$2\Phi(_{0}^{\Lambda^{\frac{1}{2}}}$$\sqrt{-1}\Lambda^{\frac{1}{2})\tau_{K)K^{T}}}0K(I_{H}-K22(_{0}^{\Lambda^{\frac{1}{2}}}$$\sqrt{-1}\Lambda^{\frac{1}{2})}0\Phi^{T}$$2\Phi\Phi^{T}$

.

(51)

38

Therefore, we obtain,$A^{T}.A$$U\Lambda^{\frac{1}{2}}\Lambda^{\frac{1}{2}}U^{T}$$BA$$W\Lambda^{\frac{1}{2}}\Lambda^{\frac{1}{2}}U^{T}$$BB^{T}$,$W\Lambda^{\frac{1}{2}}\Lambda^{\frac{1}{2}}W^{T}$

.

(52)

Now, we are in a position to prove overtraining. The first term in the right hand sideof$\mathrm{e}\mathrm{q}.(25)$is written as

Tr $[(F-BA)A\tau A(BA-B0A\mathrm{o})T]$$\sim \mathrm{h}[\Lambda^{\frac{1}{2}}\Lambda\Lambda^{\frac{1}{2}}$$\cross\{\Lambda^{\frac{1}{2}}\Lambda^{\frac{1}{2}}-W^{T}B_{0}A0U\}]$

Lemma 1 in Appendix and further decomposition of$K_{2}$

and$K_{4}$. (53)

show

Tr $[(F-BA)A\tau A(BA-B_{0}A0)^{\tau}]$$\epsilon^{2}\overline{\Lambda}^{\frac{1}{22}}(KK\tilde{\Lambda}--\epsilon^{2}\tilde{\Lambda}^{\frac{2T1}{\mathrm{s}^{2}}}K\epsilon_{222}^{\frac{3}{2}}\Lambda^{\frac{1}{12}\tau_{12}}22\tilde{\Lambda}^{\frac{32}{22}}+\epsilon^{2}\tilde{\Lambda}^{\frac{3}{\mathrm{s}^{2}}}K2K2\tilde{\Lambda}^{\frac{3}{\tilde{\Lambda}22}}K2\tau K22\tilde{\Lambda}\frac{1}{22}23K22\tilde{\Lambda}^{\frac{)1}{22}} \epsilon^{2}\overline{\Lambda}^{\frac{1}{32}}(-222+K_{22})T\tau\overline{\Lambda}\epsilon^{\frac{3}{2}\Lambda}\epsilon_{K\tilde{\Lambda}_{22}}2\tilde{\Lambda}^{\frac{\frac{1}{112}}{22}}K\tau K_{2}2\tilde{\Lambda}K222K_{2}\tau\tilde{\Lambda}\frac{\frac{1}{212}}{3K2}2\tau_{K\tilde{\Lambda}_{3}}K\tilde{\Lambda}2K2\tau 1222\tilde{\Lambda}222\frac{1}{\mathrm{s}^{2}})$$\sim \mathrm{b}[(_{-\epsilon’\tilde{\Lambda}^{\frac{12}{32}}K_{2}}^{\Lambda^{\frac{1}{\tilde{\Lambda}12}}}\epsilon^{\frac{1}{2}\frac{1}{\underline 2,1\sim 2}}K\tau_{2}K_{2}1\frac{3}{12}K21TK_{21}\Lambda^{\frac{3}{\Lambda 12}}1\Lambda\frac{3}{12}$.
$\cross(_{\epsilon^{\frac{1}{2}}\tilde{\Lambda}^{\frac{1}{32}}}-\epsilon^{\frac{1}{2}}\overline{\Lambda}^{\frac{1}{22}}K_{222}^{\tau_{2}}K)KO(\epsilon\Lambda\frac{1}{12}+1\Lambda\frac{11}{12}+O(\in)O(\Xi) \epsilon\tilde{\Lambda}_{2^{-\mathcal{E}}}\tilde{\Lambda}\frac{1}{22}K\tau K_{22}-\epsilon^{\frac{1}{2}}\Lambda^{\frac{1}{12}}K\tau_{12}K\Xi\tilde{\Lambda}^{\frac{1}{32}}K_{2}2\tilde{\Lambda}\frac{1}{22}+O^{+}(\epsilon 2)22222\tilde{\Lambda}\frac{1}{\tilde{\Lambda}22}\frac{1}{22}+o_{(}o(\epsilon)\mathcal{E})$$\epsilon\tilde{\Lambda}^{\frac{1}{32}}K_{2}2K6^{\frac{1}{2}\frac{1}{12}}\epsilon\tilde{\Lambda}\frac{\Lambda 1}{22}KT2K_{2}22\tau\frac{1}{32}\tilde{\Lambda}^{\frac{\tilde{\Lambda 1}}{32}}O(\epsilon)2)_{(54)}1\tau\tilde{\Lambda}\frac{+1}{32}2++o(\Xi O(\in))2]$. Note that the order$\cross(2,3)$$(3,
2)$, is smaller underpart in, appeared in$(3,1)$ $\cross(1,3)$ part,, appeared in the, and the orderthe condition of. Thus, the main part is included inis also smaller under the assumption of
The leading order is$O(\epsilon^{4})\cross$$\epsilon^{3}\exp\{-2\beta\tau\sqrt{N}2(\tilde{\lambda}_{H}-\tilde{\lambda}_{H+1})t\}$$\exp\{-\beta_{\mathcal{T}}2\sqrt{N}(\tilde{\lambda}H-\tilde{\lambda}H+1)t\}$$\mathrm{e}\mathrm{q}.(47)$$\mathrm{e}\mathrm{q}.(54)$$o(\epsilon^{\frac{3}{2}})\cross K_{21}$$\mathrm{e}\mathrm{q}.(49)$Tr$[ \epsilon^{3}\tilde{\Lambda}^{\frac{1}{22}}K_{22}\tau K22\tilde{\Lambda}\frac{5}{22}-\mathit{6}3\tilde{\Lambda}^{\frac{1}{22}}K2T\tilde{\Lambda}_{3}2K22\overline{\Lambda}^{\frac{3}{22}}-\epsilon^{32}\tilde{\Lambda}^{\frac{1}{32}}K_{22}\tilde{\Lambda}_{2}K^{\tau_{2}}2\tilde{\Lambda}\frac{1}{32}\in^{3}+\tilde{\Lambda}^{\frac{3}{32}}K22\tilde{\Lambda}2K2\tau_{2}\tilde{\Lambda}\frac{1}{32}]$

.

(55)

$= \in^{3}\sum_{i=1j}^{L-H}\sum_{1=}\overline{\lambda}r+j(\tilde{\lambda}r+i-\tilde{\lambda}H+i)^{2}\mathrm{t}(K_{2}H-r)2ij\}^{2}$are positive, and this proves the trace is strictly positive. It can
All the terms in
is also strictly positive.
be proved in almost the same way that the second term in$\mathrm{e}\mathrm{q}.(55)$$\mathrm{e}\mathrm{q}.(25)$39

Thus, we obtain(56)$\frac{d}{dt}\mathrm{E}_{gen}>0$

if the target is overrealizable and is in the interval of.
From the above discussion, we can see that overtraining occurs in an intermediate interval, while overtraining of the average learning curve in Fig.4 seems to continue to theend. If we look at each trial for one set of training data, we find that some learning
curves slightly decreases after showing overtraining. However, the effect of the decreaseis very small, and the global figure of the curve is determined by the initial decrease andovertraining. It is also easy to see theoretically that this final decrease or increase is verysmall because it is caused by $o(e^{-aNt})$ terms.
$t$5$\mathrm{e}\mathrm{q}.(35)$Conclusion

We showed that strong overtraining is served in batch learning of multilayer neuralnetworks when the target is overrealizable. According to the experimental results on
multilayer perceptrons and linear neural networks, this overtraining seems to be a universal
property of multilayer models. We theoretically analyzed the batch training of linear
neural networks, showed the existence of overtraining in an intermediate time interval in
overrealizable cases.
Although the theoretical analysis in this paper is only on the linear neural networkmodel, it is very suggestive to the phenomena of overtraining, which is observed in many
application of multilayer neural networks. It will be extremely important to clarify thisovertraining phenomena theoretically also in other models.
$0\dot{\mathrm{b}}$References[1] Amari, S., Murata, N., &M\"uller, K. R. (1996). Statistical theory of overtraining-is cross-validation asymptotically effective? In D. S. Touretzky, M. C. Mozer,&M. E. Hasselmo (Eds.), Advances in Neural Information Processing Systems 8,(pp.176-182). Cambridge, MA: MIT Press.
[2] Baldi, P. &Chauvin, Y. (1991) Temporal evolution of generalization during learningin linear networks. Neural Computation, 3, 589-603.
[3] Baldi, P. F. &Hornik, K. (1995). Learning in linear neural networks: a survey. IEEE
Trans. Neural Networks, 6(4), 837-858.

[4] Bartia, R. (1997). Matrix Analysi8, New York: Springer-Verlag.

40[5] Cram\’er, H. (1946). Mathematical method of statistics, (pp.497-506). Princeton, NJ:
Princeton University Press.

[6] Fukumizu, K. (1996). A regularity condition of the information matrix of a multilayer
perceptron network. Neural Networks, 9(5), 871-879.
[7] Fukumizu, K. (1997). Special statistical properties of neural network learning. In Proc.
1997International Symposium on Nonlinear Theory and Its Applications (NOLTA’97),(pp.747-750).
[8] Fukumizu, K. (1998). Effect of Batch Learning in Multilayer Neural Networks. In Proc.
5th International Conference on Neural Information Processing (ICONIP’98), (pp.6770).

[9] Helmke, U. &Moore, J. B. (1994). Optimization and Dynamical Systems. London:

Springer-Verlag.
[10] Heskes, T. M. &Kappen, B. (1991). Learning process in neural networks. PhysicalReview A, 44(4), 2718-2726.
[11] Oja, E. (1989). A simplified neuron model as a principal component analyzer. J. Math.
Noiol., 15, 267-273.
[12] Rumelhart, D. E., Hinton, G. E. &Williams, R. J. (1986). Learning internal representations by error propagation. In D.E. Rumelhart, J.L. McClelland, &the PDP
Research Group (Eds.), Parallel distributed processing, Vol.1 (pp.318-362). Cambridge,
MA: MIT Press.
[13] Sasagawa, T. (1982). On the finite escape phenomena for matrix Riccati equations.
In IEEE Trans. Automatic Control, 27(4), 977-979.

[14] Yan, W., Helmke, U. &Moore, J. B. (1994). Global analysis of Oja’s flow for neuralnetworks. IEEE Trans. Neural Networks, 5(5), 674-683.

AppendixA

Perturbation of singular value decomposition

We prove the following
Lemma 1. Let $Z$ be a $L\cross L$ matrix, and$C_{0}$

be a $L\cross L$ matrix of the$C_{0}=$ ,.

$f_{or}m_{f}$

(57)

41

where

$C^{(0)}i\mathit{8}$$C_{0}+\epsilon Z$

a$r\cross r$. Let

matrix. For a sufficiently small positive number , we define$\epsilon$$C_{\epsilon}$(58)$C_{\epsilon}=W\Sigma_{\epsilon}U^{T}$

be the singular value decomposition of , where $W$ andis a diagonal matrix which has the singular values of
has the following form;$C_{\in}$$\Sigma_{\epsilon}$$U$$C_{\epsilon}$

are orthogonal matrixes and. Then, the matrix $W^{T}C_{0}U$$W^{T}C0U=$ .
Proof. It is known (Bartia, 1997, Section III) that$\Sigma_{\epsilon}$(59)

has the form;$\Sigma_{\epsilon}=$ ,
where
write

$\Sigma^{(0)}$(60). For ais the diagonal matrix of the singular values ofmatrix, wherematrix. Then, the upper-left block ofis a$C^{(0)}$$A=(_{A_{21}A_{22}}^{A_{1}}1A12)$$A_{11}$$:=$$L\cross L$$r\cross r$

$A$

, we

$\mathrm{e}\mathrm{q}.(58)$leads$W_{11}^{T}(\Sigma^{(}0)+O(\epsilon))U_{11}+W_{21}^{T}O(\mathcal{E})U21=C^{(0)}+\epsilon Z_{11}$This shows that

$W_{\underline{1}1}$

and$U_{11}$$W_{11}$

and$U_{11}$(61)

are of the constant order and$W_{11}^{T}\Sigma^{(}0)U11=C(0)+o(\mathcal{E})$We know that
, we have

.

.

(62)

are invertible for a small . From the upper-right block of$\epsilon$$\mathrm{e}\mathrm{q}.(58)$

.

(63)

$W_{12}=O(\epsilon)$. Now the assertion is$W_{11}^{T}(\Sigma^{(}0)+O(\epsilon))U_{12}+W_{21}^{T}O(\epsilon)U_{2}2=\epsilon Z12$

Therefore,
must be of the orderstraightforward.
$U_{12}$$O(\epsilon)$. Likewise,$\square$