生成模型-高斯判别分析GDA- 高斯混合模型GMM- EM算法
在学习生成模型之前，先学习了解下密度估计和高斯混合模型。
生成学习算法(cs229,Ng)
生成算法和判别算法的区别
举个栗子：
我们要区分elephants(y=1)和dogs(y=0)
- 对判别模型（discriminative），以logistic回归为例：
logistic回归模型：$p(y|x;\theta)，h_{\theta}=g(\theta^Tx)$,对应的模型其中g是sigmoid函数。通过logistic回归，我们找到一条决策边界decision boundary，能够区分elephants和dogs.
这个学习的过程就是找到表征这个决策过程的参数 $\theta$.
- 生成模型（generative）：
同样的我们也是要通过给定的特征x来判别其对应的类别y。但我们换个思路，就是先求p(x|y),也就是通过y来分析对应x满足的一个概率模型p(x|y)。然后在反过来看特征x，以二分类为例，p(x|y=0)和p(x|y=1)哪个概率大，那么x就属于哪一类。
然后通过p(x|y)来判断特征x所属的类别，根据贝叶斯公式：
$$p(y=1|x) = \dfrac{p(x|y=1)p(x)}{p(x)}$$
在给定了x的情况下p(x)是个定值，p(y)是先验分布，那么计算方法如下：
$$arg\max_yp(y|x) = arg\max_{y}\dfrac{p(x|y)p(y)}{p(x)}= arg\max_{y}p(x|y)p(y)$$
总结下就是：
- 生成模型：一般是学习一个代表目标的模型，然后通过它去搜索图像区域，然后最小化重构误差。类似于生成模型描述一个目标，然后就是模式匹配了，在图像中找到和这个模型最匹配的区域，就是目标了。
- 判别模型：以分类问题为例，然后找到目标和背景的决策边界。它不管目标是怎么描述的，那只要知道目标和背景的差别在哪，然后你给一个图像，它看它处于边界的那一边，就归为哪一类。
- 由生成模型可以得到判别模型，但由判别模型得不到生成模型。
然鹅，生成模型p(x|y)怎么得到呢？不慌，我们先了解下多维正态分布～
多维正态分布(the multivariate nirmal distribution)
关于一维正态分布怎么推导出多维正态分布的概率密度函数，可参考知乎:多维高斯分布是如何由一维发展而来的？
首先一维正态分布:
$p(x) = \dfrac{1}{\sqrt{2\pi}}exp(\dfrac{-x^2}{2})$
二维标准正态分布，就是两个独立的一维标准正态分布随机变量的联合分布：
$p(x,y) = p(x)p(y)=\dfrac{1}{2\pi}exp(-\dfrac{x^2+y^2}{2})$
把两个随机变量组合成一个随机向量：$v=[x\quad y]^T$
$p(v)=\dfrac{1}{2\pi}exp(-\dfrac{1}{2}v^Tv)\quad$ 显然x,y相互独立的话，就是上面的二维标准正态分布公式～
然后从标准正态分布推广到一般正态分布，通过一个线性变化：$v=A(x-\mu)$
$p(x)=\dfrac{|A|}{2\pi}exp[-\dfrac{1}{2}(x-\mu)^TA^TA(x-\mu)]$
注意前面的系数多了一个|A|（A的行列式）。
可以证明这个分布的均值为$\mu$，协方差为$(A^TA)^{-1}$。记$\Sigma = (A^TA)^{-1}$，那就有
$$p(\mathbf{x}) = \frac{1}{2\pi|\Sigma|^{1/2}} \exp \left[ -\frac{1}{2} (\mathbf{x} - \mu) ^T \Sigma^{-1} (\mathbf{x} - \mu) \right]$$
推广到n维：
$$p(\mathbf{x}) = \frac{1}{(2\pi)^{n/2}|\Sigma|^{1/2}} \exp \left[ -\frac{1}{2} (\mathbf{x} - \mu) ^T \Sigma^{-1} (\mathbf{x} - \mu) \right]$$
需要注意的是：这里的二维、n维到底指的是什么？
以飞机检测的数据点为例，假设它由heat和time决定，那么这就是个二维正态分布，数据点的生成所处的位置由其概率决定，也就是$p(\mathbf{x})$
如果这个数据有n个特征，那么其分布就是n维正态分布。
之前一直理解的是，n维正态分布是两个向量巴拉巴拉。。好像一直没搞懂。。
再顺便了解下协方差矩阵吧～
对多维随机变量$X=[X_1,X_2,…,X_n]^T$，我们往往需要计算各维度之间的协方差，这样协方差就组成了一个n×n的矩阵，称为协方差矩阵。协方差矩阵是一个对角矩阵，对角线上的元素是各维度上随机变量的方差,非对角线元素是维度之间的协方差。 我们定义协方差为$\Sigma$, 矩阵内的元素$\Sigma_{ij}$为:
$$\Sigma_{ij} = cov(X_i,X_j) = E[(X_i - E(X_i)) (X_j - E(X_j))]$$
则协方差矩阵为:
$$
\Sigma = E[(X-E(X)) (X-E(X))^T] = \left[
\begin{array}{cccc}
cov(X_1,X_1) & cov(X_1,X_2) & \cdots & cov(X_1,X_n) \
cov(X_2,X_1) & cov(X_2,X_2) & \cdots &cov(X_2,X_n) \
\vdots & \vdots& \vdots & \vdots \
cov(X_n,X_1) & cov(X_n,X_2,)&\cdots& cov(X_n,X_n)
\end{array}
\right]
$$
如果X~$N(\mu,\Sigma)$,则$Cov(X)=\Sigma$
可以这么理解协方差，对于n维随机变量X，第一维是体重$X_1$，第二维是颜值$X_2$，显然这两个维度是有一定联系的，就用$cov(X_1,X_2)$来表征，这个值越小，代表他们越相似。协方差怎么求，假设有m个样本，那么所有的样本的第一维就构成$X_1$…不要把$X_1$和样本搞混淆了。
了解了多维正态分布和协方差，我们再回到生成模型p(x|y)。。其实我们就是假设对于n维特征，p(x|y)是n维正态分布～怎么理解呢，下面就说！
高斯判别分析模型The Gaussian Discriminant Analysis model
高斯判别模型就是：假设p(x|y)是一个多维正态分布，为什么可以这么假设呢？因为对于给定y的条件下对应的特征x都是用来描述这一类y的，比如特征是n维的，第一维描述身高，一般都是满足正态分布的吧，第二维描述体重，也可认为是正态分布吧～
则生成模型：
y ~ Bernoulli($\phi)$ 伯努利分布，又称两点分布，0-1分布
x|y=0 ~ $N(u_0,\Sigma)$
x|y=1 ~ $N(u_1,\Sigma)$
- 这里可以看作是一个二分类，y=0和y=1,可以看作是伯努利分布，则$p(y)=\phi^y(1-\phi)^{1-y}$，要学的参数之一: $\phi=p(y=1)$，试想如果是多分类呢，那么要学习的参数就有$\phi_1,\phi_2,….\phi_k$
- 其中类别对应的特征x|y=0,x|y=1服从正态分布。怎么理解呢？就是既然你们都是一类人，那么你们的身高啊，体重啊等等应该满足正态分布。。有几维特征就满足几维正态分布
- 这里x是n维特征，身高，体重，颜值…balabala，所以x|y=0满足n维正态分布～x|y=1也是啦，只不过对于不同的类，对应n维特征的均值不一样，奇怪为什么协方差矩阵是一样的？？这里是将它特殊化了，后面会讲的一般性的em算法就不是这样的了
- 每个分类对应的n维特征的分布显然不是独立的，比如体重和颜值还是有关系的吧～他们的协方差，方差就统统都在$\Sigma$协方差矩阵里面了
$$p(x|y=0) = \frac{1}{(2\pi)^{n/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)^{n/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$，对于训练数据，就是观测到的数据x,y，既然他们出现了，那么他们的联合概率，也就是似然函数$\prod_{i=1}^mp(x,y)$就要最大～其对数似然log-likelihood：
$$\begin{equation}\begin{aligned}
L(\phi,\Sigma, \mu_0,\mu_1) &= log\prod_{i=1}^mp(x^{(i)},y^{(i)};\phi,\Sigma, \mu_0,\mu_1$) \
&= log\prod_{i=1}^mp(x^{(i)}|y^{(i)};\phi,\Sigma, \mu_0,\mu_1$) p(y^{(i)};\phi)\
\end{aligned}\end{equation}\label{eq2}$$
其中$p(y^{(i)};\phi)$是已知的，也就是先验概率(class priors)，$p(x^{(i)}|y^{(i)})$就是上面推导的～代入后，分别对参数求导即可：
在回过头来看这些公式，
然后通过p(x|y=0),p(x|y=1)即可对需要预测的x求出对应的概率，然后做出判别了。这样看来，如果直接对x|y=1,和x|y=0做出了正态分布的猜测，就可以直接写出来了。只不过，我们用极大似然估计重新推导了一遍。
高斯混合模型GMM
GMM
前面GDA是有标签的，也算是有监督学习。而在没有标签的情况下呢，就是无监督学习了，虽然我们无法给出x所属的类叫啥，但是我们可以判断出哪些x是同一类，以及样本中总共有多少类（虽然这个类数嘛。。类似于k-means的类数，可根据交叉验证选择）。
其实和GDA非常相似，不过这里没有了类标签，只有一堆样本特征，${x^{(1)},x^{(2)},…,x^{(m)}}$,
我们不知道这些样本属于几个类别，也不知道有哪些类了。但虽然不知道，我们确定他们是存在的，只是看不见而已。我们可以假设存在k类，${z^{(1)},z^{(2)},…,z^{(k)}}$,看不见的，我们就叫它们隐藏随机变量(latent random variable)，
这样一来，就训练样本就可以用这样的联合分概率模型表示了，$p(x^{(i)},z^{(i)})=p(x^{(i)}|z^{(i)})p(z^{(i)})$
- 同GDA不一样的是，这里是多分类，可假定$z^{(i)}\sim Multinomial(\phi)$，多项式分布（二项分布的拓展～），那么$p(z^{(i)})=\phi_j$
- 同GDA相同的是，对于每一个类别，其对应的样本满足n维正态分布，也就是：$x^{(i)}|z^{(i)}=j\sim N(\mu_j,\Sigma_j)$,但注意哦，这里每个高斯分布使用了不同的协方差矩阵$\Sigma_j$
$$p(x|z^{(1)}) = \frac{1}{(2\pi)^{n/2}|\Sigma_0|^{1/2}} \exp \left[ -\frac{1}{2} (x - \mu_0) ^T \Sigma_0^{-1} (x - \mu_0) \right]$$
$$p(x|z^{(2)}) = \frac{1}{(2\pi)^{n/2}|\Sigma_1|^{1/2}} \exp \left[ -\frac{1}{2} (x - \mu_1) ^T \Sigma_1^{-1} (x - \mu_1) \right]$$
$$….$$
$$p(x|z^{(k)}) = \frac{1}{(2\pi)^{n/2}|\Sigma_k|^{1/2}} \exp \left[ -\frac{1}{2} (x - \mu_k) ^T \Sigma_k^{-1} (x - \mu_k) \right]$$
然后带入到训练样本的对数似然（log-likelihood）:
$$L(\phi,\mu,\Sigma)=\sum_{i=1}^{m}logp(x^{(i)};\phi,\mu,\Sigma)$$
$$L(\phi,\mu,\Sigma)=\sum_{i=1}^{m}log\sum_{z^{(i)}=1}^{k}p(x^{(i)}|z^{(i)};\mu,\Sigma) p(z^{(i)};\phi)\$$
这里需要注意下标：对于类别有k类，第一个求和符号是对第i个样本在k个类别上的联合概率，第二个求和符号是m个样本的联合概率。
我们可以注意到，如果我们知道$z^{(i)}$,那么这个似然函数求极大值就很容易了，类似于高斯判别分析，这里的$z^{(i)}$相当于标签，分别对参数求导可得：
其中的参数:
- $1{z^{(i)}=j}$表示第i个样本为j类时，这个值就为１，那么$\phi_j=\frac{1}{m}\sum_{i=1}^m1{z^{(i)}=j}$表示样本中类别为j的概率
- 其中$p(z^{(i)};\phi)$是根据伯努利分布得到的，在GDA中$p(y|\phi)$是已知的频率概率。
So $z^{(i)}$ 到底有多少个分类？每个类别的概率是多少？譬如上式中 $\sum_{i=1}^{m}1{z^{(i)}=j}$ 这个没法求对吧～它是隐藏变量！所以还是按照这个方法是求不出来的～
这个时候EM算法就登场了～～～
用EM算法求解GMM模型
上面也提到了，如果$z^({i})$是已知的话，那么$\phi_j=\frac{1}{m}\sum_{i=1}^m1{z^{(i)}=j}$表示类别j的概率$p(z^{(i)}=j)$也就已知了，但是呢？我们不知道。。所以我们要猜测$p(z^{(i)}=j)$这个值，也就是EM算法的第一步：
Repeat until convergence 迭代直到收敛:{
(E-step):for each i,j,set:
$w_j^{(i)}:=p(z^{(i)}=j|x^{(i)};\phi,\mu,\Sigma)$
$w_j^{(i)}$什么意思呢?就是对于i样本,它是j类的后验概率。在GDA里面，x_i的类别是确定的，在GMM里面呢？不知道它的类别，所以只能假设k类都有可能，它是j类别的概率就是$w_j^{(i)}$，它仅仅取决于$\phi_j$,而在GMM里面，它取决于$\phi_j,\mu_j,\Sigma_j$，实际上$w_j^{(i)}$的值，就包含了两个我们在GMM所做的假设，多项式分布和正态分布。
The values $w_j$ calculated in the E-step represent our “soft” guesses for
the values of $z^{(i)}$ .
The term “soft” refers to our guesses being probabilities and taking values in [0, 1]; in
contrast, a “hard” guess is one that represents a single best guess (such as taking values
in {0, 1} or {1, . . . , k}).
硬猜测是k均值聚类，GMM是软猜测。
这样一来，参数更新就可以这样写了，也就是EM算法的第二步：
(M-step) Updata the parameters:
然后对似然函数求导，后面会详细介绍
$$\phi_j:=\frac{1}{m}\sum_{i=1}^mw_j^{(i)}$$
$$\mu_j:=\dfrac{\sum_{i=1}^mw_j^{(i)}x^{(i)}}{\sum_{i=1}^mw_j^{(i)}}$$
$$\Sigma_j:=\dfrac{\sum_{i=1}^mw_j^{(i)}(x^{(i)}-\mu_j)(x^{(i)}-\mu_j)^T}{\sum_{i=1}^mw_j^{(i)}}$$
｝
训练过程的理解可参考blog
$w_j^{(i)}表示第i个样本为ｊ类别的概率，而\phi_j$表示m个样本中j类别的概率，$\mu_j,\Sigma_j$分别表示j类别对应的n维高斯分布的期望和协方差矩阵
所以，求出$w_j^{(i)}$，一切就都解决了吧？对于后验概率$p(z^{(i)}=j|x^{(i)})$可以根据Bayes公式：
$$p(z^{(i)}=j|x^{(i)};\phi,\mu,\Sigma)=\dfrac{p(x^{(i)}|z^{(i)}=j;\mu,\Sigma)p(z^{(i)}=j;\phi)}{\sum_{l=1}^kp(x^{(i)}|z^{(i)}=l;\mu,\Sigma)p(z^{(i)}=l;\phi)}$$
- 其中先验概率$p(x^{(i)}|z^{(i)}=j;\mu,\Sigma)$可以根据高斯分布的密度函数来求，$z^{(i)}=j\sim N(\mu_j,\Sigma_j)$
- 类先验(class priors)$p(z^{(i)}=j;\phi)$可以取决于多项式分布中j类的概率$\phi_j$
The EM-algorithm is also reminiscent of the K-means clustering algorithm, except that instead of the “hard” cluster assignments $c^(i)$, we instead have the “soft” assignments $w_j$ . Similar to K-means, it is also susceptible to local optima, so reinitializing at several different initial parameters may be a good idea.
EM算法使我们联想起了k-means,区别在于k-means的聚类是通过欧氏距离c(i)来定义的，而EM是通过$w_j$probabilities来分类的。同k-means一样，这里的EM算法也是局部优化，因此最好采用不同的方式初始化～
convergence?
我们知道k-means一定是收敛的，虽然结果不一定是全局最优解，但它总能达到一个最优解。但是EM算法呢，也是收敛的。
The EM algorithm
前面我们讲的是基于高斯混合模型的EM算法，但一定所有的类别都是高斯分布吗？还有卡方分布，泊松分布等等呢，接下来我们就将讨论EM算法的一般性。
在学习一般性的EM算法前，先了解下Jensen’s inequality
Jensen’s inequality
如果函数$f$，其二阶导恒大与等于0 $(f^{‘’}\ge 0)$，则它是凸函数f(convec function)。
如果凸函数的输入是向量vector-valued inputs，那么它的海森矩阵(hessian)H是半正定的。Jensen’s 不等式：
Let f be a convex function, and let X be a random variable.
Then:
$$E[f (X)] ≥ f (EX).$$
Moreover, if f is strictly convex, then $E[f (X)] = f (EX)$ holds true if and
only if $X = E[X]$ with probability 1 (i.e., if X is a constant).
举个栗子来解释jensen不等式：
假设输入随机变量X是一维的哈，然后Ｘ取a,b的概率都是0.5,那么
$$EX=(a+b)/2,f(EX)=f(\dfrac{a+b}{2})$$,$$E[f(X)]=\dfrac{f(a)+f(b)}{2}$$
因为是凸函数，所以 $f(EX)\le E[f(X)]$
同理，如果是凹函数(concave function),那么不等式方向相反$f(EX)\ge E[f(X)]$。后面EM算法里面就要用到log(X)，log(x)就是个典型的凹函数～
The EM algorithm
首先，问题是：我们要基于给定的m个训练样本${x^{(1)},x^{(2)},…,x^{(m)}}$来进行密度估计～
像前面一样，创建一个参数模型p(x,z)来最大化训练样本的对数似然：
$$L(\theta)=\sum_{i=1}^mlogp(x;\theta)$$
$$L(\theta)=\sum_{i=1}^mlog\sum_zp(x,z;\theta)$$
一般性就是把前面特殊化的假设去掉，没有了正态分布和多项式分布。
可以看到，$z^{(i)}$是隐藏的随机变量(latent random variable),关于参数$\theta$的最大似然估计就很难计算了。
解释下公式中的推导：
- 这里是针对样本i来说，对于样本i，它可能是$z^1,z^2,…,z^k$都有可能，但他们的probability之和为１，也就是
$\sum_zQ_i(z)=1$
$\dfrac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}$
看做随机变量Ｘ,那么（２）式中的后半部分 $log\sum_{z^{(i)})}[\dfrac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}]$就是log(EX)了，$logx$是一个凹函数，则其大于$E[log(x)]$
EM迭代过程(重点):
（1）根据上式可以看做$L(\theta)\ge J(Q,\theta)$.两边都是关于$\theta$的函数，那么将$\theta$固定，调整Q在一定条件下能使等式成立。
（2）然后固定Q,调整$\theta^t$到$\theta^{t+1}$找到下界函数的最大值$J(Q,\theta^{t+1})$.显然在当前Q的条件下，$L(\theta^{t+1})\ne J(Q,\theta^{t+1})$,那么根据Jensen不等式，$L(\theta_{t+1})>J(Q,\theta^{t+1})=L(\theta^{t})$,也就是说找到了使得对数似然L更大的$\theta$.这不就是我们的目的吗？！
然后迭代循环(1)(2)步骤，直到在调整$\theta$时，下界函数$J(Q,\theta)$不在增加，即小于某个阈值。
看下Ng画的图：
任意初始化$\theta$和Q,然后找下界函数和$l(\theta)$交接的点，这就是EM算法的第一步：
我们要让不等式相等,即Jensen’s inequality中的随机变量取值是一个常量，看(2)式：
$$\dfrac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}=c$$
对左边分子分母同时对z求类和：
$$\dfrac{\sum_zp(x^{(i)},z^{(i)};\theta)}{\sum_zQ_i(z^{(i)})}=c$$
根据$\sum_zQ_i(z)=1$：
$$\sum_zp(x^{(i)},z^{(i)};\theta)=c$$
带回去可得：
$$Q_i(z^{(i)})=\dfrac{p(x^{(i)},z^{(i)};\theta)}{\sum_zp(x^{(i)},z^{(i)};\theta)}$$
$$Q_i(z^{(i)})=\dfrac{p(x^{(i)},z^{(i)};\theta)}{p(x^{(i)};\theta)}$$
$$Q_i(z^{(i)})=p(z^{(i)}|x^{(i)};\theta)$$
EM总结下来：
Repeat until convergence {
(E-step)
For each i,找到下界函数, set:
$$Q_i(z^{(i)}):=p(z^{(i)}|x^{(i)};\theta)$$
(M-step)找到下界凹函数的最大值,也就是(3)式 Set:
$$\theta:=arg\max_{\theta}\sum_i^m\sum_{z^{(i)}}^kQ_i(z^{(i)})log\dfrac{p(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}$$
}
要理解的是：
EM算法只是一种计算方式，对于上式中的$Q_i(z^{(i)})=p(z^{(i)}|x^{(i)};\theta)$我们还是要根据假设来求得，比如GMM中的多类高斯分布。然后带回到对数似然中，通过求导得到参数估计。我们费尽心机证明EM算法收敛，只是为了去证明这样去求似然函数的极大值是可行的，然后应用到类似于GMM，HMM中。
training and will converge?
首先说是否收敛，答案是肯定收敛的。。懒得输公式了。。直接贴图吧，这个比较好理解：
上面写这么多，其实就是证明$L(\theta_{t+1})>L(\theta_t)$.
Mixture of Gaussians revisited
我们知道了em算法是一种计算方式，用来解决含有隐变量似然对数很难求的问题，那么我们把它运用到GMM中。
E step:
$w_j^{(i)}:=p(z^{(i)}=j|x^{(i)};\phi,\mu,\Sigma)$
$$w_j^{(i)}:=p(z^{(i)}=j|x^{(i)};\phi,\mu,\Sigma)=\dfrac{p(x^{(i)}|z^{(i)}=j;\mu,\Sigma)p(z^{(i)}=j;\phi)}{\sum_{l=1}^kp(x^{(i)}|z^{(i)}=l;\mu,\Sigma)p(z^{(i)}=l;\phi)}$$
其中先验概率$p(x^{(i)}|z^{(i)}=j;\mu,\Sigma)$可以根据高斯分布的密度函数来求，$z^{(i)}=j\sim N(\mu_j,\Sigma_j)$
类先验(class priors)$p(z^{(i)}=j;\phi)$可以取决于多项式分布中j类的概率$\phi_j$
这样我们就完成了对$w_j^{(i)}$的soft ‘guess’，也就是E step.
M step:
然后对参数求导：
详细推导过程，参考cs229-notes8
我们在整体回顾一下整个过程，所谓的E step就是找到$Q_i(z^{j}),w_i^j$（在一定假设下是可以通过bayes公式求得的），使得下界函数与log函数相等，也就是Jensen取等号时。然后是M step就是在Q的条件下找到下界函数最大值，也就是对参数求导，导数为0的地方。
然后在根据求得的参数，再求Q，再带入求导。。。迭代直到收敛。
