前面讲到的学习算法都是对 $p(y|x;\theta)$ 建模。例如逻辑回归算法对 $p(y|x;\theta)$ 建模得到 $h_\theta(x)=g(\theta^Tx)$ (其中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)$ 建模后，使用贝叶斯规则推导后验概率分布

$$
p(y|x) = \frac{p(x|y) \cdot p(y)}{p(x)}
$$

其中 $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{align}
\arg\max_y p(y|x) &= \arg\max_y \frac{p(x|y)p(y)}{p(x)} \\
&= \arg\max_y p(x|y)p(y)
\end{align}
$$

高斯判别分析

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

多维正态分布

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

$$
p(x;\mu,\Sigma) = \frac{1}{(2\pi)^{n/2} |\Sigma|^{1/2}} exp(-\frac{1}{2}(x-\mu)^T {\Sigma}^{-1} (x-\mu))
$$

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

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

$$
E[X] = \int_{x} x p(x;\mu,\Sigma) dx = \mu
$$

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

$$
cov(Z) = E[(Z - E(Z)) (Z - E(Z))^T] = E[ZZ^T] - (E[Z])(E[Z])^T
$$

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

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

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

$$
\Sigma =
\begin{bmatrix}
1 & 0\\
0 & 1
\end{bmatrix}
;
\Sigma =
\begin{bmatrix}
1 & 0.5\\
0.5 & 1
\end{bmatrix}
;
\Sigma =
\begin{bmatrix}
1 & 0.8\\
0.8 & 1
\end{bmatrix}
$$

固定 $\Sigma = I$，均值如下
$$
\mu =
\begin{bmatrix}
1\\
0
\end{bmatrix}
;
\mu =
\begin{bmatrix}
-0.5\\
0
\end{bmatrix}
;
\mu =
\begin{bmatrix}
-1\\
-1.5
\end{bmatrix}
;
$$

高斯判别分析模型

使用多维正态分布对 $p(x|y)$ 建模，模型如下
$$
\begin{align}
y &\sim Bernoulli(\phi) \\
x|y = 0 &\sim N(\mu_0, \Sigma) \\
x|y = 1 &\sim 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} |\Sigma|^{1/2}} exp(-\frac{1}{2}(x-\mu_0)^T {\Sigma}^{-1} (x-\mu_0)) \\
p(x|y=1) &= \frac{1}{(2\pi)^{n/2} |\Sigma|^{1/2}} exp(-\frac{1}{2}(x-\mu_1)^T {\Sigma}^{-1} (x-\mu_1))
\end{align}
$$
这里的参数为：$\phi, \Sigma, \mu_0, \mu_1$，注意协方差矩阵$\Sigma$只有一个。log似然函数如下
$$
\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)};\phi,\mu_0,\mu_1,\Sigma) p(y{(i)};\phi)
\end{align}
$$
通过最大化$l$，得到参数值如下
$$
\begin{align}
\phi &= \frac{1}{m} \sum_{i=1}^{m} I{y^{(i)} = 1} \\
\mu_0 &= \frac{\sum_{i=1}^{m} I{y^{(i)} = 0} x^{(i)}}{\sum_{i=1}^{m} I{y^{(i)} = 0}} \\
\mu_1 &= \frac{\sum_{i=1}^{m} I{y^{(i)} = 1} x^{(i)}}{\sum_{i=1}^{m} I{y^{(i)} = 1}} \\
\Sigma &= \frac{1}{m} \sum_{i=1}^{m} (x^{(i)} - \mu_{y^{(i)}}) (x^{(i)} - \mu_{y^{(i)}})^T
\end{align}
$$
该算法的执行情况如下图所示：这里有两个正态分布，它们有相同的协方差矩阵和不同的期望值，分别对应训练集中的两种分类。图中的直线表示预测的分界线($p(y=1|x)=0.5$)，根据结果落在直线的哪一侧(通过计算$p(y=1|x)$和$p(y=0|x)$的值得到)来预测为对应的分类

GDA和逻辑回归

如果将$p(y=1|x;\phi,\Sigma,\mu_0,\mu_1)$ 看做是$x$的函数，它可以表示为如下形式
$$
p(y=1|x;\phi,\Sigma,\mu_0,\mu_1) = \frac{1}{1+exp(-\theta^Tx)}
$$
其中$\theta$是$\phi,\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{align}
p(x_1,…x_{50000}|y) &= p(x_1|y)p(x_2|y,x_1)p(x_3|y,x_1,x_2)…p(x_{50000}|y,x_1,…,x_{49999}) \\
&= p(x_1|y)p(x_2|y)p(x_3|y)…p(x_{50000}|y) \\
&= \prod_{i=1}^{n} p(x_i|y)
\end{align}
$$
第一个等式可根据条件概率性质推导，证明两边相等只需要在等式两边分别乘以$p(y)$。第二个等式使用了贝叶斯假设。尽管贝叶斯假设是一个很强的假设，实际上在很多问题的处理上表现很好。

我们的模型参数是：$\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=0}, \phi_{i|y=1}) = \prod_{i=1}^{m} p(x^{(i)}, y^{(i)})
$$
最大似然估计如下

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

拉普拉斯平滑

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

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

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

文本分类事件模型

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

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

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

多项式事件模型

使用$x_i$表示邮件的第$i$个单词，它的取值范围是{1,…,|V|}，其中|V|是词典中单词的个数。包含n个单词的邮件可以用长度为n的向量$(x_1,x_2,…,x_n)表示$，注意不同邮件的对应的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$是多项式分布，而之前的是伯努利分布

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

给定训练集{$(x^{(i)},y^{(i)}); i = 1,…,m$}，其中$x^{(i)}=(x_1^{(i)},x_2^{(i)},…,x_{n_i}^{(i)})$($n_i$表示第i个训练集的单词个数)，则似然函数表示如下
$$
\begin{align}
L(\phi,\phi_{i|y=0},\phi_{i|y=1}) &= \prod_{i=1}^{m}p(x^{(i)},y^{(i)}) \\
&= \prod_{i=1}^{m} (\prod_{j=1}^{n_i} p(x_j^{(i)}|y; \phi_{i|y=0},\phi_{i|y=1})) p(y^{(i)};\phi_y)
\end{align}
$$

最大似然估计如下

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