Fisher Consistency of Multicategory Support Vector Machines
Yufeng Liu · International Conference on Artificial Intelligence and Statistics · 2007
The Support Vector Machine (SVM) has become one of the most popular machine learning techniques in recent years. The success of the SVM is mostly due to its elegant margin concept and theory in binary classification. Generalization to the multicategory setting, however, is not trivial. There are a number of different multicategory extensions of the SVM in the literature. In this paper, we review several commonly used extensions and Fisher consistency of these extensions. For inconsistent extensions, we propose two approaches to make them Fisher consistent, one is to add bounded constraints and the other is to truncate unbounded hinge losses. 1 Background on Binary SVM The Support Vector Machine (SVM) is a well known large margin classifier and has achieved great success in many applications (Vapnik, 1998, Cristianini and Shawe-Taylor, 2000, and Hastie, Tibshirani, and Friedman, 2000). The basic concept behind the binary SVM is to search a separating hyperplane with maximum separation between the two classes. Suppose a training dataset containing n training pairs {xi, yi}i=1, i.i.d realizations from a probability distribution P (x, y), is given. The goal is to search for a linear function f(x) = w ′ x + b so that sign(f(x)) can be used for prediction of labels for new inputs. The SVM aims to find such an f so that points of class +1 and points of class −1 are best separated. In particular, for the separable case, the SVM’s solution maximizes the distance between f(x) = ±1 subject to yif(xi) ≥ 1; i = 1, . . . , n. This distance can be expressed as 2 ‖w‖ and is known as the geometric margin. When perfect separation between two classes is not feasible, slack variables ξi; i = 1, . . . , n, can be used to measure the amount of violation of the original constraints. Then the SVM solves the following optimization problem: min w,b 1 2 ‖w‖2 + C n ∑