GMM_understandmd

Gaussian Mixture Model (GMM)

$X$ $l\times N$ ( n= 1 ~ N)

X = [x_{1} x_{2} . . . x_{n} . . . x_{N}]

$\pi_k$ $1 \times 1$ (k = 1~K)

$\mu_k$ $l\times 1$ (k = 1~K)

$\Sigma_k$ $l \times l$ (k = 1~K)

$\boldsymbol{\phi}$ $l \times N$

\begin{matrix} ϕ = [ϕ_{k} (x_{n})] = [\dots ϕ (x_{n}) \dots ϕ (x_{N})] = [\begin{matrix} ⋮ \\ ϕ_{k} (X)^{T} \\ ⋮ \end{matrix}] \end{matrix}

$\phi_k(\boldsymbol{x})$ :

\begin{matrix} ϕ_{k} (x) = \frac{1}{(2 π)^{l / 2} | Σ_{k} |^{1 / 2}} \exp (- \frac{1}{2} (x - μ_{k})^{T} Σ_{k}^{- 1} (x - μ_{k})) \\ \ln ϕ_{k} (x) = - \frac{l}{2} \ln (2 π) - \frac{1}{2} \ln | Σ_{k} | - \frac{1}{2} (x - μ_{k})^{T} Σ_{k}^{- 1} (x - μ_{k}) \end{matrix}

$\boldsymbol{Z}$ $K \times N$

\begin{matrix} Z = [. . . z_{n} . . . z_{N}] \\ = [\begin{matrix} ⋮ \\ z_{k}^{T} \\ ⋮ \end{matrix}] \end{matrix}

$z_{k n}$ $1 \times 1$ (k = 1 ~ K)

$\boldsymbol{z_k} = [0, 1, ..., 1, ..., 0]^T$ $K$ $N$ $N \times 1$ )

$\boldsymbol{z_n} = [0, 0, ..., 1, ..., 0]^T$ $K$ $K \times 1$ $z_{k} = 1$ $p$ , random variable

\begin{matrix} p (z | π) = \prod_{k = 1}^{K} π_{k}^{1^{⊤} z_{k}} \\ p (x | z, Σ, μ) = \prod_{k = 1}^{K} {ϕ_{k} (x)}^{1^{⊤} z_{k}} \end{matrix}

Goal:

\arg max_{π, Σ, μ} p (X | π, Σ, μ)

think about the Expectation–maximization algorithm

\arg max_{π, Σ, μ} \ln p (X | θ) = L (q, θ) + KL (q ∥ p)

where

\begin{array}{r} L (q, θ) = \sum_{Z} q (Z) \ln {\frac{p (X, Z | θ)}{q (Z)}} \\ KL (q ∥ p) = - \sum_{Z} q (Z) \ln {\frac{p (Z | X, θ)}{q (Z)}} \end{array}

$\boldsymbol{z_1} \boldsymbol{z_2} ...\boldsymbol{z_n}... \boldsymbol{z_N}$ independent

$p(\boldsymbol{X}, \boldsymbol{Z} | \boldsymbol{\theta})$

\begin{aligned} p (X, Z | θ) & = p (X | Z, π, Σ, μ) p (Z | π, Σ, μ) \\ = p (X | Z, Σ, μ) p (Z | π) \\ = \prod_{n = 1}^{N} p (x_{n} | Z, Σ, μ) \prod_{n = 1}^{N} p (z_{n} | π) \\ = \prod_{n = 1}^{N} p (x_{n} | z_{n}, Σ, μ) \prod_{n = 1}^{N} p (z_{n} | π) \end{aligned}

Hence

\begin{aligned} \ln (p (X, Z | θ)) & = \sum_{n = 1}^{N} \ln p (x_{n} | z_{n}, Σ, μ) + \sum_{n = 1}^{N} \ln p (z_{n} | π) \\ = \sum_{n = 1}^{N} \sum_{k = 1}^{K} (\ln π_{k}) z_{k n} + \sum_{n = 1}^{N} \sum_{k = 1}^{K} (\ln ϕ_{k} (x_{n})) z_{k n} \\ = \ln π^{T} \cdot Z \cdot o n e s (N, 1) + \\ \sum_{n = 1}^{N} \sum_{k = 1}^{K} [- \frac{l}{2} \ln (2 π) - \frac{1}{2} \ln | Σ_{k} | - \frac{1}{2} (x_{n} - μ_{k})^{T} Σ_{k}^{- 1} (x_{n} - μ_{k})] z_{k n} \\ = (\ln π^{T} - \frac{1}{2} \ln | Σ |^{T}) \cdot Z \cdot o n e s (N, 1) - \frac{l}{2} \ln (2 π) o n e s (1, K) \cdot Z \cdot o n e s (N, 1) \\ - \frac{1}{2} \sum_{k = 1}^{K} [tr ((X - μ_{k} \cdot 1^{T})^{T} Σ_{k}^{- 1} (X - μ_{k} \cdot 1^{T}) \cdot diag (z_{k}))] \\ = (\ln π^{T} - \frac{1}{2} \ln | Σ |^{T}) \cdot Z \cdot o n e s (N, 1) - \frac{l}{2} \ln (2 π) N \\ - \frac{1}{2} \sum_{k = 1}^{K} [tr ((X - μ_{k} \cdot 1^{T})^{T} Σ_{k}^{- 1} (X - μ_{k} \cdot 1^{T}) \cdot diag (z_{k}))] \end{aligned}

notice: $X$ $Z, \theta$ $q(Z), \theta$

EM method

\ln p (X | θ) = L (q, θ) + KL (q | p)

$q(Z)$ $\theta$

$q \equiv q^k = p\left(\boldsymbol{Z} | \boldsymbol{X}, \boldsymbol{\theta}^{k}\right) = p\left(\boldsymbol{Z} | \boldsymbol{X}, \boldsymbol{\theta}^{\text { old }}\right)$

\begin{aligned} θ^{k + 1} & \equiv \underset{θ}{argmax} L (q^{k}, θ) \\ = \underset{θ}{argmax} \sum_{Z} q^{k} \ln {\frac{p (X, Z | θ)}{q^{k}}} \\ = \underset{θ}{argmax} \sum_{Z} q^{k} \ln p (X, Z | θ) - \sum_{Z} q^{k} \ln (q^{k}) \\ = \underset{θ}{argmax} \sum_{Z} q^{k} \ln p (X, Z | θ) \\ = \underset{θ}{argmax} Q (θ, θ^{old}) \end{aligned}

L (q^{k}, θ^{k + 1}) > L (q^{k}, θ^{k}) = \ln p (X | θ^{k})

$\boldsymbol{\theta}^{\text { old }} \equiv \boldsymbol{\theta}^{k}$

Q (θ, θ^{old}) \equiv \sum_{Z} q^{k} \ln p (X, Z | θ)

$\theta$ $q(Z)$

$\boldsymbol{\theta} \equiv \boldsymbol{\theta}^{k+1}$

\ln p (X | θ^{k + 1}) = L (q, θ^{k + 1}) + KL (q | p (Z | X, θ^{k + 1})) = const

$\mathrm{KL}(q | p)\downarrow$ $\mathcal{L}(q, \boldsymbol{\theta^{k+1}})\uparrow$

$\mathrm{KL}(q | p)\downarrow$ $q$ $q^{k+1} = p(\boldsymbol{Z} | \boldsymbol{X}, \boldsymbol{\theta})$

\begin{matrix} \ln p (X | θ^{k + 1}) == L (q^{k + 1}, θ^{k + 1}) \end{matrix}

$\boldsymbol{\theta}^{\text { old }}$ $\boldsymbol{\theta}$ value

θ^{old} \Leftarrow θ^{k + 1}

\begin{aligned} q^{k + 1} & \equiv \underset{q}{argmax} L (q, θ^{k + 1}) \\ \equiv \underset{q}{argmin} KL (q | p (Z | X, θ^{k + 1})) = 0 \\ = p (Z | X, θ^{k + 1}) \\ \ln p (X | θ^{k + 1}) & \equiv L (q, θ^{k + 1}) + KL (q | p (Z | X, θ^{k + 1})) \\ = L (q^{k}, θ^{k + 1}) + KL (q^{k} | p (Z | X, θ^{k + 1})) \\ = L (q^{k + 1}, θ^{k + 1}) + KL (q^{k + 1} | p (Z | X, θ^{k + 1})) \\ = L (q^{k + 1}, θ^{k + 1}) \end{aligned}

\ln p (X | θ^{k + 1}) = L (q^{k + 1}, θ^{k + 1}) > L (q^{k}, θ^{k + 1})

in all

\ln p (X | θ^{k + 1}) = L (q^{k + 1}, θ^{k + 1}) > L (q^{k}, θ^{k + 1}) > \ln p (X | θ^{k}) = L (q^{k}, θ^{k})

\begin{matrix} lim_{k \to \infty} \ln p (X | θ^{k}) = lim_{k \to \infty} L (q^{k}, θ^{k + 1}) = max_{θ} \ln p (X | θ) \\ \begin{aligned} θ_{m a x} & \equiv max_{θ} \ln p (X | θ) \\ = lim_{k \to \infty} θ^{k + 1} \\ = lim_{k \to \infty} \underset{θ}{argmax} \sum_{Z} q^{k} \ln p (X, Z | θ) \\ = lim_{k \to \infty} \underset{θ}{argmax} Q (θ, θ^{k}) \end{aligned} \end{matrix}

$q(Z)$ $\theta$

$q \equiv q^k = p\left(\boldsymbol{Z} | \boldsymbol{X}, \boldsymbol{\theta}^{k}\right) = p\left(\boldsymbol{Z} | \boldsymbol{X}, \boldsymbol{\theta}^{\text { old }}\right)$

$\boldsymbol{\theta}^{\text { old }} \equiv \boldsymbol{\theta}^{k}$

Q (θ, θ^{old}) \equiv \sum_{Z} q^{k} \ln p (X, Z | θ)

Here

\begin{aligned} θ^{k + 1} & \equiv \underset{θ}{argmax} L (q^{k}, θ) \\ = \underset{θ}{argmax} \sum_{Z} q^{k} \ln p (X, Z | θ) - \sum_{Z} q^{k} \ln (q^{k}) \\ = \underset{θ}{argmax} \sum_{Z} q^{k} \ln p (X, Z | θ) \\ = \underset{θ}{argmax} Q (θ, θ^{old}) \end{aligned}

Now find close form of Q

$\sum_\limits{\boldsymbol{Z}} p\left(\boldsymbol{Z} | \boldsymbol{X}, \boldsymbol{\theta}^{\text { old }}\right)$ of $Z$ [probability distribution] random variable

$q^k = p\left(\boldsymbol{Z} | \boldsymbol{X}, \boldsymbol{\theta}^{k}\right) = p\left(\boldsymbol{Z} | \boldsymbol{X}, \boldsymbol{\theta}^{\text { old }}\right)$

\begin{aligned} Q (θ, θ^{old}) & \equiv \sum_{Z} p (Z | X, θ^{old}) \ln p (X, Z | θ) \\ = \sum_{Z} p (Z | X, θ^{old}) {(\ln π^{T} - \frac{1}{2} | Σ |^{T}) \cdot Z \cdot o n e s (N, 1) \\ - \frac{l}{2} \ln (2 π) o n e s (1, K) \cdot Z \cdot o n e s (N, 1) \\ - \frac{1}{2} \sum_{k = 1}^{K} [tr ((X - μ_{k} \cdot 1^{T})^{T} Σ_{k}^{- 1} (X - μ_{k} \cdot 1^{T}) \cdot diag (z_{k}))]} \\ = {[\sum_{n = 1}^{N} \sum_{z_{n}} p (z_{n} | x_{n}, θ^{old}) z_{n}^{T}] (\ln π - \frac{1}{2} | Σ | - \frac{l}{2} \ln (2 π) \cdot 1.)} \\ - \frac{1}{2} {\sum_{n = 1}^{N} \sum_{k = 1}^{K} [\sum_{z_{n}} p (z_{n} | x_{n}, θ^{old}) (x_{n} - μ_{k})^{T} Σ_{k}^{- 1} (x_{n} - μ_{k}) z_{k n}]} \\ = [γ \cdot 1.]^{T} (\ln π - \frac{1}{2} | Σ | - \frac{l}{2} \ln (2 π) \cdot 1.) \\ - \frac{1}{2} \sum_{k = 1}^{K} tr (d i a g (γ_{k}^{T}) \cdot (X - μ_{k} \cdot 1^{T})^{T} Σ_{k}^{- 1} (X - μ_{k} \cdot 1^{T})) \end{aligned}

Here

p (z_{n} | x_{n}, θ^{old}) = \frac{p (x_{n} | z_{n}, θ^{old}) p (z_{n} | θ^{old})}{\sum_{z_{n}} p (x_{n} | z_{n}, θ^{old}) p (z_{n} | θ^{old})}

$1.^T \boldsymbol{\gamma}=ones(1, N)$

\begin{matrix} p (z_{n} = k | x_{n}, θ^{old}) = \frac{ϕ_{k}^{old} (x_{n}) π_{k}^{old}}{\sum_{k = 1}^{K} ϕ_{k}^{old} (x_{n}) π_{k}^{old}} \equiv γ_{k n} \\ γ = ϕ^{old} (X) ⊙ (π_{k}^{old} \cdot {1.}^{T}) ⊙ (\frac{1.}{1. \cdot (π^{old})^{T} ϕ^{old} (X)}) \end{matrix}

maximize Q

\begin{aligned} max_{θ} Q (θ, θ^{old}) & \equiv \sum_{Z} p (Z | X, θ^{old}) \ln p (X, Z | θ) \\ = [γ \cdot 1.]^{T} (\ln π - \frac{1}{2} | Σ | - \frac{l}{2} \ln (2 π) \cdot 1.) \\ - \frac{1}{2} \sum_{k = 1}^{K} tr (d i a g (γ_{k}^{T}) \cdot (X - μ_{k} \cdot 1^{T})^{T} Σ_{k}^{- 1} (X - μ_{k} \cdot 1^{T})) \end{aligned} s.t. {1.}^{T} \cdot π = 1

$L \equiv Q - \lambda (1.^T \cdot \boldsymbol{\pi} - 1)$

$\boldsymbol{\pi}$

\begin{aligned} \frac{\partial L}{\partial π} & = [γ \cdot 1.] ⊙ \frac{1.}{π} - λ 1. = 0 \end{aligned}

[γ \cdot 1.] = λ π

Hence

\begin{aligned} λ & = {1.}^{T} [γ \cdot 1.] = [{1.}^{T} γ] \cdot 1. = o n e s (1, N) \cdot 1. = N \\ π & = \frac{[γ \cdot 1.]}{{1.}^{T} [γ \cdot 1.]} = \frac{[γ \cdot 1.]}{N} \end{aligned}

$\mu_k$

\begin{aligned} \frac{\partial L}{\partial μ_{k}} & = - \frac{1}{2} \cdot 2 \cdot (- 1) Σ_{k}^{- 1} (X - μ_{k} \cdot 1^{T}) d i a g (γ_{k}^{T}) \cdot 1. = 0 \end{aligned}

\begin{matrix} (X - μ_{k} \cdot 1^{T}) d i a g (γ_{k}^{T}) \cdot 1. = 0 \\ (X - μ_{k} \cdot 1^{T}) γ_{k} = 0 \end{matrix}

Hence

μ_{k} = \frac{X γ_{k}}{{1.}^{T} γ_{k}}

$\Sigma_k$

\begin{aligned} d L & = [γ_{k}^{T} \cdot 1.]^{T} (\frac{- 1}{2}) Σ_{k}^{- 1} d Σ_{k} \\ - \frac{1}{2} tr (d i a g (γ_{k}^{T}) \cdot (X - μ_{k} \cdot 1^{T})^{T} d Σ_{k}^{- 1} (X - μ_{k} \cdot 1^{T})) \\ = [γ_{k}^{T} \cdot 1.]^{T} (\frac{- 1}{2}) Σ_{k}^{- 1} d Σ_{k} \\ - \frac{1}{2} tr ((X - μ_{k} \cdot 1^{T}) d i a g (γ_{k}^{T}) \cdot (X - μ_{k} \cdot 1^{T})^{T} d Σ_{k}^{- 1}) \\ = - (\frac{1}{2}) [γ_{k}^{T} \cdot 1.]^{T} Σ_{k}^{- 1} d Σ_{k} \\ + \frac{1}{2} tr ((X - μ_{k} \cdot 1^{T}) d i a g (γ_{k}^{T}) \cdot (X - μ_{k} \cdot 1^{T})^{T} Σ_{k}^{- 1} d Σ_{k} Σ_{k}^{- 1}) \\ = - (\frac{1}{2}) [γ_{k}^{T} \cdot 1.]^{T} Σ_{k}^{- 1} d Σ_{k} \\ + \frac{1}{2} tr (Σ_{k}^{- 1} (X - μ_{k} \cdot 1^{T}) d i a g (γ_{k}^{T}) \cdot (X - μ_{k} \cdot 1^{T})^{T} Σ_{k}^{- 1} d Σ_{k}) \end{aligned}

$0=d(\Sigma_k^{-1}\Sigma_k) = (d\Sigma_k^{-1})\Sigma + \Sigma_k^{-1}d\Sigma_k$ $d\Sigma_k^{-1} = - \Sigma_k^{-1}d\Sigma_k \Sigma_k^{-1}$

\begin{aligned} \frac{\partial L}{\partial Σ_{k}} & = - (\frac{1}{2}) [γ_{k}^{T} \cdot 1.] Σ_{k}^{- T} \\ + \frac{1}{2} (Σ_{k}^{- T} (X - μ_{k} \cdot 1^{T}) d i a g (γ_{k}^{T}) \cdot (X - μ_{k} \cdot 1^{T})^{T} Σ_{k}^{- T}) \\ = 0 \end{aligned}

\begin{matrix} [γ_{k}^{T} \cdot 1.] I_{l \times l} = Σ_{k}^{- T} (X - μ_{k} \cdot 1^{T}) d i a g (γ_{k}^{T}) \cdot (X - μ_{k} \cdot 1^{T})^{T} \\ [γ_{k}^{T} \cdot 1.] I_{l \times l} = (X - μ_{k} \cdot 1^{T}) d i a g (γ_{k}^{T}) \cdot (X - μ_{k} \cdot 1^{T})^{T} Σ_{k}^{- 1} \\ Σ_{k} = \frac{(X - μ_{k} \cdot 1^{T}) d i a g (γ_{k}^{T}) \cdot (X - μ_{k} \cdot 1^{T})^{T}}{[γ_{k}^{T} \cdot 1.]} \end{matrix}

To sum up

For M step

\begin{aligned} π & = \frac{[γ \cdot 1.]}{{1.}^{T} [γ \cdot 1.]} = \frac{[γ \cdot 1.]}{N} \\ μ_{k} & = \frac{X γ_{k}}{{1.}^{T} γ_{k}} \\ Σ_{k} & = \frac{(X - μ_{k} \cdot 1^{T}) d i a g (γ_{k}^{T}) \cdot (X - μ_{k} \cdot 1^{T})^{T}}{{1.}^{T} γ_{k}} = \frac{X d i a g (γ_{k}^{⊤}) X^{T}}{{1.}^{T} γ_{k}} - μ_{k} μ_{k}^{⊤} \end{aligned}

$1.^T \boldsymbol{\gamma}=ones(1, N)$

For E step

\begin{matrix} p (z_{n} = k | x_{n}, θ^{old}) = \frac{ϕ_{k}^{old} (x_{n}) π_{k}^{old}}{\sum_{k = 1}^{K} ϕ_{k}^{old} (x_{n}) π_{k}^{old}} \equiv γ_{k n} \\ γ = ϕ^{old} (X) ⊙ (π^{old} \cdot {1.}^{T}) ⊙ (\frac{1.}{1. \cdot (π^{old})^{T} ϕ^{old} (X)}) \end{matrix}

$\boldsymbol{\gamma}_k$ is (N x 1) matrix

\begin{matrix} γ = [\begin{matrix} ⋮ \\ γ_{k}^{T} \\ ⋮ \end{matrix}] \end{matrix}

Gaussian Mixture Model (GMM)

Goal:

EM method

[M step] fix q(Z)q(Z), change θ\theta

[E step] fix θ\theta, change q(Z)q(Z)

in all

Calculation of [M step] fix q(Z)q(Z), change θ\theta

maximize Q

To sum up

$q(Z)$ $\theta$

$\theta$ $q(Z)$

$q(Z)$ $\theta$