Motivação do algoritmo de maximização de expectativa

Na abordagem do algoritmo EM, usamos a desigualdade de Jensen para chegar a

$$\log p(x|\theta) \geq \int \log p(z,x|\theta) p(z|x,\theta^{(k)}) dz - \int \log p(z|x,\theta) p(z|x,\theta^{(k)})dz$$

e defina por$\theta^{(k+1)}$

$$\theta^{(k+1)}=\arg \max_{\theta}\int \log p(z,x|\theta) p(z|x,\theta^{(k)}) dz$$

Tudo o que eu leio EM apenas explica tudo, mas sempre me senti desconfortável por não ter uma explicação do porquê o algoritmo EM surge naturalmente. Entendo que a probabilidade de $\log$ é normalmente tratada para lidar com adição em vez de multiplicação, mas a aparência de $\log$ na definição de $\theta^{(k+1)}$ parece desmotivada para mim. Por que se deve considerar $\log$ e não outras funções monotônicas? Por várias razões, suspeito que o "significado" ou a "motivação" por trás da maximização das expectativas tenham algum tipo de explicação em termos de teoria da informação e estatísticas suficientes. Se houvesse tal explicação, seria muito mais satisfatória do que apenas um algoritmo abstrato.

O algoritmo EM tem diferentes interpretações e pode surgir de diferentes formas em diferentes aplicações.

Tudo começa com a função de probabilidade , ou equivalente, a função de probabilidade do que gostaríamos de maximizar. (Geralmente usamos logaritmo, pois simplifica o cálculo: é estritamente monótono, côncavo e .) Em um mundo ideal, o valor de depende apenas do parâmetro do modelo , para que possamos procurar pelo espaço de e encontrar um que maximize .$p(x \vert \theta)$$\log p(x \vert \theta)$$\log(ab) = \log a + \log b$$p$ $\theta$$\theta$$p$

No entanto, em muitas aplicações interessantes do mundo real, as coisas são mais complicadas, porque nem todas as variáveis ​​são observadas. Sim, podemos observar diretamente , mas algumas outras variáveis não são observadas. Devido às variáveis ​​ausentes , estamos em uma espécie de situação de galinha e ovos: sem não podemos estimar o parâmetro e sem não podemos inferir qual pode ser o valor de .$x$$z$ $z$$z$$\theta$$\theta$$z$

É onde o algoritmo EM entra em ação. Começamos com uma estimativa inicial dos parâmetros do modelo e derivamos os valores esperados das variáveis ​​ausentes (isto é, a etapa E). Quando temos os valores de , podemos maximizar a probabilidade de escrever os parâmetros (ou seja, a etapa M, correspondente à equação na declaração do problema). Com este , podemos derivar os novos valores esperados de (outra etapa E), e assim por diante. Em outra palavra, em cada etapa, assumimos um dos dois, ez z θ arg max θ z $\theta$$z$$z$$\theta$$\arg \max$$\theta$$z$$z$$\theta$, é conhecido. Repetimos esse processo iterativo até que a probabilidade não possa mais ser aumentada.

Este é o algoritmo EM em poucas palavras. É sabido que a probabilidade nunca diminuirá durante esse processo iterativo de EM. Mas lembre-se de que o algoritmo EM não garante a otimização global. Ou seja, pode acabar com um ótimo local da função de probabilidade.

A aparência de na equação de é inevitável, porque aqui a função que você gostaria de maximizar é escrita como uma probabilidade de log.θ ( k + 1 $\log$$\theta^{(k+1)}$

Probabilidade x probabilidade logarítmica

Como já foi dito, o é introduzido com a máxima probabilidade simplesmente porque geralmente é mais fácil otimizar somas do que produtos. A razão pela qual não consideramos outras funções monotônicas é que o logaritmo é a função exclusiva com a propriedade de transformar produtos em somas.$\log$

Outra maneira de motivar o logaritmo é o seguinte: Em vez de maximizar a probabilidade dos dados em nosso modelo, podemos tentar equivalentemente minimizar a divergência de Kullback-Leibler entre a distribuição de dados, e a distribuição de modelo, ,p ( x ∣ θ $p_\text{data}(x)$$p(x \mid \theta)$

$$D_\text{KL}[p_\text{data}(x) \mid\mid p(x \mid \theta)] = \int p_\text{data}(x) \log \frac{p_\text{data}(x)}{p(x \mid \theta)} \, dx = const - \int p_\text{data}(x)\log p(x \mid \theta) \, dx.$$

O primeiro termo no lado direito é constante nos parâmetros. Se tivermos amostras da distribuição de dados (nossos pontos de dados), podemos aproximar o segundo termo com a probabilidade média de log dos dados,$N$

$$\int p_\text{data}(x)\log p(x \mid \theta) \, dx \approx \frac{1}{N} \sum_n \log p(x_n \mid \theta).$$

Uma visão alternativa do EM

Não tenho certeza se esse será o tipo de explicação que você procura, mas achei a seguinte visão da maximização das expectativas muito mais esclarecedora do que sua motivação pela desigualdade de Jensen (você pode encontrar uma descrição detalhada em Neal & Hinton (1998) ou no livro PRML de Chris Bishop, capítulo 9.3).

Não é difícil mostrar que

$$\log p(x \mid \theta) = \int q(z \mid x) \log \frac{p(x, z \mid \theta)}{q(z \mid x)} \, dz + D_\text{KL}[q(z \mid x) \mid\mid p(z \mid x, \theta)]$$

para qualquer . Se chamarmos o primeiro termo no lado direito , isso implica queF ( q , θ $q(z \mid x)$$F(q, \theta)$

$$F(q, \theta) = \int q(z \mid x) \log \frac{p(x, z \mid \theta)}{q(z \mid x)} \, dz = \log p(x \mid \theta) - D_\text{KL}[q(z \mid x) \mid\mid p(z \mid x, \theta)].$$

Como a divergência de KL é sempre positiva , é um limite inferior na probabilidade de log para cada fixo . Agora, EM pode ser visto como maximizando alternativamente em relação a e . Em particular, pela configuração no E-passo, nós minimizar a divergência KL no lado da mão direita e, assim, maximizar .q F q θ q ( z ∣ x ) = p ( z ∣ x , θ ) $F(q, \theta)$$q$$F$$q$$\theta$$q(z \mid x) = p(z \mid x, \theta)$$F$

O artigo que achei esclarecedor no que diz respeito à maximização de expectativas é o K-Means Bayesiano como um algoritmo de "maximização-expectativa" (pdf) de Welling e Kurihara.

Suponha que tenhamos um modelo probabilístico com observações, variáveis ​​aleatórias ocultas e um total de parâmetros. Recebemos um conjunto de dados e somos forçados (por potências mais altas) a estabelecer .x z θ D p ( z , θ | D $p(x,z,\theta)$$x$$z$$\theta$$D$$p(z,\theta|D)$

1. Amostra de Gibbs

Podemos aproximar por amostragem. A amostragem de Gibbs fornece alternando:p ( z , θ | D $p(z,\theta|D)$$p(z,\theta|D)$

$$\theta \sim p(\theta|z,D) \\ z \sim p(z|\theta,D)$$

2. Bayes Variacionais

Em vez disso, podemos tentar estabelecer uma distribuição e e minimizar a diferença com a distribuição que buscamos após . A diferença entre distribuições tem um nome conveniente, a KL-divergência. Para minimizar , atualizamos:q ( z ) p ( θ , z | D ) K L [ q ( θ ) q ( z ) | | p ( θ , z | D ) $q(\theta)$$q(z)$$p(\theta,z|D)$$KL[q(\theta)q(z)||p(\theta,z|D)]$

$$q(\theta) \propto \exp (E [\log p(\theta,z,D) ]_{q(z)} ) \\ q(z) \propto \exp (E [\log p(\theta,z,D) ]_{q(\theta)} )$$

3. Maximização de Expectativas

Apresentar distribuições de probabilidade completas para e pode ser considerado extremo. Por que não consideramos uma estimativa pontual para uma delas e mantemos a outra agradável e diferenciada. Em EM, o parâmetro é estabelecido como indigno de uma distribuição completa e definido como seu valor MAP (Máximo A Posteriori), .θ θ θ $z$$\theta$$\theta$$\theta^*$

$$\theta^* = \underset{\theta}{\operatorname{argmax}} E [\log p(\theta,z,D) ]_{q(z)} \\ q(z) = p(z|\theta^*,D)$$

Aqui seria realmente uma notação melhor: o operador argmax pode retornar vários valores. Mas não vamos escolher. Comparado com Bayes variacionais, você vê que a correção do por não altera o resultado, portanto, isso não é mais necessário.log $\theta^* \in \operatorname{argmax}$$\log$$\exp$

4. Maximização-Expectativa

Não há razão para tratar como uma criança mimada. Também podemos usar estimativas pontuais para nossas variáveis ​​ocultas e dar aos parâmetros o luxo de uma distribuição completa.z ∗$z$$z^*$$\theta$

$$z^* = \underset{z}{\operatorname{argmax}} E [\log p(\theta,z,D) ]_{q(\theta)} \\ q(\theta) = p(\theta|z^*,D)$$

Se nossas variáveis ​​ocultas são variáveis ​​indicadoras, de repente temos um método computacionalmente barato para realizar inferência no número de clusters. Isto é, em outras palavras: seleção de modelo (ou detecção automática de relevância ou imagine outro nome sofisticado).$z$

5. Modos condicionais iterados

Obviamente, o filho-poster da inferência aproximada é usar estimativas pontuais para os parâmetros e para as observações .$\theta$$z$

$$\theta^* = \underset{\theta}{\operatorname{argmax}} p(\theta,z^*,D) \\ z^* = \underset{z}{\operatorname{argmax}} p(\theta^*,z,D) \\ $$

Para ver como a Maximização-Expectativa se desenrola, recomendo o artigo. Na minha opinião, a força deste artigo não é, contudo, a aplicação a uma alternativa significa, mas essa exposição lúcida e concisa da aproximação.$k$

Existe uma técnica de otimização útil subjacente ao algoritmo EM. No entanto, geralmente é expresso na linguagem da teoria das probabilidades, por isso é difícil perceber que, no centro, existe um método que não tem nada a ver com probabilidade e expectativa.

Considere o problema de maximizar (ou equivalentemente ) em relação a . Se você escrever uma expressão para e configurá-la como zero, muitas vezes você terminará com uma equação transcendental para resolver. Estes podem ser desagradáveis.log g ( x ) x g ' ( x

$$g(x)=\sum_i\exp(f_i(x))$$ $\log g(x)$$x$$g'(x)$

Agora, suponha que os joguem bem juntos, no sentido de que combinações lineares deles fornecem algo fácil de otimizar. Por exemplo, se todos os são quadráticos em , uma combinação linear de também será quadrática e, portanto, fácil de otimizar.f i ( x ) x f i ( x $f_i$$f_i(x)$$x$$f_i(x)$

Dada essa suposição, seria legal se, para otimizar , pudéssemos, de alguma forma, embaralhar o além do para que ele pudesse atender às s e elimine-os. Então o poderia tocar juntos. Mas não podemos fazer isso.log Σ exp f $\log g(x)=\log \sum_i\exp(f_i(x))$$\log$$\sum$$\exp$$f_i$

Vamos fazer a próxima melhor coisa. Faremos outra função que é semelhante a . E nós vamos fazer isso com combinações lineares de .g f $h$$g$$f_i$

Digamos que é um palpite para um valor ideal. Gostaríamos de melhorar isso. Vamos encontrar outra função que corresponde ao e o seu derivado em , ou seja e . Se você plotar um gráfico de em um pequeno bairro de será semelhante a . h g x 0 g ( x 0 ) = h ( x 0 ) g ′ ( x 0 ) = h ′ ( x 0 ) h x 0$x_0$$h$$g$$x_0$$g(x_0)=h(x_0)$$g'(x_0)=h'(x_0)$$h$$x_0$$g$

Você pode mostrar queQueremos algo que corresponda a isso em . Existe uma escolha natural:Você pode ver que eles correspondem em . TemosComo é uma constante, temos uma combinação linear simples de cuja derivada corresponde a . Nós apenas temos que escolher a constante em para fazer .x 0 h ( x ) = constante + Σ i f i ( x ) exp ( f i ( x 0 ) ) . x = x 0 h ′ ( x ) =

$$g'(x)=\sum_i f_i'(x)\exp(f_i(x)).$$ $x_0$ $$h(x)=\mbox{constant}+\sum_i f_i(x)\exp(f_i(x_0)).$$ $x=x_0$x 0 f i ghg( x 0 )=h( x 0 $$h'(x)=\sum_i f_i'(x)\exp(f_i(x_0)).$$ $x_0$$f_i$$g$$h$$g(x_0)=h(x_0)$

Assim, começando com , que formam e que optimize. Como é semelhante a na vizinhança de , esperamos que o ideal de seja semelhante ao ideal de g. Depois de ter uma nova estimativa, construa a próxima repita. h ( x ) g ( x ) x 0 h $x_0$$h(x)$$g(x)$$x_0$$h$$h$

Espero que isso tenha motivado a escolha de . Este é exatamente o procedimento que ocorre no EM.$h$

Mas há mais um ponto importante. Usando a desigualdade de Jensen, você pode mostrar que . Isso significa que, quando você otimiza sempre obtém um que torna maior em comparação com . Portanto, mesmo que tenha sido motivado por sua similaridade local com , é seguro maximizar globalmente a cada iteração. A esperança que mencionei acima não é necessária.h ( x ) x g g ( x 0 ) h g $h(x)\le g(x)$$h(x)$$x$$g$$g(x_0)$$h$$g$$h$

Isso também fornece uma pista de quando usar EM: quando combinações lineares dos argumentos da função são mais fáceis de otimizar. Por exemplo, quando são quadráticos - como acontece quando se trabalha com misturas de gaussianos. Isso é particularmente relevante para estatísticas em que muitas das distribuições padrão são de famílias exponenciais .$\exp$

Como você disse, não entrarei em detalhes técnicos. Existem alguns tutoriais muito bons. Um dos meus favoritos são as anotações de Andrew Ng . Veja também as referências aqui .

1. O EM é naturalmente motivado em modelos de mistura e modelos com fatores ocultos em geral. Tomemos, por exemplo, o caso dos modelos de mistura gaussiana (GMM). Aqui modelamos a densidade das observações como uma soma ponderada de gaussianos: onde é a probabilidade de a amostra sido causada / gerada pelo i-ésimo componente, é a média da distribuição e é a covariância matriz. A maneira de entender essa expressão é a seguinte: cada amostra de dados foi gerada / causada por um componente, mas não sabemos qual. A abordagem é então expressar a incerteza em termos de probabilidade (p ( x ) = K ∑ i = 1 π i N ( x | μ i , Σ i ) π i x μ i Σ i π $K$

   $$p(x) = \sum_{i=1}^{K}\pi_{i} \mathcal{N}(x|\mu_{i}, \Sigma_{i})$$ $\pi_{i}$$x$$\mu_{i}$$\Sigma_{i}$$\pi_{i}$ representa as chances de que o i-ésimo componente possa ser responsável por essa amostra) e a soma ponderada. Como um exemplo concreto, imagine que você deseja agrupar documentos de texto. A idéia é assumir que cada documento pertence a um tópico (ciência, esportes, ...) que você não conhece de antemão !. Os tópicos possíveis são variáveis ​​ocultas. Então, você recebe vários documentos e, contando n gramas ou quaisquer recursos extraídos, deseja encontrar esses clusters e ver a qual cluster cada documento pertence. O EM é um procedimento que ataca este problema passo a passo: o passo de expectativa tenta melhorar as atribuições das amostras que alcançou até agora. Na etapa de maximização, você melhora os parâmetros da mistura, ou seja, a forma dos clusters.

2. O ponto não é usar funções monotônicas, mas funções convexas. E a razão é a desigualdade de Jensen, que garante que as estimativas do algoritmo EM melhorem a cada passo.