Tech Showcase: LCS on the Multiplexer Problem

Written By Ian Hamilton

At Transparent AI, we're committed to developing machine learning systems that don't just make accurate predictions, but also clearly explain their decision-making process. Today, we'd like to share a technical demonstration that showcases one of our foundational approaches to explainable AI: Learning Classifier Systems (LCS) applied to the multiplexer problem.

The Multiplexer Problem: A Test Case for Explainable AI

The multiplexer problem is a classic challenge in machine learning that exhibits a property called epistasis. But before we dive into that, let's understand what a multiplexer actually is.

A multiplexer (often abbreviated as "MUX") is essentially a selector circuit. It takes multiple input signals and, based on the values of certain control bits (address bits), selects one of the input signals to pass to the output. In the n-bit multiplexer problem:

  • The first k bits are address bits (where 2^k = n-k)

  • The remaining n-k bits are data bits

  • The output is determined by using the address bits to select which data bit to return

For example, in a 6-bit multiplexer:

  • We have 2 address bits (positions 0 and 1)

  • We have 4 data bits (positions 2, 3, 4, and 5)

  • The address bits select which data bit to return:

    • Address 00 selects data bit at position 2

    • Address 01 selects data bit at position 3

    • Address 10 selects data bit at position 4

    • Address 11 selects data bit at position 5

The Challenge of Epistasis

What makes the multiplexer problem particularly interesting is the epistasis it exhibits. Epistasis occurs when the effect of one feature depends entirely on the values of other features. In the multiplexer, the address bits determine which data bit is relevant - the other data bits are completely irrelevant to the output when they're not selected.

This creates a challenging learning environment for many traditional machine learning algorithms. Decision trees would need to create many branches to capture all possible scenarios, neural networks might struggle to identify the conditional relationships, and simple rule-based systems would require numerous specific rules.

Learning Classifier Systems: Rules That Explain Themselves

Learning Classifier Systems (LCS) are a family of rule-based machine learning algorithms that combine:

  1. A population of condition-action rules (classifiers)

  2. Reinforcement learning to evaluate rule performance

  3. Genetic algorithms to discover new, better rules

The beauty of LCS is that they produce human-readable rules that directly explain how the system makes decisions. Here's a simplified view of how an LCS works:

# Simplified LCS Pseudocode Initialize population with random rules For each training iteration:

1. Get an input state from the environment

2. Find all rules whose conditions match the state (matching set)

3. Select an action based on the matching rules

4. Receive feedback (reward) from the environment

5. Update the fitness of matching rules based on the reward

6. Periodically apply genetic algorithm:

- Select high-fitness rules as parents

- Create offspring through crossover and mutation

- Replace low-fitness rules with offspring

The Power of Wildcards: Finding General Patterns

One of the most powerful aspects of LCS is its ability to represent general patterns using wildcards (often denoted as "#"). A wildcard in a rule's condition means "this bit can be either 0 or 1" - it doesn't matter for the rule to match.

For example, in the 6-bit multiplexer problem, a rule might look like:

IF [0, 0, 1, #, #, #] THEN output = 1

This rule says: "If the address bits are 00 and the data bit at position 2 is 1, then output 1." The wildcards indicate that the values of the other data bits don't matter for this rule.

The goal of an LCS is to find rules that are:

  1. Accurate - They predict the correct output

  2. General - They use wildcards wherever possible

  3. Complete - The rule set covers all possible input scenarios

Finding the Perfect Rules with Genetic Algorithms

The genetic algorithm component of an LCS is crucial for discovering optimal rules. It works through:

  1. Selection: Choosing high-fitness rules as parents

  2. Crossover: Combining parts of two parent rules to create offspring

  3. Mutation: Randomly changing bits or introducing wildcards

  4. Replacement: Removing low-fitness rules from the population

The fitness function typically rewards both accuracy and generality, encouraging the evolution of rules that are both precise and broadly applicable.

For the 6-bit multiplexer, there are exactly 8 perfect rules - one for each combination of address bits and possible output value. Each perfect rule specifies only:

  • The 2 address bits (always specific, never wildcards)

  • The selected data bit (also specific)

  • Wildcards for all other positions

The 8 Perfect Rules for the 6-bit Multiplexer

After running our LCS implementation on the 6-bit multiplexer problem, here are the 8 perfect rules it discovered:

  1. IF [0, 0, 0, #, #, #] THEN output = 0

    • When address is 00 and data bit 0 (position 2) is 0, output 0

  2. IF [0, 0, 1, #, #, #] THEN output = 1

    • When address is 00 and data bit 0 (position 2) is 1, output 1

  3. IF [0, 1, #, 0, #, #] THEN output = 0

    • When address is 01 and data bit 1 (position 3) is 0, output 0

  4. IF [0, 1, #, 1, #, #] THEN output = 1

    • When address is 01 and data bit 1 (position 3) is 1, output 1

  5. IF [1, 0, #, #, 0, #] THEN output = 0

    • When address is 10 and data bit 2 (position 4) is 0, output 0

  6. IF [1, 0, #, #, 1, #] THEN output = 1

    • When address is 10 and data bit 2 (position 4) is 1, output 1

  7. IF [1, 1, #, #, #, 0] THEN output = 0

    • When address is 11 and data bit 3 (position 5) is 0, output 0

  8. IF [1, 1, #, #, #, 1] THEN output = 1

    • When address is 11 and data bit 3 (position 5) is 1, output 1

These rules are beautiful in their elegance and simplicity. Each one captures exactly what it needs to (the address bits and the relevant data bit) and ignores what's irrelevant (using wildcards).

Example Run: Watching the LCS Learn

When we run our LCS implementation on the 6-bit multiplexer problem, we can observe how it gradually discovers these perfect rules. Here's a sample of the output using input parameters of POPULATION SIZE = 500, MAX GENERATIONS = 10,000, CROSSOVER RATE = 0.8, MUTATION RATE = 0.2, WILDCARD RATE = 0.5:

Generation 0: Accuracy = 0.8438, Perfect Rules = 5/8

…

Generation 400: Accuracy = 0.8594, Perfect Rules = 6/8

…

Generation 1650: Accuracy = 0.8125, Perfect Rules = 7/8

…

Generation 2500: Accuracy = 0.9375, Perfect Rules = 8/8

Found all 8 perfect rules at generation 2542!

The system gradually improves its accuracy as it discovers more of the perfect rules. By generation 2542, it has found all 8 perfect rules and achieves near-perfect accuracy. The code takes about a minute to run.

Why This Matters for Explainable AI

What makes this approach particularly valuable for explainable AI is that the rules discovered by the LCS are immediately interpretable by humans. There's no need for post-hoc explanations or approximations - the rules themselves are the explanation.

For example, when presented with the input [0, 1, 1, 1, 0, 0], our system can explain its decision:

  • "I predicted output 1 because the address bits are 01, which selects data bit 1 (position 3), and that bit is 1."

  • "I used rule #4: IF [0, 1, #, 1, #, #] THEN output = 1"

This level of transparency is crucial for applications where understanding the reasoning behind decisions is as important as the decisions themselves.

Beyond the Multiplexer: Real-World Applications

While the multiplexer problem might seem abstract, the techniques demonstrated here have real-world applications in:

  • Automated medical diagnosis where doctors need to understand the reasoning

  • Financial risk assessment where regulations require explainable decisions

  • System anomaly detection where engineers need to understand what triggered an alert

  • Pattern recognition in complex data where insights about relationships are valuable

At Transparent AI, we're continuing to build on these foundations, developing more sophisticated explainable AI systems that maintain the transparency demonstrated in this simple example while scaling to handle much more complex real-world problems.

This technical demonstration is part of our commitment to advancing AI systems that are not just powerful, but also transparent, interpretable, and accountable.

Ian Hamilton
Previous

Educational Series: Hyperdimensional Computing
Next

Development Update: InsightAI Agent Proof-of-Concept