Abstract
Multiple instance learning (MIL) is a branch of machine learning that attempts to learn information from bags of instances. Many real-world applications such as localized content-based image retrieval and text categorization can be viewed as MIL problems. In this paper, we propose a new graph-based semi-supervised learning approach for multiple instance learning. By defining an instance-level graph on the data, we first propose a new approach to construct an optimization framework for multiple instance semi-supervised learning, and derive an efficient way to overcome the non-convexity of MIL. We empirically show that our method outperforms state-of-the-art MIL algorithms on several real-world data sets.
Introduction
This research addresses the intersection of Multiple Instance Learning (MIL) and Semi-Supervised Learning (SSL). In MIL, data is organized into "bags," where a bag is labeled positive if it contains at least one positive instance. SSL aims to leverage a small amount of labeled data alongside a large pool of unlabeled data to improve model performance.
The core challenge in this domain is the non-convex optimization problem created by the MIL "at least one" rule. Previous semi-supervised MIL approaches, such as the MISSL algorithm, attempted to simplify this by treating entire bags as single nodes in a graph. However, this bag-level approach is often heuristic, loses granular information, and struggles when bag sizes vary significantly.
Methodology: The IL-SMIL Framework
The authors propose IL-SMIL (Instance-level Semisupervised Multiple Instance Learning), which shifts the focus from the group level to the individual instance level. The framework builds an instance-level graph where every individual instance is a node, and edges represent similarity calculated via a Gaussian kernel.
Key Innovations
- Manifold Regularization: The framework assumes that the "soft labels" of instances should vary smoothly across the graph; similar instances in feature space should likely share similar labels.
- The "Max" Loss Function: For a negative bag, the algorithm penalizes any instance not labeled negative. For a positive bag, it only imposes a penalty based on the most positive instance, perfectly mirroring the MIL definition.
- Optimization via CCCP: Because the
maxfunction is non-convex, the authors employ the Constrained Concave-Convex Procedure (CCCP). This iterative method uses a first-order Taylor expansion to approximate non-convex constraints, turning the problem into a series of convex Quadratic Programming (QP) sub-problems that are guaranteed to converge.
Experimental Evaluation
The authors evaluated IL-SMIL on three diverse real-world benchmarks: Drug Activity Prediction (Musk1 and Musk2), Localized Content-Based Image Retrieval (Elephant, Tiger, and Fox), and Text Categorization (TST1-TST10 sets from the Reuters-21578 corpus).
Key Results and Insights
- Superior Accuracy: On the Musk1 dataset, IL-SMIL achieved an AUC of 84.17%, significantly outperforming the previous semi-supervised leader, MISSL (76.61%).
- Stability through Unlabeled Data: A major finding was that supervised methods (like MI-SVM) showed high variance in performance. IL-SMIL was significantly more stable, proving that unlabeled data acts as a powerful regularizer. As shown in the learning curves, performance (AUC) generally increased and variance decreased as more unlabeled bags were added.
- Text Categorization: IL-SMIL outperformed MISSL on all test sets, with an average improvement of approximately 8%.
Conclusion
IL-SMIL demonstrates that instance-level graph construction provides a more theoretically sound and accurate foundation for semi-supervised MIL than bag-level heuristics. By preserving the intrinsic geometry of the data and effectively managing non-convexity through CCCP, the model achieves state-of-the-art performance. Future work may focus on validating the detailed instance-level labels produced by the model for more granular classification tasks.
Summary updated