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.
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.
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