A comparison of methods for multiclass support vector machines

Support vector machines (SVMs) were originally designed for binary classification. How to effectively extend it for multiclass classification is still an ongoing research issue. Several methods have been proposed where typically we construct a multiclass classifier by combining several binary classifiers. Some authors also proposed methods that consider all classes at once. As it is computationally more expensive to solve multiclass problems, comparisons of these methods using large-scale problems have not been seriously conducted. Especially for methods solving multiclass SVM in one step, a much larger optimization problem is required so up to now experiments are limited to small data sets. In this paper we give decomposition implementations for two such "all-together" methods. We then compare their performance with three methods based on binary classifications: "one-against-all," "one-against-one," and directed acyclic graph SVM (DAGSVM). Our experiments indicate that the "one-against-one" and DAG methods are more suitable for practical use than the other methods. Results also show that for large problems methods by considering all data at once in general need fewer support vectors.     

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.     

Multiclass LS-SVMs: Moderated Outputs and Coding-Decoding Schemes

A common way of solving the multiclass categorization problem is to reformulate the problem into a set of binary classification problems. Discriminative binary classifiers like, e.g., Support Vector Machines (SVMs), directly optimize the decision boundary with respect to a certain cost function. In a pragmatic and computationally simple approach, Least Squares SVMs (LS-SVMs) are inferred by minimizing a related regression least squares cost function. The moderated outputs of the binary classifiers are obtained in a second step within the evidence framework. In this paper, Bayes' rule is repeatedly applied to infer the posterior multiclass probabilities, using the moderated outputs of the binary plug-in classifiers and the prior multiclass probabilities. This Bayesian decoding motivates the use of loss function based decoding instead of Hamming decoding. For SVMs and LS-SVMs with linear kernel, experimental evidence suggests the use of one-versus-one coding. With a Radial Basis Function kernel one-versus-one and error correcting output codes yield the best performances, but simpler codings may still yield satisfactory results. This revised version was published online in August 2006 with corrections to the Cover Date.     

One-Class-at-a-Time Removal Sequence Planning Method for Multiclass Classification Problems

Using dynamic programming, this work develops a one-class-at-a-time removal sequence planning method to decompose a multiclass classification problem into a series of two-class problems. Compared with previous decomposition methods, the approach has the following distinct features. First, under the one-class-at-a-time framework, the approach guarantees the optimality of the decomposition. Second, for a K-class problem, the number of binary classifiers required by the method is only K-1. Third, to achieve higher classification accuracy, the approach can easily be adapted to form a committee machine. A drawback of the approach is that its computational burden increases rapidly with the number of classes. To resolve this difficulty, a partial decomposition technique is introduced that reduces the computational cost by generating a suboptimal solution. Experimental results demonstrate that the proposed approach consistently outperforms two conventional decomposition methods     

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.     

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

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

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.     

A Novel and Principled Multiclass Support Vector Machine

Support vector machines (SVMs) have been demonstrated very efficient for binary classification problems; however, computationally efficient and effective multiclass SVMs are still missing. Most existing multiclass SVM classifiers are constructed either by combining multiple binary SVM classifiers, which often perform moderately for some problems, or by converting multiclass problems into one single optimization problem, which is unfortunately computationally expensive. To address these issues, a novel and principled multiclass SVM based on geometric properties of hyperspheres, termed SVMGH, is proposed in this paper. Different from existing SVM‐based methods that seek a cutting hyperplane between two classes, SVMGH draws the discriminative information of each class by constructing a minimum hypersphere containing all class members, and then defines a label function based on the geometric properties of the minimum hyperspheres. We prove theoretically the geometric properties of the minimum hyperspheres to guarantee the validation of SVMGH. The computational efficiency is enhanced by a data reduction strategy as well as a fast training method. Experimental results demonstrate that the proposed SVMGH shows better performance and higher computational efficiency than the state of the art on multiclassification problems while maintaining comparable performance and efficiency on binary classification problems.     

多类支持向量机方法的研究现状与分析

支持向量机（SVM）是建立在统计学理论基础上的一种小样本机器学习方法，最初应用于解决两类分类问题．然而在解决实际问题中遇到的多为多分类问题，如何有效的将其推广到多类分类问题是一个正在研究的问题．该文对现有的多类支持向量机方法从组合多个两类分类器、层次结构、一次性优化问题和纠错编码等4个角度进行了综合归纳和分析，详细介绍了每种方法的代表性算法，并比较其优劣．     

Optimisation of multiclass supervised classification based on using output codes with error-correcting

An approach of solving the problem of multiclass supervised classification, based on using errorcorrecting codes is considered. The main problem here is the creation of binary code matrix, which provides high classification accuracy. Binary classifiers must be distinct and accurate. In this issue, there are many questions. What should be the elements of the matrix, how many elements provide the best accuracy and how to find them? In this paper an approach to solve some optimization problems for the construction of the binary code matrix is considered. The problem of finding the best binary classifiers (columns of matrix) is formulated as a discrete optimization problem. For some partial precedent classification approach, there is a calculation of the effective values of optimising function. Prospects of this approach are confirmed by a series of experiments on various practical tasks.     

A review on the combination of binary classifiers in multiclass problems

Several real problems involve the classification of data into categories or classes. Given a data set containing data whose classes are known, Machine Learning algorithms can be employed for the induction of a classifier able to predict the class of new data from the same domain, performing the desired discrimination. Some learning techniques are originally conceived for the solution of problems with only two classes, also named binary classification problems. However, many problems require the discrimination of examples into more than two categories or classes. This paper presents a survey on the main strategies for the generalization of binary classifiers to problems with more than two classes, known as multiclass classification problems. The focus is on strategies that decompose the original multiclass problem into multiple binary subtasks, whose outputs are combined to obtain the final prediction.     

Differential prioritization in feature selection and classifier aggregation for multiclass microarray datasets

The high dimensionality of microarray datasets endows the task of multiclass tissue classification with various difficulties—the main challenge being the selection of features deemed relevant and non-redundant to form the predictor set for classifier training. The necessity of varying the emphases on relevance and redundancy, through the use of the degree of differential prioritization (DDP) during the search for the predictor set is also of no small importance. Furthermore, there are several types of decomposition technique for the feature selection (FS) problem—all-classes-at-once, one-vs.-all (OVA) or pairwise (PW). Also, in multiclass problems, there is the need to consider the type of classifier aggregation used—whether non-aggregated (a single machine), or aggregated (OVA or PW). From here, first we propose a systematic approach to combining the distinct problems of FS and classification. Then, using eight well-known multiclass microarray datasets, we empirically demonstrate the effectiveness of the DDP in various combinations of FS decomposition types and classifier aggregation methods. Aided by the variable DDP, feature selection leads to classification performance which is better than that of rank-based or equal-priorities scoring methods and accuracies higher than previously reported for benchmark datasets with large number of classes. Finally, based on several criteria, we make general recommendations on the optimal choice of the combination of FS decomposition type and classifier aggregation method for multiclass microarray datasets.     

Incorporating label dependency into the binary relevance framework for multi-label classification

In multi-label classification, examples can be associated with multiple labels simultaneously. The task of learning from multi-label data can be addressed by methods that transform the multi-label classification problem into several single-label classification problems. The binary relevance approach is one of these methods, where the multi-label learning task is decomposed into several independent binary classification problems, one for each label in the set of labels, and the final labels for each example are determined by aggregating the predictions from all binary classifiers. However, this approach fails to consider any dependency among the labels. Aiming to accurately predict label combinations, in this paper we propose a simple approach that enables the binary classifiers to discover existing label dependency by themselves. An experimental study using decision trees, a kernel method as well as Naïve Bayes as base-learning techniques shows the potential of the proposed approach to improve the multi-label classification performance.     

Improved multiclass feature selection via list combination

Feature selection is a crucial machine learning technique aimed at reducing the dimensionality of the input space. By discarding useless or redundant variables, not only it improves model performance but also facilitates its interpretability. The well-known Support Vector Machines–Recursive Feature Elimination (SVM-RFE) algorithm provides good performance with moderate computational efforts, in particular for wide datasets. When using SVM-RFE on a multiclass classification problem, the usual strategy is to decompose it into a series of binary ones, and to generate an importance statistics for each feature on each binary problem. These importances are then averaged over the set of binary problems to synthesize a single value for feature ranking. In some cases, however, this procedure can lead to poor selection. In this paper we discuss six new strategies, based on list combination, designed to yield improved selections starting from the importances given by the binary problems. We evaluate them on artificial and real-world datasets, using both One–Vs–One (OVO) and One–Vs–All (OVA) strategies. Our results suggest that the OVO decomposition is most effective for feature selection on multiclass problems. We also find that in most situations the new K-First strategy can find better subsets of features than the traditional weight average approach.     

基于分解策略处理多分类不均衡问题的方法

针对多分类不均衡问题,提出了一种新的基于一对一（one-versus-one,OVO）分解策略的方法。首先基于OVO分解策略将多分类不均衡问题分解成多个二值分类问题;再利用处理不均衡二值分类问题的算法建立二值分类器;接着利用SMOTE过抽样技术处理原始数据集;然后采用基于距离相对竞争力加权方法处理冗余分类器;最后通过加权投票法获得输出结果。在KEEL不均衡数据集上的大量实验结果表明,所提算法比其他经典方法具有显著的优势。     

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.

A multiresolution spectral angle‐based hyperspectral classification method

Due to the lack of training samples, hyperspectral classification often adopts the minimum distance classification method based on spectral metrics. This paper proposes a novel multiresolution spectral‐angle‐based hyperspectral classification method, where band subsets will be selected to simultaneously minimize the average within‐class spectral angle and maximize the average between‐class spectral angle. The method adopts a pairwise classification framework (PCF), which decomposes the multiclass problem into two‐class problems. Based on class separability criteria, the original set of bands is recursively decomposed into band subsets for each two‐class problem. Each subset is composed of adjacent bands. Then, the subsets with high separability are selected to generate subangles, which will be combined to measure the similarity. Following the PCF, the outputs of all the two‐class classifiers are combined to obtain the final output. Tested with an Airborne Visible/Infrared Imaging Spectrometer (AVIRIS) data set for a six‐class problem, the results demonstrate that our method outperforms the previous spectral metric‐based classification methods.     

An all-pair quantum SVM approach for big data multiclass classification

In this paper, we discuss a quantum approach for the all-pair multiclass classification problem. In an all-pair approach, there is one binary classification problem for each pair of classes, and so there are k(k???1)/2 classifiers for a k-class classification problem. As compared to the classical multiclass support vector machine that can be implemented with polynomial run time complexity, our approach exhibits exponential speedup due to quantum computing. The quantum all-pair algorithm can also be used with other classification algorithms, and a speedup gain can be achieved as compared to their classical counterparts.     

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.     

An ensemble approach of dual base learners for multi-class classification problems

In this work, we formalise and evaluate an ensemble of classifiers that is designed for the resolution of multi-class problems. To achieve a good accuracy rate, the base learners are built with pairwise coupled binary and multi-class classifiers. Moreover, to reduce the computational cost of the ensemble and to improve its performance, these classifiers are trained using a specific attribute subset. This proposal offers the opportunity to capture the advantages provided by binary decomposition methods, by attribute partitioning methods, and by cooperative characteristics associated with a combination of redundant base learners. To analyse the quality of this architecture, its performance has been tested on different domains, and the results have been compared to other well-known classification methods. This experimental evaluation indicates that our model is, in most cases, as accurate as these methods, but it is much more efficient.