TLDR: A new research paper introduces Poker, a novel Inductive Logic Programming (ILP) system that addresses the traditional ILP challenge of requiring manually crafted background theories and negative examples. Poker achieves this by automatically generating and labeling new positive and negative examples during learning. It utilizes a general background theory called Second-Order Definite Normal Forms (SONFs), eliminating the need for task-specific knowledge. Experiments show that Poker’s accuracy significantly improves with the number of self-generated examples, effectively preventing over-generalization that plagues other systems when negative examples are scarce.
Inductive Logic Programming (ILP) is a powerful approach in artificial intelligence that can learn complex rules, known as logic programs, from a few examples. Systems like Meta-Interpretive Learning (MIL) are particularly good at this, even learning recursive programs with new, invented concepts that generalize well to new situations. However, a significant hurdle for ILP has always been its reliance on human experts. These experts typically need to provide a specific ‘background theory’ – a set of pre-existing knowledge – and carefully selected ‘negative examples’ to guide the learning process and prevent the system from making overly broad generalizations.
What if this expert knowledge isn’t readily available? This is the core question addressed by a new research paper titled “Self-Supervised Inductive Logic Programming”. The paper introduces a novel approach called Self-Supervised ILP and presents a new MIL algorithm implemented in a system named Poker.
Introducing Poker: Learning Without Manual Supervision
Poker is designed to alleviate the burden on users by being “self-supervised.” This means it can learn effectively from a combination of a few labeled positive examples (what it *should* accept) and a larger number of unlabelled examples (data where the correct outcome is unknown). Crucially, Poker automatically generates and labels new positive and negative examples during the learning process. This innovative capability allows Poker to learn without needing a background theory specifically tailored to each learning task, and without over-generalizing, because it can create its own negative examples.
The intuition behind Poker’s algorithm is based on detecting contradictions. If a hypothesis (a learned logic program) accepts two examples, but one is assumed to be positive and the other negative, Poker identifies this as a contradiction. It then refines its set of hypotheses and re-labels examples to resolve these contradictions, iteratively improving its understanding.
A General Background Theory: Second-Order Definite Normal Forms (SONFs)
Instead of problem-specific background theories, Poker utilizes a maximally general higher-order background theory called a Second-Order Definite Normal Form (SONF). The paper defines SONFs as a set of constrained ‘metarules’ – high-level rules that guide the construction of logic programs. These SONFs are designed to be general enough to learn any logic program within a certain class, removing the need for manual, task-specific adjustments. The authors illustrate this with two SONFs: one for Context-Free Grammars (CFLs) and another for L-System grammars.
Also Read:
- Bridging Open and Closed Worlds: A New Approach to Automated Planning with Ontologies
- Unpacking the Nuances of AI Explanations: Facets and Diversity in Abductive Reasoning
Experimental Validation
The researchers conducted experiments comparing Poker to Louise, a state-of-the-art MIL system. They tested Poker’s performance when learning grammars for Context-Free Languages and L-Systems, varying the number of automatically generated examples. The results were compelling:
- For L-Systems, Poker’s generative accuracy improved, and the size of its learned hypotheses decreased as the number of automatically generated examples increased. In contrast, Louise, lacking the ability to generate negative examples, showed increasing over-generalization.
- For Binary CFLs, Poker initially over-generalized when no negative examples were generated. However, as the number of automatically generated examples increased, both its True Positive Rate (correctly identifying positive examples) and True Negative Rate (correctly rejecting negative examples) improved significantly, indicating that Poker learned a correct hypothesis and labeling. Louise consistently over-generalized in these experiments.
These findings demonstrate that Poker’s ability to automatically generate negative examples is key to its improved performance and its capacity to use a general background theory without over-generalizing. This frees the user from the laborious task of manually selecting background theories and negative examples for each new learning target.
The paper represents a significant step towards making Inductive Logic Programming more practical and widely applicable by reducing its reliance on extensive human expertise. For more details, you can read the full research paper here.
