A Lagrangian Relaxation Approach for Binary Multiple Instance Classification
- 7 January 2019
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Neural Networks and Learning Systems
- Vol. 30 (9) , 2662-2671
Abstract
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.Keywords
This publication has 30 references indexed in Scilit:
- Computer-aided diagnosis from weak supervision: A benchmarking studyComputerized Medical Imaging and Graphics, 2015
- Convex proximal bundle methods in depth: a unified analysis for inexact oraclesMathematical Programming, 2014
- Multiple instance classification: Review, taxonomy and comparative studyArtificial Intelligence, 2013
- Multiple Instance Classification via Successive Linear ProgrammingJournal of Optimization Theory and Applications, 2007
- Tuning Strategy for the Proximity Parameter in Convex MinimizationJournal of Optimization Theory and Applications, 2006
- About Lagrangian Methods in Integer OptimizationAnnals of Operations Research, 2005
- Lagrangean relaxationTOP, 2003
- The Nature of Statistical Learning Theory1995
- Minimization Methods for Non-Differentiable Functions1985
- Lagrangean relaxation for integer programming1974