Abstract
This paper identifies and analyzes the "General Utility Problem," a phenomenon that unifies overfitting in inductive learning with the utility problem in speedup learning. Through the empirical study of "performance response curves," we demonstrate that across diverse machine learning paradigms, performance typically follows a predictable arc—rising to a peak before gradually degrading as additional knowledge is acquired.
Introduction
A common assumption in machine learning is that "more knowledge is better." However, practitioners across different subfields frequently observe performance degradation as models grow in complexity. In inductive learning, such as decision tree induction, models may begin to "memorize" noise, leading to overfitting. In speedup learning, where systems learn macro-operators to solve problems faster, the overhead of searching an increasingly large library of shortcuts can eventually outweigh the time saved.
This research argues that these are not isolated quirks of specific algorithms but manifestations of a single General Utility Problem. The central challenge lies in identifying the optimal point to cease learning to maintain peak performance.
The General Utility Problem
The core of this analysis is the performance response curve. This curve plots a measure of performance (such as classification accuracy or inverse CPU time) against the amount of learned knowledge (e.g., number of tree splits, training cycles, or macro-operators).
As illustrated in Figure 1, the typical response is characterized by a sharp initial improvement followed by a gradual decline. This suggests a universal trend where excessive knowledge acquisition becomes counterproductive.
Empirical Methodology
To validate the existence of this universal trend, four distinct learning paradigms were examined:
- Splitting Methods (ID3): Accuracy vs. the number of nodes/splits.
- Set-Covering Methods (AQ): Accuracy vs. the number of disjuncts (rules).
- Neural Networks (BackProp): Accuracy vs. the number of training cycles (epochs).
- Speedup Learning (Planner): Problem-solving speed vs. the number of learned macro-operators ("macrops").
The study utilized classic benchmarks including synthetic Boolean domains (DNF2), the UCI "Flag" domain, and medical datasets (Lymphography, Breast Cancer, Primary Tumor). Speedup learning was tested in Blocks World and Robot navigation domains.
Key Insights
The Universal Curve and Bias-Variance Tradeoff
Regardless of the underlying algorithm, the performance curves exhibit a similar topology. This is fundamentally linked to the bias-variance tradeoff. As knowledge is added, "bias" (error from oversimplification) decreases, while "variance" (error from over-sensitivity to training data) increases. The peak of the response curve represents the "sweet spot" where the total error is minimized.
The Importance of Search Order
The visibility of the utility problem depends significantly on the learning strategy. In decision tree induction, a "breadth-first" expansion of nodes reveals a clear, smooth utility curve. In contrast, "depth-first" or "best-first" strategies result in erratic performance fluctuations that can mask the underlying trend.
As shown in Figure 3, the breadth-first approach (solid line) provides the most stable representation of the performance peak, whereas other methods introduce noise that complicates the identification of the optimal stopping point.
Results and Discussion
The empirical results quantify a significant "performance gap" between the final state of a learner and its peak performance:
- Inductive Learners: Final accuracy typically ranged from 82% to 98% of the peak accuracy. For instance, ID3 on the DNF2 domain dropped to 93.6% of its peak by the conclusion of training.
- Speedup Learners: Degradation was more pronounced; the Planner's final speed in the Blocks domain was only 67.4% of its peak speed.
Statistical analysis confirmed that the difference between peak and final performance is significant in most cases, suggesting that "stopping early" is a viable and necessary optimization strategy.
Conclusion
The General Utility Problem provides a unified framework for understanding performance degradation across machine learning. While techniques like pruning help, they often fail to reach the theoretical peak identified by the response curve. Future work involves refining Model-Based Adaptive Control (MBAC) systems to fit parabolic models to these curves in real-time, though defining "knowledge complexity" consistently across paradigms remains a challenge.
Summary updated