Multi-instance learning with any hypothesis class

By Sivan Sabato, Naftali Tishby. 2011

49 citations recorded by the source corpus.

In the supervised learning setting termed Multiple-Instance Learning (MIL), the examples are bags of instances, and the bag label is a function of the labels of its instances. Typically, this function is the Boolean OR. The learner observes a sample of bags and the bag labels, but not the instance labels that determine the bag labels. The learner is then required to emit a classification rule for bags based on the sample. MIL has numerous applications, and many heuristic algorithms have been used successfully on this problem, each adapted to specific settings or applications. In this work we provide a unified theoretical analysis for MIL, which holds for any underlying hypothesis class, regardless of a specific application or problem domain. We show that the sample complexity of MIL is only poly-logarithmically dependent on the size of the bag, for any underlying hypothesis class. In addition, we introduce a new PAC-learning algorithm for MIL, which uses a regular supervised learning algorithm as an oracle. We prove that efficient PAC-learning for MIL can be generated from any efficient non-MIL supervised learning algorithm that handles one-sided error. The computational complexity of the resulting algorithm is only polynomially dependent on the bag size.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

Learning Theory for Distribution Regression (2014, methodology): “…MIL applications and the spate of heuristic solution techniques, there exist few theoretical results in the area (Auer, 1998; Long and Tan, 1998; Blum and Kalai, 1998; Babenko et al., 2011; Zhang et al., 2013; Sabato and Tishby, 2012) and they focus on the multi-instance classification (MIC) task.”
Distribution Kernel Methods for Multiple-Instance Learning (2013, neutral): “Other existing work describes when instance or bag concepts are learnable in the probably approximately correct (PAC) framework from MI data using instance classifiers (Auer, Long, and Srinivasan 1997; Blum and Kalai 1998; Sabato and Tishby 2012).”
Learning Neural Networks with Two Nonlinear Layers in Polynomial Time (2017, background): “Sabato and Tishby (2012) removed the independence assumption and gave sample complexity bounds for learning future bags.”
Graph Convolutional Label Noise Cleaner: Train a Plug-And-Play Action Classifier for Anomaly Detection (2019, background): “Sabato and Tishby [54] provide a theoretical analysis in which MIL tasks can be viewed as learning under one-sided label noise.”
Multiple instance learning: A survey of problem characteristics and applications (2016, background): “Sabato and Tishby [47] analyzed the of sample complexity in MIL, and they found that the statistical performance of MIL is only mildly dependent on the number of instances per bag.”