Oja's rule

Oja's learning rule, or simply Oja's rule, named after Finnish computer scientist Erkki Oja, is a model of how neurons in the brain or in artificial neural networks change connection strength, or learn, over time. It is a modification of the standard Hebb's Rule (see Hebbian learning) that, through multiplicative normalization, solves all stability problems and generates an algorithm for principal components analysis. This is a computational form of an effect which is believed to happen in biological neurons.

Theory

Oja's rule requires a number of simplifications to derive, but in its final form it is demonstrably stable, unlike Hebb's rule. It is a single-neuron special case of the Generalized Hebbian Algorithm. However, Oja's rule can also be generalized in other ways to varying degrees of stability and success.

Formula

Consider a simplified model of a neuron ${\displaystyle y}$ that returns a linear combination of its inputs x using presynaptic weights w:

${\displaystyle \,y(\mathbf {x} )~=~\sum _{j=1}^{m}x_{j}w_{j}}$

Oja's rule defines the change in presynaptic weights w given the output response ${\displaystyle y}$ of a neuron to its inputs x to be

${\displaystyle \,\Delta \mathbf {w} ~=~\mathbf {w} _{n+1}-\mathbf {w} _{n}~=~\eta \,y_{n}(\mathbf {x} _{n}-y_{n}\mathbf {w} _{n}),}$

where η is the learning rate which can also change with time. Note that the bold symbols are vectors and n defines a discrete time iteration. The rule can also be made for continuous iterations as

${\displaystyle \,{\frac {d\mathbf {w} }{dt}}~=~\eta \,y(t)(\mathbf {x} (t)-y(t)\mathbf {w} (t)).}$

Derivation

The simplest learning rule known is Hebb's rule, which states in conceptual terms that neurons that fire together, wire together. In component form as a difference equation, it is written

${\displaystyle \,\Delta \mathbf {w} ~=~\eta \,y(\mathbf {x} _{n})\mathbf {x} _{n}}$,

or in scalar form with implicit n-dependence,

${\displaystyle \,w_{i}(n+1)~=~w_{i}+\eta \,y(\mathbf {x} )x_{i}}$,

where y(x_n) is again the output, this time explicitly dependent on its input vector x.

Hebb's rule has synaptic weights approaching infinity with a positive learning rate. We can stop this by normalizing the weights so that each weight's magnitude is restricted between 0, corresponding to no weight, and 1, corresponding to being the only input neuron with any weight. We do this by normalizing the weight vector to be of length one:

${\displaystyle \,w_{i}(n+1)~=~{\frac {w_{i}+\eta \,y(\mathbf {x} )x_{i}}{\left(\sum _{j=1}^{m}[w_{j}+\eta \,y(\mathbf {x} )x_{j}]^{p}\right)^{1/p}}}}$.

Note that in Oja's original paper,[1] p=2, corresponding to quadrature (root sum of squares), which is the familiar Cartesian normalization rule. However, any type of normalization, even linear, will give the same result without loss of generality.

For a small learning rate ${\displaystyle |\eta |\ll 1}$ the equation can be expanded as a Power series in ${\displaystyle \eta }$.[1]

${\displaystyle \,w_{i}(n+1)~=~{\frac {w_{i}}{\left(\sum _{j}w_{j}^{p}\right)^{1/p}}}~+~\eta \left({\frac {yx_{i}}{\left(\sum _{j}w_{j}^{p}\right)^{1/p}}}-{\frac {w_{i}\sum _{j}yx_{j}w_{j}^{p-1}}{\left(\sum _{j}w_{j}^{p}\right)^{(1+1/p)}}}\right)~+~O(\eta ^{2})}$.

For small η, our higher-order terms O(η²) go to zero. We again make the specification of a linear neuron, that is, the output of the neuron is equal to the sum of the product of each input and its synaptic weight, or

${\displaystyle \,y(\mathbf {x} )~=~\sum _{j=1}^{m}x_{j}w_{j}}$.

We also specify that our weights normalize to 1, which will be a necessary condition for stability, so

${\displaystyle \,|\mathbf {w} |~=~\left(\sum _{j=1}^{m}w_{j}^{p}\right)^{1/p}~=~1}$,

which, when substituted into our expansion, gives Oja's rule, or

${\displaystyle \,w_{i}(n+1)~=~w_{i}+\eta \,y(x_{i}-w_{i}y)}$.

Stability and PCA

In analyzing the convergence of a single neuron evolving by Oja's rule, one extracts the first principal component, or feature, of a data set. Furthermore, with extensions using the Generalized Hebbian Algorithm, one can create a multi-Oja neural network that can extract as many features as desired, allowing for principal components analysis.

A principal component a_j is extracted from a dataset x through some associated vector q_j, or a_j = q_j⋅x, and we can restore our original dataset by taking

${\displaystyle \mathbf {x} ~=~\sum _{j}a_{j}\mathbf {q} _{j}}$.

In the case of a single neuron trained by Oja's rule, we find the weight vector converges to q₁, or the first principal component, as time or number of iterations approaches infinity. We can also define, given a set of input vectors X_i, that its correlation matrix R_ij = X_iX_j has an associated eigenvector given by q_j with eigenvalue λ_j. The variance of outputs of our Oja neuron σ²(n) = ⟨y²(n)⟩ then converges with time iterations to the principal eigenvalue, or

${\displaystyle \lim _{n\rightarrow \infty }\sigma ^{2}(n)~=~\lambda _{1}}$.

These results are derived using Lyapunov function analysis, and they show that Oja's neuron necessarily converges on strictly the first principal component if certain conditions are met in our original learning rule. Most importantly, our learning rate η is allowed to vary with time, but only such that its sum is divergent but its power sum is convergent, that is

${\displaystyle \sum _{n=1}^{\infty }\eta (n)=\infty ,~~~\sum _{n=1}^{\infty }\eta (n)^{p}<\infty ,~~~p>1}$.

Our output activation function y(x(n)) is also allowed to be nonlinear and nonstatic, but it must be continuously differentiable in both x and w and have derivatives bounded in time.[2]

Generalizations

Recently, in the context of associative learning, it has been shown that the Hebbian rule, which is similar to Oja's rule, can be generalized using an Ising-like model:[3] The main idea of the generalization is based on formulating energy function like in Ising model and then applying stochastic gradient descent algorithm to this energy function. The energy function and the update rule corresponding to following the derivative are given by:

${\displaystyle E(\mathbf {w} )=-h\mathbf {w} -b\mathbf {w} ^{\top }\mathbf {V} \mathbf {w} -c\mathbf {w} ^{\top }\mathbf {x} y}$,

${\displaystyle \mathbf {w} _{n+1}=\mathbf {w} _{n}+\eta (h+b(\mathbf {V} +\mathbf {V} ^{\top })\mathbf {w} _{n}+c\mathbf {x} _{n+1}y_{n+1})}$,

where: ${\displaystyle y\in \{-1,1\}}$, ${\displaystyle b\in \mathbb {R} }$ is the coupling among inputs, ${\displaystyle c>0}$ is the correlation strength between the model and the output, ${\displaystyle h\in \mathbb {R} }$ corresponds to the presence of an external magnetic field, ${\displaystyle \mathbf {V} \in \{0,1\}^{D\times D}}$ determines the connections among inputs.

Then, for ${\displaystyle h=0}$, ${\displaystyle b=0}$, and ${\displaystyle c=1}$ we get the Hebbian rule, and for ${\displaystyle h=0}$, ${\displaystyle b=-0.5}$, ${\displaystyle c=1}$, and ${\displaystyle \mathbf {V} =\mathbf {I} }$, where ${\displaystyle \mathbf {I} }$ is an identity matrix, introduce weight decay. The formula then reduces to:

${\displaystyle \mathbf {w} _{n+1}=\mathbf {w} _{n}+\eta (2b\mathbf {w} _{n}+\mathbf {x} _{n+1}y_{n+1})}$,

Applications

Oja's rule was originally described in Oja's 1982 paper,[1] but the principle of self-organization to which it is applied is first attributed to Alan Turing in 1952.[2] PCA has also had a long history of use before Oja's rule formalized its use in network computation in 1989. The model can thus be applied to any problem of self-organizing mapping, in particular those in which feature extraction is of primary interest. Therefore, Oja's rule has an important place in image and speech processing. It is also useful as it expands easily to higher dimensions of processing, thus being able to integrate multiple outputs quickly. A canonical example is its use in binocular vision.[4]

Biology and Oja's subspace rule

There is clear evidence for both long-term potentiation and long-term depression in biological neural networks, along with a normalization effect in both input weights and neuron outputs. However, while there is no direct experimental evidence yet of Oja's rule active in a biological neural network, a biophysical derivation of a generalization of the rule is possible. Such a derivation requires retrograde signalling from the postsynaptic neuron, which is biologically plausible (see neural backpropagation), and takes the form of

${\displaystyle \Delta w_{ij}~\propto ~\langle x_{i}y_{j}\rangle -\epsilon \left\langle \left(c_{\mathrm {pre} }*\sum _{k}w_{ik}y_{k}\right)\cdot \left(c_{\mathrm {post} }*y_{j}\right)\right\rangle ,}$

where as before w_ij is the synaptic weight between the ith input and jth output neurons, x is the input, y is the postsynaptic output, and we define ε to be a constant analogous the learning rate, and c_pre and c_post are presynaptic and postsynaptic functions that model the weakening of signals over time. Note that the angle brackets denote the average and the ∗ operator is a convolution. By taking the pre- and post-synaptic functions into frequency space and combining integration terms with the convolution, we find that this gives an arbitrary-dimensional generalization of Oja's rule known as Oja's Subspace,[5] namely

${\displaystyle \Delta w~=~Cx\cdot w-w\cdot Cy.}$[6]

See also

• BCM theory
• Synaptic plasticity
• Self-organizing map
• Principal components analysis
• Independent components analysis
• Generalized Hebbian Algorithm

References

1. Oja, Erkki (November 1982). "Simplified neuron model as a principal component analyzer". Journal of Mathematical Biology. 15 (3): 267–273. doi:10.1007/BF00275687. PMID 7153672. BF00275687.
2. Haykin, Simon (1998). Neural Networks: A Comprehensive Foundation (2 ed.). Prentice Hall. ISBN 978-0-13-273350-2.
3. Jakub M. Tomczak, Associative learning using Ising-like model, in Advances in Systems Science, (eds.) Jerzy Świątek, Adam Grzech, Paweł Świątek, Jakub M. Tomczak, Advances in Intelligent and Soft Computing, Vol. 240, Springer-Verlag, 2014, pp. 295-304, PDF
4. Intrator, Nathan (2007). "Unsupervised Learning". Neural Computation lectures. Tel-Aviv University. Retrieved 2007-11-22.
5. Oja, Erkki (1989). "Neural Networks, Principal Components, and Subspaces". International Journal of Neural Systems. 1 (1): 61–68. doi:10.1142/S0129065789000475.
6. Friston, K.J.; C.D. Frith; R.S.J. Frackowiak (22 October 1993). "Principal Component Analysis Learning Algorithms: A Neurobiological Analysis". Proceedings: Biological Sciences. 254 (1339): 47–54. Bibcode:1993RSPSB.254...47F. doi:10.1098/rspb.1993.0125. JSTOR 49565. PMID 8265675.

External links

• Oja, Erkki: Oja learning rule in Scholarpedia
• Oja, Erkki: Aalto University