Support Vector Machines for Multiple-Instance Learning

S. AndrewsIoannis TsochantaridisThomas Hofmann

article2002NeurIPS1,676 citations

Extends Support Vector Machines to multiple-instance learning by formulating pattern-level and bag-level maximum margin optimizations as mixed integer quadratic programs, enabling kernel-based classification on weakly annotated data across drug design, image indexing, and text categorization tasks.

Listen

Real-world data often comes with incomplete or ambiguous labels where collections of instances—known as bags—are labeled as a whole rather than individually. For instance, in pharmaceutical drug design, an entire molecule is tested for efficacy without knowing which specific 3D shape (conformation) is active; in image retrieval, a whole image is labeled without isolating the exact object; and in document categorization, a document is tagged by topic without specifying the key passage. Multiple-instance learning solves this ambiguity under the rule that a bag is positive if at least one instance inside it is positive. Until recently, this domain relied mostly on specialized, restrictive algorithms rather than powerful, general-purpose classification methods.

The article demonstrates how to adapt Support Vector Machines—a state-of-the-art classification framework—to multiple-instance learning by formulating the task as a maximum-margin optimization problem. Specifically, the article develops and evaluates two distinct mathematical formulations: mi-SVM, which maximizes the classification margin at the individual pattern level, and MI-SVM, which maximizes the margin across whole bags.

To implement these methods, the article casts both formulations as mixed-integer quadratic programs and solves them using alternating heuristic algorithms. These heuristics alternate between training a standard classifier and updating the unobserved pattern labels or identifying a single representative witness pattern per positive bag. The authors benchmarked the models against standard techniques, such as Expectation-Maximization Diverse Density, across three distinct application domains: pharmaceutical molecule activity (the MUSK1 and MUSK2 datasets), automated image annotation using segmented Corel animal photos, and high-dimensional text categorization using passage-level splits of medical abstracts from the TREC9 dataset.

The experimental findings show that the proposed methods achieve strong, competitive results across multiple domains. On benchmark molecular data, mi-SVM reached 87.4% accuracy on MUSK1 and 83.6% on MUSK2, while MI-SVM achieved 77.9% and 84.3% respectively. In image classification tasks across three animal categories, both methods consistently outperformed the reference baseline by several percentage points, with linear MI-SVM reaching up to 84.0% accuracy on tiger images compared to 72.1% for the baseline. Similarly, in high-dimensional text categorization, both formulations with linear and polynomial kernels outperformed the baseline method across nearly all evaluated document categories, frequently exceeding 80% to 90% accuracy.

These results demonstrate that organizations can successfully apply flexible, kernel-based Support Vector Machines to weakly supervised and partially labeled data. This reduces the time and cost required for fine-grained manual data labeling, such as annotating exact image segments or specific text passages, without sacrificing classification performance. The choice between the two formulations offers practical trade-offs: mi-SVM is ideal when the goal is to discover or classify individual instances, whereas MI-SVM is preferable when only bag-level predictions are required.

Organizations handling weakly annotated data should consider adopting these maximum-margin formulations as standard baselines over domain-specific ad-hoc algorithms. Because the heuristics can be sensitive to local minima, practitioners should explore initialization strategies and algorithmic refinements such as simulated annealing or branch-and-bound techniques to optimize solution quality. Future work should focus on validating these techniques on full-scale, production-sized datasets and refining image representations to achieve higher absolute accuracy.

  • Paper: Support-vector networks, Corinna Cortes et al. (1995). It introduces the foundational Support Vector Machine classification framework and margin-maximization formulation that the source adapts directly to the multiple-instance learning setting.
  • Paper: A training algorithm for optimal margin classifiers, Bernhard E. Boser et al. (1992). It establishes the core dual quadratic optimization and kernel-based maximum-margin principles underpinning the source's mi-SVM and MI-SVM formulations.
  • Paper: Transductive Inference for Text Classification using Support Vector Machines, Thorsten Joachims (1999). It pioneers mixed-integer optimization and alternating heuristic routines for weakly labeled Support Vector Machines, providing the algorithmic template used by the source to handle unobserved instance labels.
  • Paper: Exploiting Generative Models in Discriminative Classifiers, T. Jaakkola et al. (1998). It establishes how kernel functions can be leveraged within discriminative margin classifiers for complex, structured, and variable-length data domains.
  • Paper: Attention-based Deep Multiple Instance Learning, Maximilian Ilse et al. (2018). It extends multiple-instance learning beyond classical maximum-margin methods by incorporating neural attention mechanisms to evaluate instance contributions and bag predictions end-to-end.
  • Paper: Robust Object Tracking with Online Multiple Instance Learning, Boris Babenko et al. (2011). It applies the multiple-instance learning paradigm formulated in the source to real-time visual tracking by treating ambiguous target bounding boxes as bags of instances.
  • Paper: Large Margin Methods for Structured and Interdependent Output Variables, Ioannis Tsochantaridis et al. (2005). It generalizes maximum-margin optimization from binary and bag-level instance assignments to complex, structured, and interdependent output spaces using cutting-plane methods.
  • Paper: Self-Paced Learning for Latent Variable Models, M. P. Kumar et al. (2010). It builds on latent-variable maximum-margin frameworks like mi-SVM by introducing self-paced learning to prevent alternating optimization heuristics from falling into poor local minima.
  • Paper: Multiple Kernel Learning Algorithms, Mehmet Gönen et al. (2011). It provides a comprehensive framework for learning combinations of multiple kernels, extending the single-kernel selection strategies explored in the source.
Cover for Support Vector Machines for Multiple-Instance Learning

Abstract

This paper presents two new formulations of multiple-instance learning as a maximum margin problem. The proposed extensions of the Support Vector Machine (SVM) learning approach lead to mixed integer quadratic programs that can be solved heuristically. Our generalization of SVMs makes a state-of-the-art classification technique, including non-linear classification via kernels, available to an area that up to now has been largely dominated by special purpose methods. We present experimental results on a pharmaceutical data set and on applications in automated image indexing and document categorization.

Table of Contents

  • 1 Introduction
  • 2 Multiple-Instance Learning
  • 3 Maximum Pattern Margin Formulation of MIL
  • 4 Maximum Bag Margin Formulation of MIL
  • 5 Optimization Heuristics
  • 6 Experimental Results
  • 6.1 MUSK Data Set
  • 6.2 Automatic Image Annotation
  • 6.3 Text Categorization
  • 7 Conclusion and Future Work
  • Acknowledgments
  • References

Knowls

  1. Knowl 1 — mi-SVM Pattern-Margin Formulation for Multiple-Instance Learning

    model/method

    In multiple-instance learning (MIL), training patterns x1,…,xn∈Rd\mathbf{x}_1, \dots, \mathbf{x}_n \in \mathbb{R}^d are grouped into bags BI={xi:i∈I}B_I = \{\mathbf{x}_i : i \in I\} with index sets I⊆{1,…,n}I \subseteq \{1, \dots, n\} and binary bag labels YI∈{−1,1}Y_I \in \{-1, 1\}. An individual instance xi\mathbf{x}_i has an unobserved label yi∈{−1,1}y_i \in \{-1, 1\}. A negative bag (YI=−1Y_I = -1) implies yi=−1y_i = -1 for all i∈Ii \in I, whereas a positive bag (YI=1Y_I = 1) requires at least one pattern i∈Ii \in I to have yi=1y_i = 1.

    The mi-SVM formulation treats unobserved instance labels yiy_i as discrete optimization variables subject to the bag-level constraints and maximizes the standard instance margin jointly over (w,b,ξ)(w, b, \xi) and {yi}\{y_i\} via the mixed-integer quadratic program:

    min⁡{yi}min⁡w,b,ξ12∥w∥2+C∑i=1nξi\min_{\{y_i\}} \min_{\mathbf{w}, b, \boldsymbol{\xi}} \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_{i=1}^n \xi_i

    subject to ∀i:yi(⟨w,xi⟩+b)≥1−ξi,ξi≥0,yi∈{−1,1},\text{subject to } \forall i: \quad y_i (\langle \mathbf{w}, \mathbf{x}_i \rangle + b) \ge 1 - \xi_i, \quad \xi_i \ge 0, \quad y_i \in \{-1, 1\},

    ∑i∈Iyi+12≥1∀I with YI=1,andyi=−1∀i∈I with YI=−1,\sum_{i \in I} \frac{y_i + 1}{2} \ge 1 \quad \forall I \text{ with } Y_I = 1, \quad \text{and} \quad y_i = -1 \quad \forall i \in I \text{ with } Y_I = -1,

    where w∈Rd\mathbf{w} \in \mathbb{R}^d is the weight vector, b∈Rb \in \mathbb{R} is the bias term, ξi≥0\xi_i \ge 0 are slack variables, and C>0C > 0 is the regularization parameter.

  2. Knowl 2 — MI-SVM Bag-Margin Formulation for Multiple-Instance Learning

    model/method

    The MI-SVM approach extends the margin concept directly to bags. The functional margin of a bag BI={xi:i∈I}B_I = \{\mathbf{x}_i : i \in I\} with label YI∈{−1,1}Y_I \in \{-1, 1\} with respect to a hyperplane (w,b)(\mathbf{w}, b) is defined as γI=YImax⁡i∈I(⟨w,xi⟩+b)\gamma_I = Y_I \max_{i \in I} (\langle \mathbf{w}, \mathbf{x}_i \rangle + b). The soft-margin bag formulation is:

    min⁡w,b,ξ12∥w∥2+C∑IξI\min_{\mathbf{w}, b, \boldsymbol{\xi}} \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_I \xi_I

    subject to ∀I:YImax⁡i∈I(⟨w,xi⟩+b)≥1−ξI,ξI≥0,\text{subject to } \forall I: \quad Y_I \max_{i \in I} (\langle \mathbf{w}, \mathbf{x}_i \rangle + b) \ge 1 - \xi_I, \quad \xi_I \ge 0,

    where ξI\xi_I is a slack variable associated with bag BIB_I.

    For positive bags (YI=1Y_I = 1), introducing a selector variable s(I)∈Is(I) \in I to choose the single witness instance xs(I)\mathbf{x}_{s(I)} representing bag BIB_I yields the equivalent mixed-integer formulation:

    min⁡smin⁡w,b,ξ12∥w∥2+C∑IξI\min_{s} \min_{\mathbf{w}, b, \boldsymbol{\xi}} \frac{1}{2} \|\mathbf{w}\|^2 + C \sum_I \xi_I

    subject to ∀I:\text{subject to } \forall I: if YI=−1:−(⟨w,xi⟩+b)≥1−ξI,∀i∈I,\text{if } Y_I = -1: \quad -(\langle \mathbf{w}, \mathbf{x}_i \rangle + b) \ge 1 - \xi_I, \quad \forall i \in I, if YI=1:⟨w,xs(I)⟩+b≥1−ξI,\text{if } Y_I = 1: \quad \langle \mathbf{w}, \mathbf{x}_{s(I)} \rangle + b \ge 1 - \xi_I, and ξI≥0.\text{and } \xi_I \ge 0.

    In this formulation, non-witness instances in positive bags do not affect the objective function once s(I)s(I) is fixed.

  3. Knowl 3 — Dual Formulation and Bag-Influence Box Constraints for MI-SVM

    theoretical result

    For fixed positive bag witness selections s(I)∈Is(I) \in I, the dual objective function of the MI-SVM optimization problem is equivalent to the standard SVM Wolfe dual, with modified box constraints on the Lagrange multipliers α\alpha:

    0≤αI≤Cfor bags I such that YI=10 \le \alpha_I \le C \quad \text{for bags } I \text{ such that } Y_I = 1

    0≤∑i∈Iαi≤Cfor bags I such that YI=−10 \le \sum_{i \in I} \alpha_i \le C \quad \text{for bags } I \text{ such that } Y_I = -1

    where αI\alpha_I denotes the Lagrange multiplier associated with the positive witness instance xs(I)\mathbf{x}_{s(I)}, and αi\alpha_i denotes the multiplier for instance ii in negative bag BIB_I. Consequently, the total influence of any single bag (positive or negative) on the learned hyperplane is bounded by the regularization parameter CC.

  4. Knowl 4 — mi-SVM Alternating Optimization Algorithm

    algorithm

    The mi-SVM heuristic optimizes the mixed-integer pattern-margin problem by alternating between solving a convex quadratic program (QP) over (w,b)(\mathbf{w}, b) given imputed instance labels {yi}\{y_i\}, and updating the labels {yi}\{y_i\} given the current hyperplane.

    Input: Training instances xi\mathbf{x}_i, bag index sets II, bag labels YI∈{−1,1}Y_I \in \{-1, 1\}, regularization constant CC
    Output: Hyperplane parameters (w,b)(\mathbf{w}, b)
    initialize yi=YIy_i = Y_I for all i∈Ii \in I
    repeat
        compute SVM solution (w,b)(\mathbf{w}, b) for dataset with imputed labels {(xi,yi)}\{(\mathbf{x}_i, y_i)\}
        compute outputs fi=⟨w,xi⟩+bf_i = \langle \mathbf{w}, \mathbf{x}_i \rangle + b for all xi\mathbf{x}_i in positive bags
        set yi=sgn(fi)y_i = \text{sgn}(f_i) for every i∈Ii \in I where YI=1Y_I = 1
        for each positive bag BIB_I with YI=1Y_I = 1 do
            if ∑i∈I(1+yi)/2==0\sum_{i \in I} (1 + y_i) / 2 == 0 then
                compute i∗=arg⁡max⁡i∈Ifii^* = \arg\max_{i \in I} f_i
                set yi∗=1y_{i^*} = 1
            end if
        end for
    until imputed labels {yi}\{y_i\} do not change
    return (w,b)(\mathbf{w}, b)

    The condition ∑i∈I(1+yi)/2==0\sum_{i \in I} (1 + y_i) / 2 == 0 detects if all patterns in a positive bag have been assigned negative labels, in which case the pattern with the maximal output fif_i is forced to have label yi∗=1y_{i^*} = 1 to satisfy the multiple-instance constraint.

  5. Knowl 5 — MI-SVM Alternating Optimization Algorithm

    algorithm

    The MI-SVM heuristic solves the mixed-integer bag-margin problem by alternating between solving an SVM QP using selected witness instances for positive bags alongside all negative instances, and updating the witness selector variables s(I)s(I) based on the resulting discriminant function.

    Input: Training instances xi\mathbf{x}_i, bag index sets II, bag labels YI∈{−1,1}Y_I \in \{-1, 1\}, regularization constant CC
    Output: Hyperplane parameters (w,b)(\mathbf{w}, b)
    initialize xI=∑i∈Ixi/∣I∣\mathbf{x}_I = \sum_{i \in I} \mathbf{x}_i / |I| for every positive bag BIB_I with YI=1Y_I = 1
    repeat
        compute QP solution (w,b)(\mathbf{w}, b) for dataset with positive examples {xI:YI=1}\{\mathbf{x}_I : Y_I = 1\} and all negative patterns
        compute outputs fi=⟨w,xi⟩+bf_i = \langle \mathbf{w}, \mathbf{x}_i \rangle + b for all xi\mathbf{x}_i in positive bags
        for each positive bag BIB_I with YI=1Y_I = 1 do
            set s(I)=arg⁡max⁡i∈Ifis(I) = \arg\max_{i \in I} f_i
            set xI=xs(I)\mathbf{x}_I = \mathbf{x}_{s(I)}
        end for
    until selector variables s(I)s(I) do not change for all positive bags
    return (w,b)(\mathbf{w}, b)

    Each positive bag is initially represented by its centroid vector before iteratively switching to the instance xs(I)\mathbf{x}_{s(I)} that achieves the largest discriminant value.

  6. Knowl 6 — Classification Performance on Benchmark MUSK Datasets

    data/table

    Classification accuracy (in %) averaged over ten 10-fold cross-validation runs on the benchmark MUSK1 and MUSK2 datasets. MUSK1 contains ~6 conformations per molecule on average, whereas MUSK2 contains >60 conformations per bag. Each conformation is described by a 166-dimensional feature vector. The SVM methods use an RBF kernel K(x,y)=exp⁡(−γ∥x−y∥2)K(\mathbf{x}, \mathbf{y}) = \exp(-\gamma \|\mathbf{x} - \mathbf{y}\|^2) with coarsely tuned γ\gamma.

    Dataset EM-DD DD MI-NN IAPR mi-SVM MI-SVM
    MUSK1 84.8 88.0 88.9 92.4 87.4 77.9
    MUSK2 84.9 84.0 82.5 89.2 83.6 84.3

    Both SVM formulations achieve competitive classification performance against general MIL baselines (EM-DD, DD, MI-NN). While mi-SVM substantially outperforms MI-SVM on MUSK1 (87.4% vs 77.9%), MI-SVM achieves higher accuracy on MUSK2 (84.3% vs 83.6%). Neither formulation matches the task-tailored Iterated Axis-Parallel Rectangle (IAPR) baseline.

  7. Knowl 7 — Classification Performance on Corel Image Annotation Datasets

    data/table

    Classification accuracy (in %) evaluated on Corel image subsets preprocessed with the Blobworld segmentation system, representing images as bags of segment descriptors (color, texture, shape; 230 features total). Each category has 100 positive and 100 negative images.

    Dataset Dims EM-DD mi-SVM MI-SVM
    Category inst/feat linear poly rbf linear poly rbf
    Elephant 1391/230 78.3 82.2 78.1 80.0 81.4 79.0 73.1
    Fox 1320/230 56.1 58.2 55.2 57.9 57.8 59.4 58.8
    Tiger 1220/230 72.1 78.4 78.1 78.9 84.0 81.6 66.6

    Both mi-SVM and MI-SVM consistently outperform EM-DD across the three image categories by several percentage points, with MI-SVM linear achieving the highest accuracy on Tiger (84.0%) and mi-SVM linear achieving the highest on Elephant (82.2%).

  8. Knowl 8 — Classification Performance on TREC9 Text Categorization Datasets

    data/table

    Classification accuracy (in %) on seven text categorization benchmarks extracted from TREC9 (OHSUMED MEDLINE documents annotated with MeSH terms). Documents are represented as bags of overlapping passages of up to 50 words each, resulting in sparse, high-dimensional bag representations.

    Dataset Dims EM-DD mi-SVM MI-SVM
    Category inst/feat linear poly rbf linear poly rbf
    TST1 3224/6668 85.8 93.6 92.5 90.4 93.9 93.8 93.7
    TST2 3344/6842 84.0 78.2 75.9 74.3 84.5 84.4 76.4
    TST3 3246/6568 69.0 87.0 83.3 69.0 82.2 85.1 77.4
    TST4 3391/6626 80.5 82.8 80.0 69.6 82.4 82.9 77.3
    TST7 3367/7037 75.4 81.3 78.7 81.3 78.0 78.7 64.5
    TST9 3300/6982 65.5 67.5 65.6 55.2 60.2 63.7 57.0
    TST10 3453/7073 78.5 79.6 78.3 52.6 79.5 81.0 69.1

    Linear and polynomial kernels outperform RBF kernels on high-dimensional text data across almost all subsets. Both mi-SVM and MI-SVM generally outperform EM-DD (e.g., reaching ~93.9% on TST1 compared to 85.8% for EM-DD and ~87.0% on TST3 compared to 69.0%), while showing comparable accuracy to each other.

  9. Knowl 9 — Susceptibility of MIL-SVM Optimization Heuristics to Local Minima

    limitation

    Because mi-SVM and MI-SVM are formulated as mixed-integer quadratic programs, finding the global optimum is computationally intractable for realistic dataset sizes. The proposed alternating optimization procedures are heuristic local descent methods that can get trapped in suboptimal local minima. Empirical sensitivity to local minima is evidenced by performance variations when changing the number of integer variables updated per iteration (asynchronous vs. synchronous updates) and varying the initial configuration.

Coverage note — None was omitted; all core contributions including both SVM formulations (mi-SVM and MI-SVM), dual properties, optimization heuristics, empirical results across chemistry, vision, and text, and stated limitations are fully represented.

References

  1. 1.P. Auer. On learning from multi-instance examples: Empirical evaluation of a theoretical approach. In Proc. 14th International Conf. on Machine Learning, pages 21–29. Morgan Kaufmann, San Francisco, CA, 1997.
  2. 2.C. Carson, M. Thomas, S. Belongie, J. M. Hellerstein, and J. Malik. Blobworld: A system for region-based image indexing and retrieval. In Proceedings Third International Conference on Visual Information Systems. Springer, 1999.
  3. 3.A. Demirez and K. Bennett. Optimization approaches to semisupervised learning. In M. Ferris, O. Mangasarian, and J. Pang, editors, Applications and Algorithms of Complementarity. Kluwer Academic Publishers, Boston, 2000.
  4. 4.T. G. Dietterich, R. H. Lathrop, and T. Lozano-Perez. Solving the multiple instance problem with axis-parallel rectangles. Artificial Intelligence, 89(1-2):31–71, 1997.
  5. 5.T. Gärtner, P. A. Flach, A. Kowalczyk, and A. J. Smola. Multi-instance kernels. In Proc. 19th International Conf. on Machine Learning. Morgan Kaufmann, San Francisco, CA, 2002.
  6. 6.T. Joachims. Transductive inference for text classification using support vector machines. In Proceedings 16th International Conference on Machine Learning, pages 200–209. Morgan Kaufmann, San Francisco, CA, 1999.
  7. 7.P.M. Long and L. Tan. PAC learning axis aligned rectangles with respect to product distributions from multiple-instance examples. In Proc. Comp. Learning Theory, 1996.
  8. 8.O. Maron and T. Lozano-Pérez. A framework for multiple-instance learning. In Advances in Neural Information Processing Systems, volume 10. MIT Press, 1998.
  9. 9.O. Maron and A. L. Ratan. Multiple-instance learning for natural scene classification. In Proc. 15th International Conf. on Machine Learning, pages 341–349. Morgan Kaufmann, San Francisco, CA, 1998.
  10. 10.J. Ramon and L. De Raedt. Multi instance neural networks. In Proceedings of ICML-2000, Workshop on Attribute-Value and Relational Learning, 2000.
  11. 11.B. Schölkopf and A. Smola. Learning with Kernels. Support Vector Machines, Regularization, Optimization and Beyond. MIT Press, 2002.
  12. 12.Qi Zhang and Sally A. Goldman. EM-DD: An improved multiple-instance learning technique. In Advances in Neural Information Processing Systems, volume 14. MIT Press, 2002.

Citation

MLA
Andrews, S., et al. “Support Vector Machines for Multiple-Instance Learning”. Advances in Neural Information Processing Systems, vol. 15, 2002, https://proceedings.neurips.cc/paper_files/paper/2002/file/3e6260b81898beacda3d16db379ed329-Paper.pdf.
APA
Andrews, S., Tsochantaridis, I., & Hofmann, T. (2002). Support Vector Machines for Multiple-Instance Learning. Advances in Neural Information Processing Systems, 15. https://proceedings.neurips.cc/paper_files/paper/2002/file/3e6260b81898beacda3d16db379ed329-Paper.pdf
Chicago
Andrews, S., I. Tsochantaridis, and T. Hofmann. 2002. “Support Vector Machines for Multiple-Instance Learning”. Advances in Neural Information Processing Systems 15. https://proceedings.neurips.cc/paper_files/paper/2002/file/3e6260b81898beacda3d16db379ed329-Paper.pdf.
Harvard
Andrews, S., Tsochantaridis, I. and Hofmann, T. (2002) “Support Vector Machines for Multiple-Instance Learning”, Advances in Neural Information Processing Systems. Curran Associates, Inc. Available at: https://proceedings.neurips.cc/paper_files/paper/2002/file/3e6260b81898beacda3d16db379ed329-Paper.pdf.
Vancouver
1. Andrews S, Tsochantaridis I, Hofmann T (2002) Support Vector Machines for Multiple-Instance Learning. Advances in Neural Information Processing Systems 15:

BibTeX

@inproceedings{andrews2002support,
  title = {Support Vector Machines for Multiple-Instance Learning},
  author = {Andrews, Stuart and Tsochantaridis, Ioannis and Hofmann, Thomas},
  year = {2002},
  booktitle = {Advances in Neural Information Processing Systems},
  publisher = {Curran Associates, Inc.},
  volume = {15},
  url = {https://proceedings.neurips.cc/paper_files/paper/2002/file/3e6260b81898beacda3d16db379ed329-Paper.pdf}
}
Metadata:DOI registry

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF
License: Authors