生成学习算法

logistic回归的执行过程就是要搜索这样的一条直线，能够将两类数据分隔开。

判别学习算法描述为以下公式： $$ Learns \quad P(y|X) \quad or \quad learns \quad h_\Theta(X) \in \{0, 1\} \quad directly. $$

所以logistics回归是判别学习算法的一个例子。

一个生成学习算法给定所属的类的情况下显示某种特定特征的概率。其计算公式如下： $$ P(y=1|X) = \frac {P(X|y=1)P(y)} {P(X)} \\ P(X) = p(y=0|X)P(X) + P(y=1|X)P(X) $$ 一个生成学习算法一开始是对$P(X|y)$进行建模，而不是对$P(y|X)$。

高斯判别分析

推导过程： $$ 假设 \quad X \in \mathbb R^n, \quad 并且是连续的 \\ 假设 \quad P(X|y) \quad 服从高斯分布 \\ 随机变量z \sim N(\mu, \Sigma), \quad 这里\mu是均值，\Sigma是协方差 = E[(X-\mu)(X-\mu)^T] \\ 那么概率密度函数为P(z) = \frac 1 {(2\pi)^{\frac n 2}|\Sigma|^{\frac 1 2}} exp(- \frac 1 2 (X-\mu)^T\Sigma^{-1}(X-\mu)) \\ P(y) = \phi^y(1-\phi)^{1-y} \\ P(X|y=0) = \frac 1 {(2\pi)^{\frac n 2}|\Sigma|^{\frac 1 2}}exp(- \frac 1 2 (X-\mu_0)^T\Sigma^{-1}(X-\mu_0)) \\ P(X|y=1) = \frac 1 {(2\pi)^{\frac n 2}|\Sigma|^{\frac 1 2}}exp(- \frac 1 2 (X-\mu_1)^T\Sigma^{-1}(X-\mu_1)) \\ 参数的对数似然性公式为 \quad \ell(\phi, \mu_0, \mu_1, \Sigma) = log\Pi_{i=1}^mP(X^{(i)}, y^{(i)}) \\ = log\Pi_{i=1}^mP(X^{(i)}| y^{(i)})P(y^{(i)})，这个是Joint \quad likelihood\\ 这里对比logistics回归里的参数对数似然性公式为\quad \ell(\Theta) = log\Pi_{i=1}^mP(y^{(i)|X^{(i)}}; \Theta)，这个是Conditional \quad likelihood\\ 最大化\ell得出\\ \phi = \frac {\Sigma_i y^{(i)}} m = \frac {\Sigma_i \mathbb 1 \{y^{(i) = 1}\}} m \\ \mu_0 = \frac {\Sigma_i^m \mathbb 1 \{y^{(i) = 0}\} X{(i)}} {\Sigma_i^m \mathbb 1 \{y^{(i) = 0}\}} \\ \mu_1 = \frac {\Sigma_i^m \mathbb 1 \{y^{(i) = 1}\} X{(i)}} {\Sigma_i^m \mathbb 1 \{y^{(i) = 1}\}} \\ \Sigma = \cdots \\ 预测\underset{y}{\operatorname{argmax}}P(y|X) = \frac {\underset{y}{\operatorname{argmax}}P(X|y)P(y)} {P(X)} = \underset{y}{\operatorname{argmax}}P(X|y)P(y) \\ 这里P(X) = P(X|y=0)P(y=0) + P(X|y=1)P(y=1) \\ 如果P(y)是均匀分布的P(y=0)=P(y=1)，则上述公式就推导得到\underset{y}{\operatorname{argmax}}P(X|y) $$

生成学习算法与判别学习算法的对比

这里有几个结论：

  1. 如果$X|y$服从高斯分布，那么$P(y=1|X)$的后验分布函数将是一个logistics函数。
  2. 如果$P(X|y=1) \sim Poisson(\lambda_1)，P(X|y=0) \sim Poisson(\lambda_0)$，那么$P(y=1|X)$的后验分布函数将是一个logistics函数。
  3. 如果$P(X|y=1)、P(X|y=0)$服从某个相同的指数分布族，那么的后验分布函数将是一个logistics函数。

因此$X|y$服从高斯分布或泊松分布是比$y|X$服从logistics分布更强的假设。

如果$P(X|y)$服从高斯分布的假设假设或大概成立，那么高斯判别算法的表现将会更好，将会优于logistic回归，因为高斯判别算法利用了更多的关于数据的信息。相反如果不确定$P(X|y)$的分布情况，那么logistic回归的表现可能会更好。

高斯判别分析为了拟合出一个还不错的模型，通常需要更少的数据。而logistic回归算法做了更弱的假设，与高斯判别分析相比，为了拟合出模型它需要多的样本。

朴素贝叶斯方法

这里先讲了一个创建特征向量$X$来表示某一封邮件的办法。

假设$X \in \{0, 1\}^n，n=50000$，现在要对$P(X|y)$建模，则$X$有$2^{50000}$个可能，如果使用多项式分布的softmax回归，则需要得到$2^{50000}-1$个参数，这样计算量太大了。

朴素贝叶斯方法，推导过程如下：

假设$X_i$是条件独立的，因此有$P(X_1, X_2, \cdots, X_n|y) = P(X_1|y)P(X_2|y) \cdots P(X_n|y) = \prod_{i=1}^nP(X_i|y)$。

而在伯努利分布里，参数定义如下：

$\phi_{i|y=1} = P(X_i=1|y=1)，\quad \phi_{i|y=0} = P(X_i=1|y=0)，\quad \phi_y=P(y=1)$

因此就可以写出Joint参数似然性:

$\ell(\phi_y, \phi_{i|y=1}, \phi_{i|y=0}) = \prod_{i=1}^mP(X^{(i)}, y^{(i)})$，之后进行极大似然估计，就得到了

$\phi_{j|y=1} = \frac {\sum_{i=1}^m \mathbb 1 \{X_j^{(i)}, y^{(i)}=1\}} {\sum_{i=1}^m \mathbb 1 \{y^{(i)} = 1\}}$

$\phi_{j|y=0} = \frac {\sum_{i=1}^m \mathbb 1 \{X_j^{(i)}, y^{(i)}=0\}} {\sum_{i=1}^m \mathbb 1 \{y^{(i)} = 0\}}$

$\phi_y = \frac {\sum_{i=1}^m\{y^{(i)} = 1\}} {m}$

又因为贝叶斯公式，得到

$P(y=1|X)=\frac {P(X|y=1)P(y=1)} {P(X|y=1)P(y=1) + P(X|y=0)P(y=0)} = \frac {(\prod_{i=1}^nP(X_i|y=1))P(y=1)} {(\prod_{i=1}^nP(X_i|y=1))P(y=1) + (\prod_{i=1}^nP(X_i|y=0))P(y=0)}$

最后将上述的$\phi_{j|y=1}，\phi_{j|y=0}，\phi_y$代入上式，即可得到预测结果。

这里讲朴素贝叶斯讲得比较复杂，如果想比较简单地理解，推荐看看阮一峰的一篇文章-朴素贝叶斯分类器的应用。

Laplace平滑

为了避免一些没有见过的事件，算法认为这些事件不可能发生，于是可以使用Laplace平滑改进此问题。方法如下：

如果$y \in \{1, 2, \cdots, k\}$，那么$P(y=j)=\frac {\sum_{i=1}^m \mathbb 1 \{y^{(i)} = j\} + 1} {m+k}$