译者按： 吴恩达和迈克尔乔丹的经典合作之一，是当年吴恩达在乔丹门下读博时发表的，分类问题是机器学习最典型的问题，而朴素贝叶斯和逻辑回归又是最基础最常用的分类算法，两位大神对此进行了深入精到的分析，对机器学习和AI的爱好者来说不可错过

作者： 

Andrew Y. Ng（吴恩达）   ，   Michael I. Jordan（迈克尔一乔丹）

 计算机科学和统计系

加州大学伯克利分校

摘要

我们比较判别式和生成式学习，以logistic回归和朴素贝叶斯为代表。我们表明，与广泛持有的观点（判别式分类器几乎总是被优先考虑的）相反，通常会有两种不同的性能体系，即训练集大小增加，其中每个算法效果更好。这源于观察，在反复实验中证实，尽管判别式学习具有较低的渐近误差，但生成式分类器也可以更快地接近其（较高）渐近性误差。

一、简介

生成分类器学习输入x和标签y的联合概率p（x，y）的模型，并通过使用贝叶斯规则来计算p（ylx），然后选择最可能的标签y来进行预测。 判别分类器直接对后验p（ylx）建模，或者从输入x学习一个直接映射到类标签。 使用判别式而不是生成性分类器有几个令人信服的原因，其中一个由Vapnik简洁地阐述[6]，即“应该直接解决[分类]问题，并且不会解决更普遍的问题作为中间步骤 [例如 作为建模p（xly）]。“ 事实上，抛开计算问题和处理缺失数据等问题，目前的共识似乎是，判别式分类几乎总是被优先于生成性分类。

另一个流行的民间智慧是需要的例子数量，拟合一个模型通常在模型的自由参数数量上大致是线性的。这对于VC的“众多”模型的观察具有理论基础，维数大致是线性的或者至多是参数数量中的一些低阶多项式（参见例如[1,3]），并且已知在VC维中判别性设置中的样本复杂度是线性的[6]。

在本文中，我们从经验和理论上研究这些信念的真实程度。 概率模型p（x，y）的一个参数族可以适合于优化输入和标签的联合似然，或者适合于优化条件似然p（ylx），或者甚至适合于最小化0-1训练 通过对p（ylx）进行阈值处理得到的误差进行预测。 给定根据第一准则的分类器hGen拟合，并且根据第二或第三准则（使用相同的参数族模型）拟合模型hDis，我们称hGen和hD为生成 - 区分对。 例如，如果p（xly）是高斯的且p（y）是多项式的，则相应的生成判别对是正态判别分析和逻辑回归。 类似地，对于离散输入的情况，众所周知，朴素贝叶斯分类器和逻辑回归形成了一个生成 - 区分对[4,5]。

为了比较生成性和判别式学习，似乎很自然地关注这样的对。在本文中，我们考虑朴素贝叶斯模型（用于离散和连续输入）及其区分模拟，逻辑回归/线性分类，并且显示：（a）生成模型的确具有更高的渐近误差训练样例变得很大），但是（b）生成模型也可能比判别模型更快地逼近其渐近误差 - 可能有许多训练样例，它们的数量只是对数而不是线性的参数。这表明，并且我们的实证结果强烈支持 - 随着训练样本数量的增加，可能会有两种截然不同的表现方式，第一种方式是生成模型已经接近其渐近误差，因此表现更好，第二种情况是判别模型接近其较低的渐近误差并做得更好。

二、预演

我们考虑一个二元分类任务，并从离散数据的情况开始。假设X = {O，l} n是n维输入空间，我们假设二进制

简单的输入（泛化没有困难）。 让输出标签为Y = {T，F}，并且在X X Y上存在一个联合分布V. 绘制了训练集S = {x（i），y（i）}〜1。 生成贝叶斯分类器使用S来计算概率的估计值p（xiIY）和p（y）p（xi IY）和p（y），如下所示：

（对于p（y = b），也是类似的），其中#s { - }计算出现的次数事件在训练集S中。这里，设定l =°对应于采用经验估计概率，并且l更传统地被设置为正值，例如1，这对应于使用概率的拉普拉斯平滑。 为了对测试示例x进行分类，当且仅当以下数量为正数时，朴素贝叶斯分类器hGen：X r- + Y预测hGen（x）= T：

在连续输入的情况下，除了我们现在假设X = [O，l] n并且设p（xilY = b）被参数化为具有参数{ti ly = b的单变量高斯分布和 如果注意到j1，而不是if，则取决于y）。 参数通过最大可能性进行拟合，例如{ti ly = b是训练集中标签y = b的所有示例的第i个坐标的经验平均值。 请注意，此方法也等同于假定对角线协方差矩阵的正态判别分析。 在下面的续集中，我们还让J.tree = b = E [XiIY = b]和a; = Ey [Var（xi ly）]是“真”的均值和方差（不管数据是否为高斯分布）。

在离散和连续的情况下，众所周知，朴素贝叶斯的判别式是逻辑回归。 该模型具有参数[，8，OJ，并且假定p（y = Tlx;，8，O）= 1 /（1 + exp（ - ，8Tx-0））。 给定一个测试例x，当且仅当线性判别函数

是积极的。 作为一个判别模型，参数[（3，（）]可以适合于最大化训练集上的条件或全部条件，或者最小化 其中1 { - }是指示器函数（I {True} = 1，I {False} = 0）0-1训练误差L〜= ll {hois（x（i））1-y（i）}。 在错误度量为0-1分类错误的情况下，我们认为后者可以更真实地用于判别式学习的“精神”，尽管前者也经常被用作后者的计算效率近似值。 我们将在很大程度上忽略这两种版本的歧视性学习之间的差异，并且在滥用术语的情况下，我们会松散地使用术语“逻辑回归”来指代，尽管我们的正式分析将集中在后一种方法上。

最后，让1i是所有线性分类器的族（从X到Y的映射）; 并给出一个分类器h：X I -t y，将其泛化误差定义为c（h）= Pr（x，y）〜v [h（x）1-y]。

三、分析和算法

当D使得两类远离线性分离时，逻辑回归和朴素贝叶斯都不可能做得好，因为两者都是线性分类器。 因此，为了获得非平凡的结果，将这些算法的性能与它们的渐近误差进行比较是最有趣的（参见不可知论学习设置）。 更确切地说，让hGen，oo是朴素贝叶斯分类器的人口版本; 即hGen，oo是具有参数p（xly）= p（xly），p（y）= p（y）的朴素贝叶斯分类器。 同样，让hOis是逻辑回归的人口版本。 接下来的两个命题是完全简单的。

命题1让hGen和hDis是任何生成歧视的分类器，binoo和hdis是它们的渐近/种群版本。 然后lc（hDis，oo）：Sc（hGen，oo）。

命题2让hDis为n维逻辑回归。 然后高概率c（hois）：S c（hois，oo）+ 0（J〜log〜）

因此，对于c（hOis）：S c（hOis，oo）+ EO以高概率保持（这里EO> 0是某个固定常量），只需选择m = O（n）即可。

命题1表明，渐近地判别式逻辑回归的误差小于生成朴素贝叶斯的误差。 这很容易表明，由于c（hDis）收敛于infhE1-lc（h）（其中1i是所有线性分类器的类别），因此它必须渐近地不比朴素贝叶斯挑选的线性分类器差。 这个命题也为广泛认为判别式分类器比生成式分类器更好的观点提供了基础。

命题2是另一个标准结果，并且是一个直接的应用Vapnik一致收敛于逻辑回归，并使用1i具有VC维n的事实。 命题的第二部分指出，判别式学习的样本复杂性 - 即需要接近渐近误差的例子的数量 - 至多是n的数量级。 请注意，最坏情况下的样本复杂度也受n阶[6]的限制。

因此，判别式学习的图片相当清楚：错误收敛于最佳线性分类器的收敛，并且收敛在n个例子的顺序之后。 

生成式学习如何？特别是朴素贝叶斯分类器的情况？ 我们从以下引理开始。

引理3

任何101,8>°和任何l 2：°都是固定的。 假设对于一些固定的Po> 0，我们有Po：s：p（y = T）：s：1 - Po。 让m = 0（（1 / Ei）log（n / 8））。 然后概率至少为1 - 8：

1.在离散输入的情况下，IjJ（XiIY = b）-p（xilY = b）1：s：101和IjJ（y =b） - p（y = b）I：s：101，对于所有i = 1，...，n和bEY。

2.在连续输入的情况下，IPi ly = b -f-li ly = b I：s：101，laT-O“TI：s：101，并且IjJ（y = b）-p（y = b） ：s：101，所有i = 1，...，n和bEY。

证明（草图）。考虑离散情况，现在让l =°。设101：s：po / 2。通过Chernoff界限，概率至少为1 - 81 = 1 - 2exp（-2Eim），正例的比例将在p（y = T）的101范围内，这意味着IjJ（y = b） - p（y = b）1：s：101，我们至少有1m正数和1m负数示例，其中I = Po-101 = 0（1）。所以再次通过Chernoff界限，对于具体的i，b，IjJ（XiIY = b）-p（xilY = b）1> 101的机会最多为82 = 2exp（-2Ehm）。由于存在2n个这样的概率，联盟限制的错误总发生概率最多为81 + 2n82。用81和8 / s定义代替，我们看到为了保证81 + 2n82：s：8，只要m如前所述即可。最后，平滑（l> 0）对这些概率至多添加一个小的O（l / m）扰动，并使用与上述相同的参数（比如说101/2）而不是101，并且认为这个O / m）扰动至多为101/2（这是因为m至少为1 / Ei），再次给出结果。对于连续情况的结果用基于切尔诺夫边界的论证（以及假设Xi E [0,1]）被类似地证明。

因此，在n个样本中，只有对数而不是线性的样本，生成分类器hGen的参数均匀接近它们的渐近线

hGen中的值，oo。因此，很容易得出结论，c（hGen），即错误生成的朴素贝叶斯分类器也趋于其渐近值c（hGen，oo）

在这个例子之后，暗示只需要0（log n）个例子来适应a朴素贝叶斯模型。我们将很快建立一些简单的条件

这种直觉确实是正确的。请注意，这意味着即使朴素贝叶斯收敛于c（hGen，oo）与logistic回归相比更高的渐近误差

c：（hDis，oo），它也可能比O（log n）快得多O（n），

训练例子。显示c（hGen）方法c（hGen，oo）的一种方式是通过显示参数'收敛意味着hGen很可能会做出同样的预测

hGen，oo。回想一下，hGen通过对判别函数进行阈值处理来进行预测lGen在（2）中定义。设lGen，oo为相应的判别函数

由hGen使用，oo。在每个例子上，lGen和lGen都落在同一个地方零的边，hGen和hGen，oo会做出同样的预测。而且，只要

lGen，oo（x）的概率相当高，远离零，那么lGen（x）是一个很小的lGen的扰动oo（x）通常也会与lGen oo（x）在同一边。

定理4定义G（T）= Pr（x，y）〜v [（lGen，oo（x）E [O，Tn] A y = T）V（lG en，oo（X）E [-Tn，O ] AY = F）]。 假设对于一些固定的Po> 0，我们有Po：s：p（y = T）：s：1 - Po，并且Po：s：P（Xi = 11Y = b）：s：1 - Po对于所有的i，b离散输入）或O“T 2：Po（在连续的情况下）然后以高概率，

证明（草图）。 c（hGen） - c（hGen，oo）受上述机会的上界限hGen，oo正确地对随机选择的示例进行分类，但hGen将其错误分类。

引理3确保hGen的所有参数在hGen的所有参数O（j（log n）/ m）内的概率很高。这又意味着，lGen中的总和中的n + 1项（如等式2）中的每个项都在lGen，oo中对应项的O（j（1ogn）/ m）之内，因此IlGen（x） -lGen，oo（x）1：SO（nj（1ogn）/ m）。假设T = O（j（logn）/ m），我们就可以看出，只有当y = T且lGen时，hGen，oo才有可能是正确的，而hGen可能是错误的（x，y） X）E [0，Tn]（因此有可能是lGen，oo（X）::::: 0，lGen（x）：S 0），或者如果y = F和lGen，oo（X）E [-Tn，0]。这个概率恰好是G（T），因此上界c（hGen） - c（hGen，oo）。 d

定理中的关键量是G（T），当T很小时它必须很小，以使边界不平凡。注G（T）以上界为界Prx [lGen，oo（x）E [-Tn，Tn]] - lGen，oo（X）（一个随机变量，其分布由x“”V引起）接近零的概率。要获得关于这些随机变量的缩放的直觉，请考虑以下几点：

命题5假设，对于至少一个0（1）分数的特征我（我=1，...，n），对于一些IP（Xi = 11Y = T）-P（Xi = 11Y = F）I :::::'Y 固定'Y> 0（或者在连续输入的情况下，IJLi ly = T -JLi ly = FI :::::'Y）。 然后E [lGen，oo（x）ly = T] = O（n）和-E [lGen，oo（x）ly = F] = O（n）。

因此，只要类标签给出有关0（1）分数的信息特征（或者不太正式，只要大多数特征与类标签“相关”），IlGen的期望值oo（X）I将是O（n）。 这个命题很容易通过证明条件（例如）事件y = T，以lGen，oo（x）（如等式（2）中的总和中的每个项，但用fi代替fi） 非负的期望（由KL散度的非负性），此外0（1）部分的期望值远离零。

命题5保证IlGen，oo（x）1有很大的期望，但我们要想绑定G实际上是稍微强一点，那就是随机的变量IlGen，oo（x）1进一步大/远离零，具有高概率。那里有几种方法可以获得足够的条件来确保G很小。一获得松散界限的方法是通过切比雪夫不等式。对于其余的这个讨论，让我们为了简单而隐含地说明一个测试事件示例x具有标签T.切比雪夫不等式意味着Pr [lGen，oo（x）：SE [lGen，oo（X）] - t]：S Var（lGen，oo（x））/ t2。现在，lGen，oo（X）是n个随机数之和变量（忽略涉及先验p（y）的术语）。如果（仍然以y为条件），这n个随机变量是独立的（即如果“朴素贝叶斯假设”假设xi在条件上独立于给定的y，保持），那么它的方差是O（n）;即使n个随机变量不完全独立，方差可能也是如此仍然不会大于0（n）（甚至可能更小，取决于相关性的迹象），并且至多是O（n2）。所以，如果E [lGen，oo（x）ly = T] = an（as将通过命题5来保证）对于一些> 0，通过设置t =（a-T）n，Chebyshev不等式给出了Pr [lGen，oo（x）：S Tn]：S 0（1 /（a-T）2n1 /）一致地界定，那么我们也是

有G（T）= O（T）。无论如何，我们对定理4也有如下推论。

推论6假设定理4的条件成立，并假设G（T）：S Eo / 2 + 对于满足F（T） - + 0的函数F（T）（与n无关）的F（T）为T - + 0，

和一些固定的EO> O.那么对于€（hGen）：S c（hGen，oo）+ EO保持高

图1：来自VCI Machine Learning的数据集的15个实验的结果库。 绘图的泛化误差与m（平均超过1000个随机数

火车/测试分割）。 虚线是逻辑回归; 实线是朴素贝叶斯。

请注意，前面的讨论暗示了推论的先决条件确实存在于朴素贝叶斯（和命题5）的假设情况下对于任何常数fa，只要n足够大以至于fa ::::: exp（-O（o：2n））（对于有界限的Var（lGen，oo（x））情况也是如此，并且限制性更强的fa ::::: O（I /（o：2n17）））。 这也意味着这些（后者也要求T）> 0）是渐近样本复杂度为0（log n）的充分条件。

四、实验

逻辑回归算法具有较低的渐近误差，生成的朴素贝叶斯分类器也可以更快地收敛到其（较高）渐近误差。因此，随着训练样本数量m的增加，人们会期望生成朴素贝叶斯最初做的更好，但对于区分逻辑回归最终赶上并很可能超过朴素贝叶斯的性能。为了测试这些预测，我们对15个数据集进行了实验，其中8个连续输入，7个离散输入，来自VCI机器学习库2.这些实验的结果如图1所示。我们发现理论预测出人意料地好。有一些logistic回归的表现没有赶上朴素贝叶斯的情况，但这主要是在特别小的数据集中观察到的，在这些数据集中，m估计不能大到足以让我们观察到大规模逻辑回归的预期优势m限制。

五、讨论

Efron [2]也分析了逻辑回归和正态判别分析（for连续的投入），并得出结论，前者只是渐近的略微（1/3 - 1/2倍）统计效率较低。这与我们的形成鲜明对比结果，一个关键的区别是，而不是假设P（xly）是高斯的一个对角协方差矩阵（就像我们所做的那样），Efron考虑了P（xly）的情况建模为具有完全信任矩阵的高斯。在这种情况下，估计协方差矩阵是奇异的，如果我们在n个训练样本中的线性少于，那么正态判别分析不能比学习快得多逻辑回归在这里。第二个重要的区别是Efron的考虑只有P（xly）确实是高斯的特例。这样的渐近在一般情况下比较不是很有用，因为唯一可能的结论，如果€（hDis，oo）<€（hGen，oo）是逻辑回归是优越的算法。

相反，正如我们以前所看到的那样，这是非渐近的情况观察到有趣的“双机制”行为。实用的分类算法通常涉及某种形式的正则化特定的逻辑回归通常可以在实践中通过技术改进如通过L1约束收缩参数，强加一个裕度约束在可分离的情况下，或各种形式的平均。这种正则化技术可以被看作是改变模特家庭，但是，他们在很大程度上是这样正交于本文的分析，这是基于特别考察的清晰的生成歧视模型配对案例。通过开发更清晰了解纯生殖和歧视的条件方法最成功，我们应该能够更好地设计混合分类器享受最广泛的条件范围内的最佳性能。最后，虽然我们的讨论集中在朴素贝叶斯和逻辑回归，但是直接将分析扩展到其他几种模型，包括生成歧视通过使用固定结构，有界贝叶斯生成P（xly）网络模型（其中朴素贝叶斯是一个特例）。

致谢

我们感谢Andrew McCallum提供有用的对话。吴恩达得到了微软研究院奖学金支持。 这项工作也得到了英特尔的资助

References

[1] M. Anthony and P. Bartlett. Neural Network Learning: Theoretical Foundations. Cambridge

University Press, 1999.

[2] B. Efron. The efficiency of logistic regression compared to Normal Discriminant Analysis.

Journ. of the Amer. Statist. Assoc., 70:892- 898, 1975.

[3] P. Goldberg and M. Jerrum. Bounding the VC dimension of concept classes parameterized

by real numbers. Machine Learning, 18:131-148, 1995.

[4] G.J. McLachlan. Discriminant Analysis and Statistical Pattern Recognition. Wiley,

New York, 1992.

[5] Y. D. Rubinstein and T. Hastie. Discriminative vs. informative learning. In Proceedings

of the Third International Conference on Knowledge Discovery and Data Mining, pages

49- 53. AAAI Press, 1997.

[6] V. N. Vapnik. Statistical Learning Theory. John Wiley & Sons, 1998.