AndrewNg MachineLearning 学习笔记 05

第五课 生成学习算法

1. 摘要

本课的内容均是围绕生成学习算法。首先讲了生成学习算法的基本思路，之后具体讨论了一种特定的生成学习算法——高斯判别分析(GDA)，这里我们会插播一点多元高斯分布的内容，最后的朴素贝叶斯和拉普拉斯平滑都是对生成学习算法的完善和补充。

2. 生成学习算法

2.1 基本思路

首先回顾一下我们之前提到的分类算法，其思路都是让模型学习\(h_{\theta}(x) = P(y|x; \theta)\)或者直接让\(h_{\theta}(x)\)输出 0 或者 1，最后得到一个分类结果。我们可以从下图直观理解一下算法思路：

3. 高斯判别分析(GDA)

3.1 核心假设

高斯判别分析是生成学习算法的具体实践，为了求得\(P(x|y)\)，我们假设\(P(x|y)\)是服从高斯分布的。对于更一般的情况来说，参数向量\(X \in \mathbb{R}^n, P(X|Y) \sim \mathcal{N}(\vec{\mu}, \Sigma)\)。

3.2 多元高斯分布

如果某个多元随机变量\(x \in \mathbb{R}^n\)服从高斯分布，那么它的概率密度函数可以写成如下形式：

该分布包括均值\(\mu \in \mathbb{R}^n\)，以及协方差矩阵\(\Sigma \in \mathbb{R}^{n\times n}\)，按照定义，协方差矩阵可以写为

其实多元高斯分布和一元高斯分布的很多性质是类似的，我们在研究多元的性质时可以类比一元的性质，这样会容易理解得多。下面几个图片展示了二元高斯分布在不同均值及协方差矩阵之下的图形。

首先是均值为 0，协方差矩阵分别为\(I\)、\(0.6I\)、\(2I\)的多元高斯分布

下面依然是均值为 0 的高斯分布，但协方差矩阵分别为

最后，我们来看一下，协方差矩阵为单位阵，均值不同的高斯分布。

3.3 高斯判别分析模型

假设我们有一个分类问题，输出值 y 的只可能取 0 或者 1，或者说 y 是服从以\(\phi\)为参数伯努利分布的，同时输入值 x 是连续的随机变量，根据我们的核心假设，可以建立如下模型：
\begin{align}
y & \sim Bernoulli(\phi) \\
p(x|y = 0) & \sim \mathcal{N}(\mu_0, \Sigma) \\
p(x|y = 1) & \sim \mathcal{N}(\mu_1, \Sigma)
\end{align}
将它们的分布写出来：
\begin{align}
p(y) & = \phi^y(1 - \phi)^{1 - y} \\
p(x|y = 0) & = \frac{1}{(2\pi)^{n/2}\vert{\Sigma}\vert^{1/2}}exp(-\frac12(x - \mu_0)^T\Sigma^{-1}(x - \mu_0)) \\
p(x|y = 1) & = \frac{1}{(2\pi)^{n/2}\vert{\Sigma}\vert^{1/2}}exp(-\frac12(x - \mu_1)^T\Sigma^{-1}(x - \mu_1)) \\
\end{align}
这样我们模型的参数就由\(\phi\)、\(\mu_0\)、\(\mu_1\)、\(\Sigma\)组成(这里我们通常使用同样的协方差矩阵)。这样就可以写出其参数的对数似然函数：
\begin{align}
l(\phi, \mu_0, \mu_1, \Sigma) & = log\prod_{i = 1}^{m}p(x^{(i)}, y^{(i)}; \phi, \mu_0, \mu_1, \Sigma) \\
& = log\prod_{i = 1}^{m}p(x^{(i)}|y^{(i)}; \mu_0, \mu_1, \Sigma)p(y^{(i)}; \Sigma)
\end{align}

相比较我们之前写的似然函数，上面这个有个专门的名字叫做联合似然函数(Joint Likelihood)，之前的应该称为条件似然函数(Conditional Likelihood)。

为了使上面的似然函数 l 最大化，我们需要 4 个参数的最大似然估计，直接给出如下：
\begin{align}
\phi & = \frac{1}{m}\sum_{i = 1}^{m}1\{y^{(i)} = 1\} \\
\mu_0 & = \frac{\sum_{i = 1}^{m}1\{y^{(i)} = 0\}x^{(i)}}{\sum_{i = 1}^{m}1\{y^{(i)} = 0\}} \\
\mu_1 & = \frac{\sum_{i = 1}^{m}1\{y^{(i)} = 1\}x^{(i)}}{\sum_{i = 1}^{m}1\{y^{(i)} = 1\}} \\
\Sigma & = \frac{1}{m}\sum_{i = 1}^{m}(x^{(i)} - \mu_{y^{(i)}})(x^{(i)} - \mu_{y^{(i)}})^T
\end{align}

代入模型后，我们会得到如下这样的图像

3.4 高斯判别分析和 Logistics 回归的关系

我们之前在讨论 Logistics 回归的时候，也是画出过前面图片中一样的直线，来区分输出类别，显然高斯判别分析和 Logistics 回归有某种内在的联系。现在我们试用从 Logistics 的角度来看高斯判别分析，即考虑关于 x 的函数\(p(y = 1|x; \phi, \Sigma, \mu_0, \mu_1)\)，我们可以对其做一些数学上的变换，使其可以写为如下形式：
\begin{align}
p(y = 1|x; \phi, \Sigma, \mu_0, \mu_1) & = \frac{p(x|y = 1)p(y = 1)}{p(x)} \\
& = \frac{p(x|y = 1)p(y = 1)}{p(x|y = 1)p(y = 1) + p(x|y = 0)p(y = 0)} \\
& = \dots \\
& = \frac{1}{1 + exp(-\theta^{T}x)}
\end{align}
这里面的\(\theta\)是关于\(\phi, \Sigma, \mu_0, \mu_1\)的函数，这样的形式正是 Logistics 回归。
到这里我们自然会考虑一个问题：对于同样的数据，我们应该使用高斯判别分析还是 Logistics 回归？

上面的推导可以看出一些线索，我们从高斯判别分析可以推出 Logistics 回归的形式，说明高斯判别分析隐含着 Logistics 回归。更进一步说，高斯判别分析，对数据模型做出了 不弱于 Logistics 回归的假设。
但是该结论反过来并不成立，若数据服从如泊松分布，则我们得到的\(p(y = 1|x)\)同样是一个 Sigmoid 函数。

现在再回头考虑我们的问题，既然高斯判别分析对数据作出了更强的假设，而且从事实上数据的确是服从高斯分布的，那么我们在训练的时候，显然选择高斯判别分析一定事半功倍。我们可以用更少的数据训练出更好的模型，因为我们利用了数据集更多的特点。但反过来，如果我们一开始的假设是错误的(比如数据实际是服从泊松分布)，那么 Logistics 回归应该是更为正确的，换句话说，Logistics 回归对数据的假设并不敏感，具有更强的鲁棒性(robust)。

4. 朴素贝叶斯模型

前面我们讨论的高斯判别分析，其输入是一个在实数域连续变化的向量，下面我们说说输入向量是离散值的情况。

我们先考虑这样一个应用场景：我们要做一个垃圾邮件分类器，把收到的邮件自动归为垃圾或非垃圾邮件。这类问题我们也称为 文本分类。在最开始，我们已经获得了一些被人工标记为垃圾或非垃圾的邮件，接下来的问题就是，我们如何用一个特征向量表示一封邮件。
下面就是我们使用的办法，用一个词典向量来表示一封右键。如果邮件包含词典中第 i 个词语，那我们就设置向量第 i 个位置的元素为 1。比如下面这样：

如上所示，说明我们的 email 中包含 a 和 buy 这两个词语并且不包括 aardvark、aardwolf 和 zygmurgy。因此我们的输入参数 x 是一个 n 维向量，这个 n 就是上述词典的大小(n 的值可能为几千至上万)。如果我们使用多项式分布，对\(p(x|y)\)进行建模，那么所有可能的情况就会有\(2^n\)种，对应\(2^n - 1\)个参数，这是完全不可想象的。因此我们需要对模型做一个很强的假设：

对于给定的 y，\(x_i\)之间条件独立。

上面的假设称为 朴素贝叶斯假设，该假设保证了下面式子的成立：
\begin{align}
& p(x_1, x_2, \ldots, x_n | y) \\
= \quad & p(x_1 | y)p(x_2 | y, x_1)p(x_3 | y, x_1, x_2) \cdots p(x_n | y, x_1, \ldots, x_{n - 1}) & \text{应用概率链式法则} \\
= \quad & p(x_1 | y)p(x_2 | y) \cdots p(x_n | y) & \text{应用前面的假设} \\
= \quad & \prod_{i = 1}^n{p(x_i | y)}
\end{align}
用通俗的话来解释一下，即给定一个已知垃圾或非垃圾的邮件，在该邮件中，单词'a'出现的概率并不会影响'aardvark'、'buy'或'zygmurgy'出现的概率。从另一个角度讲，对于前面给定的邮件，已知某个单词出现的概率并不能帮助我们推测其它单词在这封邮件中出现的概率。这个假设显然是不符合语言常识的，比如在邮件里我们发现了“彩票”字样，那么在邮件中就很可能出现“赔率”、“盘口”等词语，但是在众多情况下，朴素贝叶斯分类依然是一个很有效的算法。

我们的模型有三个参数：\( \phi_{i|y=1} = p(x_i|y=1)\)，\( \phi_{i|y=0} = p(x_i|y=0)\)和\( \phi_y = p(y=1)\)，可以写出似然函数如下：

对于参数的最大似然估计为：
\begin{align}
\phi_{j|y=1} & = \frac{\sum_{i=1}^m 1\{x_j^{(i)}=1 \land y^{(i)} = 1\}}{\sum_i^m 1\{y^{(i)} = 1\}} \\
\phi_{j|y=0} & = \frac{\sum_{i = 1}^m 1\{x_j^{(i)}=1 \land y^{(i)} = 0\}}{\sum_i^m 1\{y^{(i)} = 0\}} \\
\phi_{y=1} & = \frac{\sum_{i = 1}^m 1\{y^{(i)} = 1\}}{m}
\end{align}

其实上面的三个参数有很明显的现实意义，比如\(\phi_{j|y=1}\)就代表着在垃圾邮件中，词典中第 j 个单词出现的比例。
对于一个生成学习算法来说，关键的部分就是对于\(p(x|y)\)和\(p(y)\)进行估计，然后应用贝叶斯公式。因此有了上面三个参数，我们就可以写出这个垃圾邮件分类器的贝叶斯公式了。
\begin{align}
p(y = 1|x) & = \frac{p(x|y = 1)p(y = 1)}{p(x)} \\
& = \frac{p(x|y = 1)p(y = 1)}{p(x|y = 1)p(y = 1) + p(x|y = 0)p(y = 0)} \\
& = \frac{(\prod_{i=1}^n{p(x_i|y = 1)})p(y = 1)}{(\prod_{i=1}^n{p(x_i|y = 1)})p(y = 1) + (\prod_{i=1}^n{p(x_i|y = 0)})p(y = 0)}
\end{align}
至此，我们就完成了一个以生成学习算法为基础的垃圾邮件分类器。

4.1 拉普拉斯平滑(Laplace Smoothing)

我们前面用生成学习算法完成了一个垃圾邮件分类器，但这个分类器有一个很重大的缺陷。比如说，我的邮箱有一天突然收到了一封 gakki 寄来的邮件，说她的婚礼上还缺一个新郎问我想不想去，可是对于一个理工男来说，在之前的邮件里从来没有出现过婚礼这个词，这样一来，我们的垃圾邮件分类器就犯难了，假设"婚礼"这个词是我们词典中第 520 个词，根据我们前面写出的参数及公式：
\begin{align}
\phi_{520|y=1} & = \frac{\sum_{i = 1}^m 1\{x_{520}^{(i)}=1 \land y^{(i)} = 1\}}{\sum_i^m 1\{y^{(i)} = 1\}} = 0 \\
\phi_{520|y=0} & = \frac{\sum_{i = 1}^m 1\{x_{520}^{(i)}=1 \land y^{(i)} = 0\}}{\sum_i^m 1\{y^{(i)} = 0\}} = 0 \\
\end{align}
这两个参数表达的意义本来是，第 520 个词在垃圾及非垃圾邮件中出现的频率。可现在的情况是，之前的邮件中从没出现过这个词，因此参数的结果都为 0。如果把这样的参数代入公式，就会得到如下结果：

因为\(\prod_{i=1}^n{p(x_i|y = 1)}\)中含有\(\phi_{520|y=1}\)这一项，故该乘积恒为 0，\(\prod_{i=1}^n{p(x_i|y = 1)}\)同理，从而导致了上面的预测的概率为\(\frac{0}{0}\)，说直白一点就是可能得到任何结果。

为了避免上面的情况，我们就需要 拉普拉斯平滑来修正这个问题。

拉普拉斯平滑的用法非常简单，举个例子：假设国足在过去 5 场比赛中全部输球，现在我们要预测第六场国足获胜的概率。因此根据我们的样本，国足获胜的概率为

这显然不是一个很好的预测（而且很不得人心），即使国足再怎么输球，我们也不能预测说下一场国足取胜的概率就是 0。因此我们使用拉普拉斯平滑对上面的公式做一个修正：

这样还算是一个皆大欢喜的结果，虽然可能性很小但不是完全不可能。当然如果目标结果并不是二元值而是 k 种可能，那么在分母部分只要加上 k 就好了。个人对拉普拉斯平滑的粗浅理解就是为每种可能的结果预先引入了一个相等的概率，其最终目的还是为了防止过拟合。