Abstract
The process of representing a large data set with a smaller number of vectors in the best possible way, also known as vector quantization, has been intensively studied in the recent years. Very efficient algorithms like the Kohonen self-organizing map (SOM) and the Linde Buzo Gray (LBG) algorithm have been devised. In this paper a physical approach to the problem is taken, and it is shown that by considering the processing elements as points moving in a potential field an algorithm equally efficient as the before mentioned can be derived. Unlike SOM and LBG this algorithm has a clear physical interpretation and relies on minimization of a well defined cost function. It is also shown how the potential field approach can be linked to information theory by use of the Parzen density estimator. In the light of information theory it becomes clear that minimizing the free energy of the system is in fact equivalent to minimizing a divergence measure between the distribution of the data and the distribution of the processing elements, hence, the algorithm can be seen as a density matching method.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
Abbreviations
- C-S:
-
Cauchy–Schwartz
- K-L:
-
Kullback–Leibler
- LBG:
-
Linde Buzo Gray
- PE:
-
Processing element
- SOM:
-
Self-organized map
- QE:
-
Quantization error
- VQIT:
-
Vector Quantization using information theoretic concepts
References
Bishop CM, Svensen M and Williams CKI (1996) GTM: a principled alternative to the self-organizing map. Artificial Neural Networks–ICANN 96. 1996 International Conference Proceedings pp. 165–701.
R Durbin D Willshaw (1987) ArticleTitleAn analogue approach of the travelling salesman problem using an elastic net method Nature 326 689–691
Erdogmus D and Principe JC (2002) Generalized information potential criterion for adaptive system training. IEEE Transactions on Neural Networks 13(5).
D Erdogmus JC Principe K Hild (2002) ArticleTitleBeyond second-order statistics for learning Natural Computing 1 IssueID1 85–108
E Erwin K Obermayer K Schulten (1992) ArticleTitleSelf-organizing maps: ordering, convergence properties and energy functions Biological Cybernetics 67 4755
T Graepel M Burger K Obermeyer (1995) ArticleTitlePhase transitions in stochastic self-organizing maps Physical Review E 56 IssueID4 3876–3890
T Heskes (1999) Energy functions for self-organizing maps SE Oja Kaski (Eds) Kohonen Maps Elsevier Amsterdam 303–316
T Heskes B Kappen (1993) ArticleTitleError potentials for self-organization Proceedings IJCNN93 3 1219–1223
T Kohonen (1982) ArticleTitleSelf-organized formation of topologically correct feature maps Biological Cybernetics 43 59–69
S Kullback RA Leibler (1951) ArticleTitleOn information and sufficiency The Annals of Mathematical Statistics 22 79–86
Lampinen J and Kostiainen T (2002) Generative probability density model in the self organizing map.
Y Linde A Buzo RM Gray (1980) ArticleTitleAn algorithm for vector quantizer design IEEE Trans Commun COM 28 84–95
J MacQueen (1967) ArticleTitleSome methods for classification and analysis of multivariate observations Proceedings of the Fifth Berkeley Symposium on Mathematical statistics and probability 1 281–297
J Mercer (1909) ArticleTitleFunctions of positive and negative type and their connection with the theory of integral equations Philosophical Transactions Royal Society London A 209 415–446
E Parzen (1962) ArticleTitleOn estimation of a probability density function and mode Annals of Mathematical Statistic 27 1065–1076
JC Principe D Xu Q Zhao J Fisher (2000) ArticleTitleLearning from examples with information theoretic criteria Journal of VLSI Signal Processing-Systems 26 IssueID1-2 61–77
A Rényi (1970) Probability Theory North-Holland Publishing Company Amsterdam
CL Scofield (1988) ArticleTitleUnsupervised learning in the N-dimensional Coulomb network Neural Networks 1 IssueID1 129
J Sum C-S Leung L-W Chan L Xu (1997) ArticleTitleYet another algorithm which can generate topography map IEEE Transactions on Neural Networks 8 IssueID5 1204–1207
MM Hulle ParticleVan (2002) ArticleTitleKernel-based topographic map formation achieved with an information-theoretic approach Neural Networks 15 IssueID8-9 1029–1039
VN Vapnik (1995) The Nature of Statistical Learning Theory Springer-Verlag New York
H Yin N Allinson (2001) ArticleTitleSelf-organizing mixture networks for probability density estimation IEEE Transactions on Neural Networks 12 IssueID2 405–411
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Lehn-schiøler, T., Hegde, A., Erdogmus, D. et al. Vector quantization using information theoretic concepts. Nat Comput 4, 39–51 (2005). https://doi.org/10.1007/s11047-004-9619-8
Issue Date:
DOI: https://doi.org/10.1007/s11047-004-9619-8