Kernels for Generalized Multiple-Instance Learning

The multiple-instance learning (MIL) model has been successful in numerous application areas. Recently, a generalization of this model and an algorithm for it have been introduced, showing significant advantages over the conventional MIL model on certain application areas. Unfortunately, that algorithm is not scalable to high dimensions. We adapt that algorithm to one that uses a support vector machine with our new kernel k(A). This reduces the time complexity from exponential in the dimension to polynomial. Computing our new kernel is equivalent to counting the number of boxes in a discrete bounded space that contain at least one point from each of two multisets. We first show that this problem is #P-complete and then present a fully polynomial randomized approximation scheme (FPRAS) for it. We then extend k(A) by enriching its representation into a new kernel k(min) and also consider a normalized version of k(A) that we call k(A/V) (which may or may not be a kernel but whose approximation yielded positive semidefinite Gram matrices in practice). We then empirically evaluate all three measures on data from content-based image retrieval, biological sequence analysis, and the Musk data sets. We found that our kernels performed well on all data sets relative to algorithms in the conventional MIL model.