A Novel Reconstruction Strategy of Half-Versus-Half for Multi-Class SVMs

Support vector machine (SVM) for pattern recognition is a binary classifier. When dealing with multi-class tasks, a popular and applicable way is to decompose the original problem into a set of binary sub-problems. This paper presents a novel half-versus-half (HVH) decomposition scheme. Unlike the conventional implementation methods, HVH is built via dividing the training dataset of K-classes into two comparable sub-sets of classes, which can consider the multi-classification as a decision-making table. The structure of HVH requires at most log₂(K) binary SVMs, which is far less than that of conventional methods. Experiments are performed on several benchmark datasets, and the results show that HVH has advantages over conventional methods in complexity and testing speed.