Online error correcting output codes

This article proposes a general extension of the error correcting output codes framework to the online learning scenario. As a result, the final classifier handles the addition of new classes independently of the base classifier used. In particular, this extension supports the use of both online example incremental and batch classifiers as base learners. The extension of the traditional problem independent codings one-versus-all and one-versus-one is introduced. Furthermore, two new codings are proposed, unbalanced online ECOC and a problem dependent online ECOC. This last online coding technique takes advantage of the problem data for minimizing the number of dichotomizers used in the ECOC framework while preserving a high accuracy. These techniques are validated on an online setting of 11 data sets from UCI database and applied to two real machine vision applications: traffic sign recognition and face recognition. As a result, the online ECOC techniques proposed provide a feasible and robust way for handling new classes using any base classifier.     

Coding and decoding strategies for multi-class learning problems

It is known that the error correcting output code (ECOC) technique, when applied to multi-class learning problems, can improve generalisation performance. One reason for the improvement is its ability to decompose the original problem into complementary two-class problems. Binary classifiers trained on the sub-problems are diverse and can benefit from combining using a simple distance-based strategy. However there is some discussion about why ECOC performs as well as it does, particularly with respect to the significance of the coding/decoding strategy. In this paper we consider the binary (0,1) code matrix conditions necessary for reduction of error in the ECOC framework, and demonstrate the desirability of equidistant codes. It is shown that equidistant codes can be generated by using properties related to the number of 1’s in each row and between any pair of rows. Experimental results on synthetic data and a few popular benchmark problems show how performance deteriorates as code length is reduced for six decoding strategies.     

基于特征空间变换的纠错输出编码

针对基于纠错输出编码多类分类中如何保证基分类器差异性的问题, 提出一种基于特征空间变换的编码方法. 该方法引入特征空间, 将编码矩阵扩展成三维矩阵; 然后基于二类划分, 利用特征变换得到不同的特征子空间, 从而训练得到差异性大的基分类器. 基于公共数据集的实验结果表明: 该方法能够比原始的编码矩阵获得更优的分类性能, 同时增加了基分类器的差异性; 该方法适用于任何编码矩阵, 为大数据的分类提供了新的思路.

     

基于证据理论的纠错输出编码解决多类分类问题

针对多类分类问题,利用纠错输出编码作为分解框架,把多类问题转化为多个二类问题加以解决;同时提出一种基于证据理论的解码策略,把每一个二分器的输出作为证据之一进行融合,并讨论在两种编码类型(二元和三元编码矩阵)下证据融合的不同策略.通过实验分别对UCI数据集和3种一维距离像数据集进行测试,并与几种经典的解码方法进行比较,验证了所提出的方法能有效提高纠错输出编码特别是三元编码矩阵的分类正确率.     

Design of reject rules for ECOC classification systems

ECOC is a widely used and successful technique, which implements a multi-class classification system by decomposing the original problem into several two-class problems. In this paper, we study the possibility to provide ECOC systems with a tailored reject option carried out through different schemes that can be grouped under two different categories: an external and an internal approach. The first one is based on the reliability of the entire system output and does not require any change in its structure. The second scheme, instead, estimates the reliability of the internal dichotomizers and implies a slight modification in the decoding stage. Experimental results on popular benchmark data sets are reported to show the behavior of the different schemes.     

一种搜索编码法及其在监督分类中的应用

纠错输出码作为监督分类领域中的一个新的研究方向,是提高分类器泛化能力的一种有效方法,但目前还没有通用的确定性编码方法.分析了现有纠错输出码的性质,提出一种搜索编码法,该方法通过对整数空间的顺序搜索,获得满足任意类别数目与最小汉明距离要求的输出码;然后探讨了基于搜索编码的监督分类技术.对简单贝叶斯与BP神经网络算法进行实验,结果表明,搜索编码法可作为一种通用的编码方法用于提高监督分类器的泛化能力.     

On the design of an ECOC-Compliant Genetic Algorithm

Genetic Algorithms (GA) have been previously applied to Error-Correcting Output Codes (ECOC) in state-of-the-art works in order to find a suitable coding matrix. Nevertheless, none of the presented techniques directly take into account the properties of the ECOC matrix. As a result the considered search space is unnecessarily large. In this paper, a novel Genetic strategy to optimize the ECOC coding step is presented. This novel strategy redefines the usual crossover and mutation operators in order to take into account the theoretical properties of the ECOC framework. Thus, it reduces the search space and lets the algorithm to converge faster. In addition, a novel operator that is able to enlarge the code in a smart way is introduced. The novel methodology is tested on several UCI datasets and four challenging computer vision problems. Furthermore, the analysis of the results done in terms of performance, code length and number of Support Vectors shows that the optimization process is able to find very efficient codes, in terms of the trade-off between classification performance and the number of classifiers. Finally, classification performance per dichotomizer results shows that the novel proposal is able to obtain similar or even better results while defining a more compact number of dichotomies and SVs compared to state-of-the-art approaches.     

基于子类划分和粒子群优化的自适应编码多类分类方法

纠错输出编码(ECOC)可以有效地解决多类分类问题.基于数据的编码是主要的编码方法之一.对此,提出一种基于子类划分和粒子群优化(PSO)的自适应编码方法,利用混淆矩阵衡量各类别的相关性,基于规则的方法对类别进行自适应组合,根据组合方案构建类别的二类划分并最终形成编码矩阵,通过引入PSO算法寻找最优阈值,从而得到最优编码矩阵.实验结果表明,所提出的编码方法可以得到更好的分类性能.     

Traffic sign recognition system with β -correction

Traffic sign classification represents a classical application of multi-object recognition processing in uncontrolled adverse environments. Lack of visibility, illumination changes, and partial occlusions are just a few problems. In this paper, we introduce a novel system for multi-class classification of traffic signs based on error correcting output codes (ECOC). ECOC is based on an ensemble of binary classifiers that are trained on bi-partition of classes. We classify a wide set of traffic signs types using robust error correcting codings. Moreover, we introduce the novel β-correction decoding strategy that outperforms the state-of-the-art decoding techniques, classifying a high number of classes with great success.     

Error-resilient pattern classification using a combination of spreading and coding gains

An approach that aims to enhance error resilience in pattern classification problems is proposed. The new approach combines the spread spectrum technique, specifically its selectivity and sensitivity, with error-correcting output codes (ECOC) for pattern classification. This approach combines both the coding gain of ECOC and the spreading gain of the spread spectrum technique to improve error resilience. ECOC is a well-established technique for general purpose pattern classification, which reduces the multi-class learning problem to an ensemble of two-class problems and uses special codewords to improve the error resilience of pattern classification. The direct sequence code division multiple access (DS-CDMA) technique is a spread spectrum technique that provides high user selectivity and high signal detection sensitivity, resulting in a reliable connection through a noisy radio communication channel shared by multiple users. Using DS-CDMA to spread the codeword, assigned to each pattern class by the ECOC technique, gives codes with coding properties that enable better correction of classification errors than ECOC alone. Results of performance assessment experiments show that the use of DS-CDMA alongside ECOC boosts error-resilience significantly, by yielding better classification accuracy than ECOC by itself.     

Thinned-ECOC ensemble based on sequential code shrinking

Error-correcting output coding (ECOC) is a strategy to create classifier ensembles which reduces a multi-class problem into some binary sub-problems. A key issue in designing any ECOC classifier refers to defining optimal codematrix having maximum discrimination power and minimum number of columns. This paper proposes a heuristic method for application-dependent design of optimal ECOC matrix based on a thinning algorithm. The main idea of the proposed Thinned-ECOC method is to successively remove some redundant and unnecessary columns of any initial codematrix based on a metric defined for each column. As a result, computational cost of the ensemble is reduced while preserving its accuracy. Proposed method has been validated using the UCI machine learning database and further applied to a couple of real-world pattern recognition problems (the face recognition and gene expression based cancer classification). Experimental results emphasize the robustness of Thinned-ECOC in comparison with existing state-of-the-art code generation methods.     

On the Decoding Process in Ternary Error-Correcting Output Codes

A common way to model multiclass classification problems is to design a set of binary classifiers and to combine them. Error-Correcting Output Codes (ECOC) represent a successful framework to deal with these type of problems. Recent works in the ECOC framework showed significant performance improvements by means of new problem-dependent designs based on the ternary ECOC framework. The ternary framework contains a larger set of binary problems because of the use of a “do not care” symbol that allows us to ignore some classes by a given classifier. However, there are no proper studies that analyze the effect of the new symbol at the decoding step. In this paper, we present a taxonomy that embeds all binary and ternary ECOC decoding strategies into four groups. We show that the zero symbol introduces two kinds of biases that require redefinition of the decoding design. A new type of decoding measure is proposed, and two novel decoding strategies are defined. We evaluate the state-of-the-art coding and decoding strategies over a set of UCI Machine Learning Repository data sets and into a real traffic sign categorization problem. The experimental results show that, following the new decoding strategies, the performance of the ECOC design is significantly improved.     

Decoding design based on posterior probabilities in Ternary Error-Correcting Output Codes

Ternary Error-Correcting Output Codes (ECOC), which can unify most of the state-of-the-art decomposition frameworks such as one-versus-one, one-versus-all, sparse coding, dense coding, etc., is considered more flexible to model multiclass classification problems than Binary ECOC. Meanwhile, there are many corresponding decoding strategies that have been proposed for Ternary ECOC in earlier literatures. Note that there is few working by posterior probabilities, which can be considered as a Bayes decision rule and hence obtain a better performance in usual. Passerini et al. (2004) [16] have recently proposed a decoding strategy based on posterior probabilities. However, according to the analyses of this paper, Passerini et al.'s (2004) [16] method suffers some defects and result in bias. To overcome that, we proposed a variation of it by refining the decomposition process of probability to get smoother estimates. Our bias–variance analysis shows that the decrease in error by our variant is due to a decrease in variance. Besides, we extended an efficient method of obtaining posterior probabilities based on the linear rule for decoding process in Binary ECOC to Ternary ECOC. On ten benchmark datasets, we observe that the two decoding strategies based on posterior probabilities in this paper obtain better performance than other ones in earlier references.     

Effectiveness of error correcting output coding methods in ensemble and monolithic learning machines

Abstract Error Correcting Output Coding (ECOC) methods for multiclass classification present several open problems ranging from the trade-off between their error recovering capabilities and the learnability of the induced dichotomies to the selection of proper base learners and to the design of well-separated codes for a given multiclass problem. We experimentally analyse some of the main factors affecting the effectiveness of ECOC methods. We show that the architecture of ECOC learning machines influences the accuracy of the ECOC classifier, highlighting that ensembles of parallel and independent dichotomic Multi-Layer Perceptrons are well-suited to implement ECOC methods. We quantitatively evaluate the dependence among codeword bit errors using mutual information based measures, experimentally showing that a low dependence enhances the generalisation capabilities of ECOC. Moreover we show that the proper selection of the base learner and the decoding function of the reconstruction stage significantly affects the performance of the ECOC ensemble. The analysis of the relationships between the error recovering power, the accuracy of the base learners, and the dependence among codeword bits show that all these factors concur to the effectiveness of ECOC methods in a not straightforward way, very likely dependent on the distribution and complexity of the data.An erratum to this article can be found at     

Research on the unbiased probability estimation of error-correcting output coding

Supervised classification based on error-correcting output codes (ECOC) is an efficient method to solve the problem of multi-class classification, and how to get the accurate probability estimation via ECOC is also an attractive research direction. This paper proposed three kinds of ECOC to get unbiased probability estimates, and investigated the corresponding classification performance in depth at the same time. Two evaluating criterions for ECOC that has better classification performance were concluded, which are Bayes consistence and unbiasedness of probability estimation. Experimental results on artificial data sets and UCI data sets validate the correctness of our conclusion.     

New results on error correcting output codes of kernel machines

We study the problem of multiclass classification within the framework of error correcting output codes (ECOC) using margin-based binary classifiers. Specifically, we address two important open problems in this context: decoding and model selection. The decoding problem concerns how to map the outputs of the classifiers into class codewords. In this paper we introduce a new decoding function that combines the margins through an estimate of their class conditional probabilities. Concerning model selection, we present new theoretical results bounding the leave-one-out (LOO) error of ECOC of kernel machines, which can be used to tune kernel hyperparameters. We report experiments using support vector machines as the base binary classifiers, showing the advantage of the proposed decoding function over other functions of I he margin commonly used in practice. Moreover, our empirical evaluations on model selection indicate that the bound leads to good estimates of kernel parameters.     

基于纠错输出编码的多类概率建模

目前模式识别领域中缺乏有效的多类概率建模方法,对此提出利用纠错输出编码作为多类概率建模框架,将二元纠错输出编码研究的概率输出问题转化为线性超定方程的求解问题,通过线性最小二乘法来求解并获取多类后验概率的结果;而对于三元纠错输出编码的等价非线性超定方程组,提出一种迭代法则来求解多类概率输出.实验中通过与3种经典方法相比较可以发现,新方法求取的概率输出具有更好的分布形态,并且该方法具有较好的分类性能.     

Efficient implementation of class-based decomposition schemes for Naïve Bayes

Previous studies have shown that the classification accuracy of a Naïve Bayes classifier in the domain of text-classification can often be improved using binary decompositions such as error-correcting output codes (ECOC). The key contribution of this short note is the realization that ECOC and, in fact, all class-based decomposition schemes, can be efficiently implemented in a Naïve Bayes classifier, so that—because of the additive nature of the classifier—all binary classifiers can be trained in a single pass through the data. In contrast to the straight-forward implementation, which has a complexity of O(n?t?g), the proposed approach improves the complexity to O((n+t)?g). Large-scale learning of ensemble approaches with Naïve Bayes can benefit from this approach, as the experimental results shown in this paper demonstrate.     

Stochastic organization of output codes in multiclass learning problems

The best-known decomposition schemes of multiclass learning problems are one per class coding (OPC) and error-correcting output coding (ECOC). Both methods perform a prior decomposition, that is, before training of the classifier takes place. The impact of output codes on the inferred decision rules can be experienced only after learning. Therefore, we present a novel algorithm for the code design of multiclass learning problems. This algorithm applies a maximum-likelihood objective function in conjunction with the expectation-maximization (EM) algorithm. Minimizing the augmented objective function yields the optimal decomposition of the multiclass learning problem in two-class problems. Experimental results show the potential gain of the optimized output codes over OPC or ECOC methods.     

Discriminant error correcting output codes based on spectral clustering

Error correcting output codes (ECOCs) is a powerful framework to solve the multi-class problems. Finding the optimal partitions with maximum class discrimination efficiently is a key point to improve its performance. In this paper, we propose an alternative and efficient approach to obtain the partitions which are discriminative in the class space. The main idea of the proposed method is to transform the partition in the class space into the cut for an undirected graph using spectral clustering. In addition to measuring the class similarity, the confusion matrix with a pre-classifier is used. Our method is compared with the classical ECOC and DECOC over a synthetic dataset, a set of UCI machine learning repository datasets and one face recognition application. The results show that our proposal is able to obtain comparable or even better classification accuracy while reducing the computational complexity in comparison with the state-of-the-art coding methods.