Probabilistic Graphical Models – Semana 2

Depois de escrever/estudar os vídeos das aulas correspondentes à primeira semana, fui fazer os exercícios práticos e teóricos. Aprendi um pouco sobre Octave e conheci a ferramenta SAMIAM, uma interface gráfica para facilitar a manipulação de redes Bayesianas.

CPD’s Estruturados

Um CPD ou distribuição de probabilidade condicional é normalmente representado através de uma tabela, considerando todas as possíveis combinações de valores das variáveis das quais ela depende. Nesse conjunto de aulas são apresentados outros tipos de CPD’s.

Fundamentos

Um conceito importante que será utilizado nas próximas seções é o de independência para contexto específico (tradução livre de context-specific independence). Em alguns casos duas variáveis são independentes apenas se o valor observado de uma outra variável tiver um valor específico.

Um caso simples onde isso acontece é na rede Bayesiana onde uma variável é o OU de duas outras variáveis, conforme a Figura 1. Inicialmente, x1 e x2 são independentes. Porém, se observarmos y, elas deixam de ser. Por outro lado, se y for igual a 0, as variáveis se tornam independentes novamente, pois “independentemente” do valor da outra variável, sabemos que o valor de x1 ou x2 será 0.

Figura 1: OR determinístico

Podemos pensar nesse tipo de independência como um caso especial de independência condicional. Nesta, para que haja independência, deve haver independência para contexto específico para todas as combinações de valores das variáveis observadas.

CPD’s determinísticos

Um exemplo de CPD determinístico foi apresentado na seção anterior. Nesses casos, não precisamos de uma tabela considerando todas as possíveis combinações de resultados, sendo suficiente a função que descreve uma variável a partir de seus pais.

CPD’s com estrutura de árvore

Em casos em que não há independência condicional entre duas variáveis, mas há independência para um contexto específico, podemos usar uma representação de árvore para diminuir o número de combinações possíveis de entradas a serem consideradas.

Figura 2: CPD em forma de árvore

CPD Multiplexador. Usando a estrutura em árvore, podemos construir uma rede que representa um multiplexador, conforme a Figura 3. A variável A pode assumir valores de 1 a k, enquanto Y pode assumir os valores Z_1 a Z_k. Se a é o valor de A, e y o valor de Y, então y = Z_a. O CPD para Y que modela o multiplexador é simples: P(Y = X_a | A = a) = 1 e P(Y = X_a | A \neq a) = 0 para todo 1 \le a \le k.

Figura 3: Multiplexador

CPD OU ruidoso

Uma generalização do CPD determinístico é o CPD ruidoso (noisy). Um modelo onde esse CPD aparece é quando uma variável Y possui diversas causas X_1, \cdots, X_k e estas podem causar Y de maneira independente. Nesse caso, adicionamos uma “camada” de variáveis Z_1, \cdots, Z_k, onde Z_k é binária, sendo 1 se e somente se, a variável X_k causa Y. Esse novo conjunto de variáveis representa a transmissão de ruídos representados pelo conjunto de variáveis X, por isso o nome.

Também usamos a variável Z_0 para modelar o fato de que Y pode ser causada por outro meio além das variáveis X. Neste modelo, fazemos Y ser um OU determinístico de Z_0, \cdots, Z_k, conforme a Figura 4.

Figura 4: CPD OR ruidoso

Os CPD’s das variáveis Z_k para k > 0 são P(Z_k = 1 | X_k = 0) = 0 e P(Z_k = 1 | X_k = 1) = \lambda_k se X_k = 1, ou seja, podemos ler \lambda_k como a probabilidade da variável X_k causar Y. Para k = 0, P(Z_0 = 1) = \lambda_0.

Assim, é possível escrever o CPD de Y em função de X_1, \cdots, X_k. Temos que

P(Y = 0 | X_1, \cdots, X_k) = (1 - \lambda_0) \prod_{i | X_i = 1} (1 - \lambda_i).

CPD’s para o caso contínuo

Se uma dada variável Y depende de outra variável contínua X, é impossível tabelar todos os possíveis valores de X. Nesse caso, podemos definir Y como uma função de distribuição de probabilidade tendo X como parâmetro.

Um exemplo é usar a distribuiçãoa gaussiana para Y, com a média sendo o valor observado de X e uma variância fixa, ou seja Y \sim \mathcal{N}(X, \sigma^2).

Se Y depende de mais variáveis contínuas, podemos por exemplo usar algum tipo de combinação entre os valores observados para definir a média. Se Y também depende de uma variável discreta, podemos ter um CPD misto, onde as variáveis discretas definem as linhas da tabela e em cada linha existe uma distribuição com diferentes parâmetros.


Redes de Markov

Redes de Markov são representadas por um grafo não direcionado.

Redes de Markov por pares

Redes de Markov por pares. são um caso especial de redes de Markov, onde as relações entre variáveis são sempre entre pares e por isso podemos representá-las através de um grafo não direcionado.

Ao invés de definir fatores sobre os vértices como no caso das redes Bayesianas, definimos sobre as arestas. Nesse contexto, esses fatores são chamados de funções de compatibilidade ou funções afim.

As entradas de um fator entre duas variáveis X_i, X_j, o qual denotamos por \phi(X_i, X_j) , são as possíveis combinações dos valores das variáveis envolvidas.

Fazendo o produto dos fatores do grafo, obtemos \tilde P(X_1, \cdots, X_k) = \prod_{(X_i, X_j) \in E} \phi(X_i, X_j), que é uma medida não normalizada. Seja Z a constante de normalização (também conhecida como função de partição, termo herdado da físisca estatistica), então podemos definir a função de distribuição de probabilidade:

P(X_1, \cdots, X_k) = \tilde P(X_1, \cdots, X_k)/Z

Uma observação é que não há uma correspondência intuitiva entre os fatores e a distribuição de probabilidade P para redes de Markov ao contrário de redes Bayesianas.

Esse modelo não é muito expressivo. Para se ter uma ideia, considere um conjunto de n variáveis com d possíveis valores cada. Mesmo que tenhamos um grafo completo, com O(n^2) arestas e cada uma tendo O(d^2) entradas, a função de distribuição terá O(n^2d^2) entradas, ao passo que poderíamos ter uma com O(d^n).

Distribuição geral de Gibbs

A fraqueza do modelo anterior está na restrição de fatores com apenas duas variáveis. Para remediar isso, podemos usar a distribuição geral de Gibbs, que é uma generalização de redes de Markov por pares. Nesse caso, as arestas podem ser incidentes a mais de dois vértices, como num hipergrafo.

Mais formalmente, temos um conjunto de fatores \Phi = \{\phi_1(D_1), \cdots, \phi_k(D_k)\} onde D_i é o conjunto de variáveis incluídas no fator \phi_i, e é chamada de domínio. A distribuição geral de Gibbs corresponde ao produto de fatores em \Phi normalizado.

Rede de Markov induzida. denotada por H_{\Phi}, é uma rede de Markov por pares com conjunto de vértices correspondente à união dos domínios dos fatores em \Phi e existe uma aresta entre duas variáveis X_i e X_j se X_i, X_j \in D_i para algum \phi_i \in \Phi.

Com isso, podemos apresentar a definição de fatoração para redes de Markov.

Fatoração. Uma distribuição de probabilidade P fatora uma rede de Markov H se existe um conjunto de fatores \Phi = \{\phi_1(D_1), \cdots, \phi(D_k)\} tal que

(1) P = P_{\Phi}
(2) H é o grafo induzido de \Phi.

Note que há perda de informação quando representamos os fatores por uma rede de Markov induzida e portanto não conseguimos recuperar \Phi a partir de H_\Phi.

Entretanto, a relação de influência entre variáveis para uma distribuição de Gibbs pode ser representada por H_\Phi. Para isso, definimos o análogo de caminho ativo como sendo um caminho neste grafo sem nenhuma variável observada. Assim, dizemos que uma variável influencia a outra se existe algum caminho ativo entre elas.

Campos condicionais aleatórios

Campos condicionais aleatórios ou CRF (Conditional Random Field) são semelhantes a uma distribuição de Gibbs, exceto que a normalização é feita de modo diferente. Nesse caso, temos um conjunto de variáveis observadas X e calculamos a constante de normalização somando apenas para as entradas onde X tem o valor observado. A distribuição obtida depois da normalização é condicionada pelo valor das variáveis observadas X.

Mais formalmente, dado o produto de fatores não normalizado:

\tilde P_{\Phi}(X, Y) = \prod_{i =1}^{k} \phi_i(D_i)

A constante de normalização para uma dada observação de X é igual a

Z_{\Phi}(X) = \sum_{Y} \tilde P_{\Phi}(X, Y)

Dessa forma, temos uma distribuição condicional:

P_{\Phi}(Y | X) = \dfrac{\tilde P_{\Phi}(X, Y)}{Z_{\Phi}(X)}

Modelo logístico. (Logistic model ou Logistic regression) é um caso particular do CRF, onde temos uma variável Y conectada a um conjunto de variáveis X_1, \cdots, X_k.

O fator de cada (Y, X_i) é dado por

\phi(X_i, Y) = \exp(w_i 1\{X_i = 1, Y = 1\})

onde 1\{X_i = 1, Y = 1\} é uma função indicador, que retorna 1 se e somente se as variáveis possuem os valores indicados. Nesse caso, o produto dos fatores é:

\tilde P(Y, X) = \exp\{\sum_i (w_i X_i Y)\}

Discriminando por valores, a distribuição de probabilidade de Y = 1 dado X é dada por

P(Y = 1|X) = \dfrac{\tilde P(Y = 1, X)}{\tilde P(Y = 1, X) + \tilde P(Y = 0, X)}

Sendo \tilde P(Y = 0, X) = 1 e \tilde P(Y = 1, X) = \exp\{\sum_i (w_i X_i)\}

Independência em redes de Markov

Na mesma forma que temos a d-separação em redes Bayesianas, temos a separação entre duas variáveis X e Y em uma rede de Markov H dado Z, denotada por \mbox{sep}_H(X, Y | Z), que ocorre quando não existe nenhum caminho ativo entre elas dado Z.

Lema 1. Se P fatora uma rede de Markov H e \mbox{sep}_H(X, Y | Z), então P \models (X \perp Y | Z).

Da mesma forma que para redes Bayesianas, podemos definir o conjunto de independências condicionais sobre H como

I(H) = \{(X \perp Y | Z) : \mbox{sep}_H(X, Y | Z) \}

Se P satisfaz todas as independências de I(H), dizemos que H é um I-mapa (mapa de independência) de P. Logo, usando o Lema 1, temos

Teorema. P fatora uma rede de Markov H, então H é um I-mapa de P.

Inversamente, temos um resultado quase simétrico:

Teorema de Hammersley Clifford. Dada uma distribuição positiva P, se H é um I-mapa de P, então P fatora H.

I-mapas e mapas perfeitos

Nota: essa seção diz respeito a ambas redes Bayesianas e de Markov.

Podemos definir um conjunto de independências condicionais sobre P (ao invés de um grafo) como

I(P) = \{(X \perp Y | Z) : P \models (X, Y | Z) \}

Note que se P fatora uma rede G, então I(G) \subseteq I(P), mas o contrário não é verdade.

Um grafo mais esparso tende a conter mais independências e portanto representar mais precisamente as independências de P. Para isso, podemos remover arestas redundantes até obter um I-mapa minimal, ou seja, um grafo para o qual não existe aresta (X,Y) tal que E(G) \setminus (X, Y) é um I-mapa.

Idealmente, gostaríamos de encontrar um grafo tal que I(G) = I(P), caracterizando um I-mapa perfeito, mas nem toda distribuição admite tal mapa. Também temos o caso de que uma distribuição admite um I-mapa perfeito usando redes Bayesianas (grafo direcionado), mas não usando redes de Markov (grafo não-direcionado). Um exemplo simples é a estrutura em V.

O contrário também pode acontecer. Não é possível capturar exatamente as independências de uma rede de Markov como a da Figura 5, no caso (A \perp C | B, D) e (B \perp D | A, C).

Figura 5: Loop

Uma última definição: Dois grafos G_1 e G_2 são ditos I-equivalentes de I(G_1) = I(G_2).

Modelos Log-Linear

Esses modelos possuem a seguinte forma,

\tilde P = \exp(-\sum_j w_j f_j(D_j)),

onde w_j são chamados coefiecientes e f_j() características (features), com um domínio D_j, que é um conjunto de variáveis.

Esse modelo é bastante expressivo, de movo que podemos representar fatores com ele. Se por exemplo o fator \phi tem como domínio duas variáveis X e Y, tal que \phi(X = x_i, Y = y_j) = \sigma_{ij}, usamos uma função indicador para definir a função característica f_{ij} = 1(X = x_i, Y  = y_i) e coeficiente w_{ij} = \ln(\sigma_{ij}).

Mas o interessante é que podemos modelar apenas valores de variáveis que são relacionados (usando tabelas, teríamos várias entradas com valor 0), como no caso de processamento de linguagem natural. Podemos definir uma característica que retorna 1 se e somente se uma palavra começar com letra maiúscula e o rótulo for pessoa. O coeficiente correspondente captura a correlação entre esses dois valores.

Os comentários estão fechados.

%d bloggers like this: