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 abstract of this article will be published in the August 2012 issue of "Intellectual Archive Bulletin", ISSN 1929-1329.

The Library and Archives Canada reference page:

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


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