Qual é a diferença entre EM e Gradient Ascent?

Qual é a diferença entre os algoritmos EM (Maximização de Expectativas) e Subida de Gradiente (ou descida)? Existe alguma condição sob a qual eles são equivalentes?

gradient-descent expectation-maximization Aslan986
fonte

Respostas:

A partir de:

Xu L e Jordan MI (1996). Sobre propriedades de convergência do algoritmo EM para misturas gaussianas . Computação Neural 2: 129-151.

Abstrato:

Mostramos que a etapa EM no espaço do parâmetro é obtida a partir do gradiente por meio de uma matriz de projeção P, e fornecemos uma expressão explícita para a matriz.

Página 2

Em particular, mostramos que o passo EM pode ser obtido pré-multiplicando o gradiente por uma matriz de denite positiva. Fornecemos uma expressão explícita para a matriz ...

Page 3

Ou seja, o algoritmo EM pode ser visto como um algoritmo de subida de gradiente métrico variável ...

Isto é, o artigo fornece transformações explícitas do algoritmo EM em gradiente-ascensão, Newton, quase-Newton.

Da wikipedia

Existem outros métodos para encontrar estimativas de máxima verossimilhança, como descida do gradiente, gradiente conjugado ou variações do método de Gauss-Newton. Diferentemente do EM, esses métodos normalmente requerem a avaliação de primeira e / ou segunda derivada da função de probabilidade.

Ron Coleman
fonte

Essa resposta parece sugerir que EM e descida de gradiente são basicamente o mesmo algoritmo, com transformações disponíveis para alternar de um algoritmo para outro. Definitivamente, isso não é verdade em geral e depende fortemente do modelo generativo levado em consideração. O artigo citado apenas tira conclusões para os modelos de mistura gaussiana (que são modelos generativos relativamente simples), e com razão. Na minha experiência (reconhecidamente limitada), quando o modelo é altamente não linear e o papel das variáveis latentes é importante, o EM é a única maneira de derivar regras de atualização sensatas.

blue

Não, eles não são equivalentes. Em particular, a convergência EM é muito mais lenta.

Se você estiver interessado em um ponto de vista de otimização no EM, neste artigo, você verá que o algoritmo EM é um caso especial de uma classe mais ampla de algoritmos (algoritmos de ponto proximal).

Elvis
fonte

Ou para um tipo semelhante de idéia, Hinton e Neal (1998)

conjugateprior

"A convergência EM é muito mais lenta"; isso não está bem definido e, certamente, geralmente não é verdade. Os algoritmos EM são uma classe inteira de algoritmos. Para muitos problemas, um certo algoritmo EM é o estado da arte.

Cliff AB

@CliffAB, por favor, não hesite em falar sobre isso, eu adoraria ler seus argumentos - como li esta resposta de quatro anos, percebo que não responderia hoje. Desde então, descobri que, em muitos casos, o EM é uma subida gradiente com um parâmetro de 'taxa de aprendizado' dependendo do ponto atual ... (posso editar essa resposta em algum momento para apontar resultados do tipo)

Elvis

"Convergência mais lenta" pode ser definida em termos de taxa de convergência. A taxa de convergência de uma subida de gradiente dependerá da 'taxa de aprendizado', que não é fácil de escolher, dificultando a subida de gradiente em muitos casos. No entanto, ainda tenho a sensação de que, embora o EM possa ser, em alguns casos, o único algoritmo viável (as derivações da probabilidade ou a probabilidade em si são difíceis de calcular), sua taxa de convergência é baixa, em comparação com um método semelhante a Newton.

Elvis

"O" algoritmo EM é realmente uma classe inteira de algoritmos; aquele em que a função de destino original é difícil de otimizar, mas se alguma outra variável fosse conhecida, a solução seria muito mais fácil (normalmente na forma fechada). O esquema básico é preencher a variável esperada condicional aos valores atuais dos outros parâmetros e atualizar os parâmetros com base no valor esperado da variável. Foi demonstrado que a rapidez com que o algoritmo converge depende de quão informativos são os dados imputados; quanto mais "informativos" forem os dados ausentes, mais lenta será a convergência.

Cliff AB