On Nearest-Neighbor Error-Correcting Output Codes with Application to All-Pairs Multiclass Support Vector Machines

Aldebaro Klautau, Nikola Jevtić, Alon Orlitsky; 4(Apr):1-15, 2003.

Abstract

A common way of constructing a multiclass classifier is by combining the outputs of several binary ones, according to an error-correcting output code (ECOC) scheme. The combination is typically done via a simple nearest-neighbor rule that finds the class that is closest in some sense to the outputs of the binary classifiers. For these nearest-neighbor ECOCs, we improve existing bounds on the error rate of the multiclass classifier given the average binary distance. The new bounds provide insight into the one-versus-rest and all-pairs matrices, which are compared through experiments with standard datasets. The results also show why elimination (also known as DAGSVM) and Hamming decoding often achieve the same accuracy.

[abs][pdf][ps.gz][ps]