text:
# Supervised Learning with Restricted Training Sets: a Generating Functional Analysis

## 1 Introduction

It is now a little more than ten years since studies of the dynamics of supervised learning in artificial neural networks started appearing in the statistical physics literature. Early theoretical studies focussed on on-line learning using complete training sets where the probability of the same example appearing twice during training was zero, e.g. . This work enabled the evaluation of properties like convergence speed, generalization ability and optimal learning rates. However, such studies were still significantly removed from real-world scenarios. The most serious restriction was that one had to assume the availability of an infinite amount of training date, homogeneously distributed over the input space. In a recent article  it was shown that even for very simple inhomogenuity the generalization error is no longer self-averaging and deterministic. The issue of repeating examples during training is technically a much harder problem and has received much attention recently. Most of the work has focussed on simple or linear learning rules  or different kinds of approximations, such as Fokker-Planck approaches  and Gaussian local field distributions . Exact work on non-linear learning rules has drawn heavily on techniques from the spin glass and disordered systems community (for an early overview of these techniques see e.g. ). The generating functional technique was used to study the dynamics of Gibbs learning in a perceptron with binary weights in . A dynamical version of the cavity method was employed in  to study gradient descent batch learning and the methods of dynamical replica theory were applied to the problem of on-line learning in . The on-line learning scenario in this last sequence of papers is the one that we study here, but in the present paper we adapt the generating functional method à la De Dominicis to deal with on-line learning. This paper might be the first to present exact macroscopic equations for on-line learning of restricted training sets for non-linear learning rules which are not of a gradient-descent type.

Precise definitions will be given in section 2, but the general setup is the following. The examples presented to the student perceptron are $`N`$ dimensional vectors chosen with equal probability from a fixed training set $`\mathrm{\Omega }`$. The number of examples in $`\mathrm{\Omega }`$ is $`p=\alpha N`$. At each presentation the student is given the teacher’s classification of the pattern. The student can then decide to change its ‘program’, represented by the $`N`$ dimensional vector $`𝝈^N`$, in order to resemble more the teacher’s program $`𝝉^N`$. The random choice of a pattern from the training set makes the evolution of the student weight vector $`𝝈`$ a stochastic process. In section 3 we write down a generating function for all the possible paths of $`𝝈`$. This function can be averaged over all possible realizations of the training set $`\mathrm{\Omega }`$ (a quenched disorder average). At that point we will take the limit $`N`$ to infinity, to find saddle-point equations for a set of five order parameters and their conjugates. The reader who is mainly interested in results can skip section 3 and go directly to section 4, where the equations are reduced to a single exact set of three equations involving the student autocorrelation $`C(t,t^{})=𝝈(t)𝝈(t^{})/N`$, the student-teacher overlap $`R(t)=𝝈(t)𝝉/N`$ and the student response function $`G(t,t^{})`$. This set gives a surprisingly simple and intuitive picture of the evolution of the order parameters and the distribution of the local fields. From that point it is easy to establish links with earlier work on infinite training sets, batch learning and linear learning rules. Numerical evidence is presented, showing that the present theory is in very good agreement with the simulations.

In section 5, the stationary state of a student with constant weight decay is studied. For the stationary state one can split all relevant order parameters into persistent and non-persistent parts. If we keep only the persistent parts and the single-time non-persistent parts, we find a closed set of equations containing just four scalar order parameters. The procedure is inspired by a similar method applied to the solution of detailed balance spin glass dynamics, where it can be shown to be exact. Although the numerical evidence certainly seems to suggest that the procedure yields the correct results, we can not proof this fact rigorously here. At the moment, it remains an interesting open question.

## 2 Definitions

We study on-line learning in a student perceptron characterized by a vector $`𝝈^N`$. The student classifies patterns $`𝝃\mathrm{\Omega }\{1,+1\}^N`$ according to $`S(𝝃)=\text{sgn}(𝝈𝝃)`$. The student tries to learn the task set by the teacher $`T(𝝃)=\text{sgn}(𝝉𝝃)`$ with $`𝝉^N`$, i.e. we only consider linear separable classifications. The components of the weight vectors of teacher and student are assumed not to scale with $`N`$. The set $`\mathrm{\Omega }`$ contains only $`p=\alpha N`$ examples, independently chosen with equal probability from $`\{1,+1\}^N`$. Patterns will be labeled by the Greek index $`\mu `$. At each iteration each pattern is equally likely to be chosen for presentation to the student, independently of previous rounds. If at step $`m`$, pattern $`\mu (m)`$ is presented to the learning student, the student’s weight vector is slightly adjusted to converge to the desired classification according to a recipe of the general form:

$$𝝈(m+1)=𝝈(m)+\frac{\eta }{\sqrt{N}}𝝃^{\mu (m)}F(\frac{𝝈(m)𝝃^{\mu (m)}}{\sqrt{N}},\frac{𝝉𝝃^{\mu (m)}}{\sqrt{N}}).$$
(1)
The speed of the evolution is set by the learning rate $`\eta `$. The function $`F(x,y)`$ is the learning rule. Popular learning rules are e.g.

$$F(x,y)=\{\begin{array}{cc}yx,\hfill & \text{Linear}\hfill \\ \text{sgn}(y),\hfill & \text{Hebb}\hfill \\ \text{sgn}(y)x,\hfill & \text{Adaline}\hfill \\ \text{sgn}(y)\theta (xy),\hfill & \text{Perceptron}\hfill \\ |x|\text{sgn}(y)\theta (xy),\hfill & \text{Adatron}\hfill \end{array}$$
(2)
where $`\theta `$ is the stepfunction, $`\theta (x)=1`$ for $`x0`$ and $`\theta (x)=0`$ for $`x<0`$. The first three learning rules are all linear in $`x`$, while the last two only alter the student’s weights when student and teacher disagree.

A theoretical study of perceptrons can be useful for predicting learning times, for evaluating different learning rules or for finding optimal learning rates. For this purpose one is not so much interested in predicting the specific microscopic realizations of $`𝝈`$ over time, but rather in the number of errors the perceptron makes in the classification of the training set (training error, $`E_t`$) and the number of errors in the classification of the complete set of examples $`\{1,+1\}^N`$ (generalization error, $`E_g`$):

$`E_t(𝝈)`$ $``$ $`\theta ((𝝈𝝃)(𝝉𝝃))_\mathrm{\Omega }={\displaystyle \frac{1}{p}}{\displaystyle \underset{𝝃\mathrm{\Omega }}{}}\theta ((𝝈𝝃)(𝝉𝝃)),`$ (3)
$`E_g(𝝈)`$ $``$ $`\theta ((𝝈𝝃)(𝝉𝝃))={\displaystyle \frac{1}{2^N}}{\displaystyle \underset{𝝃\{1,+1\}^N}{}}\theta ((𝝈𝝃)(𝝉𝝃)).`$ (4)
Given $`𝝈`$, the generalization error is independent of the training set. It is in fact a standard result in perceptron theory that this error is only dependent on the angle between student and teacher vector, i.e. the norm of $`𝝈`$ and its overlap with $`𝝉`$.

$$E_g(𝝈)=\frac{1}{\pi }\mathrm{arccos}\left(\frac{R(𝝈)}{\sqrt{C(𝝈,𝝈)}}\right).$$
(5)
## 3 The generating functional

The random choice of a pattern $`\mu (m)`$ makes it more convenient to go to a description of an ensemble of students with a distribution of weight vectors, $`P_m(𝝈)`$, than to study the stochastic evolution of $`𝝈`$ directly. In this setting we can study the (moment) generating function $`Z_M`$ for iteration times up to $`M`$:

$$Z_M[𝝍]=D𝝈P(𝝈(0),𝝈(1),\mathrm{},𝝈(M))\mathrm{}^{i_{m=0}^M𝝍(m)𝝈(m)},$$
(6)
where $`D_{m=0}^M𝝈=_md𝝈(m)`$ is an integral over all possible paths the students could take. Derivation of $`Z_M`$ with respect to $`𝝍`$ generates all moments of the distribution $`P`$. The microscopic dynamics of weight vectors at time $`m`$ can be written in the general form $`P_{m+1}(𝝈)=𝑑𝝈^{}W(𝝈|𝝈^{})P_m(𝝈^{})`$, with the transition probabilities

$$W(𝝈|𝝈^{})=\frac{1}{p}\underset{\mu =1}{\overset{p}{}}\delta \left(𝝈𝝈^{}\frac{\eta }{\sqrt{N}}𝝃^\mu F(\frac{𝝈^{}𝝃^\mu }{\sqrt{N}},\frac{𝝉𝝃^\mu }{\sqrt{N}})\right)$$
(7)
To disentangle the double $`𝝃`$ dependence of the transition rates, we employ the integral representation of the Dirac delta-function and introduce

$`W(𝝈|𝝈^{},𝐱^{},𝐲)`$ $`=`$ $`{\displaystyle \frac{1}{p}}{\displaystyle \underset{\mu }{}}\delta \left(𝝈𝝈^{}{\displaystyle \frac{\eta }{\sqrt{N}}}𝝃^\mu F(𝐱^\mu ,y^\mu )\right)`$ (8)
$`=`$ $`{\displaystyle \frac{d\widehat{𝝈}}{(2\pi )^N}\mathrm{exp}\left[i\widehat{𝝈}(𝝈𝝈^{})\right]\widehat{W}(\widehat{𝝈}|𝐱^{},𝐲,𝐰)},`$ (9)
where we introduced three shorthands, called local fields (in analogy with spin systems)

$$x^\mu =\frac{1}{\sqrt{N}}𝝈𝝃^\mu ,y^\mu =\frac{1}{\sqrt{N}}𝝉𝝃^\mu ,w^\mu =\frac{1}{\sqrt{N}}\widehat{𝝈}𝝃^\mu ,$$
(10)
and the Fourier transform of the transition rate $`\widehat{W}`$. For large $`N`$, $`\widehat{W}`$ will be of order $`1+𝒪(N^{1/2})`$ and will therefore factorize over the patterns

$`\widehat{W}(\widehat{𝝈}|𝐱,𝐲,𝐰)`$ $`=`$ $`{\displaystyle \frac{1}{p}}{\displaystyle \underset{\mu }{}}\mathrm{exp}\left(i\eta w^\mu F(x^\mu ,y^\mu )\right)`$
$`=`$ $`\mathrm{exp}\left[{\displaystyle \frac{1}{p}}{\displaystyle \underset{\mu }{}}\mathrm{}^{i\eta w^\mu F(x^\mu ,y^\mu )}1\right],(N\mathrm{})`$
We can now rewrite the generating function:

$`Z_M[𝝍]={\displaystyle D𝝈P_0(𝝈(0))\underset{m=0}{\overset{M1}{}}W(𝝈(m+1)|𝝈(m))}`$
$`={\displaystyle \frac{D𝝈D\widehat{𝝈}}{(2\pi )^N}D𝐱𝑑𝐲D𝐰P_0(𝝈(0))\mathrm{\Gamma }[𝐲,𝐱,𝐰,𝝈]\underset{m}{}\widehat{W}(\widehat{𝝈}(m)|𝐱(m),𝐲,𝐰(m))}`$
$`\times {\displaystyle \underset{m}{}}\mathrm{exp}[i\widehat{𝝈}(m)(𝝈(m+1)𝝈(m))+i𝝍(m)𝝈(m)]`$
where the appearance of the training examples is restricted to the function $`\mathrm{\Gamma }`$, given by:

$`\mathrm{\Gamma }[𝐲,𝐱,𝐰,𝝈]`$ $`=`$ $`{\displaystyle \underset{\mu }{}}\delta \left[y^\mu {\displaystyle \frac{𝝉𝝃^\mu }{\sqrt{N}}}\right]{\displaystyle \underset{m}{}}\delta \left[x^\mu (m){\displaystyle \frac{𝝈(m)𝝃^\mu }{\sqrt{N}}}\right]\delta \left[w^\mu (m){\displaystyle \frac{\widehat{𝝈}(m)𝝃^\mu }{\sqrt{N}}}\right]`$
In the thermodynamic limit $`(N\mathrm{}`$), all the macroscopic observables in this model are self-averaging with respect to the realization of the training set. To avoid the difficulty of choosing a typical training set, we can thus safely consider the disorder averaged generating function $`[Z]_{dis}`$. The only term involving the actual patterns is $`\mathrm{\Gamma }`$. The quenched disorder average of $`\mathrm{\Gamma }`$ is

$`\left[\mathrm{\Gamma }\right]_{dis}={\displaystyle 𝑑\widehat{𝐲}D\widehat{𝐱}D\widehat{𝐰}\underset{\mu }{}\mathrm{exp}\left[i\widehat{y}^\mu y^\mu +\underset{m}{}i\widehat{x}^\mu (m)x^\mu (m)+\underset{m}{}i\widehat{w}^\mu (m)w^\mu (m)\right]}`$
$`\times 2^N{\displaystyle \underset{𝝃^\mu \{\pm 1\}^N}{}}\mathrm{exp}{\displaystyle \frac{\mathrm{}}{\sqrt{N}}}𝝃^\mu \left[\widehat{y}^\mu 𝝉+{\displaystyle \underset{m}{}}\widehat{x}^\mu (m)𝝈(m)+{\displaystyle \underset{m}{}}\widehat{w}^\mu (m)\widehat{𝝈}(m)\right]`$
Of the term on the second line, only the quadratic terms in $`𝝉`$, $`𝝈`$ and $`\widehat{𝝈}`$ survive in the thermodynamic limit. Near this limit we find that this term containing the training patterns becomes

$`{\displaystyle \underset{\mu ,i}{}}\mathrm{exp}\left[{\displaystyle \frac{1}{2N}}\left(\widehat{y}^\mu \tau _i+{\displaystyle \underset{m}{}}\widehat{x}^\mu (m)\sigma _i(m)+{\displaystyle \underset{m}{}}\widehat{w}^\mu (m)\widehat{\sigma }_i(m)\right)^2\right],`$
in the thermodynamic limit. We assume that the initial probability distribution $`P_0(𝝈)`$ factorizes over sites. Full factorization of the generating function over patterns and input channels can then be achieved if we introduce the following order parameters and their conjugates via delta-functions:

$`R_m={\displaystyle \frac{1}{N}}{\displaystyle \underset{i}{}}\sigma _i(m)\tau _i,`$ $`r_m={\displaystyle \frac{1}{N}}{\displaystyle \underset{i}{}}\widehat{\sigma }_i(m)\tau _i,`$
$`C_{mn}={\displaystyle \frac{1}{N}}{\displaystyle \underset{i}{}}\sigma _i(m)\sigma _i(n),`$ $`c_{mn}={\displaystyle \frac{1}{N}}{\displaystyle \underset{i}{}}\widehat{\sigma }_i(m)\widehat{\sigma }_i(n),`$
$`K_{mn}={\displaystyle \frac{1}{N}}{\displaystyle \underset{i}{}}\sigma _i(m)\widehat{\sigma }_i(n).`$
When changing $`m`$ to $`m+1`$, the expectation of these order parameters can only can by a value of order $`N^1`$. We thus rescale the time as $`t=m/\mathrm{\Delta }N`$. From here, one could go to a continuous time description by introducing $`\tau =\mathrm{\Delta }t`$ and taking the limit $`\mathrm{\Delta }`$ to zero, but we delay this step in order to avoid technical difficulties in evaluating the path integrals. The generating function attains a form suitable for saddle-point integration:

$$\left[Z[𝝍]\right]_{dis}\mathrm{}\mathrm{exp}\left[N(\mathrm{\Psi }+\mathrm{\Phi }+\mathrm{\Omega })\right]$$
(12)
There are three distinct leading order contributions to the exponent. The first is a ‘bookkeeping’ term, linking the order parameters to their conjugates:

$$\mathrm{\Psi }=i\widehat{R}R+i\widehat{r}r+i\mathrm{Tr}\left[\widehat{C}^TC+\widehat{K}^TK+\widehat{c}^Tc\right]$$
(13)
The second term reflects the coupled dynamics of the local fields:

$`\mathrm{\Phi }={\displaystyle \frac{1}{N}}{\displaystyle \underset{\mu }{}}\mathrm{log}{\displaystyle }{\displaystyle \frac{dyd\widehat{y}}{2\pi }}{\displaystyle \frac{DxD\widehat{x}}{(2\pi )^T}}{\displaystyle \frac{D\widehat{w}Dw}{(2\pi )^T}}\mathrm{exp}[i\widehat{w}w+{\displaystyle \frac{\mathrm{\Delta }}{\alpha }}{\displaystyle \underset{t}{}}(\mathrm{}^{i\eta w_tF(x_t,y)}1)`$
$`+i\widehat{y}(y\theta _y^\mu )+i\widehat{x}(x\theta _x^\mu ){\displaystyle \frac{1}{2}}\widehat{x}C\widehat{x}{\displaystyle \frac{1}{2}}\widehat{y}^2`$ (14)
$`\widehat{x}K\widehat{w}\widehat{y}R\widehat{x}{\displaystyle \frac{1}{2}}\widehat{w}c\widehat{w}\widehat{y}r\widehat{w}],`$
where we have added additional sources $`𝜽_x`$ and $`𝜽_y`$ to couple to $`\widehat{𝐱}`$ and $`\widehat{𝐲}`$. These sources act as biases of teacher and student. The third term describes the evolution of the now decoupled weight components:

$`\mathrm{\Omega }={\displaystyle \frac{1}{N}}{\displaystyle \underset{i}{}}\mathrm{log}{\displaystyle }{\displaystyle \frac{D\sigma D\widehat{\sigma }}{(2\pi )^T}}P_{0i}(\sigma _0)\mathrm{exp}[i\tau _i\widehat{R}\sigma i\tau _i\widehat{r}\widehat{\sigma }`$ (15)
$`i\sigma \widehat{C}\sigma i\widehat{\sigma }\widehat{c}\widehat{\sigma }i\sigma \widehat{K}\widehat{\sigma }+i\widehat{\sigma }G_0^1\sigma i\widehat{\sigma }\theta _i+i\sigma \psi _i]`$
where $`[G_0^1]_{tt^{}}=\delta _{t+1,t^{}}\delta _{tt^{}}`$ and where we have included an external driving force $`\theta _i(t)`$ in the system. With a modest amount of foresight we write $`G_{tt^{}}=iK_{tt^{}}`$. Upon taking derivatives with respect to the generating fields $`\{\psi _i(t),\theta _i(t)\}`$, we find *at* the relevant saddle-point:

$`R_t=\underset{N\mathrm{}}{lim}{\displaystyle \frac{1}{N}}{\displaystyle \underset{i}{}}\left[\sigma _i(t)\tau _i\right]_{dis},`$
$`C_{tt^{}}=\underset{N\mathrm{}}{lim}{\displaystyle \frac{1}{N}}{\displaystyle \underset{i}{}}\left[\sigma _i(t)\sigma _i(t^{})\right]_{dis},`$
$`G_{tt^{}}=\underset{N\mathrm{}}{lim}{\displaystyle \frac{1}{N}}{\displaystyle \underset{i}{}}{\displaystyle \frac{}{\theta _i(t^{})}}\left[\sigma _i(t)\right]_{dis}`$
Using the built-in normalisation $`\left[Z(0)\right]_{dis}`$, we also find

$`r_t=\underset{N\mathrm{}}{lim}{\displaystyle \frac{1}{N}}{\displaystyle \underset{i}{}}{\displaystyle \frac{}{\theta _i(t)}}\left[\tau _i\right]_{dis}=0,`$
$`c_{tt^{}}=\underset{N\mathrm{}}{lim}{\displaystyle \frac{1}{N}}{\displaystyle \underset{i}{}}{\displaystyle \frac{^2}{\theta _i(t)\theta _i(t^{})}}\left[Z(0)\right]_{dis}=0`$
If we perform the saddle-point integration, we find in addition that

$`i\widehat{R}_t=\underset{N\mathrm{}}{lim}{\displaystyle \frac{1}{N}}{\displaystyle \underset{\mu }{}}{\displaystyle \frac{^2}{\theta _y^\mu \theta _x^\mu (t)}}\left[Z(0)\right]_{dis}=0,`$
$`i\widehat{C}_{tt^{}}=\underset{N\mathrm{}}{lim}{\displaystyle \frac{1}{N}}{\displaystyle \underset{\mu }{}}{\displaystyle \frac{^2}{\theta _x(t)\theta _x(t^{})}}\left[Z(0)\right]_{dis}=0.`$
At this point we can already simplify (or remove altogether) the generating fields $`\theta _i(t)=\theta _t,\theta _x^\mu (t)=\theta _{xt},\theta _y^\mu (t)=\theta _{yt}`$ and $`\psi _i(t)=0`$. The external fields $`\theta _x`$ and $`\theta _y`$ can be interpreted as biases or thresholds of the student and teacher, respectively. Without loss of generality we may set $`\tau _i=1`$. The evolution of the local fields and the weight vector are now linked only via the remaining non-zero order parameters. We proceed to evaluate the two separate processes at the saddle-point.

### 3.1 Pattern average $`\mathrm{\Phi }`$

Focussing on the evaluation of the pattern average $`\mathrm{\Phi }`$ we find that the terms involving $`w`$ can be interpreted as averages over a Poisson-distribution:

$`{\displaystyle \frac{dw_t}{2\pi }\mathrm{exp}\left[i\widehat{w}_tw_t+\frac{\mathrm{\Delta }}{\alpha }\left(\mathrm{}^{i\eta w_tF(x_t,y)}1\right)\right]}`$
$`={\displaystyle \underset{k_t=0}{\overset{\mathrm{}}{}}}{\displaystyle \frac{dw_t}{2\pi }\mathrm{exp}\left[i\widehat{w}_tw_ti\eta k_tw_tF(x_t,y)\frac{\mathrm{\Delta }}{\alpha }\right]\frac{1}{k_t!}\left(\frac{\mathrm{\Delta }}{\alpha }\right)^{k_t}}`$
$`={\displaystyle \underset{k_t=0}{\overset{\mathrm{}}{}}}\delta (\widehat{w}_t\eta k_tF(x_t,y))(k_t),`$
where $`(k)`$ is a Poisson distribution with average $`\mathrm{\Delta }/\alpha `$. For $`\mathrm{\Delta }N1`$, $`(k)`$ gives the probability that a specific pattern is presented $`k`$ times to the student in time interval $`\mathrm{\Delta }`$. The saddle-point equations of the remaining non-zero order parameters are found to be:

$$\widehat{r}_t=\alpha \frac{}{\theta _y}f_t_\mathrm{\Phi },2i\widehat{c}_{tt^{}}=\alpha f_tf_t^{}_\mathrm{\Phi },i\widehat{G}_{tt^{}}=\alpha \frac{}{\theta _{xt}}f_t^{}_\mathrm{\Phi },$$
(16)
with the shorthand $`f_t=\eta k_tF(x_t,y)`$. The average $`_\mathrm{\Phi }`$ is using the measure implied by equation (3). Performing the disorder average has turned the $`\widehat{y}`$ integral into a Gaussian one. Evaluating this integration yields:

$`\mathrm{\Phi }`$ $`=`$ $`\alpha \mathrm{log}{\displaystyle \frac{dy}{\sqrt{2\pi }}\frac{DxD\widehat{x}}{(2\pi )^T}\underset{t}{}\left[\underset{k_t}{}(k_t)\right]}`$
$`\mathrm{exp}\left[{\displaystyle \frac{1}{2}}(y\theta _y)^2{\displaystyle \frac{1}{2}}\widehat{x}D\widehat{x}+i\widehat{x}(x\theta _xGfR(y\theta _y))\right],`$
where we have introduced the student autocovariance $`D_{tt^{}}=C_{tt^{}}R_tR_t^{}`$. We note the operator identity $`/\theta _y=yR/\theta _x`$, which in turn implies using (16) that

$$\widehat{r}_t=\alpha yf_t_\mathrm{\Phi }+\underset{t^{}}{}i\widehat{G}_{tt^{}}^TR_t^{}$$
(18)
### 3.2 Weight component average $`\mathrm{\Omega }`$

The saddle-point equations involving the weight vectors are:

$$R_t=\sigma _t_\mathrm{\Omega },C_{tt^{}}=\sigma _t\sigma _t^{}_\mathrm{\Omega },G_{tt^{}}=\frac{}{\theta _t^{}}\sigma _t_\mathrm{\Omega },$$
(19)
where $`_\mathrm{\Omega }`$ is an average with the measure induced by (15). This measure can be generated by the stochastic process: $`\widehat{r}+i\widehat{G}^T\sigma +G_0^1\sigma \theta \rho =0,`$ where $`\rho _t`$ is a Gaussian noise with zero mean and covariance $`\rho _t\rho _t^{}=\mathrm{\Lambda }_{tt^{}}2i\widehat{c}_{tt^{}}`$. From this process, we find a simple expression for $`\sigma `$ (upon setting $`\theta =0`$):

$$\sigma =G(\widehat{r}+\rho ),$$
(20)
with the response, student-teacher overlap and student autocovariance given by

$$G=\left[G_0^1+i\widehat{G}^T\right]^1,R=G\widehat{r},D=G\mathrm{\Lambda }G^T$$
(21)
## 4 Effective single pattern process

Upon combining the results of the previous two paragraphs, we find a closed set of exact equations relating the evolution of $`R`$, $`D`$ and $`G`$ to the evolution of the local field distribution implied by the measure in (3.1). Setting $`\theta _y=0`$ in this equation, we find that the distribution is generated by the following stochastic process for a student-pattern overlap:

$$x_t=R_ty+\underset{t^{}}{}G_{tt^{}}f_t^{}+z_t+\theta _{xt},$$
(22)
where $`y`$ and $`z_t`$ are independent Gaussian random variables with zero mean and variances $`y^2=1`$ and $`z_tz_t^{}=D_{tt^{}}`$. In general $`x_t`$ will depend on previous values of $`x`$ via the term $`[Gf]_t=\eta _t^{}G_{tt^{}}k_t^{}F(x_t^{},y)`$.

The evolution of the order parameters is given using the bare propagator $`G_0`$. To ensure that the students’ weight distribution will eventually reach a stationary state, we let the weights decay with rate $`\gamma `$. The bare propagator then takes the form $`[G_0^1]_{tt^{}}=\delta _{t+1,t^{}}\lambda \delta _{tt^{}}`$, where $`\lambda 1\mathrm{\Delta }\gamma `$. In the limit of $`\mathrm{\Delta }0`$, this corresponds to $`[G_0]_{tt^{}}=\theta (tt^{}\mathrm{\Delta }/2)\mathrm{exp}[\mathrm{\Delta }\gamma (tt^{}1)]`$. The equations (21) and (16) determine the evolution of the response function:

$$[G_0^1G]_{tt^{}}=𝕀_{tt^{}}+\alpha \underset{s}{}\frac{f_t}{\theta _s}G_{st^{}},$$
(23)
where now $``$ is the Gaussian averages over $`y`$ and all $`z_t`$’s. Using equation (21) along with the relation (18), we find:

$$[G_0^1R]_t=\widehat{r}_t\underset{s}{}i\widehat{G}_{ts}^TR_s=\alpha yf_t.$$
(24)
The combination of equations (21) and (16) gives the evolution of $`D`$:

$$[G_0^1D]_{tt^{}}=\alpha f_t[Gf+z]_t^{}=\alpha f_t(x_t^{}R_t^{}y),$$
(25)
where we have set $`\theta _x`$ to zero. The evolution of the diagonal terms of $`Q_tD_{tt}R_t^2`$ can be implicitly calculated using this equation, but the distribution of $`x_{t+1}`$ has to been known before $`Q_{t+1}`$ can be calculated. To avoid this difficulty, we use equation (25) together with the scaling arguments $`\widehat{G}_{tt^{}}=𝒪(\mathrm{\Delta }^2)`$ for $`t<t^{}`$, $`\widehat{G}_{tt}=𝒪(\mathrm{\Delta })`$ and $`z_{t+1}\lambda z_t=𝒪(\mathrm{\Delta }^{1/2})`$ to determine for small $`\mathrm{\Delta }`$ the evolution of $`Q_t`$ more explicitly:

$`Q_{t+1}=\lambda ^2Q_t+\alpha \lambda f_tx_t+\alpha f_tx_{t+1}`$
$`=\lambda ^2Q_t+2\alpha \lambda f_tx_t+\alpha f_t([z+Gf]_{t+1}\lambda [z+Gf]_t)`$
$`=\lambda ^2Q_t+2\alpha \lambda f_tx_t+\alpha f_t^2+𝒪(\mathrm{\Delta }^{3/2})(\mathrm{\Delta }0)`$ (26)
The equations (23)-(4) could perhaps have been found using less sophisticated methods, but the strength of the generating functional method is that it is also capable of producing the joint local field distribution $`P(x,y)`$ generated by (22). The generalization error is a direct function of these order parameters, while the training error is a slave of the local field distribution governed by them:

$$E_g(t)=\frac{1}{\pi }\mathrm{arccos}\left(\frac{R_t}{\sqrt{Q_t}}\right),E_t(t)=\theta (x_ty)$$
(27)
The evolution of the order parameters can be calculated numerically by a Monte Carlo procedure similar to the single spin procedure outlined in . The general idea is to follow the evolution of $`M`$ patterns overlaps. For each of these patterns, one generates at time $`t=0`$ a teacher overlap $`y`$ from the standard normal distribution. Time is discretized with unit $`\mathrm{\Delta }`$. At each time step and for *each* pattern, one generates the Gaussian noise $`z_t`$, correlated with the previous noise values $`z_t^{}`$ *for that particular pattern* and a Poissonian random variable $`k_t`$. Averages over all patterns are Monte Carlo implementations of the averages occuring in the evolution equations for $`D`$,$`R`$ and $`G`$. By increasing $`M`$ and decreasing $`\mathrm{\Delta }`$ the evolution of the $`N\mathrm{}`$-perceptron can be calculated up to arbitrary precision. This is shown for various $`\alpha `$ in figure 1 with $`M=20,000`$ and $`\mathrm{\Delta }=0.05`$. The figures illustrate that the agreement of the theory with the simulations is quite satisfactory.

### 4.1 Batch learning

So far, we have treated only the case of on-line learning. This is the most widely applied learning scenario, but much of the analytical work on learning with restricted training sets has been devoted to off-line or batch learning. In batch learning one first calculates the average effect of learning (a large sample of) the entire training set, before making a weight update. For small learning rates, batch and on-line learning ought to generate the same macroscopic flow. For completeness we discuss here what changes when we switch from an on-line to a batch scenario. The effect on the theory as presented above is the disappearance of the extra noise term $`f_t^2`$ in the evolution of $`Q`$ in equation (4) and the replacement of the Poisson variable $`k_t`$ by its average $`\mathrm{\Delta }/\alpha `$. The intuition behind the first change is that big changes in the student weight vector can no longer happen after a single pattern is presented; the weights undergo a much smoother evolution due to the averaging of the update over all patterns. As a result of the second change, the student training pattern overlap becomes:

$$x_t=R_ty+z_t+\eta \frac{\mathrm{\Delta }}{\alpha }\underset{s}{}G_{ts}F(x_s,y)$$
(28)
This equation was derived earlier in the context of gradient-descent batch learning by Wong et. al using an elegant application of the dynamical cavity method . Again, the reason for the change in a training pattern overlap $`x_t`$ is that instead of big changes when $`k_t`$ times that particular pattern is presented to the student in time interval $`(\mathrm{\Delta }t,\mathrm{\Delta }(t+1))`$, now during an interval interval $`x_t`$ feels the average effect of the influence of the pattern. These are the only changes necessary in the present analysis when switching from on-line to batch learning.

### 4.2 Linear learning rules

The average occurring in the evolution of the response function G in (23) can be explicitly calculated if the student is using a learning rule that is linear in $`x`$, e.g. the linear, Hebbian or adaline rules. For this type of rules of the form $`F(x,y)=g(y)cx`$, we find:

$$\frac{f_t}{x_t^{}}=\eta ck_t\left(\delta _{tt^{}}+\underset{s}{}G_{ts}\frac{f_s}{x_t^{}}\right).$$
(29)
To causality of $`G`$ allows us to perform the Poisson averages and a little matrix algebra leads to

$$G_0^1G=𝕀\mathrm{\Delta }c\eta \left[𝕀+c\eta \frac{\mathrm{\Delta }}{\alpha }G\right]^1G$$
(30)
The resulting response is translation invariant, i.e. $`G_{tt^{}}=G(\mathrm{\Delta }(tt^{}))`$ for $`tt^{}`$. The on-line response found here for linear learning rules agrees with the batch-results found for the linear rule in  and the adaline rule in . The Fourier transform of the previous relation reads

$$G^1(\omega )=\gamma i\omega +c\eta \frac{1}{1+\frac{c\eta }{\alpha }G(\omega )}$$
(31)
This equation is analysed in . For $`\gamma =0`$ and for $`c0`$, a transition in the behaviour of the response takes place at $`\alpha _c=1`$. This position is identical for on-line and off-line learning. The nature of this transition is easily understood. Without decay, the evolution of the weight vector is confined to the linear subspace spanned by the patterns in the training set. Below $`\alpha _c=1`$, the random patterns are unlikely to span the whole $`N`$-dimensional space, resulting in a non-decaying part of the response function. This argument is valid for general rules without decay.

The student overlap with a particular pattern can also be written in a more explicit way:

$$x=\left[𝕀+c\eta GK\right]^1(Ry+z+\eta g(y)Gk),K_{tt^{}}k_t\delta _{tt^{}}$$
(32)
The final results are rather cumbersome, but all the averages appearing in the evolution of the order parameters involving $`k`$ and $`z`$ can be done without any problems. The only remaining integrals are of the form $`g(y)y`$ and $`g(y)^2`$ with the standard Gaussian measure.

### 4.3 Infinite training sets

To compare our results to the well-known unrestricted training set results, we take the limit $`\alpha \mathrm{}`$. In this case the probability of repeating an example is zero. This is reflected in the fact that $`k0`$ as $`\alpha \mathrm{}`$. Given $`y`$, the local fields $`x`$ are random variables given by:

$$x_t=yR_t+z_t,$$
(33)
or, equivalently, $`x_t`$ is a Gaussian random variable with mean $`yR_t`$ and covariance $`D_{tt^{}}`$. The effects of the retarded self-interaction caused by $`G`$ thus completely vanish. If we go to a continuum time description, we recover equations found in e.g. . The evolution of the student-teacher overlap and the student self-overlap are given by

$`{\displaystyle \frac{dR}{dt}}=\gamma R_t+\eta yF(x,y)_t`$ (34)
$`{\displaystyle \frac{dQ}{dt}}=2\gamma Q+2\eta xF(x,y)_t+\eta ^2F(x,y)^2_t,`$ (35)
with the Gaussian single-time average defined by $`x_t=0,y_t=0,x^2_t=Q_t,y^2_t=1,xy_t=R_t`$.

## 5 Stationary state

Many learning rules will not reach a stationary state that is independent of the initial conditions, as soon as weight decay is absent. Weight decay, or another type of constraint, may also be necessary to bound the length of the student vector. In the Hebbian case, for example, the student weights keep on growing in the direction of the perceived teacher, regardless of the size of the training error. In order for the student to reach a stationary state, we assume that the weight decay $`\gamma `$ is large enough to bound $`R`$ and $`C`$ and that the integrated response or susceptibility $`g`$ is finite:

$$g\underset{t\mathrm{}}{lim}\mathrm{\Delta }\underset{t^{}}{}G_{tt^{}}<\mathrm{}.$$
(36)
This condition, known in the disordered systems literature as *absence of anomalous response*. We also assume that for sufficiently large $`t`$ the order parameters become time translation invariant: $`R_t=R`$, $`G_{t+\tau ,t}=G_\tau `$, $`D_{t+\tau ,t}=D_\tau `$. These assumptions are related to the replica symmetry ansatz in the replica equilibrium analyses . We split the covariance kernel $`D_t`$ in a persistent part $`d=lim_t\mathrm{}D_t`$ and a non-persistent part $`\stackrel{~}{D}_t=D_td`$. If $`d`$ exists, then

$$d=\overline{D}\underset{T\mathrm{}}{lim}\frac{1}{T}\underset{t=0}{\overset{T}{}}D_t$$

Given time translation invariance, one derives from equations (24) and (25) that

$`R={\displaystyle \frac{\eta }{\gamma }}yF(x,y)`$ (37)
$`d=\underset{\tau \mathrm{}}{lim}\underset{t\mathrm{}}{lim}{\displaystyle \frac{\eta }{\gamma }}F(x_{t+\tau },y)(x_tyR)={\displaystyle \frac{\eta }{\gamma }}\overline{F}(\overline{x}yR)`$ (38)
A relation earlier found involving the covariance (21) now yields

$$d=\alpha \overline{Gff^TG^T}=\frac{\eta ^2g^2}{\alpha }\overline{F}^2,$$
(39)
while the stationary value of $`Q`$ can be found from (4):

$$Q=\frac{\eta }{\gamma }F(x,y)x+\frac{\eta ^2}{2\gamma }F(x,y)^2.$$
(40)
All the averages either involve a single time or two infinitely separated distant times. We lack an explicit expression for the single time probability distribution of $`x_t`$. The probability of $`x_t`$ is related to realisations of $`x`$ at previous times via the response function $`G`$. This makes the evaluation of the averages as hard as solving the dynamical equations themselves. The same problem exists in the field of (Ising) spin glasses and recurrent neural networks. In those cases where the stationary state is in detailed balance (e.g. when the dynamics are of gradient descent type and the systems feels a Gaussian white noise) a fluctuation dissipation relation connects the correlation $`C`$ and the response $`G`$. It is known for such systems that when calculating the persistent and single time parts of the correlation and the integrated response, the non-persistent parts can be chosen arbitrarily as long as the FDT is obeyed. In particular one can set them to zero and take only the persistent parts and the integrated response into account. Although there are big differences between the learning perceptron discussed here and the aforementioned spin systems (for one, the learning rule $`F`$ does not have to be a gradient), we assume this decoupling property of persistent from non-persistent parts still holds<sup>1</sup><sup>1</sup>1Note that a rigorous proof would first require the derivation of a non-equilibrium generalization of FDT theorems.. We replace the equilibrium distribution of $`x`$ generated by equation (22) by a distribution generated by a stochastic relation containing only the integrated response $`g`$ and random variables described by the persistent part of the covariance matrix $`D`$, the single-time correlation $`Q`$ and the student-teacher overlap $`R`$:

$$x_t=yR+z+\stackrel{~}{z}_t+\frac{\eta }{\alpha }g\overline{F},$$
(41)
where $`y,z`$ and $`\stackrel{~}{z}_t`$ are all independent Gaussian random variables with zero mean and covariances $`y^2=1`$,$`z^2=d`$ and $`\stackrel{~}{z}_t\stackrel{~}{z}_t^{}=(QR^2d)\delta _{tt^{}}`$. The average learning term $`\overline{F}`$ for a specific pattern with a certain $`(y,z)`$, can be expressed self-consistently as:

$$\overline{F}_{yz}\underset{T\mathrm{}}{lim}\frac{1}{T}\underset{t<T}{}F(x_t,y)=𝑑\stackrel{~}{z}p(\stackrel{~}{z})F(yR+z+\stackrel{~}{z}+\frac{\eta g}{\alpha }\overline{F}_{yz},y)$$
(42)
For Hebbian learning one has $`\overline{F}=\text{sgn}(y)`$, but in general (42) will be a transcedental equation, so one has to revert to numerical methods to solve it. Once $`\overline{F}`$ can be found for any point $`(y,z)`$, the remaining two independent Gaussian integrals over $`y`$ and $`z`$ can be evaluated to close equations (37) to (40). The remaining closed set can be solved numerically. Results for Hebbian and perceptron learning rules and various training sets sizes are presented in figure 2. For the perceptron rule, the results shown in figure 3 compare $`E_g`$ and $`E_t`$ for different decay strengths. Perceptron results are independent of $`\eta `$. The theoretical predictions seem to be in almost perfect agreement with the simulations. Although no adatron results are shown, we expect that the proposed procedure is equally valid for the this latter rule. Our method of calculation is only valid when $`G`$ is time translation invariant and the integrated response is bounded. For this to happen, we need the presence of a weight decay. The complication is that any decay, however small, will cause the adatron student weight vector to vanish. An alternative way of ensuring that the student ensemble reaches a stationary state that does not exhibit this problem is by constraining $`𝝈`$ to a sphere. This can be implemented by choosing $`\gamma _t(Q_t1)`$. However, the adatron rule yields zero training error in this setup. This causes other problems in numerically evaluating this stationary state equations.

### 5.1 Distribution of local fields

As seen earlier, a big simplifying effect of the limit $`\alpha \mathrm{}`$ is to render the local fields $`x`$ and $`y`$ Gaussian. This happens irrespective of the learning rule involved. As soon as $`\alpha <\mathrm{}`$, the effect of the extra term $`Gf`$ in equation (41) sets in and the Gaussian form of the distribution evaporates for non-linear rules. The non-Gaussian form of the joint local field distribution has been discussed at length in , but equation (41) gives an intuitive idea of the origin of the deviations reported there.

For a Hebbian learning rule, $`F(x,y)=\text{sgn}(y)`$, the conditional distribution $`p(x|y)`$ remains Gaussian with variance D, but will be shifted away from the mean $`yR`$ by the amount $`\eta g\text{sgn}(y)/\alpha `$. An example with $`\alpha =1`$ and $`\gamma =0.1`$ is shown in figure 4b. For the perceptron learning rule, this is no longer true. The random variables $`y`$ and $`z`$ are independently distributed Gaussian variables. From (42) we find that:

$$\overline{F}=\frac{1}{2}\text{sgn}(y)\frac{1}{2}\text{erf}\left(\frac{yR+z+\frac{\eta g}{\alpha }\overline{F}}{\sqrt{2(Dd)}}\right)$$
(43)
Samples of the $`(y,z)`$ statistics for $`\alpha =1`$ and $`\gamma =0.1`$ of $`\overline{F}`$ as a function of $`z`$ are shown in figure 5a for $`y>0`$ (top) and $`y<0`$ (bottom). The width of the sloping segment is $`\eta g/\alpha `$, while the size of $`\sqrt{Dd}`$ determines the rounding at the edges. The value of $`\overline{x}`$ corresponding to $`y=1`$ as a function of the Gaussian disorder $`z`$ is drawn in figure 5b. For $`y`$ positive and roughly $`z>yR`$, one has $`\overline{x}=yR+z`$, whereas for $`z<yR\eta g/\alpha `$ one finds $`\overline{x}=yR+z+\eta g/\alpha `$. For $`z`$ in the range $`yR\eta g/\alpha <z<yR`$, we find $`\overline{x}0`$. In this particular example (using the same values for the order parameters as the graphs shown in figure 4c) $`\sqrt{d}0.27`$ so that the Gaussian measure confines $`z`$ close to the origin. Thus the resulting local field distribution is distinctly non-Gaussian as shown in figure 4c.

## 6 Conclusion

In this paper, we have studied the statics and dynamics of an ensemble of students learning on-line the classification of a large number of examples. This problem boils down to solving a large number of coupled stochastic difference equations, each corresponding to a single input channel. The situation is complicated by the existence of disorder in the form of the composition of the training set. Using the generating function method we have transformed this Markovian system of $`N`$ coupled equations in the limit of $`N`$ to infinity into an effective single pattern process. The price paid for this reduction is that the new process has noise which is correlated in time and the presence of a retarded self-interaction in the system, which make the dynamics non-Markovian. In principle it is possible to calculate the evolution of the system analytically, but in general it will be impossible to pursue this after the very first few time steps. However, the process can be solved numerically up to arbitrary precision.

Our calculation provides a solid basis for the further analytical study of linear rules. For non-linear rules the importance of our exact macroscopic dynamical equations is mainly in the insight they can give into the behaviour of different learning rules and the possibility they create to study and solve stationary states of both on-line and batch, gradient and non-gradient learning. Until now, the stationary states of these kinds of learning processes have only been directly accessable with tools from equilibrium statistical mechanics, requiring detailed balance. This confined analyses to batch gradient-descent learning. This restriction has now been lifted. From our macroscopic evolution equations we can extract the stationary state equations very easily if we assume time translation invariance and the absence of anomalous response. We have not yet addressed the issue where this is likely to hold for on-line learning. To reduce the time-dependent order parameters like the student-autocorrelation and the student-response to a finite set of scalar order parameters, we apply a method we know from similar spin-glass problems based on the detachment of single-time and persistent order parameters from the non-persistent ones. The procedure consists of removing all non-persistent parts of the order parameters (except for the single time quantities), retaining only a small closed set of equations containing just four (Q,R,d,g) scalar macroscopic order parameters. Whether this last procedure is indeed exact, remains to be seen and will be the subject of a future study, but the numerical evidence clearly suggests that the underlying assumption holds.

## References