On multiple-instance learning of halfspaces

In multiple-instance learning the learner receives bags, i.e., sets of instances. A bag is labeled positive if it contains a positive example of the target. An Ω(dlogr) lower bound is given for the VC-dimension of bags of size r for d  -dimensional halfspaces and it is shown that the same lower bound holds for halfspaces over any large point set in general position. This lower bound improves an Ω(logr) lower bound of Sabato and Tishby, and it is sharp in order of magnitude. We also show that the hypothesis finding problem is NP-complete and formulate several open problems.

► We study the complexity of learning halfspaces, a basic learning problem, in the multi-instance model of learning. ► Give a lower bound for the VC-dimension (sharp in order of magnitude). ► The lower bound uses results on cyclic polytopes. ► Also consider both the complexity of hypothesis finding and active learning.