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

20

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

logp(x|θ)logp(z,x|θ)p(z|x,θ(k))dzlogp(z|x,θ)p(z|x,θ(k))dz

e defina porθ(k+1)

θ(k+1)=argmaxθlogp(z,x|θ)p(z|x,θ(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 θ(k+1) parece desmotivada para mim. Por que se deve considerar registro 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.

user782220
fonte
3
Qual é o algoritmo de maximização de expectativa? , Nature Biotechnology 26 : 897–899 (2008) tem uma bela imagem que ilustra como o algoritmo funciona.
chl
@chl: Eu vi esse artigo. O ponto que eu estou pedindo é que aviso que em nenhum lugar não explica por que uma abordagem não-log não pode trabalho
user782220

Respostas:

10

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|θ)registrop(x|θ)registro(umab)=registrouma+registrobp θθ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 .xz zzθθ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 zθzzθargmaxθzzθ, é 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 )registroθ(k+1)

Weiwei
fonte
Não vejo como isso responde à pergunta.
usar o seguinte código
9

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.registro

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 θ )pdados(x)p(xθ)

DKL[pdados(x)∣∣p(xθ)]=pdados(x)registropdados(x)p(xθ)dx=const-pdados(x)registrop(xθ)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

pdados(x)registrop(xθ)dx1Nnregistrop(xnθ).

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

registrop(xθ)=q(zx)registrop(x,zθ)q(zx)dz+DKL[q(zx)∣∣p(zx,θ)]

para qualquer . Se chamarmos o primeiro termo no lado direito , isso implica queF ( q , θ )q(zx)F(q,θ)

F(q,θ)=q(zx)registrop(x,zθ)q(zx)dz=registrop(xθ)-DKL[q(zx)∣∣p(zx,θ)].

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 , θ ) FF(q,θ)qFqθq(zx)=p(zx,θ)F

Lucas
fonte
Obrigado pelo post! Embora o documento fornecido não diga que o logaritmo é a função exclusiva de transformar produtos em somas. Diz que o logaritmo é a única função que cumpre todas as três propriedades listadas ao mesmo tempo .
21313 Weiwei
@ Weiwei: Certo, mas a primeira condição exige principalmente que a função seja invertível. Obviamente, f (x) = 0 também implica f (x + y) = f (x) f (y), mas este é um caso desinteressante. A terceira condição pede que a derivada em 1 seja 1, o que é verdadeiro apenas para o logaritmo basear . Abandone essa restrição e você obterá logaritmos em bases diferentes, mas ainda assim logaritmos. e
Lucas
4

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,θ)xzθDp(z,θ|D)

1. Amostra de Gibbs

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

θp(θ|z,D)zp(z|θ,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(θ)q(z)p(θ,z|D)KL[q(θ)q(z)||p(θ,z|D)]

q(θ)exp(E[logp(θ,z,D)]q(z))q(z)exp(E[logp(θ,z,D)]q(θ))

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θθθ

θ=argmaxθE[logp(θ,z,D)]q(z)q(z)=p(z|θ,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 expθargmaxlogexp

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 θzzθ

z=argmaxzE[logp(θ,z,D)]q(θ)q(θ)=p(θ|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 .zθz

θ=argmaxθp(θ,z,D)z=argmaxzp(θ,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

Anne van Rossum
fonte
(+1) este é um resumo bonito de todos os métodos.
Kdarps
4

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)=iexp(fi(x))
logg(x)xg(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 )fifi(x)xfi(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 ilogg(x)=logiexp(fi(x))logexpfi

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 ihgfi

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 gx0hgx0g(x0)=h(x0)g(x0)=h(x0)hx0g

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)=ifi(x)exp(fi(x)).
x0
h(x)=constant+ifi(x)exp(fi(x0)).
x=x0x 0 f i ghg( x 0 )=h( x 0 )
h(x)=ifi(x)exp(fi(x0)).
x0fEughg(x0 0)=h(x0 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 hx0 0h(x)g(x)x0 0hh

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 hh(x)g(x)h(x)xgg(x0 0)hgh

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

Dan Piponi
fonte
3

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 π iK

    p(x)=Eu=1KπEuN(x|μEu,ΣEu)
    πEuxμEuΣEuπEu 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.

jpmuc
fonte