O raciocínio por trás do Algoritmo Expectation-Maximization
Entendendo as motivações e como o Algoritmo EM funciona
Os algoritmos de clusterização desempenham um papel importante na compreensão dos dados. Entender relacionamentos complexos e detectar semelhanças entre milhares de registros em um conjunto de dados usando apenas ferramentas de visualização é uma tarefa praticamente impossível, principalmente no contexto de dados multidimensionais.
Em geral, tais algoritmos carregam consigo uma série de suposições sobre qual fenômeno probabilístico gerou os dados que eventualmente serão processados.
Neste artigo, vamos falar sobre os aspectos estatísticos do Algoritmo Expectation-Maximization (EM). Durante a leitura, será possível perceber que essa técnica é empregada em problemas de estimativa de densidade. Tais problemas visam representar os dados em uma forma compacta utilizando uma distribuição estatística como Gaussiana, Beta ou Gama.
Podemos pensar nesses problemas como uma tarefa de agrupamento, com uma ótica probabilística. Isso é o que torna o Algoritmo EM um modelo generativo probabilístico.
A expressão “modelo generativo probabilístico” refere-se a um modelo de agrupamento que, em vez de fazer uma atribuição “hard”, onde um cluster é atribuído para cada ponto de dados (por exemplo, K-Means), é referenciada a probabilidade que um determinado ponto pertença a cada cluster, configurando uma atribuição “soft”.
No entanto, sabemos que apenas uma distribuição gaussiana não é capaz de mapear milhares de instâncias de um dataset em K clusters precisamente, nem qualquer outra distribuição sozinha seria. Precisamos de um ferramental mais robusto para isso.
Como você pode ver no gráfico abaixo, neste exemplo precisaríamos de pelo menos 3 clusters para segmentar os dados de maneira viável. Nesse contexto, iniciando nossa discussão, vamos falar sobre Modelos de Mistura (MM) — mais especificamente, Modelos de Mistura de Gaussianas (MMG).
Modelos de Mistura (de Gaussianas)
A construção de um modelo estimador de densidade não pode ser limitada a apenas uma função de densidade de probabilidade. Os Modelos de Misturas lidam com essa limitação, combinando um conjunto de distribuições para criar um espaço convexo de busca de parâmetros ótimos para tais distribuições, baseando-se na Estimativa de Máxima Verossimilhança (EMV).
Modelos de Mistura
Um Modelo de Misturas é expresso pelas seguintes equações:
Onde, K é o número de componentes do modelo (clusters), πⱼ representa o peso do j-ésimo componente no modelo, e cada pⱼ(x) é um membro de uma família de distribuições (Gaussianas, Poisson, Bernoulli, etc.).
Consequentemente, um Modelo de Mistura de Gaussianas (MMG) é um Modelo de Mistura tal que a combinação linear de todos os pⱼ(x) forma uma combinação finita de distribuições gaussianas. Matematicamente, define-se da seguinte forma:
Onde θ é a coleção de todos os parâmetros do modelo (pesos, médias, e matrizes de covariância de cada componente):
A partir desta combinação de distribuições convexas, obtemos uma ferramenta poderosa para representar dados multimodais. O plot a seguir mostra a aparência de um MMG derivado de 3 componentes:
Por design, para cada ponto de dados, x (em vermelho), pode-se calcular a probabilidade que ele pertença a cada componente (realizar uma atribuição “soft”), que será nominada futuramente como responsabilidade.
Por último, a equação (3) fornece a verossimilhança de um ponto x em um MMG. Neste caso particular, podemos reescrevê-la assim:
Encontrando os parâmetros ótimos de um MMG
Suponha que temos um conjunto de dados X de n pontos independentes e distribuídos de forma idêntica (i.d.i.):
O objetivo de um MMG é representar a distribuição desses dados da maneira mais precisa possível. Para chegar a tal representação, é necessário estimar os parâmetros do MMG de forma a maximizar a sua verossimilhança com respeito ao conjunto de parâmetros θ.
Como as amostras são i.d.i, o estimador da máxima verossimilhança sobre X pode ser obtido pelo produto das verossimilhanças individuais de cada ponto. Em outras palavras, podemos expressar a sentença anterior da seguinte maneira — aplicando ainda a função logarítmica para simplificar as equações:
Pela equação (3), sabemos que p(xᵢ|θ) é uma combinação linear de distribuições Gaussianas. Portanto, usando (3) em (5), temos:
Infelizmente, não há solução analítica para a equação (6). Isto é, não existe uma solução fechada para encontrar os parâmetros ótimos em θ, mesmo que se recorra ao procedimento padrão de tomar a derivada de (6) com relação a θ e iguale-a a zero. As equações (7–9) nos mostram como poderíamos fazer isso:
Note que o cálculo de cada parâmetro de θ (μ’s, Σ’s, π’s) depende dos demais parâmetros de uma maneira complexa. É por essa razão que não há solução fechada para essas equações.
No entanto, é possível resolver as equações (7–9) de maneira iterativa, otimizando alguns parâmetros enquanto os demais são mantidos fixos. É com esta motivação que vamos falar do Algoritmo Expectation-Maximization (EM).
O Algoritmo EM
Antes de entrar nos detalhes de como se dá o processo iterativo de encontrar os parâmetros ótimos de um MMG — descrito pelo Algoritmo EM, vamos definir uma quantidade crucial que nos possibilitará reescrever as equações de forma compacta.
Responsabilidades (passo E)
Como vimos anteriormente, um MMG é constituído de várias distribuições gaussianas. A parcela de contribuição de cada Gaussiana sobre a verossimilhança total de um ponto em relação ao MMG é chamada de responsabilidade.
A responsabilidade rᵢⱼ pode ser interpretada como a probabilidade posterior de que o ponto xᵢ tenha sido gerado pelo cluster j. De maneira simples, rᵢⱼ é a probabilidade de que o j-ésimo componente do modelo gerou o ponto xᵢ. Matematicamente, as responsabilidades são dadas pela equação:
Perceba que para calcular cada responsabilidade, precisamos já conhecer o conjunto de parâmetros θ. Portanto, para cada ponto xᵢ, teremos K responsabilidades, que pode ser expresso como um vetor K-dimensional, onde cada posição indica a probabilidade que o ponto xᵢ pertença a cada componente do modelo.
Além disso, da equação (10), ainda podemos definir a responsabilidade total do j-ésimo componente do modelo sobre todo o dataset:
Estimando os parâmetros de um MMG (passo M)
Não vamos abordar aqui todos os detalhes das provas de como os parâmetros ótimos de um MMG são aprendidos de maneira que o logaritmo da verossimilhança seja maximizado com relação a θ, pois elas são longas e merecem um post para si mesmas.
Formalmente, há uma maneira consistente de atualizar os parâmetros individuais de um MMG dados parâmetros μ’s, Σ’s, e π’s inicializados aleatoriamente. As equações (12–14) descrevem como se dá a atualização desses parâmetros:
Note que a atualização de μ, Σ, e π depende das responsabilidades (rᵢⱼ), que por sua vez, dependem de μ, Σ, e π. Por esse motivo não há uma solução fechada para as equações (7–9).
Adicionalmente, as equações (12–14) não buscam maximizar precisamente o logaritmo da verossimilhança sobre θ, dado pela equação (6). Na verdade, essas equações buscam maximizar uma função auxiliar do logaritmo da verossimilhança, a esperança do logaritmo da verossimilhança, que é derivado da equação (6), usando a desigualdade de Jensen. Essa função auxiliar é dada por:
Processo iterativo
O que vimos até este ponto, nos remete a um processo iterativo que pode nos ajudar a resolver o problema de encontrar um conjunto de parâmetros ótimos (locais) θ, o Algoritmo EM.
O Algoritmo EM tem esse nome porque ele consiste em um processo iterativo que alterna entre duas etapas:
Na primeira etapa é realizado o cálculo das responsabilidades individuais (passo E) de cada cluster sobre cada ponto usando os parâmetros (μ, Σ, e π). Na segunda etapa, os parâmetros são atualizados de forma a maximizar a esperança do logaritmo da verossimilhança (passo M) dado pela equação (15).
Os passos E e M são repetidos até que não haja mudança significativa na esperança do logaritmo da verossimilhança, que é calculado sempre após o passo M. Resumindo, o procedimento pode ser descrito como a seguir:
1. Inicialize aleatoriamente os parâmetros μ's, Σ's, and π's;
2. Passo E:
Calcule as responsabilidades para cada ponto xᵢ usando μ, Σ, e π, de acordo com a equação (10):3. Passo M:
Atualize os parâmetros μ, Σ, and π (utilizando as responsabilidades obtidas no passo E) de acordo com as equaões (12-14):4. Repita os passos 2 e 3 até que não haja mudança significativa na função da esperança do logaritmo da verossimilhança de acordo com a equação (15):Este procedimento garante que a esperança do logaritmo da verossimilhança cresça monotonicamente.
O Algoritmo EM foi pensado para ser usado em dados multidimensionais. No entanto, para propósitos de visualização, escrevi o código do algoritmo em Python e usei ele para clusterizar um dataset unidimensional. Os resultados obtidos estão na animação abaixo:
Pode-se ver que o algoritmo levou 41 iterações para convergir definitivamente. No gráfico à direita, podemos ver a evolução da esperança do logaritmo da verossimilhança, aumentando lentamente até eventualmente parar. O código deste exemplo está disponível no meu GitHub.
Considerações finais
O Algoritmo EM é bastante sensível à inicialização dos parâmetros. O que algumas pessoas recomendam que se faça é primeiro executar o Algoritmo K-Means (pois ele tem um baixo custo computacional) e usar os centros finais como as médias iniciais do Algoritmo EM. Fazendo isso, reduz-se substancialmente o número de iterações que o Algoritmo EM levaria para convergir. Adicionalmente, pela minha experiência, é mais fácil encontrar o número apropriado de clusters que deve ser adotado para segmentar o problema usando o K-Means.
O Algoritmo EM é considerado melhor que o K-means porque ele fornece não apenas a informação do centro dos clusters, mas também a informação da dispersão dos dados (variâncias) em torno dos centros.
Além disso, é relativamente fácil adaptar o Algoritmo EM ao setup original do problema de filtros colaborativos para sistemas de recomendação.
Referências
Se você busca uma oportunidade de desenvolvimento, trabalhando com inovação em um negócio de alto impacto, acesse o portal B2W Carreiras! Nele, você consegue acessar todas as vagas disponíveis. Venha fazer parte do nosso time!
