Generalized Hebbian algorithm

<h2 id="theory">Theory</h2>
Consider a problem of learning a linear code for some data. Each data is a multi-dimensional vector 
 
 
 
 x
 ∈
 
 
 R
 
 
 n
 
 
 
 
 {\displaystyle x\in \mathbb {R} ^{n}}
 
, and can be (approximately) represented as a linear sum of linear code vectors 
 
 
 
 
 w
 
 1
 
 
 ,
 …
 ,
 
 w
 
 m
 
 
 
 
 {\displaystyle w_{1},\dots ,w_{m}}
 
. When 
 
 
 
 m
 =
 n
 
 
 {\displaystyle m=n}
 
, it is possible to exactly represent the data. If 
 
 
 
 m
 <
 n
 
 
 {\displaystyle m<n}
 
, it is possible to approximately represent the data. To minimize the L2 loss of representation, 
 
 
 
 
 w
 
 1
 
 
 ,
 …
 ,
 
 w
 
 m
 
 
 
 
 {\displaystyle w_{1},\dots ,w_{m}}
 
 should be the highest principal component vectors.
The generalized Hebbian algorithm is an iterative algorithm to find the highest principal component vectors, in an algorithmic form that resembles <a href="/facts/Unsupervised_learning/8a6f61MC">unsupervised</a> Hebbian learning in neural networks.
Consider a one-layered neural network with 
 
 
 
 n
 
 
 {\displaystyle n}
 
 input neurons and 
 
 
 
 m
 
 
 {\displaystyle m}
 
 output neurons 
 
 
 
 
 y
 
 1
 
 
 ,
 …
 ,
 
 y
 
 m
 
 
 
 
 {\displaystyle y_{1},\dots ,y_{m}}
 
. The linear code vectors are the connection strengths, that is, 
 
 
 
 
 w
 
 i
 j
 
 
 
 
 {\displaystyle w_{ij}}
 
 is the <a href="/facts/Synaptic_weight/HPmNlR3j">synaptic weight</a> or connection strength between the 
 
 
 
 j
 
 
 {\displaystyle j}
 
-th input and 
 
 
 
 i
 
 
 {\displaystyle i}
 
-th output neurons.
The generalized Hebbian algorithm learning rule is of the form

Δ
        
          w
          
            i
            j
          
        
         
        =
         
        η
        
          y
          
            i
          
        
        
          (
          
            
              x
              
                j
              
            
            −
            
              ∑
              
                k
                =
                1
              
              
                i
              
            
            
              w
              
                k
                j
              
            
            
              y
              
                k
              
            
          
          )
        
      
    
    {\displaystyle \,\Delta w_{ij}~=~\eta y_{i}\left(x_{j}-\sum _{k=1}^{i}w_{kj}y_{k}\right)}

where 
 
 
 
 η
 
 
 {\displaystyle \eta }
 
 is the <a href="/facts/Learning_rate/EClSgMCR">learning rate</a> parameter.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>

<h3>Derivation</h3>
In matrix form, Oja's rule can be written

d
 
 w
 (
 t
 )
 
 
 
 d
 
 t
 
 
 
  
 =
  
 w
 (
 t
 )
 Q
 −
 
 d
 i
 a
 g
 
 [
 w
 (
 t
 )
 Q
 w
 (
 t
 
 )
 
 
 T
 
 
 
 ]
 w
 (
 t
 )
 
 
 {\displaystyle \,{\frac {{\text{d}}w(t)}{{\text{d}}t}}~=~w(t)Q-\mathrm {diag} [w(t)Qw(t)^{\mathrm {T} }]w(t)}
 
,
and the Gram-Schmidt algorithm is

Δ
 w
 (
 t
 )
  
 =
  
 −
 
 l
 o
 w
 e
 r
 
 [
 w
 (
 t
 )
 w
 (
 t
 
 )
 
 
 T
 
 
 
 ]
 w
 (
 t
 )
 
 
 {\displaystyle \,\Delta w(t)~=~-\mathrm {lower} [w(t)w(t)^{\mathrm {T} }]w(t)}
 
,
where w(t) is any matrix, in this case representing synaptic weights, Q = η x xT is the autocorrelation matrix, simply the outer product of inputs, diag is the function that <a href="/facts/Matrix_diagonalization/y3MkyTCy">diagonalizes</a> a matrix, and lower is the function that sets all matrix elements on or above the diagonal equal to 0. We can combine these equations to get our original rule in matrix form,

Δ
 w
 (
 t
 )
  
 =
  
 η
 (
 t
 )
 
 (
 
 
 y
 
 (
 t
 )
 
 x
 
 (
 t
 
 )
 
 
 T
 
 
 
 −
 
 L
 T
 
 [
 
 y
 
 (
 t
 )
 
 y
 
 (
 t
 
 )
 
 
 T
 
 
 
 ]
 w
 (
 t
 )
 
 )
 
 
 
 {\displaystyle \,\Delta w(t)~=~\eta (t)\left(\mathbf {y} (t)\mathbf {x} (t)^{\mathrm {T} }-\mathrm {LT} [\mathbf {y} (t)\mathbf {y} (t)^{\mathrm {T} }]w(t)\right)}
 
,
where the function LT sets all matrix elements above the diagonal equal to 0, and note that our output y(t) = w(t) x(t) is a linear neuron.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>

<h3>Stability and Principal Components Analysis</h3>
<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>
<a href="/facts/Oja%27s_rule/RnvIoB5F">Oja's rule</a> is the special case where 
 
 
 
 m
 =
 1
 
 
 {\displaystyle m=1}
 
.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> One can think of the generalized Hebbian algorithm as iterating Oja's rule. 
With Oja's rule, 
 
 
 
 
 w
 
 1
 
 
 
 
 {\displaystyle w_{1}}
 
 is learned, and it has the same direction as the largest principal component vector is learned, with length determined by 
 
 
 
 E
 [
 
 x
 
 j
 
 
 ]
 =
 E
 [
 
 w
 
 1
 j
 
 
 
 y
 
 1
 
 
 ]
 
 
 {\displaystyle E[x_{j}]=E[w_{1j}y_{1}]}
 
 for all 
 
 
 
 j
 
 
 {\displaystyle j}
 
, where the expectation is taken over all input-output pairs. In other words, the length of the vector 
 
 
 
 
 w
 
 1
 
 
 
 
 {\displaystyle w_{1}}
 
 is such that we have an <a href="/facts/Autoencoder/jnTqhtm9">autoencoder</a>, with the latent code 
 
 
 
 
 y
 
 1
 
 
 =
 
 ∑
 
 i
 
 
 
 w
 
 1
 i
 
 
 
 x
 
 i
 
 
 
 
 {\displaystyle y_{1}=\sum _{i}w_{1i}x_{i}}
 
, such that 
 
 
 
 E
 [
 ‖
 x
 −
 
 y
 
 1
 
 
 
 w
 
 1
 
 
 
 ‖
 
 2
 
 
 ]
 
 
 {\displaystyle E[\|x-y_{1}w_{1}\|^{2}]}
 
 is minimized.
When 
 
 
 
 m
 =
 2
 
 
 {\displaystyle m=2}
 
, the first neuron in the hidden layer of the autoencoder still learns as described, since it is unaffected by the second neuron. So, after the first neuron and its vector 
 
 
 
 
 w
 
 1
 
 
 
 
 {\displaystyle w_{1}}
 
 has converged, the second neuron is effectively running another Oja's rule on the modified input vectors, defined by 
 
 
 
 
 x
 ′
 
 =
 x
 −
 
 y
 
 1
 
 
 
 w
 
 1
 
 
 
 
 {\displaystyle x'=x-y_{1}w_{1}}
 
, which we know is the input vector with the first principal component removed. Therefore, the second neuron learns to code for the second principal component. 
By induction, this results in finding the top-
 
 
 
 m
 
 
 {\displaystyle m}
 
 principal components for arbitrary 
 
 
 
 m
 
 
 {\displaystyle m}
 
.

<h2 id="applications">Applications</h2>
The generalized Hebbian algorithm is used in applications where a <a href="/facts/Self-organizing_map/uuMRbpkl">self-organizing map</a> is necessary, or where a feature or <a href="/facts/Principal_components_analysis/pCbVTqdR">principal components analysis</a> can be used. Examples of such cases include <a href="/facts/Artificial_intelligence/lJGauQwX">artificial intelligence</a> and speech and image processing.
Its importance comes from the fact that learning is a single-layer process—that is, a synaptic weight changes only depending on the response of the inputs and outputs of that layer, thus avoiding the multi-layer dependence associated with the <a href="/facts/Backpropagation/lCsIdKHc">backpropagation</a> algorithm. It also has a simple and predictable trade-off between learning speed and accuracy of convergence as set by the <a href="/facts/Learning/lehEKRjC">learning</a> rate parameter η.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>

As an example, (Olshausen and Field, 1996)<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> performed the generalized Hebbian algorithm on 8-by-8 patches of photos of natural scenes, and found that it results in Fourier-like features. The features are the same as the principal components found by principal components analysis, as expected, and that, the features are determined by the 
 
 
 
 64
 ×
 64
 
 
 {\displaystyle 64\times 64}
 
 variance matrix of the samples of 8-by-8 patches. In other words, it is determined by the second-order statistics of the pixels in images. They criticized this as insufficient to capture higher-order statistics which are necessary to explain the Gabor-like features of simple cells in the <a href="/facts/Primary_visual_cortex/qmF8F5Sb">primary visual cortex</a>.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Hebbian_learning/Mmtd6Dzt">Hebbian learning</a></li>
<li><a href="/facts/Factor_analysis/LT6B9I7D">Factor analysis</a></li>
<li><a href="/facts/Contrastive_Hebbian_learning/zTJ1v8SE">Contrastive Hebbian learning</a></li>
<li><a href="/facts/Oja%27s_rule/RnvIoB5F">Oja's rule</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Sanger, Terence D. (1989). "Optimal unsupervised learning in a single-layer linear feedforward neural network" (PDF). Neural Networks. 2 (6): 459–473. CiteSeerX 10.1.1.128.6893. doi:10.1016/0893-6080(89)90044-0. Retrieved 2007-11-24. <a href="/w/index.php?title=Terence_Sanger&action=edit&redlink=1" target="_blank">/w/index.php?title=Terence_Sanger&action=edit&redlink=1</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Hebb, D.O. (1949). The Organization of Behavior. New York: Wiley & Sons. ISBN 9781135631918. <a href="9781135631918" target="_blank">9781135631918</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Hertz, John; Anders Krough; Richard G. Palmer (1991). Introduction to the Theory of Neural Computation. Redwood City, CA: Addison-Wesley Publishing Company. ISBN 978-0201515602. <a href="978-0201515602" target="_blank">978-0201515602</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Gorrell, Genevieve (2006), "Generalized Hebbian Algorithm for Incremental Singular Value Decomposition in Natural Language Processing.", EACL, CiteSeerX 10.1.1.102.2084 <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Sanger, Terence D. (1989). "Optimal unsupervised learning in a single-layer linear feedforward neural network" (PDF). Neural Networks. 2 (6): 459–473. CiteSeerX 10.1.1.128.6893. doi:10.1016/0893-6080(89)90044-0. Retrieved 2007-11-24. <a href="/w/index.php?title=Terence_Sanger&action=edit&redlink=1" target="_blank">/w/index.php?title=Terence_Sanger&action=edit&redlink=1</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Haykin, Simon (1998). Neural Networks: A Comprehensive Foundation (2 ed.). Prentice Hall. ISBN 978-0-13-273350-2. <a href="978-0-13-273350-2" target="_blank">978-0-13-273350-2</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">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. S2CID 16577977. BF00275687. <a href="/wiki/Erkki_Oja" target="_blank">/wiki/Erkki_Oja</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Haykin, Simon (1998). Neural Networks: A Comprehensive Foundation (2 ed.). Prentice Hall. ISBN 978-0-13-273350-2. <a href="978-0-13-273350-2" target="_blank">978-0-13-273350-2</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Olshausen, Bruno A.; Field, David J. (June 1996). "Emergence of simple-cell receptive field properties by learning a sparse code for natural images". Nature. 381 (6583): 607–609. doi:10.1038/381607a0. ISSN 1476-4687. PMID 8637596. <a href="https://www.nature.com/articles/381607a0" target="_blank">https://www.nature.com/articles/381607a0</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
</ol>

Generalized Hebbian algorithm open-in-new

Generalized Hebbian algorithm