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

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

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.     

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.     

Subclass problem-dependent design for error-correcting output codes

A common way to model multi-class classification problems is by means of Error-Correcting Output Codes (ECOC). Given a multi-class problem, the ECOC technique designs a code word for each class, where each position of the code identifies the membership of the class for a given binary problem. A classification decision is obtained by assigning the label of the class with the closest code. One of the main requirements of the ECOC design is that the base classifier is capable of splitting each sub-group of classes from each binary problem. However, we can not guarantee that a linear classifier model convex regions. Furthermore, non-linear classifiers also fail to manage some type of surfaces. In this paper, we present a novel strategy to model multi-class classification problems using sub-class information in the ECOC framework. Complex problems are solved by splitting the original set of classes into sub-classes, and embedding the binary problems in a problem-dependent ECOC design. Experimental results show that the proposed splitting procedure yields a better performance when the class overlap or the distribution of the training objects conceil the decision boundaries for the base classifier. The results are even more significant when one has a sufficiently large training size.     

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.     

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     

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.     

Face verification via error correcting output codes

We propose a novel approach to face verification based on the Error Correcting Output Coding (ECOC) classifier design concept. In the training phase, the client set is repeatedly divided into two ECOC specified sub-sets (super-classes) to train a set of binary classifiers. The output of the classifiers defines the ECOC feature space, in which it is easier to separate transformed patterns representing clients and impostors. As a matching score in this space, we propose the average first order Minkowski distance between the probe and gallery images. The proposed method exhibits superior verification performance on the well known XM2VTS data set as compared with previously reported results.     

基于最小二乘和纠错输出编码的多类分类

多类分类是目标识别中必须面对的一个关键问题,现有分类器大都为二分器,无法满足对多类目标进行分类,为此,提出利用纠错输出编码方法对多类问题进行分解,即把多类问题转化成二类问题;同时讨论一种基于最小二乘法对二分器结果进行融合的策略。实验分别对UCI数据集和三种一维距离像数据集进行测试,结果表明与经典的多分类器相比,提出的多类分类策略有较高的分类正确率。     

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

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

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.     

Data-driven decomposition for multi-class classification

This paper presents a new study on a method of designing a multi-class classifier: Data-driven Error Correcting Output Coding (DECOC). DECOC is based on the principle of Error Correcting Output Coding (ECOC), which uses a code matrix to decompose a multi-class problem into multiple binary problems. ECOC for multi-class classification hinges on the design of the code matrix. We propose to explore the distribution of data classes and optimize both the composition and the number of base learners to design an effective and compact code matrix. Two real world applications are studied: (1) the holistic recognition (i.e., recognition without segmentation) of touching handwritten numeral pairs and (2) the classification of cancer tissue types based on microarray gene expression data. The results show that the proposed DECOC is able to deliver competitive accuracy compared with other ECOC methods, using parsimonious base learners than the pairwise coupling (one-vs-one) decomposition scheme. With a rejection scheme defined by a simple robustness measure, high reliabilities of around 98% are achieved in both applications.     

Intelligent GPGPU Classification in Volume Visualization: A framework based on Error‐Correcting Output Codes

In volume visualization, the definition of the regions of interest is inherently an iterative trial‐and‐error process finding out the best parameters to classify and render the final image. Generally, the user requires a lot of expertise to analyze and edit these parameters through multi‐dimensional transfer functions. In this paper, we present a framework of intelligent methods to label on‐demand multiple regions of interest. These methods can be split into a two‐level GPU‐based labelling algorithm that computes in time of rendering a set of labelled structures using the Machine Learning Error‐Correcting Output Codes (ECOC) framework. In a pre‐processing step, ECOC trains a set of Adaboost binary classifiers from a reduced pre‐labelled data set. Then, at the testing stage, each classifier is independently applied on the features of a set of unlabelled samples and combined to perform multi‐class labelling. We also propose an alternative representation of these classifiers that allows to highly parallelize the testing stage. To exploit that parallelism we implemented the testing stage in GPU‐OpenCL. The empirical results on different data sets for several volume structures shows high computational performance and classification accuracy.     

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.     

Local context-based recognition of sketched diagrams

We present a new methodology aimed at the design and implementation of a framework for sketch recognition enabling the recognition and interpretation of diagrams. The diagrams may contain different types of sketched graphic elements such as symbols, connectors, and text. Once symbols are distinguished from connectors and identified, the recognition proceeds by identifying the local context of each symbol. This is seen as the symbol interface exposed to the rest of the diagram and includes predefined attachment areas on each symbol. The definition of simple constraints on the local context of each symbol allows to greatly simplify the definition of the visual grammar, which is used only for further refinement and interpretation of the set of acceptable diagrams. We demonstrate the potential of the methodology using flowcharts and binary trees as examples.     

Efficient prediction algorithms for binary decomposition techniques

Binary decomposition methods transform multiclass learning problems into a series of two-class learning problems that can be solved with simpler learning algorithms. As the number of such binary learning problems often grows super-linearly with the number of classes, we need efficient methods for computing the predictions. In this article, we discuss an efficient algorithm that queries only a dynamically determined subset of the trained classifiers, but still predicts the same classes that would have been predicted if all classifiers had been queried. The algorithm is first derived for the simple case of pairwise classification, and then generalized to arbitrary pairwise decompositions of the learning problem in the form of ternary error-correcting output codes under a variety of different code designs and decoding strategies.     

Customizing short-length LT codes with evolution strategies for video streaming protection

Designing short-length Luby Transform (SLLT) codes to best protect video streaming and multicasting over lossy communication remains largely an empirical exercise. In this paper, we present a systematic approach to customize the decoding performance of these codes so that the protected video bitstreams may have the best playback quality over a wide range of channel loss rates. Our approach begins with the proposal of a new SLLT decoding performance model based on three parameters: decoding overhead, symbol decoding failure rate and tail probability of symbol decoding failure rate. We then formulate the design of SLLT codes as a multi-objective optimization problem, specify the design objectives in terms of goal program, and search for the most suitable codes using an augmented weighted Tchebycheff method implemented with the Covariance Matrix Adaptation Evolution Strategy (CMA-ES). Two design examples are provided to illustrate the effectiveness of our approach: (1) an SLLT post-code of a short-length raptor code that provides erasure protection to H.264 AVC bitstreams, and (2) an SLLT post-code of a rateless UEP code that supports graceful degradation of H.264 SVC playback quality. Empirical results demonstrate that the proposed method is capable of producing SLLT codes with customized decoding performance, whereas, the customized codes enable the playback pictures to attain significantly higher PSNR values at different stages of the decoding process than the pictures recovered under the protection of conventionally optimized codes.     

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