Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR00-066 | 14th July 2000 00:00

On Learning from Ambiguous Information


Authors: Peter Auer
Publication: 12th September 2000 20:04
Downloads: 1189


We investigate a variant of the 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.

ISSN 1433-8092 | Imprint