Solving multi-class problems by data-driven topology-preserving output codes

Aiming at decomposing a complex multi-class problem into fewer and simpler sub-problems to gain an overall classifier of low complexity, we propose a universal data-driven topology-preserving output code (TPOC) scheme, and a computationally efficient supervised circular learning algorithm (CLA) for the learning of the required TPOC map in the scheme. The scheme leads to a compact code and low complexity, and is an extension of binary, ternary and ECOC code. Experiments on Iris data, NCI data, octaphase-shift-keying data and handwritten digits reveal that the scheme substantially outperforms DECOC, one-against-all, natural coding and ECOC in using a less complex classifier with no loss or even enhanced generalization performance: the total number of support vectors is reduced greatly in SVM study and that of synaptic weights is greatly reduced (e.g., by 86% with training time reduced by 98% in MLP study in handwritten digit recognition problem); the total number of synaptic weights is further reduced by about one-fourth with less than one-hundredth loss of generalization performance when classifier complexities are assigned adaptive to the coding process. Finally, it is successfully applied to automatic target recognition based on a real measured radar data.