A 'PAC' Algorithm for Making Feature Maps

Abstract

Kohonen and others have devised network algorithms for computing so-called topological feature maps . We describe a new algorithm, called the CDF-Inversion (CDFI) Algorithm, that can be used to learn feature maps and, in the process, approximate an unknown probalility distribution to within any specified accuracy. The primary advantags of the algorithm over previous feature-map algorithms are that it is simple enough to analyze mathematically for correctness and efficiency, and that it distributes the points of the map evenly, in a sense that can be made rigorous. Like other vector-quantization algorithms it is potentially useful for many applications, including monitoring and statistical modeling. While not a network algorithm, the CDFI algorithm is well-suited to implementation on parallel computers.