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

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

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.     

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.     

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

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

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.     

An incremental node embedding technique for error correcting output codes

The error correcting output codes (ECOC) technique is a useful way to extend any binary classifier to the multiclass case. The design of an ECOC matrix usually considers an a priori fixed number of dichotomizers. We argue that the selection and number of dichotomizers must depend on the performance of the ensemble code in relation to the problem domain. In this paper, we present a novel approach that improves the performance of any initial output coding by extending it in a sub-optimal way. The proposed strategy creates the new dichotomizers by minimizing the confusion matrix among classes guided by a validation subset. A weighted methodology is proposed to take into account the different relevance of each dichotomizer. As a result, overfitting is avoided and small codes with good generalization performance are obtained. In the decoding step, we introduce a new strategy that follows the principle that positions coded with the symbol zero should have small influence in the results. We compare our strategy to other well-known ECOC strategies on the UCI database, and the results show it represents a significant improvement.     

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

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

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

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

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.     

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     

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

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

     

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.     

基于纠错输出编码的人脸表情识别

多分类问题一直是模式识别领域的一个热点,提出了一种基于纠错输出编码和支持向量机的多分类器算法。根据通信编码理论设计纠错输出编码矩阵;按照该编码矩阵设计若干个互不相关的子支持向量机,根据编码原理将它们融合为一个多分类器。为了验证本分类器的有效性,采用Gabor小波提取人脸表情特征,应用二元主成分（2DPCA）分析法对提取的特征进行降维处理,应用该分类器进行了人脸表情的识别。实验结果表明,提出的方法能有效提高人脸表情的识别率,并具有极好的鲁棒性。     

基于直接序列扩频码的图像空间域水印技术

提出了一种基于直接序列扩频码的图像空间域水印方案.在建立数字图像水印的通信模型的基础上,通过生成原图的视觉掩模以充分保证图像的逼真度,在数字图像相应的空间域嵌入扩频码调制水印,同时利用纠错编码技术来进一步增强水印的抗干扰性能.水印的检测通过计算像差图像和原扩频码的相关性来实现.实验表明,该方案提高了数字水印的稳健性和隐蔽性,具有较好的主观效果.     

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.     

基于KNN模型的层次纠错输出编码算法

纠错输出编码是一种解决多类分类问题的有效方法,但其编码矩阵只对类进行编码且都采用事先构造出来的统一形式,适应性较差。为此,提出一种新颖的层次纠错输出编码算法。该算法在训练阶段先通过KNN模型算法在数据集上构建多个同类簇,选取各类中最具代表性的簇形成层次编码矩阵,然后再根据编码矩阵进行单分类器训练。在测试阶段,该算法通过模型融合进一步发挥KNN模型和纠错输出编码各自的优点。在UCI公共数据集上的实验结果表明,新方法的性能优于KNN模型算法和纠错输出编码算法。     

Combining eigenvector methods and support vector machines for detecting variability of Doppler ultrasound signals

In this paper, the multiclass support vector machines (SVMs) with the error correcting output codes (ECOC) were presented for detecting variabilities of the multiclass Doppler ultrasound signals. The ophthalmic arterial (OA) Doppler signals were recorded from healthy subjects, subjects suffering from OA stenosis, subjects suffering from ocular Behcet disease. The internal carotid arterial (ICA) Doppler signals were recorded from healthy subjects, subjects suffering from ICA stenosis, subjects suffering from ICA occlusion. Methods of combining multiple classifiers with diverse features are viewed as a general problem in various application areas of pattern recognition. Because of the importance of making the right decision, better classification procedures for Doppler ultrasound signals are searched. Decision making was performed in two stages: feature extraction by eigenvector methods and classification using the SVMs trained on the extracted features. The research demonstrated that the multiclass SVMs trained on extracted features achieved high accuracy rates.     

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.     

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.     

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.