Expectation Maximization (EM) adalah sejenis metode probabilistik untuk mengklasifikasikan data. Harap perbaiki saya jika saya salah jika itu bukan pengklasifikasi.
Apa penjelasan intuitif dari teknik EM ini? Apa yang ada di expectation
sini dan apakah makhluk itu maximized
?
machine-learning
cluster-analysis
data-mining
mathematical-optimization
expectation-maximization
Pria London
sumber
sumber
Jawaban:
Catatan: kode di balik jawaban ini dapat ditemukan di sini .
Misalkan kita memiliki beberapa data yang diambil sampelnya dari dua kelompok yang berbeda, merah dan biru:
Di sini, kita bisa melihat titik data mana yang termasuk dalam grup merah atau biru. Ini memudahkan untuk menemukan parameter yang menjadi ciri setiap grup. Misalnya, rata-rata dari grup merah adalah sekitar 3, rata-rata grup biru adalah sekitar 7 (dan kita dapat menemukan cara yang tepat jika kita mau).
Ini, secara umum, dikenal sebagai estimasi kemungkinan maksimum . Dengan adanya beberapa data, kami menghitung nilai parameter (atau parameter) yang paling menjelaskan data tersebut.
Sekarang bayangkan bahwa kita tidak dapat melihat nilai mana yang diambil sampelnya dari kelompok mana. Semuanya tampak ungu bagi kami:
Di sini kita memiliki pengetahuan bahwa ada dua kelompok nilai, tetapi kita tidak tahu kelompok mana nilai tertentu itu termasuk.
Masih dapatkah kita memperkirakan sarana untuk kelompok merah dan biru yang paling sesuai dengan data ini?
Ya, seringkali kita bisa! Maksimalisasi Harapan memberi kita cara untuk melakukannya. Ide yang sangat umum di balik algoritme adalah ini:
Langkah-langkah ini memerlukan penjelasan lebih lanjut, jadi saya akan membahas masalah yang dijelaskan di atas.
Contoh: memperkirakan mean dan deviasi standar
Saya akan menggunakan Python dalam contoh ini, tetapi kodenya harus cukup mudah dipahami jika Anda tidak terbiasa dengan bahasa ini.
Misalkan kita memiliki dua kelompok, merah dan biru, dengan nilai yang didistribusikan seperti pada gambar di atas. Secara spesifik, setiap grup berisi nilai yang diambil dari distribusi normal dengan parameter berikut:
Berikut adalah gambar grup merah dan biru ini lagi (untuk menyelamatkan Anda dari keharusan menggulir ke atas):
Ketika kita dapat melihat warna dari setiap titik (yaitu kelompok mana tempat itu berada), sangat mudah untuk memperkirakan mean dan deviasi standar untuk setiap kelompok. Kami hanya meneruskan nilai merah dan biru ke fungsi bawaan di NumPy. Sebagai contoh:
Tetapi bagaimana jika kita tidak dapat melihat warna dari titik-titik tersebut? Artinya, alih-alih merah atau biru, setiap titik telah diwarnai ungu.
Untuk mencoba dan memulihkan parameter mean dan deviasi standar untuk grup merah dan biru, kita dapat menggunakan Expectation Maximization.
Langkah pertama kita ( langkah 1 di atas) adalah menebak nilai parameter untuk mean dan deviasi standar setiap grup. Kami tidak harus menebak dengan cerdas; kami dapat memilih nomor yang kami suka:
Estimasi parameter ini menghasilkan kurva lonceng yang terlihat seperti ini:
Ini adalah perkiraan yang buruk. Kedua cara (garis putus-putus vertikal) terlihat jauh dari "tengah" apapun untuk kelompok titik yang masuk akal, misalnya. Kami ingin meningkatkan perkiraan ini.
Langkah selanjutnya ( langkah 2 ) adalah menghitung kemungkinan setiap titik data muncul di bawah tebakan parameter saat ini:
Di sini, kami hanya menempatkan setiap titik data ke dalam fungsi kepadatan probabilitas untuk distribusi normal menggunakan tebakan kami saat ini pada mean dan deviasi standar untuk merah dan biru. Ini memberitahu kita, misalnya, bahwa dengan dugaan kami saat ini titik data pada 1,761 adalah jauh lebih mungkin merah (0,189) dari biru (0,00003).
Untuk setiap titik data, kita dapat mengubah dua nilai kemungkinan ini menjadi bobot ( langkah 3 ) sehingga dijumlahkan menjadi 1 sebagai berikut:
Dengan perkiraan kami saat ini dan bobot yang baru kami hitung, kami sekarang dapat menghitung perkiraan baru untuk mean dan deviasi standar dari grup merah dan biru ( langkah 4 ).
Kami dua kali menghitung mean dan deviasi standar menggunakan semua titik data, tetapi dengan bobot yang berbeda: sekali untuk bobot merah dan satu kali untuk bobot biru.
Bagian penting dari intuisi adalah semakin besar bobot warna pada titik data, semakin banyak titik data yang memengaruhi perkiraan selanjutnya untuk parameter warna tersebut. Ini memiliki efek "menarik" parameter ke arah yang benar.
Kami memiliki perkiraan baru untuk parameter. Untuk memperbaikinya lagi, kita dapat melompat kembali ke langkah 2 dan mengulangi prosesnya. Kami melakukan ini hingga perkiraan bertemu, atau setelah beberapa iterasi dilakukan ( langkah 5 ).
Untuk data kami, lima iterasi pertama dari proses ini terlihat seperti ini (iterasi terbaru memiliki tampilan yang lebih kuat):
Kami melihat bahwa rata-rata sudah menyatu pada beberapa nilai, dan bentuk kurva (diatur oleh deviasi standar) juga menjadi lebih stabil.
Jika kami melanjutkan untuk 20 iterasi, kami berakhir dengan yang berikut:
Proses EM telah menyatu ke nilai-nilai berikut, yang ternyata sangat dekat dengan nilai sebenarnya (di mana kita dapat melihat warna - tidak ada variabel tersembunyi):
Dalam kode di atas, Anda mungkin telah memperhatikan bahwa estimasi baru untuk deviasi standar dihitung menggunakan estimasi mean dari iterasi sebelumnya. Pada akhirnya, tidak masalah jika kita menghitung nilai baru untuk mean terlebih dahulu karena kita hanya mencari varian nilai (tertimbang) di sekitar titik pusat. Kami masih akan melihat estimasi untuk parameter yang bertemu.
sumber
EM adalah algoritme untuk memaksimalkan fungsi kemungkinan ketika beberapa variabel dalam model Anda tidak teramati (yaitu ketika Anda memiliki variabel laten).
Anda mungkin cukup bertanya, jika kita hanya mencoba memaksimalkan suatu fungsi, mengapa kita tidak menggunakan mesin yang ada untuk memaksimalkan suatu fungsi. Nah, jika Anda mencoba memaksimalkan ini dengan mengambil turunan dan menyetelnya ke nol, Anda menemukan bahwa dalam banyak kasus kondisi orde pertama tidak memiliki solusi. Ada masalah ayam-dan-telur yang untuk memecahkan parameter model Anda, Anda perlu mengetahui distribusi data Anda yang belum teramati; tetapi distribusi data Anda yang tidak teramati adalah fungsi dari parameter model Anda.
EM mencoba untuk menyiasatinya dengan menebak secara berulang distribusi untuk data yang tidak teramati, kemudian memperkirakan parameter model dengan memaksimalkan sesuatu yang merupakan batas bawah pada fungsi kemungkinan aktual, dan mengulangi hingga konvergensi:
Algoritme EM
Mulailah dengan menebak nilai parameter model Anda
Langkah-E: Untuk setiap titik data yang memiliki nilai yang hilang, gunakan persamaan model Anda untuk menyelesaikan distribusi data yang hilang berdasarkan tebakan Anda saat ini dari parameter model dan memberikan data yang diamati (perhatikan bahwa Anda sedang menyelesaikan distribusi untuk setiap yang hilang nilai, bukan untuk nilai yang diharapkan). Sekarang kita memiliki distribusi untuk setiap nilai yang hilang, kita dapat menghitung ekspektasi fungsi kemungkinan sehubungan dengan variabel yang tidak teramati. Jika tebakan kami untuk parameter model benar, kemungkinan yang diharapkan ini akan menjadi kemungkinan aktual dari data yang kami observasi; jika parameternya tidak benar, itu hanya akan menjadi batas bawah.
M-step: Sekarang kita memiliki fungsi kemungkinan yang diharapkan tanpa variabel yang tidak teramati di dalamnya, maksimalkan fungsi seperti yang Anda lakukan dalam kasus yang diamati sepenuhnya, untuk mendapatkan perkiraan baru dari parameter model Anda.
Ulangi sampai konvergensi.
sumber
Berikut adalah resep langsung untuk memahami algoritme Maksimalisasi Ekspektasi:
1- Baca makalah tutorial EM ini oleh Do dan Batzoglou.
2- Anda mungkin memiliki tanda tanya di kepala Anda, lihat penjelasan di halaman pertukaran tumpukan matematika ini .
3- Lihat kode ini yang saya tulis dengan Python yang menjelaskan contoh di kertas tutorial EM item 1:
Peringatan: Kode mungkin berantakan / suboptimal, karena saya bukan pengembang Python. Tapi itu berhasil.
sumber
Secara teknis istilah "EM" agak kurang ditentukan, tapi saya asumsikan Anda mengacu pada teknik analisis cluster Gaussian Mixture Modeling, yang merupakan contoh dari prinsip EM umum.
Sebenarnya, analisis cluster EM bukanlah pengklasifikasi . Saya tahu bahwa beberapa orang menganggap pengelompokan sebagai "klasifikasi tanpa pengawasan", tetapi sebenarnya analisis kluster adalah sesuatu yang sangat berbeda.
Perbedaan utama, dan klasifikasi kesalahpahaman besar yang selalu dimiliki orang dengan analisis cluster adalah bahwa: dalam analisis cluster, tidak ada "solusi yang benar" . Ini adalah metode penemuan pengetahuan , sebenarnya dimaksudkan untuk menemukan sesuatu yang baru ! Ini membuat evaluasi menjadi sangat rumit. Ini sering dievaluasi menggunakan klasifikasi yang dikenal sebagai referensi, tetapi itu tidak selalu sesuai: klasifikasi yang Anda miliki mungkin atau mungkin tidak mencerminkan apa yang ada dalam data.
Izinkan saya memberi contoh: Anda memiliki kumpulan data pelanggan yang besar, termasuk data jenis kelamin. Metode yang membagi kumpulan data ini menjadi "pria" dan "wanita" adalah optimal jika Anda membandingkannya dengan kelas yang ada. Dalam cara berpikir "prediksi", ini bagus, karena untuk pengguna baru Anda sekarang dapat memprediksi jenis kelamin mereka. Dalam cara berpikir "penemuan pengetahuan", ini sebenarnya buruk, karena Anda ingin menemukan beberapa struktur baru dalam data. Sebuah metode yang misalnya akan membagi data menjadi orang tua dan anak-anak, namun akan mendapatkan skor yang lebih buruk dibandingkan dengan kelas pria / wanita. Namun, itu akan menjadi hasil pengelompokan yang sangat baik (jika usia tidak diberikan).
Sekarang kembali ke EM. Pada dasarnya ini mengasumsikan bahwa data Anda terdiri dari beberapa distribusi normal multivariasi (perhatikan bahwa ini adalah asumsi yang sangat kuat, khususnya saat Anda memperbaiki jumlah cluster!). Kemudian mencoba menemukan model optimal lokal untuk ini dengan secara bergantian meningkatkan model dan penugasan objek ke model .
Untuk hasil terbaik dalam konteks klasifikasi, pilih jumlah cluster yang lebih besar dari jumlah kelas, atau bahkan terapkan pengelompokan ke kelas tunggal saja (untuk mengetahui apakah ada beberapa struktur di dalam kelas!).
Misalnya Anda ingin melatih pengklasifikasi untuk membedakan "mobil", "sepeda", dan "truk". Ada sedikit gunanya mengasumsikan data terdiri dari tepat 3 distribusi normal. Namun, Anda mungkin berasumsi bahwa ada lebih dari satu jenis mobil (dan truk serta sepeda). Jadi, alih-alih melatih pengklasifikasi untuk ketiga kelas ini, Anda mengelompokkan mobil, truk, dan sepeda menjadi 10 kelompok (atau mungkin 10 mobil, 3 truk, dan 3 sepeda, apa pun), lalu melatih pengklasifikasi untuk membedakan 30 kelas ini, lalu menggabungkan hasil kelas kembali ke kelas aslinya. Anda mungkin juga menemukan bahwa ada satu cluster yang sangat sulit untuk diklasifikasikan, misalnya Trikes. Mereka agak mobil, dan agak sepeda. Atau truk pengiriman, yang lebih mirip mobil besar daripada truk.
sumber
Jawaban lain yang bagus, saya akan mencoba memberikan perspektif lain dan menangani bagian intuitif dari pertanyaan itu.
Algoritma EM (Expectation-Maximization) adalah varian dari kelas algoritma iteratif yang menggunakan dualitas
Kutipan (penekanan saya):
Biasanya dual B dari sebuah objek A terkait dengan A dalam beberapa cara yang menjaga kesimetrisan atau kompatibilitas . Misalnya AB = const
Contoh algoritme iteratif yang menggunakan dualitas (dalam pengertian sebelumnya) adalah:
Dengan cara yang sama, algoritma EM juga dapat dilihat sebagai dua langkah maksimalisasi ganda :
Dalam algoritma iteratif menggunakan dualitas ada asumsi eksplisit (atau implisit) dari titik ekuilibrium (atau tetap) konvergensi (untuk EM ini dibuktikan dengan menggunakan pertidaksamaan Jensen)
Jadi garis besar dari algoritma tersebut adalah:
Catatan bahwa ketika seperti algoritma konvergen ke optimum (global), telah menemukan konfigurasi yang terbaik di kedua indra (yaitu di kedua x domain / parameter dan y domain / parameter). Namun algoritme hanya dapat menemukan optimal lokal dan bukan optimal global .
saya akan mengatakan ini adalah deskripsi intuitif dari garis besar algoritma
Untuk argumentasi dan penerapan statistik, jawaban lain telah memberikan penjelasan yang baik (periksa juga referensi dalam jawaban ini)
sumber
Jawaban yang diterima merujuk pada Makalah Chuong EM , yang menjelaskan EM dengan baik. Ada juga video youtube yang menjelaskan makalah tersebut lebih detail.
Singkatnya, berikut adalah skenarionya:
Dalam kasus pertanyaan percobaan pertama, secara intuitif kami akan berpikir B menghasilkannya karena proporsi kepala cocok dengan bias B dengan sangat baik ... tetapi nilai itu hanya tebakan, jadi kami tidak dapat memastikan.
Dengan pemikiran tersebut, saya suka memikirkan solusi EM seperti ini:
Ini mungkin penyederhanaan yang berlebihan (atau bahkan secara fundamental salah pada beberapa level), tapi saya harap ini membantu pada level intuitif!
sumber
EM digunakan untuk memaksimalkan kemungkinan model Q dengan variabel laten Z.
Ini adalah pengoptimalan berulang.
e-step: berdasarkan estimasi saat ini dari Z menghitung fungsi loglikelihood yang diharapkan
m-step: temukan theta yang memaksimalkan Q ini
Contoh GMM:
e-step: estimasi penugasan label untuk setiap titik data dengan mempertimbangkan estimasi parameter gmm saat ini
m-step: memaksimalkan theta baru dengan tugas label baru
K-means juga merupakan algoritme EM dan ada banyak animasi penjelasan di K-means.
sumber
Menggunakan artikel yang sama oleh Do dan Batzoglou yang dikutip dalam jawaban Zhubarb, saya menerapkan EM untuk masalah itu di Java . Komentar untuk jawabannya menunjukkan bahwa algoritme macet di optimal lokal, yang juga terjadi dengan implementasi saya jika parameter thetaA dan thetaB sama.
Di bawah ini adalah keluaran standar dari kode saya, menunjukkan konvergensi parameter.
Di bawah ini adalah implementasi EM Java saya untuk memecahkan masalah di (Do dan Batzoglou, 2008). Bagian inti dari implementasi adalah loop untuk menjalankan EM hingga parameter bertemu.
Di bawah ini adalah seluruh kode.
sumber