Robust and discriminative distance for Multi-Instance Learning

Multi-Instance Learning (MIL) is an emerging topic in machine learning, which has broad applications in computer vision. For example, by considering video classification as a MIL problem where we only need labeled video clips (such as tagged online videos) but not labeled video frames, one can lower down the labeling cost, which is typically very expensive. We propose a novel class specific distance Metrics enhanced Class-to-Bag distance (M-C2B) method to learn a robust and discriminative distance for multi-instance data, which employs the not-squared ℓ
₂
-norm distance to address the most difficult challenge in MIL, i.e., the outlier instances that abound in multi-instance data by nature. As a result, the formulated objective ends up to be a simultaneous ℓ
_{2, 1}
-norm minimization and maximization (minmax) problem, which is very hard to solve in general due to the non-smoothness of the ℓ
_{2, 1}
-norm. We thus present an efficient iterative algorithm to solve the general ℓ
_{2, 1}
-norm minmax problem with rigorously proved convergence. To the best of our knowledge, we are the first to solve a general ℓ
_{2, 1}
-norm minmax problem in literature. We have conducted extensive experiments to evaluate various aspects of the proposed method, in which promising results validate our new method in cost-effective video classification.