Shapiros Model Inference System

The foundations of ILP are laid out by [Muggleton 95], and surveys [Sammut 93] [Muggleton and De Raedt 94] and a compilation [Muggleton 92] are available. Moreover, special ILP workshops exist. This present survey is organized as follows. First, in Section 3.4.1, we present Shapiro s Model Inference System, the pioneering learner of ILP. Then, in Section 3.4.2, we briefly discuss other relevant model-based systems. 

The (positive and negative) examples are presented one-by-one, and the incremental synthesis mechanism debugs its current program accordingly. 

A program (hypothesis) is a finite set of definite clauses. The program search space is ordered by a clause subsumption relation, a particular case of generalization and an extension of Plotkin s 0-subsumption. This allows intelligent pruning of the search space, and thus an improvement over basic identification-by-enumeration  

The resulting synthesis mechanism is then as follows (we here omit aspects related to the detection of potential non-termination, which may arise due to the semidecidability of subsumption checking). 

Algorithm 3-1 Incremental synthesis of logic programs from examples. 

---

Shapiro pointed out that the oracle of his Model Inference System (MIS, see Section 3.4.1) could be partly mechanized by the incorporation of constraints and partial specifications [Shapiro 82, page 79]. The idea is investigated by [Lichtenstein and Shapiro 88], whose system asks non-ground queries to an oracle. 

This Model Inference System (MIS, see Section 3.4.1) has spawned a lot of renewed interest in generalization models. For instance, [Tinkham 90] extends Shapiro s results to a second-order search space. Simultaneously, but independently, [Gegg-Harrison 89] also suggests generalization operators within a second-order logic, though for an entirely different application. 

---