Spectral error correcting output codes for efficient multiclass recognition

The error correcting output codes (ECOC) is a general framework to extend any binary classifier to the multiclass case. Finding the optimal ECOC is known as a NP hard problem. In this paper, we present a spectral analysis approach for the design of ECOC. We construct a similarity graph of the classes and generate ECOC with a subset of thresholded eigenvectors of the graph Laplacian. Using the spectral analysis, the coding efficiency, classifier´s diversity, Hamming distance among codewords, and binary classifiers´ accuracy can be simultaneously considered. The resulting ECOC is efficient, thus only a small set of binary classifiers are to be evaluated when making a decision. In experiments with large multiclass problems, our method is between 3 and 12 times faster comparing to one-against-all, with comparable classification accuracy. Our method also shows a better performance than the most of leading methods, e.g., ClassMap, random dense ECOC, random sparse ECOC, and discriminant ECOC.