Deterministic Annealing for Topographic Vector Quantization and Self-Organizing Maps

Graepel Thore, Computer Science Department, FR 2-1, KON, Technical University of Berlin, Franklinstr. 28/29, 10587 Berlin, Germany,
Burger Matthias, Computer Science Departement, FR 2-1, KON, Technical University of Berlin, Franklinstr. 28/29, 10587 Berlin, Germany,
Obermayer Klaus, Computer Science Department, Fr 2-1, KON, Technical University of Berlin, Franklinstr. 28/29, 10587 Berlin, Germany
Email: burger@cs.tu-berlin.de


Abstract:

We have developed a robust optimization scheme for self-organizing maps in the framework of noisy vector quantization. Based on a cost function that takes distortions from channel noise into account we derive a fuzzy algorithm of EM-type for topographic vector quantization (STVQ) which employes deterministic annealing. This annealing process leads to phase transitions in the cluster representation for which we are able to calculate critical modes and temperatures as a function of the neighbourhood function and the covariance matrix of the data. Similar results are obtained for the automatic selection of feature dimensions. Deterministic annealing also offers an alternative to the heuristic stepwise shrinking of the neighbourhood width in the SOM and makes it possible to use the neighbourhood solely to encode desired neighbourhood relations between the clusters. A soft version of the SOM (SSOM) is derived as a computationally efficient approximation to the E-step of STVQ. Both methods are numerically tested on a two-dimensional map of the plane and! we conclude that the temperature annealing can be precisely controlled and could for many applications be the method of choice.

Paper in PostScript


WSOM'97