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.     

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.     

Comparing Combination Rules of Pairwise Neural Networks Classifiers

A decomposition approach to multiclass classification problems consists in decomposing a multiclass problem into a set of binary ones. Decomposition splits the complete multiclass problem into a set of smaller classification problems involving only two classes (binary classification: dichotomies). With a decomposition, one has to define a recombination which recomposes the outputs of the dichotomizers in order to solve the original multiclass problem. There are several approaches to the decomposition, the most famous ones being one-against-all and one-against-one also called pairwise. In this paper, we focus on pairwise decomposition approach to multiclass classification with neural networks as the base learner for the dichotomies. We are primarily interested in the different possible ways to perform the so-called recombination (or decoding). We review standard methods used to decode the decomposition generated by a one-against-one approach. New decoding methods are proposed and compared to standard methods. A stacking decoding is also proposed which consists in replacing the whole decoding or a part of it by a trainable classifier to arbiter among the conflicting predictions of the pairwise classifiers. Proposed methods try to cope with the main problem while using pairwise decomposition: the use of irrelevant classifiers. Substantial gain is obtained on all datasets used in the experiments. Based on the above, we provide future research directions which consider the recombination problem as an ensemble method.     

基于混合粒子群算法的运动估计研究

针对块匹配运动估计算法中传统搜索方法的不足,提出了一种新的基于混合粒子群的块匹配运动估计算法。在保留系统随机搜索性能的同时根据运动矢量特性合理地设计初始搜索种群,并通过混沌差分进化搜索协同粒子群算法迭代寻优,混沌序列用于优化差分变异算子,以提高算法的精细搜索能力。通过相同点检测技术和恰当的终止计划有效地降低了系统的运算复杂度。经实验测试与验证,该算法在搜索质量和运算复杂度中达到了一种动态平衡的状态,其整体性能高于传统的快速运动估计算法,效果更逼近于穷举搜索法。     

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 new fast algorithm for multiclass hyperspectral image classification with SVM

The support vector machine (SVM) has been a dominant machine-learning technique in the last decade and has demonstrated its efficiency in many applications. Research on classification of hyperspectral images have shown the efficiency of this method to overcome the Hughes phenomenon for classification of such images. A major drawback of classification by SVM is that this classifier was originally developed to solve binary problems, and the algorithms for multiclass problems usually have a high-computational load. In this article, a new and fast method for multiclass problems is proposed. This method has two stages. In the first stage, samples are classified by a maximum likelihood (ML) classifier, and in the second stage, SVM selects the final label of a sample among high-probability classes for that sample by a tree structure. So, for each sample, only some classes must be searched by SVM to find its label. The uncertainty of ML classification for a sample is obtained by the entropy of probabilities, and the number of classes that must be searched by SVM for a sample is obtained based on the uncertainty of that sample in the primary ML classification. This approach is compared with two widely used multiclass algorithms: one-against-one (OAO) and directed acyclic graph (DAGSVM). The obtained results on real data from the Airborne Visible/Infrared Imaging Spectrometer (AVIRIS) revealed less computational time and better accuracy compared to these multiclass algorithms.     

Parallelizing multiclass support vector machines for scalable image annotation

Machine learning techniques have facilitated image retrieval by automatically classifying and annotating images with keywords. Among them, Support Vector Machines (SVMs) are used extensively due to their generalization properties. SVM was initially designed for binary classifications. However, most classification problems arising in domains such as image annotation usually involve more than two classes. Notably, SVM training is a computationally intensive process especially when the training dataset is large. This paper presents a resource aware parallel multiclass SVM algorithm (named RAMSMO) for large-scale image annotation which partitions the training dataset into smaller binary chunks and optimizes SVM training in parallel using a cluster of computers. A genetic algorithm-based load balancing scheme is designed to optimize the performance of RAMSMO in balancing the computation of multiclass data chunks in heterogeneous computing environments. RAMSMO is evaluated in both experimental and simulation environments, and the results show that it reduces the training time significantly while maintaining a high level of accuracy in classifications.     

MINAS: multiclass learning algorithm for novelty detection in data streams

Data stream mining is an emergent research area that aims at extracting knowledge from large amounts of continuously generated data. Novelty detection (ND) is a classification task that assesses if one or a set of examples differ significantly from the previously seen examples. This is an important task for data stream, as new concepts may appear, disappear or evolve over time. Most of the works found in the ND literature presents it as a binary classification task. In several data stream real life problems, ND must be treated as a multiclass task, in which, the known concept is composed by one or more classes and different new classes may appear. This work proposes MINAS, an algorithm for ND in data streams. MINAS deals with ND as a multiclass task. In the initial training phase, MINAS builds a decision model based on a labeled data set. In the online phase, new examples are classified using this model, or marked as unknown. Groups of unknown examples can be used later to create valid novelty patterns (NP), which are added to the current model. The decision model is updated as new data come over the stream in order to reflect changes in the known classes and allow the addition of NP. This work also presents a set of experiments carried out comparing MINAS and the main novelty detection algorithms found in the literature, using artificial and real data sets. The experimental results show the potential of the proposed algorithm.     

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.     

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.     

超球体多类支持向量机理论

目前的多类分类器大多是经二分类器组合而成的,存在训练速度较慢的问题,在分类类别多的时候,会遇到很大困难,超球体多类支持向量机将超球体单类支持向量机扩展到多类问题,由于每类样本只参与一个超球体支持向量机的训练.因此,这是一种直接多类分类器,训练效率明显提高.为了有效训练超球体多类支持向量机,利用SMO算法思想,提出了超球体支持向量机的快速训练算法.同时对超球体多类支持向量机的推广能力进行了理论上的估计.数值实验表明,在分类类别较多的情况,这种分类器的训练速度有很大提高,非常适合解决类别数较多的分类问题.超球体多类支持向量机为研究快速直接多类分类器提供了新的思路.     

A Fast Multiclass Classification Algorithm Based on Cooperative Clustering

We present a fast multiclass classification algorithm to address the multiclass problems with a new clustering method, namely cooperative clustering. In the method of cooperative clustering, we iteratively compute the cluster centers of all classes simultaneously. For every cluster center in a class, a cluster center in an adjacent class is selected and the pair of cluster centers is drawn towards the boundary. In this way, the data set around a class is found and the data set plus the data in this class can be trained to form a classifier. With cooperative clustering, one binary classifier in the one-vs-all approach can be trained with far less samples. Furthermore, a kNN method is proposed to accelerate the classifying procedure. With this algorithm, both training and classification efficiency are improved with a slight impact on classification accuracy.     

A technique for feature selection in multiclass problems

One of the main phases in the development of a system for the classification of remote sensing images is the definition of an effective set of features to be given as input to the classifier. In particular, it is often useful to reduce the number of features available, while saving the possibility to discriminate among the different land-cover classes to be recognized. This paper addresses this topic with reference to applications that involve more than two land-cover classes (multiclass problems). Several criteria proposed in the remote sensing literature are considered and compared with one another and with the criterion presented by the authors. Such a criterion, unlike those usually adopted for multiclass problems, is related to an upper bound to the error probability of the Bayes classifier. As the objective of feature selection is generally to identify a reduced set of features that minimize the errors of the classifier, the aforementioned property is very important because it allows one to select features by taking into account their effects on classification errors. Experiments on two remote sensing datasets are described and discussed. These experiments confirm the effectiveness of the proposed criterion, which performs slightly better than all the others considered in the paper. In addition, the results obtained provide useful information about the behaviour of different classical criteria when applied in multiclass cases.     

Adapted One-versus-All Decision Trees for Data Stream Classification

One versus all (OVA) decision trees learn k individual binary classifiers, each one to distinguish the instances of a single class from the instances of all other classes. Thus OVA is different from existing data stream classification schemes whose majority use multiclass classifiers, each one to discriminate among all the classes. This paper advocates some outstanding advantages of OVA for data stream classification. First, there is low error correlation and hence high diversity among OVA's component classifiers, which leads to high classification accuracy. Second, OVA is adept at accommodating new class labels that often appear in data streams. However, there also remain many challenges to deploy traditional OVA for classifying data streams. First, as every instance is fed to all component classifiers, OVA is known as an inefficient model. Second, OVA's classification accuracy is adversely affected by the imbalanced class distribution in data streams. This paper addresses those key challenges and consequently proposes a new OVA scheme that is adapted for data stream classification. Theoretical analysis and empirical evidence reveal that the adapted OVA can offer faster training, faster updating and higher classification accuracy than many existing popular data stream classification algorithms.     

Facial expression recognition using iterative universum twin support vector machine

Facial expressions are one of the most important characteristics of human behaviour. They are very useful in applications on human computer interaction. To classify facial emotions, different feature extraction methods are used with machine learning techniques. In supervised learning, information about the distribution of data is given by data points not belonging to any of the classes. These data points are known as universum data. In this work, we use universum data to perform multiclass classification of facial emotions from human facial images. Moreover, the existing universum based models suffer from the drawback of high training cost, so we propose an iterative universum twin support vector machine (IUTWSVM) using Newton method. Our IUTWSVM gives good generalization performance with less computation cost. To solve the optimization problem of proposed IUTWSVM, no optimization toolbox is required. Further, improper selection of universum points always leads to degraded performance of the model. For generating better universum, a novel scheme is proposed in this work based on information entropy of data. To check the effectiveness of proposed IUTWSVM, several numerical experiments are performed on benchmark real world datasets. For multiclass classification of facial emotions, the performance of IUTWSVM is compared with existing algorithms using different feature extraction techniques. Our proposed algorithm shows better generalization performance with less training cost in both binary as well as multiclass classification problems.     

基于二叉树的多分类SVM算法在电子邮件过滤中的应用

目前性能较好的多分类算法有1-v-r支持向量机（SVM）、1-1-1SVM、DDAG SVM等，但存在大量不可分区域且训练时间较长的问题。提出一种基于二叉树的多分类SVM算法用于电子邮件的分类与过滤，通过构建二叉树将多分类转化为二值分类，算法采用先聚类再分类的思想，计算测试样本与子类中心的最大相似度和子类间的分离度，以构造决策节点的最优分类超平面。对于C类分类只需C-1个决策函数，从而可节省训练时间。实验表明，该算法得到了较高的查全率、查准率。     

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.

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.     

DESIGN OF DECISION TREE VIA KERNELIZED HIERARCHICAL CLUSTERING FOR MULTICLASS SUPPORT VECTOR MACHINES

As a very effective method for universal purpose pattern recognition, support vector machine (SVM) was proposed for dichotomic classification problem, which exhibits a remarkable resistance to overfitting, a feature explained by the fact that it directly implements the principle of structural risk minimization. However, in real world, most of classification problems consist of multiple categories. In an attempt to extend the binary SVM classifier for multiclass classification, decision-tree-based multiclass SVM was proposed recently, in which the structure of decision tree plays an important role in minimizing the classification error. The present study aims at developing a systematic way for the design of decision tree for multiclass SVM. Kernel-induced distance function between datasets was discussed and then kernelized hierarchical clustering was developed and used in determining the structure of decision tree. Further, simulation results on satellite image interpretation show the superiority of the proposed classification strategy over the conventional multiclass SVM algorithms.     

Learning with few examples for binary and multiclass classification using regularization of randomized trees

The human visual system is often able to learn to recognize difficult object categories from only a single view, whereas automatic object recognition with few training examples is still a challenging task. This is mainly due to the human ability to transfer knowledge from related classes. Therefore, an extension to Randomized Decision Trees is introduced for learning with very few examples by exploiting interclass relationships. The approach consists of a maximum a posteriori estimation of classifier parameters using a prior distribution learned from similar object categories. Experiments on binary and multiclass classification tasks show significant performance gains