Abstract
We introduce a new approach to model selection that performs better than the standard complexity-penalization and hold-out error estimation techniques in many cases. The basic idea is to exploit the intrinsic metric structure of a hypothesis space, as determined by the natural distribution of unlabeled training patterns, and use this metric as a reference to detect whether the empirical error estimates derived from a small (labeled) training sample can be trusted in the region around an empirically optimal hypothesis. Using simple metric intuitions we develop new geometric strategies for detecting overfitting and performing robust yet responsive model selection in spaces of candidate functions. These new metric-based strategies dramatically outperform previous approaches in experimental studies of classical polynomial curve fitting. Moreover, the technique is simple, efficient, and can be applied to most function learning tasks. The only requirement is access to an auxiliary collection of unlabeled training data.
Introduction: The Fundamental Dilemma
The central challenge in machine learning is the tradeoff between representation and identification. To minimize error, we require a hypothesis class $H$ that is expressive enough to contain a good approximation of the target function. However, as the complexity of $H$ increases, it becomes increasingly difficult to identify the best hypothesis from a finite, noisy training sample. This often leads to overfitting, where a complex model achieves low training error by "memorizing" noise rather than capturing the underlying signal.
Standard approaches to this problem include complexity penalization (e.g., Structural Risk Minimization or SRM) and hold-out testing (e.g., cross-validation). While widely used, these methods can fail catastrophically when training data is sparse, as they rely on error estimates that may be highly unreliable in high-complexity regions of the hypothesis space.
Metric-Based Model Selection
This paper proposes a novel alternative: treating model selection as a geometric problem. By leveraging unlabeled data, we can estimate the "true" distance between any two hypotheses $h$ and $g$ based on their average discrepancy over the input distribution $P_X$. We define a pseudo-metric: $$d(h, g) = \left( \int (h(x) - g(x))^2 dP_X(x) \right)^{1/2}$$
The TRI and ADJ Strategies
Two primary strategies are introduced to exploit this metric structure:
- Triangle Inequality (TRI): This method uses the triangle inequality as a geometric "sanity check." If a simple hypothesis $h_i$ and a complex hypothesis $h_j$ both claim low error relative to the target, but are found to be far apart in the metric space, the complex model's claim is likely spurious. TRI selects the most complex model that remains geometrically consistent with all simpler models in the sequence.
- Adjusted Distance Estimates (ADJ): This heuristic observes the ratio between the "true" distance (calculated via unlabeled data) and the "empirical" distance (calculated on the training set) between hypotheses. This ratio acts as a local "inflation factor" to adjust the training error of complex models, providing a more realistic estimate of their generalization performance.
Experimental Results: Polynomial Curve Fitting
The effectiveness of these methods was evaluated through a series of experiments in polynomial regression, fitting functions like a step function and a squared sine wave. Training sets were deliberately kept small to highlight the risks of overfitting.
The results demonstrate that metric-based approaches provide a critical safety net. While standard methods like Generalized Cross-Validation (GCV) and SRM occasionally suffered from "catastrophic overfitting"—producing models with errors many orders of magnitude worse than the optimal—TRI and ADJ remained remarkably stable.
As shown in the table, at the 95th percentile, GCV produced an error ratio of $8.3 \times 10^{16}$, effectively failing to learn. In contrast, the ADJ method maintained a ratio of 1.20, staying very close to the best possible performance.
Conclusion
By incorporating unlabeled data to define an intrinsic geometry of the hypothesis space, we can detect when empirical error estimates become untrustworthy. The TRI and ADJ strategies offer a robust and responsive alternative to traditional model selection, particularly in data-poor regimes. While these heuristics demonstrate strong empirical performance, further theoretical grounding and exploration of alternative metric-based strategies remain key areas for future research.
Summary updated