Abstract

We consider learning a distance metric in a weakly supervised setting where “bags” (or sets) of instances are labeled with “bags” of labels. A general approach is to formulate the problem as a Multiple Instance Learning (MIL) problem where the metric is learned so that the distances between instances inferred to be similar are smaller than the distances between instances inferred to be dissimilar. Classic approaches alternate the optimization over the learned metric and the assignment of similar instances. In this paper, we propose an effificient method that jointly learns the metric and the assignment of instances. In particular, our model is learned by solving an extension of kmeans for MIL problems where instances are assigned to categories depending on annotations provided at bag-level. Our learning algorithm is much faster than existing metric learning methods for MIL problems and obtains state-ofthe-art recognition performance in automated image annotation and instance classifification for face identifification