From propositional to relational learning

The wine tasting example is simple: The data consist of a single table and each row had only one index (the name of the person). This case is called attribute-value learning or propositional learning. The case with relational data in multiple tables and with multiple indices is more complex. In the wine example, first we need to reformulate $b \leftarrow a$ as $\mathrm{likes}(X,b)\leftarrow \mathrm{likes}(X,a)$, that is, every person $X$ who likes $a$, also likes $b$. Then, we could also have knowledge of marriages between people, that is, $\mathrm{husband}(X,Y)$ is true iff $X$ is the husband of $Y$. Now the hypotheses include clauses such as $\mathrm{likes}(X,Y)\leftarrow \mathrm{husband}(X,Z), \mathrm{likes}(Z,Y)$, that is, every husband $X$ likes all the wines $Y$ that his wife $Z$ likes. We could also know the grape and origin of each wine and make a hypothesis that anyone who likes a wine that is made of Pinot Noir likes all wines from the same origin. The hypothesis space becomes more complex, but the trellis defined by the generality relationships is still present as is.

For traversing the hypothesis space, refinement operators are used. One is the most general specialisation, $\mathrm{mgs}(\cdot)$, that corresponds to an edge downwards in the lattice of Figure 5.1. Let us define that $D>C$ means that $D$ is more specific than $C$. Hypothesis $D\in \mathrm{mgs}(C)$ iff $D>C$ and there is no hypothesis $E$ such that $D>E>C$. For example, hypothesis $\{a,b\}$ is more specific than hypothesis $\{a\}$ since everyone who likes both wines $a$ and $b$ trivially like wine $a$. The hypothesis $\{a,b\}$ is also a most general specialisation of $\{a\}$ since there is no other hypothesis that would fit between these two. Note that a hypothesis may have more than one most general specialisation. The least general generalisation, $\mathrm{lgg}(\cdot)$, is the inverse of $\mathrm{mgs}(\cdot)$. It corresponds to an edge upwards in the hypothesis lattice. $D\in \mathrm{lgg}(C)$ iff $D<C$ and there is no $E$ such that $D<E<C$.

One can generate all (possibly infinite) hypotheses in the hypothesis space if one applies the most general specialisation operation to the null hypothesis repeatedly. Two of such systems include FOIL by Quinlan (1990) and PROGOL by Muggleton (1995). Some ILP systems, such as GOLEM by Muggleton and Feng (1992) and Aleph by Srinivasan (2005), start from the most specific hypotheses and work their way upwards using the least general generalisation, and some ILP systems use both types of refinement operators. There are dozens of ILP systems listed on the web page^5.2 of Network of Excellence in Inductive Logic Programming ILPnet2.