Probabilistic Graphical Models – Semana 6

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

Inferência em modelos temporais

Tracking da crença em tempo real

Um modelo temporal pode ser representado sucintamente através de templates. Porém, a rede expandida (grounded ou unrolled) pode ficar enorme. Ficaria inviável manter uma distribuição conjunta considerando todas as variáveis do modelo.

O tracking da crença em tempo real é uma maneira aproximada de calcular a crença para um conjunto de variáveis em um dado nível t a partir apenas da crença no nível anterior.

Dada a crença \sigma^{(t)}(S^{(t)}) do conjunto de variáveis S^{(t)} no nível t temos

(1) \sigma^{(t)}(S^{(t)}) = P(S^{(t)} | o^{(1:t)})

Podemos deduzir a seguinte relação de inferência da crença em uma iteração dada a crença na iteração anterior.

\sigma^{(t + 1)}(S^{(t+1)}) \propto P(o^{(t+1)}|S^{(t+1)}) \sigma^{(\cdot t + 1)}(S^{(t+1)})

Note que precisamos renormalizar a distribuição \sigma^{(t + 1)}(S^{(t+1)}) para obter o valor correto.

Nas aulas não ficou muito claro como essa recorrência foi obtida. Complementando com respostas no fórum, decidi escrever uma versão mais mastigada como segue.

Prova:

Seja \sigma^{(\cdot t + 1)} (observe o ponto antes do t) a distribuição do estado S^{(t+1)} sem levar em conta a observação em t+1, que é dada por,

(2) \sigma^{(\cdot t + 1)}(S^{(t+1)}) = P(S^{(t+1)} | o^{(1:t)})

Usando a relação

(3) P(A|B) = \frac{P(AB)}{P(B)},

podemos mostrar que

P(S^{(t+1)}, S^{(t)} | o^{(1:t)}) = P(S^{(t+1)} | S^{(t)}, o^{(1:t)}) P( S^{(t)} | o^{(1:t)})

Marginalizando para S^{(t)}, temos que

P(S^{(t+1)} | o^{(1:t)}) = \sum_{S^{(t)}}P(S^{(t+1)}, S^{(t)} | o^{(1:t)})

ou seja,

\sigma^{(\cdot t + 1)}(S^{(t+1)}) = \sum_{S^{(t)}} P(S^{(t+1)} | S^{(t)}, o^{(1:t)}) P(S^{(t)} | o^{(1:t)})

Pela estrutura desse tipo de rede Bayesiana, temos que S^{(t+1)} é independente de tudo dado S^{(t)}, ou seja,

P(S^{(t+1)} | S^{(t)}, o^{(1:t)}) = P(S^{(t+1)} | S^{(t)})

Usando essa relação e (1) concluímos então que,

\sigma^{(\cdot t + 1)}(S^{(t+1)}) = \sum_{S^{(t)}} P(S^{(t+1)} | S^{(t)}) \sigma^{(t)}(S^{(t+1)})

Dada a relação (3), podemos mostrar que dados os conjuntos de variáveis A, B, C,

P(A|BC) = \dfrac{P(C|AB)P(A|B)}{P(C|B)}

Com isso, podemos encontrar uma relação de recorrência para \sigma^{(t + 1)}(S^{(t+1)}). Por definição temos que

\sigma^{(t + 1)}(S^{(t+1)}) = P(S^{(t+1)} | o^{(1:t)}, o^{(t+1)})

Usando (2) temos

= \dfrac{P(o^{(t+1)}|S^{(t+1)}o^{(1:t)})P(S^{(t+1)}|o^{(1:t)})}{P(o^{(t+1)}|o^{(1:t)})}

Observando que o^{(t+1)} é independente de o^{(1:t)} dado S^{(t+1)}, substituindo (2) e observando que o denominador P(o^{(t+1)}|o^{(1:t)}) é uma constante normalizadora, podemos concluir que

\sigma^{(t + 1)}(S^{(t+1)}) \propto P(o^{(t+1)}|S^{(t+1)}) \sigma^{(\cdot t + 1)}(S^{(t+1)})

Emaranhamento

Uma limitação do tracking da esperança em tempo real é que conforme expandimos a rede Bayesiana dinâmica (t aumenta), as independências condicionais para um dado nível (X(t) \perp Y(t) | Z(t)) tendem a sumir, pois cada vez mais existirão caminhos ativos entre elas (através dos ancestrais).

Assim, a crença em tempo real tende a ficar muito correlacionada, se distanciando da crença exata. Note que neste caso que a crença exata deveria considerar praticamente todas as variáveis do modelo para levar em conta as dependências, ficando com um tamanho exponencial.


Tomada de decisão

Utilidade esperada máxima

Considere um problema de decisão \cal D consistindo de um conjunto \pmb{X} de variáveis aleatórias, um conjunto de ações A e uma distribuição dos estados das variáveis condicionados por A, denotada por P(\pmb{X}|A). Considere uma função utilidade denotada por U(\pmb{X}, A), que corresponde a função peso para as atribuições de \pmb{X} e A.

Definimos a utilidade esperada do problema de decisão \cal D como a soma ponderada da utilidade de uma atribuição (\pmb{x},a), ponderada por sua probabilidade, ou seja:

EU[{\cal D}[a]] = \sum_x P(\pmb{x}| a) U(\pmb{x},a)

O problema da utilidade esperada máxima (Maximum Expected Utility (MEU)) consiste em escolher a ação a que maximiza a utilidade esperada, ou seja,

a^* = \mbox{argmax}_a EU[{\cal D}[a]]

Há casos em que a ação é condicionada por variáveis aleatórias, como no exemplo da Figura 1, onde a ação Found (relacionada a fundar ou não fundar uma empresa), está condicionada ao resultado de uma pesquisa de mercado, associada à variável Survey.

Figura 1: Exemplo

Neste caso, ao invés de encontrar uma única ação a ser tomada, devemos encontrar uma tabela onde as entradas são os possíveis valores das variáveis, a qual definimos regra de decisão, denotada por \delta_A e corresponde a essencialmente ao CPD, P(A | \mbox{predecessores}(A)).

Neste caso, a soma ponderada para calcular a utilidade esperada engloba todos os valores de a, ou seja,

EU[{\cal D}[\delta_A]] = \sum_{\pmb{x},a} P_{\delta_A}(\pmb{x}| a) U(\pmb{x}|a)

O objetivo agora é encontrar o CPD \delta_A.

No caso de uma rede Bayesiana, podemos desmembrar a distribuição conjunta P_{\delta_A}(\pmb{x}| a) em um produto de fatores. Definindo \pi_X como os pais da variável X na rede, podemos reescrever EU[{\cal D}[\delta_A]] como,

= \sum_{X_1,\cdots, X_n,A} \left((\prod_{i} P(X_i|\pi_{X_i}) \cdot U(\pi_U) \cdot \delta_A(A|\pi_A) \right)

Definindo W como \{X_1,\cdots, X_n\} \setminus \pi_A, podemos fatorar o somatório e isolar \delta_A,

= \sum_{\pi_A,A} \delta_A(A|\pi_A) \sum_W ((\prod_{i} P(X_i|\pi_{X_i}) \cdot U(\pi_U))

Denotando por \mu(A, \pi_A) o produto dos fatores marginalizando W, temos

= \sum_{\pi_A,A} \delta_A(A|\pi_A) \mu(A, \pi_A)

Com isso é podemos construir a solução ótima \delta^*_A(A|\pi_A) como um CPD determinístico, cujas entradas podem ser obtidos de maneira gulosa:

\delta^*_A(A|\pi_A) =   \begin{cases}  1 & \mbox{Se } a = \mbox{argmax}_A \mu(A, \pi_a) \\  0 & \mbox{Caso contrario}  \end{cases}

Funções de utilidade

A escolha da função utilidade é complicada, principalmente porque a utilidade é um conceito subjetivo.

Além disso, a utilidade não é uma função linear do valor esperado. Por exemplo, para a maior parte das pessoas, ganhar R$500 é melhor do que ganhar R$1000 com 50% de chance.

O gráfico da Figura 2 é uma aproximação da percepção de utilidade em função da quantia de dinheiro. Note que a função cresce menos do que a função linear.

Figura 2: Gráfico utilidade vs. recompensa

Devido a essa característica, quando consideramos risco, como no exemplo de se ganhar R$1000 com 50% de chance, temos que o valor utilidade nesse caso é menor do que R$500 (o valor esperado), mais especificamente é equivalente a ganhar ~R$400 com 100% de chance.

Um caso onde isso fica mais evidente é o paradoxo de São Petersburgo, onde o valor esperado é infinito, mas a utilidade em geral é equivalente a R$2!

Valor da informação perfeita

Uma vez que obter informações que auxiliem no suporte a decisão — como pesquisa de mercado, sensores mais precisos, exames médicos — possuem um custo (equipamentos mais caros, exames mais perigosos), devemos ser capazes de medir qual o ganho no valor utilidade eles trazem.

Considere um diagrama de decisão \cal D. Denotamos por {\cal D}_{X \rightarrow A} como o diagrama \cal D adicionado da aresta X \rightarrow A. Definimos o valor de uma observação X antes de decidir por uma ação de A como a melhoria na utilidade que essa observação traz, ou seja,

\mbox{VPI}(A|X) = \mbox{MEU}({\cal D}_{X \rightarrow A}) - \mbox{MEU}({\cal D})

Teorema. \mbox{VPI}(A|X) \ge 0, sendo que \mbox{VPI}(A|X) = 0 se e somente se, a decisão ótima para \cal D é a também a solução ótima para {\cal D}_{X \rightarrow A}.

Conclusão

Logo no final do ano passado eu havia falado que um dos objetivos ao fazer o curso era criar uma boa base para aprender técnicas de tomada de decisão sob incerteza. Foi uma surpresa boa descobrir que este assunto foi coberto nesse curso!

Em um post anterior, eu já havia indicado este post que apresenta uma discussão bem bacana sobre loterias e funções de utilidade.

Os comentários estão fechados.

%d bloggers like this: