Convergência do algoritmo EM com distribuição bivariada de mistura

9

Eu tenho um modelo de mistura no qual desejo encontrar o estimador de probabilidade máxima de um dado conjunto de dados e um conjunto de dados parcialmente observados . Eu implementei a etapa E (calculando a expectativa de z dado x e os parâmetros atuais \ theta ^ k ) e a etapa M, para minimizar a probabilidade logarítmica negativa, dada a expectativa de z .xzzθ k zxθkz

Pelo que entendi, a probabilidade máxima está aumentando para cada iteração, isso significa que a probabilidade de log negativa deve estar diminuindo para cada iteração? Entretanto, conforme iteramos, o algoritmo não produz realmente valores decrescentes da probabilidade logarítmica negativa. Em vez disso, pode estar diminuindo e aumentando. Por exemplo, esses eram os valores da probabilidade logarítmica negativa até a convergência:

insira a descrição da imagem aqui

Existe aqui que eu não entendi?

Além disso, para dados simulados quando eu executo a probabilidade máxima para as variáveis ​​latentes verdadeiras (não observadas), tenho um ajuste quase perfeito, indicando que não há erros de programação. Para o algoritmo EM, ele frequentemente converge para soluções claramente subótimas, particularmente para um subconjunto específico dos parâmetros (isto é, as proporções das variáveis ​​classificadoras). É sabido que o algoritmo pode convergir para mínimos locais ou pontos estacionários, há uma busca heurística convencional ou de igual modo a aumentar a probabilidade de encontrar o mínimo global (ou máximo) . Para esse problema em particular, acredito que existem muitas classificações errôneas porque, da mistura bivariada, uma das duas distribuições assume valores com probabilidade uma (é uma mistura de vidas úteis onde a vida real é encontrada porz zT=zT0+(1z) que indica o pertencimento a qualquer distribuição. O indicador é obviamente censurado no conjunto de dados. zzinsira a descrição da imagem aqui

Acrescentei uma segunda figura para quando começo com a solução teórica (que deve estar próxima da ideal). No entanto, como pode ser visto, a probabilidade e os parâmetros divergem dessa solução para uma que é claramente inferior.

edit: Os dados completos estão no formato que é um tempo observado para o sujeito , indica se o tempo está associado a um evento real ou se for censurado corretamente (1 indica evento e 0 indica censura correta), é o tempo de truncamento da observação (possivelmente 0) com o indicador de truncamento e finalmente é o indicador a que população a observação pertence (desde sua bivariada, precisamos considerar apenas 0 e 1). t i i δ i L i τ i z ixi=(ti,δi,Li,τi,zi)tiiδiLiτizi

Para , temos a função de densidade , da mesma forma que está associada à função de distribuição da cauda . Para o evento de interesse não ocorrerá. Embora não haja associado a essa distribuição, nós a definimos como , portanto e . Isso também produz a seguinte distribuição completa da mistura:z=1fz(t)=f(t|z=1)Sz(t)=S(t|z=1)z=0tinff(t|z=0)=0S(t|z=0)=1

f(t)=i=01pif(t|z=i)=pf(t|z=1) e S(t)=1p+pSz(t)

Prosseguimos para definir a forma geral da probabilidade:

L(θ;xi)=Πif(ti;θ)δiS(ti;θ)1δiS(Li)τi

Agora, é apenas parcialmente observado quando , caso contrário, é desconhecido. A probabilidade total se tornazδ=1

L(θ,p;xi)=Πi((pfz(ti;θ))zi)δi((1p)(1zi)(pSz(ti;θ))zi)1δi((1p)(1zi)(pSz(Li;θ))zi)τi

onde é o peso da distribuição correspondente (possivelmente associada a algumas covariáveis ​​e seus respectivos coeficientes por alguma função de link). Na maioria da literatura, isso é simplificado para a seguinte probabilidade de logaritmop

(ziln(p)+(1p)ln(1p)τi(ziln(p)+(1zi)ln(1p))+δizifz(ti;θ)+(1δi)ziSz(ti;θ)τiSz(Li;θ))

Para a etapa M , essa função é maximizada, embora não seja integralmente em um método de maximização. Em vez disso, não podemos que isso possa ser separado em partes .l(θ,p;)=l1(θ,)+l2(p,)

Para a etapa k: th + 1 E , devemos encontrar o valor esperado das variáveis ​​latentes (parcialmente) não observadas . Usamos o fato de que para , então .ziδ=1z=1

E(zi|xi,θ(k),p(k))=δi+(1δi)P(zi=1;θ(k),p(k)|xi)

Aqui temos, porP(zi=1;θ(k),p(k)|xi)=P(xi;θ(k),p(k)|zi=1)P(zi=1;θ(k),p(k))P(xi;θ(k),p(k))

que nos dáP(zi=1;θ(k),p(k)|xi)=pSz(ti;θ(k))1p+pSz(ti;θ(k))

(Observe aqui que , portanto não há evento observado, portanto, a probabilidade dos dados é fornecida pela função de distribuição da cauda.δi=0xi

Good Guy Mike
fonte
Você poderia escrever as variáveis ​​do nosso problema desde o início e suas equações E e M?
Alberto22
11
Obviamente, editei a pergunta com mais detalhes sobre a etapa E e M
Bom rapaz Mike
Para esclarecer, os valores plotados são o MLE completo, considerando os valores estimados para os dados incompletos.
9788By Mike Mike
O que é ? Eu não entendo "embora não haja t associado a essa distribuição, nós a definimos como inf ...". Sz
w ij
11
O algoritmo EM maximiza diretamente a probabilidade esperada de dados completos, mas pode garantir o aumento da probabilidade observada de dados. Você está verificando o aumento da probabilidade de dados observados?
Randel #

Respostas:

6

O objetivo do EM é maximizar a probabilidade de log de dados observada,

l(θ)=iln[zp(xi,z|θ)]

Infelizmente, isso tende a ser difícil de otimizar em relação a . Em vez disso, o EM forma e maximiza repetidamente a função auxiliarθ

Q(θ,θt)=Ez|θt(ilnp(xi,zi|θ))

Se maximiza , EM garante queθt+1Q(θ,θt)

l(θt+1)Q(θt+1,θt)Q(θt,θt)=l(θt)

Se você deseja saber exatamente por que esse é o caso, a Seção 11.4.7 do Aprendizado de máquina de Murphy : uma perspectiva probabilística fornece uma boa explicação. Se sua implementação não satisfizer essas desigualdades, você cometeu um erro em algum lugar. Dizendo coisas como

Tenho um ajuste quase perfeito, indicando que não há erros de programação

é perigoso. Com muitos algoritmos de otimização e aprendizado, é muito fácil cometer erros e ainda assim obter respostas de aparência correta na maioria das vezes. Uma intuição de que gosto é que esses algoritmos são destinados a lidar com dados confusos, portanto, não é surpreendente que eles também lidem bem com bugs!


Na outra metade da sua pergunta,

existe uma heurística de pesquisa convencional ou da mesma forma para aumentar a probabilidade de encontrar o mínimo (ou máximo) global

Reinicializações aleatórias é a abordagem mais fácil; o próximo mais fácil é provavelmente o recozimento simulado sobre os parâmetros iniciais. Também ouvi falar de uma variante do EM chamada de recozimento determinístico , mas não o usei pessoalmente, por isso não posso falar muito sobre isso.

Andy Jones
fonte
11
Boa resposta (+1). Seria ainda melhor se você incluísse referências formais (em particular, uma referência a uma fonte parcialmente citada "Machine Learning: A Probabilistic Perspective").
Aleksandr Blekh 6/04/2015
Muito obrigado pela resposta. Descobri que o algoritmo converge corretamente agora após corrigir um erro no código, mas somente quando excluo meus dados truncados. Caso contrário, ele vai mal. Eu acredito que isso é resultado de alguns erros.
Good Guy Mike
De fato, o problema é que eu trato de "truncamento heterogêneo", ou seja, existe um ponto de truncamento individual para cada observação, em vez de um limite de truncamento unânime para todas as observações. Nunca encontrei ou não encontro essas configurações na literatura, portanto não posso verificar se estou resolvendo isso corretamente. Se por acaso você visse essa configuração, eu adoraria dar uma olhada nessas referências! Li
Good Guy Mike