Multiple Instance Learning for Soft Bags via Top Instances

A generalized formulation of the multiple instance learn-ing problem is considered. Under this formulation, both positive and negative bags are soft, in the sense that nega-tive bags can also contain positive instances. This reflects a problem setting commonly found in practical applications, where labeling noise appears on both positive and negative training samples. A novel bag-level representation is in-troduced, using instances that are most likely to be positive (denoted top instances), and its ability to separate soft bags, depending on their relative composition in terms of positive and negative instances, is studied. This study inspires a new large-margin algorithm for soft-bag classification, based on a latent support vector machine that efficiently explores the combinatorial space of bag compositions. Empirical eval-uation on three datasets is shown to confirm the main find-ings of the theoretical analysis and the effectiveness of the proposed soft-bag classifier. 1