引入
在前面的课程中，我们学会了使用 Logistic 回归来解决二分类问题。
- Logistc 回归本质上是一种判别学习算法（Discriminative Learning Algorithm），目标是找到一个决策边界或者一个条件概率分布函数，将输入数据映射到对应的类别或者数值。
- 与此不同，本节课学习的 GDA 和 Naive Bayes 本质上是生成学习算法（Generative Learning Algorithm），即通过学习输入数据和标签的联合概率分布来进行分类或回归任务。
上面的说法还是有点抽象，我们以肿瘤性质预测任务为例进行分析。假设输入特征 \(x\) 是肿瘤的大小。
对于判别学习算法来说，目标是学习到一个良性肿瘤和恶性肿瘤的边界——也就是“\(x\) 大于某个值时表明肿瘤是恶性，小于某个值时肿瘤是良性”。从概率的角度来说，我们学到的其实是 \(P(y | x)\) 。当获得新的输入 \(x^*\) 时，只需要计算 \(P(y=1 | x = x^*)\) 和 \(P(y = 0 | x = x^*)\) ，然后比较两者的大小就能够做出预测。
对于生成学习算法来说，我们学到的是 \(P(x | y)\) 和 \(P(y)\) 。
- \(P(x|y)\) 表示给定\(y\) 的时候 \(x\) 的概率，具体来说\(P(x| y=1)\) 表示恶性肿瘤大小的概率分布，\(P(x| y=1)\) 表示良性肿瘤大小的概率分布。因此，最终我们每个类别都建立一个概率分布。
- \(P(y)\) 表示 \(y\) 本身的概率，具体来说 \(P(y = 1)\) 表示恶性肿瘤出现的概率，\(P(y = 0)\) 表示良性肿瘤出现的概率。
最终，我们的目标仍然是“给定一个输入\(x\)，预测对应 的\(y\)”，即找到 \(\mathop{\arg\max}\limits_{y}P(y | x)\)。根据贝叶斯公式，我们有
\[ \begin{aligned} &P(y=1 \mid x) = \frac{P(x|y=1) \cdot P(y = 1)}{P(x)} = \frac{P(x|y=1) \cdot P(y =1)}{P(x|y = 1) \cdot P(y=1) + P(x|y=0) \cdot P(y=0) } \\ &P(y=0 \mid x) = \frac{P(x|y=0) \cdot P(y = 0)}{P(x)} = \frac{P(x|y=0) \cdot P(y = 0)}{P(x|y = 1) \cdot P(y=1) + P(x|y=0) \cdot P(y=0) } \end{aligned} \]
对于一个特定输入\(x^*\), 我们只需要比较\(P(y = 1 | x = x^*)\) 和 \(P(y = 0 | x = x^*)\) 的相对大小即可。又因为\(P(x)\) 是相同的，我们只需要比较\(P(x|y) \cdot P(y)\)即可。\(P(x|y) \cdot P(y)\) 也即是联合概率分布\(P(x,y)\) ，因此前面我们说“生成学习算法实际上是学习的输入数据和标签的联合概率分布”。
高斯判别分析（GDA）
高斯判别分析是生成学习算法中的一种。在数据集非常小的时候执行速度很快，只需要以此计算，不需要迭代。
关键假设
在 GDA 中，我们假设 :
- \(x | y\) 满足多元高斯分布（Gaussian）
- \(y\) 满足伯努利分布（Bernoulli）
模型参数
假如是二分类任务，根据上述假设我们有
\[ \begin{aligned} &P(x \mid y=0) = \frac{1}{\sqrt{(2\pi)^n|\sum|}} \exp (-\frac{1}{2} (x - \mu_0)^T \mathop{\sum}\nolimits^{-1}(x - \mu_0)) \\ &P(x \mid y=1) = \frac{1}{\sqrt{(2\pi)^n|\sum|}} \exp (-\frac{1}{2} (x - \mu_1)^T \mathop{\sum}\nolimits^{-1}(x - \mu_1)) \\ &P(y) = \phi^y(1-\phi)^{1-y} \end{aligned} \]
不难看出有四个参数：
- \(\mu_0 \in \mathbb{R}^n\)
- \(\mu_1 \in \mathbb{R}^n\)
- \(\sum \in \mathbb{R}^{n \times n }\)
- \(\phi \in \mathbb{R}\)。
因为我们假定\(P(x | y=0)\)和\(P(x | y=1)\) 有相同协方差矩阵，因此并没有 \(\sum\nolimits_0\) 和 \(\sum\nolimits_1\) 之分，而是使用同一个\(\sum\)。当我们采用同一个\(\sum\) ，最终的决策边界是线性的，比较适合需要线性边界的分类问题。当然可以用不同的\(\sum\)，但这样决策边界就不是线性的了，同时也增加了计算量。
训练
我们采用最大似然估计来找到这四个参数的值。在判别学习算法中，比如 Logistic 回归，我们使用的是条件似然（conditional likehood）。而对于生成学习算法，我们使用的是联合似然（joint likehood），似然函数的定义为
\[ \begin{aligned} \mathcal{L}(\phi, \mu_0, \mu_1,\sum) &= \prod_{i=1}^m P( x^{(i)},y^{(i)}; \ \ \phi, \mu_0, \mu_1,\sum ) \\ &= \prod_{i=1}^m P( x^{(i)} \mid y^{(i)}; \ \ \phi, \mu_0, \mu_1,\sum ) \cdot P(y^{(i)})\\ \end{aligned} \]
我们对似然函数取对数得到\(\ell(\phi, \mu_0, \mu_1,\sum)\)，并令其导数等于0，得到最终的参数值：
$$\[\begin{aligned} & \phi = \frac{\sum\limits_{i=1}^m y^{(i)}}{m} = \frac{\sum\limits_{i=1}^m \mathcal{I}(y^{(i)}=1)}{m} \\\\ & \mu_0 = \frac{\sum\limits_{i=1}^m \mathcal{I}(y^{(i)} =0) \cdot x^{(i)} }{\sum\limits_{i=1}^m \mathcal{I}(y^{(i)} =0)} \\\\ & \mu_1 = \frac{\sum\limits_{i=1}^m \mathcal{I}(y^{(i)} =1) \cdot x^{(i)} }{\sum\limits_{i=1}^m \mathcal{I}(y^{(i)} = 1)} \\\\ & \sum = \frac{1}{m}\sum_{i=1}^{m}(x^{(i)} - \mu \cdot y^{(i)}) (x^{(i)} - \mu \cdot y^{(i)})^T \end{aligned}\]
$$
其中 \(\mathcal{I}(A)\) 是指示器函数（Indicator）
\[ \mathcal{I}(A) = \begin{cases} 1, & \text{if } A = \tt{true} \\ 0, & \text{if } A = \tt{false} \end{cases} \]
预测
给定输入 \(x\)，我们可以利用上面训练得到的参数，找到对应的预测值 \(y\)
\[ \begin{aligned} y &= \mathop{\arg\max}\limits_y P(y | x) \\ &= \mathop{\arg\max}\limits_y \frac{P(y) \cdot P(x | y)}{P(x)} \end{aligned} \]
因为 \(P(x)\) 是相同的，只起到归一化的作用，所以我们通常可以不用计算（除非需要求出具体的概率值），即
\[ y = \mathop{\arg\max}\limits_y (P(y) \cdot P(x | y)) \]
判别学习算法和生成学习算法
我们可以画出\(P(x\mid y=1)\)、\(P(x \mid y = 0)\) 以及对应的\(P(y=1 \mid x)\)的图像。
不难看出，\(P(y=1 \mid x)\)的图像很像 Logistc 函数。实际上，GDA这些概率分布假设是可以 推出 \(P(y=1 \mid x)\) 是Logistic函数，但是反之不成立。也就是说，GDA的假设更强一些（strong assume），Logistic 的假设更弱一些（weak assume）。
当然，如果 \(x|y=0\) 和 \(x | y=1\) 取指数族的其他分布，比如泊松分布，也能够推出$ P(y=1 x)$ 是 Logistic 函数。反之同样不可以。
设置更强的假设实际上是为模型注入了更多的信息。因此，当我们数据量比较少时，可以通过设置比较强的假设提高模型的效果。但是，如果假设和实际的偏差比较大，模型效果可能会非常差。所以，如果事先不知道 \(x \mid y\) 属于什么分布时，还是使用 Logistic 回归比较可靠。
在大数据时代，我们可以获得非常多的数据来训练模型，因此可以不需要设置假设，直接让模型从数据中获得信息即可。像GPT2、GPT3、GPT4 等模型，也都是采用了“暴力美学”的思想，给模型投喂大量的数据，最终获得了amazing的效果。
朴素贝叶斯
朴素贝叶斯（Naive Bayes）是一种基于贝叶斯定理的简单且常用的分类算法。它假设特征之间相互独立，即特征之间没有任何关联。尽管这个假设在现实中往往是不成立的，但朴素贝叶斯仍然在许多实际问题中表现良好。
问题引入
我们可以通过“垃圾邮件分类”问题来介绍朴素贝叶斯算法。在该问题中，输入特征 \(x\) 是一个n 维向量，n是词典的大小，\(x\) 每一个分量表示“词典该位置的单词是否出现”。标签 \(y\) 为0 或者 1，表示是否为垃圾邮件。
假设词典为 [a, English， I， like，zoo]，维度为5。有一封邮件的内容为“I like Englist”，则对应的 \(x\) 就是
\[ x = \begin{bmatrix} 0 &1 & 1 & 1 & 0 \end{bmatrix}^T \]
如果我们使用生成学习算法，则需要对\(P(x | y)\) 进行建模。因为词典的规模一般非常大，假设n = 10000，则 \(x\) 的可能取值的数量就达到\(2^{10000}\)，然后我们需要\((2^{100000} - 1)\)维的参数向量，这就太过复杂了。
问题解决
思路
如果应用朴素贝叶斯，那么问题就会变得简单——即假设给定\(y\) 值的条件下，\(x\) 的各个分量都是独立的，即
\[ \begin{aligned} P(x|y) &= P(x_1, x_2, ..., x_n \mid y) \\ &= P(x_1 \mid y) P(x_2 \mid y)\ ... \ P(x_n \mid y) \end{aligned} \]
具体到这个例子，就是说——在该邮件是垃圾邮件的条件下（\(y = 1\)），
模型参数
我们假设 \(P(x \mid y)\) 和 \(P(y)\) 都遵循伯努利分布，则模型具有以下参数
- \(\phi_{j \mid y = 1} = P(x_j = 1 \mid y = 1)\)
- \(\phi_{j \mid y = 0} = P(x_j = 1 \mid y = 0)\)
- \(\phi_y = p(y = 1)\)
训练
我们采用最大似然估计来找到这三个参数的值。似然函数 $(y, {jy=1}, _{jy=0}) $ 的定义如下所示
$$\[\begin{aligned} \mathcal{L}(\phi_y, \phi_{j\mid y=1}, \phi_{j\mid y=0}) &= \prod_{i = 1}^{n} P(x^{(i)}, y^{(i)}; \phi_y, \phi_{j\mid y=1}, \phi_{j\mid y=0}) \end{aligned}\]
$$
令其导数等于0，得到最终的参数值
$$\[\begin{aligned} &\phi_y \ \ \ \ \ \ = \frac{\sum\limits_{i=1}^m \mathcal{I}(y^{(i)} = 1)}{m} \\ & \phi_{j \mid y = 1} = \frac{\sum\limits_{i=1}^m \mathcal{I}(x_j^{(i)} = 1, y^{(i)} = 1)}{\sum\limits_{i=1}^m \mathcal{I}(y^{(i)} = 1)} \\ & \phi_{j \mid y = 0} = \frac{\sum\limits_{i=1}^m \mathcal{I}(x_j^{(i)} = 1, y^{(i)} = 0)}{\sum\limits_{i=1}^m \mathcal{I}(y^{(i)} = 0)} \\ \end{aligned}\]
$$
预测
预测时可以使用贝叶斯公式，结合朴素贝叶斯的假设，我们有
\[ \begin{aligned} y &= \mathop{\arg\max}\limits_y P(y | x) \\ &= \mathop{\arg\max}\limits_y \frac{P(y) \cdot P(x | y)}{P(x)} \\ &= \mathop{\arg\max}\limits_y \frac{P(y) \cdot P(x_1 | y) \cdot P(x_2 | y) \dots P(x_n | y)}{P(x)} \end{aligned} \]
