Thumbnail
Access Restriction
Open

Author Sabato, Sivan ♦ Srebro, Nathan ♦ Tish, Naftali
Source CiteSeerX
Content type Text
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Supervised Learning Setting ♦ Label Complexity ♦ Real Data Set ♦ Individual Example ♦ Theoretical Analysis ♦ Multi-instance Learning ♦ Training Sample ♦ Bag Size ♦ Simple Iterative Procedure ♦ Required Label Drop ♦ Single Label ♦ Latent Svm ♦ Positive Example Exists ♦ Problem Parameter ♦ Training Label ♦ Main Cost ♦ Original Label ♦ Obtained Label
Description We consider a supervised learning setting 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 theoretical 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 lowerror 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. 1
International Conference on Artificial Intelligence and Statistics (AISTATS), 9:685–692
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2010-01-01