以线性回归、逻辑回归为代表的广义线性模型，都是在针对 $p(y|x;\theta)$，也就是给定 $x$ 时 $y$ 的条件概率分布进行建模。
以分类问题为例，给定一个训练集，逻辑回归，试图寻找一条直线——也就是决策边界——来区分正类和反类。模型建立后，对于一个新的测试样本，给定其特征，我们判定这个样本落在决策边界的哪一侧，然后据此做出预测。
直接学习 $p(y|x)$ 的算法，或者说直接将输入空间 $\chi$ 映射到标签 $\{0, 1\}$的算法，称为判别学习算法 Discriminative Learning Algorithm。与此相反，针对 $p(x|y)$ 建模的算法，称为生成学习算法 Generative Learning Algorithm。
还是以分类问题为例，生成学习算法通过对训练集的学习，给定一个分类 $y \in \{0, 1\}$，我们的模型试图描述这个分类对应的特征的分布。
通过对 $p(y)$ （称为先验概率 class prior）和 $p(x|y)$ 建模，我们之后通过贝叶斯法则来计算给定 $x$ 时 $y$ 的后验分布： $$ p(y|x) = \frac{p(x|y)p(y)}{p(x)} $$
其中，分母 $p(x) = p(x|y=1)p(y=1)+p(x|y=0)p(y=0)$。而实际上，在预测时，我们并不需要计算 $p(x)$，因为 $$ \begin{split} arg \max_yp(y|x) &= arg \max_y\frac{p(x|y)p(y)}{p(x)} \\ &= arg \max_yp(x|y)p(y) \end{split} $$
本节包括以下内容：
多维正态分布也称作多维高斯分布，其参数包括均值向量 mean vector $\mu \in \mathbb{R}^n$ 以及协方差矩阵 covariance matrix $\Sigma \in \mathbb{R}^{n \times n}$。
关于多维正态分布的具体特征，可参见随机变量及其数字特征-矩、协方差矩阵，这里略过详细介绍。
对于特征 $x$ 为连续型变量的分类问题，我们可以使用高斯判别分析（GDA）模型。该模型的假设包括： $$ \begin{split} y &\sim Bernoulli(\phi) \\ x|y=0 &\sim N(\mu_0, \Sigma) \\ x|y=1 &\sim N(\mu_1, \Sigma) \\ \end{split} $$ 对应的概率质量函数/概率密度函数为 $$ \begin{split} 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{split} $$
这里模型的参数为 $\phi, \Sigma, \mu_0, \mu_1$。（注意到尽管我们使用了不同的均值向量 $\mu_0$ 和 $\mu_1$，这里通常只使用同一个协方差矩阵 $\Sigma$）其对数似然函数为 $$ \begin{split} \ell(\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)}; \mu_0, \mu_1, \Sigma)p(y^{(i)};\phi) \end{split} $$
使 $\ell$ 最大的各参数分别为 $$ \begin{split} \phi &= \frac{1}{m}\sum_{i=1}^m 1\{y^{(i)}=1\} \\ \mu_0 &= \frac{\sum_{i=1}^m 1\{y^{(i)}=0\}x^{(i)}}{\sum_{i=1}^m 1\{y^{(i)}=0\}} \\ \mu_1 &= \frac{\sum_{i=1}^m 1\{y^{(i)}=1\}x^{(i)}}{\sum_{i=1}^m 1\{y^{(i)}=1\}} \\ \Sigma &= \frac{1}{m} \sum_{i=1}^m (x^{(i)}-\mu_{y^{(i)}})(x^{(i)}-\mu_{y^{(i)}})^T \end{split} $$
由于使用了相同的协方差，最终根据 $y=1$ 和 $y=0$ 估计出的多维高斯分布，形状将完全相同，区别仅仅在于均值。而两个高斯分布的等差线相交的地方，就是高斯判别分析模型的决策边界。
高斯判别分析和逻辑回归之间，存在着非常有意思的关联。如果我们将 $p(y=1|x;\phi, \mu_0, \mu_1, \Sigma)$ 视为 $x$ 的函数，即 $$ p(y=1|x) = \frac{p(x|y=1)p(y=1)}{p(x|y=1) + p(x|y=0)} $$
则这个函数可以写成 $$ p(y=1|x;\phi, \mu_0, \mu_1, \Sigma) = \frac{1}{1+exp(-\theta^Tx)} $$ 的形式，其中，$\theta$ 是 $\phi, \Sigma, \mu_0, \mu_1$ 的函数。这正是作为一种判别学习算法的逻辑回归对 $p(y=1|x)$ 的建模形式。
但是，高斯判别分析和逻辑回归求出的决策边界通常是不同的，也就是说 $\theta$ 的值是不同的，该如何区分两种模型的优劣呢？
注意我们上面的结论是，当 $p(x|y)$ 服从多维高斯分布时，则 $p(y|x)$ 必然是sigmoid函数的形式。而这个命题的逆命题是错误的，也就是说，当 $p(y|x)$ 是sigmoid函数的形式时，并不能得出 $p(x|y)$ 服从多维高斯分布。换言之，高斯判别分析的假设，比逻辑回归更强。
当高斯判别分析的假设成立时，它会找到比逻辑回归更好的模型，高斯判别分析是一个渐进有效估计量 asymptotically efficient estimator，渐进有效估计量的含义是，在大样本的条件下，没有其它算法可以严格意义上比高斯判别分析更准确地预测 $p(y|x)$。但同时，当假设成立，即使数据量小，高斯判别分析的效果通常也好于逻辑回归。
相反，由于使用了更弱的假设约束，逻辑回归会更健壮，不容易受到错误假设的影响。有很多种不同的假设（其中包括所有的指数分布族），都会使得 $p(y|x)$ 呈现sigmoid函数的形态。譬如一个数据集的 $p(x|y)$ 服从泊松分布，其 $p(y|x)$ 为sigmoid函数，当我们使用高斯判别分析来建模时，最终结果会很难预料，但我们可以预计逻辑回归仍然可以正常预测。
总结来说，当数据并不是高斯分布时，数据量较大的情况下，逻辑回归几乎总是比高斯判别分析表现得更好。出于这个原因，在实际项目中逻辑回归的使用远远多于高斯判别分析。这个区别，或多或少也是判别算法和生成算法的区别，尽管如此，我们接下来介绍的朴素贝叶斯算法，依然是非常经典且流行的分类算法。
在高斯判别分析中，特征向量 $x$ 是连续型的实数向量。而朴素贝叶斯算法则用于处理特征向量 $x$ 是离散型的情况，朴素贝叶斯的最常见应用场景是以垃圾邮件判定为代表的文本分类 text classification问题。
我们要用一个特征向量来表示给定的文本（比如一封email、一则新闻），首先我们需要构造一个词典 vocabulary。将真正意义上的字典里所有的词都列进来当然最为理想，但这会使特征矩阵非常大。习惯上，我们会从整个训练集中抽取所有出现的词（或者进一步，根据TF-IDF词频等算法，抽取权重较高的词）排序后作为词典，中文在抽取过程中还需要首先分词。对于一个训练样本来说，如果其包含词典中第 $i$ 个词，则 $x_i=1$，否则 $x_i=0$。
比如一个词典，包含三个词a, buy, zoo，则向量 $[1, 0, 1]$ 表示一个样本，包含关键词a, zoo，不包含关键词buy。
由特征向量，我们需要构造一个生成模型，对 $p(x|y)$ 建模。设想，我们的词典中包含50000个词，那么 $x \in \{0, 1\}^{50000}$ （$x$ 是一个 $50000$ 维的向量，所有的元素只取 $0$ 或 $1$），如果要用多项分布的假设表示 $2^50000$ 种可能的结果，最终我们需要一个 $2^{50000}-1$ 维的参数向量，这是无法接受的。
所以我们需要一个更强的假设，我们假设 $x_i$ 在给定 $y$ 时相互独立。这个假设称作贝叶斯假设 Naive Bayes(NB) assumption，基于这个假设的算法叫做贝叶斯分类器 Naive Bayes classifier。举个例子，$y=1$ 表示垃圾邮件，buy是词典中第2087个单词，price是词典中第39831个单词，那么我们的假设是，给定一则垃圾邮件（$y=1$），$x_{2087}$ 的取值（buy是否出现在该邮件中）与 $x_{39831}$ 的取值（price是否出现在该邮件中）不相关，即 $p(x_{2087}|y)=p(x_{2087}|y,x_{39831})$。注意这里的假设并不是 $x_{2087}$ 和 ${x_{39831}}$ 相互独立（$p(x_{2087})=p(x_{2087}|x_{39831})$），而是在给定 $y$ 的条件下相互独立。我们有 $$ \begin{split} p(x_1, ..., x_{50000}|y) &= p(x_1|y)p(x_2|y,x_1)p(x_3|y,x_1,x_2) \cdot\cdot\cdot p(x_{50000}|y,x_1,...,x_{49999}) \\ &=p(x_1|y)p(x_2|y)p(x_3|y) \cdot\cdot\cdot p(x_{50000}|y) \\ &=\prod_{i=1}^n p(x_i|y) \end{split} $$
在实际使用中，尽管贝叶斯假设十分严格，但贝叶斯分类器的表现通常较好。
这里，模型的参数包括 $\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)$，给定训练集 $\{(x^{(i)}, y^{(i)}); i=1,...,m\}$，根据样本可以写成联合最大似然函数如下：
$$L(\phi_y,\phi_{i|y=0},\phi_{i|y=1}) = \prod_{i=1}^m p(x^{(i)}, y^{(i)})$$取得最大值时各参数的取值如下： $$ \begin{split} \phi_{j|y=1} &= \frac{\sum_{i=1}^m 1\{x_j^{(i)}=1 \land y_j^{(i)}=1 \}}{\sum_{i=1}^m 1\{y_j^{(i)}=1\}} \\ \phi_{j|y=0} &= \frac{\sum_{i=1}^m 1\{x_j^{(i)}=1 \land y_j^{(i)}=0 \}}{\sum_{i=1}^m 1\{y_j^{(i)}=0\}} \\ \phi_y &= \frac{\sum_{i=1}^m 1\{y^{(i)}=1\}}{m} \end{split} $$
有了以上的参数，给定特征 $x$，我们就可以计算其属于某个分类的概率，然后只要挑选概率最大的分类即可： $$ \begin{split} p(y=1|x) &= \frac{p(x|y=1)p(y=1)}{p(x)} \\ &= \frac{(\prod_{i=1}^n p(x_i|y=1))p(y=1)}{(\prod_{i=1}^n p(x_i|y=1))p(y=1) + (\prod_{i=1}^n p(x_i|y=0))p(y=0)} \end{split} $$
注意到我们这里的朴素贝叶斯主要用于特征 $x$ 均为二元离散变量的情况，但模型可以非常容易地扩展到 $k$ 元离散变量的情况，我们只要假定 $p(x_i|y)$ 服从多项分布即可。即使对于连续型的特征，我们也可以通过分组的办法将其离散化 discretize，然后按照多项分布的方式来建模。尤其，当原先的连续型特征不能很好地满足多维正态分布的情况，特征离散化后使用朴素贝叶斯分类器的效果，通常会比高斯判别分析更好。
假设朴素贝叶斯算法词典中的词，并非取自训练集，而是从其它语料中抽取的。那么就存在这样的可能，即词典中的某个词，训练集中的所有样本都不包含，这个词在词典中排第 $i$ 个，则 $\phi_{i|y=1} = 0 = \phi_{i|y=0}$，这会使得 $p(y=1|x) = \frac{0}{0+0}$，无从进行分类判断。
从统计学的角度来说，因为一个事件在样本中没有发生，就判定这个事件发生的概率为 $0$，这是一个糟糕的估计量。
以多项分布为例，随机变量 $z$ 的取值范围为 $\{1,...,k\}$。对应的各参数 $\phi_i = p(z=i)$。给定 $m$ 个独立观测 $\{z^{(1)}, z^{(2)}, ..., z^{(m)}\}$，其最大似然估计量为 $$ \phi_j = \frac{\sum_{i=1}^m 1\{z^{(i)}=j\}}{m} $$
如果某个分类的值没有在样本里出现，则 $\phi_j$ 就会等于 $0$。为了解决这个问题，我们可以使用拉普拉斯平滑 Laplace smoothing，替换上述估计量为 $$ \phi_j = \frac{\sum_{i=1}^m 1\{z^{(i)}=j\}+1}{m+k} $$
这里，我们对分子增加 $1$，对分母增加 $k$，注意到这样 $\sum_{j=1}^k \phi_j=1$ 的约束依然满足，同时任意 $\phi_j$ 等不会等于0。
对朴素贝叶斯分类器使用拉普拉斯平滑，得到的统计量如下：
$$ \begin{split} \phi_{j|y=1} &= \frac{\sum_{i=1}^m 1\{x_j^{(i)}=1 \land y_j^{(i)}=1 \} + 1}{\sum_{i=1}^m 1\{y_j^{(i)}=1\} + 2} \\ \phi_{j|y=0} &= \frac{\sum_{i=1}^m 1\{x_j^{(i)}=1 \land y_j^{(i)}=0 \} + 1}{\sum_{i=1}^m 1\{y_j^{(i)}=0\} + 2} \\ \end{split} $$在文本分类的语境下，朴素贝叶斯模型也被称作多元伯努利事件模型 multi-variate Bernoulli event model。在这个模型中，以邮件分类为例，我们假设首先，邮件是否为垃圾邮件，是根据先验概率 $p(y)$ 随机决定的，在这之后，对于词典中的每个词，独立地按照概率 $p(x_i|y)=\phi_{i|y}$ 决定是否将这个词加入到邮件中。
而这里我们将介绍多项事件模型 multinomial event model。多项事件模型的特征与朴素贝叶斯有所不同。令 $x_i$ 表示邮件中的第 $i$ 个词，因而这里 $x_i$ 是一个整数，取值范围为 $\{1,...,|V|\}$，其中 $|V|$ 是词典中收录词的数量。一封包含 $n$ 个词的邮件，现在表示为 $n$ 维向量 $(x_1, x_2, ..., x_n)$，注意到对不同的邮件，其长度是可以不一样的。
在多项事件模型中，依然以邮件分类为例：首先也是一个随机过程根据先验概率 $p(y)$ 决定是否为垃圾邮件。之后，根据某个多项分布，按照概率 $p(x_1|y)$ 生成词汇 $x_1$，之后选择 $x_2$ 的过程独立于 $x_1$ 但是来自同一个多项分布。之后是 $x_3, x_4, ..., x_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), \phi_{i|y=0}=p(x_j=i|y=0)$，其联合似然函数为 $$ \begin{split} 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{split} $$
取最大值时的各参数取值如下： $$ \begin{split} \phi_{k|y=1} &= \frac{\sum_{i=1}^m \sum_{j=1}^{n_i} 1\{x_j^{(i)}=k \land y^{(i)} = 1\}}{\sum_{i=1}^m 1\{y^{(i)}=1\}n_i} \\ \phi_{k|y=0} &= \frac{\sum_{i=1}^m \sum_{j=1}^{n_i} 1\{x_j^{(i)}=k \land y^{(i)} = 0\}}{\sum_{i=1}^m 1\{y^{(i)}=0\}n_i} \\ \phi_y &= \frac{\sum_{i=1}^m 1\{y^{(i)}=1\}}{m} \end{split} $$
如果我们希望加入拉普拉斯平滑，则有： $$ \begin{split} \phi_{k|y=1} &= \frac{\sum_{i=1}^m \sum_{j=1}^{n_i} 1\{x_j^{(i)}=k \land y^{(i)} = 1\} + 1}{\sum_{i=1}^m 1\{y^{(i)}=1\}n_i + |V|} \\ \phi_{k|y=0} &= \frac{\sum_{i=1}^m \sum_{j=1}^{n_i} 1\{x_j^{(i)}=k \land y^{(i)} = 0\} + 1}{\sum_{i=1}^m 1\{y^{(i)}=0\}n_i + |V|} \\ \end{split} $$
In [ ]: