Geun Bae Song, Halng Sei Lee

The KIPS Transactions:PartB , Vol. 8, No. 4, pp. 343-350, Aug. 2001
10.3745/KIPSTB.2001.8.4.343,   PDF Download:

Abstract

Vector quantizer (VQ) design needs an algorithm to minimize a multidimensional objective function. The generalized Lloyd algorithm (GLA) is one of the most well-known such algorithms today. The GLA is a kind of descent algorithm which decreases monotonically an objective function and generates codebooks in a batch processing mode. The Kohonen learning algorithm (KLA) is an on-line VQ design algorithm, where the codebook is designed (or updated) while training data arrives. The KLA was proposed originally by Kohonen as a learning algorithm for neural networks. The KLA can be also considered as a kind of descent algorithm just as the GLA. Therefore, these two algorithms, although convenient to use, get entrapped into local minima for complex high-dimensional VQ design problems. To solve this entrapment issue we discuss the simulated annealing (SA) method which searches for a solution in a non-deterministic manner. The SA is the only method which is statistically guaranteed to yield globally optimal performance. We first review the previous work on the general formulation of the SA applied to batch processing VQ design, and then propose a new design algorithm based on the SA for on-line VQ design. We call this new algorithm OLVQ-SA. Experimental results for Gauss-Markov sources and real speech demonstrate that the proposed algorithm can consistently provide better codebooks than the KLA.

Statistics
Cite this article