Sivan Sabato, Nathan Srebro, Naftali Tishby. Reducing Label Complexity by Learning From Bags

Natural Sciences / Computer Science / Analysis of algorithms

Submitted on: Aug 24, 2012, 19:14:31

Description: We consider a supervised learning set t ing in which the main cost of learning is the number of training labels and one can obtain a single label for a bag of examples, indicating only if a positive example exists in the bag, as in Multi-Instance Learning. We thus propose to create a training sample of bags, and to use the obtained labels to learn to classify individual examples. We provide a theoret ical analysis showing how to select the bag size as a function of the problem parameters, and prove that if the original labels are distributed unevenly, the number of required labels drops considerably when learning from bags. We demonstrate that finding a low-error separating hyperplane from bags is feasible in this setting using a simple iterative procedure similar to latent SVM. Experiments on synthetic and real data sets demonstrate the success of the approach.

The Library of Congress (USA) reference page :

To read the article posted on Intellectual Archive web site please click the link below.


© Shiny World Corp., 2011-2019. All rights reserved. To reach us please send an e-mail to