Probabilistic Graphical Models – Semana 7

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

Estimativa de parâmetros em Redes Bayesianas

Estimativa de verossimilhança máxima

Dada uma amostra {\cal D} = \{x[1], \cdots, x[M] \} obtida de maneira independente de uma distribuição desconhecida, queremos estimar \theta que represente \cal D.

Uma medida da qualidade dessa distribuição é a verossimilhança, denotada por L(\theta:{\cal D}) e definida como a probabilidade de se obter \cal D dada a distribuição \theta, ou seja

L(\theta:{\cal D}) = P({\cal D}|\theta) = \prod_{i=1}^{M} P(x[i]|\theta)

Definimos estatística suficiente como uma estatística que provê a mesma informação de uma amostra, sendo suficiente para calcularmos a verossimilhança. Vamos defini-la em termos de uma função que recebe uma amostra x e retorne uma tupla \mathbb{R}^k.

Um exemplo é a estatística suficiente para uma distribuição multinomial de k valores. Podemos definir a função s(x_i) = (0, \cdots, 0, 1, 0, \cdots, 0) que recebe um valor x_i e retorna uma tupla apenas com a i-ésima posição contendo 1 e o resto 0.

Agora calculamos a verossimilhança definindo \bar M = (M_1, \cdots, M_k) = \sum_{x[i] \in {\cal D}} s(x[i]). Note que M_k representa o número de amostras com o valor k. Logo, a verossimilhança é dada por

L(\bar{\theta}:{\cal D}) = \prod_{i=1}^{k} \theta_i^{M_i}

Outro exemplo é a distribuição Gaussiana com média \mu e variância \sigma^2. A distribuição pode ser dada por

p(X) = \dfrac{1}{\sqrt{2\pi \sigma^2}} \exp \left(-x^2 \dfrac{1}{2\sigma^2} + x \dfrac{\mu}{\sigma^2} - \dfrac{\mu^2}{\sigma^2}\right)

Podemos definir a estatística suficiente como s(x) = (1, x, x^2). Seja

\bar M = (M_1, M_2, M_3) = \sum_{x[i] \in {\cal D}} s(x[i])

podemos escrever a função de verossimilhança como

L(\theta: {\cal D}) = \left(\dfrac{1}{\sqrt{2\pi \sigma^2}}\right)^k \exp \left(-M_3 \dfrac{1}{2\sigma^2} + M_2 \dfrac{\mu}{\sigma^2} - M_1 \dfrac{\mu^2}{\sigma^2}\right)

O problema da estimativa de verossimilhança máxima (Maximum Likelihood Estimation, MLE) consiste em, dado um conjunto de amostras \cal D, encontrar a distribuição \theta que maximiza a verossimilhança L(\theta: D).

No caso da distribuição multinomial, podemos mostrar que o MLE é

\theta^*_i = \frac{M_i}{\sum_{i=1}^m M_i}

No caso da distribuição Gaussiana, temos

\mu^* = \dfrac{1}{M}

\sigma^* = \sqrt{\dfrac{1}{M} \sum_m (x[m] - \mu^*)^2}

Estimativa de verossimilhança máxima em Redes Bayesianas

Podemos generalizar a estimativa de verossimilhança para as distribuições em Redes Bayesianas. Suponha que tenhamos uma rede Bayesiana e queremos estimar as distribuições de probabilidades, nesse caso, os CPDs.

Novamente, dado um conjunto de amostras, \cal D, definimos a verossimilhança

L(\Theta: D) = \prod_{m} P(x[m]:\Theta)

Podemos fatorar essa distribuição em um produto dos CPDs de cada nó i usando a regra da cadeia.

= \prod_{m} \prod_i P(x_i[m] | \pmb{u}_i[m] : \theta_i)

Neste caso \pmb{u}_i representa os pais da variável i na rede. Re-arranjando os fatores, podemos trocar a ordem dos produtórios e obter,

= \prod_{i} \prod_m P(x_i[m] | \pmb{u}_i[m] : \theta_i)

Definindo a verossimilhança local como

L_i({\cal D}: \theta_i) = \prod_m P(x_i[m] | \pmb{u}_i[m] : \theta_i)

Temos finalmente que

L(\Theta: D) = \prod_{i} L_i(D:\theta_i)

Supondo inicialmente que os CPDs não são compartilhados por nenhuma variável, temos um \theta_i para cada variável. Vamos mostrar como determinar esses CPDs de maneira independente.

L_i({\cal D}: \theta_i) = \prod_{m} P(x[m]|\pmb{u}_[m] : \theta) = \prod_{m} P(x[m]|\pmb{u}_[m] : \theta_{X|\pmb{U}})

Re-arranjando os produtos para agrupá-los por valores de x e \pmb{u} (buckets), temos

\displaystyle = \prod_{x, \pmb{u}} \prod_{\substack{m:x[m] = x\\\pmb{u}[m] = \pmb{u}}} P(x[m]|\pmb{u}_[m] : \theta_{X|\pmb{U}})

Observamos que P(x|\pmb{u}) corresponde a uma entrada do CPD dado por \theta_{X|\pmb{U}}, que denotamos por \theta_{x|\pmb{u}}, portanto,

\displaystyle = \prod_{x, \pmb{u}} \prod_{\substack{m:x[m] = x\\\pmb{u}[m] = \pmb{u}}} \theta_{x|\pmb{u}}

Note que o termo \theta_{x|\pmb{u}} será multiplicado pelo número de amostras tais que x[m] = x e \pmb{u}[m] = \pmb{u}, que denotamos por M[x,\pmb{u}],

\displaystyle = \prod_{x, \pmb{u}} \theta_{x|\pmb{u}}^{M[x,\pmb{u}]}

Finalmente, vemos que a distribuição P(X|\pmb{U} = \pmb{u}) corresponde à distribuição multinomial, então podemos calcular o MLE \theta^*_{x|\pmb{u}} como

\theta^*_{x|\pmb{u}} = \dfrac{M[x,\pmb{u}]}{\sum_{x'} M[x',\pmb{u}]} = \dfrac{M[x,\pmb{u}]}{M[\pmb{u}]}

CPDs compartilhados. Note que a fórmula que obtivemos depende apenas dos valores de x e \pmb{u} e do CPD \theta_{x|\pmb{u}}. Assim, se tivermos CPDs compartilhados entre variáveis, como no modelo temporal, a única diferença é que podemos contar as ocorrências em M[x,\pmb{u}] múltiplas vezes para uma mesma amostra.

Observamos finalmente que o número de buckets cresce exponencialmente com o número de pais da variável. Isso faz com que os valores de \frac{M[x,\pmb{u}]}{M[\pmb{u}]} fiquem muito pequenos, levando à ocorrência da fragmentação e requerendo um maior número de amostras.

Estimativa Bayesiana

Uma maneira alternativa de se fazer estimativas das distribuições dos CPDs é usando uma outra rede Bayesiana. Neste caso supomos que cada amostra de \cal D representa um nó da rede e elas dependem de uma variável contínua que representa a distribuição \theta.

Neste caso a variável \theta tem um CPD correspondente a uma distribuição inicial P(\theta). A ideia é usar a rede para determinar a distribuição a posteriori de P(\theta) uma vez que observamos \cal D. Usando a regra de Bayes temos que,

(1) P(\theta|x[1], \cdots, x[M]) = \dfrac{P(x[1], \cdots, x[M]|\theta) P(\theta)}{P(x[1], \cdots, x[M])}

Veja que o primeiro termo do numerador corresponde à verossimilhança. P(\theta) é a distribuição a priori e P(\theta|x[1], \cdots, x[M]) a distribuição a posteriori. Uma vez que temos o conjunto de amostragem, o denominador é uma constante normalizadora.

Portanto, podemos reescrever (1) como

(2) P(\theta|{\cal D}) \propto P({\cal D}|\theta) P(\theta)

Distribuição multinomial

Suponha que \theta é uma distribuição multinomial sobre k valores. Como um valor a priori da distribuição de \theta, em geral utiliza-se a distribuição de Dirichlet, denotada por Dir(\alpha_1, \cdots, \alpha_k), onde \alpha_i é chamado de hiper-parâmetro. Basicamente, a distribuição é proporcional a um produtório,

Dir(\alpha_1, \cdots, \alpha_k) \propto \prod_{i=1}^{k} {\theta_i}^{\alpha_i - 1}

Intuitivamente os hiper-parâmetros correspondem às frequências de variáveis amostradas discriminadas por valor.

Usando a distribuição de Dirichlet como a distribuição a priori e lembrando que para uma distribuição multinomial a verossimilhança é dada por

P({\cal D}|\theta) = \prod_{i=1}^{k} \theta_i^{M_i}

Por (2), concluímos que a distribuição a posteriori é dada por,

P(\theta|{\cal D}) = \prod_{i=1}^{k} \theta_i^{\alpha_i + M_i - 1}

Note que P(\theta|{\cal D}) = Dir(\alpha_1 + M_1, \cdots, \alpha_k + M_k), ou seja, a distribuição a posteriori continuou sendo uma distribuição de Dirichlet. Devido a essa característica, dizemos que a distribuição de Dirichlet é um conjugado a priori para a distribuição multinomial.

Previsão Bayesiana

Considere uma rede bayesiana simples como a da Figura 1. Suponha que a variável \theta tem distribuição Dir(\alpha_1,\cdots,\alpha_k) = \prod_{j=1}^{k} \theta_j^{\alpha_j - 1}.

Figura 1: Variável condicionada por uma distribuição de Dirichlet

Podemos calcular a distribuição em X multiplicando os CPD’s e marginalizando \theta, ou seja,

(3) P(X) = \int_{\theta} P(X|\theta) P(\theta) d\theta

Para um valor específico de X = x_i, temos que P(X = x_i|\theta) = \theta_i. Substituindo também P(\theta) pela definição da eq. de Dirichlet teremos

P(X = x_i) = \frac{1}{Z} \int_{\theta} \theta_i \left(\prod_{j=1}^{k} \theta_j^{\alpha_j - 1}\right)d\theta

Que segundo as aulas é igual a

(4) = \dfrac{\alpha_i}{\sum_{j=1}^{k} \alpha_j}

Agora, suponha que tenhamos um conjunto de M+1 variáveis condicionadas por \theta, que novamente supomos possuir a distribuição Dir(\alpha_1,\cdots,\alpha_k), conforme a Figura 2.

Figura 2: Rede Bayesiana com M+1 variáveis condicionadas a uma distribuição de Dirichlet

Imagine que observamos as M primeiras variáveis (conjunto \cal D) e queremos prever a distribuição da M+1-ésima, temos que

P(X[M+1] | {\cal D}) = \int_{\theta} P(X[M+1]|{\cal D},\theta) P(\theta|{\cal D}) d\theta

Dado \theta, X[M+1] é independente de \cal D, logo

P(X[M+1] | {\cal D}) = \int_{\theta} P(X[M+1]|\theta) P(\theta|{\cal D}) d\theta

Vimos anteriormente que P(\theta|{\cal D}) = Dir(\alpha_1 + M_1, \cdots, \alpha_k + M_k). Note então que o lado direito da equação acima é idêntico ao lado direito da equação (3). Portanto, podemos calcular $P(X[M+1] = x_i |{\cal D})$, mas usando \alpha_i + M_i, levando a

(5) P(X[M+1] = x_i |{\cal D}) = \dfrac{\alpha_i + M_i}{\sum_{j=1}^{k} (\alpha_j + M_j)}

Definimos como o tamanho da amostra equivalente a soma \alpha = \alpha_1 + \cdots + \alpha_k. Observe que se \alpha_j = 0, teríamos o MLE.

Usando redes Bayesianas, damos um “chute” inicial na distribuição, que eventualmente converge para o mesmo valor que o MLE conforme o número de iterações aumenta. A vantagem é que temos uma maior robustez nas iterações iniciais, quando temos poucas amostras. O gráfico da Figura 3 mostra bem esse fenômeno.

Figura 3: Gráfico de estimativa de uma distribuição de Bernoulli, usando diferentes métodos.

Note que a magnitude de \alpha define o quanto a distribuição inicial terá efeito sobre as distribuições obtidas a priori. Veja como a Dir(.5,.5) (verde-claro) quase não tem diferença sobre a MLE, enquanto Dir(10,10) (preto) muda bastante.

Estimativas Bayesianas para Redes Bayesianas

Podemos generalizar as ideias apresentadas anteriormente para estimar as distribuições dos CPDs de toda uma rede Bayesiana. Consideremos uma rede Bayesiana com uma variável X e uma variável Y que depende condicionalmente de X.

Para estimar os CPDs dessas duas variáveis usando um conjunto de M amostras, podemos construir outra rede Bayesiana conforme a Figura 4.

Figura 4: Estimativa de parâmetros para uma rede Bayesiana”

Note que \theta_X corresponde ao CPD de X e \theta_{Y|X} corresponde ao CPD de Y. Se partirmos de distribuições iniciais para \theta_X e \theta_{Y|X}, temos que as amostras (X[m], Y[m]) são independentes.

Dado o conjunto de amostras {\cal D}, temos que \theta_X e \theta_{Y|X} são independentes. Assim, a distribuição a posteriori de \theta pode ser dada por

P(\theta_X, \theta_{Y|X} | {\cal D}) = P(\theta_X|{\cal D}) P(\theta_{Y|X}|{\cal D})

Podemos refinar o modelo e considerar os possíveis valores de X, criando um CPD de Y para cada valor. Por exemplo, se X for uma variável binária teremos a rede Bayesiana da Figura 5

Figura 5: Estimativa refinada de parâmetros para uma rede Bayesiana

Neste caso, dado o conjunto \cal D, não fica evidente pela rede que \theta_{Y|x^0} é independente de \theta_{Y|x^1}, mas aqui temos independência específica por contexto, pois quando o valor de X é conhecido, uma das duas arestas incidentes a cada Y[m] some.

De qualquer maneira, podemos computar as probabilidades a posteriori de \theta independentemente. Se a distribuição a priori de \theta_{X|\pmb{u}} for Dir(\alpha_{x^1|\pmb{u}}, \cdots, \alpha_{x^k|\pmb{u}}), a distribuição a posteriori será Dir(\alpha_{x^1|\pmb{u}} + M[x^1|\pmb{u}], \cdots, \alpha_{x^k|\pmb{u}} + M[x^k|\pmb{u}])

Uma escolha inicial dos hiper-parâmetros das distribuições de Dirichlet, consiste em escolher um tamanho de amostra equivalente \alpha e para cada CPD distribuí-lo pelo número de entradas. Por exemplo, se o CPD for sobre uma única variável binária, teremos Dir(\alpha/2, \alpha/2). Se tivermos uma variável binária dependendo de outra, fazemos a divisão de \alpha por 4.


Estimativa de parâmetros em Redes de Markov

Vamos apresentar métodos para a estimativa de parâmetros em redes de Markov ou MRF (Markov Random Fields) e para redes de Markov condicionais ou CRF (Conditional Random Fields). Ao invés de um produto de fatores, vamos considerar a representação mais genéricas através de modelos log-lineares.

Verossimilhança máxima para modelos log-lineares

Considere uma distribuição conjunta de um modelo log-linear

P(\pmb{X} : \theta) = \dfrac{1}{Z(\theta)} \tilde P(\pmb{X} : \theta) = \dfrac{1}{Z(\theta)} \exp \left\{\sum_{i=1}^{k} \theta_i f_i(\pmb{x}) \right\}

Note que para simplificar a notação, estamos supondo que f_i ignora todas as entradas de \pmb{x} que não pertencem a seu domínimo D_i. Aqui Z(\theta) é a constante normalizadora dada pela soma de \tilde P(\pmb{X}=\pmb{x}) para todos as possíveis atribuições \pmb{x}, ou seja

Z(\theta) = \sum_{\pmb{x}} \exp (\sum_i \theta_i f_i (\pmb{x}))

Podemos definir a log-verossimilhança de um conjunto de amostras \cal D, denotado por \ell(\theta:{\cal D}) como

\ell(\theta:{\cal D}) = \ln (L(\theta:{\cal D})) = \sum_m(\ln P(\pmb{x}[m] : \theta))

Substituindo P(\pmb{x}[m] : \theta) pela distribuição log-linear temos

= \sum_m (\sum_i \theta_i f_i(\pmb{x}[m]) - \ln Z(\theta))

podemos re-arrajar os somatórios e obter:

= (\sum_i \theta_i (\sum_m f_i(\pmb{x}[m]))) - M\ln Z(\theta)

Diferentemente do caso de redes Bayesianas, aqui não podemos decompor em verossimilhanças locais porque o termo Z(\theta) acopla os termos \theta_1, \cdots, \theta_k.

Porém, podemos mostrar que essa função é côncava, podendo ser resolvida numericamente por um método de descida de gradiente, por exemplo. Na prática, costuma-se utilizar o L-BFGS (Low Memory Broyden Fletcher Goldfarb Shanno).

Para computar os gradientes, vamos considerar a derivada da log-verossimilhança.

\dfrac{\partial}{\partial\theta_i} \dfrac{1}{M} \ell(\theta:{\cal D}) =  \dfrac{\partial}{\partial\theta_i} \left((\sum_i \theta_i \dfrac{1}{M} (\sum_m f_i(\pmb{x}[m]))) - \ln Z(\theta)\right)

Note que dividimos a log-verossimilhança pela constante M antes de derivar. Isso é para simplificar o resultado. Como estamos derivando com relacão a \theta_i, o único termo que restará do primeiro somatório é

\dfrac{1}{M} \sum_m f_i(x[m])

que corresponde à média dos valores de f_i considerando todas as amostras. Definimos esse termo como esperança empírica, denotada por E_{\cal D}[f_i(\pmb{X})]. Veja que este valor independe da distribuição \theta.

Já para o segundo termo, aplicamos inicialmente a regra da cadeia para obter

\dfrac{\partial}{\partial\theta_i} \ln Z(\theta)
= \dfrac{1}{Z(\theta)} \sum_{\pmb{x}} \left( \dfrac{\partial}{\partial \theta_i} \exp \{\sum_j \theta_j f_j(\pmb{x}) \} \right)

Podemos aplicar novamente a regra da cadeia para \exp, obtendo

= \dfrac{1}{Z(\theta)} \sum_{\pmb{x}} \left( f_i(\pmb{x}) \exp \{\sum_j \theta_j f_j(\pmb{x}) \} \right)

Rearranjando os termos ficamos com

= \sum_{\pmb{x}} \left( \dfrac{1}{Z(\theta)} \exp \{\sum_j \theta_j f_j(\pmb{x}) \} \right) f_i(\pmb{x})

Veja que o priimeiro termo do somatório é exatamente nossa distribuição original, P(\pmb{X} : \theta) com \pmb{X} = \pmb{x}. Reescrevendo temos:

\dfrac{\partial}{\partial\theta_i} \ln Z(\theta) = \sum_{\pmb{x}} P(\pmb{X} = \pmb{x}) f_i(\pmb{x})

Esse termo representa a esperança de f_i considerando a distribuição \theta e será denotado por E_\theta[f_i]. Veja que para calcular a probabilidade de cada possível atribuição \pmb{x}, podemos usar os métodos de inferência vistos em aulas passadas.

Resumindo, temos o seguinte resultado:

\dfrac{\partial}{\partial\theta_i} \dfrac{1}{M} \ell(\theta:{\cal D}) = E_{\cal D}[f_i(\pmb{X})] - E_\theta[f_i]

Usando essa diferença para construir o gradiente, obtemos finalmente o seguinte teorema:

Teorema. A distribuição \hat \theta resulta na MLE se e somente se E_{\cal D}[f_i(X)] = E_\theta[f_i] para todo i=1,\cdots,k

MLE para CRFs

No caso de CRFs (Conditional Random Fields), temos a distribuição conjunta condicional

P_\theta(\pmb{Y}|\pmb{x}) = \dfrac{1}{Z_{\pmb{x}}(\theta)}\tilde P_\theta(\pmb{x}, \pmb{Y}),

onde Z_{\pmb{x}}(\theta) = \sum_{\pmb{Y}} \tilde P_\theta(\pmb{x}, \pmb{Y})

Considere o conjunto de amostras {\cal D} = \{(x[m], y[m])\}_{m=1}^M. Podemos novamente definir a log-verossimilhança:

\ell_{Y|x}(\theta:{\cal D}) = \sum_{m=1}^M \ln P_\theta(y[m], x[m] : \theta)

= \sum_m (\sum_i \theta_i f_i(\pmb{x}[m]) - \ln Z_{x[m]}(\theta))

Note que neste caso não podemos extrair o termo Z_{x[m]}(\theta) para fora do somatório porque ele depende de x[m].

Para determinar o gradiente, podemos novamente calcular a derivada em relação a \theta_i:

\dfrac{\partial}{\partial \theta_i} \dfrac{1}{M} \ell_{Y|x}(\theta:{\cal D}) = \dfrac{\partial}{\partial \theta_i} \dfrac{1}{M} \sum_m (\sum_i \theta_i f_i(\pmb{x}[m]) - \ln Z_{x[m]}(\theta))

Usando as mesmas ideias do caso de MRF’s, concluiremos que

\dfrac{\partial}{\partial \theta_i} \dfrac{1}{M} \ell_{Y|X}(\theta:{\cal D}) = \dfrac{1}{M} \sum_{m=1}^{M} (f_i(x[m],y[m]) - E_\theta[f_i(x[m], Y)])

Onde E_\theta[f_i(x[m], Y)] =  \sum_Y P_\theta(Y|x[m]) f_j(Y, x[m])

A diferença aqui é que a cada passo do algoritmo, devemos recalcular P_\theta(Y|x[m])] para cada amostra x[m]. Porém, em geral o conjunto Y será menor para CRF’s.

Estimativa MAP para MRFs e CRFs

Da mesma forma que para redes Bayesianas, podemos “chutar” uma distribuição a priori e obter uma distribuição a posteriori. Entretanto, devido ao acoplamento presente na verossimilhança de redes de Markov, não há uma fórmula fechada para a distribuição, como a de Dirichlet para redes Bayesianas.

O que fazemos é manter um conjunto de parâmetros que maximizem a dstribuição a posteriori, ou seja, uma MAP (Maximum A Posteriori).

Uma possível distribuição a pirori que pode ser usada é a distribuição gaussiana com métia 0.

P(\theta : \sigma^2) = \prod_{i=1}^{k} \dfrac{1}{\sqrt{2\pi}\sigma} \exp \left\{ - \dfrac{\theta_i^2}{2\sigma^2} \right\}

Intuitivamente, quanto maior o valor de \sigma, maior a confiança de que o valor de \theta_i esteja próximo de 0.

Outra alternativa é usar a distribuição de Laplace,

P(\theta:\beta) = \prod_{i=1}^{k} \dfrac{1}{2\beta} \exp \left\{-\dfrac{|\theta_i|}{\beta} \right\}

Queremos encontrar a distribuição \theta que maximiza a distribuição conjunta dado o conjunto de amostras, ou seja,

\mbox{argmax}_\theta P({\cal D}, \theta) = \mbox{argmax}_\theta P({\cal D} | \theta) P(\theta)

Neste caso P({\cal D} | \theta) é a verossimilhança e P(\theta) é a distribuição a priori. Como o logaritmo é monotomicamente crescente com sua entrada, podemos aplicar o log ao termo dentro de argmax:

= \mbox{argmax}_\theta(\ell(\theta:{\cal D}) + \log P(\theta))

O plot de \log P(\theta) para a distribuição Gaussiana, é uma função quadrática. Esta curva corresponde a uma penalização da log-verossimilhança e é conhecida como regularização-L2.

De maneira análoga, o plot para a distribuição de Laplace é uma função linear e é equivalente à regularização-L1.

Os comentários estão fechados.

%d bloggers like this: