Learning First Order Rules from Ambiguous Examples

We investigate here relational concept learning from examples when we only have a partial information regarding examples: each such example is qualified as ambiguous as we only know a set of its possible complete descriptions. A typical such situation arises in rule learning when truth values of some atoms are missing in the example description while we benefit from background knowledge. We first give a sample complexity result for learning from ambiguous examples, then we propose a framework for relational rule learning from ambiguous examples and describe the learning system LEAR. Finally we discuss various experiments in which we observe how LEAR copes with increasing degrees of incompleteness.