StanFord 机器学习公开课笔记(4):生成学习算法

作者: v1gor | 来源:发表于2019-11-02 14:06 被阅读0次

生成学习算法

生成学习算法和判别学习算法的区别

判别学习算法(Discriminative)

我们之前学习过Logistic算法来解决分类问题，回想一下分类过程：我们使用所有训练样本训练出一个函数, $h_\theta(x)$ 之后若要预测一个样本的类别，只需要将这个样本的特征作为得到的函数 $h_\theta(x)$ 的输入，看看输出是啥即可。类似这样的分类方法，称为判别学习算法，判别学习算法一般有以下两种类型：

直接学习 $P(y|x)$ 。给出一个 $x$ ，得到 $p(y|x)$ 的值，接着比较 $y=1$ 和 $y = 0$ 时 $P(y|x)$ 的值的大小，就能够判定x的类别。
或直接学习一个算法 $h_\theta(x)\in \{0,1\}$ ，就和之前的logistic分类一样。

生成学习算法(Generative)

以二分类问题为例：假设我们需要对一组癌症肿瘤样本进行分类，得到一个能够区分良性肿瘤和恶性肿瘤的算法。在生成学习算法的思路中，不是直接用样本去拟合一个函数 $h_\theta(x)$ 来预测新的输入的类别，而是分别对训练样本中的良性样本和恶性样本进行拟合，得到两个模型，接着当需要预测一个新肿瘤样本的类别的时候，就用新样本的特征数据分别输入两个模型中，哪个模型的拟合程度高，就认为新样本属于哪个类别。

形式化地说，生成学习算法对 $P(x|y)$ 和 $P(y)$ 进行建模，接着通过贝叶斯公式计算出 $P(y=1|x) = \frac{P(x|y=1)P(y=1)}{P(x)}$ ，式中的 $P(x)$ 可以通过 $P(x) = P(y=1|x)P(x) + P(y = 0|x)P(x)$ 计算出。

生成学习算法的例子——高斯判别分析

假设 $x \in R$ 且是一个连续值，高斯判别分析要求 $P(x|y)$ 符合高斯分布。

多元（高维）高斯分布：是一维高斯分布的推广， $Z \sim N(\vec{\mu},\Sigma)$ 其中随机变量Z是符合高维高斯分布的一个高维向量， $\Sigma = E[(x-\mu)(x-\mu)^T]$ 是协方差矩阵， $\vec{\mu}$ 是高斯分布的均值。这样高维高斯分布的概率密度公式就是 $P(z) = \frac{1}{(2\pi)^{\frac{n}{2}}|\Sigma|^{\frac{1}{2}}}exp(-\frac{1}{2}(x-\mu)^T\Sigma^{-1}(x-\mu))$ 这个公式不需要记，但是需要知道 $\Sigma$ 和 $\mu$ 的含义以及它们对高斯分布图像的影响。

补充：协方差矩阵的知识

$\Sigma$ 是单位矩阵， $\mu$ 是零向量

此时的图像一般被认为是标准图像：

markdown-img-paste-20180219191046886.png

减小 $\Sigma$ 中对角线的值

实际上是减小了各个维度上随机变量的方差，因此各维数据都更加聚集，图像整体更加“瘦长”：

markdown-img-paste-20180219191206622.png

增大 $\Sigma$ 中对角线的值

实际上是增大了各个维度上随机变量的方差，因此各维数据都更加分散，图像整体更加“矮胖”：

markdown-img-paste-20180219191217656.png

增加非主对角线上的元素值

实际上增加了各维随机变量的关联性：

0.5

markdown-img-paste-20180219191228252.png
0.8

markdown-img-paste-20180219191236964.png

减小非主对角线上的元素值

实际上增加了各维变量的关联性（另一个方向）

markdown-img-paste-20180219191312455.png

改变 $\mu$ 的值

实际上改变了图像的位置

markdown-img-paste-20180219191341901.png

用高斯判别分析来分类两种肿瘤样本

俯视图：

markdown-img-paste-20180220101707480.png

这个分割线和Logistic方法梯度上升得出的分割线的斜率有些不同，接下来介绍高斯判别分布的具体过程。

$P(y)$ 符合伯努利分布

因此 $P(y) = \phi^y(1-\phi)^{(1-y)}$
$P(x|y)$ 符合高斯分布

因此 $P(x|y = 0) = \frac{1}{(2\pi)^{\frac{n}{2}}|\Sigma|^{\frac{1}{2}}}exp(-\frac{1}{2}(x-\mu_0)^T\Sigma^{-1}(x-\mu_0))$

$P(x|y = 1) = \frac{1}{(2\pi)^{\frac{n}{2}}|\Sigma|^{\frac{1}{2}}}exp(-\frac{1}{2}(x-\mu_1)^T\Sigma^{-1}(x-\mu_1))$
联合似然性(joint likelyhood)

$\begin{align} l(\phi,\mu_0,\mu_1,\Sigma)& = log\Pi^m_{i=1}P(x^{(i)},y^{(i)})\\ &=log\Pi^m_{i=1}P(x^{(i)}|y^{(i)})P(y^{(i)}) \end{align}$

上述公式中，我们的似然性公式中的每一个因子是 $P(x^{(i)},y^{(i)})$ 是联合分布，因此这个式子称为"联合似然性"公式，而在判别学习算法（如Logistic）中，我们的似然公式如下：

$l(\theta) = log\Pi^{m}_{i=1}P(x^{(i)}|y^{(i)};\theta)$

这个式子中的每个因子为 $P(x^{(i)}|y^{(i)};\theta)$ ,因此这个似然公式称为“条件似然公式(conditional likelyhood)”

现在，假设给定m个样本，我们开始具体的建模和预测过程：

根据训练样本数据计算出极大似然分布参数 $\phi,\mu_0,\mu_1,\Sigma$

$\phi = \frac{\Sigma^{m}_{i=1}I\{y^{(i)}=1\}}{m}$
$\mu_0 = \frac{\Sigma^{m}_{i=1}I\{y^{(i)}=0\}x^{(i)}}{\Sigma^{m}_{i=1}I\{y^{(i)}=0\}}$

实质上计算的是所有非恶性肿瘤样本 $x$ 的特征的均值。
$\mu_1 = \frac{\Sigma^{m}_{i=1}I\{y^{(i)}=1\}x^{(i)}}{\Sigma^{m}_{i=1}I\{y^{(i)}=1\}}$

实质上计算的是所有恶性肿瘤样本 $x$ 的特征的均值。
$\Sigma = \frac{1}{m}\Sigma^{m}_{i=1}(x^{(i)}-\mu_{y^{(i)}})(x^{(i)}-\mu_{y^{(i)}})^T$

将这些公式及具体的样本数据代入，就能计算出 $l(\phi,\mu_0,\mu_1,\Sigma)$ 。

根据 $\phi,\mu_0,\mu_1,\Sigma$ 进行预测

$\begin{align} arg\; max_yP(y|x) & = arg\;max_y\frac{P(x|y)P(y)}{P(x)}\\ & = arg \;max_yP(x|y)P(y) \end{align}$

上式中的 $arg\;max_yP(y|x)$ 的含义是：使得 $p(y|x)$ 的值最大的 $y$ 。由于 $p(x)$ 的值与 $y$ 无关，所以上式化简了分母 $P(x)$

如果y是均匀分布的，也就是取得每种类别的概率都相同，那么上式可以继续化简：

$arg\; max_yP(y|x) = arg \;max_yP(x|y)$

这种情况并不常见，因此多数使用的还是式子： $arg\; max_yP(y|x) = arg \;max_yP(x|y)P(y)$

而 $P(x|y)P(y)$ 已经由训练样本数据拟合出来，因此只需要代入要预测的样本特征 $x$ ,求出 $arg \;max_yP(x|y)P(y)$ 即可。

具体求解方法视频和讲义中都没讲，我认为应该是将要预测的 $x$ 代入之前推得的 $P(x|y = 1)$ 和 $P(x|y=0)$ 的表达式中（此时表达式的参数已经由极大似然估计求得），之后比较大小即可。

高斯判别分析和Logistic的关系

一个有趣的事情是，如果你将 $P(y=1|x;\phi,\mu_0,\mu_1,\Sigma)$ 看做是 $x$ 的函数，那么这个函数将能够用 $P(y=1|x;\phi,\mu_0,\mu_1,\Sigma) = \frac{1}{1+exp(-\theta^Tx)}$ 表示，这和sigmod函数的表达式是一致的。但是高斯判别分析（GDA）和Logstic方法得到的两个函数的图像是不一样的（虽然它们的形式是一样的）。

注：根据贝叶斯公式，

$\begin{align} P(y=1|x;\phi,\mu_0,\mu_1,\Sigma)&=\frac{P(x|y=1;\phi,\mu_0,\mu_1,\Sigma)P(y=1)}{P(x)}\\ &= \frac{P(x|y=1;\phi,\mu_0,\mu_1,\Sigma)P(y=1)}{P(x|y=1)P(y=1)+P(x|y=0)P(y=0)} \end{align}$

而右式中的所有式子的参数都已经用训练样本拟合出来，因此可以计算出左式的数学表达式，发现计算结果是一个sigmod具有相同形式的函数。

生成学习算法和判别学习方法的权衡

正如上一节提及的，在高斯判别分析中，我们假设 $x|y$ 符合高斯分布，从而得出一个结论（没有提供证明）： $P(y=1|x)$ 的分布函数符合logistic后验分布函数 $\frac{1}{1+exp(-\theta^Tx)}$ 。

其实，不仅是高斯分布，如果 $x|y=0$ 和 $x|y=1$ 都符合泊松分布，上述结论仍然成立，即 $P(y=1|x) = \frac{1}{1+exp(-\theta^Tx)}$

实际上有更一般的结论：如果 $x|y=0 \sim ExpFamily(\eta_0)$ 且 $x|y=1 \sim ExpFamily(\eta_1)$ ，则 $P(y=1|x)$ 是logistic函数。这其实反过来印证了logistic函数的鲁棒性，因为它能够较好地拟合指数分布族能够表示的分布的数据。

生成学习算法的优势

在已知 $x|y$ 符合哪种分布的情况下，使用生成学习算法的效果往往比使用判别学习算法的效果好。以高斯判别分析为例，它假设 $x|y$ 符合高斯分布，且之前的结论告诉我们在这个假设下推导出的 $P(y=1|x)$ 是符合logistic函数形式的；因此可以认为生成学习算法使用了比判别学习算法更强的假设，因此更加具有针对性，如果使用了正确的分布模型（比如对一个组 $x|y$ 符合或近似符合高斯分布的样本使用高斯判别分布），那么将会得到比判别分析更好的效果。反之，如果不知道 $x|y$ 符合哪种分布，那么具有更加弱的假设的判别学习算法将很有可能得到更好的效果。
生成学习算法需要更少的数据来拟合模型。这仍然是因为判别学习算法做了更弱的假设，因此如果要拟合出和生成学习算法同等效果的模型（假设生成学习算法选用了正确的分布），判别学习算法需要更多的数据来保证模型的鲁棒性。

另一个生成学习算法——朴素贝叶斯(Naive Bayes)

使用朴素贝叶斯算法来区分垃圾邮件

特征选择

我们使用一个代表单词列表的位向量来描述邮件，如

markdown-img-paste-20180221101839571.png

向量中的每一个元素代表了一封邮件中是否出现对应的单词。这个列表可以通过读取大量近期邮件（如近两个月的邮件）的内容来获得。

判别学习算法不可取

现在我们说明拟合出一个函数 $h_\theta(x)$ 来作为判定函数是不可取的：

特征选择的方式决定了特征向量 $x$ 的维数是很大的（一般是50000这个数量级），因此 $x$ 共有 $2^{50000}$ 种可能的取值。如果使用多项式分布（这是比较适合这个问题的概率分布）来拟合，则需要拟合 $2^{50000} - 1$ 个参数，这是很难的，因此需要令求捷径来解决这个问题。

注：和由伯努利分布推导出sigmod函数的推导过程一样，多项式分布的函数也可以通过指数分布族自然推出（具体过程在上一讲的讲义中）

生成学习算法——朴素贝叶斯假设

为了解决这个问题，我们需要做出一个很强的假设：

朴素贝叶斯假设：对给定的 $y$ , $x$ 是条件独立的。

根据概率论的链式法则(注意这个式子没有用到任何假设)：

$P(x_1,x_2...,x_n|y) = P(x_1|y)P(x_2|y,x_1)P(x_3|y,x_1,x_2)...$

使用贝叶斯假设之后：

$\begin{align} P(x_1,x_2...,x_{50000}|y) &= P(x_1|y)P(x_2|y)P(x_3|y)...\\ &=\Pi^{50000}_{i=1}P(x_i|y) \end{align}$

贝叶斯假设通俗来讲就是：不论一封邮件是不是垃圾邮件，那单词之间出现的概率都不会相互影响，比如单词"a"的出现将不会影响单词"buy"出现的概率。也就是在你了解了一封邮件是不是垃圾邮件的前提下，知道其中的一部分词汇并不会帮助你预测其中可能出现的其他词汇。

这个假设是不可能成立的，因为一封垃圾邮件中出现"csapp"的概率显然比出现"buy"的概率要小得多；如果一封邮件中出现了"cs299",那么邮件中很有可能会出现这个课程的老师或助教的名字。

虽然这个假设字面上是错误的，但是它在文本、邮件、网页内容的分类上的效果是非常好的（这就很神奇:O）

开始建模

这个模型的参数如下：

$\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)$

接着写出联合似然分布的表达式：

$L(\phi_y,\phi_{i|y=1},\phi_{i|y=0}) = \Pi^m_{i=1}P(x^{(i)},y^{(i)})$

用训练样本数据拟合出使得上式取最大值的参数：

$\phi_y = \frac{\Sigma^{m}_{i=1} I\{y^{(i)}=1\}}{m}$

$\phi_{j|y=0} = \frac{\Sigma^{m}_{i=1}I\{y^{(i)} = 0,x_j^{(i)} = 1\}}{\Sigma^{m}_{i=1}I\{y^{(i)} = 0\}}$

$\phi_{j|y=1} = \frac{\Sigma^{m}_{i=1}I\{y^{(i)} = 1,x_j^{(i)} = 1\}}{\Sigma^{m}_{i=1}I\{y^{(i)} = 1\}}$

上面第三个式子的含义是：遍历每个垃圾邮件，统计其中出现单词列表中第 $j$ 个单词的邮件的频率； $\phi_{j|y=1}$ 的含义就是垃圾邮件中包含单词列表中第j个单词的邮件的概率。

进行预测

接下来根据得到的参数来预测新样本的类别：

首先在贝叶斯假设的前提下计算：
$\begin{align} P(x_1,x_2...,x_{50000}|y=0) &= \Pi^{50000}_{i=1}P(x_i|y=0)\\ &= \Pi^{50000}_{i=1}\phi_{i|y=0}^{x_i}(1-\phi_{i|y=0})^{(1-x_i)} \end{align}$

然后计算：

$\begin{align} P(x_1,x_2...,x_{50000}|y=1) &= \Pi^{50000}_{i=1}P(x_i|y=1)\\ &= \Pi^{50000}_{i=1}\phi_{i|y=1}^{x_i}(1-\phi_{i|y=1})^{(1-x_i)} \end{align}$

比较上述两式的结果，哪个大，新样本就属于哪一类。

拉普拉斯平滑(Laplace Smoothing)

上面介绍的贝叶斯分类器存在一个问题：

在判定一个新样本的类别时，如果这个新样本中出现了一个训练样本中从未出现过的词，比如"NIPS",那么根据链式法则和贝叶斯假设：

$\begin{align} P(y=0|x) &= \frac{P(x|y=0)P(y=0)}{P(x)}\\ &=\frac{\Pi^{50000}_{i=1}P(x_i|y=0)P(y=0)}{P(x|y=0)P(y=0)+P(x|y=1)P(y=1)} \end{align}$
$\begin{align} P(y=1|x) &= \frac{P(x|y=1)P(y=1)}{P(x)}\\ &=\frac{\Pi^{50000}_{i=1}P(x_i|y=1)P(y=1)}{P(x|y=0)P(y=0)+P(x|y=1)P(y=1)} \end{align}$

假设“NIPS”是词典中的第30000个词，那么根据极大似然估计得到的参数：

$\phi_{30000|y=0} = 0$

$\phi_{30000|y=1} = 0$

因此 $P(y=0|x) = P(y=1|x) = \frac{0}{0+0}$

这是个未定义的值。也就是说，如果新的样本中出现了一个之前没有出现过的词，那么这个词不论在垃圾邮件还是非垃圾邮件中出现的概率都是0，这时贝叶斯分类器将会无法正确判定这个样本属于哪个类别。

这是因为用训练样本拟合参数时，我们仅仅因为训练样本数据中没有出现过某个词，就认为未来出现这个词的概率为0，这显然是不合理的。

因此需要一种方式来修正参数，那就是Laplace平滑：

之前我们使用公式

$\phi_y = \frac{\Sigma^{m}_{i=1} I\{y^{(i)}=1\}}{\Sigma^{m}_{i=1} I\{y^{(i)}=1\} + \Sigma^{m}_{i=1} I\{y^{(i)}=0\}}$

来预测 $\phi_y$ ，如果 $\Sigma^{m}_{i=1} I\{y^{(i)}=1\} = 0$ , $\Sigma^{m}_{i=1} I\{y^{(i)}=0\} = 5$ 那么 $\phi_y = \frac{0}{0+5} = 0$

也就是说如果训练样本中没有垃圾邮件，那么贝叶斯分类器将会认为未来出现垃圾邮件的概率也是0。

在Laplace平滑中，改用下面的方法计算：

$\phi_y = \frac{1+\Sigma^{m}_{i=1} I\{y^{(i)}=1\}}{1+\Sigma^{m}_{i=1} I\{y^{(i)}=1\} + 1+\Sigma^{m}_{i=1} I\{y^{(i)}=0\}} = \frac{1+\Sigma^{m}_{i=1}I\{y^{(i)}=1\}}{m+2}$

这样，在上述同等情况下， $\phi_y$ 的值就变为：

$\phi_y = \frac{0+1}{0+1+5+1} = \frac{1}{7}$

这显然是一个更合理的参数，因为训练样本中未出现垃圾邮件，所以我们预测接下来出现垃圾邮件的概率较小（而不是0）.

同理，对其它参数也应用Laplace平滑：

$\phi_{j|y=0} = \frac{1+\Sigma^{m}_{i=1}I\{y^{(i)} = 0,x_j^{(i)} = 1\}}{2+\Sigma^{m}_{i=1}I\{y^{(i)} = 0\}}$

$\phi_{j|y=1} = \frac{\Sigma^{m}_{i=1}I\{y^{(i)} = 1,x_j^{(i)} = 1\}+1}{2+\Sigma^{m}_{i=1}I\{y^{(i)} = 1\}}$

贝叶斯分类中的Laplace平滑的过程总结来说就是分子的每一项加上1，分母加上总的类别数。

StanFord 机器学习公开课笔记(4):生成学习算法

生成学习算法

生成学习算法和判别学习算法的区别

判别学习算法(Discriminative)

生成学习算法(Generative)

生成学习算法的例子——高斯判别分析

$\Sigma$ 是单位矩阵， $\mu$ 是零向量

减小 $\Sigma$ 中对角线的值

增大 $\Sigma$ 中对角线的值

增加非主对角线上的元素值

减小非主对角线上的元素值

改变 $\mu$ 的值

用高斯判别分析来分类两种肿瘤样本

根据训练样本数据计算出极大似然分布参数 $\phi,\mu_0,\mu_1,\Sigma$

根据 $\phi,\mu_0,\mu_1,\Sigma$ 进行预测

高斯判别分析和Logistic的关系

生成学习算法和判别学习方法的权衡

生成学习算法的优势

另一个生成学习算法——朴素贝叶斯(Naive Bayes)

使用朴素贝叶斯算法来区分垃圾邮件

特征选择

判别学习算法不可取

生成学习算法——朴素贝叶斯假设

开始建模

进行预测

拉普拉斯平滑(Laplace Smoothing)

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

StanFord 机器学习公开课笔记(4):生成学习算法

生成学习算法

生成学习算法和判别学习算法的区别

判别学习算法(Discriminative)

生成学习算法(Generative)

生成学习算法的例子——高斯判别分析

是单位矩阵， 是零向量

减小 中对角线的值

增大 中对角线的值

增加非主对角线上的元素值

减小非主对角线上的元素值

改变 的值

用高斯判别分析来分类两种肿瘤样本

根据训练样本数据计算出极大似然分布参数

根据 进行预测

高斯判别分析和Logistic的关系

生成学习算法和判别学习方法的权衡

生成学习算法的优势

另一个生成学习算法——朴素贝叶斯(Naive Bayes)

使用朴素贝叶斯算法来区分垃圾邮件

特征选择

判别学习算法不可取

生成学习算法——朴素贝叶斯假设

开始建模

进行预测

拉普拉斯平滑(Laplace Smoothing)

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

$\Sigma$ 是单位矩阵， $\mu$ 是零向量

减小 $\Sigma$ 中对角线的值

增大 $\Sigma$ 中对角线的值

改变 $\mu$ 的值

根据训练样本数据计算出极大似然分布参数 $\phi,\mu_0,\mu_1,\Sigma$

根据 $\phi,\mu_0,\mu_1,\Sigma$ 进行预测