Rule Learning by Searching on Adapted Nets

LiMin FuAAAI 1991

Abstract

In the early 1990s, the field of artificial intelligence faced a significant divide between connectionist models (neural networks), which excelled at pattern recognition in noisy environments, and symbolic AI (expert systems), which offered human-readable transparency. This paper, originally published in the 1991 AAAI Proceedings, introduces the KT algorithm—a method to bridge this gap by extracting symbolic "if-then" rules from trained backpropagation networks. By intelligently pruning the search space based on weight signs, the KT algorithm achieves high coincidence rates with the original network while maintaining computational efficiency.

Introduction

Neural networks are often criticized as "black boxes" because their internal logic is distributed across a complex web of numerical weights. While effective, this lack of explainability makes them difficult to maintain and trust in critical applications. Conversely, symbolic systems are transparent but struggle with the noise and complexity of real-world data. The KT algorithm addresses this dilemma by treating a trained network as an "adapted net" from which symbolic logic can be systematically derived.

The KT Algorithm

The KT algorithm operates in two distinct phases: training and rule extraction. First, a standard neural network is trained using backpropagation. Once the network has converged, the KT algorithm is applied to extract rules that describe the network's behavior.

Key Innovations in Rule Extraction

To avoid the exponential search space inherent in checking every possible combination of inputs (which can reach $3^n$ for $n$ attributes), the KT algorithm employs several heuristic strategies:

  • Attribute Categorization: The algorithm identifies pos-atts (attributes with positive weights that confirm a concept) and neg-atts (attributes with negative weights that disconfirm it). This allows the search to focus only on relevant combinations.
  • Layer-by-Layer Extraction: For multi-layer networks, the algorithm extracts rules for each layer individually, treating hidden units as intermediate "hidden attributes."
  • The REWRITE Process: Using a method similar to backward chaining, the algorithm collapses these intermediate rules into final symbolic expressions that link raw inputs directly to the target output.
Extracted symbolic rules for a single-layer network in the wind shear domain.

Experimental Evaluation: Wind Shear Detection

The algorithm was evaluated using a dataset for wind shear detection via infrared sensors. The task involved classifying whether a "microburst"—a dangerous low-altitude wind condition—was present based on five primary features: Depth, Polarity, Maximum gradient, Slope, and Summation of gradients. These features were digitized into binary "high" or "low" values.

Performance and Efficiency

The KT algorithm demonstrated remarkable efficiency. On a SUN Sparc station, rule extraction took only 7.5 seconds, compared to the 928 seconds required to train the network. Furthermore, the algorithm was able to distill the network's logic into a sparse set of rules. Out of 243 possible rule combinations, KT identified that only 3 to 10 rules were necessary to replicate the network's performance.

Key Insights

The Impact of Sigmoid Steepness

One of the paper's most significant findings is the role of the transfer function's steepness ($\lambda$). A steeper sigmoid (e.g., $\lambda = 20$) causes the network to behave more like a discrete logic gate. This behavior significantly improves the accuracy of rule extraction, often leading to a 100% coincidence rate between the network's predictions and the extracted rules.

Coincidence rates between the neural network and extracted rules across different architectures and transfer function steepness (λ).

Hidden Layers as Feature Abstraction

Interestingly, rules extracted from multi-layer networks were often simpler and contained fewer conditions than those from single-layer networks. This suggests that hidden layers perform a form of "feature abstraction," simplifying the final logic required to reach a classification.

Conclusion and Future Work

The KT algorithm provides a robust framework for making neural networks interpretable. While it faces challenges with extremely large networks where information is spread thinly across many hidden units, it successfully transforms the "black box" into a transparent symbolic system. Future research directions include refining hidden layer analysis to further streamline rule extraction in massive architectures and addressing the "Big Rule" problem where complex, multi-variable conditions might be missed by heuristic limits.

Summary updated

BibTeX
@inproceedings{fu1991rule,
  author = {LiMin Fu},
  title = {{Rule Learning by Searching on Adapted Nets}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1991},
}
Figure