Algoritma EM
- Diperkenalkan oleh
- Dempster, Laird & Rubin
- Tahun
- 1977
- Jenis
- Iterative optimization algorithm
- Keluarga
- Estimation
Teks ini adalah terjemahan mesin dan belum ditinjau. Baca versi asli dalam bahasa Inggris
Apa fungsinya?
Algoritma Ekspektasi-Maksimalisasi (EM) adalah prosedur optimasi iteratif untuk menemukan estimasi kemungkinan maksimum atau kemungkinan aposteriori maksimum dari parameter dalam model statistik dengan variabel laten atau data yang hilang.
Diperkenalkan oleh Dempster, Laird, dan Rubin dalam makalah penting mereka tahun 1977, EM bergantian antara menghitung log-kemungkinan data lengkap yang diharapkan (langkah-E) dan memaksimalkannya terhadap parameter (langkah-M), menjamin kemungkinan non-menurun monoton pada setiap iterasi.
Intuisi di balik metode
Bayangkan mencoba mempelajari aturan permainan dengan mengamati pemain yang kartunya tidak dapat Anda lihat. Di setiap putaran, Anda menebak kartu apa yang kemungkinan mereka pegang berdasarkan apa yang Anda amati, lalu memperbarui model Anda tentang aturan dengan asumsi tebakan tersebut benar. EM melakukan hal ini: langkah-E mengisi informasi yang hilang secara probabilistik menggunakan estimasi parameter saat ini, dan langkah-M menyesuaikan kembali model seolah-olah nilai-nilai yang diisi tersebut adalah observasi nyata.
Sejarah
Algoritma ini secara formal disatukan dan dinamai oleh Arthur Dempster, Nan Laird, dan Donald Rubin dalam makalah JRSS-B mereka tahun 1977, yang tetap menjadi salah satu artikel statistik yang paling banyak dikutip yang pernah diterbitkan. Makalah tersebut menggeneralisasi prosedur kasus khusus sebelumnya yang dikembangkan secara independen untuk masalah data hilang tertentu. Dekade berikutnya menghasilkan banyak ekstensi termasuk algoritma ECM, ECME, AECM, dan SEM, memperluas penerapan dan mempercepat konvergensi dalam banyak pengaturan praktis.
Kapan digunakan
Gunakan algoritma EM ketika data mengandung nilai yang hilang, keadaan tersembunyi, atau variabel laten dan Anda memerlukan estimasi kemungkinan maksimum. Algoritma ini sangat cocok untuk model campuran Gaussian, model Markov tersembunyi, analisis faktor, dan imputasi data yang hilang. Asumsi utama meliputi bahwa data yang hilang adalah hilang secara acak (MAR) dan model data lengkap dapat ditangani. Keterbatasan meliputi sensitivitas terhadap inisialisasi, kemungkinan konvergensi ke maksimum lokal, dan konvergensi yang lambat di dekat titik pelana. Alternatifnya meliputi optimasi berbasis gradien dengan integrasi numerik, inferensi variasi, atau metode MCMC.
Batasan dan pertimbangan
- Konvergensi ke maksimum lokal daripada maksimum global ketika permukaan kemungkinan bersifat multimodal
- Dapat menunjukkan konvergensi yang sangat lambat (linear) ketika fraksi informasi yang hilang besar
- Memerlukan analis untuk menentukan model data lengkap dan distribusi variabel laten
- EM standar tidak secara langsung menyediakan matriks kovariansi data teramati dari estimasi; langkah tambahan (misalnya, metode Louis atau algoritma SEM) diperlukan untuk kesalahan standar
Syarat dari sumber tidak menggantikan tinjauan ilmiah independen atau validasi oleh mesin analisis.
Kelebihan
- Peningkatan monoton yang terjamin dalam kemungkinan data teramati pada setiap iterasi, memastikan konvergensi yang stabil
- Mengubah masalah data yang hilang yang sulit menjadi serangkaian optimasi data lengkap yang dapat ditangani
- Dapat diterapkan secara luas di seluruh model keluarga eksponensial, model campuran, dan kerangka kerja variabel laten
- Pembaruan langkah-M bentuk tertutup tersedia untuk banyak model standar, membuat implementasi efisien
Penerapan
- Penyesuaian model campuran Gaussian untuk pengelompokan dan estimasi kepadatan
- Pelatihan model Markov tersembunyi untuk pengenalan ucapan dan analisis urutan biologis
- Imputasi ganda dan analisis data hilang dalam penelitian klinis dan ilmu sosial
- Estimasi parameter dalam analisis faktor dan analisis kelas laten
- Segmentasi dan rekonstruksi gambar dalam pencitraan medis
Cara kerjanya
Cara kerjanya
Sebelum iterasi dimulai, analis memilih nilai awal untuk parameter yang tidak diketahui, yang dilambangkan dengan theta-0. Nilai-nilai ini dapat dipilih secara acak, dari penyesuaian yang disederhanakan, atau berdasarkan pengetahuan domain. Kualitas inisialisasi dapat memengaruhi maksimum lokal tempat algoritma konvergen, menjadikan beberapa pengulangan acak sebagai praktik umum.
Rumus
\text{Choose initial parameter estimates } \theta^{(0)}Diberikan estimasi parameter saat ini theta-t, langkah-E menghitung Q, nilai harapan dari log-kemungkinan data lengkap atas distribusi variabel laten yang tidak teramati Z, dikondisikan pada data yang teramati X. Ekspektasi ini secara efektif menggantikan kuantitas yang tidak diketahui dengan estimasi probabilistiknya tanpa berkomitmen pada satu nilai imputasi tunggal.
Rumus
Q(\theta \mid \theta^{(t)}) = \mathbb{E}_{Z \mid X, \theta^{(t)}}[\log p(X, Z \mid \theta)]Langkah-M memaksimalkan fungsi Q dari langkah-E terhadap theta, menghasilkan estimasi yang diperbarui theta-(t+1). Karena log-kemungkinan data lengkap seringkali lebih mudah dimaksimalkan daripada log-kemungkinan data teramati marjinal, langkah ini seringkali dapat ditangani bahkan ketika kemungkinan maksimum langsung tidak dapat ditangani.
Rumus
\theta^{(t+1)} = \arg\max_{\theta} \, Q(\theta \mid \theta^{(t)})Langkah-E dan langkah-M diulang secara bergantian. Setelah setiap siklus penuh, log-kemungkinan data teramati dievaluasi. Iterasi berhenti ketika perubahan dalam log-kemungkinan (atau dalam vektor parameter) turun di bawah toleransi epsilon yang ditentukan pengguna. Dempster dkk. membuktikan bahwa setiap siklus tidak dapat menurunkan kemungkinan data teramati, memastikan konvergensi yang stabil.
Rumus
\text{Repeat E- and M-steps until } |\ell(\theta^{(t+1)}) - \ell(\theta^{(t)})| < \epsilonKesalahan umum
- Menggunakan satu inisialisasi acak berisiko berakhir pada maksimum lokal yang buruk; selalu jalankan beberapa pengulangan dan pilih solusi dengan log-kemungkinan akhir tertinggi
- Menyatakan konvergensi terlalu dini dengan hanya memantau perubahan parameter daripada log-kemungkinan data teramati dapat menghasilkan estimasi yang tidak akurat
- Menerapkan EM ketika data Hilang Tidak Secara Acak (MNAR) tanpa penyesuaian model dapat menimbulkan bias sistematis dalam estimasi
- Mengabaikan masalah perpindahan label dalam model campuran menghasilkan penugasan komponen yang tidak dapat diinterpretasikan bahkan setelah konvergensi yang benar
Pertanyaan yang sering diajukan
Apakah algoritma EM selalu konvergen ke maksimum global?
Tidak. EM dijamin hanya menemukan maksimum lokal (atau titik pelana) dari kemungkinan data teramati. Ketika permukaan kemungkinan memiliki banyak mode, solusi akhir bergantung pada inisialisasi. Menjalankan algoritma dari beberapa titik awal yang berbeda dan mempertahankan solusi dengan log-kemungkinan tertinggi adalah obat praktis standar.
Bagaimana EM berbeda dari optimasi kemungkinan maksimum langsung?
MLE langsung memaksimalkan log-kemungkinan data teramati, yang mungkin melibatkan integral yang tidak dapat ditangani atas variabel laten. EM menghindarinya dengan secara iteratif memaksimalkan log-kemungkinan data lengkap yang diharapkan, yang seringkali dapat ditangani secara analitis. Imbalannya adalah EM mungkin konvergen secara lambat, sedangkan metode berbasis gradien bisa lebih cepat ketika gradien dari kemungkinan marjinal tersedia.
Kapan saya harus memilih imputasi MICE daripada algoritma EM?
MICE (Multiple Imputation by Chained Equations) lebih disukai ketika data mencakup variabel dengan tipe campuran, hubungan non-linear, atau struktur interaksi kompleks yang sulit dikodekan dalam satu model data lengkap parametrik. EM lebih alami ketika model gabungan yang terdefinisi dengan baik untuk semua variabel ada dan inferensi menargetkan parameter model daripada kumpulan data yang diimputasi.
Metode terkait
Sumber
Dempster, A. P., Laird, N. M., & Rubin, D. B. (1977). Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society: Series B, 39(1), 1–38.
Buka referensi DOIDisalin.