Using similarity between paired instances to improve multiple-instance learning via embedded instance selection

Multiple-instance Learning (MIL) copes with classification of sets of instances named bags, as opposed to the traditional view that aims at learning from single instances. Recently, several instance selection-based MIL algorithms have been presented to tackle the MIL problem. Multiple-Instance Learning via Embedded Instance Selection (MILES) is so far the most effective one among them, at least in our experiments. However, MILES regards all instances in the training set as initial instance prototypes, which leads to high complexity for both feature mapping and classifier learning. In this paper, we try to address this issue based on the similarity between paired instances within a bag. The main idea is choosing a pair of instances with the lowest similarity value from each bag and using all such pairs of instances as initial instance prototypes that are applied to MILES instead of the original set of initial instance prototypes. The evaluation on two benchmark datasets demonstrates that our approach can significantly improve the efficiency of MILES while maintaining or even strengthening its effectivenss.