A Lagrangian Relaxation Approach for Binary Multiple Instance Classification

In the standard classification problems, the objective is to categorize points into different classes. Multiple instance learning (MIL), instead, is aimed at classifying bags of points, each point being an instance. The main peculiarity of a MIL problem is that, in the learning phase, only the label of each bag is known whereas the labels of the instances are unknown. We discuss an instance-level learning approach for a binary MIL classification problem characterized by two classes of instances, positive and negative, respectively. In such a problem, a negative bag is constituted only by negative instances, while a bag is positive if it contains at least one positive instance. We start from a mixed integer nonlinear optimization model drawn from the literature and the main result we obtain is to prove that a Lagrangian relaxation approach, equipped with a dual ascent scheme, allows us to obtain an optimal solution of the original problem. The relaxed problem is tackled by means of a block coordinate descent (BCD) algorithm. We provide, finally, the results of our implementation on some benchmark data sets.