BSVM: A Banded Support Vector Machine

Author: Gautam V. Pendse

Abstract

We describe a novel binary classi cation technique called Banded SVM (B-SVM). In the standard C-SVM formulation of Cortes and Vapnik (1995), the decision rule is encouraged to lie in the interval [1, ∞]. The new B-SVM objective function contains penalty terms that encourage the decision rule to lie in a user speci ed range [ρ1, ρ2]. In addition to the standard set of support vectors (SVs) near the class boundaries, B-SVM results in a second set of SVs in the interior of each class.

Read about BSVM

Main ideas

  1. Scalar linear projections of multivariate random vectors with finite co-variance have a finite variance.

  2. Chebyshev's inequality implies that most of the values of the above scalar linear projection are concentrated around its mean.

  3. If we consider the SVM decision rule as a measure of membership in class +1 and class -1 then the decision rule values should also be concentrated in each class.

  4. The standard C-SVM objective function does not enforce this band formation in each class.

  5. B-SVM includes a novel penalty term in the objective function that encourages class specific band formation and this leads to a novel Lagrangian dual optimization problem of which the C-SVM dual is a special case.

    BSVM logic

Key references

  1. Gautam V. Pendse. BSVM: A Banded Support Vector Machine. [pdf ], arXiv:1107.2347v1, 2011. (this work)

  2. B. E. Boser, I. M. Guyon and V. Vapnik. A training algorithm for optimal margin classiers. Proceedings of the 5th Annual ACM Workshop on Computational Learning Theory, 144-152, 1992. [pdf ]

  3. C. Cortes and V. Vapnik. Support vector networks. Machine Learning, 20:273-297, 1995. [pdf ]

PDF Figures

  1. Figure1 [BSVM penalty function]
  2. Figure2 [C-SVM vs. BSVM support vectors]
  3. Figure3 [C-SVM vs. BSVM decision function and heat map]
  4. Figure4 [C-SVM vs. BSVM sensitivity curve]

Download Webpage and Data

Toy data used for comparing C-SVM and B-SVM along with this webpage can be downloaded here: bsvm_webpage_data.zip . This data is freely available under the terms of the license described below. This zip file includes the following directories:

webpage

This directory contains a standalone version of this webpage bsvm.html for offline browsing.

data

This directory contains a MATLAB .mat file: demo_data.mat which contains the data used to generate Figure 2 and Figure 3. A README.m file contains a brief description of the data.

License

Creative Commons License
BSVM toy data and webpage by Gautam V. Pendse is licensed under a Creative Commons Attribution 3.0 Unported License.

Copyright © 2011, Gautam V. Pendse
e-mail: gpendse@mclean.harvard.edu