Eu li algumas explicações do algoritmo EM (por exemplo, do reconhecimento de padrões e aprendizado de máquina de Bishop e do primeiro curso de Roger e Gerolami sobre aprendizado de máquina). A derivação do EM está bem, eu entendo. Também entendo por que o algoritmo cobre algo: em cada etapa, melhoramos o resultado e a probabilidade é limitada por 1,0; portanto, usando um fato simples (se uma função aumenta e é limitada, converge), sabemos que o algoritmo converge para alguma solução.

No entanto, como sabemos que é um mínimo local? Em cada etapa, estamos considerando apenas uma coordenada (variável latente ou parâmetros), para que possamos perder alguma coisa, como se o mínimo local exigisse o movimento de ambas as coordenadas ao mesmo tempo.

Acredito que esse seja um problema semelhante ao da classe geral de algoritmos de escalada, da qual EM é uma instância. Portanto, para um algoritmo geral de escalada em montanhas, temos esse problema para a função f (x, y) = x * y. Se começarmos do ponto (0, 0), somente considerando as duas direções ao mesmo tempo, poderemos subir do valor 0.

Não é garantido que o EM converja para um mínimo local. Só é garantido que converja para um ponto com gradiente zero em relação aos parâmetros. Portanto, ele pode realmente ficar preso nos pontos de sela.

Primeiro de tudo, é possível que o EM converja para um mínimo local , um máximo local ou um ponto de sela da função de probabilidade. Mais precisamente, como Tom Minka apontou, o EM é garantido para convergir para um ponto com gradiente zero .

Eu posso pensar em duas maneiras de ver isso; a primeira visão é pura intuição e a segunda é o esboço de uma prova formal. Primeiro, explicarei brevemente como o EM funciona:

$t$$b_t(\theta)$$L(\theta)$$\theta_t = \arg\max_\theta b_t(\theta)$

Expectativa Maximização como subida de gradiente

Em cada iteração , EM exige que o limite toque na função de probabilidade na solução da iteração anterior, isto é, que implica que seus gradientes também são os mesmos; isto é . Portanto, EM é pelo menos tão bom quanto a subida do gradiente porque é pelo menos tão bom quanto . Em outras palavras:b t L θ t - 1 g = ∇ b t ( θ t - 1 ) = ∇ L ( θ t - 1 ) θ t θ t - 1 + η $t$$b_t$$L$$\theta_{t-1}$$g = \nabla b_t(\theta_{t-1}) = \nabla L(\theta_{t-1})$$\theta_t$$\theta_{t-1} + \eta g$

se EM converge para então é um ponto convergente para subida de gradiente e EM satisfaz qualquer propriedade compartilhada entre as soluções de ascensão de gradiente (incluindo o valor de gradiente zero).θ $\theta^*$$\theta^*$

Esboço de uma prova formal

Pode-se mostrar que a diferença entre os limites e a função de probabilidade converge para zero; isto é Pode-se provar que o gradiente do limite também converge para o gradiente da função de probabilidade; ou seja: Por causa de e e que os limites usados ​​no EM são diferenciáveis, e que , temos esse e, portanto, .