ML4. 生成学习算法(Generative Learning algorithms)

此部分内容包含了大量的概率论知识计算

目前为止，我们讲过的学习算法的模型都是 $p (y|x;\theta)$ ，也就是给定 $x$ 下 $y$ 的条件分布，以 $\theta$ 为参数。例如，逻辑回归中就是以 $h_\theta(x) = g(\theta^T x)$ 作为 $p (y|x;\theta)$ 的模型，这里的 $g$ 是一个 $S$ 型函数（sigmoid function）。接下来，咱们要讲一下一种不同类型的学习算法。

设想有这样一种分类问题，我们要学习基于一个动物的某个特征来辨别它是大象 $(y=1)$ 还是小狗 $(y=0)$ 。给定一个训练集，用逻辑回归或者基础版的感知器算法（perceptron algorithm） 这样的一个算法能找到一条直线，作为区分开大象和小狗的边界。接下来，要辨别一个新的动物是大象还是小狗，程序就要检查这个新动物的值落到了划分出来的哪个区域中，然后根据所落到的区域来给出预测。

还有另外一种方法。找到所有大象数据的分布特征，以及小狗数据的分布特征（比如高斯分布）。然后对于个一个新的动物，程序会检测这两个分布特征，将这个新的动物归于更符合那个分布的类里。

从数学上来说，逻辑回归以及感知器算法（perceptron algorithm）之类的直接试图建立 $p(y|x)$ 的算法，直接用投图（mappings directly）的思路来判断对应 $y$ 的值落到了 $\{0, 1\}$ 中哪个区域，这些都叫判别式学习算法（discriminative learning algorithms）。 和之前的这些判别式算法不同，下面我们要讲的新算法是对 $p(x|y)$ 和 $p(y)$ 来进行建模。这类算法叫 做生成学习算法（generative learning algorithms 。例如如果 $y$ 用来表示一个样例是小狗 $(0)$ 或者大象 $(1)$ ，那么 $p(x|y = 0)$ 就是对小狗特征分布的建模，而 $p(x|y = 1)$ 就是对大象特征分布的建模。

对 $p(y)$ (通常称为先验类 (class priors)) 和 $p(x|y)$ 进行建模之后，我们的算法就是用贝叶斯规则(Bayes rule) 来推导对应给定 $x$ 下 $y$ 的后验分布(posterior distribution)：

$p(y|x)=\frac{p(x|y)p(y)}{p(x)}$

这里的分母（denominator） 为：

$p(x) = p(x|y = 1)p(y = 1) + p(x|y = 0)p(y = 0)$

通过条件概率的公式，便可以求出 $p(x|y)$ 和 $p(y)$ 。实际上如果我们计算 $p(y|x)$ 来进行预测，那就并不需要去计算这个分母，因为 $p(x)$ 表示了所有的情况，所以 $p(x)=1$ ，因此就有：

$\begin{aligned} \arg \max_y p(y|x) & =\arg \max_y \frac{p(x|y)p(y)}{p(x)}\\ &= \arg \max_y p(x|y)p(y) \end{aligned}$

1 高斯判别分析（Gaussian discriminant analysis）

咱们要学的第一个生成学习算法就是高斯判别分析（Gaussian discriminant analysis ，缩写为GDA。在这个模型里面，我们假设 $p(x|y)$ 是一个多元正态分布。 所以首先咱们简单讲一下多元正态分布的一些特点，然后再继续讲 GDA 高斯判别分析模型。

1.1 多元正态分布（multivariate normal distribution）

$n$ 维多元正态分布，也叫做多元高斯分布，参数为一个 $n$ 维 均值向量 $\mu \in R^n$ ，以及一个 协方差矩阵 $\Sigma \in R^{n\times n}$ ，其中 $\Sigma \geq 0$ 是一个对称（symmetric）的半正定（positive semi-definite）矩阵。当然也可以写成" $N (\mu, \Sigma)$ " 的分布形式,密度（density）函数为：

$p(x;\mu,\Sigma)=\frac{1}{(2\pi)^{n/2}|\Sigma|^{1/2}} exp(-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu))$

在上面的等式中，" $|\Sigma|$ "的意思是矩阵 $\Sigma$ 的行列式（determinant）。

对于一个在 $N(\mu,\Sigma)$ 分布中的随机变量 $X$ ，其平均值（跟正态分布里面差不多，所以并不意外）就是 $\mu$ 了：

$E[X]=\int_x xp(x;\mu,\Sigma)dx=\mu$

随机变量 $Z$ 是一个有值的向量（vector-valued random variable）， $Z$ 的 协方差（covariance） 的定义是： $Cov(Z) = E[(Z-E[Z])(Z-E[Z])^T ]$ 。这是对实数随机变量的方差（variance）这一概念的泛化扩展。这个协方差还可以定义成 $Cov(Z) = E[ZZ^T]-(E[Z])(E[Z])^T$ 。如果 $X$ 是一个多变量正态分布，即 $X \sim N (\mu, \Sigma)$ ，则有：

$Cov(X)=\Sigma$

下面举一个简单的例子，一个二元的正态分布可以是下面的样子：

$X \sim \mathcal N_2(\mu, \Sigma) , \qquad \mu = \begin{bmatrix} \mu_1 \\ \mu_2 \end{bmatrix} , \qquad \Sigma = \begin{bmatrix} \sigma_1^2 & 0 \\ 0 & \sigma_2^2 \\ \end{bmatrix}$

将参数具体后的图像如下：

$X \sim \mathcal N_2(\mu, \Sigma) , \qquad \mu = \begin{bmatrix} 0 \\ 1 \end{bmatrix} , \qquad \Sigma = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ \end{bmatrix}$

下面看更多的例子：

这三个图像的中心位置相同，只有 $\Sigma$ 在发生改变，其 $\Sigma$ 矩阵依次为：

$\Sigma_1 = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ \end{bmatrix} ; \qquad \Sigma_2 = \begin{bmatrix} 0.6 & 0 \\ 0 & 0.6 \\ \end{bmatrix} ; \qquad \Sigma_3 = \begin{bmatrix} 2 & 0 \\ 0 & 2 \\ \end{bmatrix}$

从这几个图可以看出，随着协方差矩阵 $\Sigma$ 变大，高斯分布的形态就变得更宽平（spread-out），而如果协方差矩阵 $\Sigma$ 变小，分布就会更加集中（compressed）。

来看一下更多的样例：

这些图片的 $\Sigma$ 为：

$\Sigma_1 = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ \end{bmatrix} ; \qquad \Sigma_2 = \begin{bmatrix} 1 & 0.5 \\ 0.5 & 1 \\ \end{bmatrix} ; \qquad \Sigma_3 = \begin{bmatrix} 1 & 0.8 \\ 0.8 & 1 \\ \end{bmatrix}$

第一幅图还跟之前的标准正态分布的样子很相似，然后我们发现随着增大协方差矩阵 $\Sigma$ 的反对角线（off-diagonal）的值，密度图像开始朝着 45° 方向 (也就是 $x_1 = x_2$ 所在的方向)逐渐压缩（compressed）。看一下三个同样分布密度图的轮廓图（contours）能看得更明显：

下面的是另外一组样例，调整了协方差矩阵 $\Sigma$ :

$\Sigma =\begin{bmatrix} 1 & -0.5 \\ -0.5 & 1 \\ \end{bmatrix}; \Sigma =\begin{bmatrix} 1 & -0.8 \\ -0.8 & 1 \\ \end{bmatrix} \Sigma =\begin{bmatrix} 3 & 0.8 \\ 0.8 & 1 \\ \end{bmatrix};$

上面这三个图像对应的协方差矩阵分别如下所示：

当我们将反对角线的值取负后，图像朝着另外一个方向的 45° 角开始压缩。

当固定协方差矩阵为单位矩阵，即 $\Sigma = I$ ，然后调整均值 $\mu$ ，我们就可以让密度图像随着均值而移动：

上图对应的均值 $\mu$ 如下所示：

$\mu =\begin{bmatrix} 1 \\ 0 \\ \end{bmatrix}; \mu =\begin{bmatrix} -0.5 \\ 0 \\ \end{bmatrix}; \mu =\begin{bmatrix} -1 \\ -1.5 \\ \end{bmatrix};$

1.2 高斯判别分析模型（Gaussian Discriminant Analysis model）

假如我们有一个分类问题，其中输入特征 $x$ 是一系列的连续随机变量（continuous-valued random variables），那就可以使用高斯判别分析（Gaussian Discriminant Analysis ，缩写为 GDA）模型，其中对 $p(x|y)$ 用多元正态分布来进行建模。这个模型为：

$\begin{aligned} y & \sim Bernoulli(\phi)\\ x|y = 0 & \sim N(\mu_o,\Sigma)\\ x|y = 1 & \sim N(\mu_1,\Sigma)\\ \end{aligned}$

分布写出来的具体形式如下：

$\begin{aligned} p(y) & =\phi^y (1-\phi)^{1-y}\\ p(x|y=0) & = \frac{1}{(2\pi)^{n/2}|\Sigma|^{1/2}} exp ( - \frac{1}{2}(x-\mu_0)^T\Sigma^{-1}(x-\mu_0) )\\ p(x|y=1) & = \frac{1}{(2\pi)^{n/2}|\Sigma|^{1/2}} exp ( - \frac{1}{2}(x-\mu_1)^T\Sigma^{-1}(x-\mu_1) )\\ \end{aligned}$

在上面的等式中，模型的参数包括 $\phi, \Sigma, \mu_0 和 \mu_1$ 。（要注意，虽然这里有两个不同方向的均值向量 $\mu_0$ 和 $\mu_1$ ，针对这个模型还是一般只是用一个协方差矩阵 $\Sigma$ 。）取对数的似然函数（log-likelihood）如下所示：

$\begin{aligned} l(\phi,\mu_0,\mu_1,\Sigma) &= \log \prod^m_{i=1}p(x^{(i)},y^{(i)};\phi,\mu_0,\mu_1,\Sigma)\\ &= \log \prod^m_{i=1}p(x^{(i)}|y^{(i)};\mu_0,\mu_1,\Sigma)p(y^{(i)};\phi)\\ \end{aligned}$

通过使 $l$ 取得最大值，找到对应的参数组合，然后就能找到该参数组合对应的最大似然估计，如下所示：

$\begin{aligned} \phi & = \frac {1}{m} \sum^m_{i=1}1\{y^{(i)}=1\}\\ \mu_0 & = \frac{\sum^m_{i=1}1\{y^{(i)}=0\}x^{(i)}}{\sum^m_{i=1}1\{y^{(i)}=0\}}\\ \mu_1 & = \frac{\sum^m_{i=1}1\{y^{(i)}=1\}x^{(i)}}{\sum^m_{i=1}1\{y^{(i)}=1\}}\\ \Sigma & = \frac{1}{m}\sum^m_{i=1}(x^{(i)}-\mu_{y^{(i)}})(x^{(i)}-\mu_{y^{(i)}})^T\\ \end{aligned}$

用图形化的方式来表述，这个算法可以按照下面的图示所表示：

图中展示的点就是训练数据集，图中的两个高斯分布就是针对两类数据各自进行的拟合。要注意这两个高斯分布的轮廓图有同样的形状和拉伸方向，这是因为他们都有同样的协方差矩阵 $\Sigma$ ，但他们有不同的均值 $\mu_0$ 和 $\mu_1$ 。此外，图中的直线给出了 $p (y = 1|x) = 0.5$ 这条边界线。在这条边界的一侧，我们预测 $y = 1$ 是最可能的结果，而另一侧，就预测 $y = 0$ 是最可能的结果。

1.3 讨论：高斯判别分析（GDA）与逻辑回归（logistic regression）

高斯判别分析模型与逻辑回归有很有趣的相关性。如果我们把变量（quantity） $p (y = 1|x; \phi, \mu_0, \mu_1, \Sigma)$ 作为一个 $x$ 的函数，就会发现可以用如下的形式来表达：

$p(y=1|x;\phi,\Sigma,\mu_0,\mu_1)=\frac 1 {1+exp(-\theta^Tx)}$

其中的 $\theta$ 是对 $\phi$ , $\Sigma$ , $\mu_0$ , $\mu_1$ 的某种函数。这就是逻辑回归（也是一种判别分析算法）用来对 $p (y = 1|x)$ 建模的形式。

这两个模型中什么时候该选哪一个呢？一般来说，高斯判别分析（GDA）和逻辑回归，对同一个训练集，可能给出的判别曲线是不一样的。哪一个更好些呢？

我们刚刚已经表明，如果 $p(x|y)$ 是一个多变量的高斯分布（且具有一个共享的协方差矩阵 $\Sigma$ ），那么 $p(y|x)$ 则必然符合一个逻辑函数（logistic function）。然而，反过来，这个命题是不成立的。例如假如 $p(y|x)$ 是一个逻辑函数，这并不能保证 $p(x|y)$ 一定是一个多变量的高斯分布。

$GDA \ ^{\Rightarrow{}}_{\nLeftarrow}\ LR$

这就表明高斯判别模型能比逻辑回归对数据进行更强的建模和假设（stronger modeling assumptions）。 这也就意味着，在这两种模型假设都可用的时候，高斯判别分析法去拟合数据是更好的，是一个更好的模型。 尤其当 $p(x|y)$ 已经确定是一个高斯分布（有共享的协方差矩阵 $\Sigma$ ），那么高斯判别分析是渐进有效的（asymptotically efficient）。 实际上，这也意味着，在面对非常大的训练集（训练样本规模 $m $特别大）的时候，严格来说，可能就没有什么别的算法能比高斯判别分析更好（比如考虑到对 $p(y|x)$ 估计的准确度等等）。所以在这种情况下就表明，高斯判别分析（GDA）是一个比逻辑回归更好的算法；再扩展一下，即便对于小规模的训练集，我们最终也会发现高斯判别分析（GDA）是更好的。

奈何事有正反，由于逻辑回归做出的假设要明显更弱一些（significantly weaker），所以因此逻辑回归给出的判断鲁棒性（robust）也更强，同时也对错误的建模假设不那么敏感。有很多不同的假设集合都能够将 $p(y|x)$ 引向逻辑回归函数。例如，如果 $x|y = 0\sim Poisson(\lambda_0)$ 是一个泊松分布，而 $x|y = 1\sim Poisson(\lambda_1)$ 也是一个泊松分布，那么 $p(y|x)$ 也将是适合逻辑回归的（logistic）。逻辑回归也适用于这类的泊松分布的数据。但对这样的数据，如果我们强行使用高斯判别分析（GDA），然后用高斯分布来拟合这些非高斯数据，那么结果的可预测性就会降低，而且GDA这种方法也许可行，也有可能是不能用。

总结一下也就是：高斯判别分析方法（GDA）能够建立更强的模型假设，并且在数据利用上更加有效（比如说，需要更少的训练集就能有"还不错的"效果），当然前提是模型假设争取或者至少接近正确。逻辑回归建立的假设更弱，因此对于偏离的模型假设来说更加鲁棒（robust）。然而，如果训练集数据的确是非高斯分布的（non-Gaussian），而且是有限的大规模数据（in the limit of large datasets），那么逻辑回归将更加合适。因此，在实际中，逻辑回归的使用频率要比GDA高得多。

2 朴素贝叶斯法（Naive Bayes）

在高斯判别分析（GDA）方法中，特征向量 $x$ 是连续的，值为实数的向量。下面我们要讲的是当 $x_i$ 是离散值的时候来使用的另外一种学习算法。

下面我们来尝试使用机器学习的方法建立一个邮件筛选器。我们要将邮件分为两类，垃圾邮件，和普通邮件。对邮件进行分类是一个案例，属于文本分类这一更广泛问题集合。

假设我们有了一个训练集（也就是一堆已经标好了是否为垃圾邮件的邮件）。要构建垃圾邮件分选器，咱们先要开始确定用来描述一封邮件的特征 $x_i$ 有哪些。

我们将用一个特征向量来表示一封邮件，这个向量的长度等于字典中单词的个数。如果邮件中包含了字典中的第 $i$ 个单词，那么就令 $x_i = 1$ ；反之则 $x_i = 0$ 。例如下面这个向量：

$x=\begin{bmatrix}1\\0\\0\\\vdots \\1\\ \vdots \\0\end{bmatrix} \begin{matrix}\text{a}\\ \text{aardvark}\\ \text{aardwolf}\\ \vdots\\ \text{buy}\\ \vdots\\ \text{zygmurgy}\\ \end{matrix}$

就用来表示一个邮件，其中包含了两个单词 "a" 和 "buy"，但没有单词 "aardvark"， "aardwolf" 或者 "zymurgy" 。这个单词集合编码整理成的特征向量也成为词汇表（vocabulary,）， 所以特征向量 $x$ 的维度就等于词汇表的长度。

注：实际应用中并不需要遍历整个英语词典来组成所有英语单词的列表，实践中更常用的方法是遍历一下训练集，然后把出现过一次以上的单词才编码成特征向量。这样做除了能够降低模型中单词表的长度之外，还能够降低运算量和空间占用，此外还有一个好处就是能够包含一些你的邮件中出现了而词典中没有的单词，比如本课程的缩写CS229。有时候（比如在作业里面），还要排除一些特别高频率的词汇，比如像冠词the，介词of 和and 等等；这些高频率但是没有具体意义的虚词也叫做stop words，因为很多文档中都要有这些词，用它们也基本不能用来判定一个邮件是否为垃圾邮件。

选好了特征向量了，接下来就是建立一个生成模型（generative model）。所以我们必须对 $p(x|y)$ 进行建模。但是，假如我们的单词有五万个词，则特征向量 $x \in \{0, 1\}^{50000}$ （即 $x$ 是一个 $50000$ 维的向量，其值是 $0$ 或者 $1$ ），如果我们要对这样的 $x$ 进行多项式分布的建模，那么就可能有 $2^{50000}$ 种可能的输出，然后就要用一个 $(2^{50000}-1)$ 维的参数向量。这样参数明显太多了。

要给 $p(x|y)$ 建模，先来做一个非常强的假设。我们假设特征向量 $x_i$ 对于给定的 $y$ 是独立的。 这个假设也叫做朴素贝叶斯假设（Naive Bayes ，NB assumption）， 基于此假设衍生的算法也就叫做朴素贝叶斯分类器（Naive Bayes classifier）。 例如，如果 $y = 1$ 意味着一个邮件是垃圾邮件；然后其中"buy" 是第 $2087$ 个单词，而 "price"是第 $39831$ 个单词；那么接下来我们就假设，如果我告诉你 $y = 1$ ，也就是说某一个特定的邮件是垃圾邮件，那么对于 $x_{2087}$ （也就是单词 buy 是否出现在邮件里）的了解并不会影响你对 $x_{39831}$ （单词price出现的位置）的采信值。更正规一点，可以写成 $p(x_{2087}|y) = p(x_{2087}|y, x_{39831})$ 。（要注意这个并不是说 $x_{2087}$ 和 $x_{39831}$ 这两个特征是独立的，那样就变成了 $p(x_{2087}) = p(x_{2087}|x_{39831})$ ，我们这里是说在给定了 $y$ 的这样一个条件下，二者才是有条件的独立。）

然后我们就得到了等式：

$\begin{aligned} p(x_1, ..., x_{50000}|y) & = p(x_1|y)p(x_2|y,x_1)p(x_3|y,x_1,x_2) ... p(x_{50000}|y,x_1,x_2,...,x_{49999})\\ & = p(x_1|y)p(x_2|y)p(x_3|y) ... p(x_{50000}|y)\\ & = \prod^n_{i=1}p(x_i|y)\\ \end{aligned}$

第一行的等式就是简单地来自概率的基本性质，第二个等式则使用了朴素贝叶斯假设。这里要注意，朴素贝叶斯假设也是一个很强的假设，产生的这个算法可以适用于很多种问题。

我们这个模型的参数为 $\phi_{i|y=1} = p (x_i = 1|y = 1), \phi_{i|y=0} = p (x_i = 1|y = 0)$ , 而 $\phi_y = p (y = 1)$ 。和以往一样，给定一个训练集 $\{(x^{(i)},y^{(i)}); i = 1, ..., m\}$ ，就可以写出下面的联合似然函数：

$\mathcal{L}(\phi_y,\phi_{j|y=0},\phi_{j|y=1})=\prod^m_{i=1}p(x^{(i)},y^{(i)})$

找到使联合似然函数取得最大值的对应参数组合 $\phi_y , \phi_{i|y=0} 和 \phi_{i|y=1}$ 就给出了最大似然估计：

$\begin{aligned} \phi_{j|y=1} &=\frac{\sum^m_{i=1}1\{x_j^{(i)} =1 \wedge y^{(i)} =1\} }{\sum^m_{i=1}1\{y^{(i)} =1\}} \\ \phi_{j|y=0} &= \frac{\sum^m_{i=1}1\{x_j^{(i)} =1 \wedge y^{(i)} =0\} }{\sum^m_{i=1}1\{y^{(i)} =0\}} \\ \phi_{y} &= \frac{\sum^m_{i=1}1\{y^{(i)} =1\}}{m}\\ \end{aligned}$

在上面的等式中，" $\wedge$ (and)"这个符号的意思是逻辑"和"。这些参数有一个非常自然的解释。例如 $\phi_{j|y=1}$ 正是垃圾 $(y = 1)$ 邮件中出现单词 $j$ 的邮件所占的比例。

拟合好了全部这些参数之后，要对一个新样本的特征向量 $x$ 进行预测，只要进行如下的简单地计算：

$\begin{aligned} p(y=1|x)&= \frac{p(x|y=1)p(y=1)}{p(x)}\\ &= \frac{(\prod^n_{i=1}p(x_i|y=1))p(y=1)}{(\prod^n_{i=1}p(x_i|y=1))p(y=1)+ (\prod^n_{i=1}p(x_i|y=0))p(y=0)} \\ \end{aligned}$

然后选择有最高后验概率的概率。

最后我们要注意，刚刚我们对朴素贝叶斯算法的使用中，特征向量 $x_i$ 都是二值化的，其实特征向量也可以是多个离散值，比如 $\{1, 2, ..., k_i\}$ 这样也都是可以的。这时候只需要把对 $p(x_i|y)$ 的建模从伯努利分布改成多项式分布。实际上，即便一些原始的输入值是连续值（比如我们第一个案例中的房屋面积），也可以转换成一个小规模的离散值的集合，然后再使用朴素贝叶斯方法。例如，如果我们用特征向量 $x_i$ 来表示住房面积，那么就可以按照下面所示的方法来对这一变量进行离散化：

居住面积
离散值

这样，对于一个面积为 $890$ 平方英尺的房屋，就可以根据上面这个集合中对应的值来把特征向量的这一项的 $x_i$ 值设置为 $3$ 。然后就可以用朴素贝叶斯算法，并且将 $p(x_i|y)$ 作为多项式分布来进行建模，就都跟前面讲过的内容一样了。当原生的连续值的属性不太容易用一个多元正态分布来进行建模的时候，将其特征向量离散化然后使用朴素贝叶斯法（NB）来替代高斯判别分析法（GDA），通常能形成一个更好的分类器。

2.1 拉普拉斯平滑（Laplace smoothing）

刚刚讲过的朴素贝叶斯算法能够解决很多问题了，但还能对这种方法进行一点小调整来进一步提高效果，尤其是应对文本分类的情况。我们来简要讨论一下一个算法当前状态的一个问题，然后在讲一下如何解决这个问题。

还是考虑垃圾邮件分类的过程，设想你学完了CS229的课程，然后做了很棒的研究项目，之后你决定在 $2003$ 年 $6$ 月译者注：作者这讲义一定写得很早把自己的作品投稿到NIPS会议，这个NIPS是机器学习领域的一个顶级会议，递交论文的截止日期一般是六月末到七月初。你通过邮件来对这个会议进行了讨论，然后你也开始收到带有 nips 四个字母的信息。但这个是你第一个NIPS论文，而在此之前，你从来没有接到过任何带有 nips 这个单词的邮件；尤其重要的是，nips 这个单词就从来都没有出现在你的垃圾/正常邮件训练集里面。假如这个 nips 是你字典中的第 $35000$ 个单词，那么你的朴素贝叶斯垃圾邮件筛选器就要对参数 $\phi_{35000|y}$ 进行最大似然估计，如下所示：

$\begin{aligned} \phi_{35000|y=1} &= \frac{\sum^m_{i=1}1\{x^{(i)}_{35000}=1 \wedge y^{(i)}=1 \}}{\sum^m_{i=1}1\{y^{(i)}=0\}} &=0 \\ \phi_{35000|y=0} &= \frac{\sum^m_{i=1}1\{x^{(i)}_{35000}=1 \wedge y^{(i)}=0 \}}{\sum^m_{i=1}1\{y^{(i)}=0\}} &=0 \\ \end{aligned}$

也就是说，因为之前程序从来没有在别的垃圾邮件或者正常邮件的训练样本中看到过 nips 这个词，所以它就认为看到这个词出现在这两种邮件中的概率都是 $0$ 。因此当要决定一个包含 nips 这个单词的邮件是否为垃圾邮件的时候，他就检验这个类的后验概率，然后得到了：

$\begin{aligned} p(y=1|x) &= \frac{ \prod^n_{i=1} p(x_i|y=1)p(y=1) } {\prod^n_{i=1} p(x_i|y=1)p(y=1) +\prod^n_{i=1} p(x_i|y=0)p(y=0) }\\ &= \frac00\\ \end{aligned}$

这是因为对于" $\prod^n_{i=1} p(x_i|y)$ "中包含了 $p(x_{35000}|y) = 0$ 的都加了起来，也就还是 $0$ 。所以我们的算法得到的就是 $\frac00$ ，也就是不知道该做出怎么样的预测了。

然后进一步拓展一下这个问题，统计学上来说，只因为你在自己以前的有限的训练数据集中没见到过一件事，就估计这个事件的概率为零，这明显不是个好主意。假设问题是估计一个多项式随机变量 $z$ ，其取值范围在 $\{1,..., k\}$ 之内。接下来就可以用 $\phi_i = p (z = i)$ 来作为多项式参数。给定一个 $m$ 个独立观测 $\{z^{(1)}, ..., z^{(m)}\}$ 组成的集合，然后最大似然估计的形式如下：

$\phi_j=\frac{\sum^m_{i=1}1\{z^{(i)}=j\}}m$

正如咱们之前见到的，如果我们用这些最大似然估计，那么一些 $\phi_j$ 可能最终就是零了，这就是个问题了。要避免这个情况，咱们就可以引入拉普拉斯平滑（Laplace smoothing）， 这种方法把上面的估计替换成：

$\phi_j=\frac{\sum^m_{i=1}1\{z^{(i)}=j\}+1}{m+k}$

这里首先是对分子加 $1$ ，然后对分母加 $k$ ，要注意 $\sum^k_{j=1} \phi_j = 1$ 依然成立（自己检验一下），这是一个必须有的性质，因为 $\phi_j$ 是对概率的估计，然后所有的概率加到一起必然等于 $1$ 。另外对于所有的 $j$ 值，都有 $\phi_j \neq 0$ ，这就解决了刚刚的概率估计为零的问题了。在某些特定的条件下（相当强的假设条件下，arguably quite strong），可以发现拉普拉斯平滑还真能给出对参数 $\phi_j$ 的最佳估计（optimal estimator）。

回到我们的朴素贝叶斯分选器问题上，使用了拉普拉斯平滑之后，对参数的估计就写成了下面的形式：

$\begin{aligned} \phi_{j|y=1} & =\frac{\sum^m_{i=1}1\{x_j^{(i)}=1\wedge y ^{(i)}=1\}+1}{\sum^m_{i=1}1{\{y^{(i)}=1\}}+2}\\ \phi_{j|y=0} & =\frac{\sum^m_{i=1}1\{x_j^{(i)}=1\wedge y ^{(i)}=10\}+1}{\sum^m_{i=1}1{\{y^{(i)}=0\}}+2}\\ \end{aligned}$

（在实际应用中，通常是否对 $\phi_y$ 使用拉普拉斯并没有太大影响，因为通常我们会对每个垃圾邮件和非垃圾邮件都有一个合适的划分比例，所以 $\phi_y$ 会是对 $p(y = 1)$ 的一个合理估计，无论如何都会与零点有一定距离。）

2.2 针对文本分类的事件模型（Event models for text classification）

到这里就要给咱们关于生成学习算法的讨论进行一下收尾了，所以就接着讲一点关于文本分类方面的另一个模型。我们刚已经演示过的朴素贝叶斯方法能够解决很多分类问题了，不过还有另一个相关的算法，在针对文本的分类效果还要更好。

在针对文本进行分类的特定背景下，咱们上面讲的朴素贝叶斯方法使用的是一种叫做多元伯努利事件模型（Multi-Variate Bernoulli event model）。 在这个模型里面，我们假设邮件发送的方式，是随机确定的（根据先验类class priors， $p(y)$ ），无论是不是垃圾邮件发送者，他是否给你发下一封邮件都是随机决定的。那么发件人就会遍历词典，决定在邮件中是否包含某个单词 $i$ ，各个单词之间互相独立，并且服从概率分布 $p(x_i=1|y)=\phi_{i|y}$ 。因此，一条消息的概率为： $p(y)\prod^n_{i-1}p(x_i|y)$

然后还有另外一个模型，叫做多项式事件模型（Multinomial event model）。 要描述这个模型，我们需要使用一个不同的记号和特征集来表征各种邮件。设 $x_i$ 表示单词中的第 $i$ 个单词。因此， $x_i$ 现在就是一个整数，取值范围为 $\{1,...,|V|\}$ ，这里的 $|V|$ 是词汇列表（即字典）的长度。这样一个有 $n$ 个单词的邮件就可以表征为一个长度为 $n$ 的向量 $(x_1,x_2,...,x_n)$ ；这里要注意，不同的邮件内容， $n$ 的取值可以是不同的。例如，如果一个邮件的开头是"A NIPS . . ." ，那么 $x_1 = 1$ ("a" 是词典中的第一个)，而 $x_2 = 35000$ (这是假设 "nips"是词典中的第35000个)。

在多项式事件模型中，我们假设邮件的生成是通过一个随机过程的，而是否为垃圾邮件是首先决定的（根据 $p(y)$ ），这个和之前的模型假设一样。然后邮件的发送者写邮件首先是要生成从对单词 $(p(x_1|y))$ 的某种多项式分布中生成 $x_1$ 。然后第二步是独立于 $x_1$ 来生成 $x_2$ ，但也是从相同的多项式分布中来选取，然后是 $x_3$ , $x_4$ 等等，以此类推，直到生成了整个邮件中的所有的词。因此，一个邮件的总体概率就是 $p(y)\prod^n_{i=1}p(x_i|y)$ 。要注意这个方程看着和我们之前那个多元伯努利事件模型里面的邮件概率很相似，但实际上这里面的意义完全不同了。尤其是这里的 $x_i|y$ 现在是一个多项式分布了，而不是伯努利分布了。

我们新模型的参数还是 $\phi_y = p(y)$ ，这个跟以前一样，然后还有 $\phi_{k|y=1} = p(x_j =k|y=1)$ (对任何 $j$ )以及 $\phi_{i|y=0} =p(x_j =k|y=0)$ 。要注意这里我们已经假设了对于任何 $j$ 的值， $p(x_j|y)$ 这个概率都是相等的，也就是意味着在这个哪个词汇生成的这个分布不依赖这个词在邮件中的位置 $j$ 。

如果给定一个训练集 $\{(x^{(i)},y^{(i)}); i = 1, ..., m\}$ ，其中 $x^{(i)} = ( x^{(i)}_{1} , x^{(i)}_{2} ,..., x^{(i)}_{n_i})$ （这里的 $n$ 是在第 $i$ 个训练样本中的单词数目），那么这个数据的似然函数如下所示：

$\begin{aligned} \mathcal{L}(\phi,\phi_{k|y=0},\phi_{k|y=1})& = \prod^m_{i=1}p( x^{(i)},y^{(i)})\\ & = \prod^m_{i=1}(\prod^{n_i}_{j=1}p(x_j^{(i)}|y;\phi_{k|y=0},\phi_{k|y=1}))p( y^{(i)};\phi_y)\\ \end{aligned}$

让上面的这个函数最大化就可以产生对参数的最大似然估计：

$\begin{aligned} \phi_{k|y=1}&= \frac{\sum^m_{i=1}\sum^{n_i}_{j=1}1\{x_j^{(i)}=k\wedge y^{(i)}=1\}}{\sum^m_{i=1}1\{y^{(i)}=1\}n_i} \\ \phi_{k|y=0}&= \frac{\sum^m_{i=1}\sum^{n_i}_{j=1}1\{x_j^{(i)}=k\wedge y^{(i)}=0\}}{\sum^m_{i=1}1\{y^{(i)}=0\}n_i} \\ \phi_y&= \frac{\sum^m_{i=1}1\{y^{(i)}=1\}}{m}\\ \end{aligned}$

如果使用拉普拉斯平滑（实践中会用这个方法来提高性能）来估计 $\phi_{k|y=0}$ 和 $\phi_{k|y=1}$ ，就在分子上加1，然后分母上加 $|V|$ ，就得到了下面的等式：

$\begin{aligned} \phi_{k|y=1}&= \frac{\sum^m_{i=1}\sum^{n_i}_{j=1}1\{x_j^{(i)}=k\wedge y^{(i)}=1\}+1}{\sum^m_{i=1}1\{y^{(i)}=1\}n_i+|V|} \\ \phi_{k|y=0}&= \frac{\sum^m_{i=1}\sum^{n_i}_{j=1}1\{x_j^{(i)}=k\wedge y^{(i)}=0\}+1}{\sum^m_{i=1}1\{y^{(i)}=0\}n_i+|V|} \\ \end{aligned}$

当然了，这个并不见得就是一个最好的分类算法，不过朴素贝叶斯分选器通常用起来还都出乎意料地那么好。所以这个方法就是一个很好的"首发选择"，因为它很简单又很好实现。

上篇：ML3. 广义线性模型(Generalized Linear Models)
下篇：ML5. 支持向量机 (Support Vector Machine)

本文使用 Zhihu On VSCode 创作并发布

ML4. 生成学习算法(Generative Learning algorithms)

TIM

1 高斯判别分析（Gaussian discriminant analysis）

1.1 多元正态分布（multivariate normal distribution）

1.2 高斯判别分析模型（Gaussian Discriminant Analysis model）

1.3 讨论：高斯判别分析（GDA）与逻辑回归（logistic regression）

2 朴素贝叶斯法（Naive Bayes）

2.1 拉普拉斯平滑（Laplace smoothing）

2.2 针对文本分类的事件模型（Event models for text classification）

为你推荐

利用python实现逻辑回归（以鸢尾花数据为例）

行人重识别(2)——行人检测之HOG+SVM

深度学习PyTorch笔记（8）：线性代数

使用scikit-learn构建模型的万能模板（机器学习入门必看）

卷积神经网络（ResNet-18）识别Fashion-MNIST数据集（Pytorch版）

Rich feature hierarchies for accurate object detection and semantic segmentation(R-CNN)

关于作者

TIM

38

0

0

3

基于Matlab的机器人学习日志 -- 2

AMR1. Intro

Paper 9. Human-level control through deep reinforcement learning

相关推荐

机器学习算法之集成学习之模型融合

基于sklearn随机森林算法对鸢尾花数据进行分类

机器学习中的矩阵向量求导(五) 矩阵对矩阵的求导

Swin Transformer的继任者：Local Vision Transformer的革命

简单双向LSTM模型实战项目

浅析扩散模型与图像生成【应用篇】(二)——ADM

热门泡泡

30积分失眠，聊聊自己搞ROS的心得体会吧

ros学习路线

30积分 TF_REPEATED_DATA ignoring data错误

各位大佬，有什么ROS定位算法推荐吗

5积分想买能用ROS2的开发套件。或者开发板

5积分 ros中启动gazebo时报错

给作者打赏

ML4. 生成学习算法(Generative Learning algorithms)

TIM

1 高斯判别分析（Gaussian discriminant analysis）

1.1 多元正态分布（multivariate normal distribution）

1.2 高斯判别分析模型（Gaussian Discriminant Analysis model）

1.3 讨论：高斯判别分析（GDA）与逻辑回归（logistic regression）

2 朴素贝叶斯法（Naive Bayes）

2.1 拉普拉斯平滑（Laplace smoothing）

2.2 针对文本分类的事件模型（Event models for text classification）

为你推荐

利用python实现逻辑回归（以鸢尾花数据为例）

行人重识别(2)——行人检测之HOG+SVM

深度学习PyTorch笔记（8）：线性代数

使用scikit-learn构建模型的万能模板（机器学习入门必看）

卷积神经网络（ResNet-18）识别Fashion-MNIST数据集（Pytorch版）

Rich feature hierarchies for accurate object detection and semantic segmentation(R-CNN)

评论（0）

关于作者

TIM

38

0

0

3

基于Matlab的机器人学习日志 -- 2

AMR1. Intro

Paper 9. Human-level control through deep reinforcement learning

相关推荐

机器学习算法之集成学习之模型融合

基于sklearn随机森林算法对鸢尾花数据进行分类

机器学习中的矩阵向量求导(五) 矩阵对矩阵的求导

Swin Transformer的继任者：Local Vision Transformer的革命

简单双向LSTM模型实战项目

浅析扩散模型与图像生成【应用篇】(二)——ADM

热门泡泡

30积分 失眠，聊聊自己搞ROS的心得体会吧

ros学习路线

30积分 TF_REPEATED_DATA ignoring data错误

各位大佬，有什么ROS定位算法推荐吗

5积分 想买能用ROS2的开发套件。或者开发板

5积分 ros中启动gazebo时报错

给作者打赏

忘记密码

修改头像

添加你感兴趣的标签

举报类型（必选）

举报详情（选填）

30积分失眠，聊聊自己搞ROS的心得体会吧

5积分想买能用ROS2的开发套件。或者开发板