生成学习算法
目前为止说过的学习算法的模型都是$p(y \mid x;\theta)$，也就是给定$x$下的$y$的条件分布，以$\theta$为参数。例如，逻辑回归就是以$h_{\theta}(x)=g(\theta^Tx)$作为$p(y \mid x;\theta)$的模型，这里的$g$是一个sigmoid函数，接下来要讲一个不同类型的学习算法。
设想有这样的一种分类问题，我们要学习基于一个动物的某个特征来辨别它是大象(y=1)还是小狗(y=0)。给定一个训练集，用逻辑回归或者基础版的感知器算法这样的一个算法能找到一条直线，作为区分大象和小狗的边界。然后我们只要看值落在哪个区域就可以分辨出是大象还是小狗。
或者还有另外一种算法。首先，观察大象，然后我们针对大象的样子来进行建模。然后再观察小狗，针对小狗的样子另外建立一个模型。最后我们只需要把动物和这两个模型比对，越接近哪个就是哪个动物。
例如逻辑回归之类的直接试图建立$p(y \mid x)$的算法，以及感知器算法等直接用投图的思路来判断对应$X$的值落到了{0，1}中哪个区域的算法，这些都叫判别式学习算法。和之前的这些判别式算法不同，下面我们要讲的新算法是对$p(y \mid x)$和$p(y)$来进行建模。这类算法叫做生成学习算法。例如如果$y$是用来表示一个样例是小狗(0)或者大象(1)，那么$p(x \mid y=0)$就是对小狗特征的分布的建模，反之，$p(x \mid y=1)$就是对大象特征分布的建模。
在对 $p(y)$（称为分类先验）和 $p(x \mid y)$ 进行建模之后，我们的算法可以使用贝叶斯法则在给定 $x$ 的情况下输出后验分布：
$$ p(y \mid x) = \frac{p(x \mid y)p(y)}{p(x)}. $$这里，分母
$$ p(x) = p(x \mid y=1)p(y=1) + p(x \mid y=0)p(y=0) $$给出，因此也可以用我们学习到的 $p(x \mid y)$ 和 $p(y)$ 表示。实际上，如果为了进行预测而计算 $p(y \mid x)$，那么我们实际上并不需要计算分母，因为
$$ \arg\max_y p(y \mid x) = \arg\max_y \frac{p(x \mid y)p(y)}{p(x)} = \arg\max_y p(x \mid y)p(y). $$高斯判别分析
我们要学习的第一个生成学习算法就是高斯判别分析，在这个模型里面，我们假设$p(x \mid y)$是一个多元正态分布。所以首先我们简单讲下多元正态分布的一些特点
多元正态分布
$n$ 维的多元正态分布，也称为多元高斯分布，由均值向量 $\mu \in \mathbb{R}^n$ 以及协方差矩阵$\Sigma \in \mathbb{R}^{n \times n}$ 参数化，其中 $\Sigma \ge 0$ 是半正定对称矩阵。多元正态分布也写为 $\mathcal{N}(\mu, \Sigma)$，其密度由下式给出：
$$ p(x; \mu, \Sigma) = \frac{1}{(2\pi)^{n/2} \lvert \Sigma \rvert^{1/2}} \exp\!\left( -\frac{1}{2}(x-\mu)^T \Sigma^{-1} (x-\mu) \right). $$在上面的等式中，“$|\Sigma|$”的意思是矩阵 $\Sigma$ 的行列式，对于一个在 $\mathcal{N}(\mu,\Sigma)$ 分布中的随机变量 $X$，其平均值就是$\mu$了
$$ E[X] = \int_x x\, p(x;\mu,\Sigma)\, dx = \mu. $$向量值随机变量 $Z$ 的协方差定义为$\mathrm{Cov}(Z) = E[(Z - E[Z])(Z - E[Z])^T]$。这概括了实值随机变量方差的概念。协方差也可以定义为$\mathrm{Cov}(Z) = E[ZZ^T] - (E[Z])(E[Z])^T$。如果 $X \sim \mathcal{N}(\mu,\Sigma)$，那么
$$ \mathrm{Cov}(X) = \Sigma $$高斯判别分析模型
假如我们有一个分类问题，其中输入特征$x$是一系列的连续随机变量，那就可以使用高斯判别分析模型，其中对$p(x \mid y)$用多元正态分布来进行建模，这个模型为：
$$ \begin{array}{c} 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{array} $$分布写出来的具体形式如下：
$$ \begin{array}{rcl} p(y) &=& \phi^y(1-\phi)^{1-y} \\ p(x \mid y=0) &=& \dfrac{1}{(2\pi)^{n/2}\,|\Sigma|^{1/2}} \exp\!\left(-\dfrac{1}{2}(x-\mu_0)^T\Sigma^{-1}(x-\mu_0)\right) \\ p(x \mid y=1) &=& \dfrac{1}{(2\pi)^{n/2}\,|\Sigma|^{1/2}} \exp\!\left(-\dfrac{1}{2}(x-\mu_1)^T\Sigma^{-1}(x-\mu_1)\right) \end{array} $$这里，我们的模型的参数是 $\phi, \Sigma, \mu_0, \mu_1$。（虽然存在两个不同的均值向量 $\mu_0$ 和 $\mu_1$，但是该模型通常仅使用同一个协方差矩阵 $\Sigma$。）数据的对数似然性由下式给出：
$$ \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)} \mid y^{(i)};\mu_0,\mu_1,\Sigma)\, p(y^{(i)};\phi). $$通过参数最大化$l$，然后就能找到该参数组合对应的最大似然估计如下
$$ \begin{array}{rcl} \phi &=& \dfrac{1}{m}\displaystyle\sum_{i=1}^m 1\{y^{(i)} = 1\} \\ \mu_0 &=& \dfrac{\displaystyle\sum_{i=1}^m 1\{y^{(i)} = 0\}\, x^{(i)}} {\displaystyle\sum_{i=1}^m 1\{y^{(i)} = 0\}} \\ \mu_1 &=& \dfrac{\displaystyle\sum_{i=1}^m 1\{y^{(i)} = 1\}\, x^{(i)}} {\displaystyle\sum_{i=1}^m 1\{y^{(i)} = 1\}} \\ \Sigma &=& \dfrac{1}{m}\displaystyle\sum_{i=1}^m \big(x^{(i)} - \mu_{y^{(i)}}\big) \big(x^{(i)} - \mu_{y^{(i)}}\big)^T \end{array} $$推导过程如下：
先观察 $P(x \mid y)$ 的形式，可以得到如下公式
$$ P(x\mid y)=\frac{1}{(2\pi)^{n/2}\,|\Sigma|^{1/2}} \exp\!\left(-\frac{1}{2}(x-\mu_y)^{T}\Sigma^{-1}(x-\mu_y)\right) $$接着计算 $\log P(x,y)$
$$ \begin{array}{rcl} \log P(x,y) & = & \log P(x\mid y)P(y)\\ & = & \log\Bigg( \frac{1}{(2\pi)^{n/2}\lvert\Sigma\rvert^{1/2}} \exp\!\left( -\frac{1}{2}(x-\mu_y)^T\Sigma^{-1}(x-\mu_y) \right) \phi^{1(y=1)} (1-\phi)^{1(y=0)} \Bigg)\\ & = & \,-\frac{n}{2}\log(2\pi) \,-\frac{1}{2}\log\lvert\Sigma\rvert \,-\frac{1}{2}(x-\mu_y)^T\Sigma^{-1}(x-\mu_y)+ 1(y=1)\log\phi+ 1(y=0)\log(1-\phi) \end{array} $$对数似然函数为：
$$ \begin{aligned} \ell(\phi,\mu_0,\mu_1,\Sigma) &= \log\prod_{i=1}^{m} p(x^{(i)},y^{(i)};\phi,\mu_0,\mu_1,\Sigma) \\ &= \sum_{i=1}^{m} \log p(x^{(i)},y^{(i)};\phi,\mu_0,\mu_1,\Sigma) \\ &= \sum_{i=1}^{m}\Bigg( \log\frac{1}{(2\pi)^{n/2}\det(\Sigma)^{1/2}} -\frac{1}{2}(x^{(i)}-\mu_{y^{(i)}})^T \Sigma^{-1}(x^{(i)}-\mu_{y^{(i)}})+ 1(y^{(i)}=1)\log\phi+ 1(y^{(i)}=0)\log(1-\phi) \Bigg) \end{aligned} $$关于 $\phi$ 求梯度
$$ \begin{array}{rcl} \displaystyle\frac{\partial \ell}{\partial \phi} &=& \displaystyle \sum_{i=1}^{m} \left( \frac{\mathbf{1}\{y^{(i)}=1\}}{\phi} -\frac{\mathbf{1}\{y^{(i)}=0\}}{1-\phi} \right) = 0 &\Longrightarrow& \displaystyle\sum_{i=1}^{m}\mathbf{1}\{y^{(i)}=1\} = m\phi &\Longrightarrow& \displaystyle \phi=\frac{1}{m}\sum_{i=1}^{m}\mathbf{1}\{y^{(i)}=1\} \end{array} $$关于 $\mu_1,\mu_0$ 求梯度
$$ \begin{array}{rcl} \nabla_{\mu_1}\ell &=& \displaystyle \sum_{i=1}^{m} \Sigma^{-1}(x^{(i)}-\mu_{y^{(i)}})\, 1_{y^{(i)}=1} = 0 &\Longrightarrow& \sum_{i=1}^{m} (x^{(i)}-\mu_1)\, 1_{y^{(i)}=1} = 0 &\Longrightarrow& \mu_1=\frac{\sum_{i=1}^{m} \mathbf{1}\{y^{(i)} = 0\} \, x^{(i)}}{\sum_{i=1}^{m} \mathbf{1}\{y^{(i)} = 0\}} \end{array} $$关于 $\Sigma$ 的极大似然估计
$$ \nabla_A \log|A| = (A^{-1})^T, \nabla_A(x^T A y) = xy^T $$$$ \begin{array}{rcl} \nabla_{\Sigma^{-1}}\ell &=& \nabla_{\Sigma^{-1}} \left( \frac{m}{2}\log|\Sigma^{-1}| \right) -\frac{1}{2}\nabla_{\Sigma^{-1}} \sum_{i=1}^{m} (x^{(i)}-\mu_{y^{(i)}})^T \Sigma^{-1} (x^{(i)}-\mu_{y^{(i)}}) = 0 &\Longrightarrow& \displaystyle \frac{m}{2}\Sigma -\frac{1}{2}\sum_{i=1}^{m} (x^{(i)}-\mu_{y^{(i)}}) (x^{(i)}-\mu_{y^{(i)}})^T = 0 &\Longrightarrow& \displaystyle \Sigma =\frac{1}{m}\sum_{i=1}^{m} (x^{(i)}-\mu_{y^{(i)}}) (x^{(i)}-\mu_{y^{(i)}})^T \end{array} $$因此结论成立。
讨论：高斯判别分析与logistic回归
高斯判别分析模型与逻辑回归有很有趣的相关性。如果我们把变量 $ p(y = 1 \mid x; \phi, \mu_0, \mu_1, \Sigma) $作为一个 \(x\) 的函数，就会发现可以用如下的形式来表达：
$$ p(y = 1 \mid x; \phi, \Sigma, \mu_0, \mu_1)=\frac{1}{1 + \exp(-\theta^T x)} $$其中的 \(\theta\) 是对 \(\phi, \Sigma, \mu_0, \mu_1\) 的某种函数。这就是逻辑回归（也是一种判别分析算法）用来对\( p(y = 1 \mid x) \)建模的形式。
Proof：
先计算 \( P(x) \)
$$ P(x)=P(y = 1) P(x \mid y = 1)+P(y = 0) P(x \mid y = 0) $$$$ \left. \begin{array}{l} P(x)= \phi \dfrac{1}{(2\pi)^{n/2}|\Sigma|^{1/2}} \exp\!\left(-\dfrac{1}{2}(x-\mu_1)^T \Sigma^{-1}(x-\mu_1) \right)+ (1-\phi) \dfrac{1}{(2\pi)^{n/2}|\Sigma|^{1/2}} \exp\!\left(-\dfrac{1}{2}(x-\mu_0)^T \Sigma^{-1}(x-\mu_0) \right) \end{array} \right. $$利用贝叶斯公式计算 \( P(y \mid x) \)，分别对 \( y = 1, y = 0 \) 计算：
$$ P(y \mid x)= \frac{P(x \mid y) P(y)}{P(x)} $$因此，
$$ \left. \begin{array}{lcl} P(y=1 \mid x) & = & \dfrac{P(x \mid y=1)P(y=1)} {\phi \dfrac{1}{(2\pi)^{n/2}|\Sigma|^{1/2}} \exp\!\left(-\dfrac12 (x-\mu_1)^T\Sigma^{-1}(x-\mu_1)\right) +(1-\phi)\dfrac{1}{(2\pi)^{n/2}|\Sigma|^{1/2}} \exp\!\left(-\dfrac12 (x-\mu_0)^T\Sigma^{-1}(x-\mu_0)\right)} \\[1em] & = & \dfrac{\dfrac{1}{(2\pi)^{n/2}|\Sigma|^{1/2}} \exp\!\left(-\dfrac12 (x-\mu_1)^T\Sigma^{-1}(x-\mu_1)\right)\phi} {\phi \dfrac{1}{(2\pi)^{n/2}|\Sigma|^{1/2}} \exp\!\left(-\dfrac12 (x-\mu_1)^T\Sigma^{-1}(x-\mu_1)\right) +(1-\phi)\dfrac{1}{(2\pi)^{n/2}|\Sigma|^{1/2}} \exp\!\left(-\dfrac12 (x-\mu_0)^T\Sigma^{-1}(x-\mu_0)\right)} \\[1em] & = & \dfrac{1} {1+\dfrac{1-\phi}{\phi} \exp\!\left( -\dfrac12 (x-\mu_0)^T\Sigma^{-1}(x-\mu_0) +\dfrac12 (x-\mu_1)^T\Sigma^{-1}(x-\mu_1) \right)} \end{array} \right. $$计算指数部分
$$ \left. \begin{array}{lcl}-\dfrac12 (x-\mu_0)^T\Sigma^{-1}(x-\mu_0)+ \dfrac12 (x-\mu_1)^T\Sigma^{-1}(x-\mu_1)& = & \dfrac{1}{2} \Big( x^T\Sigma^{-1}x- 2\mu_1^T\Sigma^{-1}x+ \mu_1^T\Sigma^{-1}\mu_1 - x^T\Sigma^{-1}x+ 2\mu_0^T\Sigma^{-1}x- \mu_0^T\Sigma^{-1}\mu_0 \Big) \\& = & \dfrac{1}{2} \Big( 2(\mu_0^T\Sigma^{-1}-\mu_1^T\Sigma^{-1})x+ \mu_1^T\Sigma^{-1}\mu_1- \mu_0^T\Sigma^{-1}\mu_0 \Big) \\& = & (\mu_0^T\Sigma^{-1}-\mu_1^T\Sigma^{-1})x+ \dfrac{1}{2} \big( \mu_1^T\Sigma^{-1}\mu_1- \mu_0^T\Sigma^{-1}\mu_0 \big) \end{array} \right. $$so
$$ \left. \begin{array}{lcl} P(y=1 \mid x) & = & \dfrac{1} {1 + \dfrac{1-\phi}{\phi} \exp\!\left( (\mu_0^T\Sigma^{-1}-\mu_1^T\Sigma^{-1})x+ \dfrac12(\mu_1^T\Sigma^{-1}\mu_1-\mu_0^T\Sigma^{-1}\mu_0) \right)} \\ & = & \dfrac{1} {1 + \exp\!\left( (\mu_0^T\Sigma^{-1}-\mu_1^T\Sigma^{-1})x+ \dfrac12(\mu_1^T\Sigma^{-1}\mu_1-\mu_0^T\Sigma^{-1}\mu_0)+ \ln\dfrac{1-\phi}{\phi} \right)} \end{array} \right. $$令
$$ \left. \theta= (\mu_1^T\Sigma^{-1}-\mu_0^T\Sigma^{-1})^T= \Sigma^{-1}(\mu_1-\mu_0) \qquad \theta_0=-\dfrac12(\mu_1^T\Sigma^{-1}\mu_1-\mu_0^T\Sigma^{-1}\mu_0)- \ln\dfrac{1-\phi}{\phi} \right. $$从而
$$ \left. p(y=1 \mid x;\phi,\Sigma,\mu_0,\mu_1)= \dfrac{1}{1+\exp\!\big(-(\theta^T x+\theta_0)\big)} \right. $$那么这两个模型，我们应该如何选择呢？一般来说，高斯判别分析和logistic回归，对同一个训练集，可能给出的判别曲线是不一样的。哪一个更好一点呢？