SVM-Based Generalized Multiple-Instance Learning via Approximate Box Counting
Abstract
The multiple-instance learning (MIL) model has been very successful inapplication areas such as drug discovery and content-based image-retrieval. Recently, a generalization of this model and an algorithm for thisgeneralization were introduced, showing significant advantages over theconventional MIL model on certain application areas. Unfortunately, thisalgorithm is inherently inefficient, preventing scaling to high dimensions. Wereformulate 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) forit. Finally, we empirically evaluate our kernel.
Cite
Text
Tao et al. "SVM-Based Generalized Multiple-Instance Learning via Approximate Box Counting." International Conference on Machine Learning, 2004. doi:10.1145/1015330.1015405Markdown
[Tao et al. "SVM-Based Generalized Multiple-Instance Learning via Approximate Box Counting." International Conference on Machine Learning, 2004.](https://mlanthology.org/icml/2004/tao2004icml-svm/) doi:10.1145/1015330.1015405BibTeX
@inproceedings{tao2004icml-svm,
title = {{SVM-Based Generalized Multiple-Instance Learning via Approximate Box Counting}},
author = {Tao, Qingping and Scott, Stephen Donald and Vinodchandran, N. V. and Osugi, Thomas Takeo},
booktitle = {International Conference on Machine Learning},
year = {2004},
doi = {10.1145/1015330.1015405},
url = {https://mlanthology.org/icml/2004/tao2004icml-svm/}
}