Source-linked AI summary
Multi-Instance Learning by Treating Instances As Non-I.I.D. Samples
Zhi-Hua Zhou, Yu-Yin Sun, Yu-Feng Li
TL;DR
Multi-instance learning traditionally treats the unlabeled instances within labeled bags as i.i.d., despite relations among instances that may carry structure. The paper proposes graph-based methods that process each bag as a whole using node and edge information, and experiments find them highly competitive with state-of-the-art methods. Their effectiveness depends on computational scale and on whether the captured structure is meaningful.
Problem
Previous multi-instance learning methods typically treat instances within a bag as i.i.d., although those instances are rarely independent and their relations may convey important information.
Method
The paper proposes MIGraph and miGraph, which represent each bag as a graph or affinity-based graph and use kernels incorporating node, edge, or clique information.
Results
The proposed methods achieve performances highly competitive with state-of-the-art methods across several multi-instance classification and regression tasks.
Takeaways & Limitations
Modeling relations among instances can provide an effective non-i.i.d. alternative while retaining the ability to handle i.i.d. samples through an identity matrix.
Takeaways & Limitations
MIGraph has complexity O(n_i n_j + m_i m_j), making it difficult to execute for bags containing many instances.
Abstract
from arXiv · showhide
Multi-instance learning attempts to learn from a training set consisting of labeled bags each containing many unlabeled instances. Previous studies typically treat the instances in the bags as independently and identically distributed. However, the instances in a bag are rarely independent, and therefore a better performance can be expected if the instances are treated in an non-i.i.d. way that exploits the relations among instances. In this paper, we propose a simple yet effective multi-instance learning method, which regards each bag as a graph and uses a specific kernel to distinguish the graphs by considering the features of the nodes as well as the features of the edges that convey some relations among instances. The effectiveness of the proposed method is validated by experiments.
1 Introduction
Multi-instance learning represents each example as a labeled bag of unlabeled instances, capturing structure that flat representations may miss. This paper addresses the limits of treating bag instances as i.i.d. by proposing methods that exploit their relations.
- Each training example is a bag whose label is known while the labels of its instances are unknown.
- Representing structured objects as bags of instances can capture more information than a flat single-instance representation.For images, partitioning an object into meaningful regions preserves partition information that may help learning.
- Using multi-instance representation is unnecessary when a single-instance representation already suffices.
- Previous methods typically treated bag instances as i.i.d., neglecting potentially informative relations among instances from the same object.The paper motivates treating correlated image parts as related samples rather than unrelated ones.
- The paper proposes two non-i.i.d. multi-instance methods that process each bag as a whole and achieve performance highly competitive with state-of-the-art methods.
2 Related Work
Related work spans many multi-instance learning algorithms and extensions beyond standard classification. The paper positions its approach as a graph-based solution for modeling relations among instances in propositional data.
- Prior multi-instance learning methods include density estimation, nearest-neighbor, tree, neural-network, rule-learning, ensemble, and logistic-regression approaches.
- Kernel-based work includes MI-Kernel, mi-SVM, MI-SVM, MissSVM, and PPMM, which use different bag or instance representations.These methods respectively involve set kernels, margin constraints, partially labeled instances, or aggregate mixture-model posteriors.
- Multi-instance learning has also been extended to regression, generalized, semi-supervised, active, and multi-label settings.
- This paper focuses mainly on standard multi-instance learning and proposes handling bags as graphs for propositional data.The authors distinguish this from earlier work using multi-instance learning to handle relational data where each instance is itself a graph.
3 The Proposed Methods
The proposed methods represent each multi-instance bag as a whole while modeling relations among its instances. MIGraph uses explicit graphs and a node-and-edge graph kernel, whereas miGraph uses affinity matrices and an efficient soft clique-based kernel.
- MIGraph: MIGraph explicitly maps every bag to an undirected graph and uses a graph kernel combining node and edge information.The node kernel captures instance features, while the edge kernel captures relations conveyed by graph edges.
- MIGraph: MIGraph constructs an ϵ-graph whose nodes are instances and whose weighted edges represent affinity between sufficiently close instances.An edge is added when pairwise distance is below threshold ϵ; its weight expresses node affinity.
- MIGraph: MIGraph defines edge features from normalized endpoint degrees and normalized edge weights, making edges similar when their endpoint properties are similar.The edge feature vector is [d_u, p_u, d_v, p_v]′, with degree and affinity components defined from the graph structure.
- MIGraph: The MIGraph graph kernel is positive definite, applies to arbitrary graphs, and has complexity O(n_i n_j + m_i m_j).Its complexity is dominated by the number of edges, which can make MIGraph difficult to execute for bags containing many instances.
- miGraph: miGraph derives an affinity matrix for each bag and defines an efficient kernel that incorporates clique information without explicitly finding cliques.The kernel acts as a soft version of a clique-based graph kernel and adapts instance weights according to their relations.
4 Experiments
The experiments evaluate MIGraph and miGraph across benchmark classification, image and text categorization, and regression tasks using cross-validation or leave-one-out testing. Results show strong performance, with method choice depending partly on bag size and a computational limitation for MIGraph on large bags.
- Benchmark Tasks: Five benchmark data sets were evaluated with ten repetitions of 10-fold cross-validation against MI-Kernel and other multi-instance methods.The benchmark set comprised Musk1, Musk2, Elephant, Fox, and Tiger.
- Benchmark Tasks: miGraph and MIGraph were respectively the best and second-best methods on Musk2, Elephant, and Fox, while miGraph significantly outperformed MI-Kernel except on Musk2.On Musk1, both proposed methods were surpassed only by PPMM among the reported methods.
- Image Categorization: On image categorization, MIGraph was the best-performing method, while both proposed methods were highly competitive with state-of-the-art alternatives.The authors characterize MIGraph as preferable for bags with few instances and miGraph as preferable for bags with many instances.
- Image Categorization: The proposed methods exceeded MI-Kernel on most 1000-Image categories, except African and Dinosaurs, where the simple graph schemes may not capture the relevant structure.The paper notes that incorrect structural information can be worse than treating instances as i.i.d. samples.
- Text Categorization: MIGraph did not return results in a reasonable time for the text categorization experiments, reflecting its computational difficulty on bags with many instances.Its graph-kernel complexity is O(n_i n_j + m_i m_j), with the edge term dominating for densely connected bags.
- Text Categorization: On all twenty text categorization data sets, miGraph was significantly better than MI-Kernel under ten repetitions of 10-fold cross-validation.The reported win/tie/lose counts were 10/0/0 on 16 data sets, 9/0/1 on two, and 7/2/1 on two.
- Multi-Instance Regression: Leave-one-out experiments found that MIGraph and miGraph also worked well on four multi-instance regression data sets.The regression results were reported using squared loss alongside results from several previously published methods.
5 Conclusion
The paper addresses the limitations of i.i.d. assumptions in multi-instance learning by modeling relations among instances. Its methods are effective across classification and regression tasks and motivate broader relational extensions.
- The proposed methods treat instances within each bag as non-i.i.d. because their relations may convey important information.
- Experiments find the methods simple and highly competitive with the best-performing methods on several classification and regression tasks.
- The methods can also handle i.i.d. samples by using an identity matrix.
- The authors identify better graph kernels, graph edit distance, and metric learning as future ways to capture more useful bag structure.
- The approach suggests incorporating instance-relational mechanisms into other multi-instance settings, including generalized, semi-supervised, active, and multi-label learning.