3 ms·
My research group (I'm a PhD student) is working on algorithms that learn logic programs from examples and background knowledge (also given as logic programs).
by YeGoblynQueenne 7y ago
My research group (I'm a PhD student) is working on algorithms that learn
logic programs from examples and background knowledge (also given as logic
programs). The programs our algorithms learn are first order definite datalog
programs, which means they are sets of first order Horn clauses without
negation as failure and without any functions of arity more than 1 as
arguments of literals or terms.
The reason for the restriction is completeness and efficiency. Definite
datalog programs are guaranteed to terminate (given a finite predicate and
constant signature), so the search for a hypothesis (the learned program)
cannot "go infinite" even when the target theory (what you are trying to
learn) is recursive, even when it has mutually recursive clauses. As a result
our algorithms can learn recursive programs (which, is rather important). The
space of hypotheses doubles in size when negation as failure is allowed, which
improves the efficiency of the search for hypotheses.
The problem of course is that some programs cannot be expressed in definite
datalog than can be expressed in Prolog with negation as failure and arbitrary functions
as arguments. So that's a bit of a limitation. For instance, one has to jump
through hoops to learn programs with "exceptions" (A if B except if C), say
like a program calculating leap years (which have exceptions for years
divisible by 100 and 400) or fizzbuzz.
This is not directly programming with datalog- it's machine learning of datalog
programs from data. But I think it's similar to the experience you're asking
for.
My group's algorithms:
Metagol (a meta-interpretive learner for definite datalog programs):
https://github.com/metagol/metagol https://github.com/metagol/metagol
Louise (a polynomial-time version of Metagol):
https://github.com/stassa/louise https://github.com/stassa/louise
- iamwil 7y agoSo you're building a program that can learn to write datalog programs. Is it because datalog programs are tedious enough they should be automateable? Why this particular research direction? > The space of hypotheses doubles in size when negation as failure is allowed, which improves the efficiency of the search for hypotheses. That line confused me. Shouldn't a double in the search space decrease the efficiency of the search for the hypothesis?
- srean 7y agoWhole lot easier to understand, compose and guide than DNNs. Thats a reason enough.
- YeGoblynQueenne 7y agoWell, there's that. My intuition is that ILP should appeal to computer scientists more than statistical machine learning. Unfortunately, it is not very widely known- we're a small field.
- srean 7y agoLets drink to its health/resurgence. I am an more on the applied maths camp rather than the CS camp but I feel a practical and effective merger of logic and probabilistic reasoning is sorely needed to climb out of the rut we are in. Neural Turing is all nice and dandy but it seems a very heavy handed way of expressing/learning dependencies.
- YeGoblynQueenne 7y ago>> Why this particular research direction? The work I described falls under the category of Inductive Logic Programming, a field at the intersection of machine learning and logic programming. In ILP (as in logic programming) it's typical to restrict the expressivity of first-order languages to improve efficiency and to guarantee termination. Such restrictions often apply primarily to theoretical results, while in practice there is more freedom. For example, my group's algorithms can learn normal programs in practice, but our theoretical results only guarantee termination (and so, learnability) of definite datalog programs. In general, it takes a lot of work to find a representation language that is expressive enough to allow learing of interesting and useful programs, and at the same time, restricted enough to guarantee those programs _can_ be learned. >> The space of hypotheses doubles in size when negation as failure is allowed, which improves the efficiency of the search for hypotheses I'm sorry if this was confusing. I meant that restricting hypotheses to definite programs improves efficiency compared to allowing normal programs (with negation as failure). The reason is that, if negation as failure is allowed, in the worst case, an algorithm must consider both a literal and its negation for inclusion in a clause, which doubles the cost of search for a hypothesis.