判别式和生成式
对于一个分类任务，判别式和生成式分别代表了两种不同的思路：
判别式
通过直接从输入数据中学习，得到一个『特定输入对应的实际类别』的概率模型，模型的参数为 \(\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)\]
Gaussian discriminant analysis
作为生成式模型的第一个例子，它假设数据的分布 \(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 和 Logistic 回归
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\)，\(k\) 是多项式分布可选的类的数量。所以我们分母也需要稍作改动，最终我们得到
\[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}\]
多项式分布事件模型和之前的模型的不同点在于，新模型除了统计某一个词是否出现，还考虑了某一个词出现的次数。
