久久精品中字,欧美日韩熟妇一区久久

概述

EM算法迭代地通過E步和M步求解含隱變量的模型的參數(shù)，可以使用極大似然估計(jì)法，也可以使用貝葉斯估計(jì)法。

術(shù)語

三硬幣模型：假設(shè)有3枚硬幣A,B,C,正面出現(xiàn)的概率分別為a,b,c.進(jìn)行如下拋硬幣試驗(yàn)：先擲硬幣A，根據(jù)其結(jié)果選出硬幣B或C，正面選A，反面選B；然后拋擲選出的硬幣，記錄擲硬幣的結(jié)果，正面為1，反面為0。獨(dú)立重復(fù)n次試驗(yàn)。

觀測變量：概率模型中可以觀測到的隨機(jī)變量。比如樸素貝葉斯模型中的輸入X(待分類文本等)，上面例子中的最后擲硬幣的結(jié)果.常用Y表示觀測變量的數(shù)據(jù)

隱變量(潛在變量)：概率模型中觀測不到的隨機(jī)變量，比如上面例子中的擲硬幣A的結(jié)果，常用Z表示隱變量的數(shù)據(jù)

完全數(shù)據(jù)：Y和Z連在一起稱為完全數(shù)據(jù)

不完全數(shù)據(jù)：只有Y

EM算法

預(yù)備知識

Jensen不等式：

若f(x)是凸函數(shù)，有

$tf(x_1) +(1-t)f(x_2) \geq f\left (tx_1+(1-t)x_2 \right)$

直覺理解就是凸函數(shù)任意兩點(diǎn)的割線位于函數(shù)圖形上方

若對于任意點(diǎn)集? $\{x_i\}$ ,若? $\lambda_i \geq 0$ 且? $\sum_{i}\lambda_i = 1$ ?，有

$\sum_i \lambda_i f(x_i)\geq f(\sum_i \lambda_ix_i)$

推導(dǎo)

我們面對一個(gè)含有隱變量的概率模型，目標(biāo)是極大化觀測數(shù)據(jù)(不完全數(shù)據(jù))Y關(guān)于參數(shù) $\theta$ 的對數(shù)似然函數(shù)，即極大化

$L(\theta)=\log P(Y|\theta)=\log \sum_{Z}P(Y,Z|\theta)=\log \left (\sum_{Z}P(Y|Z,\theta)P(Z|\theta) \right )$

由于優(yōu)化函數(shù)中含未觀測數(shù)據(jù)并包含和的對數(shù)，所以直接優(yōu)化很難。

考慮迭代優(yōu)化 $L(\theta)$ ，假設(shè)在第i次迭代后 $\theta$ 的估計(jì)值為 $\theta_i$ ,我們希望下次迭代新的估計(jì)值能夠使 $L(\theta) \gt L(\theta_i)$ ,一直迭代直到得到 $L(\theta)$ 極大值。考慮兩者的差

$\begin{align*}L(\theta)-L(\theta_i)&=\log \left (\sum_{Z}P(Y|Z,\theta)P(Z|\theta) \right )-\log P(Y|\theta_i) \\&=\log \left (\sum_{Z}P(Z|Y,\theta_i)\frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta_i)} \right ) -\log P(Y|\theta_i) \\&\geq\sum_ZP(Z|Y,\theta_i)\log \frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta_i)} -\log P(Y|\theta_i) \ \ \ \ \ \ 利用jensen不等式\\&=\sum_ZP(Z|Y,\theta_i)\log \frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta_i)} - \log P(Y|\theta_i)\sum_ZP(Z|Y,\theta_i) \\&=\sum_ZP(Z|Y,\theta_i)\log \frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta_i)P(Y|\theta_i)}\end{align*}$

令 $B(\theta, \theta_i)=L(\theta_i)+\sum_ZP(Z|Y,\theta_i)\log \frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta_i)P(Y|\theta_i)}$ ,

則 $L(\theta) \geq B(\theta, \theta_i)$ ,即函數(shù) $B(\theta, \theta_i)$ 是函數(shù) $L(\theta)$ 的一個(gè)下界【不同迭代B函數(shù)不同，隨著迭代的增加B函數(shù)越接近L】，因此任何可以使 $B(\theta, \theta_i)$ 增大的 $\theta$ 也可以使 $L(\theta)$ 增大。為了使 $L(\theta)$ 有盡可能大的增長，選擇 $\theta$ 使 $B(\theta, \theta_i)$ 達(dá)到極大，即

$\begin {align*}\theta_i&=\arg \max_{\theta}B(\theta, \theta_i)\\&=\arg \max_{\theta}\left \{L(\theta_i)+\sum_ZP(Z|Y,\theta_i)\log \frac{P(Y|Z,\theta)P(Z|\theta)}{P(Z|Y,\theta_i)P(Y|\theta_i)} \right \} \\&=\arg \max_{\theta}\left \{\sum_ZP(Z|Y,\theta_i)\log \left(P(Y|Z,\theta)P(Z|\theta)\right) \right \} \\&=\arg \max_{\theta}\left \{\sum_ZP(Z|Y,\theta_i)\log P(Y,Z|\theta) \right \}\end{align*}$

上式中最優(yōu)化的函數(shù)稱為Q函數(shù)，不斷迭代這個(gè)過程直到收斂就得到了使似然函數(shù)近似極大的參數(shù)。

正式定義

EM算法通過迭代最大化似然函數(shù)，每次迭代分為兩步：E步，求期望；M步，求極大化。具體過程如下：

選擇參數(shù)初值，開始迭代；

E步：計(jì)算Q函數(shù)

$\begin {align*}Q(\theta, \theta_i)&=E_Z[\log P(Y,Z|\theta)|Y,\theta_i] \\&= \sum_Z P(Z|Y,\theta_i) \log P(Y,Z|\theta)\end {align*}$

M步：求使Q函數(shù)極大化的 $\theta$ ,確定i+1次迭代的參數(shù)估計(jì)值 $\theta_{i+1}$ :

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

迭代至收斂。

說明

EM算法可以任意初始化參數(shù)初值，但是對初值敏感，實(shí)踐中經(jīng)常取多個(gè)不同的初始值并進(jìn)行比較，選擇較好的初始值。

當(dāng)參數(shù)值的變化或Q函數(shù)的變化小于某個(gè)閾值時(shí)，停止迭代。

EM算法無法保證得到全局最優(yōu)值，這也是選取多個(gè)初始值比較的根本原因

上面Q函數(shù)是對于單次試驗(yàn)的期望,對于多次試驗(yàn)可以求多次試驗(yàn)的期望和作為Q函數(shù)（使用求積表示似然函數(shù)）

解決三硬幣問題

假設(shè)三硬幣模型最后觀察到的結(jié)果是1101001011，求abc。

令Z為拋擲硬幣A的結(jié)果，Y為最后的觀察結(jié)果。對一次實(shí)驗(yàn)，有

$\begin {align*}P(Y=y)&=\sum_Z P(Y,Z)=P(Y|Z=1)P(Z=1)+P(Y|Z=0)P(Z=0) \\&=ab^y(1-b)^{1-y}+(1-a)c^y(1-c)^{1-y}\end {align*}$

計(jì)算Q函數(shù)

$\begin {align*}Q(\theta, \theta_i)&=\sum_Z P(Z|Y,\theta_i) \log P(Y,Z|\theta) \\&=\sum_Z \frac{P(Y,Z|\theta_i)}{P(Y|\theta_i)} \log P(Y,Z|\theta) \\&=\frac{a_ib_i^y(1-b_i)^{1-y}}{a_ib_i^y(1-b_i)^{1-y}+(1-a_i)c_i^y(1-c_i)^{1-y}} \log {ab^y(1-b)^{1-y}} + \frac{(1-a_i)c_i^y(1-c_i)^{1-y}}{a_ib_i^y(1-b_i)^{1-y}+(1-a_i)c_i^y(1-c_i)^{1-y}} \log {(1-a)c^y(1-c)^{1-y}} \\&=\mu_i \log {ab^y(1-b)^{1-y}} + (1-\mu_i)\log {(1-a)c^y(1-c)^{1-y}}\end {align*}$

求多次試驗(yàn)的Q函數(shù)，有

$Q(\theta, \theta_i)_{multi}=\sum_{j=1}^n{[\mu_i^j \log {ab^{y_j}(1-b)^{1-y_j}}+(1-\mu_i^j)\log {(1-a)c^{y_j}(1-c)^{1-y_j}}]}$

求導(dǎo)數(shù)，有

$\frac{\delta Q}{\delta a} =\sum_{j=1}^n \frac{\mu_i^j - a}{a(1-a)}=0$

有 $a_{i+1}=a=\frac{1}{n}\sum_{j=1}^n\mu_i^j$

同理有

$b_{i+1}=\frac{\sum_{j=1}^n\mu_i^jy_j}{\sum_{j=1}^n\mu_i^j}$

$c_{j+1}=\frac{\sum_{j=1}^n(1-\mu_i^j)y_j}{\sum_{j=1}^n(1-\mu_i^j)}$

令 $\theta_0=(a_0,b_0, c_0)=(0.5, 0.5, 0.5)$ ,有 $\hat \theta = (\hat a, \hat b, \hat c)=(0.5, 0.6, 0.6)$

令 $\theta_0=(a_0,b_0, c_0)=(0.4, 0.6, 0.7)$ ，有 $\hat \theta = (\hat a, \hat b, \hat c)=(0.4064, 0.5368, 0.6432)$

高斯混合模型

高斯混合模型為

$P(y|\theta) = \sum_{i=1}^K\alpha_i\phi_i(y|\theta_k)$ ,

其中 $\alpha_i$ 是分模型系數(shù)， $\sum_{i=1}^K\alpha_i=1,\alpha_i \geq0$ , $\phi_i(y|\theta_i)$ 是高斯分布密度， $\theta_i=(\mu_i, \sigma_i^2 )$ ,

$\phi(y|\theta)=\frac{1}{\sqrt {2 \pi} \sigma}\exp \left (-\frac{(y - \mu)^2}{2\sigma^2} \right) \\ \phi(y|\theta) = \frac{1}{(2 \pi)^{ \frac {D}{2}} } \frac{1}{\Sigma^{\frac{1}{2}} } \exp \left( -\frac{1}{2} (x - \mu)^T\Sigma^{-1}(x - \mu) \right)$

。高斯混合模型認(rèn)為數(shù)據(jù)是這樣生成的：首先依概率 $\alpha$ 選擇分模型，然后根據(jù)選擇的分模型生成數(shù)據(jù)。包含隱變量“選擇的分模型”，可以通過EM算法估計(jì)高斯混合模型的參數(shù)

和K-means聚類的關(guān)系

【待】

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

EM

EM

概述

術(shù)語