Validity and reliability

O algoritmo Expectation Maximization ou EM, como é comumente citado na literatura, consiste em um algoritmo para estimar parâmetros de uma mistura de gaussianas que melhor modele um conjunto qualquer de dados [15] (método paramétrico). Basicamente o algoritmo encontra um vetor de parâmetros Θ de uma função densidade de probabilidade. Em resumo temos que encontrar P (x|Θ), que é a probabilidade de ocorrer um vetor x dados os parâmetros Θ). No caso gaussiano, Θ é formado por médias, matrizes de covariância e probabilidades a priori. O algoritmo EM encontra os parâmetros da distribuição maximizando a verossimilhança dos dados expressa pela equação 2.21.

L(Θ) =

N



i=1

P (xi|Θ) (2.21)

Em geral não se maximiza diretamente L(Θ) e sim o seu logaritmo. Por ser uma função estritamente crescente, o logaritmo da verossimilhança terá um máximo no mesmo ponto que teria a verossimilhança em si, e torna o problema de maximização mais simples de se trabalhar, pois transforma o produtório em um somatório formando a expressão

log(L(Θ)) =

N

i=1

log(P (xi|Θ)). (2.22)

Este critério de maximização da verossimilhança, não é o único critério que pode ser utilizado. Akaike [2] propõe uma alternativa para o critério da verossimilhança que leva em conta o número de parâmetros utilizados. Este critério é comumente denominado de critério de informação de Akaike (AIC). Posteriormente a este critério, outros autores desenvolveram outros critérios [7] que também podem ser utilizados para o cálculo dos parâmetros ideais.

Para distribuições formadas por misturas de gaussianas a maximização de L(Θ) deve ser feita respeitando-se a restrição nos valores das probabilidades a priori Pi

como mostrado na equação 2.20. Para isto, alguma técnica de aplicação de restrições deve ser introduzida, como por exemplo o funcional de Lagrange.

A verossimilhança pode ser vista como a probabilidade de ocorrer todos os pontos dados se eles forem modelados por uma distribuição com parâmetros Θ e sua ocorrência for independente. Em estatística, a probabilidade de ocorrer dois eventos independentes é dada pelo produto das probabilidades

P (x1, x2) = P (x1) P (x2) (2.23)

De maneira geral se tivermos N eventos temos

P (x1, x2, . . . , xn) = P (x1) P (x2) . . . P (xN). (2.24)

Neste sentido, dado um vetor de parâmetros formados por exemplo por uma média e uma variância (no caso gaussiano), podemos formar uma distribuição de probabilidades. Após isso, dado um conjunto de observações X, a probabilidade destes pontos terem ocorrido desta distribuição é dada pela verossimilhança (o produtório significa exatamente a ocorrência de todos os pontos). Podemos então resumir da seguinte maneira; A função de verossimilhança L(Θ) é a probabilidade de ocorrerem os N pontos dados sabendo-se que a distribuição tem parâmetros Θ. Desta maneira, dados um conjuntos de pontos podemos especular que, como os pontos já são dados, a probabilidade destes ocorrerem é máxima (pois dentre todas as possibilidades, estes pontos foram os que ocorreram). Assim, se calcularmos quais parâmetros Θ maximizam a verossimilhança, estamos encontrando a distribuição que provavelmente forneceu os dados em questão.

A solução analítica para este problema de maximização da verossimilhança consiste em encontrar o máximo de log(Θ) (derivando e igualando a zero) solucionando o sistema de equações dado por

∂ L(Θ) ∂Θi

= 0. (2.25)

Este sistema consiste de várias equações não lineares (uma para cara parâmetro), e no caso de mistura de gaussianas D-dimensionais, as equações são matriciais, sendo os parâmetros definidos pelas médias das gaussianas e pelas suas matrizes de

covariância (supondo as probabilidades a priori conhecidas).

Embora a solução para este sistema possa ser implementada utilizando o método numérico iterativo, ainda assim o custo computacional seria proibitivo. Neste sentido, o algoritmo EM é uma ferramenta alternativa para a solução do problema. Por se tratar de um método de otimização, o algoritmo EM está sujeito a encontrar máximos locais ou apresentar problemas de convergência. Recentemente, Figueiredo e Jain [38] propuseram um novo método de estimação baseado no algoritmo EM que procura resolver este problemas utilizando técnicas de simulated annealing1_.

2.5.1.1 Descrição do algoritmo

O algoritmo EM é um algoritmo iterativo utilizado para minimizar a função de verossimilhança. Partindo de uma solução inicial para o vetor de parâmetros e melhorar esta solução a cada iteração. A atualização dos parâmetros é feita calculando-se os valores que resolvem o sistema da equação 2.25. De fato, para misturas de gaussianas, obter uma expressão isolada para os parâmetros nestas equações é muito difícil. A solução é realizar uma aproximação (descrita detalhadamente na literatura [15, 14]) e calcular uma função mais simples que aproxime o valor das verossimilhança, dados os vetores de dados atuais. Este passo é denominado na literatura de Expectation. O próximo passo é encontrar quais os parâmetros que maximizam a função encontrada na fase de expectation. Este passo recebe o nome de maximization.

Em seu trabalho, Dempster et al. [15] mostram que, para o caso de misturas de gaussianas com parâmetros de média, matrizes covariância e probabilidades a priori, estes são calculados iterativamente utilizando as equações 2.26

1

annealing ou recozimento é um termo utilizado em otimização para designar algoritmos motivados por teorias da área de termodinâmica onde a busca é feita inicialmente com uma alta entropia (buscas de longo alcance) e a medida que o algoritmo evolui, a busca vai sendo estreitada [45]

Pi(k+1) = N  j=1 h(k)_i (j) N µ(k+1)_i = N  j=1 h(k)_i (j) xj N  j=1 h(k)_i (j) Σ(k+1)_i = N  j=1 h(k)_i (j) (xj−µi)t(xj−µi) N  j=1 h(k)_i (j) (2.26)

onde os hi representam as probabilidades a posteriori calculadas como

h(k)_i (j) = P (k) i p(xj|µ(k)i , Σ (k) i ) Nc  t=1 P_t(k)p(xj|µ(k)t , Σ (k) t ) . (2.27)

Esta solução maximiza o logaritmo da verossimilhança sujeitas as restrições nas probabilidades a priori Pi mostradas na equação 2.20.

A Figura 2.9 mostra a inicialização dos parâmetros e a convergência em um exemplo de uso do algoritmo EM.

(a) Inicialização (b) Após 100 iterações

Figura 2.9: Exemplo de utilização do algoritmo EM

No exemplo são utilizados dados gerados por uma mistura de três gaussianas. As elipses representam o contorno de cada gaussiana. Observe que na Figura 2.9(a), as gaussianas são inicializadas de maneira aleatória, não modelando corretamente os dados. Ao final do processo, o algoritmo converge para os parâmetros da mistura e as gaussianas se ajustam de maneira a modelar corretamente os dados.

maximization é utilizada na solução de diversos problemas de otimização de parâmetros de distribuições. Existem várias maneiras de se chegar na otimização dos parâmetros e o grande problema aparece quando se tem de manipular a expressão do logaritmo da verossimilhança, que no caso das misturas de gaussianas aparece na forma do logaritmo de uma soma. Em 1998, Minka [65] apresentou uma abordagem de limite inferior de modo a resolver este problema.

Mesmo com as simplificações envolvidas e devido ao fato de ser um algoritmo iterativo, o algoritmo EM possui um custo computacional considerável e nem sempre encontra um máximo global para verossimilhança, exigindo assim, outras técnicas de estimação de parâmetros de distribuições de probabilidades.