ML1-9 高斯判别分析 GDA

1. 判别学习与生成学习

到目前为止，我们主要讨论的是对 $p(y|x;\theta)$ 建模的学习算法，即给定 $x$ 的 $y$ 的条件分布。例如，逻辑回归将 $p(y|x;\theta)$ 建模为 $h_\theta(x)=g(\theta^T x)$，其中 $g$ 是 Sigmoid 函数。我们将讨论一种不同类型的学习算法。

考虑一个分类问题，我们希望根据动物的某些特征学习区分大象（$y=1$）和狗（$y=0$）。

给定一个训练集，像逻辑回归或感知器算法（基本上）试图找到一条直线——即一个决策边界——来分隔大象和狗。然后，为了将一个新动物分类为大象或狗，它检查该动物落在决策边界的哪一侧，并据此做出预测。

这里有一个不同的方法。首先，看看大象，我们可以建立一个关于大象外观的模型。然后，看看狗，我们可以建立一个关于狗外观的独立模型。最后，为了分类一个新动物，我们可以将新动物与大象模型匹配，再与狗模型匹配，看新动物更像大象还是更像我们在训练集中看到的狗。

• 判别学习：直接学习 $p(y|x)$ 的算法（如逻辑回归）或者直接从输入空间 $\mathcal{X}$ 到标签 $\{0, 1\}$ 学习映射的算法（如感知器算法）
• 生成学习：对 $p(x|y)$ （和 $p(y)$） 进行建模

例如，如果 $y$ 表示一个样本是狗（$0$）还是大象（$1$），那么 $p(x|y=0)$ 对狗的特征分布建模，$p(x|y=1)$ 对大象的特征分布建模。

在建模 $p(y)$（称为类先验）和 $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|y)$ 和 $p(y)$ 来表达。实际上，如果我们要计算 $p(y|x)$ 以进行预测，那么我们实际上不需要计算分母，因为（$y$ 并不影响 $p(x)$）：

$$\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)$$

2. 高斯判别分布

我们要看的第一个生成式学习算法是高斯判别分析（GDA）。在这个模型里，我们会假设 $p(x|y)$ 是服从多元正态分布的。

2.1 多元高斯分布

多元高斯分布（也称为多元正态分布）是高斯分布从一维随机变量到 $n$ 维随机变量（或简称为 $n$-随机变量）的推广。换句话说，多元高斯寻求对多个随机变量建模，而不是单变量随机变量。

假设 $X$ 分布为多元高斯分布，即 $X \in \mathbb{R}^{n}$，由均值向量 $\mu \in \mathbb{R}^{n}$ 和协方差矩阵 $\Sigma \in \mathbb{R}^{n \times n}$ 参数化，其中 $\Sigma \succeq 0$ 是对称且半正定的。形式上，这可以写成

$$\mathcal{N}(\mu, \Sigma)$$

其密度由下式给出（$x$ 在这里是个向量）：

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

可以对比一维情形：$f(x) = \frac{1}{\sqrt{2\pi}\sigma} \exp\left(-\frac12 \frac{(x-\mu)^2}{\sigma^2}\right)$

对于一个服从 $N(µ, Σ)$ 分布的随机变量 $X$，它的均值（不出所料）是 $µ$：

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

向量值随机变量 $Z$ 的协方差定义为：

$$\text{Cov}(Z) = \mathbb{E}[(Z - \mathbb{E}[Z])(Z - \mathbb{E}[Z])^T]$$

这推广了实值随机变量的方差概念。协方差还可以定义为：

$$\text{Cov}(Z) = \mathbb{E}[ZZ^T] - (\mathbb{E}[Z])(\mathbb{E}[Z])^T$$

如果 $X \sim \mathcal{N}(\mu, \Sigma)$，则 $\text{Cov}(X) = \Sigma$。

以下是高斯分布密度的一些示例：

• 左侧的图显示均值为零（即 $2 \times 1$ 的零向量）且协方差矩阵 $\Sigma = I$（$2 \times 1$ 单位矩阵）的高斯分布
  • 均值为零且协方差为单位矩阵的高斯分布也称为标准正态分布
• 中间的图显示均值为零且 $\Sigma = 0.6I$ 的高斯分布
• 右侧的图显示均值为零且 $\Sigma = 2I$ 的高斯分布

我们可以发现，当 $\Sigma$ 变大时，高斯分布变得更加 “spread-out”；当 $\Sigma$ 变小时，高斯分布变得更加 “compressed”。这是因为概率密度函数积分为 1。

再来看看另外的一些例子：

上述图形显示均值为 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$ 的非对角线元素增大，密度变得更加向 $45^\circ$ 方向 “compressed”（给定 $x_1 = x_2$），整个分布越来越倾向于将两个随机变量建模为正相关的关系。当我们查看三个密度的等高线时，这一点更清楚：

最后一组关于 $\Sigma$ 的例子：

以上图形分别使用了

$$\Sigma = \begin{bmatrix} 1 & -0.5 \\ -0.5 & 1 \end{bmatrix},\; \Sigma = \begin{bmatrix} 1 & -0.8 \\ -0.8 & 1 \end{bmatrix},\; \Sigma = \begin{bmatrix} 3 & 0.8 \\ 0.8 & 1 \end{bmatrix}$$

从左至中间图中，我们看到通过减小协方差矩阵的非对角线元素，密度再次变得“compressed”，但方向相反。最后，随着参数的变化，更一般地，等高线将形成椭圆（最右侧的图展示了一个例子）。

作为最后一组例子，固定 $\Sigma = I$ ，通过改变 $\mu$ ，我们可以移动密度均值的位置。

上述图形使用

$$\mu = \begin{bmatrix} 1 \\ 0 \end{bmatrix},\; \mu = \begin{bmatrix} -0.5 \\ 0 \end{bmatrix},\; \mu = \begin{bmatrix} -1 \\ -1.5 \end{bmatrix}$$

2.2 GDA 模型

当我们有一个分类问题，其中输入特征 $x$ 是连续值随机变量时，我们可以使用高斯判别分析（GDA） 模型，该模型使用多元正态分布对 $p(x|y)$ 建模。模型如下：

$$\begin{align*} &y \sim \mathrm{Bernoulli}(\phi) \\ &x \mid y = 0 \sim \mathcal{N}(\mu_0, \Sigma) \\ &x \mid y = 1 \sim \mathcal{N}(\mu_1, \Sigma) \end{align*}$$

写出分布：

$p(y) = \phi^y (1 - \phi)^{1-y}$
$p(x|y = 0) = \frac{1}{(2\pi)^{d/2} |\Sigma|^{1/2}} \exp\left( -\frac{1}{2} (x - \mu_0)^T \Sigma^{-1} (x - \mu_0) \right)$
$p(x|y = 1) = \frac{1}{(2\pi)^{d/2} |\Sigma|^{1/2}} \exp\left( -\frac{1}{2} (x - \mu_1)^T \Sigma^{-1} (x - \mu_1) \right)$

这里，我们模型的参数是 $\phi、\Sigma、\mu_0、\mu_1$（注意，虽然有两个不同的均值向量 $\mu_0$ 和 $\mu_1$，但是这个模型通常只使用一个协方差矩阵 $\Sigma$ ）。数据的对数似然由下式给出：

$$\begin{aligned} \ell(\phi,\mu_0,\mu_1,\Sigma) &= \log\prod_{i=1}^n p(x^{(i)},y^{(i)};\phi,\mu_0,\mu_1,\Sigma) \\ &= \log\prod_{i=1}^n p(x^{(i)}\mid y^{(i)};\mu_0,\mu_1,\Sigma)\,p(y^{(i)};\phi) \end{aligned}$$

提示

这里可以看出判别学习与生成学习在似然函数处的不同：

• 生成学习最大化 $p(x|y)p(y)$，也即最大化联合似然 $P(x, y)$
• 判别学习最大化条件似然 $p(y|x)$

通过关于参数最大化 $\ell$，我们得到参数的最大似然估计（关于指示函数1{}）：

$\phi = \frac{1}{n} \sum_{i=1}^n 1\{y^{(i)} = 1\}$
$\mu_0 = \frac{\sum_{i=1}^n 1\{y^{(i)} = 0\} x^{(i)}}{\sum_{i=1}^n 1\{y^{(i)} = 0\}}$
$\mu_1 = \frac{\sum_{i=1}^n 1\{y^{(i)} = 1\} x^{(i)}}{\sum_{i=1}^n 1\{y^{(i)} = 1\}}$
$\Sigma = \frac{1}{n} \sum_{i=1}^n (x^{(i)} - \mu_{y^{(i)}})(x^{(i)} - \mu_{y^{(i)}})^T$

算法的效果如下图所示：

图中显示了训练集，以及拟合到两个类别数据的两个高斯分布的等高线。注意，两个高斯分布具有相同的形状和方向的等高线，因为它们共享协方差矩阵 $\Sigma$ ，但具有不同的均值 $\mu_0$，$\mu_1$。图中还显示了决策边界所在的直线，此处 $p(y=1|x) = 0.5$。因此，在边界的一侧，我们预测 $y = 1$，在另一侧，我们预测 $y = 0$。

Why Two Separate Means, but a Single Covariance Matrix？

如果你选择用两种不同的均值和一个共同的协方差矩阵来构建模型，那么决策边界会是线性的，这种情况适用于很多问题。
选择使用两个不同的协方差矩阵是合理的，应该也能很好地工作。不过，需要注意的是，你会将近似地翻倍参数数量，最终得到的决策边界就不再是线性的了。

2.3 GDA 与逻辑回归

下面的图展示了逻辑回归的决策边界（绿色），它叠加在GDA示意图中。注意，这两个算法实际上得到了稍微不同的决策边界。

GDA 模型与逻辑回归之间有一个有趣的关系。假设我们已经拟合GDA的一系列参数，对于某个给定的 $x$，利用贝叶斯公式可以计算出

$$P(y = 1 \mid x; \phi, \mu_0, \mu_1, \Sigma) = \frac{P(x \mid y = 1; \phi, \mu_0, \mu_1, \Sigma)\,P(y = 1; \phi)}{P(x; \phi, \mu_0, \mu_1, \Sigma)}$$

咱们来画一下 $P(y = 1 \mid x)$ 的取值情况，看看在不同的 $x$ 值下它长什么样。要做到这点，先考虑一个简单的数据集，里面只有一个特征 ，还有一些负样本和一些正样本，就像下面这样：

现在使用 GDA 在该数据集上进行操作。为此，需要给这两个类别分别拟合一个高斯分布，如下图。注意，我们给这两个高斯分布设置了相同的方差。因为数据集在两个类之间是50-50分割的，所以 $P(Y=1) = 0.5$，也称为二分之一先验。

接下来，就可以绘制 $P(y = 1 \mid x)$ 的图形：

我们可以注意到将绘制出的点连成线，这个图形将与 sigmoid 函数的样子非常相似。实际上，如果将 $p(y=1|x; \phi, \mu_0, \mu_1, \Sigma)$ 视为 $x$ 的函数，那么它可以表示为以下形式：

$$p(y=1|x; \phi, \Sigma, \mu_0, \mu_1) = \frac{1}{1 + \exp(-\theta^T x)}$$

其中，$\theta$ 是 $\phi、\Sigma、\mu_0、\mu_1$ 的某个适当函数，$x_0 = 1$ 以将常数项压入 $\theta$。这个形式恰好与逻辑回归的建模相对应。

因此，如果 $p(x|y)$ 是多元高斯分布（注意这里必须要共享 $\Sigma$，否则之前的表示不成立，因为无法消去二次项），那么 $p(y|x)$ 必然遵循逻辑函数。然而，反过来并不成立：即 $p(y|x)$ 是逻辑函数并不意味着 $p(x|y)$ 是多元高斯分布。

这表明 GDA 对数据做出了比逻辑回归更强的建模假设。事实证明，当这些建模假设正确时，GDA 会找到对数据更好的拟合，并且是一个更好的模型。具体来说，当 $p(x|y)$ 确实是高斯分布（具有共享 $\Sigma$）时，GDA 是渐近有效的。非正式地说，这意味着在极大训练集（大的 $n$）的极限下，没有算法比 GDA 严格更好（在估计 $p(y|x)$ 的准确性方面）。特别地，可以证明在这种设定下，GDA 将是比逻辑回归更好的算法；而且更一般地，即使在较小训练集规模下，我们通常也期望 GDA 更好。

相比之下，通过做出显著更弱的假设，逻辑回归也更加鲁棒，对不正确的建模假设不那么敏感。有许多不同的假设集使得 $p(y|x)$ 呈现逻辑函数的形式。例如，如果 $x|y = 0 \sim \mathrm{Poisson}(\lambda_0)$ 且 $x|y = 1 \sim \mathrm{Poisson}(\lambda_1)$，那么 $p(y|x)$ 将是逻辑函数。逻辑回归在这样的泊松数据上也会很好地工作。但如果我们在这样的数据上使用 GDA——将高斯分布拟合到非高斯数据上——那么结果会较难预测，GDA 可能（也可能不）表现良好。

参考

1. CS229 课程讲义

   https://cs229.stanford.edu/main_notes.pdf

2. Amann's Algorithm • CS229 • Gaussian Discriminant Analysis

   https://aman.ai/cs229/gda/