Leave-one-out error bounds estimation for error correcting output codes

Error correcting output codes (ECOC) is a decomposition framework, which can transform a complex multiclass classification problem into a series of two-class classification problems. It can complete one multiclass classification task efficiently. To improve its generalization performance, we studied the design of its base classifier, which is also known as model selection in ECOC. The key point is how to estimate the generalization error of ECOC. Leave-one-out (LOO) error is an almost unbiased estimator of generalization error, so we studied how to estimate the LOO error bounds for ECOC. First, we provided the definition of LOO error for ECOC. And then, based on this definition, upper bound and lower bound of LOO error for ECOC was given under the condition that base classifiers were support vector machines (SVM) and decoding method was linear loss function. The experiments on synthetic dataset and UCI dataset show that the upper bound of LOO error for ECOC leads to good estimates of parameters in base classifiers, and designing base classifiers can improve the generalization performance of ECOC. Furthermore, we also report that training error is one lower bound of LOO error for ECOC, and the application of this lower bound should be studied in the future.