1
$\begingroup$

I have to give a presentation on unsupervised learning in 2 days, and I have to explain/show the equivalence between Hebb's learning rule (or Oja's rule to be more specific) and PCA. The thing is that I haven't taken a linear algebra class yet, and therefore I haven't been able to understand any of the proofs I came across since they all rely heavily on linear algebra. So, can some explain to me the equivalence in layman's words? I think an intuitive explanation of what it is PCA does that Oja's rule does would be enough for the presentation.

P.S I watched computerphile's video on PCA, and I understand that PCA finds orthogonal unit vectors representing best-fitting lines for the data, which allows us to reduce its dimensionality. However, I didn't go over the formulas since they need a minimum understanding of Eigenvalues and -vectors.

New contributor
Mohamed Fathy is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
5
  • $\begingroup$ Having not known what Oja's rule was before reading it, I feel the Wikipedia article for Hebbian learning a pretty good job of explaining the connection. $\endgroup$
    – Tyberius
    Nov 23 at 2:29
  • $\begingroup$ How good are you with vector-matrix products, vector norms, the Euclidean norm and scalar product, at least in the form $\|x\|=\sqrt{x^Tx}$? Do you know the matrix trace and understand the rule $tr(AB)=tr(BA)$? $\endgroup$ Nov 23 at 9:57
  • $\begingroup$ @LutzLehmann I'm familiar with most of these concepts, at least on a definition-level; i.e. I understand how to perform them, but I'm not sure what some of them "mean" or represent. $\endgroup$ Nov 23 at 12:49
  • $\begingroup$ Next, can you check your claim, is it really that the learning rule is equivalent to the computation of the full PCA of $X$ (equal the eigen-decomposition of $X^TX$, which can be more comfortably computed from the SVD, singular value decomposition of $X$)? The sources only claim the approximation of the dominant principal component. $\endgroup$ Nov 23 at 14:25
  • $\begingroup$ Of course the extended sources (or a fuller reading of them) contain generalized methods with multiple outputs, which could correspond to the next-largest principal components. The wikipedia articles are quite confusing on the generalizations, it is not quite clear what is vector and matrix, what is normal matrix multiplication and what a non-standard operation. $\endgroup$ Nov 23 at 20:48
1
$\begingroup$

The wikipedia article on Hebbsian learning with one node is good. You should be able to grasp the idea of "burning in" the weights at connections of the same polarity and "erasing" the weights where there are opposite signs.

Next you need to comprehend the stochastics, that $$ \Delta w_k=\eta x_kx_k^Tw\Delta t $$ averages out for small $\eta\Delta t$ to $$ \Delta w_k=\eta X^TXw\,\Delta t+O(\Delta t^2), $$ where the rows of $X$ are the vectors $x_k$ (or more precisely, $x_k^T$). This transposition is for convenience, to better connect to conventions in other related topics.

This can now be further approximated to the differential equation $$ \dot w=\eta Cw $$ with the correlation matrix $C=X^TX$. Such linear systems have exponential growth, generally either exploding to infinity or converging to the zero vector. In the application one is however only interested in the relative sizes of the weights, so one can either scale this vector after each step or force it directly to stay inside some radius range. This latter can generally be achieved as $$ \dot w=\eta (Cw-\lambda(w)w) $$ with some scalar-valued function $\lambda(w)$. Exploring the dynamic of the squared radius $$ \frac12\frac{d}{dt}\|w\|^2=w^T\dot w=\eta (w^TCw-\lambda(w)\|w\|^2) $$ gives a fixed point at $\|w\|=1$ when setting $\lambda(w)=w^TCw$. This is stable, deviations from this radius get corrected towards the unit radius.

Circling back to the stochastic discrete step equation, the same approach towards a modification in radial direction gives $$ \Delta w_k=\eta (x_kx_k^Tw-\lambda(x_k,w)w)\,\Delta t. $$ Then the dynamic of the radius is approximately $$ \frac12(\|w_{k+1}\|^2-\|w_k\|^2)\approx (|x_k^Tw|^2-\lambda(x_k,w)\|w\|^2)\,\Delta t $$ so that with $\lambda(x_k,w)=|x_k^Tw|^2$ there is again a forcing towards the unit radius, that is, most importantly, neither growing to large values nor vanishing in small values and underflow.

Now to finish up, the stationary points of the averaged differential equation $$ \dot w=\eta (Cw-\lambda(w)w) $$ are the eigenvectors of $C$. Only the maximal one is dynamically stable, the others are saddle points, even at the minimal eigenvalue the radial direction is stable, the directions tangential to the sphere are all unstable.

With all probability the stochastic iteration will follow the flow towards the most stable state. Coincidentially, an eigenvector of $C$ is a principal component of $X$, and also a right singular vector in the singular value decomposition $X=U\Sigma V^T$. With the standard algorithms (Golub-Kahan) the computation of an SVD is a little more numerically well-conditioned than a PCA computation via matrix product and eigen-decomposition.

$\endgroup$
1
  • $\begingroup$ Thanks a lot for your explaination and for the effort you had put into your answer :) $\endgroup$ Nov 25 at 15:46

Your Answer

Mohamed Fathy is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.