Abstract
Traditional Inductive Logic Programming (ILP) often struggles with incomplete or indefinite information, particularly in non-Horn theories. This paper introduces brave induction, a novel logical framework that bridges the gap between overly restrictive explanatory induction and overly broad satisfiability-based learning. By requiring that an observation be true in at least one minimal model of a theory, brave induction provides a flexible yet semantically grounded approach to learning. We present the BRAIN algorithm for clausal theories and its extension to Answer Set Programming, demonstrating its utility across domains such as systems biology and multiagent negotiation.
Introduction
In the field of Inductive Logic Programming (ILP), the standard paradigm is explanatory induction. This approach requires that a hypothesis $H$, when combined with background knowledge $B$, logically entails an observation $O$ ($B \wedge H \models O$). While effective for Horn theories, this "cautious" requirement is often too strong for non-Horn theories—those allowing for disjunction or indefinite information. In such cases, a theory may have multiple minimal models, and explanatory induction might reject a valid hypothesis because the observation fails in a single fringe model.
Conversely, learning from satisfiability (LFS) is too weak, accepting any hypothesis consistent with the data ($B \wedge H \wedge O$ is satisfiable). This leads to an unmanageably large hypothesis space. Brave induction serves as a middle ground, establishing a hierarchy of logical induction: Explanatory < Cautious < Brave < Learning from Satisfiability.
Methods
The semantic foundation of this framework is brave inference. A hypothesis $H$ is said to cover an observation $O$ under background knowledge $B$ if $B \wedge H$ has at least one minimal model satisfying $O$. This differs from cautious and explanatory induction in how it handles the conjunction of observations and solutions.
The BRAIN Algorithm
To implement this framework, the authors developed the BRAIN (BRAve INduction) algorithm, which proceeds through four key stages:
- Computing Ground Hypotheses: Uses inverse entailment to derive specific ground clauses from $B$ and $\neg O$.
- Generalization: Employs Plotkin’s Least Generalization under Subsumption (LGS) to lift specific instances into general rules.
- Constructing Weak Forms: Uses Greatest Specialization under Implication (GSI) to identify broader, "weaker" hypotheses that still satisfy the brave coverage criteria.
- Optimization: Prunes isolated atoms and redundant clauses to ensure the output is concise and interpretable.
The framework is further extended to Nonmonotonic Logic Programming via the BRAIN$^{not}$ algorithm, which utilizes Answer Set Programming (ASP) to handle default negation.
Results and Applications
The authors provide a rigorous theoretical analysis and empirical validation of brave induction across several domains.
Theoretical Properties
- Complexity: Deciding the existence of a brave induction solution is NP-complete for clausal theories and ASP. Verifying a specific hypothesis is more complex, identified as $\Sigma_2^P$-complete in the polynomial hierarchy.
- Soundness: The BRAIN algorithm is proven sound; every hypothesis it generates is a valid solution under the brave induction semantics.
Domain-Specific Case Studies
Brave induction was applied to several real-world scenarios where traditional ILP fails:
- Systems Biology: Inferring "master reactions" within metabolic networks where information is often incomplete.
- Requirements Engineering: Completing software specifications by inducing rules from desirable and undesirable scenarios.
- Multiagent Negotiation: Generating counter-proposals by inducing the conditions under which an agent might accept a deal.
Discussion and Future Work
Brave induction is inherently nonmonotonic; adding new observations can invalidate previously held hypotheses, mirroring human belief revision. However, the framework has limitations. The BRAIN algorithm is sound but not complete, as its optimization phase may prune valid hypotheses for efficiency. Additionally, the reliance on minimal model semantics leads to an "exclusive" interpretation of disjunction, which may not be suitable for all domains. Future work will focus on incorporating possible model semantics for inclusive disjunction and developing more efficient search heuristics to improve scalability for large-scale datasets.
Summary updated