An experimental and theoretical comparison of model selection methods
An experimental and theoretical comparison of model selection methods
复制标题
DOI：
10.1023/a:1007344726582
复制
发表时间：
1997-04-01
期刊：
影响因子：
7.5
通讯作者：
Ron, D
中科院分区：
文献类型：
--
作者：
Kearns, M;Mansour, Y;Ron, D
我们研究了从独立随机样本中监督学习布尔函数的模型选择问题。更确切地说，我们比较的方法来找到一个平衡的复杂性的假设选择和它的观察到的误差在一个随机训练样本的大小有限，当目标是最大限度地减少由此产生的泛化误差。我们进行了详细的比较三个著名的模型选择方法-Vapnik的保证风险最小化（GRM）的变化，Rissanen的最小描述长度原则（MDL）的一个实例，和（坚持）交叉验证（CV）。我们介绍了一个通用类的模型选择方法（称为惩罚为基础的方法），包括GRM和MDL，并提供一般的方法来分析这些规则。我们提供了控制的实验证据和正式的定理来支持以下结论：即使在简单的模型选择问题，检查的方法的行为可以是复杂的和无与伦比的。此外，对规则进行再多的“调整”（如在复杂性惩罚项上引入常数乘数，或特定于分布的“有效维数”）也不能消除这种不可比性。对于基于惩罚的方法，可以给出泛化误差的一般界，作为样本大小的函数。这种界限的质量精确地取决于所考虑的方法自动限制所选假设的复杂性的程度。对于任何模型选择问题，与任何其他方法相比，交叉验证的额外误差可以由两项之和限制。只有当底层函数类的学习曲线在（1-gamma）m和m个示例之间经历“相变”时（其中gamma是CV中保存用于测试的分数），第一项才是大的。第二个和竞争的长期可以任意小，增加伽玛。类的惩罚为基础的方法是从根本上有障碍的意义上说，存在两种类型的模型选择问题，每一个惩罚为基础的方法必须招致大的泛化误差至少有一个，而CV享有小的泛化误差。
We investigate the problem of model selection in the setting of supervised learning of boolean functions from independent random examples. More precisely, we compare methods for finding a balance between the complexity of the hypothesis chosen and its observed error on a random training sample of limited size, when the goal is that of minimizing the resulting generalization error. We undertake a detailed comparison of three well-known model selection methods - a variation of Vapnik's Guaranteed Risk Minimization (GRM), an instance of Rissanen's Minimum Description Length Principle (MDL), and (hold-out) cross validation (CV). We introduce a general class of model selection methods (called penalty-based methods) that includes both GRM and MDL, and provide general methods for analyzing such rules. We provide both controlled experimental evidence and formal theorems to support the following conclusions:Even on simple model selection problems, the behavior of the methods examined can be both complex and incomparable. Furthermore, no amount of ''tuning'' of the rules investigated (such as introducing constant multipliers on the complexity penalty terms, or a distribution-specific ''effective dimension'') can eliminate this incomparability.It is possible to give rather general bounds on the generalization error, as a function of sample size, for penalty-based methods. The quality of such bounds depends in a precise way on the extent to which the method considered automatically limits the complexity of the hypothesis selected.For any model selection problem, the additional error of cross validation compared to any other method can be bounded above by the sum of two terms. The first term is large only if the learning curve of the underlying function classes experiences a ''phase transition'' between (1-gamma)m and m examples (where gamma is the fraction saved for testing in CV). The second and competing term can be made arbitrarily small by increasing gamma.The class of penalty-based methods is fundamentally handicapped in the sense that there exist two types of model selection problems for which every penalty-based method must incur large generalization error on at least one, while CV enjoys small generalization error on both.