On Learning from Ambiguous Information
We investigate a variant of Probably Almost Correct learning model where the learner
has to learn from ambiguous information. The ambiguity is introduced by assuming that
the learner does not receive single instances with their correct labels as training data,
but that the learner receives tuples of instances where a tuple has a negative label if all
instances of the tuple should be labeled as negative and a tuple has a positive label if
at least one instance of the tuple should be labeled as positive. Thus, a positive tuple is
ambiguous since it is not known which of its instances is a positive instance.
Such ambiguous information is, for example, relevant in learning problems for drug
design. We present an improved algorithm for learning axis-parallel rectangles in this
model of ambiguous information. In the drug design domain such rectangles represent the
shapes of molecules with certain properties.