Mengapa algoritma maksimalisasi ekspektasi digunakan?

22

Dari sedikit yang saya tahu algoritma EM dapat digunakan untuk menemukan kemungkinan maksimum ketika menetapkan ke nol turunan parsial sehubungan dengan parameter kemungkinan memberikan seperangkat persamaan yang tidak dapat diselesaikan secara analitis. Tetapi apakah algoritma EM diperlukan alih-alih menggunakan beberapa teknik numerik untuk mencoba menemukan kemungkinan maksimum sehubungan dengan kendala dari set persamaan yang disebutkan.

expectation-maximization pengguna782220
sumber

20

Pertanyaannya sah dan saya memiliki kebingungan yang sama ketika saya pertama kali mempelajari algoritma EM.

Secara umum, algoritma EM mendefinisikan proses berulang yang memungkinkan untuk memaksimalkan fungsi kemungkinan model parametrik dalam kasus di mana beberapa variabel model (atau diperlakukan sebagai) "laten" atau tidak diketahui.

Secara teori, untuk tujuan yang sama, Anda dapat menggunakan algoritma minimisasi untuk secara numerik menemukan fungsi kemungkinan maksimum untuk semua parameter. Namun dalam situasi nyata minimalisasi ini adalah:

jauh lebih intensif secara komputasi
kurang kuat

Aplikasi yang sangat umum dari metode EM adalah pemasangan model campuran. Dalam hal ini mempertimbangkan variabel yang menetapkan setiap sampel ke salah satu komponen sebagai variabel "laten" masalahnya sangat disederhanakan.

Mari kita lihat sebuah contoh. Kami memiliki N sampel diekstraksi dari campuran 2 distribusi normal. Untuk menemukan parameter tanpa EM kita harus meminimalkan: $s = \{s_i\}$

- \log L. (x, θ) = - \log [{Sebuah}_{1} \exp (\frac{(x - μ_{1})^{2}}{2 σ_{1}^{2}}) + {Sebuah}_{2} \exp (\frac{(x - μ_{2})^{2}}{2 σ_{2}^{2}})]

$-\log \mathcal{L}(x,\theta) = -\log\Big[ a_1 \exp\Big( \frac{(x-\mu_1)^2}{2\sigma_1^2}\Big) + a_2 \exp\Big(\frac{(x-\mu_2)^2}{2\sigma_2^2}\Big) \Big]$

Sebaliknya, dengan menggunakan algoritma EM, pertama-tama kita "menetapkan" setiap sampel ke komponen ( langkah E ) dan kemudian menyesuaikan (atau memaksimalkan kemungkinan ) setiap komponen secara terpisah ( langkah M ). Dalam contoh ini, langkah-M hanyalah rata-rata tertimbang untuk menemukan dan . Mengulangi dua langkah ini adalah cara yang lebih sederhana dan lebih kuat untuk meminimalkan . $\mu_k$ $\sigma_k$ $-\log \mathcal{L}(x,\theta)$

pengguna2304916
sumber

12

EM tidak diperlukan daripada menggunakan beberapa teknik numerik karena EM juga merupakan metode numerik. Jadi itu bukan pengganti Newton-Raphson. EM adalah untuk kasus khusus ketika Anda memiliki nilai yang hilang dalam matriks data Anda. Pertimbangkan sampel yang memiliki kerapatan bersyarat . Kemudian log-kemungkinan ini adalah $X = (X_{1},...,X_{n})$ $f_{X|\Theta}(x|\theta)$ Sekarang anggaplah Anda tidak memiliki set data lengkap sehingga terdiri dari data yang diamati dan hilang (atau laten) variabel , sehingga . Maka kemungkinan log untuk data yang diamati adalah

l (θ; X) = l Hai g f_{X | Θ} (X | θ)

$l(\theta;X) = log f_{X|\Theta}(X|\theta)$

X

$X$

Y

$Y$

Z

$Z$

X = (Y, Z)

$X=(Y,Z)$

Secara umum Anda tidak dapat menghitung integral ini secara langsung dan Anda tidak akan mendapatkan solusi bentuk-tertutup untuk

. Untuk tujuan ini, Anda menggunakan metode EM. Ada dua langkah yang diulang untuk

kali. Dalam langkah ini

ini adalah langkah harapan di mana Anda menghitung

l_{Hai b s} (θ, Y) = l Hai g \int f_{X | Θ} (Y, z | θ) ν_{z} (d z)

$l_{obs}(\theta,Y)=log \int f_{X|\Theta}(Y,z|\theta)\nu_{z}(dz)$

l_{o b s} (θ, Y)

$l_{obs}(\theta,Y)$

i

$i$

(i + 1)^{t h}

$(i + 1)^{th}$

di mana

adalah estimasi

di

langkah. Kemudian hitung langkah maksimisasi di mana Anda memaksimalkan

sehubungan dengan

dan mengatur

Q (θ | θ^{(saya)}) = E_{θ^{(saya)}} [l (θ; X | Y]

$Q(\theta|\theta^{(i)}) = E_{\theta^{(i)}}[l(\theta;X|Y]$

θ^{(i)}

$\theta^{(i)}$

Θ

$\Theta$

i^{t h}

$i^{th}$

Q (θ | θ^{(i)})

$Q(\theta|\theta^{(i)})$

θ

$\theta$

θ^{(i + 1)} = m a x Q (θ | θ^{i})

$\theta^{(i+1)} = max Q(\theta|\theta^{i})$ . Anda kemudian ulangi langkah-langkah ini sampai metode menyatu ke beberapa nilai yang akan menjadi estimasi Anda.

Jika Anda memerlukan informasi lebih lanjut tentang metode ini, propertinya, bukti atau aplikasinya cukup lihat artikel Wiki yang sesuai .

Andy
sumber

1

+1 ... EM tidak hanya untuk kasus nilai yang hilang.

Glen_b -Reinstate Monica

@ Andy: Sekalipun mempertimbangkan kasus data yang hilang, saya masih tidak mengerti mengapa menggunakan metode numerik umum untuk menemukan titik di mana turunan parsialnya nol tidak berfungsi.

user782220

Terima kasih Glen, saya hanya tahu itu dalam konteks nilai yang hilang / variabel laten. @ user782220: ketika Anda tidak dapat memiliki solusi bentuk tertutup dari turunan kemungkinan log, menetapkan turunan sama dengan nol tidak akan mengidentifikasi parameter Anda. Inilah sebabnya mengapa Anda menggunakan metode numerik dalam kasus ini. Untuk penjelasan dan contoh, lihat kuliah di sini: people.stat.sfu.ca/~raltman/stat402/402L5.pdf

Andy

1

EM digunakan karena seringkali tidak layak atau tidak mungkin untuk secara langsung menghitung parameter dari suatu model yang memaksimalkan probabilitas suatu dataset mengingat model tersebut.

Ilmuwan TheGrimm
sumber

Mengapa algoritma maksimalisasi ekspektasi digunakan?

Jawaban: