Abstract
This paper addresses the "curse of dimensionality" in model selection by introducing efficient search strategies for Information Criteria (IC). By moving away from exhaustive global searches to "comparative" and "descending" methods, the authors achieve a 4000x speedup in autoregressive modeling while maintaining—and sometimes improving—the accuracy of the selected model.
The Challenge of Model Selection
In statistical modeling, model selection involves choosing the optimal number of parameters to avoid both underfitting (missing the signal) and overfitting (modeling the noise). Researchers typically use Information Criteria, such as AIC or BIC, to find a balance between fit and simplicity by penalizing model complexity.
However, the standard Global Method requires an exhaustive search of every possible parameter combination. For a model with $m$ potential parameters, this necessitates evaluating $2^m$ models. As $m$ grows, this becomes a computational nightmare, making real-time applications or high-dimensional data analysis nearly impossible.
Search Strategies for Information Criteria
The authors compare three distinct strategies for utilizing a family of Information Criteria denoted as $\phi_\beta$:
- Global Method: An exhaustive search with $2^m$ complexity. While it is the gold standard for accuracy, it is computationally ruinous for large $m$.
- Comparative Method (Nishii): A "one-pass" approach with $m+1$ complexity. It compares the full model against versions where exactly one parameter is removed. While extremely fast, it can lack precision.
- Descending Comparative Method: An iterative, "greedy" approach with a complexity of at most $m(m+1)/2$. It starts with the full model and removes the least useful parameter one by one, recalculating at each step until the Information Criterion no longer improves.
These methods were tested on Autoregressive (AR) models, which predict signals based on past values, in both 1D (time series) and 2D (image textures) contexts.
Experimental Results and Efficiency
The methods were evaluated using synthetic 1D AR data and the Brodatz Texture Album (specifically textures d29 and d38).
As shown in the figure above, the "Descending" method effectively bridges the gap between the slow Global method and the simpler Comparative method. In 1D simulations with 10,000 samples, the success rate for identifying the correct model was nearly identical across all three methods. Crucially, the comparative methods were approximately 4000 times faster than the global search, making complex model selection feasible on standard hardware.
In 2D texture analysis, the descending method demonstrated superior parsimony. For the Brodatz texture d38, it identified a model with 38 parameters that provided a cleaner, more accurate spectral estimate than the standard comparative method, which tended to include irrelevant, noisy parameters.
Conclusion
The study demonstrates that heuristic search strategies like the Descending Comparative Method offer a powerful alternative to exhaustive searches. They provide massive efficiency gains without sacrificing the reliability of the model support identification. While currently tailored to AR models, these strategies suggest a general path forward for high-dimensional model selection in complex spectral analysis.
Summary updated