Uma tarefa comum em diversas aplicações envolve estimar, para um conjunto de dados observados — X = {xn}Nn=1, xn ∈ RM), em que as N amostras são independentes e identica-
mente distribuídas — os parâmetros do GMM gerador dos mesmos. Nesta tese, é considerado o uso do algoritmo Expectation Maximization (EM) para a estimação dos parâmetros do GMM. O algoritmo EM (Dempster et al., 1977) é uma abordagem para a computação iterativa de estimativas de máxima verossimilhança — Maximum Likelihood Estimate (MLE) — útil para uma variedade de problemas com dados incompletos (McLachlan e Krishnan, 1997). De forma intuitiva, o EM associa um problema com dados incompletos a um com dados completos cuja estimação da verossimilhança seja mais tratável (Bishop, 2006). A literatura sobre EM e GMM é rica, e sugere-se ao leitor interessado os trabalho de Dempster et al. (1977); McLachlan e Krishnan (1997); Dasgupta (1999); McLachlan e Peel (2000); Bishop (2006). Caso o leitor já esteja familiarizado com o EM no contexto de GMMs, não é necessária a leitura desta seção. Por conveniência, é utilizada a mesma notação do popular livro de Bishop (2006).
Para a aplicação do EM, inicialmente define-se o conjunto completo de dados. Neste caso, o conjunto completo é formado pelo conjunto de dados observados (X = {xn}Nn=1, xn ∈ RM), e
um conjunto correspondente de vetores indicadores (Z = {zn}Nn=1, zn∈ {0, 1}K), que indicam
a qual dos K componentes a n-ésima amostra pertence2.
A função de verossimilhança define a probabilidade de serem observados os dados comple- tos condicionada aos parâmetros, i.e., p(X , Z|Ψ). No entanto, os valores em Z são desconhe- cidos e, por tal razão, é necessário computar o valor esperado dos vetores indicadores, dado por (Bishop, 2006): γ(znk) = E[znk] = πkN (xn|µk, Σk) PK j=1πj N (xn|µj, Σj) , (2.3)
na qual E denota o operador de esperança. Esta quantidade pode ser vista como a responsabili- dadedo k-ésimo componente em explicar a observação xn(Bishop, 2006). Considerando estas
responsabilidades, pode-se obter o valor esperado da função logarítmica de verossimilhança3
2z
nutiliza uma representação 1-para-K.
3Esta função é usualmente utilizada no lugar da função de verossimilhança devido a duas propriedades:
log(a˙b) = log(a) + log(b), que torna a computação mais eficiente; a função log(.) é monotonicamente cres- cente em relação ao seu argumento. Portanto, maximizar a função de verossimilhança é equivalente a maximizar a
2.2 Estimação de Parâmetros 13 (Bishop, 2006): LLK(X |Ψ) = EZ[ln p(X , Z|Ψ)] = N X n=1 K X k=1 γ(znk){ln πk+ lnN (xn|µk, Σk)} . (2.4)
O algoritmo EM para este modelo pode ser então resumido da seguinte forma. No primeiro passo, chamado de passo E (Expectation), avaliam-se as responsabilidades esperadas (γ(znk))
de cada objeto para cada componente. É importante observar que, para tal, são necessários os parâmetros do modelo (Ψ). No caso da primeira iteração, não há nenhuma estimativa para os seus valores. Neste caso, diversas abordagens podem ser utilizadas para fornecer valores iniciais para o algoritmo. Uma das alternativas é utilizar o algoritmo K-means4 (McLachlan e Peel, 2000). No segundo passo, denominado de passo M (Maximization), os parâmetros do modelo são ajustados de forma a maximizar a função de verossimilhança. As atualizações dos parâmetros referentes a cada componente k são realizadas de acordo com:
πk = N X n=1 γ(znk) N , (2.5) µk = N X n=1 γ(znk)xn N X n=1 γ(znk) , (2.6) Σk = N X n=1 γ(znk)(xn− µk)(xn− µk) T N X n=1 γ(znk) . (2.7)
Os passos E e M são repetidos iterativamente até a convergência, dada usualmente por uma mudança pequena no valor da função logarítmica de verossimilhança. É conhecido que o algoritmo EM converge para um ótimo local da função de verossimilhança. Porém, também já foi constatado que o algoritmo EM demora a convergir em diversas aplicações (McLachlan e Krishnan, 1997).
Como a convergência para um ótimo global não é garantida, é comum repetir diversas vezes o algoritmo, a partir de inicializações diferentes, e selecionar a melhor delas, considerando-se a função de verossimilhança. Além disso, em diversas aplicações o número de componentes não é conhecido a priori. Neste caso, pode-se executar o algoritmo para diferentes números de componentes e selecionar, dentre elas, qual a melhor de acordo com alguma função de avaliação
função logarítmica de verossimilhança (Bishop, 2006).
4Embora o algoritmo K-means também seja sensível à inicialização do seus parâmetros, por ser eficiente com-
que permita avaliar modelos de diferentes complexidades5. Nesta tese, essa estratégia para encontrar o melhor modelo, quando o número de componentes é desconhecido, é referenciada por Ordered Multiple Runs of Expectation Maximization (OMR-EM). O Algoritmo 1 sumariza esta estratégia, sendo s uma função de avaliação a ser minimizada (um exemplo de função é apresentada na Seção 3.2) e SC é um critério de parada para o EM, e.g., número máximo de
iterações. Na prática, np é usualmente definido de maneira ad-hoc ou considerando os recursos
computacionais disponíveis. Assumindo que np é proporcional a Kmax (número máximo de
grupos), o custo computacional do procedimento é O(N · K2
max· M3)6.
Algoritmo 1: Ordered Multiple Runs of Expectation Maximization (OMR-EM). Entrada: X Conjunto de dados;
KminNúmero mínimo de grupos;
KmaxNúmero máximo de grupos;
np Número de inicializações aleatórias;
SC Critério de parada para o EM;
s Função de avaliação (a ser minimizada);
1 B ← ∅; // Melhor modelo (obtido) 2 para cadai ={1, . . . , np} faça
3 para cadak ={Kmin, . . . , Kmax} faça 4 Inicializa um GMM por meio do K-means; 5 Executa EM em X até que SC seja satisfeito;
6 Seja M o GMM resultante; 7 ses(M) < s(B) então 8 B ← M; 9 fim 10 fim 11 fim 12 Retorna BM
Na procura de se ter métodos que explorem o espaço de busca de forma mais eficiente, con- siderando modificações na solução atual de forma a se obter uma nova que melhor se ajuste aos dados, diversas abordagens foram propostas (McLachlan e Krishnan, 1997; Ueda e Nakano, 1998; McLachlan e Peel, 2000; Ueda et al., 2000; Zhang et al., 2003; Figueiredo e Jain, 2002; Verbeek et al., 2003; Pernkopf e Bouchaffra, 2005; Constantinopoulos e Likas, 2007). Duas abordagens são de interesse nesta tese. A primeira consiste na divisão e união de componen- tes — Split and Merge (SM) — que foi inicialmente apresentada por Ueda et al. (2000). A segunda utiliza algoritmos evolutivos para trabalhar com mais de uma solução (modelo) simul- taneamente (Pernkopf e Bouchaffra, 2005).
O uso do EM para aprender GMM pode ser visto, do ponto de vista de agrupamento de dados, como o particionamento dos dados em K grupos de forma probabilística. Portanto, cada
5A função de verossimilhança não pode ser usada para avaliar modelos de diferentes complexidades por ser
monotonicamente crescente em relação ao número de grupos (Figueiredo e Jain, 2002; Bishop, 2006).
2.3 Procedimentos para União e Divisão de Componentes em Gaussian Mixture Models 15