Negative Robust Learning Results from Horn Claus Programs

Abstract

low two different approaches to hypothesis production. MIS and CLINT, for instance, identify the target at We study the learn ability of Inductive Logic t~e limit, whereas most others use polynomial heurisProgramming (ILP) concept classes with retICS for concept induction. Consequently, these sysspect to robust-learning. We first investigate tems are generally efficient learners, but, to our knowlthe class of k-Horn clauses, and show that it edge, none can be formally shown to find the target is not learnable in that model. We prove this concept in polynomial time. using a reduction on which we impose as few Simultaneously, theoretical work has allowed to estabconstraints as possible. From this proof, we lish learnability results for some subclasses of first orthen show how we can also derive negative reder Horn clauses. Early studies were undertaken in the suIts for some PAC-learnable classes. Finally, Identification in the limit model (Gold, 1967), which we end by discussing the applicational consedescribes learning as converging towards the target quences of our work and its links with other concept, in finite time but given an unbounded amount learnability studies regarding new learnabilof examples. Schapiro (Schapiro, 1983) identified a ity models for ILP. most general class learnable in this model by a consistent algorithm (MIS) and other studies have since been carried out in this framework (Banerji, 1987),