这是一个有趣的问题，因为它为为什么经常使用的启发式方法需要更多参数提供了很好的背景$\implies$过度拟合的更多风险就是这样，一种启发式。作为讨论的基础，让我们考虑在某种意义上什么是最简单的问题，二元分类。作为一个具体的例子，我们将分别采用典型的生成-判别对、朴素贝叶斯和逻辑回归。我们以这种方式查看对应的对很重要。否则我们要说的任何话都将是无用的。我们当然可以提出非常灵活的生成模型（想象一下替换因式条件$p(x|y)$在具有 delta 函数之类的朴素贝叶斯中）基本上总是过拟合。

首先，我们应该定义过度拟合的含义。过拟合的一个有用定义涉及根据训练集误差和我们使用的分类器类型推导出泛化误差的严格概率界限。在这种情况下，相关参数是假设类的VC 维度$H$（正在使用的分类器集）。简单地说，假设类的 VC 维度由最大的示例集给出，因此对于该集的任何可能标记，存在$h \in H$它可以完全以这种方式标记它们。所以给定$m$二进制分类设置中的示例$2^m$标记它们的方法。如果存在一些集合$m$例如，对于每个$2^m$可能的标签方式有一些$h \in H$正确标记它们，我们可以得出结论$\text{VCdim}(H) \ge m$. 此外，我们说$m$点被粉碎$H$.

事实证明，朴素贝叶斯和逻辑回归都具有相同的 VC 维度，因为它们都将示例分类为$n$尺寸使用$n$维超平面。VC维度$n$维超平面是$n+1$. 您可以通过使用Randon 定理确定 VC 维度的上限并给出一组示例来证明这一点$n+1$被粉碎的点。此外，在这种情况下，我们从低维示例的直觉推广到更高维，我们可以制作漂亮的图片。

从这个意义上说，两者都同样可能过度拟合，因为我们通常会在泛化上得到相似的界限。这也解释了为什么 1 个最近邻是过拟合之王，它具有无限的 VC 维度，因为它粉碎了每一组示例。但这还不是故事的结局。

另一种正式定义过拟合的有用方法是根据假设类中的最佳预测器获得泛化界限，即，如果我们有无限数量的示例，我们都会同意的假设是最好的。在这里，朴素贝叶斯/逻辑回归比较的情况看起来有所不同。首先要注意的是，由于朴素贝叶斯的参数化方式（它们需要指定有效的条件、总和为 1 等），即使给定无限数量的示例，我们也不能保证收敛到最优线性分类器。另一方面，逻辑回归会。所以我们可以得出结论，实际上所有朴素贝叶斯分类器的集合是所有逻辑回归分类器的适当子集。这提供了一些证据，确实，从这个意义上说，朴素贝叶斯分类器可能不太容易过度拟合，因为它们的功能不那么强大/受到更多限制。确实如此。简而言之，如果我们在$n$维空间，朴素贝叶斯要求$O(\log n)$将 whp 收敛到最佳朴素贝叶斯分类器的样本。逻辑回归需要的顺序$O(n)$. 有关此结果的参考，请参阅Ng 和 Jordan 的On Discriminative vs. Generative classifiers。

生成模型通常不会过度拟合，因为它允许用户以类条件的形式放入更多的辅助信息。

考虑一个生成模型$p(c|x) = p(c)p(x|c)$. 如果类条件是具有共享协方差的多变量法线，则这将具有线性决策边界。因此，模型本身与线性 SVM 或逻辑回归一样强大。

然而，判别分类器在决策函数的选择上更加自由：它只需要找到一个合适的超平面。然而，如果假设有效，生成分类器将需要更少的样本来找到好的参数。

抱歉，这是相当随意的，背后没有硬性数学。但这是一种直觉。