Probabilistic Graphical Models – Semana 3

Este post apresenta as notas das aulas da semana 3.

Engenharia do conhecimento

Essa aula discute aspectos práticos da modelagem por redes Bayesianas ou de Markov. Não existe necessariamente um modelo correto, o que caracteriza a tarefa de criação desses modelos como uma arte e não como uma ciência.

Os modelos podem ser classificados em diversos tipos, dependendo de suas características. A seguir são descritas situações em que um tipo é mais indicado que outro, servindo mais como guia, não como regra, notando também que é possível usar modelos híbridos.

Template vs. específico. Se o problema possui variáveis com características compartilhadas, é possível usar um modelo por templates, que tem um número menor de variáveis em comparação com um modelo específico, que possui um número grande de variáveis distintas.

Generativo vs. discriminativo. Um modelo discriminativo é mais apropriado quando se tem uma tarefa particular. Nesse caso definimos características bem precisas, de modo a ter baixa correlação entre elas. Isso em geral garante um bom desempenho do modelo. Por outro lado, um modelo generativo é usado quando a tarefa não está bem especificada, pois ele é mais flexível e mais fácil de treinar.

Tipos de variáveis

Podemos classificar as variáveis de um modelo em 3 tipos:

  • alvo – as que queremos prever (saída)
  • observadas (entrada)
  • latente – escondidas. Não são explicitamente usadas, mas podem ser usadas para simplificar o modelo. Como no exemplo da Figura 1, onde a variável GMT serve apenas para não termos que definir a dependência entre W_1, \cdots W_k explicitamente usando arestas.

Figura 1: Varíavel GMT é latente

Estrutura

Em especial para redes Bayesianas, decidir a causalidade, ou seja, a orientação das arestas, não é uma tarefa simples. Dependendo da escolha, podemos ter um modelo maior ou menor. Por exemplo, se no exemplo da Figura 1 quiséssemos inverter a orientação das arestas, tornaríamos as variáveis W indpendentes, o que exigiria adicionar novas arestas entre elas.

Refinamento iterativo do modelo

Uma abordagem na criação dos modelos é o uso de iterações para refinar o modelo e ajustar parâmetros.

Na minha opinião, a modelagem de redes Bayesianas principalmente, lembra muito a modelagem de classes em engenharia de sofware, onde precisamos decidir o relacionamento entre classes (arestas) e sua hierarquia (orientação). Processos iterativos são bastante utilizados nesses casos também.


Consultas de probabilidade condicional

Uma operação comum em redes Bayesianas e de Markov é determinar a distribuição de probabilidade dado uma obervação. Suponha que queiramos determinar a distribuição de um conjunto de variáveis Y dado uma evidência E = e, ou seja, queremos calcular P(Y|E = e).

Uma alternativa é calcular a distribuição conjunta e depois fazer operações de marginalização e redução. Porém, vimos que o tamanho de um fator é exponencial no número de variáveis do modelo. Será que não há um meio mais eficiente, visto que estamos interessados em apenas uma consulta específica?

Provavelmente não, pois esse problema é NP-difícil. Mesmo o problema de, dada uma rede \Phi, decidir se P_\Phi(X = x) > 0 para um dado x é NP-difícil.

Muitos algoritmos exatos ou heurísticos usados para calcular essa distribuição são chamados de soma-produto. Isso porque a distribuição conjunta é equivalente à mulitiplicação dos fatores e a marginalização corresponde à soma de entradas do fator resultante, ou seja, temos a soma de produtos.

Vamos formalizar essa ideia. Usando a definição de probabilidade condicional, temos

P(Y | E = e) = \dfrac{P(Y, E = e)}{P(E = e)}

A distribuição P(Y, E = e) pode ser obtida a partir da distribuição conjunta removendo-se as variáveis do modelo W que não estejam nem em Y nem em E, ou seja, W = \{X_1, \cdots, X_n\} - Y - E, através de marginalização.

P(Y, E = e) = \sum_W P(Y, W, E=e)
\quad = \sum_W (\prod_{\phi_k \in \Phi} \phi_k(D_k, E = e))

Note que P(E = e) é equivalente a uma constante de marginalização. Como sabemos que P(Y | E = e) é uma distribuição, suas entradas devem somar 1, não precisamos calcular P(E = e) bastando re-normalizar P(Y, E = e).

Probabilidade a posteriori máxima

Outra consulta que podemos querer fazer em uma rede é a probabilidade a posteriori máxima ou MAP (Maximum a Posteriori). Essa consulta basicamente consiste em dizer qual o valor de maior probabilidade dado um conjunto de evidência e é importante para decidir o valor de uma variável.

Matematicamente podemos definir um MAP como:

\mbox{MAP}(Y|E=e) = \mbox{argmax}_y\{P(Y = y | E = e)\}

Nesse caso, temos que Y = \{X_1, \cdots, X_n \} - E.

Infelizmente, dada uma rede com distribuição \Phi, determinar uma atribuição x tal que P_\Phi(X = x) é máximo, também é NP-difícil.

Para esse problema, os algoritmos exatos e heurísticos são baseados em max-produto, pois consistem em encontrar o valor máximo de um produto de fatores. Note que nesse caso não temos soma (marginalização), pois não há nenhuma variável fora de Y e E a ser removida. Já vimos que:

P(Y | E = e) = \dfrac{P(Y, E = e)}{P(E = e)} \propto P(Y | E = e)

Também temos que P(Y, E = e) corresponde ao produto de fatores reduzidos, ou seja, sem as entradas correspondentes E \neq e. Vamos denotar por \phi'_k(D'_k) o fator reduzido \phi_k(D_k)

P(Y, E = e) = \frac{1}{Z} \prod_{k} \phi'_k(D'_k) \propto \prod_{k} \phi'_k(D'_k)

Para encontrar a variável que maximiza uma função, não importa a constante multiplicativa, de modo que

\mbox{argmax}_Y \{P(Y|E=e)\} = \mbox{argmax}_Y \{\prod \phi'_k (D'_k)\}


Eliminação de variáveis

Definidos esses dois problemas NP-difíceis, vamos apresentar algoritmos para resolvê-los. Primeiramente, vamos nos concentar na consulta de probabilidade condicional.

O algoritmo de eliminação de variáveis consiste em determinar a marginalização do produto de fatores, eliminando uma variável de cada vez, ao mesmo tempo em que calcula o produtório. Note que as variáveis podem ser eliminadas em qualquer ordem. Entretanto, veremos que a ordem em que as mesmas são eliminadas pode afetar a complexidade do problema.

Um passo do algoritmo é sucintamente descrito a seguir. Seja Z a variável que queremos eliminar. Denotamos por \Phi' todos os fatores quem têm Z em seu domínio, ou seja,

\Phi' = \{\phi_i \in \Phi : Z \in \mbox{Escopo}[\phi_i]\}

Multiplicamos esses fatores e obtemos um fator \psi:

\psi = \prod_{\phi_i \in \Phi'} \phi_i

Podemos fazer então a marginalização para remover Z, gerando um novo fator \tau:

\tau = \sum_{Z} \psi

Perceba que reduzimos a um novo problema com um conjunto de fatores sem a variável Z. Procedendo dessa maneira, eventualmente chegaremos no fator final.

\Phi := (\Phi \setminus \Phi') \cup \{\tau\}

Observamos que esse algoritmo funciona tanto para BN’s quanto para MN’s.

Complexidade

Podemos provar que a complexidade do algoritmo é O(Nm), onde N é o número de entradas do maior fator, m é o número de fatores. Entretanto, N \in O(d^r), onde d é a cardinalidade da maior variável e r é o tamanho do maior domínio considerando todos os fatores.

O tamanho do maior domínio depende da ordem em que as variáveis são eliminadas.

Encontrando uma ordem de eliminação

Vamos apresentar um algoritmo que visa encontrar uma ordem para melhorar a complexidade do algoritmo de eliminação de variáveis. Para isso, é conveniente definirmos grafos auxiliares.

Rede de Markov induzida. Da mesma forma que definimos uma rede de Markov induzida para a distribuição de Gibbs, podemos defini-la para uma rede Bayesiana se olharmos apenas os fatores. Lembrando, esse grafo induzido tem conjunto de vértices correspondendo às variáveis e uma aresta entre duas variáveis que aparecem no domínio de um mesmo fator.

Um detalhe é que duas variáveis que não estão conectadas no grafo induzido original, podem aparecer no domínio dos fatores intermediários gerados ao longo do algoritmo. Nesse caso, adicionamos novas arestas ao grafo, que serão chamadas arestas de preenchimento (fill edges).

O grafo induzido final é denotado por I_{\Phi,\alpha}, dado um conjunto de fatores \Phi e uma ordem \alpha. É fácil ver que todo fator usado no algoritmo de eliminação de variável corresponde a uma clique em I_{\Phi,\alpha}.

Contrariamente, temos outra observação que não é tão trivial de ver:

Teorema. toda clique maximal em I_{\Phi,\alpha} é um fator produzido durante o algoritmo.

Vamos definir mais alguns termos. A largura do grafo induzido corresponde ao tamanho da maior clique no grafo menos 1. A largura induzida minimal é a menor largura de I_{\Phi,\alpha} considerando todas as ordenações \alpha. Com isso, podemos enunciar o seguinte teorema:

Teorema. Encontrar a ordem de eliminação que gere a largura induzida minimal de I_{\Phi,\alpha} é NP-difícil.

Note porém que mesmo com uma ordem ótima, o problema de decidir a inferência ainda pode ser exponencial.

Heuristicas

Há diversas heurísticas para encontar uma boa ordem de eliminação. Apresentamos a seguir algumas gulosas baseando-se em critérios como:

  • escolha do vértice que produz o fator de menor domínio;
  • escolha do vértice que produz o fator com menor número de entradas;
  • escolha do vértice que produz o menor número de arestas de preenchimento.

Há também uma outra heurística baseada no seguinte teorema:

Teorema. O grafo induzido I_{\Phi,\alpha} é triangulado, i.e., não possui ciclos de tamanho maior que 3.

A heurística consiste então em encontrar uma triangulação com pouca largura do grafo induzido original e então é possível obter uma ordem que gera esse grafo.

Conclusões

Fiquei curioso para saber qual é a redução utilizada para mostrar a NP-completude dos problemas. Se eu tiver um tempo vou pesquisar.

A última observação ficou meio nebulosa. Como obter uma ordenação de um grafo triangulado?


Algoritmo de Passagem de mensagem

Nesta seção é apresentado um algoritmo baseado em passagem de mensagem entre vértices de um grafo. Trata-se de um algoritmo heurístico para obter distribuições marginalizadas de um dado subconjunto de variáveis.

Vamos a algumas definições.

Grafo cluster. Grafo não direcionado, onde o conjunto de vértices são clusters (subconjuntos de variáveis). Associadas às arestas, temos um subconjunto de variáveis chamado sepset, denotado por S_{i,j} \subseteq C_i \cap C_j

Dado um conjunto de fatores \Phi, atribuímos cada \phi_k \in \Phi a um cluster C_{\alpha(k)}, tal que \mbox{escopo}[\phi_k] \subseteq C_{\alpha(k)}, onde \alpha(k) corresponde ao índice do cluster ao qual o fator k foi atribuído.

Definimos o potencial de um cluster C_i, denotado por \psi(C_i) como o produto dos fatores atribuídos a ele, ou seja, \psi(C_i) = \prod_{k: \alpha(k) = i} \phi_k

Definimos a passagem de mensagens entre dois clusters C_i e C_j como um fator dado sucintamente por

\delta_{i \rightarrow j} (S_{ij}) = \sum_{C_i \setminus S_{ij}} \psi(C_i) \prod_{k \in (N(i) \setminus \{C_j\})} \delta_{k \rightarrow i}

lembrando que S_{ij} é o sepset e corresponde ao conjunto de variáveis que se quer transmitir. N(i) é o conjunto de vizinhos de C_i.

Em palavras, a definição de uma mensagem entre C_i e C_j é o produto do potencial de C_i (\psi(C_i)) pelas mensagens recebidas dos vizinhos de C_i exceto C_j, marginalizado para ficar com domínio igual a S_{ij}.

A crença (belief) de um cluster C_i, denotada por \beta(C_i) é definida como:

\beta(C_i) = \phi(C_i) \prod_{k \in N(i)} \delta_{k \rightarrow i}

ou seja, o produto de todas as mensagem recebidas dos vizinhos de C_i e seu potencial.

Com isso, podemos definir o algoritmo de propagação de mensagens. Basicamente, inicializamos cada vértice do grafo com o fator nulo e efetuamos trocas de mensagens por um certo número de informações.

Algoritmo de propagação de crenças.

  • Atribua cada fator \phi_k \in \Phi para cada cluster C_{\alpha(k)}
  • Construa os potenciais \psi(C_i)
  • Inicializa todas as mensagens com 1 (equivalente ao fator nulo)
  • Repita:
    • Selecione uma aresta (i,j) e faça a passagem de mensagem, atualizando \delta_{i \rightarrow j}
  • Calcule a crença de cada cluster \beta(C_i)

Alguns detalhes que o algoritmo não especifica é: quantas vezes iterar? Uma observação é que o algoritmo pode não convergir. Além disso, como escolher a ordem das arestas? Uma sugestão é o uso do Round-Robin.

Propriedades dos grafos cluster

Um grafo cluster deve possuir as seguintes propriedades.

Preservação de família. (family preservation) Para cada fator \phi_k \in \Phi, deve existir um cluster C tal que \mbox{Escopo}[\phi_k] \subseteq C, para que possamos atribuir o fator a algum cluster.

Caminho de Interseções. (tradução livre de Running Intersection) Essa propriedade diz que para cada par de vértices C_i e C_j no grafo e uma variável X \in C_i \cap C_j, deve existir um único caminho entre C_i e C_j tal que X \in S_{u,v}, para toda aresta (u, v) neste caminho.

Intuitivamente, isto serve para garantir que X possa ser “transportado” entre C_i e C_j. Por outro lado, a existência de mais de um caminho implica em ciclos, o que poderia causa uma retro-alimentação indesejável.

Uma forma alternativa de definir essa propriedade é através da decomposição em árvore, que diz que para cada variável X, o conjunto de vértices e arestas que contêm X, (\{C_k | X \in C_k\} e \{(i,j) | X \in S_{ij}\}, respectivamente), devem formar uma árvore.

Construção de um grafo cluster

Grafo cluster Bethe. é um tipo especial de grafo cluster bastante simples de construir e que satisfaz as duas propriedades definidas acima. Ele é composto de dois tipos de vértices:

Clusters grandes correspondendo ao domínio de cada fator, ou seja, C_{\phi_k} = \mbox{Escopo}(\phi_k) e clusters pequenos, formado por apenas uma variável, C_i = \{X_i\}.

Existe uma aresta (C_{\phi_k}, C_{i}) se X_i \in C_k.

É fácil ver que esse grafo satisfaz a propriedade dos caminho de interseções, pois ao isolarmos uma variável, o conjunto de vértices e arestas que a contém é uma estrela.

Conclusões

Não ficou muito claro como podemos usar esse segundo algoritmo para calcular uma distribuição de probabilidade condicionada a uma observação, por exemplo P(Y|E=e). Pelo que entendi, a crença de um cluster representa a distribuição marginalizada das variáveis contidas nele.

Assim, podemos inicialmente reduzir os fatores removendo as entradas tais que E \neq e e adicionar um cluster contendo Y. Executamos o algoritmo e fazemos a consulta da crença neste cluster.

Os comentários estão fechados.

%d bloggers like this: