Menerapkan Maksimalisasi Ekspektasi pada contoh lemparan koin

Saya telah mempelajari sendiri Maksimalisasi Ekspektasi belakangan ini, dan mengambil sendiri beberapa contoh sederhana dalam proses:

Dari sini : Ada tiga koin $c_0$ , $c_1$ dan $c_2$ dengan $p_0$ , $p_1$ dan $p_2$ masing-masing probabilitas untuk mendarat di Head saat dilempar. Aduk $c_0$ . Jika hasilnya adalah Head, lempar $c_1$ tiga kali, atau lempar $c_2$ tiga kali. Data yang diamati dihasilkan oleh $c_1$ dan $c_2$ adalah seperti ini: HHH, TTT, HHH, TTT, HHH. Data tersembunyi adalah hasil . Perkirakan ,p 0 p $c_0$$p_0$$p_1$ dan .$p_2$

Dan dari sini : Ada dua koin dan dengan dan menjadi probabilitas masing-masing untuk mendarat di Head saat dilempar. Setiap putaran, pilih satu koin secara acak dan lemparkan sepuluh kali; catat hasilnya. Data yang diamati adalah hasil undian yang disediakan oleh dua koin ini. Namun, kita tidak tahu koin mana yang dipilih untuk babak tertentu. Perkirakan dan .$c_A$$c_B$$p_A$$p_B$$p_A$$p_B$

Meskipun saya bisa mendapatkan perhitungan, saya tidak bisa menghubungkan cara penyelesaiannya dengan teori EM asli. Secara khusus, selama Langkah-M dari kedua contoh, saya tidak melihat bagaimana mereka memaksimalkan apa pun. Sepertinya mereka menghitung ulang parameter dan entah bagaimana, parameter baru lebih baik daripada yang lama. Selain itu, kedua E-Step bahkan tidak terlihat mirip satu sama lain, belum lagi E-Step teori asli.

Jadi, bagaimana tepatnya contoh-contoh ini bekerja?

(Jawaban ini menggunakan tautan kedua yang Anda berikan.)

$\newcommand{\Like}{\text{L}}\newcommand{\E}{\text{E}}$ Ingat definisi kemungkinan: di mana dalam kasus kami adalah penaksir untuk probabilitas bahwa koin A dan B masing-masing memiliki kepala, sebagai hasil percobaan kami, masing-masing terdiri dari 10 flips, dan menjadi koin yang digunakan dalam setiap percobaan.θ = ( θ A , θ B ) X = ( X 1 , ... , X 5 ) X i Z = ( Z 1 , ... , Z 5

$$\Like[\theta | X] = \Pr[X| \theta] = \sum_Z \Pr[X, Z | \theta]$$ $\theta = (\theta_A, \theta_B)$$X = (X_1, \dotsc, X_5)$$X_i$$Z = (Z_1, \dotsc, Z_5)$

Kami ingin menemukan penaksir kemungkinan maksimum . Algoritma Expectation-Maximization (EM) adalah salah satu metode untuk menemukan (setidaknya lokal) . Ia bekerja dengan menemukan ekspektasi bersyarat, yang kemudian digunakan untuk memaksimalkan . Idenya adalah bahwa dengan terus mencari lebih mungkin (yaitu lebih mungkin) di setiap iterasi kita akan terus meningkatkan yang pada gilirannya, meningkatkan fungsi kemungkinan. Ada tiga hal yang perlu dilakukan sebelum maju merancang algoritma berbasis EM. q qqPr[X,Z| θ$\hat{\theta}$$\hat{\theta}$$\theta$$\theta$$\Pr[X,Z|\theta]$

1. Bangun model
2. Hitung Harapan Bersyarat di bawah model (E-Step)
3. Maksimalkan kemungkinan kami dengan memperbarui perkiraan kami saat ini (Langkah-M)$\theta$

Bangun Model

Sebelum kita melangkah lebih jauh dengan EM kita perlu mencari tahu apa sebenarnya yang kita komputasi. Pada langkah-E kita menghitung persis nilai yang diharapkan untuk . Jadi, apa nilai ini? Perhatikan bahwa Alasannya adalah karena kami memiliki 5 percobaan untuk diperhitungkan, dan kami tidak tahu koin apa yang digunakan di masing-masing. Ketidaksamaan ini disebabkan olehlog Pr [ X , Z | θ $\log \Pr[X,Z|\theta]$

$$\begin{align*} \log \Pr[X,Z|\theta] &= \sum_{i=1}^5 \log\sum_{C\in \{A,B\}}\Pr[X_i, Z_i=C| \theta]\\ &=\sum_{i=1}^5 \log\sum_{C\in \{A,B\}} \Pr[Z_i=C | X_i, \theta] \cdot \frac{\Pr[X_i, Z_i=C| \theta]}{\Pr[Z_i=C | X_i, \theta]}\\ &\geq \sum_{i=1}^5 \sum_{C\in \{A,B\}} \Pr[Z_i=C | X_i, \theta] \cdot \log\frac{\Pr[X_i, Z_i=C| \theta]}{\Pr[Z_i=C | X_i, \theta]}. \end{align*}$$ $\log$menjadi cekung dan menerapkan ketimpangan Jensen. Alasan kita membutuhkan batas bawah adalah bahwa kita tidak dapat secara langsung menghitung arg max dengan persamaan aslinya. Namun kita dapat menghitungnya untuk batas bawah akhir.

Sekarang apa itu ? Ini adalah probabilitas bahwa kita melihat koin diberikan percobaan dan . Menggunakan probabilitas bersyarat yang kami miliki,C X i θ Pr [ Z i = C | X i , θ ] = Pr [ X i , Z i = C | θ $\Pr[Z_i=C|X_i,\theta]$$C$$X_i$$\theta$

$$\Pr[Z_i=C| X_i, \theta] = \frac{\Pr[X_i, Z_i = C|\theta]}{\Pr[X_i|\theta]}.$$

Meskipun kami telah membuat beberapa kemajuan, kami belum selesai dengan modelnya. Berapa probabilitas bahwa koin yang diberikan membalik urutan ? Membiarkan Sekarang adalah jelas hanya probabilitas di bawah kedua kemungkinan atau . Karena kita miliki, h i = # kepala di  X i Pr [ X i , Z i = C | θ ] = $X_i$$h_i = \#\text{heads in } X_i$ Pr[Xi| θ]Zi=AZi=BPr[Zi=A]=Pr[Zi=B]=1/

$$\Pr[X_i, Z_i = C| \theta] = \frac{1}{2} \cdot \theta_C^{h_i} (1 - \theta_C)^{10 - h_i},\ \text{ for } \ C \in \{A, B\}.$$ $\Pr[X_i|\theta]$$Z_i=A$$Z_i=B$$\Pr[Z_i = A] = \Pr[Z_i = B] = 1/2$ $$\Pr[X_i|\theta] = 1/2 \cdot (\Pr[X_i |Z_i = A, \theta] + \Pr[X_i |Z_i = B, \theta]).$$

E-Step

Oke ... itu tidak terlalu menyenangkan tetapi kita dapat mulai melakukan beberapa pekerjaan EM sekarang. Algoritma EM dimulai dengan membuat beberapa tebakan acak untuk . Dalam contoh ini kita memiliki . Kami menghitung Nilai ini sejalan dengan apa yang ada di kertas. Sekarang kita dapat menghitung jumlah kepala yang diharapkan dalam dari koin , Melakukan hal yang sama untuk koin kita dapatkan, θ 0 = ( 0,6 , 0,5 ) Pr [ Z 1 = A | X 1 , θ ] = 1 / 2 ⋅ ( 0,6 5 ⋅ 0,4 5$\theta$$\theta^0 = (0.6,0.5)$

$$\Pr[Z_1=A|X_1,\theta] = \frac{1/2 \cdot (0.6^5 \cdot 0.4^5)}{1/2 \cdot ((0.6^5 \cdot 0.4^5) + (0.5^5 \cdot 0.5^5))} \approx 0.45.$$ $X_1 = (H,T,T,T,H,H,T,H,T,H)$$A$ $$\E[\# \text{heads by coin }A | X_1, \theta] = h_1 \cdot \Pr[Z_1=A|X_1,\theta] = 5 \cdot 0.45 \approx 2.2.$$ $B$ $$\E[\# \text{heads by coin }B | X_1, \theta] = h_1 \cdot \Pr[Z_1=B|X_1,\theta] = 5 \cdot 0.55 \approx 2.8.$$ Kami dapat menghitung jumlah ekor yang sama dengan mengganti dengan . Ini berlanjut untuk semua nilai dan . Berkat linearitas ekspektasi, kita dapat mengetahui $h_1$$10 - h_1$$X_i$$h_i$ $1 \leq i \leq 5$ $$\E[\#\text{heads by coin } A|X ,\theta] = \sum_{i=1}^5 \E[\# \text{heads by coin }A | X_i, \theta]$$

M-Step

Dengan nilai yang kami perkirakan, kini hadir langkah M di mana kami ingin memaksimalkan mengingat nilai yang kami harapkan. Ini dilakukan dengan normalisasi sederhana! Demikian juga untuk . Proses ini dimulai lagi dengan E-Step dan dan berlanjut sampai nilai-nilai untuk bertemu (atau ke beberapa ambang batas yang diijinkan). Dalam contoh ini kita memiliki 10 iterasi dan . Dalam setiap iterasi, nilai meningkat, karena perkiraan yang lebih baik dari$\theta$

$$\theta_A^1 = \frac{E[\#\text{heads over } X \text{ by coin } A|X ,\theta]}{E[\#\text{heads and tails over } X \text{ by coin } A|X ,\theta]} = \frac{21.3}{21.3 + 9.6} \approx 0.71.$$ $B$$\theta^1$$\theta$$\hat{\theta} = \theta^{10} = (0.8, 0.52)$$\Pr[X,Z|\theta]$$\theta$ .

Sekarang dalam kasus ini modelnya cukup sederhana. Hal-hal dapat menjadi jauh lebih rumit dengan cukup cepat, namun algoritma EM akan selalu menyatu, dan akan selalu menghasilkan estimator kemungkinan maksimum maksimum . Mungkin merupakan penaksir lokal , tetapi untuk menyiasatinya kita bisa memulai kembali proses EM dengan inisialisasi yang berbeda. Kita dapat melakukan ini dalam jumlah yang konstan dan mempertahankan hasil terbaik (yaitu, mereka yang memiliki kemungkinan akhir tertinggi).$\hat{\theta}$