Dalam pendekatan algoritma EM kami menggunakan ketidaksetaraan Jensen untuk sampai pada
dan definisikan oleh
Semua yang saya baca EM hanya menjatuhkannya tetapi saya selalu merasa tidak nyaman dengan tidak memiliki penjelasan mengapa algoritma EM muncul secara alami. Saya mengerti bahwa likelihood biasanya digunakan untuk menangani penambahan, bukan perkalian, tetapi tampilan dalam definisi terasa tidak termotivasi untuk saya. Mengapa seseorang harus mempertimbangkan dan bukan fungsi monoton lainnya? Untuk berbagai alasan saya menduga bahwa "makna" atau "motivasi" di balik maksimalisasi harapan memiliki semacam penjelasan dalam hal teori informasi dan statistik yang memadai. Jika ada penjelasan seperti itu yang akan jauh lebih memuaskan daripada hanya algoritma abstrak.
sumber
Jawaban:
Algoritma EM memiliki interpretasi yang berbeda dan dapat muncul dalam berbagai bentuk dalam aplikasi yang berbeda.
Semuanya dimulai dengan fungsi kemungkinan , atau ekuivalen, fungsi log-likelihood ingin kami maksimalkan. (Kami umumnya menggunakan logaritma karena menyederhanakan perhitungan: Ini sepenuhnya monoton, cekung, dan .) Dalam dunia ideal, nilai hanya bergantung pada parameter model , jadi kita dapat mencari melalui ruang dan menemukan yang memaksimalkan .log p ( x | q ) log ( a b ) = log a + log b p q q pp(x|θ) logp(x|θ) log(ab)=loga+logb p θ θ p
Namun, dalam banyak aplikasi dunia nyata yang menarik hal-hal lebih rumit, karena tidak semua variabel diamati. Ya, kita mungkin secara langsung mengamati , tetapi beberapa variabel lain tidak teramati. Karena variabel yang hilang , kita berada dalam situasi ayam-dan-telur: Tanpa kita tidak dapat memperkirakan parameter dan tanpa kita tidak dapat menyimpulkan berapa nilai mungkin.z z z θ θ zx z z z θ θ z
Di sinilah algoritma EM berperan. Kita mulai dengan tebakan awal parameter model dan mendapatkan nilai yang diharapkan dari variabel yang hilang (yaitu, langkah E). Ketika kita memiliki nilai-nilai , kita dapat memaksimalkan kemungkinan wrt parameter (yaitu, langkah M, sesuai dengan persamaan dalam pernyataan masalah). Dengan kita dapat memperoleh nilai-nilai baru yang diharapkan dari (langkah E lainnya), seterusnya dan seterusnya. Dengan kata lain, dalam setiap langkah kita mengasumsikan salah satu dari keduanya, danz z θ arg maks θ z z θθ z z θ argmax θ z z θ , dikenal. Kami mengulangi proses berulang ini sampai kemungkinan tidak dapat ditingkatkan lagi.
Singkatnya, ini adalah algoritma EM. Sudah diketahui bahwa kemungkinannya tidak akan pernah berkurang selama proses EM berulang ini. Tetapi perlu diingat bahwa algoritma EM tidak menjamin global optimal. Artinya, mungkin berakhir dengan optimal lokal dari fungsi kemungkinan.
Penampilan dalam persamaan tidak bisa dihindari, karena di sini fungsi yang ingin Anda maksimalkan ditulis sebagai kemungkinan log.θ ( k + 1 )log θ(k+1)
sumber
Kemungkinan vs kemungkinan log
Seperti yang telah dikatakan, diperkenalkan dalam kemungkinan maksimum hanya karena umumnya lebih mudah untuk mengoptimalkan jumlah daripada produk. Alasan kami tidak mempertimbangkan fungsi monoton lainnya adalah bahwa logaritma adalah fungsi unik dengan sifat mengubah produk menjadi jumlah.log
Cara lain untuk memotivasi logaritma adalah sebagai berikut: Alih-alih memaksimalkan probabilitas data dalam model kami, kami dapat mencoba untuk meminimalkan Kullback-Leibler divergensi antara distribusi data, , dan distribusi model, p ( x ∣ θ ) ,pdata(x) p(x∣θ)
Istilah pertama di sisi kanan konstan dalam parameter. Jika kami memiliki sampel dari distribusi data (titik data kami), kami dapat memperkirakan istilah kedua dengan kemungkinan log rata-rata data,N
Pandangan alternatif EM
Saya tidak yakin ini akan menjadi jenis penjelasan yang Anda cari, tetapi saya menemukan pandangan berikut tentang maksimalisasi harapan jauh lebih mencerahkan daripada motivasinya melalui ketidaksetaraan Jensen (Anda dapat menemukan deskripsi terperinci dalam Neal & Hinton (1998) atau dalam buku PRML Chris Bishop, Bab 9.3).
Tidak sulit untuk menunjukkannya
untuk . Jika kita menyebut istilah pertama di sisi kanan , ini menyiratkan hal ituF ( q , θ )q(z∣x) F(q,θ)
Karena divergensi KL selalu positif , adalah batas bawah pada log-kemungkinan untuk setiap tetap . Sekarang, EM dapat dilihat sebagai secara maksimal memaksimalkan sehubungan dengan dan . Secara khusus, dengan menetapkan di E-langkah, kita meminimalkan perbedaan KL di sisi kanan dan dengan demikian memaksimalkan .F(q,θ) q F q θ q(z∣x)=p(z∣x,θ) F
sumber
Makalah yang saya temukan mengklarifikasi sehubungan dengan maksimalisasi-harapan adalah Bayesian K-Means sebagai Algoritma "Maximisasi-Ekspektasi" (pdf) oleh Welling dan Kurihara.
Misalkan kita memiliki model probabilistik dengan pengamatan x , z variabel acak tersembunyi, dan total parameter θ . Kami diberi dataset D dan dipaksa (dengan kekuatan yang lebih tinggi) untuk membuat p ( z , θ | D ) .p(x,z,θ) x z θ D p(z,θ|D)
1. Pengambilan sampel Gibbs
Kami dapat memperkirakan dengan sampling. Gibbs sampling memberi p ( z , θ | D ) dengan bergantian:p(z,θ|D) p(z,θ|D)
2. Teluk Variasional
Sebagai gantinya, kita dapat mencoba membuat distribusi dan q ( z ) dan meminimalkan perbedaan dengan distribusi kita setelah p ( θ , z | D ) . Perbedaan antara distribusi memiliki nama mewah yang nyaman, KL-divergence. Untuk meminimalkan K L [ q ( θ ) q ( z ) | | p ( θ , z | D ) ] kami memperbarui:q(θ) q(z) p(θ,z|D) KL[q(θ)q(z)||p(θ,z|D)]
3. Ekspektasi-Maksimalisasi
Untuk datang dengan distribusi probabilitas penuh untuk dan θ mungkin dianggap ekstrim. Mengapa kita tidak mempertimbangkan estimasi titik untuk salah satu dari ini dan menjaga yang lain tetap bagus dan bernuansa. Dalam EM, parameter θ ditetapkan sebagai yang tidak layak untuk distribusi penuh, dan ditetapkan ke nilai MAP (Maksimum A Posteriori), θ ∗ .z θ θ θ∗
Di sini sebenarnya akan menjadi notasi yang lebih baik: operator argmax dapat mengembalikan beberapa nilai. Tapi jangan sampai nitpick. Dibandingkan dengan variational Bayes Anda melihat bahwa mengoreksi log oleh exp tidak mengubah hasilnya, sehingga tidak perlu lagi.θ∗∈argmax log exp
4. Maksimalisasi-Harapan
Tidak ada alasan untuk memperlakukan sebagai anak manja. Kita juga bisa menggunakan estimasi titik z ∗ untuk variabel tersembunyi kami dan memberikan parameter θ kemewahan distribusi penuh.z z∗ θ
Jika variabel tersembunyi kami adalah variabel indikator, kami tiba-tiba memiliki metode yang murah secara komputasi untuk melakukan inferensi pada jumlah cluster. Dengan kata lain: pemilihan model (atau deteksi relevansi otomatis atau bayangkan nama mewah lain).z
5. Mode bersyarat iterasi
Tentu saja, anak poster inferensi perkiraan adalah dengan menggunakan estimasi titik untuk parameter serta pengamatan z .θ z
Untuk melihat bagaimana Maximization-Expectation dimainkan, saya sangat merekomendasikan artikel ini. Namun menurut saya, kekuatan dari artikel ini bukanlah aplikasi untuk alternatif berarti, tetapi penjelasan yang jelas dan ringkas tentang perkiraan ini.k
sumber
Ada teknik optimasi yang berguna yang mendasari algoritma EM. Namun, biasanya dinyatakan dalam bahasa teori probabilitas sehingga sulit untuk melihat bahwa pada intinya adalah metode yang tidak ada hubungannya dengan probabilitas dan harapan.
Mempertimbangkan masalah memaksimalkan (atau ekuivalen log g ( x ) ) terhadap x . Jika Anda menuliskan ekspresi untuk g ′ ( x ) dan menetapkannya sama dengan nol, Anda akan sering berakhir dengan persamaan transendental untuk dipecahkan. Ini bisa jahat.
Sekarang anggaplah bahwa bermain dengan baik bersama dalam arti bahwa kombinasi linear dari mereka memberi Anda sesuatu yang mudah untuk dioptimalkan. Misalnya, jika semua f i ( x ) adalah kuadrat dalam x maka kombinasi linear dari f i ( x ) juga akan kuadratik, dan karenanya mudah dioptimalkan.fi fi(x) x fi(x)
Mengingat anggapan ini, itu akan menjadi dingin jika, untuk mengoptimalkan entah bagaimana kita bisa mengocok log masa lalu Σ sehingga bisa memenuhi exp dan menghilangkan mereka. Kemudian f i bisa bermain bersama. Tetapi kita tidak bisa melakukan itu.logg(x)=log∑iexp(fi(x)) log ∑ exp fi
Mari kita lakukan hal terbaik berikutnya. Kami akan membuat fungsi lain yang mirip dengan g . Dan kami akan membuatnya dari kombinasi linear dari f i .h g fi
Katakanlah adalah tebakan untuk nilai optimal. Kami ingin meningkatkan ini. Mari kita cari fungsi lain h yang cocok dengan g dan turunannya di x 0 , yaitu g ( x 0 ) = h ( x 0 ) dan g ′ ( x 0 ) = h ′ ( x 0 ) . Jika Anda memplot grafik h di lingkungan kecil x 0 itu akan terlihat mirip dengan g .x0 h g x0 g(x0)=h(x0) g′(x0)=h′(x0) h x0 g
Anda dapat menunjukkan bahwa Kami menginginkan sesuatu yang cocok dengan ini di x 0 . Ada pilihan alami: h ( x ) = konstan + Σ i f i ( x ) exp ( f i ( x 0 ) ) .
Jadi dimulai dengan , kita membentuk h ( x ) dan mengoptimalkannya. Karena mirip dengan g ( x ) di lingkungan x 0, kami berharap optimum h mirip dengan optimum g. Setelah Anda memiliki perkiraan baru, buat h berikutnya dan ulangi lagi.x0 h(x) g(x) x0 h h
Saya harap ini memotivasi pilihan . Ini persis prosedur yang terjadi di EM.h
sumber
Seperti yang Anda katakan, saya tidak akan membahas detail teknis. Ada beberapa tutorial yang sangat bagus. Salah satu favorit saya adalah catatan kuliah Andrew Ng . Lihatlah juga referensi di sini .
Intinya tidak menggunakan fungsi monotonik tetapi fungsi cembung. Dan alasannya adalah ketidaksamaan Jensen yang memastikan bahwa estimasi algoritma EM akan meningkat pada setiap langkah.
sumber