前面讲到的学习算法都是对 $p(y|x;\theta )$ 建模。例如逻辑回归算法对 $p(y|x;\theta )$ 建模得到 $h_{\theta }(x)=g({\theta }^{T}x)$ (其中 g 是 sigmoid 函数)，直观上可以理解为：找到一条直线，将数据集划分为 $y=1$ 和 $y=0$ 两种，对新的输入，根据结果落在直线的哪一侧预测为对应的分类。这种叫做判别学习算法

和判别学习算法不同的是，生成学习算法对 $p(x|y)$ 和 $p(y)$ 建模。

举个栗子，假如我们想判断一个动物是大象 ($y=1$) 还是狗 ($y=0$)，$y$ 表示一个样本是大象还是狗，$p(x|y=1)$ 表示大象的特征分布、$p(x|y=0)$ 表示狗的特征分布。在对 $p(y)$(class priors 先验概率类型) 和 $p(x|y)$ 建模后，使用贝叶斯规则推导后验概率分布

$$\begin{array}{}\text{(1)}& p(y|x)=\frac{p(x|y)\cdot p(y)}{p(x)}\end{array}$$

其中 $p(x)=p(x|y=1)p(y=1)+p(x|y=0)p(y=0)$ (可由全概率公式得到，$p(B)=\sum _{i=1}^{n}p(A_i)p(B|A_i)$)。实际上，如果只是计算 $p(y|x)$ 用于预测，并不需要计算出分母的值 (因为分母不是 $y$ 的函数)，原因如下

$$\begin{array}{}\text{(2)}& \arg \underset{y}{max}p(y|x)& =\arg \underset{y}{max}\frac{p(x|y)p(y)}{p(x)}\text{(3)}& & =\arg \underset{y}{max}p(x|y)p(y)\end{array}$$

高斯判别分析

首先介绍高斯判别分析 GDA (Gaussian discriminant analysis)，它假定 $p(x|y)$ 服从多维正态分布 ($x$ 是向量，它的值是连续的)

多维正态分布

n 维正态分布 (又叫高斯分布)，它的参数包括一个均值向量 $\mu \in {\mathbb{R}}^n$ 和一个协方差矩阵 $\mathrm{\Sigma }\in {\mathbb{R}}^{n\times n}$ ($\sum \ge 0$ 是对称半正定矩阵)，记作 $N(\mu ,\mathrm{\Sigma })$。它的概率密度为

$$\begin{array}{}\text{(4)}& p(x;\mu ,\mathrm{\Sigma })=\frac{1}{(2\pi {)}^{n/2}|\mathrm{\Sigma }{|}^{1/2}}exp(-\frac{1}{2}(x-\mu {)}^T{\mathrm{\Sigma }}^{-1}(x-\mu ))\end{array}$$

其中 $|\mathrm{\Sigma }|$ 表示协方差矩阵 $\mathrm{\Sigma }$ 的行列式

假设随机变量 $X$ 服从多维高斯分布，则它的期望为

$$\begin{array}{}\text{(5)}& E[X]={\int }_{x}xp(x;\mu ,\mathrm{\Sigma })dx=\mu \end{array}$$

假设随机变量 $Z$ 是一个向量，它的协方差为

$$\begin{array}{}\text{(6)}& cov(Z)=E[(Z-E(Z))(Z-E(Z){)}^T]=E[Z{Z}^T]-(E[Z])(E[Z]{)}^T\end{array}$$

如下是几个二维高斯分布的概率密度图形示例

高斯分布密度 1

左边图形：均值为零向量 (2X1 的零向量)，协方差矩阵 $\mathrm{\Sigma }=I$(2X2 的单位矩阵)。这是一个标准正态分布。中间图形：均值为零向量，协方差矩阵为 $\mathrm{\Sigma }=0.6I$。右边图形：均值为零向量，协方差矩阵为 $\mathrm{\Sigma }=2I$

高斯分布密度 2

均值都为 0，协方差矩阵如下

$$\begin{array}{}\text{(7)}& \mathrm{\Sigma }=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right];\mathrm{\Sigma }=\left[\begin{array}{cc}1& 0.5\\ 0.5& 1\end{array}\right];\mathrm{\Sigma }=\left[\begin{array}{cc}1& 0.8\\ 0.8& 1\end{array}\right]\end{array}$$

高斯分布密度

固定 $\mathrm{\Sigma }=I$，均值如下
$$\begin{array}{}\text{(8)}& \mu =\left[\begin{array}{c}1\\ 0\end{array}\right];\mu =\left[\begin{array}{c}-0.5\\ 0\end{array}\right];\mu =\left[\begin{array}{c}-1\\ -1.5\end{array}\right];\end{array}$$

高斯判别分析模型

使用多维正态分布对 $p(x|y)$ 建模，模型如下
$$\begin{array}{}\text{(9)}& y& \sim Bernoulli(\varphi )\text{(10)}& x|y=0& \sim N({\mu }_0,\mathrm{\Sigma })\text{(11)}& x|y=1& \sim N({\mu }_1,\mathrm{\Sigma })\end{array}$$
对应的概率密度
$$\begin{array}{}\text{(12)}& p(y)& ={\varphi }^y(1-\varphi {)}^{1-y}\text{(13)}& p(x|y=0)& =\frac{1}{(2\pi {)}^{n/2}|\mathrm{\Sigma }{|}^{1/2}}exp(-\frac{1}{2}(x-{\mu }_0{)}^T{\mathrm{\Sigma }}^{-1}(x-{\mu }_0))\text{(14)}& p(x|y=1)& =\frac{1}{(2\pi {)}^{n/2}|\mathrm{\Sigma }{|}^{1/2}}exp(-\frac{1}{2}(x-{\mu }_1{)}^T{\mathrm{\Sigma }}^{-1}(x-{\mu }_1))\end{array}$$
这里的参数为：$\varphi ,\mathrm{\Sigma },{\mu }_0,{\mu }_1$，注意协方差矩阵 $\mathrm{\Sigma }$ 只有一个。log 似然函数如下
$$\begin{array}{}\text{(15)}& l(\varphi ,{\mu }_0,{\mu }_1,\mathrm{\Sigma })& =log\prod _{i=1}^{m}p(x^{(i)},y(i);\varphi ,{\mu }_0,{\mu }_1,\mathrm{\Sigma })\text{(16)}& & =log\prod _{i=1}^{m}p(x^{(i)}|y(i);\varphi ,{\mu }_0,{\mu }_1,\mathrm{\Sigma })p(y(i);\varphi )\end{array}$$
通过最大化 $l$，得到参数值如下
$$\begin{array}{}\text{(17)}& \varphi & =\frac{1}{m}\sum _{i=1}^{m}I{y}^{(i)}=1\text{(18)}& {\mu }_0& =\frac{\sum _{i=1}^{m}I{y}^{(i)}=0x^{(i)}}{\sum _{i=1}^{m}I{y}^{(i)}=0}\text{(19)}& {\mu }_1& =\frac{\sum _{i=1}^{m}I{y}^{(i)}=1x^{(i)}}{\sum _{i=1}^{m}I{y}^{(i)}=1}\text{(20)}& \mathrm{\Sigma }& =\frac{1}{m}\sum _{i=1}^m(x^{(i)}-{\mu }_{y^{(i)}})(x^{(i)}-{\mu }_{y^{(i)}}{)}^T\end{array}$$
该算法的执行情况如下图所示：这里有两个正态分布，它们有相同的协方差矩阵和不同的期望值，分别对应训练集中的两种分类。图中的直线表示预测的分界线 ($p(y=1|x)=0.5$)，根据结果落在直线的哪一侧 (通过计算 $p(y=1|x)$ 和 $p(y=0|x)$ 的值得到) 来预测为对应的分类

GDA 算法

GDA 和逻辑回归

如果将 $p(y=1|x;\varphi ,\mathrm{\Sigma },{\mu }_0,{\mu }_1)$ 看做是 $x$ 的函数，它可以表示为如下形式
$$\begin{array}{}\text{(21)}& p(y=1|x;\varphi ,\mathrm{\Sigma },{\mu }_0,{\mu }_1)=\frac{1}{1+exp(-{\theta }^{T}x)}\end{array}$$
其中 $\theta$ 是 $\varphi ,\mathrm{\Sigma },{\mu }_0,{\mu }_1$ 的函数。这和逻辑回归算法得到的函数形式一样。

事实上，如果 $p(x|y)$ 服从多维正态分布，则 $p(y|x)$ 是逻辑回归函数。相反，如果 $p(y|x)$ 是逻辑回归函数，$p(x|y)$ 不一定服从多维正态分布。也就是说 GDA 对数据集做了 (比逻辑回归) 更强的假设。如果实际情况和 GDA 的假设更相符，那么它的预测效果比逻辑回归要好，否则逻辑回归可能表现更好。这说明逻辑回归比 GDA 更稳定

朴素贝叶斯

和 GDA 不同的是，朴素贝叶斯算法中 $x$ 是离散的。考虑邮件分类问题 (典型的文本分类问题)，使用向量表示邮件，向量的长度等于词典的长度 (词典中的词来自所有的样本)。如果一封邮件包含词典中的第 $i$ 个词，就把 $x_i$ 设置为 1，否则设置为 0，如下是一个示例

邮件的表示

考虑使用多项分布模型表示 $p(x|y)$，若词典容量是 50000，则 $x\in (0,1{)}^{50000}$，输出有 $2^{50000}$ 种可能，需要计算的参数会非常多

贝叶斯假设：给定 $y$，$x$ 是条件独立的。例如 $y=1$ 表示垃圾邮件，“buy” 是第 2087 个单词，“price” 是第 39831 个单词，该假设认为：已知 $y=1$ 的情况下，$x_{2087}$ 和 $x_{39831}$ 相互之间没有影响，即 $p(x_{2087}|y)=p(x_{2087}|y,x_{39831})$
$$\begin{array}{}\text{(22)}& p(x_1,\dots x_{50000}|y)& =p(x_1|y)p(x_2|y,x_1)p(x_3|y,x_1,x_2)\dots p(x_{50000}|y,x_1,\dots ,x_{49999})\text{(23)}& & =p(x_1|y)p(x_2|y)p(x_3|y)\dots p(x_{50000}|y)\text{(24)}& & =\prod _{i=1}^{n}p(x_i|y)\end{array}$$
第一个等式可根据条件概率性质推导，证明两边相等只需要在等式两边分别乘以 $p(y)$。第二个等式使用了贝叶斯假设。尽管贝叶斯假设是一个很强的假设，实际上在很多问题的处理上表现很好。

我们的模型参数是：${\varphi }_{i|y=1}=p(x_i=1|y=1)$、${\varphi }_{i|y=0}=p(x_i=1|y=0)$ 和 ${\varphi }_y=p(y=1)$，可以得到联合似然函数如下
$$\begin{array}{}\text{(25)}& L({\varphi }_y,{\varphi }_{i|y=0},{\varphi }_{i|y=1})=\prod _{i=1}^{m}p(x^{(i)},y^{(i)})\end{array}$$
最大似然估计如下

最大似然估计

对于新的样本，可以通过下式计算它的后验概率

计算后验概率

拉普拉斯平滑

在使用朴素贝叶斯算法对新的邮件进行分类时，假设 “nips” 表示词典中第 35000 个单词，它在之前的样本中从未出现过，那么最大似然估计的参数

条件概率为 0

因为没有见过 “nips” 这个单词，导致两种类型概率均为 0。后验概率的计算结果为 $\frac{0}{0}$，使得无法对该邮件进行分类

后验概率为 0

考虑预估多项分布随机变量 $z$ 的期望问题，其中 $z$ 的取值范围为 {1,…,k}，将其参数化为 ${\varphi }_i=p(z=i)$，给定 m 个独立的观测结果 (样本)$z^{(1)},\dots ,z^{(m)}$，则最大似然估计表示如下
$$\begin{array}{}\text{(26)}& {\varphi }_j=\frac{\sum _{i=1}^{m}I(z^{(i)}=j)}{m}\end{array}$$
对该式应用拉普拉斯平滑可得
$$\begin{array}{}\text{(27)}& {\varphi }_j=\frac{\sum _{i=1}^{m}I(z^{(i)}=j)+1}{m+k}\end{array}$$
回到邮件分类问题，应用拉普拉斯平滑后，条件概率的分子不再为 0

应用拉普拉斯平滑

文本分类事件模型

前面讨论的贝叶斯分类模式是多元伯努利事件模型 (multi-variate Bernoulli event model)，在该模型中，我们假定邮件的生成方式如下

1. 随机决定发送垃圾邮件或非垃圾邮件 ($p(y)$)
2. 根据 $p(x_i=1|y)={\varphi }_{i|y}$ 选择要加入的单词

这样最终发送邮件的概率可表示为 $p(y)\prod _{i=1}^{n}p(x_i|y)$

多项式事件模型

使用 $x_i$ 表示邮件的第 $i$ 个单词，它的取值范围是 {1,…,|V|}，其中 | V | 是词典中单词的个数。包含 n 个单词的邮件可以用长度为 n 的向量 $(x_1,x_2,\dots ,x_n)\mathrm{表}\mathrm{示}$，注意不同邮件的对应的 n 的大小也不相同。在该模型下假定邮件的生成方式如下

1. 随机决定发送垃圾邮件或非垃圾邮件 ($p(y)$)，这与多元伯努利事件模型相同
2. 然后根据多项式分布模型选择 $x_1$($p(x_1|y)$)
3. 再通用根据多项式分布模型独立于 $x_1$ 选择 $x_2$
4. 依次选择其他单词，直到选完 n 个单词

最终邮件的概率可表示为 $p(y)\prod _{i=1}^{n}p(x_i|y)$。这与前面讨论的模型看起来比较像，实际有很大不同，其中 $x_i|y$ 是多项式分布，而之前的是伯努利分布

在该模型中 ${\varphi }_y=p(y)$、${\varphi }_{i|y=1}=p(x_j=i|y=1)$(对任意的 j)、${\varphi }_{i|y=0}=p(x_j=i|y=0)$，注意对 j 的所有取值概率 $p(x_j|y=0)$ 均相等

给定训练集 {$(x^{(i)},y^{(i)});i=1,\dots ,m$}，其中 $x^{(i)}=(x_1^{(i)},x_2^{(i)},\dots ,x_{n_i}^{(i)})$($n_i$ 表示第 i 个训练集的单词个数)，则似然函数表示如下
$$\begin{array}{}\text{(28)}& L(\varphi ,{\varphi }_{i|y=0},{\varphi }_{i|y=1})& =\prod _{i=1}^{m}p(x^{(i)},y^{(i)})\text{(29)}& & =\prod _{i=1}^m(\prod _{j=1}^{n_i}p(x_j^{(i)}|y;{\varphi }_{i|y=0},{\varphi }_{i|y=1}))p(y^{(i)};{\varphi }_y)\end{array}$$

最大似然估计如下

最大似然估计

应用拉普拉斯平滑后结果如下

拉普拉斯平滑最大似然估计