Distance Induction in First Order Logic

This paper tackles the supervised induction of a distance from examples described as Horn clauses or constrained clauses. In opposition to syntax-driven approaches, this approach is discrimination-driven: it proceeds by defining a small set of complex discriminant hypotheses. These hypotheses serve as new concepts, used to redescribe the initial examples. Further, this redescription can be embedded into the space of natural integers, and a distance between examples thus naturally follows. This distance can be used for classification via a k-nearest-neighbor process. Experiments on the mutagenesis dataset validate the approach, in terms of predictive accuracy, computational cost, and robustness with respect to the parameters of the algorithm