Introduction
In the field of automated classifier induction, researchers often face a trade-off between interpretability and performance. Decision trees, such as C4.5, offer high transparency but suffer from data fragmentation as they recursively partition the training set. Conversely, Artificial Neural Networks (ANNs) utilize the entire dataset globally but are plagued by local minima and uninterpretable "black box" hidden layers. Support Vector Machines (SVMs) provide high accuracy and global convergence but rely on complex kernel functions that are difficult for humans to audit.
This paper introduces CLEF (Constructive Learning of Features), a novel algorithm designed to bridge this gap. By reviving the classic $\Phi$-machine architecture and modernizing it with an automated feature construction process, CLEF aims to provide the accuracy of an SVM with the interpretability of a decision tree.
The CLEF Algorithm
CLEF operates as a $\Phi$-machine—a linear classifier that works on non-linear transformations of input data. Unlike traditional $\Phi$-machines that require hand-crafted features, CLEF constructs its own features directly from the training data through a four-step process:
- Boolean Transformation: All input variables are converted into Boolean features.
- Incremental Growth: The model begins with a single general feature and updates weights using a fractional error correction rule.
- Feature Splitting: When weights stabilize without achieving perfect separation, CLEF identifies the feature contributing most to the error and "splits" it into more specific logical conjunctions.
- Global Training: Unlike decision trees, CLEF updates its weights based on the entire dataset at every step, avoiding the pitfalls of recursive partitioning.
Theoretical Foundations
A key innovation of CLEF is its mathematical guarantee of linear independence. By ensuring that every newly constructed feature is linearly independent of existing ones, the algorithm creates an error surface with a single global minimum. This allows CLEF to avoid the local minima issues common in neural network training.
The splitting mechanism ensures that if the training data is separable within the generated feature space, CLEF is guaranteed to find that separation. This theoretical robustness provides a level of reliability similar to SVMs while maintaining a much simpler underlying model structure.
Empirical Performance
The authors evaluated CLEF across 20 standard classification tasks from the UCI Machine Learning Repository, including datasets like breast-cancer, iris, and wine. The results demonstrate that CLEF is a highly competitive alternative to established methods:
- Accuracy: CLEF achieved an average accuracy of 76.25%, slightly outperforming SVMs (75.81%) and significantly exceeding C4.5 (70.03%).
- Efficiency: In terms of inference speed, CLEF was approximately 10x faster than neural networks and 2x faster than SVMs. However, training CLEF is computationally intensive, typically taking 10 to 100 times longer than C4.5.
- Interpretability: The resulting classifiers are compact, often consisting of only a few dozen features. These features take the form of simple "checklist" rules (e.g., If condition A is true, add X to the score), making them highly transparent for human experts.
Conclusion and Future Work
CLEF demonstrates that it is possible to achieve state-of-the-art classification accuracy without sacrificing interpretability or risking local minima. While the current implementation lacks an explicit mechanism to prevent overfitting, future work aims to integrate structural risk minimization principles—the core theory behind SVMs—into the feature construction process. Additionally, the authors suggest that CLEF's architecture could be further refined by applying insights from modern ensemble learning methods.
Summary updated