A Layered Learning Approach to Scaling in Learning Classifier Systems for Boolean Problems

Isidro M. Alvarez, Trung B. Nguyen, Will N. Browne, Mengjie ZhangEvol. Comput 2020 · DOI · OpenReview

TL;DR

This paper introduces XCSCF, a novel approach to Learning Classifier Systems (LCSs) that leverages layered learning to tackle complex Boolean problems. By breaking down large problems into smaller, manageable subproblems and enabling knowledge transfer between them, XCSCF demonstrates significant scalability and the ability to generalize solutions to problems of varying sizes.

What Problem Does This Paper Address?

Learning Classifier Systems (LCSs) are powerful machine learning techniques inspired by cognitive science, capable of extracting knowledge and solving classification problems. However, traditional LCSs often struggle with scaling to larger, more complex problems. While approaches like using Code Fragments (CFs) have shown promise in reusing learned knowledge, they can still hit computational limits. The core challenge this paper addresses is how to enable LCSs to scale effectively to arbitrarily large problems within a domain, mimicking human learning by building complex knowledge from simpler, reusable components. This involves overcoming the "tabula rasa" problem where each new problem requires learning from scratch, and instead, enabling the system to transfer and build upon previously acquired knowledge.

Methods

The paper proposes an enhanced version of their previous system, XCSCF, incorporating a Layered Learning (LL) approach. This method breaks down complex problems into a series of simpler subproblems, forming a "curriculum." The system learns solutions to these subproblems sequentially, with each step building upon the knowledge gained from previous ones. This learned functionality is then encapsulated as Code Fragments (CFs)*, which act as reusable building blocks.

Key methodological contributions include:

  • Layered Learning Curriculum: Designing a structured sequence of subproblems for each target domain (Multiplexer, Carry-one, Majority-on, Even-parity) to guide the learning process.
  • Transfer Learning of Threshold Concepts: Enabling the system to transfer learned knowledge and functionality from simpler subproblems to more complex ones.
  • Type-fitting Code Fragments: A novel mechanism for generating CFs that ensures type compatibility between nodes, reducing the search space and preventing the creation of unworkable structures. This is inspired by Strongly-Typed Genetic Programming.
  • Experiential Toolbox: A collection of learned functions, skills, and axioms that the system can draw upon to solve problems. This toolbox grows as the system learns from new domains.
  • Bottom-up Approach: Unlike traditional top-down methods, XCSCF* learns functions and then combines them to solve more difficult problems, aligning with the LL paradigm.

Datasets

The paper evaluates XCSCF* on several benchmark Boolean problem domains:

  • Multiplexer: Specifically, n-bit Multiplexer problems, including a 135-bit version.
  • Carry-one: Problems involving binary addition carry detection.
  • Majority-on: Problems determining if the majority of bits in an input are 1.
  • Even-parity: Problems checking if the number of 1s in an input bitstring is even.

The paper does not introduce new benchmark datasets but rather uses these established problems to demonstrate the scalability and generalization capabilities of their proposed LL approach.

Key Insights and Ideas

  • Human-like Learning: The LL approach effectively mimics how humans learn complex concepts by breaking them down into smaller, manageable steps and building upon foundational knowledge.
  • Reusability is Key to Scaling: The ability to reuse learned functions and knowledge (as CFs) across subproblems and domains is crucial for overcoming the scaling limitations of traditional LCSs.
  • Curriculum Design Matters: The structured sequence of subproblems (the "curriculum") plays a vital role in guiding the learning process and ensuring that foundational knowledge is acquired before tackling more complex tasks.
  • Type-fitting Reduces Search Space: The type-fitting property for CFs significantly prunes the search space by ensuring that only compatible components are combined, leading to more efficient and robust learning.
  • Generalization from Simplicity: Even complex problems can be solved with a minimal number of general rules if the underlying logic is captured through the accumulation of learned functionalities from simpler subproblems.

Key Results

  • Successful Generalization: XCSCF* successfully learned general solutions for the Multiplexer, Carry-one, Majority-on, and Even-parity domains.
  • Scalability Demonstrated: The system was able to solve very large-scale problems, such as the 1034-bit and 8205-bit Multiplexer problems, and 100-bit Carry-one and Even-parity problems, achieving 100% accuracy without retraining.
  • Compact Solutions: The final rules generated by XCSCF* were often maximally general, with minimal specified bits in their conditions, and the learned functions formed compact, yet complex, trees.
  • Comparison to Baselines: XCSCF* outperformed traditional XCS and was comparable to XCSCFC on the 135-bit Multiplexer problem, demonstrating its effectiveness.
  • Efficient Learning: The type-fitting property of CFs helped in reducing the search space and generating workable solutions.

Limitations and Future Work

  • Human Teacher Required: The current LL approach relies on a "human teacher" to define the curriculum and the order of subproblems. The authors acknowledge that a truly autonomous system would need to discover this curriculum itself.
  • Continuous Learning: Future work aims to develop a continuous-learning system that can learn base axioms and solve problems in parallel, allowing the "toolbox" of functions and knowledge to grow organically.
  • Meta-Knowledge: The authors envision future systems that can demonstrate meta-knowledge, understanding relationships between solved problems and potentially learning curricula autonomously.
  • Real-Valued Datasets: A significant future direction is to explore whether XCS-based systems with LL can effectively handle real-valued datasets, which would require establishing appropriate datasets for LL.
  • Implicit vs. Explicit Connections: While the system learned to combine functions effectively, there's a need to further investigate how to manage the implicit connections between environment states and functions, especially when functions are nested.

Summary updated

Abstract

Learning classifier systems (LCSs) originated from cognitive-science research but migrated such that LCS became powerful classification techniques. Modern LCSs can be used to extract building blocks of knowledge to solve more difficult problems in the same or a related domain. Recent works on LCSs showed that the knowledge reuse through the adoption of Code Fragments, GP-like tree-based programs, into LCSs could provide advances in scaling. However, since solving hard problems often requires constructing high-level building blocks, which also results in an intractable search space, a limit of scaling will eventually be reached. Inspired by human problem-solving abilities, XCSCF* can reuse learned knowledge and learned functionality to scale to complex problems by transferring them from simpler problems using layered learning. However, this method was unrefined and suited to only the Multiplexer problem domain. In this paper, we propose improvements to XCSCF* to enable it to be robust across multiple problem domains. This is demonstrated on the benchmarks Multiplexer, Carry-one, Majority-on, and Even-parity domains. The required base axioms necessary for learning are proposed, methods for transfer learning in LCSs developed and learning recast as a decomposition into a series of subordinate problems. Results show that from a conventional tabula rasa, with only a vague notion of what subordinate problems might be relevant, it is possible to capture the general logic behind the tested domains, so the advanced system is capable of solving any individual n-bit Multiplexer, n-bit Carry-one, n-bit Majority-on, or n-bit Even-parity problem.
BibTeX
@article{alvarez2020layered,
  author = {Isidro M. Alvarez and Trung B. Nguyen and Will N. Browne and Mengjie Zhang},
  title = {{A Layered Learning Approach to Scaling in Learning Classifier Systems for Boolean Problems}},
  journal = {Evol. Comput.},
  year = {2020},
  doi = {10.1162/evco\_a\_00351},
}
Figure