高斯混合模型與最大期望算法

本文的閱讀等級:中級

假設你知道一個連續型隨機向量 \mathbf{x} 的機率密度函數 (以下簡稱密度函數) p(\mathbf{x}|\boldsymbol{\theta}) 受一組參數 \boldsymbol{\theta} 制約。譬如,常態分布 (高斯分布) 的密度函數 \mathcal{N}(\mathbf{x}|\boldsymbol{\mu},\Sigma) 受期望值 \boldsymbol{\mu} 與共變異數矩陣 \Sigma 制約,常態分布的參數為 \boldsymbol{\theta}=\{\boldsymbol{\mu},\Sigma\} (見“多變量常態分布”)。為了估計機率模型的參數,你需要取得該機率分布的樣本。假設我們有一筆大小為 n 的樣本 \mathcal{X}=\{\mathbf{x}_i\}_{i=1}^n,這些數據點是獨立的,而且服從相同的機率分布 p。最大似然估計 (maximum likelihood estimation) 是一種常用的參數估計法。對於給定的樣本 \mathcal{X},參數 \boldsymbol{\theta} 的似然函數 (likelihood) 定義為

\displaystyle  \mathcal{L}(\boldsymbol{\theta}|\mathcal{X})=p(\mathcal{X}|\boldsymbol{\theta})=\prod_{i=1}^np(\mathbf{x}_i|\boldsymbol{\theta})

也就是說似然函數是給定參數後,樣本的條件密度函數。在樣本 \mathcal{X} 固定的情形下,我們將似然函數看作 \boldsymbol{\theta} 的一個函數。顧名思義,最大似然估計的目標要找出 \boldsymbol{\theta}^\ast 使得 \mathcal{L} 有最大值:

\displaystyle  \boldsymbol{\theta}^\ast=\arg\max_{\boldsymbol{\theta}}\mathcal{L}(\boldsymbol{\theta}|\mathcal{X})

對數 \log 是一個單調遞增函數,可知 \mathcal{L} 的最大值與 \log\mathcal{L} 的最大值發生在同一個 \boldsymbol{\theta}^\ast。在實際應用時,我們通常考慮較易於計算的 \log\mathcal{L}(\boldsymbol{\theta}|\mathcal{X})。對於某些機率分布,最大似然估計很容易求得,譬如常態分布,計算 \log\mathcal{L}(\{\boldsymbol{\mu},\Sigma\}|\mathcal{X})\boldsymbol{\mu}\Sigma 的偏導數並設為零,可得代數解 (見“多變量常態分布的最大似然估計”)。不過,對於一些形式較為複雜的機率分布,最大似然估計未必存在代數解,這時我們必須使用迭代法計算。

 
混合模型

在一些應用領域,例如,機器學習、圖形識別 (pattern recognition) 以及電腦視覺,隨機向量 \mathbf{x} 經常具有不規則的機率分布型態。混合模型 (mixture model) 是一種描述不規則分布的機率模型。混合模型將多個形式相同的密度函數,稱為混合元件 (mixture component),組合成一個密度函數:

\displaystyle   p(\mathbf{x}|\boldsymbol{\Theta})=\sum_{k=1}^m\alpha_kp(\mathbf{x}|\boldsymbol{\theta}_k)

其中 \boldsymbol{\Theta}=\{\alpha_k,\boldsymbol{\theta}_k\}_{k=1}^m 表示混合模型的參數集合,\boldsymbol{\theta}_k 是混合元件 p(\mathbf{x}|\boldsymbol{\theta}_k) 的參數,\alpha_k\ge 0p(\mathbf{x}|\boldsymbol{\theta}_k) 的權值,\sum_{k=1}^m\alpha_k=1。混合模型的元件疊加方式稱為凸組合 (見“凸組合、凸包與凸集”),如此可保證

\displaystyle  \int p(\mathbf{x}|\boldsymbol{\Theta})d\mathbf{x}=\sum_{k=1}^m\alpha_k\int p(\mathbf{x}|\boldsymbol{\theta}_k)d\mathbf{x}=\sum_{k=1}^m\alpha_k=1

 
高斯混合模型 (Gaussian mixture model) 可能是最常見的一種混合模型,其中混合元件為高斯密度函數 p(\mathbf{x}|\boldsymbol{\theta}_k)=\mathcal{N}(\mathbf{x}|\boldsymbol{\mu}_k,\Sigma_k)\boldsymbol{\theta}_k=\{\boldsymbol{\mu}_k,\Sigma_k\}。給定樣本 \mathcal{X}=\{\mathbf{x}_i\}_{i=1}^n,混合模型參數 \boldsymbol{\Theta} 的似然函數定義為

\displaystyle   \mathcal{L}(\boldsymbol{\Theta}|\mathcal{X})=p(\mathcal{X}|\boldsymbol{\Theta})=\prod_{i=1}^np(\mathbf{x}_i|\boldsymbol{\Theta})=\prod_{i=1}^n\sum_{k=1}^m\alpha_kp(\mathbf{x}_i|\boldsymbol{\theta}_k)

計算對數,

\displaystyle   \log\mathcal{L}(\boldsymbol{\Theta}|\mathcal{X})=\log\left\{\prod_{i=1}^np(\mathbf{x}_i|\boldsymbol{\Theta})\right\}=\sum_{i=1}^n\log\left\{\sum_{k=1}^m\alpha_kp(\mathbf{x}_i|\boldsymbol{\theta}_k)\right\}

不幸地,\log\mathcal{L}(\boldsymbol{\Theta}|\mathcal{X}) 包含和的對數,致使最大化的計算變得相當困難。欲突破困境,我們需要創新的想法。

 
最大期望算法

在混合模型中,混合元件 p(\mathbf{x}|\boldsymbol{\theta}_k) 的權重 \alpha_k 既是模型參數,也可視為第 k 個混合元件被選中的事前 (prior) 機率。設想你有 m 個甕 (混合元件),每個甕裡面有無窮多顆球 (數據點),其密度函數為 p(\mathbf{x}|\boldsymbol{\theta}_k)。數據樣本 \mathcal{X}=\{\mathbf{x}_i\}_{i=1}^n 的產生過程如下:你閉上眼睛隨機挑選一個甕,然後從中抽出一顆球,睜開眼睛後發現你得到數據點 \mathbf{x}_i,按此方式重複 n 次。令 \mathbf{z}=(z_1,\ldots,z_m) 代表選出一個甕的離散型隨機向量,z_k=1z_j=0j\neq k,表示第 k 個甕被選中。實際上,\mathbf{z} 是無法量測的隨機向量,稱為隱藏變數 (hidden variable)。定義事前機率 p(z_k=1)=\alpha_kk=1,\ldots,m,稱為類別 (categorical) 分布。隱藏變數 \mathbf{z} 的機率即為

\displaystyle   p(\mathbf{z})=\prod_{k=1}^mp(z_k=1)^{z_k}=\prod_{k=1}^m\alpha_k^{z_k}

舉例來說,\mathbf{z}=(1,0,\ldots,0) 表示第一個甕被選中,發生的機率是 p(\mathbf{z})=p(z_1=1)^1p(z_2=1)^0\cdots p(z_m=1)^0=p(z_1=1)=\alpha_1。按照這個思考模型,每個混合元件可用條件密度函數表示:

\displaystyle   p(\mathbf{x}|z_k=1)=p(\mathbf{x}|\boldsymbol{\theta}_k),~~~k=1,\ldots,m

或寫成

\displaystyle   p(\mathbf{x}|\mathbf{z})=\prod_{k=1}^mp(\mathbf{x}|z_k=1)^{z_k}=\prod_{k=1}^mp(\mathbf{x}|\boldsymbol{\theta}_k)^{z_k}

使用全機率公式,我們可以得到混合模型:

\displaystyle   \begin{aligned}  p(\mathbf{x}|\boldsymbol{\Theta})&=\sum_{\mathbf{z}}p(\mathbf{x}|\mathbf{z})p(\mathbf{z})\\  &=\sum_{k=1}^mp(\mathbf{x}|z_k=1)p(z_k=1)\\  &=\sum_{k=1}^m\alpha_kp(\mathbf{x}|\boldsymbol{\theta}_k).    \end{aligned}

 
介紹混合模型的最大似然估計算法之前,我們先討論一個問題:如果你知道混合模型參數 \boldsymbol{\Theta},給定一個數據點 \mathbf{x},能否推測它來自哪個混合元件?也就是計算事後 (posterior) 機率 p(z_k=1|\mathbf{x})?使用貝氏定理 (Bayes’ theorem,見“條件機率與貝氏定理”),

\displaystyle   \begin{aligned}  r_{k}(\mathbf{x})&=p(z_k=1|\mathbf{x})\\  &=\frac{p(\mathbf{x}|z_k=1)p(z_k=1)}{p(\mathbf{x})}\\  &=\frac{p(\mathbf{x}|z_k=1)p(z_k=1)}{\sum_{l=1}^mp(\mathbf{x}|z_l=1)p(z_l=1)}\\  &=\frac{\alpha_k\,p(\mathbf{x}|\boldsymbol{\theta}_k)}{\sum_{l=1}^m\alpha_l\,p(\mathbf{x}|\boldsymbol{\theta}_l)}.  \end{aligned}

事後機率 r_k(\mathbf{x}) 稱為責任 (responsibility),意思是第 k 個混合元件要對給定的數據點 \mathbf{x} 的生成擔負多少責任。請注意,r_k(\mathbf{x}) 具有歸一性,\sum_{k=1}^mr_k(\mathbf{x})=\sum_{k=1}^mp(z_k=1|\mathbf{x})=1。稍後我們將使用此式。

 
根據前述數據產生的模型,我們要從給定的樣本 \mathcal{X}=\{\mathbf{x}_i\}_{i=1}^n 反推每個甕被選中的機率 p(z_k=1)=\alpha_k,以及每個甕裡面球的條件密度函數 p(\mathbf{x}|z_k=1) 的參數 \boldsymbol{\theta}_k,聽起來這似乎是一個不可能的任務。最大期望算法 (expectation-maximization algorithm,簡稱 EM 算法) 是計算混合模型參數的最大似然估計的一個有效方法。採用前面引入的機率記號表示對數似然函數:

\displaystyle   \log\mathcal{L}(\boldsymbol{\Theta})=\sum_{i=1}^n\log p(\mathbf{x}_i|\boldsymbol{\Theta})=\sum_{i=1}^n\log\left\{\sum_{k=1}^mp(\mathbf{x}_i|z_k=1)p(z_k=1)\right\}

最大期望算法是一種迭代法。假設 \boldsymbol{\Theta}=\{\alpha_k,\boldsymbol{\theta}_k\}_{k=1}^m 表示目前所估計出的舊混合模型參數,\boldsymbol{\Theta}'=\{\alpha'_k,\boldsymbol{\theta}'_k\}_{k=1}^m 表示尚待決定的新參數。為簡化記號,我們省略所有受制約函數的參數,例如,\mathcal{L}=\mathcal{L}(\boldsymbol{\Theta}) 代表舊模型的似然函數,p'(\mathbf{x}_i)=p(\mathbf{x}_i|\boldsymbol{\Theta}') 代表新模型的密度函數。考慮兩組模型參數的對數似然函數改變量,並代入新混合模型的密度函數表達式,

\displaystyle   \begin{aligned}  \log\mathcal{L}'-\log\mathcal{L}&=\sum_{i=1}^n\log\frac{p'(\mathbf{x}_i)}{p(\mathbf{x}_i)}\\  &=\sum_{i=1}^n\log\left\{\frac{\sum_{k=1}^mp'(\mathbf{x}_i|z_k=1)p'(z_k=1)}{p(\mathbf{x}_i)}\right\}\\  &=\sum_{i=1}^n\log\left\{\sum_{k=1}^mp(z_k=1|\mathbf{x}_i)\frac{p'(\mathbf{x}_i|z_k=1)p'(z_k=1)}{p(\mathbf{x}_i)p(z_k=1|\mathbf{x}_i)}\right\}.  \end{aligned}

上面最後一個式子之所以引進 p(z_k=1|\mathbf{x}_i) 是為了套用 Jensen 不等式 (見“凸函數”):因為 -\log 是一個凸函數,若每一 \lambda_k\ge 0\sum_{k=1}^m\lambda_k=1,下式成立:

\displaystyle   \log\left\{\sum_{k=1}^m\lambda_ky_k\right\}\ge\sum_{k=1}^m\lambda_k\log y_k

直白地說,Jensen 不等式聲明凸組合的對數大於或等於對數的凸組合。在前一式中,責任 (事後機率) p(z_k=1|\mathbf{x}_i) 就是 \lambda_k 這個角色,因此

\displaystyle   \begin{aligned}  \log\mathcal{L}'-\log\mathcal{L}&\ge \sum_{i=1}^n\sum_{k=1}^mp(z_k=1|\mathbf{x}_i)\log\left\{\frac{p'(\mathbf{x}_i|z_k=1)p'(z_k=1)}{p(\mathbf{x}_i)p(z_k=1|\mathbf{x}_i)}\right\}\\  &=\sum_{i=1}^n\sum_{k=1}^mp(z_k=1|\mathbf{x}_i)\log\left\{p'(\mathbf{x}_i|z_k=1)p'(z_k=1)\right\}\\  &~~~-\sum_{i=1}^n\sum_{k=1}^mp(z_k=1|\mathbf{x}_i)\log\left\{p(\mathbf{x}_i)p(z_k=1|\mathbf{x}_i)\right\},  \end{aligned}

其中不等式右邊的第二項由舊模型參數 \boldsymbol{\Theta} 固定,可視為一個常數 c (包含負號)。我們在乎的是與新模型參數 \boldsymbol{\Theta}' 有關的第一項,於是定義

\displaystyle   \begin{aligned}  Q(\boldsymbol{\Theta}',\boldsymbol{\Theta})&=\sum_{i=1}^n\sum_{k=1}^mp(z_k=1|\mathbf{x}_i)\log\left\{p'(\mathbf{x}_i|z_k=1)p'(z_k=1)\right\}\\  &=\sum_{i=1}^n\sum_{k=1}^mp(z_k=1|\mathbf{x}_i)\log\left\{\alpha'_k p(\mathbf{x}_i|\boldsymbol{\theta}'_k)\right\}.  \end{aligned}

原本我們希望找到新參數 \boldsymbol{\Theta}' 最大化 \log\mathcal{L}',但你知道 \log\mathcal{L}'\ge \log\mathcal{L}+Q+c,也就是說 \log\mathcal{L}+Q+c\log\mathcal{L}' 的下界。欲使 \log\mathcal{L}' 有最大的下界,你可以設法找到 \boldsymbol{\Theta}' 使最大化目標函數 Q,這比直接最大化 \log\mathcal{L}' 容易得多,最大期望算法稱之為 M─步驟 (最大─步驟)。最大化 Q 必然使得 \log\mathcal{L}' 增大,除非 \log\mathcal{L}' 已經抵達局部最大值 (local maximum)。另外,所謂的 E─步驟 (期望─步驟) 是指確立目標函數 Q(\boldsymbol{\Theta}',\boldsymbol{\Theta}),也就是用舊模型參數 \boldsymbol{\Theta} 計算責任 (事後機率) r_{ik}=r_k(\mathbf{x}_i)=p(z_k=1|\mathbf{x}_i)1=1,\ldots,nk=1,\ldots,m

 
我們將估計混合模型參數的最大期望算法整理於下:初始化 \boldsymbol{\Theta}^0=\{\alpha_k^0,\boldsymbol{\theta}^0_k\}_{k=1}^m,設 t=0。重複步驟1與2直到滿足收斂條件即停止 (譬如 \log\mathcal{L} 不再增大)。

  1. E─步驟. 使用 \boldsymbol{\Theta}^t=\{\alpha_k^t,\boldsymbol{\theta}^t_k\}_{k=1}^m 定義 Q(\boldsymbol{\Theta}',\boldsymbol{\Theta}^t)。具體地說,計算每個樣本的責任,對於 i=1,\ldots,nk=1,\ldots,m

    \displaystyle   r^t_{ik}=\frac{\alpha^t_k\,p(\mathbf{x}_i|\boldsymbol{\theta}^t_k)}{\sum_{l=1}^m\alpha^t_l\,p(\mathbf{x}_i|\boldsymbol{\theta}^t_l)}

  2. M─步驟. 解這個優化問題:

    \displaystyle   \begin{aligned}  \boldsymbol{\Theta}^{t+1}&=\arg\max_{\boldsymbol{\Theta}'}Q(\boldsymbol{\Theta}',\boldsymbol{\Theta}^t)\\  &=\arg\max_{\boldsymbol{\Theta}'}\sum_{i=1}^n\sum_{k=1}^mr^t_{ik}\log\left\{\alpha'_k\,p(\mathbf{x}_i|\boldsymbol{\theta}'_k)\right\}\\  &=\arg\max_{\boldsymbol{\Theta}'}\left\{Q_1\left(\{\alpha'_k\},\boldsymbol{\Theta}^t\right)+Q_2\left(\{\boldsymbol{\theta}'_k\},\boldsymbol{\Theta}^t\right)\right\},  \end{aligned}

    其中

    \displaystyle  \begin{aligned}  Q_1\left(\{\alpha'_k\},\boldsymbol{\Theta}^t\right)&=\sum_{i=1}^n\sum_{k=1}^mr^t_{ik}\log\alpha'_k\\  Q_2\left(\{\boldsymbol{\theta}'_k\},\boldsymbol{\Theta}^t\right)&=\sum_{i=1}^n\sum_{k=1}^mr^t_{ik}\log p(\mathbf{x}_i|\boldsymbol{\theta}'_k).\end{aligned}

 
混合模型參數 \boldsymbol{\Theta}=\{\alpha_k,\boldsymbol{\theta}_k\}_{k=1}^m 區分為兩類:\boldsymbol{\theta}_k 是所採用的混合元件參數,權重 \alpha_k\ge 0 還要滿足歸一條件 \sum_{k=1}^m\alpha_k=1。因此,M-步驟可以切割為兩個獨立的問題:

\displaystyle  \begin{aligned}  \{\alpha^{t+1}_k\}&=\arg\max_{\{\alpha'_k\}}Q_1\left(\{\alpha'_k\},\boldsymbol{\Theta}^t\right)\\  \{\boldsymbol{\theta}^{t+1}_k\}&=\arg\max_{\{\boldsymbol{\theta}'_k\}}Q_2\left(\{\boldsymbol{\theta}'_k\},\boldsymbol{\Theta}^t\right).\end{aligned}

底下說明如何利用 Lagrange 乘數法解出最大化 Q_1 的最佳權重 \alpha'_k (見“Lagrange 乘數法”):

\displaystyle   \begin{array}{ll}  \hbox{maximize} & Q_1\left(\{\alpha'_k\},\boldsymbol{\Theta}^t\right)\\  \hbox{subject to}& \sum_{k=1}^m\alpha'_k=1.  \end{array}

定義 Lagrangian 函數

\displaystyle   L\left(\{\alpha'_k\},\lambda\right)=\sum_{i=1}^n\sum_{k=1}^mr^t_{ik}\log\alpha'_k+\lambda\left(\sum_{k=1}^m\alpha'_k-1\right)

其中 \lambda 是 Lagrange 乘數。求導可得

\displaystyle   \frac{\partial L}{\partial\alpha'_k}=\frac{1}{\alpha'_k}\sum_{i=1}^nr^t_{ik}+\lambda

設上式等於零,乘以 \alpha'_k,並加總所有的 k,使用 \sum_{k=1}^mr^t_{ik}=1

\displaystyle   \lambda=\sum_{k=1}^m\lambda\alpha'_k=-\sum_{i=1}^n\sum_{k=1}^mr^t_{ik}=-n

因此,最佳權重為

\displaystyle   \alpha'_k=\frac{n^t_k}{n}

上面令 n^t_k=\sum_{i=1}^nr^t_{ik}。這個結果與所採用的模型元件無關。

 
高斯混合模型的最大期望算法

高斯混合模型是最大期望算法的一個經典應用。對於隨機變數 \mathbf{x}\in\mathbb{R}^d,寫出高斯密度函數 (見“多變量常態分布”)

\displaystyle   \mathcal{N}(\mathbf{x}|\boldsymbol{\mu}_k,\Sigma_k)=\frac{1}{(2\pi)^{d/2}|\Sigma_k|^{1/2}}\exp\left\{-\frac{1}{2}(\mathbf{x}-\boldsymbol{\mu}_k)^T\Sigma_k^{-1}(\mathbf{x}-\boldsymbol{\mu}_k)\right\}

因此

\displaystyle\begin{aligned}  Q_2(\{\boldsymbol{\mu}'_k,\Sigma'_k\},\boldsymbol{\Theta}^t)  &=\sum_{i=1}^n\sum_{k=1}^mr^t_{ik}\log\mathcal{N}(\mathbf{x}_i|\boldsymbol{\mu}'_k,\Sigma'_k)\\  &=\sum_{i=1}^n\sum_{k=1}^mr^t_{ik}\left(-\frac{d}{2}\log(2\pi)-\frac{1}{2}\log|\Sigma'_k|-\frac{1}{2}(\mathbf{x}_i-\boldsymbol{\mu}'_k)^T(\Sigma'_k)^{-1}(\mathbf{x}_i-\boldsymbol{\mu}'_k)\right).  \end{aligned}

我們的任務是求出使 Q_2 最大化的 \boldsymbol{\mu}'_k\Sigma'_k。計算 Q_2\boldsymbol{\mu}'_k 的偏導數 (見“多變量常態分布的最大似然估計”),

\displaystyle   \frac{\partial Q_2}{\partial \boldsymbol{\mu}'_k}=\sum_{i=1}^nr^t_{ik}(\Sigma'_k)^{-1}(\mathbf{x}_i-\boldsymbol{\mu}'_k)=(\Sigma'_k)^{-1}\sum_{i=1}^nr^t_{ik}(\mathbf{x}_i-\boldsymbol{\mu}'_k)

設上式為零,左乘 \Sigma'_k,解得

\displaystyle   \boldsymbol{\mu}'_k=\frac{1}{n^t_k}\sum_{i=1}^nr^t_{ik}\mathbf{x}_i

接著將 Q_2 包含的二次型改寫為跡數並使用循環不變性[1] (見“跡數的性質與應用”):

\displaystyle\begin{aligned}  Q_2(\{\boldsymbol{\mu}'_k,\Sigma'_k\},\boldsymbol{\Theta}^t)  &=\sum_{i=1}^n\sum_{k=1}^mr^t_{ik}\left(-\frac{d}{2}\log(2\pi)-\frac{1}{2}\log|\Sigma'_k|-\frac{1}{2}\hbox{trace}\left\{(\mathbf{x}_i-\boldsymbol{\mu}'_k)^T(\Sigma'_k)^{-1}(\mathbf{x}_i-\boldsymbol{\mu}'_k)\right\}\right)\\  &=\sum_{i=1}^n\sum_{k=1}^mr^t_{ik}\left(-\frac{d}{2}\log(2\pi)-\frac{1}{2}\log|\Sigma'_k|-\frac{1}{2}\hbox{trace}\left\{(\Sigma'_k)^{-1}(\mathbf{x}_i-\boldsymbol{\mu}'_k)(\mathbf{x}_i-\boldsymbol{\mu}'_k)^T\right\}\right).  \end{aligned}

計算 Q_2\Sigma'_k 的偏導數 (見“跡數與行列式的導數”,det-2,tr-18),

\displaystyle   \frac{\partial Q_2}{\partial \Sigma'_k}=-\frac{1}{2}\sum_{i=1}^nr^t_{ik}\left((\Sigma'_k)^{-1}-(\Sigma'_k)^{-1}(\mathbf{x}_i-\boldsymbol{\mu}'_k)(\mathbf{x}_i-\boldsymbol{\mu}'_k)^T(\Sigma'_k)^{-1}\right)

設上式等於零,左右同時乘以 \Sigma'_k,解得

\displaystyle   \Sigma'_k=\frac{1}{n^t_k}\sum_{i=1}^nr^t_{ik}(\mathbf{x}_i-\boldsymbol{\mu}'_k)(\mathbf{x}_i-\boldsymbol{\mu}'_k)^T

附帶一提,d\times d 階樣本共變異數矩陣 \Sigma'_k 為可逆的 (即正定) 一個充要條件是 \hbox{span}\{r_{ik}^t(\mathbf{x}_i-\boldsymbol{\mu}'_k)\}_{i=1}^n=\mathbb{R}^d (見“每週問題 October 17, 2016”)。這意味樣本大小 n 不能小於隨機向量 \mathbf{x} 的維數 d

 
最後我將高斯混合模型的最大期望算法的計算公式整理在下面:給定樣本 \mathcal{X}=\{\mathbf{x}_i\}_{i=1}^n,設高斯混合模型參數的初始值為 \alpha^0_k\boldsymbol{\mu}^0_k\Sigma_k^0k=1,\ldots,mt=0。重複執行下列步驟直到滿足收斂條件為止。

  1. E─步驟. 對於 i=1,\ldots,nk=1,\ldots,m

    \displaystyle   r^t_{ik}=\frac{\alpha^t_k\mathcal{N}(\mathbf{x}_i|\boldsymbol{\mu}^t_k,\Sigma^t_k)}{\sum_{l=1}^m\alpha^t_l\mathcal{N}(\mathbf{x}_i|\boldsymbol{\mu}^t_l,\Sigma^t_l)}

  2. M─步驟. 對於 k=1,\ldots,mn^t_k=\sum_{i=1}^nr^t_{ik},且

    \displaystyle   \begin{aligned}  \alpha^{t+1}_k&=\frac{n^t_k}{n}\\  \boldsymbol{\mu}^{t+1}_k&=\frac{1}{n^t_k}\sum_{i=1}^nr^t_{ik}\mathbf{x}_i\\  \Sigma^{t+1}_k&=\frac{1}{n^t_k}\sum_{i=1}^nr^t_{ik}(\mathbf{x}_i-\boldsymbol{\mu}^{t+1}_k)(\mathbf{x}_i-\boldsymbol{\mu}^{t+1}_k)^T.  \end{aligned}

 
最大期望算法是應用廣泛的一般性算法,不僅可計算高斯混合模型的最大似然估計,此法也適用於其他具備隱藏變數的機率模型,譬如因素分析 (見“因素分析”) 以及因素分析混合模型。最大期望算法並不限定 \mathbf{x} 為連續型隨機向量,對於離散型隨機向量仍然有效。更多詳細的討論請見[2]

註解
[1] 在數理統計的計算,我們常運用跡數化簡,例如,

\displaystyle   \mathbf{x}^TA\mathbf{x}=\hbox{trace}(\mathbf{x}^TA\mathbf{x})=\hbox{trace}(A\mathbf{x}\mathbf{x}^T)

另外,跡數也可幫助證明,譬如,“每週問題 October 26, 2015”。
[2] 維基百科:Expectation-maximization algorithm

廣告
本篇發表於 機器學習 並標籤為 , , , , , 。將永久鏈結加入書籤。

2 Responses to 高斯混合模型與最大期望算法

  1. Ricky Li 說道:

    周老师,有机会能讲一讲 SVM 的推导吗?

  2. ccjou 說道:

    全面性的理解svm需要知道優化理論的duality, KKT, SMO等概念與方法。等有時間把這些背景知識介紹後再講svm。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s