Probabilistic Graphical Models – Semana 9

Este post apresenta as notas de aula da semana 9, a última do curso online Probabilistic Graphical Models.

Aprendizado com dados incompletos

Visão geral

Na prática as amostras com as quais trabalhamos muitas vezes são incompletas, podendo ser oriundas de falhas na aquisição dos dados ou mesmo a presença de variáveis latentes (ocultas) no modelo.

Relembrando, utilizamos variáveis latentes no modelo para simplificá-lo. Considere o exemplo abaixo:

Figura 1: Uso de variáveis latentes simplifica o modelo

No exemplo podemos ver que a introdução da variável H reduz o número de arestas no modelo e consequentemente o número de parâmetros.

Lidando com dados incompletos

Podemos considerar dois casos de falta de informação. Se ela ocorre de maneira independente do valor observado, então basta ignoramos as amostras com dados incompletos. Por outro lado, se existe uma dependência entre a falta de informação e o valor observado, então não podemos simplesmente ignorar amostras defeituosas. Nesse caso precisamos considerar o mecanismo que modela a perda desses dados.

Perda ao acaso ou MAR (Missing At Random) é quando a probabilidade da ausência de um dado é independente de seu valor. Um exemplo simples é quando obtemos amostras de lançamentos de uma moeda. Se em ocasiões aleatórias deixamos de registrar o resultado de um lançamento, então temos um MAR.

Por outro lado, se por algum motivo só deixamos de anotar lançamentos que resultaram em cara, então a probabilidade de ausência do dado é influenciada pelo valor da amostra e nesse caso não temos um MAR.

Com a presença de dados restantes, a função de verossimilhança possui múltiplos ótimos locais. Uma intuição da razão disso é que substituindo o valor de uma amostra está faltando, o valor da verossimilhança continua o mesmo, embora o ponto no espaço que gera esse valor seja diferente. Essa característica é denominada identificabilidade.

Métodos para a otimização de verossimilhança

Uma vez que a função de verossimilhança pode ter vários ótimos locais, podemos usar métodos baseados em gradientes para estimar parâmetros que resultam em bons valores de verossimilhança.

Subida de gradiente

Podemos obter o gradiente usando o resultado do seguinte teorema:

\displaystyle \dfrac{\partial \log P(D| \Theta)}{\partial \theta_{x_i, u_i}} = \dfrac{1}{\theta_{x_i|u_i}} \sum_m P(x_i, u_i | d[m], \Theta)

Onde \theta_{x_i, u_i} representa o parâmetro para a atribuição X_i = x_i e Y_i = y_i no CPD de X_i. Temos que P(x_i, u_i | D, \Theta) representa a probabilidade da atribuição X_i = x_i e Y_i = y_i dadas as amostras e os parâmetros \Theta.

Para cada cálculo do gradiente, é preciso computar essa probabilidade para cada atribuição e para cada amostra d[m]. Usando inferência em uma árvore-clique apenas uma vez para um dado d[m], conseguimos obter P(x_i, u_i | D, \Theta).

As vantagens desse método é que ele pode ser generalizado para CPDs que não são na forma tabular. As desvantagens é que é preciso garantir que os parâmetros encontrados são de fato CPDs e para acelerar a convergência pode ser preciso combinar com métodos mais avançados.

Maximização de Esperança

Como alternativa ao método usando gradientes, existe um método específico para maximizar a verossimilhança que é chamado de maximização de esperança ou EM (Expectation Maximization).

A ideia por trás do método é que estimar parâmetros com dados completos é fácil. Por outro lado, computar a distribuição dos dados incompletos é fácil (via inferência) dados os parâmetros.

O algoritmo pode ser descrito pelos seguintes passos:

  • Escolha um ponto inicial para os parâmetros
  • Itere
    • Passo-E (Esperança): completar os dados restantes fazendo amostragem com os parâmetros atuais
    • Passo-M (Maximização): estimar novos parâmetros usando os dados completos

Vamos detalhar mais os Passo-E e Passo-M:

Esperança (Passo-E). Para cada conjunto de dados d[m] calcule P(X,U | d[m], \theta^t) para todas as atribuições de (X|U). Compute as estatísticas suficientes esperadas ou ESS (Expected Sufficient Statistics) para cada atribuição x, u, dadas por

\displaystyle \bar M_{\theta^t} [x, u] = \sum_{m = 1}^M P(x, u| d[m], \theta^t)

Seja \bar x[m] (\bar u[m]) o conjunto de variáveis de x (u) que estão faltando em d[m]. Podemos concluir que

\displaystyle P(x, u| d[m], \theta^t) = P(\bar x[m], \bar u[m] | d[m], \theta)

Maximização (Passo-M). Calcule a MLE usando as estatísticas suficientes esperadas como se fossem as estatísticas suficientes reais, ou seja,

\theta_{x|u}^{t+1} = \dfrac{\bar M_{\theta^t}[x,u]}{\bar M_{\theta^t}[u]}

A vantagem deste método é que podemos aproveitar algoritmos para calcular a MLE e na prática este método obtém bons resultados rapidamente, nas primeiras iterações. A desvantagem é que nas iterações finais a convergência é lenta.

É possível mostrar que a verossimilhança L(\theta: D) melhora a cada iteração nesse método.

Aspectos práticos da maximização da esperança

Algumas outras considerações práticas do algoritmo EM:

  1. Convergência da verossimilhança não necessariamente implica na convergência dos parâmetros
  2. Executar muitas iterações do algoritmo sobre um conjunto de treinamento pode levar a overfitting
  3. O chute inicial de parâmetros pode afetar bastante a qualidade das soluções obtidas

Referências

[1] Wikipedia – Expectation Maximization

Os comentários estão fechados.

%d bloggers like this: