A Semiproximal Support Vector Machine Approach for Binary Multiple Instance Learning.

We face a binary multiple instance learning (MIL) problem, whose objective is to discriminate between two kinds of point sets: positive and negative. In the MIL terminology, such sets are called bags, and the points inside each bag are called instances. Considering the case with two classes of instances (positive and negative) and inspired by a well-established instance-space support vector machine (SVM) model, we propose to extend to MIL classification the proximal SVM (PSVM) technique that has revealed very effective for supervised learning, especially in terms of computational time. In particular, our approach is based on a new instance-space model that exploits the benefits coming from both SVM (better accuracy) and PSVM (computational efficiency) paradigms. Starting from the standard MIL assumption, such a model is aimed at generating a hyperplane placed in the middle between two parallel hyperplanes: the first one is a proximal hyperplane that clusters the instances of the positive bags, while the second one constitutes a supporting hyperplane for the instances of the negative bags. Numerical results are presented on a set of MIL test data sets drawn from the literature.

Melanoma Detection by Means of Multiple Instance Learning.

We present an application to melanoma detection of a multiple instance learning (MIL) approach, whose objective, in the binary case, is to discriminate between positive and negative sets of items. In the MIL terminology these sets are called bags and the items inside the bags are called instances. Under the hypothesis that a bag is positive if at least one of its instances is positive and it is negative if all its instances are negative, the MIL paradigm fits very well with images classification, since an image (bag) is in general classified on the basis of some its subregions (instances). In this work we have applied a MIL algorithm on some clinical data constituted by color dermoscopic images, with the aim to discriminate between melanomas (positive images) and common nevi (negative images). In comparison with standard classification approaches, such as the well known support vector machine, our method performs very well in terms both of accuracy and sensitivity. In particular, using a leave-one-out validation on a data set constituted by 80 melanomas and 80 common nevi, we have obtained the following results: accuracy = 92.50%, sensitivity = 97.50% and specificity = 87.50%. Since the results appear promising, we conclude that a MIL technique could be at the basis of more sophisticated tools useful to physicians in melanoma detection.

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.

The Proximal Trajectory Algorithm in SVM Cross Validation.

We propose a bilevel cross-validation scheme for support vector machine (SVM) model selection based on the construction of the entire regularization path. Since such path is a particular case of the more general proximal trajectory concept from nonsmooth optimization, we propose for its construction an algorithm based on solving a finite number of structured linear programs. Our methodology, differently from other approaches, works directly on the primal form of SVM. Numerical results are presented on binary data sets drawn from literature.

Nonsmooth optimization techniques for semisupervised classification.

We apply nonsmooth optimization techniques to classification problems, with particular reference to the TSVM (Transductive Support Vector Machine) approach, where the considered decision function is nonconvex and nondifferentiable and then difficult to minimize. We present some numerical results obtained by running the proposed method on some standard test problems drawn from the binary classification literature.