A Lagrangian Relaxation Approach for Binary Multiple Instance Classification

Annabella Astorino

doi:10.1109/TNNLS.2018.2885852

A Lagrangian Relaxation Approach for Binary Multiple Instance Classification

2019-09-01

22

PRE

AI

DOI：10.1109/TNNLS.2018.2885852

Original

Original request for help

Save

Abstract

En 中文

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 hag 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:

Lagrangian relaxation

machine learning

multiple instance learning (MIL)

nonsmooth optimization

A Lagrangian Relaxation Approach for Binary Multiple Instance Classification

Abstract

AI Summary

Journal

Organization