5

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?

GS9
  • 233
  • 1
  • 3
  • 7

1 Answers1

2

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

Roman
  • 121
  • 5
  • What does S stand for? – user1603472 Feb 02 '16 at 10:13
  • @user1603472 see above. So computation time increases proportionately to (data_size)^2 – Roman Feb 02 '16 at 11:14
  • 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 E*S*N. 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. – user1603472 Nov 07 '16 at 11:07