Apa itu Algoritma EM dalam Pembelajaran Mesin? [Dijelaskan dengan Contoh]

Algoritma EM atau algoritma Expectation-Maximization adalah model variabel laten yang diusulkan oleh Arthur Dempster, Nan Laird, dan Donald Rubin pada tahun 1977.

Model variabel laten terdiri dari variabel yang dapat diamati dan variabel yang tidak dapat diamati. Variabel yang diamati adalah variabel yang dapat diukur sedangkan variabel yang tidak teramati (laten/tersembunyi) disimpulkan dari variabel yang diamati.

Seperti yang dijelaskan oleh ketiganya, algoritma EM dapat digunakan untuk menentukan parameter kemungkinan maksimum lokal (MLE) atau parameter maksimum a posteriori (MAP) untuk variabel laten (variabel yang tidak dapat diamati yang perlu disimpulkan dari variabel yang dapat diamati) dalam model statistik. Ini digunakan untuk memprediksi nilai-nilai ini atau menentukan data yang hilang atau tidak lengkap, asalkan Anda mengetahui bentuk umum distribusi probabilitas yang terkait dengan variabel laten ini.

Sederhananya, prinsip umum di balik algoritme EM dalam pembelajaran mesin melibatkan penggunaan instance variabel laten yang dapat diamati untuk memprediksi nilai dalam instance yang tidak dapat diamati untuk pembelajaran. Hal ini dilakukan sampai konvergensi nilai terjadi.

Algoritme adalah alat yang cukup kuat dalam pembelajaran mesin dan merupakan kombinasi dari banyak algoritme yang tidak diawasi. Ini termasuk algoritma pengelompokan k-means, di antara varian algoritma EM lainnya.

Bergabunglah dengan Kursus Pembelajaran Mesin online dari Universitas top dunia – Magister, Program Pascasarjana Eksekutif, dan Program Sertifikat Tingkat Lanjut di ML & AI untuk mempercepat karier Anda.

Algoritma Ekspektasi-Maximisasi

Mari kita telusuri mekanisme algoritma Ekspektasi-Maximization di Machine Learning:

Sumber

• Langkah 1: Kami memiliki satu set data yang hilang atau tidak lengkap dan set parameter awal lainnya. Kami berasumsi bahwa data yang diamati atau nilai awal parameter dihasilkan dari model tertentu.
• Langkah 2: Berdasarkan nilai yang dapat diamati dalam contoh yang dapat diamati dari data yang tersedia, kami akan memprediksi atau memperkirakan nilai dalam contoh yang tidak dapat diamati dari data atau data yang hilang. Ini dikenal sebagai langkah Harapan (E – langkah).
• Langkah 3: Menggunakan data yang dihasilkan dari langkah E, kami akan memperbarui parameter dan melengkapi kumpulan data. Ini dikenal sebagai langkah Maksimalisasi (M – langkah) yang digunakan untuk memperbarui hipotesis.

Langkah 2 dan langkah 3 diulang sampai konvergen. Artinya jika nilainya tidak konvergen, kita akan mengulangi langkah E – langkah dan M – langkah.

.

Sumber

Kelebihan dan Kekurangan Algoritma EM

Aplikasi Algoritma EM

Model variabel laten memiliki banyak aplikasi dunia nyata dalam pembelajaran mesin.

1. Ini digunakan dalam pengelompokan data dan analisis psikometri tanpa pengawasan.
2. Ini juga digunakan untuk menghitung kerapatan Gaussian suatu fungsi.
3. Algoritme EM banyak digunakan dalam memprediksi parameter Hidden Markov Model (HMM) dan model campuran lainnya.
4. Algoritma EM banyak digunakan dalam pemrosesan bahasa alami (NLP), visi komputer, dan genetika kuantitatif.
5. Aplikasi penting lainnya dari algoritma EM termasuk rekonstruksi gambar di bidang kedokteran dan rekayasa struktural.

Mari kita pahami algoritma EM menggunakan Model Campuran Gaussian.

Algoritma EM Untuk Model Campuran Gaussian

Untuk mengestimasi parameter dari Model Campuran Gaussian, kita memerlukan beberapa variabel yang diamati yang dihasilkan oleh dua proses terpisah yang distribusi probabilitasnya diketahui. Namun, titik data dari kedua proses digabungkan dan kami tidak tahu distribusi mana yang mereka miliki.

Kami bertujuan untuk memperkirakan parameter distribusi ini menggunakan estimasi Kemungkinan Maksimum dari algoritma EM seperti yang dijelaskan di atas.

Berikut adalah kode yang akan kita gunakan:

# Diberikan fungsi yang harus kita hitung kepadatannya

# Gaussian pada titik x_i diberikan mu, sigma: G(x_i, mu, sigma); dan

# fungsi lain untuk menghitung kemungkinan log: L(x, mu, sigma, pi)

def estimasi_gmm(x, K, tol=0,001, max_iter=100):

”' Perkirakan parameter GMM.

:param x: daftar variabel bernilai nyata yang diamati

:param K: bilangan bulat untuk jumlah Gaussian

:param tol: perubahan yang ditoleransi untuk kemungkinan log

:kembali: parameter mu, sigma, pi

”'

#0. Inisialisasi theta = (mu, sigma, pi)

N = len(x)

mu, sigma = [rand()] * K, [rand()] * K

pi = [rand()] * K

curr_L = np.inf

untuk j dalam rentang (max_iter):

sebelumnya_L = curr_L

# 1. E-langkah: tanggung jawab = p(z_i = k | x_i, theta^(t-1))

r = {}

untuk saya dalam rentang (N):

bagian = [pi[k] * G(x_i, mu[k], sigma[k]) untuk i dalam rentang(K)]

jumlah = jumlah (bagian)

untuk saya di k:

r[(i, k)] = bagian[k] / total

# 2. Langkah-M: Perbarui nilai mu, sigma, pi

rk = [jumlah([r[(i, k)] untuk i dalam rentang(N)]) untuk k dalam rentang(K)]

untuk k dalam rentang (K):

pi[k] = rk[k] / N

mu[k] = jumlah(r[(i, k)] * x[i] untuk i dalam rentang(N)) / rk[k]

sigma[k] = jumlah(r[(i, k)] * (x[i] – mu[k]) ** 2) / rk[k]

# 3. Periksa kondisi keluar

curr_L = L(x, mu, sigma, pi)

if abs(prev_L – curr_L) < tol:

merusak

kembali mu, sigma, pi

Dalam E-Step, kita dapat menggunakan teorema Bayes untuk menentukan nilai yang diharapkan dari titik data yang diberikan yang diambil dari iterasi algoritma sebelumnya. Dalam M-Step, kami berasumsi bahwa nilai variabel laten ditetapkan untuk memperkirakan proxy dalam instance yang tidak teramati menggunakan Kemungkinan Maksimum. Akhirnya, kami menggunakan rumus mean standar dan standar deviasi untuk memperkirakan parameter model campuran gaussian.

Kesimpulan

Ini membawa kita ke akhir artikel. Untuk informasi lebih lanjut tentang konsep Pembelajaran Mesin, hubungi fakultas top IIIT Bangalore dan Liverpool John Moores University melalui program Master of Science dalam Pembelajaran Mesin & AI upGrad .

Ini adalah kursus 18 bulan yang menawarkan 450+ jam konten pembelajaran, 12+ proyek industri, 10 opsi proyek Capstone, dan 10+ tugas pengkodean. Anda juga menikmati bimbingan pribadi dari pakar industri, dan konseling bimbingan karir melalui sesi langsung. Batch berikutnya dimulai pada 28 Februari 2021!