Probabilistic Graphical Models – Semana 4

Este post apresenta as notas de aula da semana 4 do curso online Probabilistic Graphical Models.

Propriedades da propagação de crença

Para concluir o algoritmo de passagem de mensagens em grafos cluster, vamos apresentar mais algumas definições.

Calibragem. Um cluster grafo é calibrado se para toda aresta (C_i, C_j), ambos têm a mesma crença para as variáveis no sepset entre eles, ou seja, a crença marginalizada de C_i e C_j para S_{ij} é igual.

Matematicamente temos que

\sum_{C_i \setminus S_{ij}} \beta(C_i) = \sum_{C_j \setminus S_{ij}} \beta(C_j)

Podemos mostrar que se houve convergência nas mensagens o grafo cluster está calibrado.

Definimos a crença do sepset como o produto das mensagens trocadas na aresta correspondente, ou seja:

\mu_{ij}(S_{ij}) = \delta_{j \rightarrow i} (S_{ij}) \delta_{i \rightarrow j} (S_{ij})

Reparametrização. é uma propriedade que grafos cluster têm devido à seguinte relação:

\dfrac{\prod_i \beta_i}{\prod_{ij} \mu_{ij}} = \tilde P_{\Phi} (X_1, \cdots, X_n)

O nome da propriedade vem do fato de que esta é uma forma alternativa de parametrizar uma distribuição de probabilidade usando crenças. Essa relação pode ser deduzida da seguinte maneira:

\dfrac{\prod_i \beta_i}{\prod_{ij} \mu_{ij}} = \dfrac{\prod_i (\psi_i \prod_{j \in N_i} \delta_{j \rightarrow i})}{\prod_{ij} \delta_{i \rightarrow j}} =

A observação chave é notar que cada \delta_{i \rightarrow j} tanto do denominador na fração acima, aparece exatamente uma vez para cada aresta. Cancelando os termos, o que sobre é

= \prod_{i} \psi_i = \tilde P_{\Phi} (X_1, \cdots, X_n)

que é definição da distribuição não normalizada.


Passagem de mensagens em Árvore-Clique

No caso particular de um caminho, é fácil mostrar que a crença em um vértice corresponde exatamente à distribuição marginalinada contendo as variáveis desse vértice.

Uma árvore-clique é uma árvore não-direcionada, onde os vértices correspondem a clusteres, a cada aresta está associada um sepset, S_{ij}, que neste caso é exatamente igual a C_i \cap C_j.

Sendo um caso especial de um grafo cluster, temos que satisfazer as propriedades mencionadas no último post, mais especificamente, a preservação de familiar e o caminho de interseções.

Note que a unicidade de caminhos é trivialmente garantido numa árvore, mas para que a propriedade do caminho de interseções ocorra, aindas precisamos garantir que vértices contendo uma mesma variável X estão conectados por um caminho contendo X.

Estas propriedades são suficientes para garantir que a crença obtida ao final do algoritmo corresponda às distribuições marginalizadas para as variáveis no cluster. Para esse tipo especial de grafo, o algoritmo de passagem de mensagem é uma variante do algoritmo de eliminação de variáveis.

Algoritmo de passagem de menssagem

Dizemos que uma mensagem é final se ela não se modificará independente de quantas iterações do algoritmo de passagem de mensagens sejam executadas. Com essa definição, temos a seguinte propriedade:

Propriedade 1. quando um vértice C_i recebe mensagens finais de todos os seus vizinhos exceto C_j, então \delta_{i \rightarrow j} é final.

Vamos apresentar um algoritmo de passagem de mensagem para árvores-cliques que se beneficia dessa propriedade, para obter mensagens finais usando apenas uma iteração. Primeiramente, note que uma folha da árvore satisfaz a Propriedade 1 acima trivialmente para seu único vizinho C_j.

A primeira parte do algoritmo consiste em sempre processar folhas dessa árvore, enviando a mensagem para seu vizinho e removendo-a em seguida. É fácil ver que as folhas do grafo resultante vão enviar mensagens finais para seu único vizinho, já que por hipótese, todos os seus outros vizinhos já lhe enviaram suas mensagens.

Desta maneira, eventualmente processaremos todos os vértices, obtendo as mensagens finais de cada aresta, porém em apenas uma das direções. Como fazer para obter as mensagens na direção oposta?

Considere o último vértice v' a ser processado no algoritmo acima. Temos que todos os seus vizinhos no grafo original já lhe enviaram mensagens na primeira etapa. Assim, todas as mensagens enviadas por v' a partir de agora são finais, devido à Propriedade 1.

Seja v'' o penúltimo vértice removido. Se ele enviou mensagem para v', então agora v' já lhe enviou uma mensagem de volta. Independentemente de ter enviado a mensagem para v' ou não, agora qualquer mensagem enviada por v'' é final.

Esse argumento construtivo nos sugere a segunda parte do algoritmo: processar os vértices na ordem reversa daquela da primeira etapa e cada vértice processado deve enviar uma mensagem para todos os que lhe enviaram mensagem na primeira fase.

Note portanto, que é possível encontrar uma ordem de passagem de mensagens em uma árvore de modo que com apenas uma iteração e todas as mensagens sejam finais. Note que nesta única iteração, foram enviadas exatamente 2(n-1) mensagens, onde n é o número de vértices/clusters.

Consultas

Uma vez calculadas as crenças nos clusters, podemos fazer consultas do tipo P(Y|E=e). Supondo que faremos essa consulta várias vezes para diferentes valores de e, podemos usar o algoritmo acima como um pré-processamento.

Uma vez calculadas as crenças, se existe uma clique contendo Y e E, podemos simplesmente marginalizar a crença para ficar com \tilde P(Y,E) e então remover as entradas E \ne e (reduzir).

Por outro lado, se não existe uma clique contendo Y e E, teremos que considerar duas cliques, uma contendo Y, denotada por C_Y e outra contendo E, denotada por C_E. Primeiramente, reduzimos a crença em C_E, o que ocasionará uma mudança nas mensagens enviadas por esse cluster e depois fazer a consulta no cluster C_Y. Entretanto, nesse caso é possível reaproveitar até n-1 sem recomputá-las.

Para isso, na primeira fase do algoritmo acima, o último vértice a ser processado deve ser C_E (note que é sempre possível escolher uma ordem de processamento em que isso acontece). Nenhuma das n-1 mensagens enviadas nessa primeira etapa partiu de C_E e portanto não dependem de \psi(C_E). Logo, só a segunda etapa do algoritmo precisa ser recomputada para cada consulta de E = e.

Porém, essa ideia é atrelada ao conjunto E. Se a consulta for feita usando outro conjunto de observação, a primeira fase deverá ser computada novamente.

Árvores-clique e independência

Seja T uma árvore-clique e (C_i, C_j) uma aresta de T. Como T satisfaz as propriedades de preservação familiar e o caminho de interseções, podemos particionar o conjunto de variáveis em três conjuntos.

Considere as duas componentes resultantes da remoção da aresta (C_i, C_j), denotando por W_i aquela que contém C_i e W_j aquela que contém C_j.

Seja W_{<(i,j)} o conjunto de variáveis que pertencem a algum cluster em W_i, mas não pertencem a S_{ij}, ou seja, W_{<(i,j)} = (\cup_{C \in W_i} C) \setminus S_{ij}

Analogamente, defnimos W_{<(j,i)} como W_{<(j,i)} = (\cup_{C \in W_j} C) \setminus S_{ij}

Observamos que W_{<(i,j)} e W_{<(j,i)} são disjuntos. Caso contrário, existiria uma variável X em W_{<(i,j)} e em W_{<(j,i)}, mas não em S_{i,j}. Isso implica que não existe um caminho contendo X conectando esses dois clusters em que X aparece, contradizendo a hipótese de que a árvore satisfaz a propriedade do caminho de interseções.

Com essa observação, podemos ver que esses três conjuntos particionam, de fato, o conjunto de variáveis em T. O seguinte teorema associa a ideia de independência ao sepset:

Teorema: Uma árvore T satisfaz a propriedade de caminhos de interseção ou RIP (Running intersection property) se e somente se, para toda aresta (i,j), P_\Phi \models (W_{<(i,j)} \perp W_{<(j,i)} | S_{ij})

Podemos ver que em uma árvore-clique correta, se observarmos as variáveis no sepset, as variáveis nas componentes W_{<(i,j)} e W_{<(j,i)} tornam-se independentes. O nome sepset agora fica sugestivo como conjunto separador.

Árvore-clique e eliminação de variáveis

Podemos construir uma árvore-clique a partir dos fatores intermediários obtidos no algoritmo de eliminação de variáveis.

Recapitulando, a cada passo i escolhemos uma varíavel Z para ser eliminada, obtendo um fator

\Phi'_i = {\phi_k \in \Phi_i | Z \in \mbox{Escopo}(\phi_k)}

\psi_i = \prod_{\phi_k \in \Phi_i'} \phi_k

\lambda_i = \mbox{Escopo}(\psi_i)

\tau_i = \sum_{Z} \psi_i

\Phi_{i+1} \leftarrow  \Phi_i \setminus \Phi' \cup \{\tau_i\}

Nesse caso, construímos uma árvore-clique onde os clusters correspondem às variáveis em \lambda_i os quais denotamos por C_{\lambda_i}. Existe uma aresta entre um cluster C_{\lambda_i} e C_{\lambda_j} se \tau_i foi usado no produtório para calcular \psi_j. Nesse caso, o sepset é igual ao domínio de \tau_i.

Após a construção dessa árvore-clique, pode haver clusters que são subconjuntos de outros cluster, o que é redundante. Assim, uma fase de pós-processamento consiste em removê-los.

Propriedades

O grafo cluster resultante é de fato uma árvore porque um \psi_i é usado em exatamente uma vez em alguma iteração posterior j > i. Sendo n o número de iterações, podemos ver que o grafo tem n-1 arestas e n nós e também não possui ciclos, logo concluímos que é uma árvore.

É possível ver que o grafo resultante respeita a preservação de família pois todo fator usado no algoritmo possui um escopo que é subconjunto de algum \lambda_i.

Temos também que o grafo resultante respeita a propriedade de caminho de independência. Considere uma variável X que aparece em dois clusters diferentes, C_i e C_j. Segundo o algoritmo, existe um caminho contendo X de cada um desses clusters até o cluster onde essa variável é eliminada. Assim, como C_i e C_j têm caminhos com vértice em comum na árvore, podemos concluir que existe um caminho único entre estes dois clusters.

Complexidade

Podemos reduzir a eliminação de variáveis para o algoritmo de passagem de mensagens em uma árvore-clique. Para calcular a marginalização de um conjunto de variáveis usamos aproximadamente o mesmo número de operações em ambos os casos. A vantagem da passagem de mensagens é o re-uso de mensagens no caso de querermos computar a maginalização de outro conjunto de variáveis.

Propagação de Crença na prática

Em um dos vídeos são discutidos aspectos práticos da propagação de crença, como convergência e corretude.

Variantes do BP

Há dois principais meios de passagem de mensagem: síncrono e assíncrono. No caso síncrono as mensagens são enviadas ao mesmo tempo enquanto no assíncrono as mensagens são enviadas em ordem.

A vantagem do caso síncrono é que o algoritmo é facilmente paralelizável. Porém, na prática o assíncrono tende a convergir mais rápido. O problema da abordagem assíncrona é que a convergência e corretude dependem da ordem utilizada para passar as mensagens.

Heurísticas

Há algumas heurísticas para a escolha da passagem das mensagens. Uma delas é o TRP (Tree reparametrization) que consiste em cada iteração escolher árvores geradoras e usar o algoritmo de árvore-clique. Outra abordagem é passar mensagens por arestas entre clusters com a crença marginalizada para o sepset mais distantes.

Outras alternativas consistem em modificar o modo como a mensagem é calculada na tentativa de obter convergência. Uma delas é as mensagens suaves (smoothing messages), onde uma mensagem é construída com uma combinação convexa (suavização) entre seu valor anterior e o novo valor, ou seja,

\delta_{i \rightarrow j} \leftarrow \lambda (\sum_{C_i \setminus S_{ij}} \psi_i \prod_{k \neq j} \delta_{k \rightarrow j}) + (1 - \lambda) \delta_{i \rightarrow j}^{old}

Conclusão

A ordem de passagem de mensagens usada pelo algoritmo em árvores-cluster não foi muito detalhado e aqui apresentei uma versão própria que me pareceu correta. Entretanto para consultas, este algoritmo é atrelado ao conjunto observado E, sendo necessário computar todas as mensagens novamente quando muda E. Porém, acho que é sempre possível aproveitar as mensagens computadas na primeira fase, independente de E.


Inferência de MAP

Vamos agora focar no tipo de consulta de probabilidade a posteriori máxima ou MAP, ou seja,

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

Algoritmos Max-Soma

Dada uma distribuição P_\Phi(X) \propto \prod_k \phi_k (D_k), queremos calcular a entrada x para a qual P_\Phi(X=x) é máxima. Vimos que isso é equivalente a

\mbox{argmax} \prod_k \phi(D_k)

Agora, vamos transformar o produtório em somatório. Seja \theta_k = \log (\phi_k). Podemos reescrever a equação acima como:

\mbox{argmax} \sum_k \theta(D_k)

A razão para usar log é por questões práticas. Como não estamos interessados no valor da distribuição máxima e sim na atribuição que corresponde a esse valor, não precisamos ficar lidando com multiplicações, que é computacionalmente mais custoso do que somas.

Podemos definir operações análogas ao processo de obtenção de probabilidades marginais. O produto de fatores agora corresponde à soma de log de fatores. Vamos definir um análogo à distribuição de probabilidade conjunta:

\theta(X) = \sum_k \theta(D_k).

Da mesma forma, a marginalização, que é a eliminação de um conjunto de variáveis, pode ser definida para o MAP. Lembrando, dado um fator \phi com domínio Z e um conjunto de variáveis X que queremos remover via marginalização, o que fazemos é somar entradas de \phi com valores de Z \setminus X iguais. Agora, definimos a marginalização-max como o máximo entre as entradas de phi com valores de Z \setminus X iguais.

A ideia dos algoritmos que iremos apresentar é obter um fator com um conjunto menor de variáveis Y sobre o qual se deseja fazer a consulta MAP(Y|E=e). Como estamos trabalhando com somas seguidas da função max, temos os algoritmos max-soma.

Os algoritmos de eliminação de variável e passagem de mensagens pode ser adaptados para esse caso, trocando o produto de fatores pela soma do log de fatores e na marginalização a função soma é trocada pela função max. E no caso da passagem de mensagem, as crenças agora correspondem a distribuição de probabilidade max-marginal.

Obtendo a atribuição MAP

Para este caso existe uma propriedade interessante quando o grafo cluster está calibrado. Considere os clusters adjacentes latex C_i = \{A, B\} e C_j = \{B, C\}. Se o sepset entre C_i e C_j é \{B\}, então a crença marginalizada para B de C_i e C_j são iguais.

Seja b^* o valor para o qual a crença marginalizada para B é máxima e seja tal valor P^*. Isso quer dizer que existe uma entrada na crença \beta_i com valor (a^*, b^*) tal que \beta_i(a^*, b^*) = P^* e em \beta_j existe (c^*, b^*) tal que \beta_j(c^*, b^*) = P^*.

Dessa forma, podemos obter a atribuição de A, B, C que geram MAP, simplesmente encontrando a atribuição em \beta_i e \beta_j separadamente.

Porém, isso só funciona se existir uma única atribuição que gere o valor máximo. Do contrário, podemos usar algumas alternativas como perturbação dos fatores para garantir uma atribuição ótima única; ou ao construir a atribuição ótima incrementalmente, armazenar os valores já atribuídos e ao processar uma nova clique verificar a consistência dos valores.

Os comentários estão fechados.

%d bloggers like this: