Pairwise-similarity-based instance reduction for efficient instance selection in multiple-instance learning

Unlike the traditional supervised learning, multiple-instance learning (MIL) deals with learning from bags of instances rather than individual instances. Over the last couple of years, some researchers have attempted to solve the MIL problem from the perspective of instance selection. The basic idea is selecting some instance prototypes from the training bags and then converting MIL to single-instance learning using these prototypes. However, a bag is composed of one or more instances, which often leads to high computational complexity for instance selection. In this paper, we propose a simple and general instance reduction method to speed up the instance selection process for various instance selection-based MIL (ISMIL) algorithms. We call it pairwise-similarity-based instance reduction for multiple-instance learning (MIPSIR), which is based on the pairwise similarity between instances in a bag. Instead of the original training bag, we use a pair of instances with the highest or lowest similarity value depending on the bag label within this bag for instance selection. We have applied our method to four effective ISMIL algorithms. The evaluation on three benchmark datasets demonstrates that the MIPSIR method can significantly improve the efficiency of an ISMIL algorithm while maintaining or even improving its generalization capability

First published online: 21 March 2014