@haoqiang 2018-01-12T09:25:23.000000Z 字数 5446 阅读 61

在高斯混合模型中使用EM算法

机器学习

1. 高斯混合模型(Gaussian Misture Model, GMM)

高斯混合模型是指具有如下形式的概率分布模型：

P (x | θ) = \sum k = 1 K α k ϕ (x | θ k)

$P(x|\theta) = \sum_{k=1}^{K}{\alpha_{k}\phi(x|\theta_{k})}$

$x_{i}$ 表示第 $i$ 个观测数据， $i = 1,2,...,N$
$K$ 是混合模型中子高斯模型的数量， $k = 1,2,...,K$
$\alpha_{k}$ 是观测数据属于第 $k$ 个子模型的概率， $\alpha_{k} \geq 0$ ， $\sum_{k=1}^{K}{\alpha_{k}} = 1$
$\phi(x|\theta_{k})$ 是第 $k$ 个子模型的高斯分布密度函数， $\theta_{k}=(\mu_{k},\sigma_{k}^{2})$ ，即：

ϕ (x | θ k) = 1 2 π σ 2 k - - - - \sqrt e x p (- ( x - μ k ) 2 2 σ 2 k)

$\phi(x|\theta_{k}) = \frac{1}{\sqrt{2\pi\sigma^{2}_{k}}} exp\left(-\frac{(x-\mu_{k})^2}{2\sigma^{2}_{k}}\right)$

2. 模型参数学习

用EM算法估计高斯混合模型的参数 $\theta=(\alpha_{1},\alpha_{2},\cdots,\alpha_{K};\theta_{1},\theta_{2},\cdots,\theta_{K})$ .

(1) 明确隐变量

考虑观测数据 $x_{i}$ ， $i = 1,2,...,N$ ，的产生方式：首先依概率 $\alpha_{k}$ 选择第 $k$ 个高斯模型 $\phi(x|\theta_{k})$ ；然后依第 $k$ 个子模型的概率分布 $\phi(x|\theta_{k})$ 生成观测数据 $x_{i}$ 。此时观测数据 $x_{i}$ 已知，反映观测数据 $x_{i}$ 来自第 $k$ 个分模型的数据未知，定义隐变量 $\gamma_{ik}$ ：

γ i k = {1, 0, 第 i 个 观 测 来 自 第 k 个 子 模 型 否 则 i = 1, 2, \dots, N; k = 1, 2, \dots, K

$\begin{aligned} \gamma_{ik}= \begin{cases} 1, & \text{第$i$个观测来自第$k$个子模型} \\ 0, & \text{否则} \end{cases}\\ i=1,2,\cdots,N;\quad k=1,2,\cdots,K \end{aligned}$

那么完全数据可表示为

(x i, γ i 1, γ i 2, \dots, γ i K), i = 1, 2, \dots, N

$(x_i,\gamma_{i1},\gamma_{i2},\cdots,\gamma_{iK}),\quad i=1,2,\cdots,N$

(2) 完全数据的对数似然函数

似然函数：

P (x, γ | θ) = \prod i = 1 N P (x i, γ i 1, γ i 2, \dots, γ i K | θ) = \prod k = 1 K \prod i = 1 N [α k ϕ (x i | θ k)] γ i k = \prod k = 1 K α n k k \prod i = 1 N [ϕ (x i | θ k)] γ i k = \prod k = 1 K α n k k \prod i = 1 N [1 2 π - - \sqrt σ k exp (- ( x i - μ k ) 2 2 σ 2 k)] γ i k

$\begin{aligned} P(x,\gamma|\theta)&=\prod^N_{i=1}{P(x_i,\gamma_{i1},\gamma_{i2},\cdots,\gamma_{iK}|\theta)}\\ &=\prod^K_{k=1}\prod^N_{i=1}\left[\alpha_k\phi(x_i|\theta_{k})\right]^{\gamma_{ik}}\\ &=\prod^K_{k=1}\alpha^{n_k}_k\prod^N_{i=1}\left[\phi(x_i|\theta_{k})\right]^{\gamma_{ik}}\\ &=\prod^K_{k=1}\alpha^{n_k}_k\prod^N_{i=1}\left[\frac{1}{\sqrt{2\pi}\sigma_k}\exp{\left(-\frac{(x_i-\mu_k)^2}{2\sigma^2_k}\right)}\right]^{\gamma_{ik}} \end{aligned}$

$n_k=\sum^N_{i=1}\gamma_{ik}$ 为第 $k$ 个组分生成的样本数， $\sum^K_{k=1}n_k=N$ .

对数似然函数：

log P (x, γ | θ) = \sum k = 1 K {n k log a k + \sum i = 1 N γ i k [log (1 2 π - - \sqrt) - log σ k - 1 2 σ 2 k (x i - μ k) 2]}

$\log{P(x,\gamma|\theta)}=\sum^K_{k=1} \left\{n_k\log{a_k}+\sum^N_{i=1}\gamma_{ik}\left[\log{(\frac{1}{\sqrt{2\pi}})}-\log{\sigma_k}-\frac{1}{2\sigma^2_k}(x_i-\mu_k)^2\right] \right\}$

(3) E步

Q (θ, θ (i)) = E [log P (x, γ | θ (i)) | x, θ (i)] = E {\sum k = 1 K {n k log a k + \sum i = 1 N γ i k [log (1 2 π - - \sqrt) - log σ k - 1 2 σ 2 k (x i - μ k) 2]}} = \sum k = 1 K {\sum i = 1 N (E γ i k) log a k + \sum i = 1 N (E γ i k) [log (1 2 π - - \sqrt) - log σ k - 1 2 σ 2 k (x i - μ k) 2]}

$\begin{aligned} Q(\theta,\theta^{(i)})&=E[\log P(x,\gamma|\theta^{(i)})|x,\theta^{(i)}]\\ &=E\left\{\sum^K_{k=1} \left\{n_k\log{a_k}+\sum^N_{i=1}\gamma_{ik}\left[\log{(\frac{1}{\sqrt{2\pi}})}-\log{\sigma_k}-\frac{1}{2\sigma^2_k}(x_i-\mu_k)^2\right] \right\}\right\}\\ &=\sum^K_{k=1} \left\{\sum^N_{i=1}(E\gamma_{ik})\log{a_k}+\sum^N_{i=1}(E\gamma_{ik})\left[\log{(\frac{1}{\sqrt{2\pi}})}-\log{\sigma_k}-\frac{1}{2\sigma^2_k}(x_i-\mu_k)^2\right] \right\} \end{aligned}$

这里需要计算 $E(\gamma_{ik}|x,\theta)$ ，记作 $\hat{\gamma}_{ik}$ .

γ^i k = E (γ i k | x, θ) = E (γ i k = 1 | x, θ) = P ( γ i k = 1 , x i | θ ) \sum K k = 1 P ( γ i k = 1 , x i | θ ) = P ( x i | γ i k = 1 , θ ) P ( γ i k = 1 | θ ) \sum K k = 1 P ( x i | γ i k = 1 , θ ) P ( γ i k = 1 | θ ) = α k ϕ ( x i | θ k ) \sum K k = 1 α k ϕ ( x i | θ k ), i = 1, 2, . . ., N; k = 1, 2, . . ., K

$\begin{aligned} \hat{\gamma}_{ik}&=E(\gamma_{ik}|x,\theta)=E(\gamma_{ik}=1|x,\theta)\\ &=\frac{P(\gamma_{ik}=1,x_i|\theta)}{\sum^K_{k=1}P(\gamma_{ik}=1,x_i|\theta)}\\ &=\frac{P(x_i|\gamma_{ik}=1,\theta)P(\gamma_{ik}=1|\theta)}{\sum^K_{k=1}P(x_i|\gamma_{ik}=1,\theta)P(\gamma_{ik}=1|\theta)}\\ &=\frac{\alpha_{k}\phi(x_{i}|\theta_{k})}{\sum_{k=1}^{K}{\alpha_{k}\phi(x_{i}|\theta_{k})}},\quad i = 1,2,...,N; k = 1,2,...,K \end{aligned}$

$\hat{\gamma}_{ik}$ 表示当前模型参数下第 $i$ 个观测数据来自第 $k$ 个子模型的概率。

将 $\hat{\gamma}_{ik}=E\gamma_{ik}$ 及 $\hat{n}_k=\sum^N_{i=1}(E\gamma_{ik})$ 带入 $Q(\theta,\theta^{(i)})$ ：

Q(θ,θ(i))=∑k=1K{n^klogak+∑i=1Nγ^ik[log(12π−−√)−logσk−12σ2k(xi−μk)2]}

$Q(\theta,\theta^{(i)})=\sum^K_{k=1} \left\{\hat{n}_k\log{a_k}+\sum^N_{i=1}\hat{\gamma}_{ik}\left[\log{(\frac{1}{\sqrt{2\pi}})}-\log{\sigma_k}-\frac{1}{2\sigma^2_k}(x_i-\mu_k)^2\right] \right\}$

(4) M步

求函数 $Q(\theta,\theta^{(i)})$ 对 $\theta$ 的极大值，新一轮的模型参数为：

θ (i + 1) = arg max θ Q (θ, θ (i))

$\theta^{(i+1)}=\arg\max_\theta{Q(\theta,\theta^{(i)})}$

用 $\hat{\mu}_k$ ， $\hat{\sigma}^2_k$ 和 $\hat{\alpha}_k$ ， $k=1,2,\cdots,K$ ，表示 $\theta^{(i+1)}$ 的各参数。分别对 $\mu_k$ ， $\sigma^2_k$ 求偏导令其为0，得到 $\hat{\mu}_k$ ， $\hat{\sigma}^2_k$ ；在 $\sum^K_{k=1}\alpha_k=1$ 条件下对 $\alpha_k$ 求偏导令其为0，得到 $\hat{\alpha}_k$ 。

μ^k Σ^k α^k = \sum N i = 1 ( γ ^ i k x i ) \sum N i = 1 γ ^ i k, k = 1, 2, . . ., K = \sum N i = 1 γ ^ i k ( x i - μ ^ k ) 2 \sum N i = 1 γ ^ i k, k = 1, 2, . . ., K (用 这 一 轮 更 新 后 的 μ k^) = \sum N i = 1 γ ^ i k N, k = 1, 2, . . ., K

$\begin{aligned} \hat{\mu}_{k} &= \frac{\sum_{i=1}^{N}{(\hat{\gamma}_{ik}}x_{i})}{\sum_{i=1}^{N}{\hat{\gamma}_{ik}}}, k=1,2,...,K\\ \hat{\Sigma}_{k} &= \frac{\sum_{i=1}^{N}{\hat{\gamma}_{ik}}(x_{i}-\hat{\mu}_{k})^2}{\sum_{i=1}^{N}{\hat{\gamma}_{ik}}}, k = 1,2,...,K (用这一轮更新后的 \hat{\mu_{k}})\\ \hat{\alpha}_{k} &= \frac{\sum_{i=1}^{N}{\hat{\gamma}_{ik}}}{N}, k=1,2,...,K \end{aligned}$

算法总结

(1) 初始化参数。

(2) E步：依据当前模型参数，计算子模型 $k$ 对观测数据 $x_i$ 的响应度

γ^i k = α k ϕ ( x i | θ k ) \sum K k = 1 α k ϕ ( x i | θ k ), i = 1, 2, . . ., N; k = 1, 2, . . ., K

$\hat{\gamma}_{ik}=\frac{\alpha_{k}\phi(x_{i}|\theta_{k})}{\sum_{k=1}^{K}{\alpha_{k}\phi(x_{i}|\theta_{k})}},\quad i = 1,2,...,N; k = 1,2,...,K$

(3) M步：计算新一轮迭代的参数模型

μ^k Σ^k α^k = \sum N i = 1 ( γ ^ i k x i ) \sum N i = 1 γ ^ i k, k = 1, 2, . . ., K = \sum N i = 1 γ ^ i k ( x i - μ ^ k ) 2 \sum N i = 1 γ ^ i k, k = 1, 2, . . ., K = \sum N i = 1 γ ^ i k N, k = 1, 2, . . ., K

$\begin{aligned} \hat{\mu}_{k} &= \frac{\sum_{i=1}^{N}{(\hat{\gamma}_{ik}}x_{i})}{\sum_{i=1}^{N}{\hat{\gamma}_{ik}}}, k=1,2,...,K\\ \hat{\Sigma}_{k} &= \frac{\sum_{i=1}^{N}{\hat{\gamma}_{ik}}(x_{i}-\hat{\mu}_{k})^2}{\sum_{i=1}^{N}{\hat{\gamma}_{ik}}}, k = 1,2,...,K\\ \hat{\alpha}_{k} &= \frac{\sum_{i=1}^{N}{\hat{\gamma}_{ik}}}{N}, k=1,2,...,K \end{aligned}$

(4) 重复第(2)(3)步直至收敛。