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.     

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.     

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.     

基于纠错编码的CSNN及其在遥感图像分类中的应用

单输出组合神经网络(CSNN)克服了BP神经网络固有的缺陷，具有网络结构确定、分类行为易于解释、并行性好等优点，但分类精度比经过结构选择的BPNN略差．采用纠错编码可以提高CSNN的分类精度，首先根据类别数与纠错能力确定类别码组，每个码字对应一种类别，每个SNN子网对这些码字中的同一位进行训练，从而确定网络结构与每个子网所学习的二值函数；对未知类别的样本进行分类时，各SNN的结果组成一个输出码，计算该输出码与各类别码的汉明距离，选择与其距离最近的类别码所对应的类别为该样本的类别；基于纠错编码的CSNN的分类行为易于转化为规则集形式，可理解性强．将该网络结构用于遥感图像分类，并与其他分类算法进行比较，结果表明采用纠错编码技术，CSNN不仅具备原有的各项优点，而且分类精度得到显著提高．     

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.     

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.     

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.     

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.     

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.     

一种自适应的多类Boosting分类算法

许多实际问题涉及到多分类技术,该技术能有效地缩小用户与计算机之间的理解差异。在传统的多类Boosting方法中,多类损耗函数未必具有猜测背离性,并且多类弱学习器的结合被限制为线性的加权和。为了获得高精度的最终分类器,多类损耗函数应具有多类边缘极大化、贝叶斯一致性与猜测背离性。此外,弱学习器的缺点可能会限制线性分类器的性能,但它们的非线性结合可以提供较强的判别力。根据这两个观点,设计了一个自适应的多类Boosting分类器,即SOHPBoost算法。在每次迭代中,SOHPBoost算法能够利用向量加法或Hadamard乘积来集成最优的多类弱学习器。这个自适应的过程可以产生多类弱学习的Hadamard乘积向量和,进而挖掘出数据集的隐藏结构。实验结果表明,SOHPBoost算法可以产生较好的多分类性能。     

Evolving Output Codes for Multiclass Problems

In this paper, we propose an evolutionary approach to the design of output codes for multiclass pattern recognition problems. This approach has the advantage of taking into account the different aspects that are relevant for a code matrix to achieve a good performance. We define a fitness function made up of five terms that refer to overall classifier accuracy, binary classifiers' accuracy, classifiers' diversity, minimum Hamming distance among codewords, and margin of classification. These five factors have not been considered together in previous works. We perform a study of these five terms to obtain a fitness function with three of them. We test our approach on 27 datasets from the UCI Machine Learning Repository, using three different base learners: C4.5, neural networks, and support vector machines. We show a better performance than most of the current standard methods, namely, randomly generated codes with approximately equal random split, codes designed using a CHC algorithm, and one-vs-all and one-vs-one methods.     

Fast Multiclass SVM Classification Using Decision Tree Based One-Against-All Method

We present an improved version of One-Against-All (OAA) method for multiclass SVM classification based on a decision tree approach. The proposed decision tree based OAA (DT-OAA) is aimed at increasing the classification speed of OAA by using posterior probability estimates of binary SVM outputs. DT-OAA decreases the average number of binary SVM tests required in testing phase to a greater extent when compared to OAA and other multiclass SVM methods. For a balanced multiclass dataset with K classes, under best situation, DT-OAA requires only (K + 1)/2 binary tests on an average as opposed to K binary tests in OAA; however, on imbalanced multiclass datasets we observed DT-OAA to be much faster with proper selection of order in which the binary SVMs are arranged in the decision tree. Computational comparisons on publicly available datasets indicate that the proposed method can achieve almost the same classification accuracy as that of OAA, but is much faster in decision making.     

Accurate ensemble pruning with PL-bagging

Ensemble pruning deals with the selection of base learners prior to combination in order to improve prediction accuracy and efficiency. In the ensemble literature, it has been pointed out that in order for an ensemble classifier to achieve higher prediction accuracy, it is critical for the ensemble classifier to consist of accurate classifiers which at the same time diverse as much as possible. In this paper, a novel ensemble pruning method, called PL-bagging, is proposed. In order to attain the balance between diversity and accuracy of base learners, PL-bagging employs positive Lasso to assign weights to base learners in the combination step. Simulation studies and theoretical investigation showed that PL-bagging filters out redundant base learners while it assigns higher weights to more accurate base learners. Such improved weighting scheme of PL-bagging further results in higher classification accuracy and the improvement becomes even more significant as the ensemble size increases. The performance of PL-bagging was compared with state-of-the-art ensemble pruning methods for aggregation of bootstrapped base learners using 22 real and 4 synthetic datasets. The results indicate that PL-bagging significantly outperforms state-of-the-art ensemble pruning methods such as Boosting-based pruning and Trimmed bagging.     

基于进化集成学习的用户购买意向预测

在电子商务时代背景下,精准预测用户的购买意向已经成为提高销售效率和优化客户体验的关键因素。针对传统集成策略在模型设计阶段往往受人为因素限制的问题,构建了一种自适应进化集成学习模型用于预测用户的购买意向。该模型能够自适应地选择最优基学习器和元学习器,并融合基学习器的预测信息和特征间的差异性扩展特征维度,从而提高预测的准确性。此外,为进一步优化模型的预测效果,设计了一种二元自适应差分进化算法进行特征选择,旨在筛选出对预测结果有显著影响的特征。研究结果表明,与传统优化算法相比,二元自适应差分进化算法在全局搜索和特征选择方面表现优异。相较于六种常见的集成模型和DeepForest模型,所构建的进化集成模型在AUC值上分别提高了2.76%和2.72%,并且能够缓解数据不平衡所带来的影响。     

Reduced one-against-all method for multiclass SVM classification

We present an improved version of one-against-all method for multiclass SVM classification based on subset sample selection, named reduced one-against-all, to achieve high performance in large multiclass problems. Reduced one-against-all drastically decreases the computing effort involved in training one-against-all classifiers, without any compromise in classification accuracy. Computational comparisons on publicly available datasets indicate that the proposed method has comparable accuracy to that of conventional one-against-all method, but with an order of magnitude faster. On the largest dataset considered, reduced one-against-all method achieved 50% reduction in computing time over one-against-all method for almost the same classification accuracy. We further investigated reduced one-against-all with linear kernel for multi-label text categorization applications. Computational results demonstrate the effectiveness of the proposed method on both the text corpuses considered.     

Binary tree of SVM: a new fast multiclass training and classification algorithm

We present a new architecture named Binary Tree of support vector machine (SVM), or BTS, in order to achieve high classification efficiency for multiclass problems. BTS and its enhanced version, c-BTS, decrease the number of binary classifiers to the greatest extent without increasing the complexity of the original problem. In the training phase, BTS has N-1 binary classifiers in the best situation (N is the number of classes), while it has log/sub 4/3/((N+3)/4) binary tests on average when making a decision. At the same time the upper bound of convergence complexity is determined. The experiments in this paper indicate that maintaining comparable accuracy, BTS is much faster to be trained than other methods. Especially in classification, due to its Log complexity, it is much faster than directed acyclic graph SVM (DAGSVM) and ECOC in problems that have big class number.     

Direct estimation of class membership probabilities for multiclass classification using multiple scores

Accurate estimation of class membership probability is needed for many applications in data mining and decision-making, to which multiclass classification is often applied. Since existing methods for estimation of class membership probability are designed for binary classification, in which only a single score outputted from a classifier can be used, an approach for multiclass classification requires both a decomposition of a multiclass classifier into binary classifiers and a combination of estimates obtained from each binary classifier to a target estimate. We propose a simple and general method for directly estimating class membership probability for any class in multiclass classification without decomposition and combination, using multiple scores not only for a predicted class but also for other proper classes. To make it possible to use multiple scores, we propose to modify or extend representative existing methods. As a non-parametric method, which refers to the idea of a binning method as proposed by Zadrozny et al., we create an “accuracy table” by a different method. Moreover we smooth accuracies on the table with methods such as the moving average to yield reliable probabilities (accuracies). As a parametric method, we extend Platt’s method to apply a multiple logistic regression. On two different datasets (open-ended data from Japanese social surveys and the 20 Newsgroups) both with Support Vector Machines and naive Bayes classifiers, we empirically show that the use of multiple scores is effective in the estimation of class membership probabilities in multiclass classification in terms of cross entropy, the reliability diagram, the ROC curve and AUC (area under the ROC curve), and that the proposed smoothing method for the accuracy table works quite well. Finally, we show empirically that in terms of MSE (mean squared error), our best proposed method is superior to an expansion for multiclass classification of a PAV method proposed by Zadrozny et al., in both the 20 Newsgroups dataset and the Pendigits dataset, but is slightly worse than the state-of-the-art method, which is an expansion for multiclass classification of a combination of boosting and a PAV method, on the Pendigits dataset.

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.     

Empirical analysis of support vector machine ensemble classifiers

Ensemble classification – combining the results of a set of base learners – has received much attention in the machine learning community and has demonstrated promising capabilities in improving classification accuracy. Compared with neural network or decision tree ensembles, there is no comprehensive empirical research in support vector machine (SVM) ensembles. To fill this void, this paper analyses and compares SVM ensembles with four different ensemble constructing techniques, namely bagging, AdaBoost, Arc-X4 and a modified AdaBoost. Twenty real-world data sets from the UCI repository are used as benchmarks to evaluate and compare the performance of these SVM ensemble classifiers by their classification accuracy. Different kernel functions and different numbers of base SVM learners are tested in the ensembles. The experimental results show that although SVM ensembles are not always better than a single SVM, the SVM bagged ensemble performs as well or better than other methods with a relatively higher generality, particularly SVMs with a polynomial kernel function. Finally, an industrial case study of gear defect detection is conducted to validate the empirical analysis results.     

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

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