Abstract
In Inductive Logic Programming (ILP), the accumulation of knowledge often leads to a "curse of knowledge," where an expanding library of learned programs overwhelms the search space. We introduce Forgetgol, a learner that intentionally "forgets" redundant or irrelevant background knowledge. By pruning its knowledge base, Forgetgol scales to over 20,000 tasks—a significant advancement over traditional systems. Our results demonstrate that intentional forgetting maintains a 100% success rate and significantly reduces learning time compared to systems that retain all knowledge.
Introduction: The Curse of Knowledge
Machine learning models face a fundamental trade-off: a hypothesis space must be large enough to contain the solution but small enough to be searched efficiently. In program induction, this space is defined by Background Knowledge (BK). While multi-task learning allows an AI to grow its BK by saving previously learned programs, it often leads to "catastrophic remembering"—the inability to prune irrelevant options, causing the search space to explode and the learner to become overwhelmed.
Methodology: Intentional Forgetting
Forgetgol builds upon Meta-Interpretive Learning (MIL), specifically the Metagol system, which uses higher-order templates called metarules to construct logic programs. Forgetgol introduces a forgetting step into the multi-task learning loop using two primary methods:
- Syntactical Forgetting: This method identifies and removes functionally identical programs. It utilizes the "Tamaki and Sato unfold operation" to expand definitions and detect duplicates under different names.
- Statistical Forgetting: Based on the Blumer bound, this approach calculates the "expected cost" of keeping a predicate. It weighs the probability of reuse against the search penalty of a larger hypothesis space.
Theoretical analysis proves that finding the optimal set of predicates to forget is NP-Hard, justifying these heuristic approaches.
Experimental Evaluation
The system was evaluated on two large-scale lifelong learning domains designed to test scalability:
- Robot Planning: A robot in a $6 \times 6$ grid learns to manipulate a ball using actions like
up,down,grab, anddropacross 20,000 unique tasks. - Lego Building: A learner builds structures on a 1D board, testing its ability to handle structural complexity over thousands of tasks.
Key Results
Forgetgol demonstrates that "less is more" in program induction. By shrinking the hypothesis space, the learner requires fewer examples and less time to find correct programs.
Robot Planning Domain
In the Robot domain, Forgetgol (using syntactical forgetting) maintained a consistent success rate and significantly outperformed the "Metabias" baseline (which remembers everything) in terms of speed. By the 20,000-task mark, Forgetgol was learning programs more than twice as fast as the baseline.
Lego Building Domain
The Lego domain highlighted the risks of catastrophic remembering. While Metabias saw its performance degrade significantly after 12,000 tasks due to search paralysis, Forgetgol maintained a 100% success rate. By the 20,000-task mark, Forgetgol was learning programs over three times faster than the baseline.
Discussion and Future Work
The success of syntactical forgetting over the more complex statistical model suggests that simple redundancy removal is highly effective. The statistical approach was often too conservative, fearing the cost of relearning more than the cost of a slightly larger search space.
Future work includes exploring semantic forgetting based on logical subsumption and implementing concept drift handling, such as adding an exponential decay factor to programs that haven't been used recently. Forgetgol proves that intentional forgetting is a vital feature for lifelong learning systems, allowing them to maintain agility in the face of ever-increasing knowledge.
Summary updated