CS229: 4

生成学习算法, Generative Learing Algorithm

生成学习算法（Generative Learing Algorithm）

之前的学习方法都是在已知$x$的情况下求不同$y$的概率，也就是直接学习$P(y|x)$，被称为判别学习算法（Discrimative Learning Algorithm）。

这一章反过来考虑数据的生成过程，即$P(x|y)$。

贝叶斯告诉我们，这二者实际上是有联系的

$$P(y|x)P(x)=P(x|y)P(y)=P(x,y)$$

现在还是已知$x$，求$y$，反过来即

$$\argmax_y P(x|y)=\argmax_y \frac{P(y|x)P(x)}{P(y)}=\argmax_y \frac{P(y|x)}{P(y)}$$

$\argmax_y$即求这个式子达到最大时对应的$y$

怎么理解这里的$y|x$和$y$的区别，即有没有先验呢？

$y|x$意思是看完了$x$的所有“细节”再来求$y$的概率，$y$只没有看$x$的具体细节求概率，比如伯努利分布，直接用频率来估计$P(y)$，当然后面也一般都是用频率来直接估计某些概率。

多元正态分布

如果$x$不只是一个实数，而是一个向量$\R^d$，下面来拓展正态分布

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

这里$\mu \in \R^d$，表示$x$的均值，即每个维度的元素就是该维度上$x$的均值。$\Sigma\in \R^{d\times d}$是一个新概念，协方差矩阵，$\Sigma_{i,j}$表示$x$第$i,j$个元素的协方差

$$cov(X,Y)=E((X-\mu_X)(Y-\mu_Y))=E(XY)-\mu_X\mu_Y=E(XY)-E(X)E(Y)\\ \rho_{X,Y}=\frac{cov(X,Y)}{\sigma_X\sigma_Y}$$

$\rho$是相关系数，表示两个变量之间的线性相关关系。

所以协方差矩阵实际上就是方差的拓展，$i=j,\Sigma_{i,j}$就是方差，$i\neq j,\Sigma_{i,j}$就是协方差，即衡量两个维度的线性相关关系。

需要注意的是，$cov(X,Y)=0$虽然表示完全没有线性关系，但是不一定相互独立；相互独立一定协方差为$0$。

比如$Y=X^2,x\sim N(0,1),cov(X,Y)=E(X^3)=0$。

协方差矩阵形式化的定义是

$cov(Z)=E((Z-\mu)(Z-\mu)^T)=E(ZZ^T)+\mu\mu^T-E(Z\mu^T+\mu Z^T)=E(ZZ^T)-\mu\mu^T$

最后一个等号，可以直接考虑$Z\mu^T,\mu Z^T$矩阵乘法的具体结果得到。

二维情况的直观理解直接看讲义。

高斯判别分析(GDAM)

一个每个维度都连续的向量$x$，进行二分类$0,1$。

用我们之前提到的生成学习算法的思想来处理。

先做如下分布假设

$$y\sim Bernouli(\phi),P(y)=\phi^y(1-\phi)^{1-y}\\ x|y=0\sim N(\mu_0,\Sigma),P(x;\mu_0,\Sigma)=\frac{1}{(2\pi)^{\frac{d}{2}}|\Sigma|^{\frac{1}{2}}}\exp(-\frac{1}{2}(x-\mu_0)^T\Sigma^{-1}(x-\mu_0)) \\ x|y=1\sim N(\mu_1,\Sigma),P(x;\mu_1,\Sigma)=\frac{1}{(2\pi)^{\frac{d}{2}}|\Sigma|^{\frac{1}{2}}}\exp(-\frac{1}{2}(x-\mu_1)^T\Sigma^{-1}(x-\mu_1))\\$$

还是做极大似然估计来确定参数

$$L(\theta)=\prod_{i=1}^{n}P(y^{(i)},x^{(i)})\\ l(\theta)=\sum_{i=1}^{n}\ln P(x^{(i)}|y^{(i)})P(y^{(i)})\\ l(\theta)=\sum_{i=1}^{n}\ln P(x^{(i)}|y^{(i)})+\sum_{i=1}^{n}\ln P(y^{(i)})\\$$

为什么前面的线性回归的似然函数是$P(y|x)$，这里就是$P(y,x)$呢？

因为我们要考虑事件的生成，要考虑一个过程而非只是结果。

更唯象一点地说，要不然求不出来$\phi$

然后代入，再分别对$\phi$求导，对$\mu_0,\mu_1$求偏导，对$\Sigma$进行矩阵求导，可以得到

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

实际上，GDA和逻辑回归也是可以关联到一起的，即GDA可以写成

$$P(y=1|x;\mu_0,\mu_1,\Sigma,\phi)=\frac{1}{1+e^{-\theta^Tx-\theta_0}}\\ P(y=1|x)P(x)=P(x|y=1)P(y=1)\\ P(y=1|x)=\frac{P(x|y=1)P(y=1)}{P(x|y=0)P(y=0)+P(x|y=1)P(y=1)}\\ P(y=1|x)=\frac{1}{1+\frac{P(x|y=0)P(y=0)}{P(x|y=1)P(y=1)}}\\$$

然后最终结果是

$$\theta=\Sigma^{-1}(\mu_1-\mu_0)\\ \theta_0=\ln(\frac{\phi}{1-\phi})+\frac{1}{2}\mu_0^T\Sigma^{-1}\mu_0-\frac{1}{2}\mu_1^T\Sigma^{-1}\mu_1$$

但是可以看到，GDA对分布的假设是更强的——逻辑回归只需要假设伯努利分布。优势是在足够符合多元正态分布的情况，GDA是最渐进有效的，在所有模型中效果是最好的；劣势是如果没那么符合预定的分布，那情况就很糟了。

但是，还是有一些技巧，能把分布改造成类似正态分布的分布，比如box-cox

朴素贝叶斯

之前的GDA是考虑不同的分类下，相应的$x$的分布，但是假设太强了。还是要解决向量的二分类问题，下面考虑怎么放松这个假设。GDA考虑$x$的生成的思想不变，只考虑放松$x$的分布。

回到一元的正态分布，充分统计量是均值和方差，我们想，能不能延续这个思想，多元的情况下还是分别考虑每个变量的均值和方差？

也就是说，每一维的“地位”是相同的，也就是说，每一维之间没有约束。

那就能得出很简洁的分布的假设了：$x$每一维相互独立，或者总的来说，$x|y=1/0$每一维条件独立。这个被称为朴素贝叶斯假设(Naive Bayes Assumption)。

$$P(x_1,x_2,...,x_d|y)=P(x_1|y)P(x_2|y)...P(x_d|y)$$

如果$x$连续，那每一维都单独符合一个正态分布；如果$x$离散，那每一维就单独符合一个伯努利分布。下面我们考虑每一维都是$0/1$。

换句话说，近似于$\Sigma$变成了对角矩阵。

通常来讲，这个假设还是太强了，但是实际应用中效果通常不错。

比如垃圾邮件分类问题，每一维表示编码一个单词，$0/1$表示单词是否出现。通常单词不可能是完全没有联系的。

感性理解，朴素贝叶斯没有太强的假设，所以不会过拟合；很多时候并不是不同维之间的依赖关系决定了分类的结果，比如出现了“免费”之类的字眼就可以断定是垃圾邮件，决定因素并不是维度之间的依赖关系。

参数就是

$$\phi_y=P(y=1),\phi_{j|y=0}=P(x_j=1|y=0),\phi_{j|y=1}=P(x_j=1|y=1)$$

$$L(\theta)=\prod_{i=1}^{n}P(x^{(i)},y^{(i)})\\ l(\theta)=\sum_{i=1}^{n}\ln(P(x^{(i)}|y^{(i)})P(y^{(i)}))\\$$

推推推，得到

$$\phi_y=\frac{\sum_{i=1}^{n}[y^{(i)}=1]}{n}\\ \phi_{j|y=0}=\frac{\sum_{i=1}^{n}[x^{(i)}_j=1,y^{(i)}=0]}{\sum_{i=1}^{n}[y^{(i)}=0]}\\ \phi_{j|y=1}=\frac{\sum_{i=1}^{n}[x^{(i)}_j=1,y^{(i)}=1]}{\sum_{i=1}^{n}[y^{(i)}=1]}\\ 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)}\\ P(y=1|x)=\frac{P(y=1)\prod_{j=1}^{n}P(x_j|y=1)}{P(y=1)\prod_{j=1}^{n}P(x_j|y=1)+P(y=0)\prod_{j=1}^{n}P(x_j|y=0)}\\$$

然后就可以预测了。

对于回归问题，看起来朴素贝叶斯很难处理？

可以把值域离散成一段一段变成分类问题来做。

拉普拉斯平滑

回到垃圾短信分类问题，如果新短信中出现了训练集没有的词

$$\phi_{k|y=1}=\phi_{k|y=0}=0$$

在计算时分子分母就都是0。

如果相应处理这种情况，但仍保持概率和为$1$，就要从一些比较大的概率里面拿一部分分给零概率的。

所谓的拉普拉斯平滑就是这样的方法，假设现在要直接用频率估计概率，$z=1,2,...,k,\phi_j=P(z=j)$

$$\phi_j=\frac{\sum_{i=1}^{n}[z^{(i)}=j]}{n}\\ \phi_j'=\frac{1+\sum_{i=1}^{n}[z^{(i)}=j]}{n+k}$$

可以发现仍能保持概率和为1。

回到垃圾短信分类问题

$$\phi_{j|y=t}=\frac{1+\sum_{i=1}^{n}[x^{(i)}_j=1,y^{(i)}=t]}{2+\sum_{i=1}^{n}[y^{(i)}=t]}$$

只做了很小的改动，所以可以认为对整体没什么影响。

文本分类的事件模型

从另一个角度来看，朴素贝叶斯背后的动力学过程相当于先决定邮件是不是垃圾邮件，然后再决定每个词是否出现。被称作伯努利事件模型。

只考虑出现与否有一点粗糙，加强为考虑出现的顺序。这里的独立性改成，每个单词出现在任意位置的概率都相同，不受出现位置和其他位置的单词的影响。

需要的参数是

$$\phi_{k|y=0},\phi_{k|y=1},\phi_y\\$$

$\phi_{k|y}$表示任意位置上出现单词$k$的概率。

$$L=\prod_{i=1}^{n}P(x^{(i)},y^{(i)})=\prod_{i=1}^{n}P(y^{(i)})\prod_{j=1}^{d_i}P(x^{(i)}_j|y^{(i)})$$

极大似然估计出

$$\phi_{k|y=0}=\frac{\sum_{i=1}^{n}\sum_{j=1}^{d_i}[x^{(i)}_j=k,y^{(i)}=0]}{\sum_{i=1}^{n}[y^{(i)}=0]d_i}\\ \phi_{k|y=1}=\frac{\sum_{i=1}^{n}\sum_{j=1}^{d_i}[x^{(i)}_j=k,y^{(i)}=1]}{\sum_{i=1}^{n}[y^{(i)}=1]d_i}\\ \phi_y=\frac{\sum_{i=1}^{n}[y^{(i)}=1]}{n}$$

使用拉普拉斯平滑

$$\phi_{k|y=0}'=\frac{1+\sum_{i=1}^{n}\sum_{j=1}^{d_i}[x^{(i)}_j=k,y^{(i)}=0]}{|V|+\sum_{i=1}^{n}[y^{(i)}=0]d_i}\\ \phi_{k|y=1}'=\frac{1+\sum_{i=1}^{n}\sum_{j=1}^{d_i}[x^{(i)}_j=k,y^{(i)}=1]}{|V|+\sum_{i=1}^{n}[y^{(i)}=1]d_i}\\$$

其中$|V|$是单词总数。