CS229 Lecture 13

---

课程要点：

Mixture of Gaussians
Native of Bayes
Factor Analysis
Gaussians Distribution

---

回顾

给定无标记样本$\{x^{(1)},x^{(2)}......x^{(m)}\}${x(1),x(2)......x(m)},希望对这些数据的概率密度进行建模$P(x)$P(x)。这里的数据可能来自多个 不同的高斯分布。$P(x)=\sum_{z} P(x|z)P(z)$P(x)=∑z​P(x∣z)P(z),其中$z$z表明来自那个分布。这里假设$z\sim Multinomial(\phi)$z∼Multinomial(ϕ)且$P(x|z_j)\sim N(u_j,\Sigma_j)$P(x∣zj​)∼N(uj​,Σj​)。似然函数为：

$\max_{\theta}\,\sum_{i=1}^{m}logP(x^{(i)};\theta)\geq\max_{\theta}\,\sum_{i=1}^{m}log\sum_{z_j}P(x^{(i)},z_{j};\theta)$θmax​i=1∑m​logP(x(i);θ)≥θmax​i=1∑m​logzj​∑​P(x(i),zj​;θ)

通过EM算法找到最优参数

E-step

$Q_i(z^{(i)})=P(z^{(i)}|x^{(i)};\theta)$Qi​(z(i))=P(z(i)∣x(i);θ)

M-step

$\theta=\arg\max_{\theta}\sum_{i}\sum_{z^{(i)}}Q_{i}(z^{(i)}log\frac{P(x^{(i)},z^{(i)};\theta)}{Q_{i}(z^{(i)})})$θ=argθmax​i∑​z(i)∑​Qi​(z(i)logQi​(z(i))P(x(i),z(i);θ)​)

直接对似然函数或者其tight下界求导的话，是十分困难的，而$x,z$x,z的联合分布其符合前面学习过的指数族，E-step和M-Step都是比较容易计算的。

EM算法步骤E实际上相当于确定了一个tight bound $l(\theta)$l(θ)的下界函数，然后M步骤做的就是求这个函数的最大，每次跳到图上红色标示处，努力的贴近$l(\theta)$l(θ)。

---

另一种理解EM算法的方法
定义一个优化目标$J(\theta,Q)=\sum_{i}\sum_{z^{(i)}}Q_{i}(z^{(i)}log\frac{P(x^{(i)},z^{(i)};\theta)}{Q_{i}(z^{(i)})})$J(θ,Q)=∑i​∑z(i)​Qi​(z(i)logQi​(z(i))P(x(i),z(i);θ)​)，满足$l(\theta)\geq J(\theta,Q)$l(θ)≥J(θ,Q),这里的大于等于是来自于Jensen’s 不等式。

根据前面学过的坐标上升可以知道：

E step: maximum with $Q$Q
M setp: maximum with $\theta$θ

---

EM算法应用到高斯混合模型

将EM算法的一般形式应用到高斯混合模型中

E step:

$w_j^{(i)}=Q_i(z^{(i)}=j)=P(z^{(i)}=j|x^{(i)};\theta,u,|\Sigma)= \frac{P(x^{(i)}|z^{(i)}=j)P(z^{(i)}=j)}{\sum P(x^{(i)}|z^{(i)}=j)P(z^{(i)}=j)}$wj(i)​=Qi​(z(i)=j)=P(z(i)=j∣x(i);θ,u,∣Σ)=∑P(x(i)∣z(i)=j)P(z(i)=j)P(x(i)∣z(i)=j)P(z(i)=j)​

上式中$x^{(i)}|z^{(i)}=j\sim N(u_j,|\Sigma_j)$x(i)∣z(i)=j∼N(uj​,∣Σj​),而$P(z^{(i)}=j)\sim Multinomial(\phi)$P(z(i)=j)∼Multinomial(ϕ).

M step:

$\max\sum_{i=1}^{m}\sum_{z^{(i)}}Q_i(z^{(i)}=j)log\frac{P(x^{(i)},z^{(i)};\phi,u,\Sigma)}{Q_i(z^{(i)}=j)}\\ =\sum_{i=1}^{m}\sum_{j=1}^{k}Q_i(z^{(i)}=j)log\frac{P(x^{(i)}|z^{(i)};u,\Sigma)P(z^{(i)}=j;\phi)}{Q_i(z^{(i)}=j)}\\ =\sum_{i=1}^{m}\sum_{j=1}^{k}w_j^{(i)}log\frac{\frac{1}{2\pi^{2/n}|\Sigma|^{1/2}}exp(-\frac{1}{2}(x^{(i)}-u^{(i)})^T\Sigma_j^{-1}(x^{(i)}-u^{(i)}))\phi_j}{w_j^{(i)}}$maxi=1∑m​z(i)∑​Qi​(z(i)=j)logQi​(z(i)=j)P(x(i),z(i);ϕ,u,Σ)​=i=1∑m​j=1∑k​Qi​(z(i)=j)logQi​(z(i)=j)P(x(i)∣z(i);u,Σ)P(z(i)=j;ϕ)​=i=1∑m​j=1∑k​wj(i)​logwj(i)​2π2/n∣Σ∣1/21​exp(−21​(x(i)−u(i))TΣj−1​(x(i)−u(i)))ϕj​​

对上式进行求导

$u_j=\frac{\sum_{i=1}^{m}w_j^{(i)}x^{(i)}}{\sum_{i=1}^{m}w_j^{(i)}}$uj​=∑i=1m​wj(i)​∑i=1m​wj(i)​x(i)​

$\phi_j=\frac{1}{m}\sum_{i=1}^{m}w_j^{(i)}$ϕj​=m1​∑i=1m​wj(i)​

在求导$\phi$ϕ时需要注意$\phi_j\geq0$ϕj​≥0并且$\sum_{j=1}^{k}\phi_j=1$∑j=1k​ϕj​=1,这些约束可以通过拉格朗日乘子进行求解。

---

文本聚类

给定一堆文本，希望可以把这些文本根据主题进行聚类。

给定训练集$\{x^{(1)},x^{(2)}......x^{(m)}\}${x(1),x(2)......x(m)},其中$x^{(i)}\in \{0,1\}^{n}$x(i)∈{0,1}n且$x_j^{(i)}$xj(i)​表示词$j$j是否出现于文本$i$i中。

这里$z^{(i)}\in\{0,1\}$z(i)∈{0,1} 因此$z^{(i)}\sim Beroli(\phi)$z(i)∼Beroli(ϕ).

$P(x^{(i)}|z^{(i)})=\prod_{i=1}^{m}P(x_j^{i}|z^{(i)})$P(x(i)∣z(i))=i=1∏m​P(xji​∣z(i))

$P(x_j^{(i)}=1|z^(i)=j)=\phi_{j|z}$P(xj(i)​=1∣z(i)=j)=ϕj∣z​

可以看到如果将上面的$z$z替换为$y$y,那么上面公式将会和朴素贝叶斯公式一样。

E step:

$w^{i}=P(z^{(i)}=1|x^{(i)};\phi_{i=z})$wi=P(z(i)=1∣x(i);ϕi=z​)

M step:

$\phi_{j|z=1}=\frac{\sum_{i=1}^{m}w^{(i)}1\{x_j^{(i)}=1\}}{\sum_{i=1}^{m}w^{(i)}}$ϕj∣z=1​=∑i=1m​w(i)∑i=1m​w(i)1{xj(i)​=1}​

$\phi_{j|z=0}=\frac{\sum_{i=1}^{m}(1-w^{(i)})1\{x_j^{(i)}=1\}}{\sum_{i=1}^{m}(1-w^{(i)})}$ϕj∣z=0​=∑i=1m​(1−w(i))∑i=1m​(1−w(i))1{xj(i)​=1}​

$\phi_{j|z}=\frac{\sum w^{(i)}}{m}$ϕj∣z​=m∑w(i)​

---

因子分析

因子分析相较于高斯混合模型其EM算法中对应的隐变量$z$z可能是连续的。

一般来说如果$m\geq n$m≥n用混合高斯来建模是可取的，但是如果说$n \approx m$n≈m或者$n\geq m$n≥m,那么又该如何模拟数据的分布$P(x)$P(x)?

当然可以选择单纯的高斯模型来建模。

有训练样本$\{x^{(1)},x^{(2)}.....x^{(m)}\}${x(1),x(2).....x(m)}，对其进行建模。假设$x\sim N(u,\Sigma)$x∼N(u,Σ),通过极大似然估计可以得出：

$u=\frac{1}{m}\sum_{i=1}^{m}x^{(i)}$u=m1​∑i=1m​x(i)

$\Sigma = \frac{1}{m}\sum_{i=1}^{m}(x^{(i)-u})(x^{(i)}-u)^T$Σ=m1​∑i=1m​(x(i)−u)(x(i)−u)T

由于$n\geq m$n≥m因此$\Sigma$Σ必然为奇异矩阵，即不满秩。其对应的高斯轮廓曲线是一个无限延伸的椭圆。

可以加上一些假设如$\Sigma= \left[\begin{array}{cccc} \sigma_1^2&&&\\ &\sigma_2^2&&\\ &&\sigma_3^2&\\ &&&\sigma_4^2 \end{array}\right]$Σ=⎣⎢⎢⎡​σ12​​σ22​​σ32​​σ42​​⎦⎥⎥⎤​ 这样得到$\sigma_j^2=\frac{1}{m}\sum({x^{(i)}-u})^2$σj2​=m1​∑(x(i)−u)2

这样的假设会导致各个维度之间完全不相关，高斯轮廓曲线是平行的。

还可以假设$\Sigma=\sigma^2I= \left[\begin{array}{cccc} \sigma^2&&&\\ &\sigma^2&&\\ &&\sigma^2&\\ &&&\sigma^2 \end{array}\right]$Σ=σ2I=⎣⎢⎢⎡​σ2​σ2​σ2​σ2​⎦⎥⎥⎤​,即高斯的轮廓曲线是圆型。以上这些假设都过强，不能采用。

---

假设$z\sim N(0,I)$z∼N(0,I),其中$z\in R^{d}\,\,(d\lt n)$z∈Rd(d<n)

$x|z\sim N(u+\Lambda z,\Psi)$x∣z∼N(u+Λz,Ψ)

对等的可以说:

$x=u+\Lambda z + \varepsilon$x=u+Λz+ε,其中$\varepsilon\sim N(0,\Psi)$ε∼N(0,Ψ)并且$\Psi$Ψ是一个对角矩阵。

上面这些参数$u\in R^{n}\,\,\,\,\,\Lambda\in R^{n\times d}\,\,\,\,\,\Psi\in R^{n\times n}$u∈RnΛ∈Rn×dΨ∈Rn×n且$d\leq n$d≤n

例子：

$z\in R$z∈R

$x\in R^2$x∈R2

$\Lambda= \left[\begin{array}{c}2\\1\end{array}\right]$Λ=[21​]

$\Psi= \left[\begin{array}{cc}1&0\\0&2\end{array}\right]$Ψ=[10​02​]

$u=\left[\begin{array}{c}0\\0\end{array}\right]$u=[00​]

$z^{(i)}\sim N(0,1)$z(i)∼N(0,1)

上图中横轴中红色的点是对$z$z的一个采样，斜线上的点是$\Lambda z$Λz,由于$u=\vec0$u=0,那么斜线上的点同样为$u+\Lambda z$u+Λz,图上绿色的圈是每个采样点$z$z对应$x$x的可能分布。因为$\varepsilon$ε服从高斯分布，因此$x$x是在在对应紫色点为中心的一个高斯分布的采样。

---

拟合模型中的参数

为了描述模型中的参数的拟合方法，需要将高斯模型写成另一种形式：
$x=\left[\begin{array}{c}x_1\\x_2\end{array}\right]$x=[x1​x2​​]其中$x_1\in R^{r}$x1​∈Rr $x_2\in R^{s}$x2​∈Rs那么自然$x\in R^{r+s}$x∈Rr+s。

$x\sim N(u,\Sigma)$x∼N(u,Σ),其中$u=\left[\begin{array}{c}u_1\\u_2\end{array}\right]$u=[u1​u2​​],那么$\Sigma=\left[\begin{array}{cc}\Sigma_{11}&\Sigma_{12}\\\Sigma_{21}&\Sigma_{22}\end{array}\right]$Σ=[Σ11​Σ21​​Σ12​Σ22​​]。其中$\Sigma_{12}\in R^{r\times s}$Σ12​∈Rr×s

$P(x_1)$P(x1​)的边际分布为：

$P(x_1)=\int_{x_2}P(x1,x2)dx_2$P(x1​)=∫x2​​P(x1,x2)dx2​

其中$x_1\sim N(u_1,\Sigma_{11})$x1​∼N(u1​,Σ11​)

$P(x_1|x_2)=\frac{P(x_1x_2)}{P(x_2)}$P(x1​∣x2​)=P(x2​)P(x1​x2​)​

其中$P(x_1x_2)\sim N(u,\Sigma)$P(x1​x2​)∼N(u,Σ)，$P(x_2)\sim N(u2,\Sigma_{22})$P(x2​)∼N(u2,Σ22​)

$P(x_1|x_2)\sim N(u_{1|2},\Sigma_{1|2})$P(x1​∣x2​)∼N(u1∣2​,Σ1∣2​)对应的$u_{1|2}=u_1+\Sigma_{12}\Sigma_{22}^{-1}(x_2-u_2)$u1∣2​=u1​+Σ12​Σ22−1​(x2​−u2​)且$\Sigma_{1|2}=\Sigma_{11}-\Sigma_{12}\Sigma_{22}^{-1}\Sigma_{21}$Σ1∣2​=Σ11​−Σ12​Σ22−1​Σ21​

---

$x$x和$z$z的联合概率分布因子分析为：

$\left[\begin{array}{c}z\\x\end{array}\right]\sim N(u_{xz},\Sigma)$[zx​]∼N(uxz​,Σ)

$z\in N(0,I)$z∈N(0,I)

$x=u+\Lambda z + \varepsilon$x=u+Λz+ε其中$\varepsilon \sim N(0,\Psi)$ε∼N(0,Ψ)

$E[z]=0$E[z]=0

$E[x]=E[u+\Lambda z+\varepsilon]=u$E[x]=E[u+Λz+ε]=u因为$\varepsilon$ε和$z$z的希望都为$0$0。

$u_{zx}=E\left[\begin{array}{c}z\\x\end{array}\right]=\left[\begin{array}{c}\vec0\\u\end{array}\right]$uzx​=E[zx​]=[0u​]

$\Sigma = \left[\begin{array}{cc}E[(z-E[z])(z-E[z])^T]&E[(z-E[z])(x-E[x])^T]\\E[(x-E[x])(x-E[x])^T]&E[(x-E[x])(z-E[z])^T]\end{array}\right]$Σ=[E[(z−E[z])(z−E[z])T]E[(x−E[x])(x−E[x])T]​E[(z−E[z])(x−E[x])T]E[(x−E[x])(z−E[z])T]​]

$\Sigma_{11}=cov(z)=I$Σ11​=cov(z)=I

$\Sigma_{21}=E[(x-E[x])(z-E[z])^T]=E[(u-\Lambda z+\varepsilon-u)z]=E[\Lambda zz^T]-E[\Sigma z]=\Lambda E[zz^T]=\Lambda$Σ21​=E[(x−E[x])(z−E[z])T]=E[(u−Λz+ε−u)z]=E[ΛzzT]−E[Σz]=ΛE[zzT]=Λ

上式中$\Sigma$Σ和$z$z是相互独立的，且期望均为0，因此$E[\Sigma z]=0$E[Σz]=0

$\Sigma_{22}=E[(u-\Lambda z+\varepsilon-u)(u-\Lambda z+\varepsilon-u)^T]=\Lambda \Lambda^T+\Psi$Σ22​=E[(u−Λz+ε−u)(u−Λz+ε−u)T]=ΛΛT+Ψ

综上$\left[\begin{array}{c}z\\x\end{array}\right]\sim N(\left[\begin{array}{c}\vec0\\u\end{array}\right],\left[\begin{array}{cc}I&\Lambda^T\\\Lambda&\Lambda \Lambda^T+\Psi\end{array}\right])$[zx​]∼N([0u​],[IΛ​ΛTΛΛT+Ψ​])

---

给定样本$\{x^{(1)},x^{(2)}......x^{(m)}\}${x(1),x(2)......x(m)}对其建模P(x)，其$x\sim N(u,\Lambda \Lambda^T+\Psi)$x∼N(u,ΛΛT+Ψ)

如果直接对其求最大似然$l(\theta)=\sum log(P(x^{(i)}))$l(θ)=∑log(P(x(i)))可以发现是十分困难的。因此为了求解最优值，因此其EM步骤为：

E step:

$Q(z^{(i)})=P(z^{(i)}|x^{(i)};\theta)$Q(z(i))=P(z(i)∣x(i);θ)

M step

$\arg \max_{\theta}\sum_{i=1}^{m}\int_{z}Q_i(z^{(i))}log\frac{P(x^{(i)},z^{(i)};u,\Lambda,\Psi)}{Q_i(z^{(i)})}$argθmax​i=1∑m​∫z​Qi​(z(i))logQi​(z(i))P(x(i),z(i);u,Λ,Ψ)​