高斯混合模型2021-8-14

高斯混合模型模型定义 $\color{#FF0000}假设的$ 生成过程求后验分布聚类参数求解极大似然估计求 $\mu_i$ 求 $\sigma_i$ 求 $\alpha_i$ 迭代过程EM算法完全数据的对数似然函数E步：确定Q函数M步：Q函数最大化例子参考文档

高斯混合模型

模型定义

\begin{matrix} (1) & \begin{array}{r} P_{M} (x) = \sum_{i = 1}^{k} α_{i} \cdot ϕ (x | μ_{i}, σ_{i}^{2}) \end{array} \end{matrix}

其中，各符号解释如下：

$x$ 为观测变量。
$k$ $\phi(x|\mu_i,\sigma_i^2) = \Large \frac{1}{\sqrt{2 \pi} \sigma_i} e^{-\frac{(x-\mu_i)^2}{2\sigma_i^2}}$ 为高斯模型的概率密度函数。
$\alpha_i$ $x$ 先验分布 $\alpha_i > 0, \sum_{i=0}^k \alpha_i=1$ 。

$\color{#FF0000}假设的$ 生成过程

注意：此过程为我们假设的数据生成过程，基于一定的假设，便于后续的推导。

假设样本的生成过程由高斯混合模型生成：

先验分布 $\alpha_1,\alpha_2,...,\alpha_k$ $x$ $\alpha_i$ $i$ 个混合成分的概率。
根据被选择的高斯分布的概率密度函数进行采样，从而生成相应的样本。
$D=\{x_1, x_2, ..., x_m\}$ 。

总结：该过程生成了若干数据，数据来源于多个高斯模型，但是，我们不知道高斯模型的参数，也不知道每个数据来自于哪个高斯模型。而我们要做的，便是解决上述两个”不知道“。

求后验分布

该步的目标是解决第二个“不知道”：数据来自于哪个高斯模型。

$D=\{x_1, x_2, ..., x_m\}$ $z_j \in \{1,2,...,k\}$ $x_j$ 假设 $z_j$ 的先验概率为：

\begin{matrix} (2) & P (z_{j} = i) = α_{i} ， i \in {1, 2, . . ., k} \end{matrix}

$z_j$ 的后验分布为：

\begin{matrix} (3) & \begin{aligned} P_{M} (z_{j} = i | x_{j}) & = \frac{P (z_{j} = i) P_{M} (x_{j} | z_{j} = i)}{P_{M} (x_{j})} \\ = \frac{α_{i} \cdot ϕ (x_{j} | μ_{i}, σ_{i}^{2})}{\sum_{l = 1}^{k} α_{l} \cdot ϕ (x_{j} | μ_{l}, σ_{l}^{2})} \end{aligned} \end{matrix}

$P_M(z_j=i|x_j)$ $x_j$ $i$ $\gamma_{ji} \; (i=1,2,...,k)$ 。

由全概率公式可得：

\begin{matrix} (4) & \sum_{i = 1}^{k} P_{M} (z_{j} = i | x_{j}) = \sum_{i = 1}^{k} γ_{j i} = 1 \end{matrix}

聚类

$D$ $k$ $C=\{C_1,C_2,...,C_k \}$ $x_j$ $\lambda_j$ 如下确定：

\begin{matrix} (5) & \underset{i \in {1, 2, . . ., k}}{argmax} γ_{j i} \end{matrix}

因此，从原型聚类的角度来看，高斯混合聚类时采用概率模型（高斯分布）对原型进行刻画，簇划分则由原型对应的后验概率确定。

参数求解

极大似然估计

$D$ $m$ $\{(\alpha_i,\mu_i,\sigma_i^2) | 1 \leq i \leq k \}$ 进行估计。对数似然函数为：

\begin{matrix} (6) & \begin{aligned} L L (D) & = l n (\prod_{j = 1}^{m} P_{M} (x_{j})) \\ = \sum_{j = 1}^{m} l n (P_{M} (x_{j})) \\ = \sum_{j = 1}^{m} l n (\sum_{l = 1}^{k} α_{l} \cdot ϕ (x_{j} | μ_{l}, σ_{l}^{2})) \\ = \sum_{j = 1}^{m} l n (\sum_{l = 1}^{k} α_{l} \cdot \frac{1}{\sqrt{2 π} σ_{l}} e^{- \frac{(x_{j} - μ_{l})^{2}}{2 σ_{l}^{2}}}) \end{aligned} \end{matrix}

$\mu_i$

$\large \frac{\partial LL(D)}{\large \partial \mu_i} = 0$ ，则：

\begin{matrix} (7) & \begin{aligned} \frac{\partial L L (D)}{\partial μ_{i}} & = \frac{\partial \sum_{j = 1}^{m} l n (\sum_{l = 1}^{k} α_{l} \cdot \frac{1}{\sqrt{2 π} σ_{l}} e^{- \frac{(x_{j} - μ_{l})^{2}}{2 σ_{l}^{2}}})}{\partial μ_{i}} \\ = \sum_{j = 1}^{m} \frac{α_{i} \cdot \frac{1}{\sqrt{2 π} σ_{i}} \cdot 2 (x_{j} - μ_{i}) \cdot e^{- \frac{(x_{j} - μ_{i})^{2}}{2 σ_{i}^{2}}}}{\sum_{l = 1}^{k} α_{l} \cdot ϕ (x_{j} | μ_{l}, σ_{l})} \\ = \sum_{j = 1}^{m} \frac{α_{i} \cdot 2 (x_{j} - μ_{i}) \cdot ϕ (x_{j} | μ_{i}, σ_{i})}{\sum_{l = 1}^{k} α_{l} \cdot ϕ (x_{j} | μ_{l}, σ_{l})} \\ = 2 \sum_{j = 1}^{m} γ_{j i} \cdot (x_{j} - μ_{i}) \\ = 2 \sum_{j = 1}^{m} γ_{j i} x_{j} - 2 \sum_{j = 1}^{m} γ_{j i} μ_{i} \\ = 0 \end{aligned} \end{matrix}

求解可得：

\begin{matrix} (8) & μ_{i} = \frac{\sum_{j = 1}^{m} γ_{j i} x_{j}}{\sum_{j = 1}^{m} γ_{j i}} \end{matrix}

$\sigma_i$

$\Large \frac{\partial LL(D)}{\Large \partial \sigma_i} = 0$ ，则：

\begin{matrix} (9) & \begin{aligned} \frac{\partial L L (D)}{\partial σ_{i}} & = \frac{\partial \sum_{j = 1}^{m} l n (\sum_{l = 1}^{k} α_{l} \cdot \frac{1}{\sqrt{2 π} σ_{l}} e^{- \frac{(x_{j} - μ_{l})^{2}}{2 σ_{l}^{2}}})}{\partial σ_{i}} \\ = \sum_{j = 1}^{m} \frac{α_{i} \cdot \frac{1}{\sqrt{2 π}} [- 1 \cdot \frac{1}{σ_{i}^{2}} \cdot e^{- \frac{(x_{j} - μ_{i})^{2}}{2 σ_{i}^{2}}} + \frac{1}{σ_{i}} \cdot (x_{j} - μ_{i})^{2} \cdot \frac{1}{σ_{i}^{3}} \cdot e^{- \frac{(x_{j} - μ_{i})^{2}}{2 σ_{i}^{2}}}]}{\sum_{l = 1}^{k} α_{l} \cdot ϕ (x_{j} | μ_{l}, σ_{l})} \\ = \sum_{j = 1}^{m} \frac{α_{i} \cdot \frac{1}{\sqrt{2 π}} \cdot e^{- \frac{(x_{j} - μ_{i})^{2}}{2 σ_{i}^{2}}} \cdot [\frac{- 1}{σ_{i}^{2}} + \frac{1}{σ_{i}^{4}} (x_{j} - μ_{i})^{2}]}{\sum_{l = 1}^{k} α_{l} \cdot ϕ (x_{j} | μ_{l}, σ_{l})} \\ = \sum_{j = 1}^{m} α_{i} \cdot \frac{1}{\sqrt{2 π}} \cdot γ_{j i} \cdot \frac{(x_{j} - μ_{i})^{2} - σ_{i}^{2}}{σ_{i}^{4}} \\ = 0 \end{aligned} \end{matrix}

求解可得：

\begin{matrix} (10) & σ_{i}^{2} = \frac{\sum_{j = 1}^{m} γ_{j i} (x_{j} - μ_{i})^{2}}{\sum_{j = 1}^{m} γ_{j i}} \end{matrix}

$\alpha_i$

$\alpha_i$ $LL(D)$ $\alpha_i > 0， \sum_{i=0}^k \alpha_i=1$ ，构造如下拉格朗日函数：

\begin{matrix} (11) & \begin{matrix} L = L L (D) + λ (\sum_{l = 1}^{k} α_{l} - 1) \\ 其 中 ， λ 为 拉 格 朗 日 乘 子 \end{matrix} \end{matrix}

$\alpha_i$ 求导可得：

\begin{matrix} (12) & \begin{aligned} \frac{\partial L}{\partial α_{i}} & = \frac{\partial {\sum_{j = 1}^{m} l n (\sum_{l = 1}^{k} α_{l} \cdot \frac{1}{\sqrt{2 π} σ_{l}} e^{- \frac{(x_{j} - μ_{l})^{2}}{2 σ_{l}^{2}}}) + λ (\sum_{l = 1}^{k} α_{l} - 1)}}{\partial α_{i}} \\ = \sum_{j = 1}^{m} \frac{\frac{1}{\sqrt{2 π} σ_{i}} e^{- \frac{(x_{j} - μ_{i})^{2}}{2 σ_{i}^{2}}}}{\sum_{l = 1}^{k} α_{l} \cdot ϕ (x_{j} | μ_{l}, σ_{l}^{2})} + λ \\ = \sum_{j = 1}^{m} \frac{ϕ (x_{j} | u_{i}, σ_{i}^{2})}{\sum_{l = 1}^{k} α_{l} \cdot ϕ (x_{j} | μ_{l}, σ_{l}^{2})} + λ \\ = 0 \end{aligned} \end{matrix}

$\alpha_i$ 可得：

\begin{matrix} (13) & \begin{aligned} \sum_{j = 1}^{m} \frac{α_{i} \cdot ϕ (x_{j} | u_{i}, σ_{i}^{2})}{\sum_{l = 1}^{k} α_{l} \cdot \Leftrightarrow ϕ (x_{j} | μ_{l}, σ_{l}^{2})} + α_{i} λ = 0 \\ \Rightarrow \sum_{j = 1}^{m} γ_{j i} + α_{i} λ = 0 \\ \Rightarrow \sum_{l = 1}^{k} \sum_{j = 1}^{m} γ_{j i} + \sum_{l = 1}^{k} α_{i} λ = 0 \\ \Rightarrow \sum_{j = 1}^{m} \sum_{l = 1}^{k} γ_{j i} + λ = 0 \\ \Rightarrow m + λ = 0 \\ \Rightarrow λ = - m \end{aligned} \end{matrix}

$\lambda$ $\sum_{j=1}^{m} \gamma_{ji} - \alpha_i m= 0$

求解可得：

\begin{matrix} (14) & α_{i} = \frac{1}{m} \sum_{j = 1}^{m} γ_{j i} \end{matrix}

迭代过程

$\gamma_{ji}$
根据参数公式对参数进行更新

EM算法

完全数据的对数似然函数

首先需要明确隐变量，写出完全数据的对数似然函数。

定义隐变量如下：

\begin{matrix} (15) & γ_{j k} = {\begin{cases} 1, & 第 j 个观测来自第 k 个分模型 \\ 0, & 否则 \end{cases} \end{matrix}

$(x_j,\gamma_{j1},\gamma_{j2},...,\gamma_{jk}), \quad j=1,2,...,m$

$\theta=(\mu,\sigma^2)$ ，则完全数据的似然函数为：

\begin{matrix} (16) & \begin{aligned} P (x, γ ∣ α, θ) & = \prod_{j = 1}^{m} P (x_{j}, γ_{j 1}, γ_{j 2}, \dots, γ_{j k} ∣ α, θ) \\ = \prod_{j = 1}^{m} \prod_{l = 1}^{k} {[α_{l} ϕ (x_{j} ∣ θ_{l})]}^{γ_{j l}} \\ = \prod_{l = 1}^{k} \prod_{j = 1}^{m} {[α_{l} ϕ (x_{j} ∣ θ_{l})]}^{γ_{j l}} \\ = \prod_{l = 1}^{k} α_{l}^{\sum_{j = 1}^{m} γ_{j l}} \prod_{j = 1}^{m} {[ϕ (x_{j} ∣ θ_{l})]}^{γ_{j l}} \\ = \prod_{l = 1}^{k} α_{l}^{\sum_{j = 1}^{m} γ_{j l}} \prod_{j = 1}^{m} {[\frac{1}{\sqrt{2 π} σ_{l}} \exp (- \frac{{(x_{j} - μ_{l})}^{2}}{2 σ_{l}^{2}})]}^{γ_{j l}} \end{aligned} \end{matrix}

上述公式解释：

$P\left(x_{j}, \gamma_{j 1}, \gamma_{j 2}, \cdots, \gamma_{j k} \mid \alpha,\theta\right)$
$\theta$ $x_j$ 的概率，则根据先验知识，该过程分为两个步骤：
- $\alpha_s$ $s$ 个高斯模型
- $\phi(x|\theta_s)$ $x_j$
$x_j$ 由哪个模型生成，则该概率为：
$\begin{matrix} (17) & P (x_{j}, γ_{j 1}, γ_{j 2}, \dots, γ_{j k} ∣ α, θ) = \prod_{l = 1}^{k} {[α_{l} \cdot ϕ (x_{j} | θ)]}^{γ_{j l}} \end{matrix}$
$\lambda$ 为1。
$P\left(x_{j}, \gamma_{j 1}, \gamma_{j 2}, \cdots, \gamma_{j k} \mid \alpha,\theta\right)$ $P(x_j)$ 的区别
$P(x_j) = \sum_{i=1}^{k} \alpha_i \cdot \phi(x_j|\mu_i,\sigma_i^2)$ $x_j$ $k$ $P\left(x_{j}, \gamma_{j 1}, \gamma_{j 2}, \cdots, \gamma_{j k} \mid \alpha,\theta \right)$ $x_j$ 只会来源于某一个高斯模型。
$\sum_{l=1}^k \sum_{j=1}^m \gamma_{jl}=1$

完全数据的对数似然函数为：

\begin{matrix} (18) & \begin{aligned} \ln P (x, γ ∣ α, θ) & = \ln {\prod_{l = 1}^{k} α_{l}^{\sum_{j = 1}^{m} γ_{j l}} \prod_{j = 1}^{m} {[\frac{1}{\sqrt{2 π} σ_{l}} \exp (- \frac{{(x_{j} - μ_{l})}^{2}}{2 σ_{l}^{2}})]}^{γ_{j l}}} \\ = \sum_{l = 1}^{k} {\sum_{j = 1}^{m} γ_{j l} \cdot \ln α_{l} + \sum_{j = 1}^{m} γ_{j l} [\ln \frac{1}{\sqrt{2 π}} - \ln σ_{l} - \frac{(x_{j} - μ_{l})^{2}}{2 σ_{l}^{2}}]} \end{aligned} \end{matrix}

$\gamma_{jl}$ $\gamma_{jl}$ ，则最大化似然函数水到渠成。

$(\alpha,\theta)$ $\gamma_{jl}$ 进行当下的估计。

$(\alpha^{(0)}, \theta^{(0)})$ $\gamma$ $\gamma$ 。将上述步骤迭代进行之，则是EM算法。

E步：确定Q函数

\begin{matrix} (19) & \begin{aligned} Q (θ, α^{(i)}, θ^{(i)}) \\ = E [\log P (x, γ ∣ α, θ) ∣ x, α^{(i)}, θ^{(i)}] \\ = E {\sum_{l = 1}^{k} {(\sum_{j = 1}^{m} γ_{j l} | x_{j}, α^{(i)}, θ^{(i)}) \cdot \ln α_{l} + (\sum_{j = 1}^{m} γ_{j l} | x_{j}, α^{(i)}, θ^{(i)}) [\ln \frac{1}{\sqrt{2 π}} - \ln σ_{l} - \frac{(x_{j} - μ_{l})^{2}}{2 σ_{l}^{2}}]}} \\ = \sum_{l = 1}^{k} {(\sum_{j = 1}^{m} E (γ_{j l} ∣ x_{j}, α^{(i)}, θ^{(i)})) \ln α_{l} + (\sum_{j = 1}^{m} E (γ_{j l} ∣ x_{j}, α^{(i)}, θ^{(i)})) [\ln (\frac{1}{\sqrt{2 π}}) - \log σ_{l} - \frac{1}{2 σ_{l}^{2}} {(x_{j} - μ_{l})}^{2}]} \end{aligned} \end{matrix}

$E\left(\gamma_{j l} \mid x_j, \alpha^{(i)}, \theta^{(i)} \right )$ $\gamma_{jl}$ 的估计：

\begin{matrix} (20) & \begin{aligned} E (γ_{j l} ∣ x_{j}, α^{(i)}, θ^{(i)}) & = P (γ_{j l} = 1 ∣ x_{j}, α^{(i)}, θ^{(i)}) \\ = \frac{P (γ_{j l} = 1, x_{j} ∣ α^{(i)}, θ^{(i)})}{\sum_{t = 1}^{k} P (γ_{j t} = 1, x_{j} ∣ α^{(i)}, θ^{(i)})} \\ = \frac{P (γ_{j l} = 1 ∣ α^{(i)}, θ^{(i)}) \cdot P (x_{j} ∣ γ_{j l} = 1, α^{(i)}, θ^{(i)})}{\sum_{t = 1}^{k} P (x_{j} ∣ γ_{j t} = 1, α^{(i)}, θ^{(i)}) P (γ_{j t} = 1 ∣ α^{(i)}, θ^{(i)})} \\ = \frac{α_{l}^{(i)} \cdot ϕ (x_{j} ∣ θ_{l}^{(i)})}{\sum_{t = 1}^{k} α_{t}^{(i)} \cdot ϕ (x_{j} ∣ θ_{t}^{(i)})} \\ = {\hat{γ}}_{j l}^{(i)}, j = 1, 2, \dots, m; l = 1, 2, \dots, k \end{aligned} \end{matrix}

$E\left(\gamma_{j l} \mid x_j, \alpha^{(i)}, \theta^{(i)} \right )$ $Q$ 函数可得：

\begin{matrix} (21) & \begin{array}{r} Q (θ, α^{(i)}, θ^{(i)}) = \sum_{l = 1}^{k} {(\sum_{j = 1}^{m} {\hat{γ}}_{j l}^{(i)}) \ln α_{l} + (\sum_{j = 1}^{m} {\hat{γ}}_{j l}^{(i)}) [\ln (\frac{1}{\sqrt{2 π}}) - \log σ_{l} - \frac{1}{2 σ_{l}^{2}} {(x_{j} - μ_{l})}^{2}]} \end{array} \end{matrix}

M步：Q函数最大化

$Q$ $Q$ 函数进行最大化，得到下一次迭代的模型参数了，即：

\begin{matrix} (22) & \begin{aligned} α^{(i + 1)}, θ^{(i + 1)} = \arg max_{θ} Q (θ, α^{(i)}, θ^{(i)}) \end{aligned} \end{matrix}

$i+1$ 轮参数为：

\begin{matrix} (23) & \begin{aligned} {\hat{μ}}_{l} & = \frac{\sum_{j = 1}^{m} {\hat{γ}}_{j l}^{(i)} x_{j}}{\sum_{j = 1}^{m} {\hat{γ}}_{j l}^{(i)}} \\ {\hat{σ}}_{l}^{2} & = \frac{\sum_{j = 1}^{m} {\hat{γ}}_{j l}^{(i)} {(x_{j} - μ_{l}^{(i)})}^{2}}{\sum_{j = 1}^{N} {\hat{γ}}_{j l}^{(i)}} \\ {\hat{α}}_{l} & = \frac{\sum_{j = 1}^{m} {\hat{γ}}_{j l}^{(i)}}{m} \\ 其 中 ， l = 1, 2, \dots, k \end{aligned} \end{matrix}

例子

见《西瓜书》P210页。

高斯混合模型

模型定义

假设的假设的\color{#FF0000}假设的生成过程

求后验分布

聚类

参数求解

极大似然估计

求μi\mu_i

求σi\sigma_i

求αi\alpha_i

迭代过程

EM算法

完全数据的对数似然函数

E步：确定Q函数

M步：Q函数最大化

例子

参考文档

$\color{#FF0000}假设的$ 生成过程

$\mu_i$

$\sigma_i$

$\alpha_i$