Nearest-prototype classifier design by deterministic annealing with random class labels

The design of nearest-prototype (NP) classifiers is a challenging problem because of the prevalence of poor local minima, and the piecewise constant nature of the cost function which is incompatible with gradient-based techniques. The paper extends the deterministic annealing (DA) method for NP-classifier design in two ways. First, the association between prototypes and class labels is also randomized, and the corresponding association probabilities are added to the set of parameters to be optimized. Second, the multiplicity (or the mass) of prototypes are optimized. During the design, all parameters are optimized so as to minimize the expected misclassification rate for a given level of randomness. The joint entropy, which measures the level of randomness, is gradually reduced while optimizing the cost Lagrangian. As the entropy approaches zero, the method seeks a deterministic classifier that minimizes the rate of misclassification