Pourquoi y a-t-il un E dans le nom de l'algorithme EM?

Je comprends où l'étape E se produit dans l'algorithme (comme expliqué dans la section mathématique ci-dessous). Dans mon esprit, l'ingéniosité clé de l'algorithme est l'utilisation de l'inégalité de Jensen pour créer une limite inférieure à la vraisemblance logarithmique. En ce sens, prendre le Expectationest simplement fait pour reformuler la probabilité logarithmique de s'insérer dans l'inégalité de Jensen (c'est-à-dire pour la fonction concave.) $E(f(x)) < f(E(x))$

Y a-t-il une raison pour laquelle le E-step est appelé ainsi? Y a-t-il une signification à la chose que nous attendons (c.-à-d. ? J'ai l'impression de manquer d'intuition derrière la raison pour laquelle l'attente est si centrale, plutôt que d'être simplement accessoire à la utilisation de l'inégalité de Jensen. $p(x_i, z_i| \theta)$

EDIT: Un tutoriel dit:

Le nom «E-step» vient du fait que l'on n'a généralement pas besoin de former explicitement la distribution de probabilité sur les achèvements, mais qu'il suffit de calculer des statistiques suffisantes «attendues» sur ces achèvements.

Qu'est-ce que cela signifie "il n'est généralement pas nécessaire de former explicitement la distribution de probabilité sur les achèvements"? À quoi ressemblerait cette distribution de probabilité?

Annexe: E-étape dans l'algorithme 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
la source

Pour moi, ce que vous demandez n'est pas clair, mais j'ai toujours supposé que la pertinence derrière la désignation de l'étape E est que, dans un certain sens, vous "remplissez" ou "imputez" le manquant en prenant l'attente. Certes, ce n'est pas exactement ce qui se passe parce que vous prenez ce qui n'est pas la même chose que de brancher quelque chose pour le il manque valeurs , mais sur le plan opérationnel, on finit souvent par faire quelque chose comme ça. Si nous faisions une augmentation des données - qui est similaire à l'EM à bien des égards.

z

$z$

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

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

Z

$Z$

gars le

Oui, c'est le genre de discussion que je veux avoir. Donc, quand vous dites imputer z en prenant l'attente ". L'attente de quoi? De plus, voulez-vous dire au lieu de ?

E_{z}

$E_z$

E_{θ}

$E_\theta$

Heisenberg

Mon éducation a toujours été d'indexer le avec le paramètre indexant la mesure de probabilité à laquelle l'attente est prise par rapport à. Dans CS, ils le font comme vous le suggérez. J'intègre , en conditionnant sur une mesure indexée par .

E

$E$

Z

$Z$

X

$X$

θ

$\theta$

gars le

Par exemple, lors de l'ajustement de mélanges gaussiens, l'étape E a imputé les indicateurs de classe manquants. Mais il le fait de manière floue en calculant les responsabilités pour chaque observation.

gars

Réponses:

Les attentes sont au cœur de l'algorithme EM. Pour commencer, la probabilité associée aux données est représentée comme une attente où l' attente est en termes de distribution marginale du vecteur latent . $(x_1,\ldots,x_n)$

\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*}$

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

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

L'intuition derrière EM est également basée sur une attente. Étant donné que ne peut pas être optimisé directement, tandis que peut mais dépend des non observés , l'idée est de maximiser à la place la log-vraisemblance complète attendue sauf que cette attente dépend également d'une valeur de , choisie comme , par exemple, d'où la fonction à maximiser (in ) dans l'étape M: $\log p(x_1,\ldots,x_n;\theta)$ $\log p(x_1,\ldots,x_n,\mathfrak{z}_1,\ldots,\mathfrak{z}_n;\theta)$ $\mathfrak{z}_i$

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]$

θ

$\theta$

θ_{0}

$\theta_0$

θ

$\theta$

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]$ L'inégalité de Jensen ne vient que pour justifier l'augmentation de la probabilité observée à chaque étape M.

Xi'an
la source

Merci pour l'explication. Puisque notre distribution postérieure pour les vecteurs latents change à chaque étape, change à chaque étape ainsi que? Si c'est le cas, cette image est un peu déroutante car il y a une courbe rouge fixe représentant , alors qu'elle "change" à chaque étape puisque nous faisons la moyenne de notre croyance actuelle à propos de les vecteurs latents à cette étape.

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

$E_\theta[p(x_1,\dots,x_n, \mathfrak{z}, \dots, \mathfrak{z}, \theta)]$

p (x; θ)

$p(x;\theta)$

p (x; θ)

$p(x;\theta)$

z

$z$

Heisenberg

désolé, je ne comprends pas la question: à chaque étape EM, la valeur de change et augmente. Cela ne signifie pas que la fonction de vraisemblance elle-même change.

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]$

Xi'an

Est-ce que ? Si le RHS change selon notre croyance postérieure sur le vecteur latent, le LHS change-t-il également?

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]$

Heisenberg

Cette identité est dans ma réponse. Les deux côtés prennent des valeurs différentes lorsque varie. Cependant, dans cette équation, il n'y a aucune notion de croyance postérieure car (a) est fixe et (b) les sont considérés marginalement.

θ

$\theta$

θ

$\theta$

z_{i}

$\mathfrak{z}_i$

Xi'an

À chaque itération , l'étape E utilise pour calculer l'intégraleD'où la fonction cible pour maximiser les changements à chaque itération . Cela ne dit rien sur la probabilité cible d'origine qui ne dépend que d'un seul .

t

$t$

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

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

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].$

t

$t$

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]$

θ

$\theta$

Xi'an

La réponse de Xi'an est très bonne, juste une extension concernant l'édition.

Le nom «E-step» vient du fait que l'on n'a généralement pas besoin de former explicitement la distribution de probabilité sur les achèvements, mais qu'il suffit de calculer des statistiques suffisantes «attendues» sur ces achèvements.

Puisque la valeur de n'est pas observée, nous estimons une distribution pour chaque point de données partir des données non observées. La fonction Q est la somme des probabilités logarithmiques attendues sur $z$ $q_x(z)$ $x$ completions $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)]$

Les éléments mentionnés probability distribution over completionsdoivent faire référence à . Pour certaines distributions (en particulier la famille exponentielle, puisque la vraisemblance est sous sa forme logarithmique), il suffit de connaître l'attendu (au lieu de la vraisemblance attendue) pour calculer et maximiser . $p(x,z|\theta)$ sufficient statistics $Q(\theta)$

Il y a une très bonne introduction au chapitre 19.2 des modèles graphiques probabilistes.

dontloo
la source