TL;DR
This paper demonstrates that common Bayesian and Minimum Description Length (MDL) classification algorithms can be "inconsistent," meaning they may never achieve the best possible performance even with infinite data. This occurs when the underlying probabilistic model used by these algorithms is "misspecified," a common scenario in real-world classification tasks.
What Problem Does This Paper Address?
In machine learning and statistics, overfitting is a major concern. Two popular methods, Bayesian inference and the Minimum Description Length (MDL) principle, are often used to combat overfitting. These methods typically involve defining a set of possible models (classifiers) and using a prior probability distribution to express belief about which model is best. The goal is to find a classifier that performs well on unseen data.
However, a crucial assumption for many theoretical guarantees of these methods is that the "true" data-generating distribution is contained within the set of models considered (i.e., the model is "well-specified"). In practice, this is rarely the case; the models we use are often simplifications of reality, leading to "misspecification." This paper investigates whether Bayesian and MDL classifiers remain optimal and consistent even when the underlying probabilistic model is misspecified. They show that, contrary to some expectations, these methods can indeed exhibit suboptimal behavior in such scenarios.
Methods
The authors analyze specific implementations of Bayesian and MDL classification algorithms. For Bayesian classification, they consider a "pragmatic" approach where classifiers are converted into conditional probability distributions. This conversion, while standard, can lead to misspecified models. They then analyze the behavior of these algorithms under misspecification, particularly focusing on the "Maximum A Posteriori" (MAP) classifier and the full Bayesian classifier.
For MDL, they focus on a "two-part" code length formulation commonly used for classification. The core of their analysis involves constructing specific learning problems and carefully chosen prior distributions that expose the inconsistency of these algorithms. They introduce a formal definition of "classification inconsistency," where the generalization error of the learned classifier remains bounded away from the optimal achievable error, regardless of the amount of data.
Datasets
Not discussed in the paper. The paper focuses on theoretical analysis and constructs artificial learning problems to demonstrate its claims, rather than evaluating algorithms on real-world datasets.
Key Insights and Ideas
- Misspecification is a critical vulnerability: Even powerful methods like Bayesian inference and MDL can fail to be consistent when the assumed probabilistic model doesn't perfectly match the true data-generating process.
- "Pragmatic" Bayesianism can falter: The standard way of converting classifiers into probability distributions for Bayesian inference can lead to misspecified models, causing the Bayesian classifier to perform suboptimally.
- MDL's two-part code can also be inconsistent: The commonly used two-part MDL approach for classification is shown to suffer from the same inconsistency issues under misspecification.
- Priors matter significantly under misspecification: While Bayesian consistency often holds even with misspecification when the model set is "simple" or "convex," this paper shows that for complex model sets (like those arising from a large set of classifiers), the choice of prior becomes crucial for avoiding inconsistency.
- The problem is not just theoretical: The authors argue that in practice, Bayesian inference is frequently applied to classification problems where misspecification is unavoidable, making their findings highly relevant.
Key Results
The paper's main result is Theorem 2, which states that for certain learning problems and priors, the Bayesian MAP classifier, the integrated MAP classifier, and the MDL classifier can be "K-suboptimal." This means their generalization error, even with infinite data, will be at least a constant K greater than the best possible error. They also provide Theorem 3, which bounds the maximal inconsistency of the full Bayesian classifier, showing it can be bounded by H(μ) + δ, where μ is the minimum achievable error rate and H is the binary entropy function.
Limitations and Future Work
The authors acknowledge a potential limitation: their analysis of Bayesian inference primarily uses a transformation that converts classifiers into probability distributions, which is standard for real-valued outputs (like neural networks) but might not fully capture how Bayesians handle 0/1-valued classifiers in all cases. They suggest that similar scenarios of misspecification might still arise for neural networks.
Future work could explore whether their inconsistency results can be extended to real-valued output classifiers. They also note that while their current approach requires specific prior choices, a more general approach might involve considering the convex closure of the model set, though this could lead to suboptimal performance in terms of the classification error measure. They also mention that their results are for infinite data; the behavior with finite data is a separate, complex question.
Summary updated