Rule induction from noisy examples
Laura Firoiu · 2000
This work is a part of an eort aimed at creating an intelligent agent embodied in a robot (Pioneer), which learns by interacting with its environment. The specic problem addressed here is rule induction from a rela-tional representation of robot experiences. The rules are expected to capture the denitions of types of expe-riences. Perceptual relations describing the robot's in-teraction with the environment are computed by hand-coded functions from the stream of values returned by the robot's sensors. In this work it is assumed that ex-periences have been correctly 1 labeled with relations denoting their types. The goal is to organize the expe-riences ' perceptual relations into rules that dene their relational labels, i.e. to learn their intensional deni-tion. Rules are desirable because they represent in a compact way the robot's interaction with the environ-ment and can be further used for planning. Rule learning is the subject of inductive logic pro-gramming (ILP) and in this work the application of the basic ILP technique of least general generalization under subsumption(lggs) is investigated. Given a set of positive examples, lggs creates a rule that logically entails each example, by selecting only what these ex-amples have in common. The problem is that in our domain the examples represent robot experiences and as such are subject to noise generated by both sensor and perceptual limitations. Specically, while the clas-si cation of examples is correct, there may be either missing or extraneous relations in the description of ex-amples. This is exactly the opposite of the usual ILP task, where examples may be missclassied, but their description is assumed correct. ILP algorithms usually deal with noise by nding a subset of the examples for which a rule can be induced. But the robot's expe-riences may yield too few or no correct examples and a classical ILP technique may be unable to generalize. The solution presented here is to replace the strong re-quirement that the induced rule entail every example in the subset with the soft requirement that the rule Copyright