Multiple Instance Classification via Successive Linear Programming
Abstract
The multiple instance classification problem [6,2,12] is formulated using a linear
or nonlinear kernel as the minimization of a linear function in a finite dimensional
(noninteger) real space subject to linear and bilinear constraints. A linearization
algorithm is proposed that solves a succession of fast linear programs that converges
in a few iterations to a local solution. Computational results on a number of datasets
indicate that the proposed algorithm is competitive with the considerably more
complex integer programming and other formulations. A distinguishing aspect of
our linear classifier not shared by other multiple instance classifiers is the sparse
number of features it utilizes. In some tasks the reduction amounts to less than one
percent of the original features.
Subject
successive linearization algorithm
support vector machines
multiple instance learning
Permanent Link
http://digital.library.wisc.edu/1793/64330Citation
05-02