Is inverse entailment a complete learning system?

No. It is a principle used within systems that also need representation, search restrictions and evaluation criteria.

Is Progol the same as Prolog?

No. Progol is an inductive logic programming system; Prolog is a logic programming language and execution tradition.

Are negative examples necessary for the logical equivalence?

No. The equivalence is logical. Negative training examples can nevertheless help reject overly broad candidate hypotheses.

AI Glossary / Graphs and symbolic AI / Advanced

Inverse entailment

Definition

Inverse entailment is a principle used in inductive logic programming to help find a hypothesis that, together with background knowledge, entails observed examples. It reformulates the logical relationship so that consequences of the background and a negated example can constrain candidate explanations.

What it means

Ordinary deduction starts with rules and derives consequences. Inductive learning starts with examples and searches for rules that could account for them. Several different rules may explain the same observations, so the learning problem usually has no unique inverse.

Write B for background knowledge, H for a proposed hypothesis and E for an example statement. The desired relationship is B and H entail E. In classical logic, this is equivalent to B and not E entailing not H.

That equivalence is a tool for organizing a search. It does not say that observing E proves H, and it does not remove the need to check consistency, other examples and generalization. The hypothesis remains a conjecture about the task.

How it works

A learner chooses an example and uses background knowledge to identify information relevant to explaining it. In mode-directed inverse entailment, declarations constrain the predicates, argument types and ways variables can be introduced.

The Progol approach constructs a specific clause associated with the example and searches for a suitable generalization within a constrained hypothesis space. Candidate rules are assessed against positive and negative examples, along with criteria favoring useful compact explanations.

These restrictions are part of the learning design. A useful relationship that cannot be expressed using the permitted predicates is unavailable to that search. The logical inverse relationship should therefore be distinguished from the implementation's bounded search and scoring choices.

Three practical examples

A relational-learning exercise proposes an inspection rule using known properties of equipment and examples of items requiring checks.
A research system learns rules relating objects through several predicates, rather than treating each example as an isolated feature vector.
A reviewer examines whether a learned rule explains positive examples without also covering explicitly negative examples.

Think of it this way

Think of seeing the result of a recipe and searching for recipes that could produce it, using knowledge of ingredients and cooking methods. The result narrows the possibilities but does not reveal one uniquely correct recipe.

The analogy explains the direction of inquiry. Inverse entailment uses formal logical relationships and constrained rule search, not culinary similarity or a guarantee that the proposed explanation actually caused the observation.

Worked example

Comparing two rules that explain the same positive example

Suppose background facts say that unit A is a pump and is outdoors, unit B is a pump and is indoors, and unit C is a valve and is outdoors. The positive example is NeedsCover(A); an explicitly negative example says that B does not need a cover.

Candidate H1 says every pump needs a cover. Candidate H2 says every outdoor pump needs a cover. Both combine with the background to entail NeedsCover(A), because A satisfies both sets of conditions.

However, H1 also entails NeedsCover(B), conflicting with the negative example. H2 does not produce that conflict: the background does not establish that B is outdoors. In this small test, the negative example distinguishes the two candidates.

For E = NeedsCover(A), the inverse relationship says that B together with not NeedsCover(A) entails not H1, and likewise not H2. Under either candidate rule, the known facts about A would imply the very statement being negated. This constrains hypotheses; it does not assert that A lacks a cover requirement.

H2 still has not been proved universally correct. Its failure to derive NeedsCover(C) is also not, by itself, a proof of the classical negation of that statement. Additional examples and explicit reasoning conventions matter.

Illustrative case study

The fictional Cedar Rules team explores learning symbolic inspection criteria from connected equipment records. It starts with known component types and installation conditions, then supplies labeled examples for the target decision.

Reviewers discover that one proposed rule fits a positive case but conflicts with an explicit negative case. They also notice that a potentially relevant environmental property is absent from the allowed predicate vocabulary. They distinguish a bad candidate rule from a limitation of the representation.

Cedar evaluates candidate rules on separate cases and records the background assumptions used to derive each conclusion. This fictional case illustrates review of inductive explanations, not a claim that inverse entailment automatically discovers a correct operational policy.

Common misconceptions and mistakes

Inverse entailment means reversing an implication and treating the converse as true. The logical reformulation uses negation; it does not license that fallacy.
One explained example proves a general rule. Multiple hypotheses can fit the same observation.
A missing fact is always a negative fact. That depends on the chosen semantics and cannot be silently assumed in classical logic.
The search can discover any rule imaginable. Representation choices, mode declarations and search bounds restrict the candidates.

Business use

The approach is relevant when a task benefits from explicit relational rules and background knowledge. It helps frame questions about why a candidate explanation covers one case but not another, and which assumptions support its conclusions.

Before considering practical use, inspect the vocabulary, example labels and intended treatment of missing information. Separate logical consistency with the training records from predictive usefulness on new records. A readable rule can still encode a sampling accident or an omitted condition. Review should therefore examine both the explanation structure and its performance beyond the examples used to construct it.

Check your understanding

Why is H1 rejected while H2 remains a candidate in the worked example?

Answer: H1 predicts that indoor pump B needs a cover, contradicting its explicit negative label. H2 requires an outdoor condition and does not derive that conflicting prediction from the supplied facts.

Related terms

Learn next

Add a second outdoor pump with a negative NeedsCover label. Determine what this does to H2, then propose an additional predicate that could distinguish the positive and negative cases without using their individual identifiers as the rule.

Sources

Muggleton's original paper develops inverse entailment and its mode-directed implementation: https://www.doc.ic.ac.uk/~shm/Papers/InvEnt.pdf

The author's Progol page describes the combination with constrained general-to-specific search: https://www.doc.ic.ac.uk/~shm/progol.html

The equipment facts, rules and Cedar Rules case are original examples. They illustrate hypothesis assessment, not a full trace of Progol's implementation.

Previous: Inverse Dirichlet distribution Next: Inverse filtering