第四部分：生成学习算法
到目前为止，我们主要讨论了直接对p(y|x;θ)建模的学习算法，即y的条件分布。 例如，对数几率回归将p(y|x;θ)建模为h(x)= g(θ'x)其中g是Sigmoid函数。 在本文中，我们将讨论一种不同类型的学习算法。
考虑一个分类问题，我们希望根据动物的某些特征来学习区分大象(y = 1)和狗(y = 0)。 给定训练集，像对数几率回归或感知机算法(基本上)的算法试图找到一条直线 (即决定边界)将大象和狗分开。 然后，为了将新动物分类为大象或狗，它检查新动物落入决定边界的哪一侧，并相应地进行预测。
这是一种不同的方法。 首先，看大象，我们可以建立一个大象看起来像什么的模型。 然后，看着狗，我们可以建立一个单独的模型，看看狗的样子。 最后，为了对新动物进行分类，我们可以将新动物与大象模型相匹配，并将其与狗模型相匹配，以查看新动物是否更像大象或更像我们在训练集中看到的狗。
尝试直接学习p(y|x)的算法(例如对数几率回归)，或试图直接从输入X的空间到目标值{0,1}学习映射的算法(例如感知器算法)称为判别学习算法。 在这里，我们将讨论试图对p(x|y) ( p(y) )建模的算法，这些算法称为生成学习算法。 例如，如果y指明是狗(0)还是大象(1)，则p(x|y=0)对狗的特征分布建模, p(x|y = 1)则对大象特征分布建模。
在对p(y) (称为类先验)和p(x | y)进行建模之后，我们的算法可以使用贝叶斯公式导出给定x的y后验分布：
这里，分母由p(x)= p(x | y = 1)p(y = 1)+ p(x | y = 0)p(y = 0)给出。 实际上，如果为了进行预测而计算p(y|x)，那么我们实际上并不需要计算分母，因为:
高斯判别分析
朴素贝叶斯
在高斯判别分析中，特征向量x是连续的实值向量。 现在让我们讨论一种不同的学习算法，其中xj是离散值的。
请考虑使用机器学习构建垃圾邮件过滤器。 在这里，我们希望根据消息是未经请求的商业(垃圾邮件)电子邮件还是非垃圾邮件来对邮件进行分类。在学会这样做之后，我们可以让我们的邮件阅读器自动过滤掉垃圾邮件，并可能将它们放在一个单独的邮件文件夹中。 对电子邮件进行分类是文本分类的众多广泛问题的其中一个示例。
假设我们有一个训练集(一组标记为垃圾邮件或非垃圾邮件的电子邮件)。 我们将通过指定用于表示电子邮件的特征xj来开始构建我们的垃圾邮件过滤器。
我们将通过特征向量表示电子邮件，其长度等于字典中的字数。 具体来说，如果电子邮件包含字典的第j个单词，那么我们将设置xj = 1; 否则我们让xj = 0。例如，矢量：
表示一封邮件包含'a'、'buy'，不包含'aardvark'、'aardwolf'、'zygmurgy'。编码到特征向量中的单词集称为词汇表，因此x的维度等于词汇表的大小。
选择了我们的特征向量后，我们现在想要建立一个生成模型。 所以，我们必须对p(x|y)建模。 但是，如果我们有一个50000字的词汇，那么x∈{0,1} 50000（x是0和1的50000维向量），如果我们用多项式分布对x建模会有2250000可能的结果，然后我们最终得到一个(2^250000-1)维参数向量， 这显然是太多的参数。
为了对p(x|y)建模，我们做了一个很强的假设。我们假设给定y条件下xi在是独立的。这个假设称为朴素贝叶斯假设，相应的算法称为朴素贝叶斯分类器。比如，如果y=1表示垃圾邮件；'buy'是第2087 word，'price'是第39831 word；然后假设我告诉你y=1(特定的电子邮件是垃圾邮件)，然后了解x2087(邮件中是否出现“buy”)将不会影响你对x39831价值的看法(是否出现“price”)。 更正式地说，这可以写成p(x2087|y)= p(x2087|y,x39831)。(注意，这与说x2087和x39831是独立的不一样,这应该表示为“p(x2087)= p(x2087 | x39831)”; 相反，我们只是假设x2087和x39831在给定y条件上是独立的。)
现在可以得到：
第一个等式仅仅来自概率的通常属性，第二个等式使用独立性假设。 我们注意到，即使Naive Bayes假设是一个非常强的假设，所得到的算法在许多问题上也能很好地工作。
我们的模型通过[φj| y=1] = p(xj=1|y=1)，[φj|y=0] = p(xj = 1|y = 0)，并且φy= p(y = 1)来参数化。 像往常一样，给定训练集{(x(i)，y(i)); i= 1,...,m}，我们可以写下数据的联合似然：
最大化这个给出最大似然估计：
参数具有非常自然的解释。 例如，φj|y = 1只是单词j出现的垃圾邮件(y = 1)中的一部分。
在拟合了所有这些参数之后，为了对具有x特征的新示例进行预测，我们就可以简单地进行计算：
并选择具有较高后验概率的类别。
最后，我们注意到虽然我们已经开发了朴素贝叶斯算法，主要是针对特征xj是二元值的问题的情况，但是对于xj可以取值{1,2,...,kj}很简单。在这里，我们只是将p(xj | y)建模为多项式而不是伯努利。实际上，即使一些原始输入属性(例如，房屋的生活区域，如我们之前的例子中)是连续值的，将它离散化是很常见的 - 也就是说，将它变成一组离散值然后应用朴素贝叶斯。比如，如果我们使用xj表示居住面积，我们可能类似下面的方式离散化居住面积：
因此，对于居住面积为890平方英尺的房屋，我们将相应特征xj的值设置为3。然后我们可以应用朴素贝叶斯算法，并使用多项分布模型p(xj | y)，如前所述。当原始的连续值属性没有通过多元正态分布很好地建模时，对特征进行离散化并使用朴素贝叶斯(而不是GDA)通常会产生更好的分类器。
拉普拉斯平滑
正如我们所描述的，朴素贝叶斯算法对于许多问题将工作得相当好，但是有一个简单的改变使它工作得更好，特别是对于文本分类。让我们简要地讨论一下算法当前形式的一个问题，然后讨论如何修复它。
考虑垃圾邮件/电子邮件分类，假设在完成CS229并在项目上做了出色的工作后，你决定在2003年6月左右向NIPS会议提交你所做的工作以供发布。因为你最后在电子邮件中讨论了这个会议，所以你也开始收到带有“nips”这个词的信息。但是这是你的第一篇NIPS论文，直到现在，你还没有看到任何包含“nips”这个词的电子邮件；尤其是“nips”从来没有出现在你的垃圾邮件/非垃圾邮件的训练集中。假定“nips”是字典中的第35000个单词，你的朴素贝叶斯垃圾邮件过滤器因此选择了参数φ35000|y的最大似然估计:
因为它从来没有在垃圾邮件或非垃圾邮件的训练示例中看到过“nips”，所以它认为在两种类型的电子邮件中看到它的概率为零。因此，当试图确定这些包含“nips”的消息之一是否是垃圾邮件时，计算类后验概率，并获得：
因为p(x35000|y) = 0，所以我们算法获得了0/0，对于这种情况不知道该如何预测。
更广泛地陈述这个问题，从统计学上讲，仅仅因为你之前在有限的训练集中没有见过它，所以在统计学上估计某个事件的概率为零是个坏主意。考虑估计多项式随机变量z的平均值的问题，变量z取{1,...,k}。我们可以用φj= p(z = j)参数化我们的多项式。 给定一组m独立观察{z(1),...,z(m)}，最大似然估计由下面得出：
正如我们之前看到的，如果我们使用这些最大似然估计，那么某些φj可能最终为零，这是一个问题。 为了避免这种情况，我们可以使用拉普拉斯平滑，如下所示：
注意，φj(j=1,...,m)和为1仍然成立，这是一个理想的属性，因为φj是对我们知道必须总和为1的概率的估计。此外，对于j的所有值，φj不等于0，解决了我们的概率被估计为零的问题。 在某些条件下，可以证明拉普拉斯平滑实际上给出了φj的最优估计。
返回我们的朴素贝叶斯分类器，使用拉普拉斯平滑，我们因此获得以下参数估计：
