24

Saya telah membaca beberapa penjelasan tentang algoritma EM (misalnya dari Pengenalan Pola Bishop dan Pembelajaran Mesin dan dari Kursus Pertama Roger dan Gerolami tentang Pembelajaran Mesin). Derivasi EM itu ok, saya mengerti. Saya juga mengerti mengapa algoritma menutupi sesuatu: pada setiap langkah kita meningkatkan hasil dan kemungkinan dibatasi oleh 1.0, jadi dengan menggunakan fakta sederhana (jika suatu fungsi bertambah dan dibatasi maka konvergen) kita tahu bahwa algoritma konvergen ke beberapa solusi.

Namun, bagaimana kita tahu itu minimum lokal? Pada setiap langkah, kami hanya mempertimbangkan satu koordinat (baik variabel laten atau parameter), jadi kami mungkin kehilangan sesuatu, seperti minimum lokal yang mengharuskan pemindahan dengan kedua koordinat sekaligus.

Ini saya percaya adalah masalah yang mirip dengan kelas umum dari algoritma mendaki bukit, yang merupakan contoh EM. Jadi untuk algoritma pendakian bukit umum kita memiliki masalah ini untuk fungsi f (x, y) = x * y. Jika kita mulai dari titik (0, 0), maka hanya dengan mempertimbangkan kedua arah sekaligus kita dapat bergerak ke atas dari nilai 0.

missing-data convergence expectation-maximization michal
sumber

3

Kemungkinan dibatasi hanya untuk varian tetap. Artinya, dalam situasi binomial, variansnya adalah

p (1 - p)

$p(1-p)$ ; atau dalam situasi Gaussian, jika varians diasumsikan diketahui. Jika varians tidak diketahui, dan harus diperkirakan, kemungkinan tidak dibatasi. Juga, dalam algoritma EM, ada pemisahan generik dari parameter yang hilang dan, setidaknya untuk statistik sering, tetapi permukaan memang mungkin memiliki pelana.

Tugas

@Stask Saya tidak yakin bahwa kemungkinan umumnya dibatasi bahkan dengan varian tetap. Apakah Anda membatasi keluarga tertentu?

Glen_b -Reinstate Monica

27

EM tidak dijamin konvergen ke minimum lokal. Hanya dijamin untuk menyatu ke titik dengan gradien nol sehubungan dengan parameter. Jadi memang bisa macet di titik sadel.

Tom Minka
sumber

1

Sebagai contoh, lihat hlm. 20 dan 38 di sini , hlm. 85 di sini - coba "sadel" di pembaca Amazon.

Tugas

13

Pertama-tama, adalah mungkin bahwa EM konvergen ke min lokal , sebuah max lokal , atau titik pelana dari fungsi kemungkinan. Lebih tepatnya, seperti yang ditunjukkan Tom Minka , EM dijamin untuk menyatu ke titik dengan gradien nol .

Saya dapat memikirkan dua cara untuk melihat ini; pandangan pertama adalah intuisi murni, dan pandangan kedua adalah sketsa bukti formal. Pertama, saya akan menjelaskan secara singkat bagaimana EM bekerja:

$t$ $b_t(\theta)$ $L(\theta)$ $\theta_t = \arg\max_\theta b_t(\theta)$

Maksimalisasi Ekspektasi sebagai kenaikan gradien

Dalam setiap iterasi , EM mensyaratkan bahwa terikat menyentuh fungsi likelihood pada solusi iterasi sebelumnya yaitu yang menyiratkan gradien mereka juga sama; itu adalah . Jadi, EM setidaknya sama baiknya dengan kenaikan gradien karena setidaknya sama baiknya dengan . Dengan kata lain: $t$ $b_t$ $L$ $\theta_{t-1}$ $g = \nabla b_t(\theta_{t-1}) = \nabla L(\theta_{t-1})$ $\theta_t$ $\theta_{t-1} + \eta g$

jika EM konvergen ke maka juga merupakan titik konvergen untuk kenaikan gradien dan EM memenuhi setiap properti yang dibagi di antara solusi kenaikan gradien (termasuk nilai gradien nol). $\theta^*$ $\theta^*$

Sketsa bukti formal

Satu dapat menunjukkan bahwa kesenjangan antara batas dan fungsi kemungkinan menyatu menjadi nol; itu adalah Seseorang dapat membuktikan bahwa gradien dari ikatan juga menyatu dengan gradien fungsi likelihood; yaitu: Karena dan dan batas-batas yang digunakan dalam EM dapat dibedakan, dan bahwa , kita memiliki dan, oleh karena itu, .

\begin{matrix} (1) & lim_{t \to \infty} L (θ_{t}) - b_{t} (θ_{t}) = 0. \end{matrix}

$\lim_{t \rightarrow \infty} L(\theta_t) - b_t(\theta_t) = 0. \tag{1}$

\begin{matrix} (2) & lim_{t \to \infty} \nabla L (θ_{t}) = \nabla b_{t} (θ_{t}) . \end{matrix}

$\lim_{t \rightarrow \infty} \nabla L(\theta_t) = \nabla b_t(\theta_t). \tag{2}$

(1)

$(1)$

(2)

$(2)$

θ_{t} = \arg max_{θ} b_{t} (θ)

$\theta_t = \arg\max_\theta b_t(\theta)$

\nabla b_{t} (θ_{t}) = 0

$\nabla b_t(\theta_t)=0$

lim_{t \to \infty} \nabla L (θ_{t}) = 0

$\lim_{t \rightarrow \infty} \nabla L(\theta_t) = 0$

Sobi
sumber

Mengapa algoritma Expectation Maximization dijamin untuk menyatu ke optimal lokal?

Jawaban:

Maksimalisasi Ekspektasi sebagai kenaikan gradien

Sketsa bukti formal