CS229 学习笔记 Part 2

对于一个分类任务，判别式和生成式分别代表了两种不同的思路：

通过直接从输入数据中学习，得到一个『特定输入对应的实际类别』的概率模型，模型的参数为 $\theta$ 。即学习建模 $p(y\mid x)$

通过对每一个类进行建模，然后就可以通过条件概率算出输入的数据更可能由哪一类生成。即学习建模 $p(x\mid y)$ 和 $p(y)$ ，然后计算 $$\arg\max\limits_y\frac{p(x \mid y)p(y)}{p(x)}$$

并且实际计算中，分母 $p(x)$ 并不会影响各个类别概率的排序，所以最终简化成 $$\arg\max\limits_y p(x \mid y)p(y)​$$

作为生成式模型的第一个例子，它假设数据的分布 $p(x\mid y)$ 是多元高斯分布 (multivariate normal distribution)，分类结果为二分类，即 $y \sim \mathrm{Bernoulli}(\phi)$。

根据生成式模型的思路，它通过训练数据，计算出两个类的隐含分布——多元高斯分布的参数 $\mu_0, \mu_1,\Sigma$ （需要注意的是，这里对于两个多元正态分布的 $\Sigma$，我们使用的是一个公共的参数，也就是我们假设两个分布的『形状』是一样的），以及对于分类结果的伯努利分布参数 $\phi$

根据定义，我们可以得到以下模型

$$p(y) = \phi^y(1-\phi)^{1-y}$$

$$p(x\mid y=0) = \frac{1}{(2\pi)^{n/2}|\Sigma|^{1/ 2}} \exp\left(-\frac{1}{2}(x-\mu_0)^T\Sigma^{-1}(x-\mu_0)\right)$$

$$p(x\mid y=1) = \frac{1}{(2\pi)^{n/2}|\Sigma|^{1/ 2}} \exp\left(-\frac{1}{2}(x-\mu_1)^T\Sigma^{-1}(x-\mu_1)\right)$$

接下来开始估计各个参数的值。我们使用一个新的似然函数 Joint likelihood

$$\ell(\phi, \mu_0, \mu_1, \Sigma) = log \prod^m_{i=1} p(x^{(i)}, y^{(i)}; \phi, \mu_0, \mu_1, \Sigma)$$

$$\phantom{ \ell(\phi, \mu_0, \mu_1, \Sigma)} = log \prod^m_{i=1} p(x^{(i)}\mid y^{(i)}; \mu_0, \mu_1, \Sigma)p(y^{(i)};\phi)$$

通过最大化此似然函数，我们能够得到以上几个参数的估计值

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

而 GDA 的判别公式则是作为作业的一部分自行完成。

GDA 的判别公式能够化为以下形式 $$p(y=1\mid x;\phi, \Sigma, \mu_0, \mu_1) = \frac{1}{1+\exp(-\theta^Tx)}$$

也就是 Logistic 回归的形式。（这个公式转化的具体过程是课后习题的一部分）

其中 $\theta$ 是关于 $\phi,\Sigma,\mu_0,\mu_1$ 的函数。那么 GDA 和 Logistic 回归（下称 LR）的区别在哪里呢？

假设 $p(x\mid y)$ 满足多元高斯分布，那么 $p(y\mid x)$ 能够写成 logistic 函数的形式。但是，反之并不成立。$p(y\mid x)$ 能够写成 logistic 函数的形式并不意味着 $p(x\mid y)$ 符合多元高斯分布。这说明，GDA 做出了一个更强的假设 (stronger modeling assumption)。

并且，当这个假设符合现实（ $p(x\mid y)$ 符合多元高斯分布 ），并且在训练集足够大的情况下，没有其他算法优于 GDA1。而且通常来说，对于一个较小的训练集，我们通常会觉得 GDA 会表现的更好。

反过来说，对于使用了较弱假设的 LR，它拥有更强的鲁棒性，对于错误的模型假设也更不敏感。对 $p(x\mid y)$ 分布的假设，有很多种情况能够使得 $p(y\mid x)$ 可以化为 Logistic 函数的形式。比如说，$x \mid y = 0$ 和 $x \mid y = 1$ 分别符合两个独立的泊松分布时既是如此。

对于一个文本分类问题，使用50000个词的简化词袋模型时，我们的目标是对 $p(x_1,\cdots,x_{50000}\mid y)$ 构建出最准确的模型。

$$p(x_1,\cdots,x_{50000}\mid y)$$

$$ = p(x_1\mid y)p(x_2\mid y,x_1)p(x_3\mid y,x_1,x_2)\cdots p(x_{50000}\mid y,x_1,x_2,\cdots,x_{49999})$$

此时的式子称为贝叶斯分类器。而朴素贝叶斯和贝叶斯的区别在于哪里呢？关键就在于以下假设：

朴素贝叶斯假设：假设 $x_i$ 条件独立于 $y_i$

则原概率公式

$$ = p(x_1\mid y)p(x_2\mid y)p(x_3\mid y)\cdots p(x_{50000}\mid y)$$

此时的式子就称为朴素贝叶斯分类器了。虽然朴素贝叶斯假设是一个很强的假设 (strong assumption)，但是它出人意料的在很多问题上都表现的不错。 使用朴素贝叶斯概率公式，则词袋中的每个词，对于每种文本分类都属于一个独立参数的伯努利分布。即此例子中，词袋大小50000，2种文本分类，于是共有 100,000 个伯努利分布参数需要估计，以及一个对于类别 y 的伯努利分布参数 $\phi_y$。

我们使用 Joint likelihood 作为目标函数

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

最大化似然函数得到各个参数的估计

$$j \in {1,2,\cdots,50000}$$

$$ \phi_{j\mid y=1} = \frac{\sum^m_{i=1}\operatorname{1}{x_j^{(i)} = 1 \wedge y^{(i)} = 1 }}{\sum^m_{i=1}\operatorname{1}{ y^{(i)} = 1 }} $$

$$\phi_{j\mid y=0} = \frac{\sum^m_{i=1}\operatorname{1}{x_j^{(i)} = 1 \wedge y^{(i)} = 0 }}{\sum^m_{i=1}\operatorname{1}{ y^{(i)} = 0 }}$$

$$\phi_y = \frac{\sum^m_{i=1}\operatorname{1}{ y^{(i)} = 1 }}{m}$$

朴素贝叶斯的判别公式如下：

$$p(y=1\mid x) = \frac{p(x\mid 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)}$$

最后，我们能够很容易的想到，可以将 $x_i$ 的取值从二值变为多值，就成为了这个算法的泛化。为了做到这一点，我们只需要将对 $p(x_i\mid y)$ 假设的伯努利分布，替换成多项式分布即可。如果原始属性是连续值，我们也可以通过分段的办法，将他离散化。之后，就可以仿照我们上述的过程来使用朴素贝叶斯算法了。当原始的连续属性使用多元正态分布不能很好的建模时，将他离散化后使用朴素贝叶斯通常能取得更好的效果。

上述标准的朴素贝叶斯通常情况下效果都很好，但是在一些特殊情况下会出现奇怪的情况。比如说，当你的分类器遇到了一个从来没有见过的词（不存在于训练数据中）的时候，对于这个词两个类别的概率都会等于零，并且由于累乘的结果，会使得整个输出都变为零。这显然不合理，所以这就是拉普拉斯平滑要解决的事情。

原理很简单，我们对于一个多项式分布输入的类别概率计算公式如下

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

我们想要让这个式子不等于零，很直觉的办法是在分子上加上一个很小的数。所以我们在分子上加一个 1。但是这还不够，我们需要让多项式分布的各个类整体概率和仍然为 1，即 $\sum^k_{j=1}\phi_j = 1$ 。所以我们分母也需要稍作改动，最终我们得到 $$p(z=j) = \phi_j = \frac{\sum^m_{i=1} \operatorname{1}{z^{(i)}=j}+1}{m+k}$$

读者可以自己验算 $\sum^k_{j=1}\phi_j = 1$

之前的模型我们称为『多变量伯努利分布事件模型』2，而对于文本分类的任务，接下来这个模型通常能够取得更好的效果，称为『多项式分布事件模型』3。

在这个模型中，一个由 n 个词组成的文本段将化为一个 n 维向量，每一维符合都一个相同的多项式分布，多项式分布一个选项对应一个特定的词。比如一个电子邮件内容为『快来 购买……』，在多项式分布中，快来对应的类别编号为33，购买的类别编号为580，则形成的输入向量就是 [33, 580, …]

文本段中每一个词的分布都来自同一个多项式分布，需要注意的是，词在文中的位置并不影响他的取值分布。

则似然函数定义如下 $$\mathcal{L}(\phi, \phi_{k\mid y=0}, \phi_{k\mid y=1}) = \prod^m_{i=1}p(x^{(i)}，y^{(i)})$$

$$= \prod^m_{i=1}\left( \prod^{n_i}_{j=1}p(x_j^{(i)}\mid y;\phi_{k\mid y=0},\phi_{k\mid y=1}) \right)p(y^{(i)};\phi_y)$$

最大化似然函数得到参数估计

$$\phi_{k\mid y=1} = \frac{\sum^m_{i=1}\sum^{n_i}_{j=1} \operatorname{1}{x_j^{(i)} = k\wedge y^{(i)} = 1 } }{\sum^m_{i=1} \operatorname{1}{ y^{(i)} = 1} n_i}$$

$$\phi_{k\mid y=0} = \frac{\sum^m_{i=1}\sum^{n_i}_{j=1} \operatorname{1}{x_j^{(i)} = k\wedge y^{(i)} = 0 } }{\sum^m_{i=1} \operatorname{1}{ y^{(i)} = 0} n_i}​$$

$$\phi_y = \frac{\sum^m_{i=1}\operatorname{1}{y^{(i)} = 1}}{m}$$

多项式分布事件模型和之前的模型的不同点在于，新模型除了统计某一个词是否出现，还考虑了某一个词出现的次数。