Learning Dynamics and Robustness of Vector Quantization and ...
learning dynamics and robustness of
vector quantization and neural gas
aree witoelar a,∗ michael biehl a anarta ghosh b barbara hammer c
a university of groningen, mathematics and computing science, p.o. box 800, nl-9700 av groningen, the netherlands
b wanprc, university of washington, seattle, wa-98195, usa
c clausthal university of technology, institute of computer science, d-98678 clausthal-zellerfeld, germany
various alternatives have been developed to improve the winner-takes-all (wta) mechanism in vector quantiza-
tion, including the neural gas (ng). however, the behavior of these algorithms including their learning dynamics,
robustness with respect to initialization, asymptotic results, etc. has only partially been studied in a rigorous mathe-
matical analysis. the theory of on-line learning allows for an exact mathematical description of the training dynamics
in model situations. we demonstrate using a system of three competing prototypes trained from a mixture of gaussian
clusters that the neural gas can improve convergence speed and achieves robustness to initial conditions. however,
depending on the structure of the data, the neural gas does not always obtain the best asymptotic quantization ***or.
key words: vector quantization, clustering, online learning, winner-takes-all algorithms, neural gas
1. introduction a variety of alternatives to overcome this problem
have been proposed, some of which are heuristically
vector quantization (vq) is an important unsu- motivated while others are based on the minimiza-
pervised learning algorithm, widely used in diﬀerent tion of a cost function related to the quantization
areas such as data mining, medical analysis, image ***or: the self-organizing map (som) , fuzzy-
compression, and speech or handwriting recognition k-means , stochastic optimization , to name
. the main objective of vq is to represent the data just a few. these algorithms have in common that
points by a small number of prototypes or codebook each pattern inﬂuences more than one prototype at
vectors. this can directly be used for compression, a time through a ”winner-takes-most” paradigm.
clustering, data mining, or (with post-labeling of the neural gas (ng) as proposed in  is a particularly
prototypes) classiﬁcation [9,14]. robust variation of vector quantization with the
the basic ”winner-takes-all” (wta) or batch introduction of neighborhood relations. unlike the
algorithms like the popular k-means clustering di- self-organizing map, , the ng system takes into
rectly optimize the quantization ***or underlying account the relative distances between prototypes
vector quantization. however, these methods can be in the input space and not on a predeﬁned lattice.
subject to conﬁnement in local minima of the quan- in practice, ng algorithms yield better solutions
tization ***or and can produce suboptimal results. than wta; however, the eﬀect of this strategy
on convergence speed or asymptotic behavior has
∗ corresponding author. hardly been rigorously investigated so far.
email address: [email protected] (aree witoelar). methods from statistical physics and the theory
url: http://www.cs.rug/∼aree (aree witoelar).
preprint submitted to elsevier 8 november 2007
of on-line learning  allow for an exact mathemat- the input data is presented sequentially during
ical description of learning systems for high dimen- training and one or more prototypes are updated on-
sional data. in the limit of inﬁnite dimensionality, line. algorithms studied here can be interpreted as
such systems can be fully described in terms of a few stochastic gradient descent procedures with respect
characteristic quantities, the so-called order param- to a cost function h(w ) related to e(w ). the gen-
eters. the evolution of these order parameters along eralized form reads
the training procedure is characterized by a set of s
coupled ordinary diﬀerential equations (ode). by 1
h(w ) = dξp (ξ) d(ξ, wi )f (ri )
integrating these odes, it is possible to analyse the 2 i=1
performance of vq algorithms in term
- Related pdf books
- Software Component Model for Field Devices
- The electronic government and its client systems
- Visualizing Time-Dependent Software Artifacts
- Learning Technology Systems: issues, trends, challenges
- CLUSTERING OF ARTICLE BLOCKS IN NEWSPAPER PAGES ...
- Constructive Solid Geometry and Volume Rendering
- Toward new software for computational phylogenetics - Computer
- A S V C S tu - University of Groningen
- A Visual Analytics Toolset for Program Structure, Metrics ...
- A Prototype System for Real Time Computer Animation of Slow ...
- Stakeholders-Driven Requirements Semantics Acquisition for ...
- Temporal Monitors for TinyOS
- Developing an architecture for the software subsystem of a ...
- Incomplete Contour Representations and Shape Descriptors: ICR ...
- Progress with Java threads as dining philosophers
- Management and Evolution of Business Process Variants
- On the convergence of the iterative solution of the likelihood
- Popular epubs
- Lecture 19: Quantization of the simple harmonic oscillator
- ROBUSTNESS OF SUBJECTIVE WELFARE ANALYSIS IN A POOR DEVELOPING ...
- Informational Robustness of Competitive Equilibria
- The Techniques for Face Recognition with Support Vector Machines
- Lagrangian Support Vector Machines - David R. Musicant dmusican ...
- Vector Control Program of Chagas disease In Ceará State – 1975 ...
- Application of Support Vector Machine-Based Semiactive Control for ...
- Modeling and Predicting Behavioral Dynamics on the Web
- Understanding Structure, Function and Conformational Dynamics of ...
- WALNUT POLLINATION DYNAMICS: POLLEN FLOW AND POLLEN LOADS IN ...