Mengapa ada E dalam algoritma nama EM?

Saya mengerti di mana langkah E terjadi dalam algoritma (seperti yang dijelaskan dalam bagian matematika di bawah). Dalam pikiran saya, kecerdikan kunci dari algoritma adalah penggunaan ketidaksetaraan Jensen untuk membuat batas bawah pada kemungkinan log. Dalam hal itu, mengambil Expectationhanya dilakukan untuk merumuskan kembali kemungkinan log agar sesuai dengan ketidaksetaraan Jensen (yaitu untuk fungsi cekung.) $E(f(x)) < f(E(x))$

Apakah ada alasan mengapa E-step disebut? Apakah ada signifikansi pada hal yang kita harapkan (yaitu ? Saya merasa seperti kehilangan intuisi di balik mengapa Ekspektasi itu begitu sentral, daripada sekadar bersifat insidental terhadap penggunaan ketidaksetaraan Jensen. $p(x_i, z_i| \theta)$

EDIT: Tutorial mengatakan:

Nama 'E-step' berasal dari fakta bahwa seseorang biasanya tidak perlu untuk membentuk distribusi probabilitas atas penyelesaian secara eksplisit, tetapi lebih perlu hanya menghitung statistik yang cukup 'diharapkan' atas penyelesaian ini.

Apa artinya "seseorang biasanya tidak perlu membentuk distribusi probabilitas atas penyelesaian secara eksplisit"? Seperti apa distribusi probabilitas itu?

Lampiran: E-langkah dalam algoritma EM

\begin{aligned} l l & = \sum_{i} \log p (x_{i}; θ) & definition of log likelihood \\ = \sum_{i} \log \sum_{z_{i}} p (x_{i}, z_{i}; θ) & augment with latent variables z \\ = \sum_{i} \log \sum_{z_{i}} Q_{i} (z_{i}) \frac{p (x_{i}, z_{i}; θ)}{Q_{i} (z_{i})} & Q_{i} is a distribution for z_{i} \\ = \sum_{i} \log E_{z_{i}} [\frac{p (x_{i}, z_{i}; θ)}{Q_{i} (z_{i})}] & taking expectations - hence the E in EM \\ \geq \sum E_{z_{i}} [\log \frac{p (x_{i}, z_{i}; θ)}{Q_{i} (z_{i})}] & Using Jensen's rule for \log which is concave \\ \geq \sum_{i} \sum_{z_{i}} Q_{i} (z_{i}) \log \frac{p (x_{i}, z_{i}; θ)}{Q_{i} (z_{i})} & Q function to maximize \end{aligned}

$\begin{align} ll &= \sum_i{\log p(x_i; \theta)} && \text{definition of log likelihood} \\ &= \sum_i \log \sum_{z_i}{p(x_i, z_i; \theta)} && \text{augment with latent variables $z$} \\ &= \sum_i \log \sum_{z_i} Q_i(z_i) \frac{p(x_i, z_i; \theta)}{Q_i(z_i)} && \text{$Q_i$ is a distribution for $z_i$} \\ &= \sum_i \log E_{z_i}[\frac{p(x_i, z_i; \theta)}{Q_i(z_i)}] && \text{taking expectations - hence the E in EM} \\ &\geq \sum E_{z_i}[\log \frac{p(x_i, z_i; \theta)}{Q_i(z_i)}] && \text{Using Jensen's rule for $\log$ which is concave} \\ &\geq \sum_i \sum_{z_i} Q_i(z_i) \log \frac{p(x_i, z_i; \theta)}{Q_i(z_i)} && \text{Q function to maximize} \end{align}$

maximum-likelihood optimization expectation-maximization latent-variable kullback-leibler Heisenberg
sumber

Tidak jelas bagi saya apa yang Anda tanyakan, tetapi saya selalu berasumsi bahwa relevansi di balik penamaan E-step adalah, dalam beberapa hal, Anda "mengisi" atau "menusuk" hilang dengan mengambil harapan. Memang, ini tidak persis apa yang sedang terjadi karena Anda mengambil yang tidak sama dengan memasukkan sesuatu untuk kehilangan nilai-nilai , tetapi secara operasional sering berakhir dengan melakukan sesuatu seperti itu. Jika kami melakukan augmentasi data - yang mirip dengan EM dalam banyak hal.

z

$z$

E_{θ} [\log p (x, Z; θ^{'}) ∣ X = x]

$E_\theta [\log p(x, Z; \theta') \mid X = x]$

Z

$Z$

cowok

Ya ini jenis diskusi yang saya inginkan. Jadi, ketika Anda mengatakan menyalahkan z dengan mengambil harapan ". Harapan tentang apa? Juga, maksud Anda alih-alih ?

E_{z}

$E_z$

E_{θ}

$E_\theta$

Heisenberg

Asuhan saya selalu mengindeks dengan parameter mengindeks ukuran probabilitas bahwa harapan sedang diambil sehubungan dengan. Di CS mereka melakukannya seperti yang Anda sarankan. Saya mengintegrasikan , mengkondisikan pada terhadap ukuran yang diindeks oleh .

E

$E$

Z

$Z$

X

$X$

θ

$\theta$

cowok

Sebagai contoh, saat memasang campuran Gaussian, langkah-E menghubungkan indikator kelas yang hilang. Tetapi ia melakukannya dengan cara yang tidak jelas dengan menghitung tanggung jawab untuk setiap pengamatan.

cowok

Jawaban:

Harapan adalah inti dari algoritma EM. Untuk memulainya, kemungkinan terkait dengan data $(x_1,\ldots,x_n)$ direpresentasikan sebagai harapan

\begin{aligned} p (x_{1}, \dots, x_{n}; θ) & = \int_{Z^{n}} p (x_{1}, \dots, x_{n}, z_{1}, \dots, z_{n}; θ) d z \\ = \int_{Z^{n}} p (x_{1}, \dots, x_{n} | z_{1}, \dots, z_{n}, θ) p (z_{1}, \dots, z_{n}; θ) d z \\ = E_{θ} [p (x_{1}, \dots, x_{n} | z_{1}, \dots, z_{n}, θ)] \end{aligned}

$\begin{align*} p(x_1,\ldots,x_n;\theta) &= \int_\mathfrak{{Z}^n} p(x_1,\ldots,x_n,\mathfrak{z}_1,\ldots,\mathfrak{z}_n;\theta)\,\text{d}\mathbf{\mathfrak{z}}\\ &=\int_\mathfrak{{Z}^n} p(x_1,\ldots,x_n|\mathfrak{z}_1,\ldots,\mathfrak{z}_n,\theta)p(\mathfrak{z}_1,\ldots,\mathfrak{z}_n;\theta)\,\text{d}\mathbf{\mathfrak{z}}\\ &=\mathbb{E}_\theta\left[ p(x_1,\ldots,x_n|\mathfrak{z}_1,\ldots,\mathfrak{z}_n,\theta)\right] \end{align*}$ di mana harapan adalah dalam hal distribusi marjinal dari vektor laten

(z_{1}, \dots, z_{n})

$(\mathfrak{z}_1,\ldots,\mathfrak{z}_n)$ .

Intuisi di balik EM juga didasarkan pada harapan. Sejak $\log p(x_1,\ldots,x_n;\theta)$ tidak dapat dioptimalkan secara langsung, sementara $\log p(x_1,\ldots,x_n,\mathfrak{z}_1,\ldots,\mathfrak{z}_n;\theta)$ bisa tetapi tergantung pada yang tidak teramati $\mathfrak{z}_i$ Idenya adalah untuk memaksimalkan kemungkinan log lengkap yang diharapkan

E [\log p (x_{1}, \dots, x_{n}, z_{1}, \dots, z_{n}; θ) | x_{1}, \dots, x_{n}]

$\mathbb{E}\left[ \log p(x_1,\ldots,x_n,\mathfrak{z}_1,\ldots,\mathfrak{z}_n;\theta) \big| x_1,\ldots,x_n \right]$ kecuali bahwa harapan ini juga tergantung pada nilai

θ

$\theta$ , dipilih sebagai

θ_{0}

$\theta_0$ , katakanlah, maka fungsi untuk memaksimalkan (dalam

θ

$\theta$ ) pada langkah M:

Q (θ_{0}, θ) = E_{θ_{0}} [\log p (x_{1}, \dots, x_{n}, z_{1}, \dots, z_{n}; θ) | x_{1}, \dots, x_{n}]

$Q(\theta_0,\theta)=\mathbb{E}_{\theta_0}\left[ \log p(x_1,\ldots,x_n,\mathfrak{z}_1,\ldots,\mathfrak{z}_n;\theta) \big| x_1,\ldots,x_n \right]$ Ketidaksetaraan Jensen hanya datang sebagai pembenaran untuk peningkatan kemungkinan yang diamati pada setiap langkah M.

Xi'an
sumber

Terima kasih untuk penjelasannya. Karena distribusi posterior kami untuk vektor laten berubah pada setiap langkah, ya

E_{θ} [p (x_{1}, \dots, x_{n}, z, \dots, z, θ)]

$E_\theta[p(x_1,\dots,x_n, \mathfrak{z}, \dots, \mathfrak{z}, \theta)]$ berubah di setiap langkah juga? Jika demikian, gambar ini agak membingungkan karena ada kurva merah tetap yang mewakili

p (x; θ)

$p(x;\theta)$ sedangkan itu

p (x; θ)

$p(x;\theta)$ "perubahan" di setiap langkah karena kami rata-rata atas kepercayaan kami saat ini tentang vektor laten

z

$z$ pada langkah itu.

Heisenberg

maaf saya tidak mengerti pertanyaan: pada setiap langkah EM, nilai

E_{θ} [p (x_{1}, \dots, x_{n} | z_{1}, \dots, z_{n}, θ)]

$\mathbb{E}_\theta\left[ p(x_1,\ldots,x_n|\mathfrak{z}_1,\ldots,\mathfrak{z}_n,\theta)\right]$ perubahan dan peningkatan. Ini tidak berarti kemungkinan fungsi itu sendiri berubah.

Xi'an

Bukan

p (x_{1}, \dots, x_{n}; θ) = E_{θ} [p (x_{1}, \dots, x_{n} | z_{1}, \dots, z_{n}, θ)]

$p(x_1,\ldots,x_n;\theta) = \mathbb{E}_\theta\left[ p(x_1,\ldots,x_n|\mathfrak{z}_1,\ldots,\mathfrak{z}_n,\theta)\right]$ ? Jika RHS berubah sesuai dengan keyakinan posterior kita tentang vektor laten, apakah LHS juga berubah?

Heisenberg

Identitas ini ada dalam jawaban saya. Kedua belah pihak mengambil nilai yang berbeda saat

θ

$\theta$ bervariasi. Namun, dalam persamaan ini tidak ada gagasan tentang keyakinan posterior sebagai (a)

θ

$\theta$ diperbaiki dan (b)

z_{i}

$\mathfrak{z}_i$ dianggap sedikit.

Xi'an

Di setiap iterasi

t

$t$ , langkah E menggunakan

p (z | x, θ_{t})

$p(\mathfrak{z}|x, \theta_t)$ untuk menghitung integral

Q (θ_{t}, θ) = E_{θ_{t}} [\log p (x_{1}, \dots, x_{n}, z_{1}, \dots, z_{n}; θ) | x_{1}, \dots, x_{n}] .

$Q(\theta_t,\theta)=\mathbb{E}_{\theta_t}\left[ \log p(x_1,\ldots,x_n,\mathfrak{z}_1,\ldots,\mathfrak{z}_n;\theta) \big| x_1,\ldots,x_n \right].$ Karenanya fungsi target untuk memaksimalkan perubahan pada setiap iterasi

t

$t$ . Ini tidak mengatakan apa-apa tentang kemungkinan target asli

p (x_{1}, \dots, x_{n}; θ) = E_{θ} [p (x_{1}, \dots, x_{n} | z_{1}, \dots, z_{n}, θ)]

$p(x_1,\ldots,x_n;\theta) = \mathbb{E}_\theta\left[ p(x_1,\ldots,x_n|\mathfrak{z}_1,\ldots,\mathfrak{z}_n,\theta)\right]$ yang hanya tergantung pada satu

θ

$\theta$ .

Xi'an

Jawaban Xi'an sangat bagus, hanya beberapa ekstensi mengenai hasil edit.

Nama 'E-step' berasal dari fakta bahwa seseorang biasanya tidak perlu untuk membentuk distribusi probabilitas atas penyelesaian secara eksplisit, tetapi lebih perlu hanya menghitung statistik yang cukup 'diharapkan' atas penyelesaian ini.

Karena nilai $z$ tidak diamati, kami memperkirakan distribusi $q_x(z)$ untuk setiap titik data $x$ sebagai completionsdata teramati. Fungsi Q adalah jumlah kemungkinan log yang diharapkan berakhir $q_x(z)$

Q (θ) = \sum_{x} E_{q_{x}} [\log p (x, z | θ)]

$Q(\theta)=\sum_x E_{q_x}[\log p(x,z|\theta)]$

Yang disebutkan probability distribution over completionsharus merujuk $p(x,z|\theta)$ . Untuk beberapa distribusi (terutama keluarga eksponensial, karena kemungkinannya ada dalam bentuk log-nya), kita hanya perlu tahu yang diharapkan sufficient statistics(bukan kemungkinan yang diharapkan) untuk menghitung dan memaksimalkan $Q(\theta)$ .

Ada pengantar yang sangat bagus dalam Bab 19.2 dari Model Grafis Probabilistik.

dontloo
sumber