Qingping Tao, Stephen Scott, N. V. Vinodchandran, and Thomas Osugi. SVM-Based Generalized Multiple-Instance Learning via Approximate Box Counting. In Proceedings of the Twenty-First International Conference on Machine Learning, pages 799–806, Banff, Alberta, Canada, July 2004.
Abstract
137Kb PDF

Abstract

The multiple-instance learning (MIL) model has been very successful in application areas such as drug discovery and content-based image-retrieval. Recently, a generalization of this model and an algorithm for this generalization were introduced, showing significant advantages over the conventional MIL model in certain application areas. Unfortunately, this algorithm is inherently inefficient, preventing scaling to high dimensions. We reformulate this algorithm using a kernel for a support vector machine, reducing its time complexity from exponential to polynomial. Computing the kernel is equivalent to counting the number of axis-parallel boxes in a discrete, bounded space that contain at least one point from each of two multisets P and Q. We show that this problem is #P-complete, but then give a fully polynomial randomized approximation scheme (FPRAS) for it. Finally, we empirically evaluate our kernel.

Keywords: Multiple-instance learning, approximation algorithms, fully polynomial randomized approximation scheme, FPRAS, support vector machines

To Stephen D. Scott's home page

Last modified 29 April 2004.