斯坦福229：机器学习【P5 GDA & Naive Bayes】¶

关键词：生成学习算法（Generative Learning Algorithms），高斯判别分析（Gaussian Discriminiant Analysis）,

回顾与引入¶

如果您有一个有两类的数据集，那么一个区别算法类似逻辑回归的做法是找到一条线来分割两类测试数据。比如你随机初始化一条分界线，然后对每一个不符合分割结果的示例做出调整，最后你就会得到一条标准的决策边界。也就是说逻辑回归本质上就是在寻找这个决策边界。

生成学习算法¶

然而现在我们有一种新的算法，并不是在寻找这个决策边界。我们称之为生成学习算法，相反这个算法每次检查一个类，对这个类所拥有的特点进行总结与归纳。在预测的过程中，我们们将需要预测的数据尝试归类到某一类中，依次给出我们的猜测。

也就是说在我们以往的学习过程中，是给定了数据集的 \(X\) 后通过学习调整 \(\Theta\) 来让 \(P(\hat y|X;\Theta)\) 有最大值。而现在我们提出的生成学习算法则是在给定了分类的类 \(Y\) 后尝试通过学习调整 \(\Theta\) 来得知 \(X\) 具有什么样的特征，也就是获得 \(P(X|y;\Theta)\) .同时，生成学习算法还会学习 \(P(y)\) .这个概率的意义是，在测试阶段，当你对于还没有任何信息的 \(X\)，你已经有的一个预测概率。比如一个刚进入门诊室的病人有良性肿瘤或恶性肿瘤的概率。

根据贝叶斯规则，如果你可以计算 \(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)} \end{align} \]

因此，在测试阶段，如果我们已知了 \(P(X|y),P(y)\) ，给出了 \(X\) 之后，可以根据这个公式来计算得到结果是 1 的概率有多大。

这就是我们用来后见生成学习算法的框架。接下来你将看到两种生成学习算法的示例，一个是用于连续增长的特征，一个适用于离散的特征。

高斯判别分布（GDA）¶

高斯判别分析算法是一种生成学习算法。他针对 \(X\) 连续增长， \(y\) 是伯努利分布只取 0 或 1，且 \(P(X|y)\) 满足多维正态分布的情况。

一些假设和定义¶

假设 \(x \in \Bbb R^n\)，并且我们在这里忘记 \(x_0=1\) 的假设，所以现在的特征维度是 n 而不是 n+1。

再假设 \(P(X|y)\) 服从高斯分布。

补充一下多元高斯分布的定义：

\[ \begin{gather} if\ z\in\mathcal N(\overrightarrow\mu,\Sigma),as\ well\ z\in \Bbb R^n\\ \overrightarrow\mu\in\Bbb R^n,\Sigma\in \Bbb R^{n×n}\\ 均值:E[z]=\overrightarrow\mu\\ 协方差矩阵:Cov[z]=E[(z-\mu)(z-\mu)^T]=E[zz^T]-\mu\mu^T\\ P(z)=\frac1{(2\pi)^{\frac n2}|\Sigma|^{\frac12}}exp(-\frac12(x-\mu)^T\Sigma^{-1}(x-\mu)) \end{gather} \]

在多元高斯的定义中，要求协方差矩阵是对称的正定矩阵。事实上对于任意随机向量的协方差矩阵都会是一个对称的半正定矩阵。

事实上最后这条概率式子很多人都记不住，大家都是用到的时候再看看的（Andrew Ng）

对于一个 \(\mu=[0,0]^T\) 的二元高斯分布，我们可以发现图像的最高点就是坐标 \((0,0)\) 处。而当协方差矩阵 \(\Sigma=\begin{bmatrix}1&0\\0&1\end{bmatrix}\) 是二阶单位矩阵，这就称为标准二元高斯分布如果我们给协方差乘上一个小于1的系数，那么这个二元高斯分布的可变性就会变小，同时峰值会有一定增加，因为他还是一个概率密度函数，所以他的积分值仍然是1。

如果我们改变的是 \(\Sigma\) 非对角线上的值为 \(\Sigma=\begin{bmatrix}1&0.8\\0.8&1\end{bmatrix}\) ，那么图形将会发生如下变化：

当我们用类似等高线的方式表示时， \(\Sigma=\begin{bmatrix}1&0\\0&1\end{bmatrix}\) 对应的就是几个完美的同心圆，而 \(\Sigma=\begin{bmatrix}1&0.8\\0.8&1\end{bmatrix}\) 看上去则会是几个同心椭圆，并且两个特征 \(x_1\) 和 \(x_2\) 呈正相关。若 \(\Sigma=\begin{bmatrix}1&-0.8\\-0.8&1\end{bmatrix}\) 则两个特征则会呈现负相关。

回归正题，根据假设有：

\[ \begin{gather} P(X|y=0)=\frac1{(2\pi)^{\frac n2}|\Sigma|^{\frac12}}exp(-\frac12(X-\mu_0)^T\Sigma^{-1}(X-\mu_0))\\ P(X|y=1)=\frac1{(2\pi)^{\frac n2}|\Sigma|^{\frac12}}exp(-\frac12(X-\mu_1)^T\Sigma^{-1}(X-\mu_1)) \end{gather} \]

对于两种情况，我们有相同的 \(\Sigma\) 和不同的 \(\mu\) .随后我们再给出 \(y\) 的概率密度函数。因为 \(y\) 服从伯努利分布，所以：

\[ P(y)=\phi^y(1-\phi)^{(1-y)} \]

至此，我们有了四个参数： \(\mu_0,\mu_1\in\Bbb R^n\) ， \(\Sigma\in\Bbb R^{n×n}\) ， \(\phi\in[0,1]\) .

推导过程¶

为了拟合这些参数，我们所要做的就是获得最大的联合似然性(\(Joint Likelihood\))：

\[ \begin{align} \mathcal L(\phi,\mu_0,\mu_1,\Sigma)=&\prod_{i=1}^mP(X^{(i)},y^{(i)};\phi,\mu_0,\mu_1,\Sigma)\\ =&\prod_{i=1}^mP(X^{(i)}|y^{(i)})·P(y^{(i)})\ \ \ 为简化表示省略参数\\ \end{align} \]

对比原有的判别式学习算法，我们做的是最大化这个似然性公式：

\[ \mathcal L(\Theta)=\prod_{i=1}^mP(y^{(i)}|X^{(i)};\Theta)\\ \]

我们尝试选择 \(\Theta\) 来在给定 \(X\) 的情况下最大化 \(y\) 的概率密度函数。而对于生成学习算法，我们将尝试选择一系列参数在给定 \(y\) 的情况下，最大化 \(X\) 的概率密度函数。

回到生成学习算法，我们使用最大似然估计：

\[ \max_{\phi,\mu_0,\mu_1,\Sigma}l(\phi,\mu_0,\mu_1,\Sigma)=\max_{\phi,\mu_0,\mu_1,\Sigma}log\mathcal L(\phi,\mu_0,\mu_1,\Sigma) \]

之后我们要做的就是化简这个式子，分析结果中的项，然后将导数设置为0，最后求解即可使得这个似然性最大。至于运算过程老师留作作业（找遍全网没找到计算过程），之后有时间我会尝试补充完整，现在先给出答案。

\[ \begin{gather} 我们定义函数I{cond}=\left\{\begin{matrix} 1 & ,cond=true\\ 0 & ,cond = false \end{matrix}\right.\\ \phi=\frac{\sum_{i=1}^mI\{y^{(i)}=1\}}{m},可以理解为有m个病人，则\phi是这m个病例中患病的概率\\ \mu_o=\frac{\sum_{i=1}^m[I\{y^{(i)}=0\}x^{(i)}]}{\sum_{i=1}^mI\{y^{(i)}=0\}},可以理解为只取一类的训练示例，并计算这些训练示例的X的均值\\ \mu_1=\frac{\sum_{i=1}^m[I\{y^{(i)}=1\}x^{(i)}]}{\sum_{i=1}^mI\{y^{(i)}=1\}},可以理解为只取另一类的训练示例，并计算这些训练示例的X的均值\\ \Sigma=\frac1m\sum_{i=1}^m(x^{(i)}-\mu_{y^{(i)}})(x^{(i)}-\mu_{y^{(i)}})^T\\ 这里的协方差矩阵表示一个能够将同一类训练示例的X满足该协方差矩阵下的多元高斯分布 \end{gather} \]

在我们的训练阶段，我们利用训练示例集的数据 \(X\) 与 \(Y\) 得到了这四个参数的值。在我们的预测阶段，我们要做的就是计算：

\[ \arg\max_yP(y|X)=\arg\max_y\frac{P(X|y)·P(y)}{P(X)} \]

翻译：计算在 \(y\) 取什么值时，\(P(y|X)\) 可以有最大值？又因为 \(P(X)\) 是一个与 \(y\) 无关的项，所以我们在考虑最大的时候只需要考虑上半部分即可：

\[ \arg\max_yP(y|X)=\arg \max_y{P(X|y)·P(y)} \]

图形化显示¶

假设我们有一个如上图所示的数据训练示例集，我们分别用GDA和逻辑回归来获得一个判别边界：

可以看到几个有趣的事情：

因为我们对不同的类假设采用的是相同的协方差矩阵 \(\Sigma\) ，因此这两组同心圆（不一定是标准的圆）的大致形状是一样的。区别在于位置不同。
GDA训练的目的就在于找到合适的 \(\mu\ \&\ \Sigma\) 使得某一类的训练示例在类内符合多维高斯分布。
GDA训练得到的决策边界和逻辑回归训练的决策边界是不完全相同的。至于预测效果不好根据图像得出。
如果我们给不同的类采取相同的 \(\Sigma\) 最终得到决策边界会是线性的。但如果给不同的类采取相同的 \(\Sigma\) 最终得到的结果并不会有太大影响，而参数数量会加倍，并且最终的决策边界也会失去线性的特性。

GDA与逻辑回归¶

我们根据贝叶斯规则：

\[ \begin{align} P(y=1|X)=&\frac{P(X|y=1)·P(y=1)}{P(X)}\\ =&\frac{P(X|y=1)·\phi}{P(X)} \Rightarrow \frac1{1+e^{-\Theta^TX}}\\ \end{align} \]

当我们带入计算后可以发现其形状神似 Sigmoid 函数。当然或许从冷冰冰的字符看不出来，我们下面举一个例子：假设 \(X\) 是一维的，并且其各类的 \(X\) 分布如第一行：

在GDA中，我们拟合参数到高斯分布后得到第二行的图像。那么我们在测试阶段任意给出一个X的点。如果这个\(X\) 距离 \(\mu_1\) 很远， \(\mu_2\) 很近，则 \(P(y=1|X)\) 就会相对更低；同理如果这个 \(X\) 距离 \(\mu_1\) 很近， \(\mu_2\) 很远，则 \(P(y=1|X)\) 就会相对更高。而在两个高斯曲线的交界处会发现 \(P(y=1|X)\) 的变化率最大。最后我们得到的曲线就会是一条 Simoid 函数图像。

事实上根据 GDA 给出的一系列假设，我们在最后得出的形式就是逻辑回归中我们使用的 Sigmoid 函数。然而反过来我们根据逻辑回归的假设却得不到 GDA 的假设。因此我们可以认定 GDA 是一个更广泛的模型。

如果我们使用的是更强大更广泛的模型并且建模建设正确的情况下我们的模型所展现出的结果就会更好，因为这等于我们向模型告知了更多信息。也就是说如果对同一类的训练示例集中 \(X\) 确实按照多元高斯分布，那么这个算法得出的结果也会更好。然而如果这个假设是不适用于某训练示例集的话，GDA的表现就会很差。

最后根据当前结果我们还可以得出一种假设：

\[ \left.\begin{matrix} \{X|y=1\} \sim Poisson(\lambda_1)\\ \{X|y=0\} \sim Poisson(\lambda_1)\\ y \sim Ber(\phi) \\ \end{matrix}\right\}\Rightarrow p(y=1|X)\ is\ logistic \]

这也是正确的，不妨称之为泊松判别分布（纯瞎编）。经过科学家研究发现，只要是指数族内的分布，都存在这样的性质。而这也表明：如果你不知道自己数据集中同一类下的 \(X\) 符合什么类型的分布，只需要用逻辑回归即可！因此如果你有大量的数据，我们更多会选择使用逻辑回归，而对于更少的数据，我们会选择使用高斯判别分布算法。

Naive Bayes¶

在这一部分我们会使用很多电子邮件的垃圾邮件分类问题来举例。这也是我们首次尝试自然语言处理。那么首先的第一个问题就是，我们如何将电子邮件映射到一个特征向量上？

电子邮件到特征向量的映射¶

第一步是收集你所有邮件中出现过的前10000（假设）个单词并将其按顺序排列后得到一个字典，比如：

a
aardvark
aardwolf
... ...
buy
... ...
CS229
... ...
zymurgy

下一步是针对一封邮件，如果字典中的单词出现在这一封邮件中则定该位为1，否则为0：

    [1  ]   a
    |0  |   aardvark
    |0  |   aardwolf
    |...|    ...
x=  |1  |   buy
    |...|    ...
    |0  |   CS229
    |...|    ...
    [0  ]   zymurgy

因此有 \(X\in\{0,1\}^n\) .其中n是你当初设置的字典的大小。也就是说 \(x_i=I\{单词出现是否在字典中\}\) .

接下来我们给出 \(P(X|y),P(y)\) 。但因为我们的 \(X\) 有 \(2^{10000}\) 种取值，所以在没有其他假设的情况下对此模型进行建模将成效不好。因此我们有条件独立假设——假设在所有 \(X\) 对于给定的 \(y\) 是条件独立的，即：

\[ \begin{align} P(X_1,X_2,...,X_{2^{10000}}|y)=&P(x_1|y)·P(X_2|X_1,y)···P(X_{2^{10000}}|X_1,...,y)\ 由链式法则成立\\ \overset{assume}{=}&P(x_1|y)·P(X_2|y)···P(X_{2^{10000}}|y)\\ =&\prod_{i=1}^nP(X_i|y) \end{align} \]

这表明看见单词 “a” 的概率并不会影响看见单词 "aardvark" 的概率。

下面我们尝试给出Naive Bayes中对GDA的参数的定义：

\[ \begin{gather} \phi_{j|y=1}=P(X_j=1|y=1),表示假定是垃圾邮件的情况下，X_j在邮件中出现的概率\\ \phi_{j|y=0}=P(X_j=1|y=0),表示假定不是垃圾邮件的情况下，X_j在邮件中出现的概率\\ \phi_y={(y=1)}，表示在收到邮件前，你收到下一封邮件是垃圾邮件的先验概率是多少 \end{gather} \]

同样我们有 \(Joint Likelihood\) :

\[ \begin{align} \mathcal L(\phi_y,\phi_{j|y})=\prod_{i=1}^{m}P(X^{(i)},y^{(i)};\phi_y,\phi_{j|y})\\ 通过最大似然估计:\begin{matrix} \phi_y=\frac{\sum_{i=1}^mI\{y^{(i)}=1\}}{m}\\ \phi_{j|y=1}=\frac{\sum_{i=1}^mI\{X_j^{(i)}=1\ \&\&\ y^{(i)}=1\}}{\sum_{i=1}^mI\{y^{(i)}=1\}}\\ \phi_{j|y=0}=\frac{\sum_{i=1}^mI\{X_j^{(i)}=1\ \&\&\ y^{(i)}=0\}}{\sum_{i=1}^mI\{y^{(i)}=0\}}\\ \end{matrix} \end{align} \]

因为没有任何的迭代计算，所以这个算法的效率是非常高的。