Learning Non-Linearly Separable Boolean Functions With Linear Threshold Unit Trees and Madaline-Style Networks

Mehran SahamiAAAI 1993

Abstract

This paper presents a hybrid machine learning framework that integrates the structural advantages of decision trees with the representational power of neural networks. By utilizing Linear Threshold Units (LTUs) as nodes in a decision tree and subsequently transforming this tree into a three-layer Madaline-style network, the proposed method effectively learns complex, non-linearly separable boolean functions. Experimental results demonstrate that this architecture, particularly when combined with the Winnow algorithm, exhibits exceptional robustness against irrelevant input features, significantly outperforming standard Back-Propagation in high-dimensional, noisy environments.

Introduction

In the early 1990s, machine learning research was largely divided between symbolic decision trees and connectionist neural networks. While decision trees like ID3 are efficient, they often struggle with complex functions by creating overly large trees. Conversely, neural networks trained via Back-Propagation are powerful but frequently falter when faced with "irrelevant attributes"—input features that provide no signal but introduce significant noise. This paper addresses these limitations by proposing a method to learn non-linearly separable boolean functions that remains accurate even as the number of irrelevant features increases.

Methodology

The proposed approach consists of two primary phases: tree construction and network transformation.

LTU Tree Construction

Unlike standard univariate decision trees that split data based on a single feature, an LTU tree uses a multivariate linear discriminant function (a hyperplane) at each node. The construction algorithm is non-incremental: it processes a training set to find an optimal hyperplane split and recursively builds sub-trees for misclassified instances. This multivariate approach allows for smaller, more generalized tree structures.

Network Transformation and Learning

The resulting LTU tree is mechanically converted into a three-layer neural network:

  1. First Hidden Layer: Contains the LTU nodes from the tree.
  2. Second Hidden Layer: Composed of AND gates representing every unique path from the root to a leaf.
  3. Output Layer: An OR gate that aggregates the successful paths.
Figure 2: A Madaline-style neural network architecture derived from an LTU tree transformation.

For training, the author employs a Madaline-style "strengthening and weakening" strategy. Unlike the global weight updates of Back-Propagation, this rule identifies the specific node in the first layer most responsible for a misclassification and adjusts only its weights. Furthermore, the Winnow algorithm—noted for its resistance to irrelevant features—is integrated into this multi-layer architecture to enhance performance in noisy datasets.

Experimental Setup

The methodology was evaluated using synthetic datasets to ensure controlled testing environments:

  • Target Function: A non-linearly separable 5-bit boolean function (a disjunction of two $r$-of-$k$ threshold functions).
  • Noise Injection: Random irrelevant bits were added to the 5 relevant bits, creating vectors ranging from 5 to 50 total dimensions.
  • Training Scales: Models were trained on sets of 1,000 and 3,000 randomly generated instances.

Key Results

The experimental results highlight the stark contrast between the proposed hybrid models and traditional Back-Propagation.

Figures 5-8: Comparative performance of Mada-winnow, Madaline, BP network, and BP tree across varying dimensions and training set sizes.
  • Resistance to Irrelevant Features: The "Mada-winnow" approach demonstrated remarkable stability. With 3,000 training instances, it achieved a 0% error rate across all tested dimensions (up to 50), effectively ignoring up to 90% irrelevant noise.
  • Back-Propagation Degradation: Standard Back-Propagation networks began to fail rapidly once input dimensions exceeded 15, illustrating an inability to distinguish signal from noise in relatively small networks.
  • Efficiency: The tree-based origin of the network allows for efficient classification; only the nodes along a single path need to be computed, rather than the entire network.

Conclusion

The integration of LTU trees and Madaline-style networks provides a powerful tool for solving non-linear boolean problems in noisy feature spaces. The surgical nature of the Madaline update rule, combined with Winnow's noise resistance, offers a significant advantage over gradient-descent methods. Future work will focus on incremental learning algorithms and automated pruning techniques to further refine network efficiency.

Reference: Sahami, M. (1993). Learning Non-Linearly Separable Boolean Functions With Linear Threshold Unit Trees and Madaline-Style Networks. Proceedings of AAAI-93.

Summary updated

BibTeX
@inproceedings{sahami1993learning,
  author = {Mehran Sahami},
  title = {{Learning Non-Linearly Separable Boolean Functions With Linear Threshold Unit Trees and Madaline-Style Networks}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1993},
}
Figure