@article{blum1998a,
author = {Blum, Avrim and Kalai, Adam Tauman},
title = {A Note on Learning from Multiple-Instance Examples},
year = {1998},
month = {January},
abstract = {We describe a simple reduction from the problem of PAC-learning from multiple-instance examples to that of PAC-learning with one-sided random classification noise. Thus, all concept classes learnable with one-sided noise, which includes all concepts learnable in the usual 2-sided random noise model plus others such as the parity function, are learnable from multiple-instance examples. We also describe a more efficient (and somewhat technically more involved) reduction to the Statistical-Query model that results in a polynomial-time algorithm for learning axis-parallel rectangles with sample complexity Õ(d2r/ε2) , saving roughly a factor of r over the results of Auer et al. (1997).},
publisher = {Kluwer Academic Publishers},
url = {http://approjects.co.za/?big=en-us/research/publication/note-learning-multiple-instance-examples/},
pages = {23-29},
journal = {Machine Learning},
volume = {30},
number = {1},
}