Good morning everybody.

So inductive logic programming, the thing we started the day before yesterday.

The basic idea is that we use Prolog to represent both our data in the form of classifications

as well as various kinds of background knowledge that we have about the kind of data that we're interested in.

And then the goal of an ILP system is to find a Prolog clause or equivalently a program or equivalently a logical formula

that specifies the specific predicate which we're interested in.

The running example that we're going to use, which I'm immediately going to freeze again, because I can never remember any of these people or how they're related.

How do I freeze this? Ah, there we go. Yup, that works.

So what we're looking for is this kind of family tree that gives us a whole bunch of data, i.e. every pair of persons is basically a data point.

So we have relations like Philip is the father of Charles, who has Charles over there.

And we have the mother predicate and the married predicate and the unary male predicate and the unary female predicate and all of that.

And what we're looking for is basically the description of what it means to be a grandparent, i.e. every pair of two persons such that one of them is a grandparent of the other

would be a positive example in our data set and every other pair would be a negative one.

In this case, we have 12 positives and 388 negatives.

And now an ILP system would need to find the formula that specifies what it means to be a grandparent inductively based on that data.

By and large, generally note that something like decision trees doesn't get us anywhere in this particular example because we're now looking for relations on the data, i.e. how the individual elements in our training data set are related to each other rather than just plain classifications of them in and of itself.

Which means decision trees are not applicable and basically all of the other systems that we've looked at so far also are not really applicable.

There are two ways to implement such a system.

The first one is top down inductive learning.

The second one is inverse resolution.

Starting with top down inductive learning, the basic idea is that we start with a program that basically always returns true, which is to say we start with a clause that as a head has the relation we're interested in and has nobody whatsoever that immediately classifies all of our positive examples correctly and immediately misclassifies all of our negative examples.

So the goal afterwards is that we successively extend our hypothesis in the form of such a clause by adding individual clauses to that rule until we found one that ideally exhaustively classifies all of our examples correctly.

There is an algorithm for that which buries most of its complexity in these two functions down here.

Extend example where it doesn't really tell us how to do that because that is the complicated part.

And new literals, which again is one of those complicated cases where it therefore doesn't really tell us how to do that in detail.

The core problem is that we basically need to solve a giant search problem over all possible clauses that we could add to the current rule, which may explode massively if we're not very careful with how to do that.

Here's a bunch of those criteria that we need to take care of.

Every time we extend our rule by a new clause predicate like for example father XZ, we have a whole bunch of choices which we can make, i.e. which predicate do we even consider?

Do we consider it to be positive or negative, i.e. as it is or in the negated form?

Likely that predicate will take some kinds of variables. What do we put in there? Do we put constants in there? Do we put variables in there?

So we have lots of choices that we need to navigate somehow. And that makes the whole problem of course relatively complicated.

But it is doable and most ILP systems do use this kind of top-down approach or at least like Aleph does, which is like this classic ILP system written in Prologue people use in practice still.

There is a whole bunch of modern ones as well, but that's like the classic one and that uses this kind of top-down approach.

So it does work, we just need to be somewhat smart about it.

One way to be smart about it is to introduce type information which Prologue usually does not have, but in the case where we have relations that deal with particular kinds of variables or constants where we know, for example, that the parent relation only makes sense if the inputs are actual people and not numbers.

Then we can inform the ILP system of that. So we basically annotate this particular attribute with the additional information that by the way the first argument is a person and the second argument also needs to be a person.

And that allows it to rule out lots of clauses which it may otherwise consider during research to find the rule that we're interested in.

Another method which is not exactly listed here is the idea of modes.

Since in Prologue we usually represent things like functions as predicates.

So if I conceptually want to have a function f that takes some argument x and then returns some other argument y, the way that we would implement that in Prologue is as a predicate onto arguments x and y.

Now if I want to generate a rule that somehow explains some kind of predicate and that rule may make use of these kinds of function like predicates, then we can basically tell Prologue that this particular predicate is in fact a function where this is the input labeled as plus and this would be the output labeled as a negative, as a minus.

That is in the ILP community that is called like mode attributes.

The advantage of that is if the ILP system now tries to generate clauses, it knows it will never look if we have a constant somewhere in scope, it will never look for something where this constant is a constant.

Because in most cases that basically does not make sense.

You're never interested in if I want to learn some function that does something arithmetically.

For example, I'm never interested in whether there are two numbers such that they added the equal to the value of the constant.

Usually that doesn't make sense.

So these attributes like this is an input, this is an output, also allow it to like exclude a whole bunch of predicate applications it would otherwise consider during the run of such a program.

Does that make sense?

Some confused looks.