The multiple-instance model was motivated by the drug activity prediction problem where each example is a possible configuration
for a molecule and each bag contains all likely configurations for the molecule. While there has been a significant amount
of theoretical and empirical research directed towards this problem, most research performed under the multiple-instance model
is for concept learning. However, binding affinity between molecules and receptors is quantitative and hence a real-valued
classification is preferable.
In this paper we initiate a theoretical study of real-valued multiple instance learning. We prove that the problem of finding
a target point consistent with a set of labeled multiple-instance examples (or bags) is NP-complete. We also prove that the
problem of learning from realvalued multiple-instance examples is as hard as learning DNF. Another contribution of our work
is in defining and studying a multiple-instance membership query (MI-MQ). We give a positive result on exactly learning the
target point for a multiple-instance problem in which the learner is provided with a MI-MQ oracle and a single adversarially
selected bag.