ON LEARNING FROM AMBIGUOUS INFORMATION

Abstract

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.