纠错输出编码的留一误差界估计

纠错输出编码（ECOC）作为分解框架，将多类分类问题转化为二类分类问题，是解决多类分类问题的有效手段。为了提高ECOC的泛化性能，对ECOC基分类器的设计问题进行了研究。解决这一问题的关键是对ECOC的泛化性能进行估计。留一（LOO）误差作为泛化性能的无偏估计，研究了ECOC留一误差界的估计问题。先给出了ECOC留一误差的定义，基于此定义，再给出了基分类器为支持向量机（SVM），解码方法为线性损失函数解码时，ECOC留一误差的上界和下界。在人工数据集和UCI数据集上的实验表明，ECOC留一误差的上界可以指导基分类器的参数选择，通过基分类器设计可以提高ECOC的泛化性能。此外，ECOC的训练误差可以作为ECOC留一误差的下界，对ECOC留一误差下界的研究可以作为未来的研究方向。

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 general-ization 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.