کاهش تعداد دسته بندی کننده (Classifier) های فرعی برای ماشین بردار پشتیبانی (SVM) چند مقوله ای دو به دو

ABSTRACT Reducing the number of sub-classifiers for pairwise multi-category support vector machines

The Support Vector Machine (SVM) is a powerful technique for classification. It classifies positive and negative samples by searching a hyperplane with the largest margin between them, so that better generalization performance and fewer training errors can be obtained. In this paper, we will discuss SVM for multi-category classification, which means the number of the categories is more than two.

Generally, the binary (two-category) SVM can be extended to multi-category case in two ways. The first way is considering all categories in one optimization problem. According to this way, a multi-category problem is formulated into one optimization equation, but there are too many parameters to adjust, so it is inefficient. The second way is constructing several binary sub-classifiers. In this way, multi-category problems are treated as a series of binary sub-problems, and many methods are developed based on this idea. Compared with the first, the second way is more widely used.

Although many methods of the second way are available, when the number of the categories or the size of each category is quite large, these methods are faced with a common problem, that is, it takes a very long time for all binary SVM sub-classifiers being trained. Targeted on this, we propose an uncertainty sampling-based multi-category SVM (abbreviated as US_MSVM) in this paper. Faster than ‘‘1-a-r’’ and pairwise, the new method has similar average accuracy with them. In each round of US_MSVM, samples of the two most indistinguishable categories are selected for the next training round. After a training round, the probabilities of positive samples (PPS) are used to decide which two categories are most indistinguishable.

The remaining of this paper is organized as follows: In Section 2, we briefly review the current research situation of multi-category SVM. The main idea of uncertainty sampling strategy will be introduced in Section 3. The new method, US_MSVM, is presented and analyzed in Section 4. Experimental results of the performance comparison between the new method and pairwise classifier on the benchmark data are shown in Section 5. Conclusions are drawn in Section 6.