Assuming $m$ observations, $n$ features and $k$ nodes in the self organizing map, what is the complexity of the classic SOM algorithm? What would be the complexity of an ensemble of SOMs, where each SOM has a different number of nodes?


According to this paper (1),

$$ T = O(NC) = O(S^2)$$ where $T$ is the computation time, $N$ is the input vector size and $C$ is the number of document presentation cycles. $S$ represents the size of the sample.

This site seems to agree with $O(S^2)$.

(1): Dmitri G. Roussinov, Hsinchun Chen. A Scalable Self-organizing Map Algorithm for Textual Classification: A Neural Network Approach to Thesaurus Generation

  • $\begingroup$ What does S stand for? $\endgroup$ – user1603472 Feb 2 '16 at 10:13
  • $\begingroup$ @user1603472 see above. So computation time increases proportionately to (data_size)^2 $\endgroup$ – Roman Feb 2 '16 at 11:14
  • $\begingroup$ Well, the SOM algorithm needs three loops 1) over epochs, 2) over samples, 3) over nodes/neurons. So the number of vector comparisons will be the product of ESN. Furthermore, the dimensionality D will determine the cost of the comparison. Of course, if any of them are thought of as constants, they will be dwarfed by the quadratic term in big-O analysis. So I think this analysis does not give the entire picture. Of course the running time will be different if the epochs are increased as well. $\endgroup$ – user1603472 Nov 7 '16 at 11:07

Your Answer

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.