Techniques in support vector classification

Abstract

This work falls into the field of Pattern Classification and more generally Artificial Intelligence. Classification is the problem of assigning a "pattern" z to be a member of a finite set ("class") X or a member of a disjoint finite set Y. In case z ∈ Rn and X, Y ⊂ Rn we can solve this problem using Support Vector Machines. Support Vector Machines are functions of the form ƒ(z) = sign (∑i αik(xi, z) + ∑jβjk(yj, z) + b), (*) where k : Rn x Rn → R and z is classified as a member of X = {xi} if ƒ(z) > 0 and a member of Y = {yj} otherwise. We consider three problems in classification, two of which concern Support Vector Machines. Our first problem concerns feature selection for classification. Feature selection is the problem of identifying properties which distinguish between the two classes X and Y. Color, for example, distinguishes between apples and oranges, while shape may not. Our method of feature selection uses a novel combination of a linear classifier known as Fisher's discriminant and a nonlinear (polynomial) map known as the Veronese map. We apply our method to a problem in materials design. Our second problem concerns the selection of the kernel k : Rn x Rn → R in (*). For kernel selection we use a kernel version of the classical Gram-Schmidt orthonormalization procedure again coupled with Fisher's discriminant. We apply our method to the materials design problem and to a handwritten digit recognition problem. Finally, we consider the problem of training Support Vector Machines. Specifically, we develop a fast method for obtaining the coefficients αi and βj in (*). Traditionally, these coefficients are found by solving a constrained quadratic programming problem. We present a geometric reformulation of the SVM quadratic programming problem. We then present, using this reformulation, a modified version of Gilbert's Algorithm for obtaining the coefficients αi and βj. We compare our algorithm with the Nearest Point Algorithm and with Sequential Minimal Optimization.