假设有两个分类器在训练集上有同样好的性能，但是我们通常认为：其中较简单的一个模型在测试集上能得到更好的效果。（这就是所谓的Occam剃刀原理）。同样的，对判别函数施加平滑性的约束。那么，“更简单”或“更平滑”的分类是否一定有更好的推广能力?!
理论上，分类器的正确率存在一个界限（即贝叶斯误差率），它可以用来比较分类器的性能极限，然而在实践中，极少能准确知道贝叶斯误差率。不存在任何一种模式分类算法具有“与生俱来”的优越性，甚至都不比随机猜测的（结果）好。只有了解问题的具体类型、先验分布情况、数据的分布、训练样本的数量、代价或奖励函数，以及一些其他信息，才能确定哪种形式的分类器将提供最好的性能。在某些假定下，可以估计出分类器的准确率（甚至在分类器完成训练之前），并且可以对不用的分类器进行比较。最后，还可以组合不同的子分类器实现一个“大”的集成分类器。（Ensemble Learning）
No Free Lunch Theorem
通常情况下通过一个独立采样的测试集（相对于训练集）来评定一个分类器推广能力。
例如，对于一个离散问题，当训练集和测试集都很大时，它们必定会有会重叠，即测试到训练过的模式。事实上，任何一种很强的算法，如最近邻法，非修剪的判定树，或是有足够多隐节点数目的神经网络，对于训练集自身都可以学习得很完美。另外，对于低噪声或低贝叶斯错误率的情况，如果采用足够有效的算法去学习训练集，那么其独立同分布（iid）误差率的上界将随训练集大小的增加而减少。
非训练集误差率(off-training set error):不在训练集中的测试错误。如果训练集非常大，那么非训练集的数据量的最大尺寸必定会较小。