Abstract
Perceptron Trees combine the structural flexibility of decision trees with the mathematical efficiency of Linear Threshold Units (LTUs). By nesting LTUs at the leaves of a decision tree and splitting nodes only when linear separability fails, this hybrid approach creates a "complete" representation that is often significantly more compact than using either method alone. This paper presents a case study on a non-linearly separable boolean function to demonstrate the advantages of this hybrid representation.
Introduction
Every machine learning formalism comes with an inherent representational bias. Decision Trees (like ID3) are biased toward concepts expressible as boolean combinations of features but struggle with numerical relationships or high-dimensional feature interactions, often resulting in massive, unreadable trees. Conversely, Linear Threshold Units (Perceptrons) are computationally efficient but strictly limited to linearly separable concepts. Paul Utgoff introduces the Perceptron Tree to bridge this gap, allowing a learning system to autonomously choose the best representation for different sub-parts of a concept.
Methods
The Perceptron Tree is a hybrid structure where internal nodes are standard decision nodes, but leaves are Linear Threshold Units. The learning process is incremental:
- Initialization: Start with a single LTU and adjust weights using standard error correction.
- Splitting Heuristic: Monitor for non-linear separability using a heuristic based on the Perceptron Cycling Theorem. If weights fail to converge after a threshold number of updates (specifically, more updates than there are features), a split is triggered.
- Refinement: Replace the failing LTU with a decision node chosen via an information-theoretic criterion (e.g., ID3's gain metric) and initialize new LTUs at the resulting leaves.
Results
The approach was evaluated on the synthetic boolean concept $(a \lor b) \oplus (c \land d)$. This 4-variable problem is intentionally non-linearly separable due to the XOR operator.
As shown in the figure above, the hybrid model is remarkably compact, requiring only 2 decision nodes and 3 LTU leaves. In contrast, a standard ID3 decision tree for the same problem is significantly more complex, requiring 8 decision nodes and 9 terminal nodes.
The Perceptron Tree achieved 100% accuracy, demonstrating that the "when to split" heuristic effectively navigates the transition from linear to tree-based representation.
Discussion
Perceptron Trees offer a "complete" representation, as they can eventually degrade into standard decision trees if necessary. However, the current splitting heuristic is conservative and may trigger splits prematurely. Additionally, while LTUs reduce tree depth, they require all feature values for prediction, which may be costly in some domains. Future work involves refining the splitting criteria and exploring other hybrid learner architectures.
Summary updated