[IEEE Trans. on Patten Analysis and Machine Intelligence, March 2000, pp. 281-297]
Learning and Design of Principal Curves
Balázs Kégl, Adam Krzyżak, Tamás Linder, and Kenneth Zeger
Abstract
Principal curves have been defined as ``self consistent'' smooth
curves which pass through the ``middle'' of a d-dimensional
probability distribution or data cloud. They give a summary of the
data and also serve as an efficient feature extraction tool. We take a new
approach by defining principal curves as continuous curves of a given
length which minimize the expected squared distance between the curve
and points of the space randomly chosen according to a given
distribution. The new definition makes it possible to carry out a
theoretical analysis of learning principal curves from training data
and it also leads to a new practical construction. In our theoretical
learning scheme the classes are polygonal lines with k-segments and
with a given length, and the algorithm chooses a curve from this class
which minimizes the average squared distance over n training points
drawn independently. Convergence properties of this learning scheme
are analyzed. A practical version of this theoretical algorithm is
implemented. In each iteration of the algorithm a new vertex is added
to the polygonal line and the positions of the vertices are updated so
that they minimize a penalized squared distance criterion. Simulation
results demonstrate that the new algorithm compares favorably with
previous methods both in terms of performance and computational
complexity, and is more robust to varying data models.