Mapping Classifier Systems Into Neural Networks

Lawrence DavisNeurIPS 1988

This 1989 paper by Lawrence Davis is a foundational piece of "bridge-building" in machine learning. At a time when the field was divided between the "connectionist" camp (neural networks) and the "evolutionary" camp (genetic algorithms and classifier systems), Davis set out to prove that these two seemingly different worlds were, in fact, functionally equivalent.

TL;DR

Davis provides a formal procedure to transform a rule-based Classifier System into a functionally identical Neural Network. By proving this isomorphism, the paper demonstrates that the differences between these two paradigms are architectural rather than fundamental, paving the way for hybrid "neuro-evolutionary" learning techniques.

The Problem: Two Distinct Species of Machine Learning?

In the late 1980s, researchers viewed Classifier Systems (CS)—which use Genetic Algorithms to evolve sets of rules—and Neural Networks (NN) as distinct species of machine learning.

Classifier systems operate on discrete bit strings and use "strength" and "bidding" to determine which rules fire. Neural networks operate on continuous weights and activation levels. Because their internal structures and learning mechanisms (evolution vs. gradient descent) looked so different, many assumed they were intrinsically different formalisms. Davis tackles a fundamental question: Are these systems actually different, or are they just different ways of describing the same underlying computational behavior?

Methodology: The Mapping Operator

The paper describes a step-by-step "mapping operator" to convert a Classifier System into an isomorphic Neural Network.

Architecture of the mapped classifier networks

This transformation relies on several key structural translations:

  1. Sub-network Construction: Each individual "classifier" (a rule) is mapped to a small sub-network consisting of match nodes, a post node, and message nodes.
  2. Weight Mapping: Davis translates the ternary logic of classifier match strings (0, 1, and # for "don't care") into specific weights. A 0 becomes a -1 weight, a 1 becomes a 1 weight, and a # becomes a 0 weight.
  3. Threshold Logic: He sets specific activation thresholds so that a "match node" only fires if the input perfectly matches the rule's criteria.
  4. Learning as Weight Rewriting: Instead of using standard backpropagation, the "learning" in this neural network is performed by a Genetic Algorithm. When the CS would normally create "children" rules via crossover or mutation, the corresponding NN "rewrites" the weights of its weakest sub-networks to match the new rules.

(Note: Datasets are not discussed in the paper. This is a theoretical proof of equivalence rather than an empirical study. The author focuses on the mathematical and procedural transformation rather than testing on a specific benchmark.)

Key Insights and Ideas

  • Isomorphism: The core "aha moment" is that if you use the same random number generator and the same initial conditions, the transformed Neural Network will behave exactly like the original Classifier System. They are functionally identical.
  • The Role of the "Don't Care" (#): Davis shows that the "don't care" symbol in genetic rules is mathematically equivalent to a zero-weight connection in a neural network—it simply nullifies the influence of that specific input bit.
  • Non-Standard Architectures: To make the mapping work, Davis notes that the resulting neural networks must be recurrent (containing feedback loops) and use threshold activation functions rather than the smooth sigmoid functions common in backpropagation.
  • Hybridization Potential: By showing that NNs can be viewed as CS, Davis suggests that we can "import" techniques from one field to the other. For example, using "strength" tracking to guide neural network learning or using genetic operators to modify network topology.

Key Results

  • Formal Proof of Equivalence: The paper successfully demonstrates that any Classifier System can be represented as a Neural Network.
  • Stochastic Winner-Take-All: The paper shows how the "bidding" process in classifier systems (where rules compete to post messages) can be mapped to a stochastic n-winners-take-all procedure in a neural network.
  • Structural Mapping: The paper provides a clear blueprint for how rule-based logic (If/Then) can be encoded directly into the weights and thresholds of a connectionist architecture.

Limitations and Future Work

  • Excessive Complexity: Davis admits the initial mapping is "excessively complex." The resulting network has many redundant nodes that could be pruned if the environment is predictable.
  • Simple Classifier Systems: The proof focuses on a relatively simple version of a classifier system. Davis notes that more advanced features—like "pass-through bits" (where parts of an input are copied directly to an output) or negation—would require much more complicated neural architectures.
  • The "Reverse" Mapping: This paper only handles half of the equivalence (CS to NN). Davis points to a companion paper for the reverse translation (NN to CS).
  • Practicality of GA for NNs: While the proof is solid, the paper acknowledges that these "classifier networks" don't use the gradient-based techniques (like backprop) that were becoming the standard for NNs at the time, leaving open the question of which learning method is more efficient for specific tasks.

Summary updated

BibTeX
@inproceedings{davis1988mapping,
  author = {Lawrence Davis},
  title = {{Mapping Classifier Systems Into Neural Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1988},
}
Figure