Probabilistic Graphical Models – Semana 1

Amanhã coemçam as aulas do Probabilistic Graphical Models. Vou usar o blog para registrar e organizar minhas anotações sobre o curso.

Segundo o calendário serão 10 semanas de aulas, com exercícios teóricos e práticos, além de uma prova final no começo de Junho.

Como a recomendação é dedicar de 10 a 15 horas semanais para estudo e provavelmente só conseguirei estudar aos finais de semana, decidi não fazer o curso de processamento de linguagem natural.

Como o material da primeira semana já está disponível, decidi me adiantar.

Revisão

Na série de vídeos “Introduction and Overview” são apresentados o conceito do PGM e suas aplicacões e são revisados conceitos básicos de probabilidade como funções de distribuição de probabilidade, variáveis aleatórias, probabilidade condicional.

São introduzidas definições que eu não conhecia: fatores (factors), que são funções que recebem como entrada todas as combinações dos valores de um conjunto de variáveis aleatórias e retornam um escalar. Esse conjunto é denominado escopo (scope).

Podemos pensar em fatores como sendo tabelas. Isso torna mais fácil entender a definição das três operações apresentadas sobre fatores: produto de fatores, marginalização de fatores e redução de fatores.

O produto de dois fatores A e B é um fator C cujo escopo é a união dos escopos de A e B. O valor retornado por C para uma dada entrada i é dado pela multiplicação dos valores retornados por A e B para as entradas que são subconjuntos de i.

A marginalização de um fator A consiste em gerar um fator A’ com um subconjunto do escopo de A. O valor de uma entrada i’ para A’ é dado somando-se os valores das entradas de A das quais i’ é subconjunto.

A redução de um fator A é um fator A’ com o valor de algumas das variáveis do domínio de A fixas. O valor da entrada i’ para A’ corresponde ao valor obtido de uma entrada de A correspondente a i’ mais os valores fixados. Parece uma generalização da distribuição de probabilidade condicional.


Redes Bayesianas

Uma rede bayesiana é um grafo direcionado acíclico (DAG). Os vértices são as variáveis aleatórias e existe uma aresta (u, v) se a variável aleatória v depende de u. Associado a cada vértice temos uma distribuição de probabilidade condicional (CPD).

Regra da cadeia para redes bayesianas. A regra da cadeia é utilizada para calcular a distribuição de probabilidade conjunta (joint probability distribution), ou seja, uma distribuição de probabilidade considerando todas as variáveis aleatórias da rede. Basicamente, o que a regra diz é esta distribuição pode ser obtida multiplicando-se os CPD’s usando produto de fatores.

Se uma distribuição P é obtida via multiplicação dos CPD’s dos vértices de uma rede bayesiana G, dizemos que P fatora (factorizes) G.

Note que dada a distribuição de probabilidade conjunto, podemos determinar a probabilidade de cada nó via marginalização.

Padrões de inferência

Inferência ocorre quando observamos (ou seja,fixamos o valor de) uma variável aleatória X e isso afeta a distribuição de probabilidade de outra variável Y. Em uma rede bayesiana, podemos classificar inferências de acordo com a relação entre as variáveis X e Y no grafo.

Inferência causal (causal reasoning) é quando a variável X observada é ancestral da variável Y.

Inferência probatória (evidential reasoning – tradução correta?) é quando a variável X é descendente da variável Y.

Inferência intercausal (intercausal reasoning) é quando as variáveis X e Y não estão conectadas por um caminho direcionado.

Fluxo de influência

Dizemos que existe um fluxo de influência de uma variável X para Y, se a observação de X influencia a distribuição de probabilidade de Y. Esse fluxo depende também de quais outras variáveis da rede além de X são observadas. Nos referimos então a conjunto de evidências como o conjunto das variáveis da rede observadas e que chamaremos de Z.

O fluxo de influência é representado por um caminho (não necessariamente direcionado) no grafo, o qual é chamado de caminho ativo (active trail). Sejam X, W e Y variáveis correspondendo a vértices consecutivos em um caminho. As possíveis relações entre elas são:

  1. X \rightarrow W \rightarrow Y
  2. X \leftarrow W \leftarrow Y
  3. X \leftarrow W \rightarrow Y
  4. X \rightarrow W \leftarrow Y

Vamos apresentar as condições em que há passagem de fluxo por X, W e Y. Para o caso 1, 2 e 3, temos passagem de fluxo se e somente se W não está em Z. Intuitivamente, se W é observado, ele mesmo exercerá influência daqui pra frente no caminho.

O caso mais contra-intuitivo é o caso 4, que é conhecido como estrutura em V. Em geral, se sabemos alguma coisa sobre X, isso não afeta nosso conhecimento sobre Y. Porém, se sabemos algo sobre W, um conhecimento sobre X, pode afetar o conhecimento sobre Y.

Um bom exemplo é dado no final da aula “Reasoning Patterns“. É dada a estrutura da Figura 1, onde y = x1 | x2. Se soubermos o valor de y, saber o valor de x1 vai alterar a probabilidade do valor de x2.

Figura 1: Rede bayesiana para um or

Assim, a regra para o caso 4 é que W e/ou algum de seus ancestrais estejam em Z. Finalmente, um caminho cujas triplas de vértices consecutivos respeitem as condições de fluxo, é um caminho ativo.

Independência

Independência condicional. Quando duas variáveis aleatórias X e Y são independentes para uma distribuição P, dizemos que P satisfaz X independente de Y, ou que P \models X \perp Y (latex: P \models X \perp Y). A independência entre X e Y dada a observação de uma variável Z é representada por (X \perp Y | Z) e caracteriza a indepndência condicional.

d-separação. Em uma rede bayesiana G, se não existe nenhum caminho ativo entre X e Y dado um conjunto de evidências Z, dizemos que há uma d-separação entre X e Y dado Z em G, ou de maneira mais compacta d\mbox{-}sep_G(X, Y | Z).

Mapa de independências. Seja I(G) o conjunto de independências condicionais (X, Y| Z) correspondentes a d-separações de G, para todo X, Y e Z. Se P satisfaz todas as indpendências em I(G), dizemos que G é um mapa de independências de P.

Dadas essas definições, temos o seguinte teorema:

Teorema: G é um mapa de indepências para P se, e somente se, P é uma fatoração sobre G.

Com esse teorema, temos dois modos de enxergar uma rede bayesiana: como fatores (CPD’s dos vértices) de uma distribuição P ou como um conjunto de independências que P deve satisfazer.

Bayes Ingênuo

Uma classe especial de redes bayesianas é o bayes ingênuo (naïve bayes), em que temos um nó com vários descendentes, conforme a Figura 2.

Figura 2: Bayes ingênuo

Essa estrutura é usada para casos simples de classificação. Os nós filhos são características e a raíz é uma variável aleatória correspondendo à classe. Assim, dada uma observação das características, deseja-se saber qual a classe mais provável.

Há dois tipos comuns de classificadores bayesianos ingênuos, que são o de Bernoulli, onde as características assumem valor binário e o multinomial onde elas podem assumir múltiplos valores.

Note que este modelo implica na independências entre as características dada a classe. Essa suposição pode ser muito simplista se as características do problema tiverem alta correlação.


Modelos Templates

Modelos templates visam representam de maneira genérica estruturas que se repetem. Com isso o modelo fica mais compacto e permite o re-uso em problemas com estruturas semelhantes.

Modelos Temporais

Há problemas que devem ser modelados considerando a passagem do tempo. Em geral discretizamos o tempo em pedaços de tamanho fixo e criamos variáveis aleatórias associadas a cada pedaço. Nesse caso costuma-se representar a variável por X^{(t)} e um conjunto de variáveis correspondendo a um intervalo t a t’ por: X^{(t:t')} = \{ X^{(t)}, \cdots, X^{(t')} \}.

Para simplificar modelos temporais, podemos fazer as seguintes suposições:

Suposição de Markov. diz que uma variável do instante de tempo t só depende do instante t-1, ou em termos matemáticos: (X^{(t+1)} \perp X^{(0:t-1)} | X^{(t)}).

Invariância em relação ao tempo, que supõe que as distribuições de probabilidade condicionais P(X^{(t+1)} | X^{(t)}) são as mesmas para todo t.

2TBN (2-time-slice Bayesian Network) é um modelo de transição entre dois fragmentos de tempo. Ele define um pedaço de rede bayesiana representando a transição de um conjunto de variáveis X_1, \cdots X_n para outro X'_1, \cdots X'_n no próximo instante de tempo. Nesse modelo, só o segundo conjunto de variáveis possuem CPD e este modelo define uma distribuição de probabilidade condicional conjunta para X'_1, \cdots X'_n.

Rede bayesiana dinâmica ou DBN (Dynamic bayesian network) consiste de uma rede que representa o estado inicial e um 2TBN representando a transição temporal. A expansão dessa rede, ou seja, a replicação do 2TBN para os instantes de tempo subsequentes forma a rede bayesiana espandida (ground bayesian network, que não sei traduzir).

Modelo de Markov Oculto

Também chamado de HMM (Hidden Markov Model) é um tipo de DBN que usa uma versão do 2TBN simplificado em que temos apenas uma variável S que muda ao longo do tempo e uma variável interna de observação, conforme a Figura 3.

Figura 3: 2TBN simplificado

Além disso, as possibilidades de transição de um estado para outro de S são limitadas. No exemplo da Figura 4, não podemos ir do estado s_1 para o estado s_3 ou s_4.

Figura 4: Transição limitada

Modelo de Placa

É um modelo que visa fatorar partes comum a vários elementos. A parte fatorada pode ser um CPD comum a todos os nós ou mesmo uma variável que está conectada a várias outras, como por exemplo a dificuldade de um curso estar ligada a todos os alunos desse curso.

A parte fatorada é representada fora da placa e os objetos que se repetem ficam dentro. A placa em si é desenhada através de um retângulo. É possível aninhar e também fazer sobreposição de placas.

Define-se uma variável template como um conjunto de variáveis aleatórias compartilhando uma certa propriedade. Uma limitação desse modelo é que os pais de uma variável template que engloba um conjunto U de variáveis, só podem englobar um subconjunto de U.

Os comentários estão fechados.

%d bloggers like this: