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.