Optimal Representative Distribution Margin Machine for Multi-Instance Learning

Tianxiang Luan, Tingjin Luo, Wenzhang Zhuge, Chenping HouIEEE Access 2020 · OpenReview

Introduction

Multi-instance learning (MIL) is a powerful paradigm for handling data where labels are assigned to sets of instances (bags) rather than individual points. This is particularly useful in fields like medical imaging, where a whole scan might be labeled "diseased" but only specific regions contain the pathology. While instance-based MIL approaches have gained traction, most focus on maximizing the minimum margin—the distance to the nearest point. This paper introduces the Multi-Instance Optimal Representative Distribution Margin (MIORDM) machine, which shifts the focus toward optimizing the entire statistical distribution of margins to achieve superior generalization.

The Challenge: Beyond Minimum Margins

In traditional Support Vector Machines (SVMs) applied to MIL, the goal is often to find a hyperplane that separates positive and negative instances with the largest possible gap to the nearest support vector. However, recent theoretical advances suggest that the "minimum margin" is a fragile metric. A model that considers the mean and variance of all margins—the margin distribution—tends to be more robust and performs better on unseen data.

The difficulty in MIL is that we do not know which instances in a positive bag are the "true" representatives of the label. MIORDM addresses this by combining distribution-aware optimization with an iterative selection process.

The MIORDM Framework

The MIORDM approach rests on two pillars: an objective function that clusters margins within a specific interval and an iterative loop that refines instance selection.

Conceptual diagram of the MIORDM process, showing the iterative selection of representative instances and the optimization of the margin distribution around a hyperplane.

1. Margin Distribution Optimization

Instead of a single boundary, MIORDM defines a margin interval $[1-\theta, 1+\theta]$. The model uses an $L_2$ loss function to penalize any representative instance whose margin falls outside this range. By minimizing these deviations, the algorithm effectively reduces the variance of the margins, forcing them to cluster around a target value. This "distributional" focus leads to a more stable hyperplane that is less sensitive to outliers.

2. Iterative Instance Selection

Because the representative instances are initially unknown, MIORDM employs an iterative strategy:

  • Initialization: To avoid class imbalance, each bag is initially represented by its mean instance.
  • Optimization: The model solves a convex quadratic programming problem to find the best hyperplane for the current set of representatives.
  • Refinement: The representative instances are updated based on the new hyperplane. For positive bags, the instance furthest from the boundary is selected; for negative bags, the instance closest to the boundary (the most challenging negative) is chosen.

Experimental Results

The researchers benchmarked MIORDM against state-of-the-art methods (such as MIRSVM, KISVM, and EMDD) across 30 diverse datasets, including image recognition (SIVAL), text classification (20Newsgroups), and classic MIL tasks (Musk).

  • Accuracy and Ranking: MIORDM achieved the best average rank (5.50) across all tests, consistently outperforming traditional margin-maximization models.
  • Generalization: The model proved exceptionally robust when training data was scarce. In tests using only 10% of available data, MIORDM maintained high accuracy while competing methods experienced significant performance degradation.
  • Efficiency: Despite its iterative nature, the use of dual coordinate descent makes MIORDM computationally efficient. On the "tiger" dataset, it completed training in approximately 0.35 seconds, compared to over 200 seconds for some legacy MIL algorithms.

Conclusion

By moving from "minimum margin" to "margin distribution," MIORDM provides a more robust framework for multi-instance learning. The iterative refinement of representative instances ensures that the model converges on the most informative data points, while the distributional objective ensures that the resulting decision boundary generalizes well to new, unseen bags. This approach opens new possibilities for high-accuracy classification in complex, weakly-labeled domains like bioinformatics and automated web mining.

Summary updated

Abstract

Multi-instance learning (MIL) plays an important role in many real applications, such as image recognition and text classification. The instance-based approach selects instances in each bag to train and has drawn significant attention recently. However, less work took the distribution information in the account and the margin distribution has been proven to be important to the generalization performance. In this paper, we propose an optimal representative distribution margin approach for multi-instance learning (MIORDM). The representative instances are the samples from the instance space and the distribution of them is important for us to find the best separation hyperplane. As the representative instances are selected iteratively, in each iteration, the instances will be more precise by the best hyperplane and the model will be better in the next iteration. In this way, a well-performed method can be derived with better generalization performance. Experiments compared with other types of state-of-the-art approaches on different datasets show that our method outperforms the others and achieves better generalization performance.
BibTeX
@inproceedings{luan2020optimal,
  author = {Tianxiang Luan and Tingjin Luo and Wenzhang Zhuge and Chenping Hou},
  title = {{Optimal Representative Distribution Margin Machine for Multi-Instance Learning}},
  booktitle = {IEEE Access},
  year = {2020},
  url = {https://openreview.net/forum?id=xonTkkLX9U},
}
Figure