TL;DR
This paper explores three methods for choosing the best probability model for data: statistical criteria (like AIC/BIC), maximizing posterior probability, and a novel "effectiveness ratio" that balances accuracy with computational cost. The authors show these methods can be unified as maximizing a penalized likelihood and highlight the effectiveness ratio's utility, especially in AI, for its explicit cost consideration and less strict assumptions.
What Problem Does This Paper Address?
Selecting the "best" probability model for a given dataset is a fundamental challenge in statistics and machine learning. This isn't just about finding a model that fits the data well, but also about choosing a model that is parsimonious and computationally efficient. The paper focuses on a specific scenario: choosing among a sequence of nested models, where each subsequent model is more general (e.g., a Gaussian mixture with more components). Traditional methods like AIC and BIC, while popular, have limitations, especially when models aren't perfectly representative of reality or when computational cost is a primary concern. The authors aim to provide a more general and practical framework for model selection that addresses these shortcomings.
Methods
The paper compares three approaches:
- Statistical Criteria (AIC/BIC): These are large-sample criteria that maximize the log-likelihood of the data, penalized by the number of model parameters. AIC and BIC are specific instances of this, differing in their penalty term.
- Maximum A Posteriori (MAP) Approach: This involves defining a prior probability distribution over the candidate models and then selecting the model with the highest posterior probability after observing the data. The paper shows that with specific prior distributions (like the geometric distribution), this approach can be equivalent to the statistical criteria approach.
- Effectiveness Ratio Approach: This is the paper's novel contribution. It seeks to maximize a ratio of the model's accuracy (likelihood) to its computational cost. This approach is particularly useful when models are chosen for convenience rather than literal truth, or when fitting to a continuous distribution rather than a discrete sample. The authors generalize the accuracy measure to relative entropy for continuous distributions.
A unifying theme is that all three approaches can be viewed as maximizing a penalized likelihood function.
Datasets
Not discussed in the paper. The paper uses a simulated exponential distribution as an example input for fitting Gaussian mixtures, rather than real-world datasets.
Key Insights and Ideas
- Unification of Approaches: The core insight is that AIC/BIC, MAP, and the effectiveness ratio can all be framed as maximizing a penalized likelihood function. This provides a theoretical bridge between seemingly different methods.
- Effectiveness Ratio's Generality: The effectiveness ratio is highlighted as the most general approach. It's valuable when:
- Candidate models are not assumed to be literally correct (e.g., chosen for computational ease).
- The goal is to fit an approximate model to a continuous input distribution, not just a sample.
- Computational cost is an explicit factor in model selection.
- Relative Entropy as Accuracy: For continuous distributions, relative entropy (Kullback-Leibler divergence) serves as a natural generalization of likelihood for measuring how well a model distribution approximates the true input distribution.
- Trade-off Between Accuracy and Cost: The effectiveness ratio explicitly models the trade-off between how well a model fits the data and how much computational effort it requires. This is crucial for practical applications, especially in AI.
Key Results
- The paper demonstrates the mathematical equivalence between the MAP approach with a geometric prior and the statistical criteria approach (AIC/BIC) under certain conditions.
- It shows that the effectiveness ratio approach, with a specific cost function (proportional to $m^k$), can be equivalent to the MAP approach.
- An example using Gaussian mixtures to fit an exponential distribution illustrates how the different approaches yield similar results for optimal model complexity (number of components), but the effectiveness ratio offers a more flexible way to incorporate computational cost. The example shows that for effectiveness ratio maximization, the optimal number of components is often smaller than for AIC/BIC, especially with higher computational costs.
Limitations and Future Work
- Large-Sample Assumption: The statistical criteria (AIC/BIC) rely on large-sample approximations, which may not hold for small datasets. The paper notes that Sclove reported good success in practice despite this.
- Heuristic Search: The paper proposes a heuristic for searching for the best model (stopping when the objective function stops improving). This heuristic could potentially miss a global optimum if the objective function has multiple local optima.
- Future Work: The authors suggest exploring more general model selection objectives beyond the effectiveness ratio and more flexible prior distributions over model size than the geometric distribution. Investigating these approaches with limited data is also highlighted as an area for future research.
Summary updated