In jtrecenti/ea2:
Resumo
- Redes Bayesianas são modelos flexíveis e fáceis de elicitar / interpretar.
- Existem três problemas principais a serem trabalhados: aprendizado, inferência e classificação.
- O problema de inferência em geral é NP-difícil. Técnicas de aproximação (determinísticas e estocásticas) são alternativas usuais.
- Utilizando os conhecimentos desenvolvidos em MAE5835 e assumindo uma suposição chamada variância limitada, é possível construir um algoritmo estocástico aproximado com tempo polinomial.
Motivação
- Redes Bayesianas são modelos flexíveis, capazes de representar uma série de fenômenos.
- "O diagrama de influência[rede Bayesiana] é a radiografia do problema" - C.A.B. Pereira.
- A estrutura de uma rede Bayesiana é de fácil interpretação e elicitação.
- É possível recuperar a distribuição conjunta de todas as variáveis.
- São modelos úteis para a tarefa de classificação (aprendizado de máquina).
- Os modelos de deep-learning podem ser vistos como redes Bayesianas profundas.
- São a base para o desenvolvimento moderno da teoria de causalidade (Pearl, 2009).
Conceitos
Probabilidade condicional
Pela definição de probabilidade condicional, temos
$$
P(X_1 = x_1, X_2 = x_2) = p(x_1, x_2) = p(x_1)p(x_2\,|\,x_1)
$$
Para $\mathbf{X} = (X_1, \dots, X_n)^\top$, temos
$$
P(\mathbf{X} = \mathbf{x}) = p(\mathbf{x}) = \prod\limits_{j=1}^n p(x_j\,|\,x_1, \dots, x_{j-1}).
$$
Probabilidade condicional
Imagine que, no seu problema, a variável $X_j$ não dependa de $X_1, \dots, X_j$, e sim de um subconjunto $\Pi_j$ dessas variáveis.
Então
$$
P(\mathbf{X} = \mathbf{x}) = p(\mathbf{x}) = \prod\limits_{j=1}^n p(x_j\,|\,\pi_j).
$$
$Pi_j$ são denominados pais de $X_j$.
Grafo direcionado acíclico | DAG
Um grafo direcionado é um par $G = (V, E)$ em que cada elemento de $E$ corresponde a um par ordenado de elementos de $V$.
Os elementos de $V$ são vértices e os elementos de $E$ são setas.
Um grafo direcionado acíclico (DAG) é um grafo direcionado que não contém circuitos.
Redes Bayesianas
Uma rede Bayesiana é uma tripla $(G, \mathbf{X}, P)$ em que
- $G = (V, E)$ é um DAG.
- $\mathbf{X}$ é um vetor de variáveis aleatórias em que cada elemento $X_i$ é representado por um vértice e cada dependência condicional é representada por uma seta.
- $P$ é um conjunto de funções de probabilidade condicionais compatível com $G$.
Problemas com Redes Bayesianas
- Aprendizado
- Estrutura: dados $\rightarrow \hat{G}$
- Parâmetros: dados $\rightarrow \hat{P}$
- Inferência: $P(\mathbf{Q}=\mathbf{q}\,|\,\mathbf{E}=\mathbf{e})$
- Predição: $f(x_1, \dots, x_p) \mapsto c$
Inferência
Definição
A partir de uma rede Bayesiana completamente especificada, desejamos calcular $P(\mathbf{Q}=\mathbf{q}\,|\,\mathbf{E}=\mathbf{e}) = p(\mathbf{q}\,|\,\mathbf{e})$.
Essa expressão é teoricamente possível de se obter, já que
$$
p(\mathbf{q}\,|\,\mathbf{e}) = \frac{\sum\limits_{\mathbf{z} \in \mathbf{X}\backslash{\mathbf{Q}, \mathbf{E}}} p(\mathbf{x})}{\sum\limits_{\mathbf{z} \in \mathbf{X}\backslash {\mathbf{E}}} p(\mathbf{x})}.
$$
No entanto, o número de termos dessas somas cresce exponencialmente com o tamanho da rede. O problema é intratável mesmo para redes pequenas (NP-difícil).
Algoritmos aproximados
Objetivo: obter uma estimativa eficiente que erre a inferência em no máximo $\epsilon$ com probabilidade $\delta$.
Tipos de erro
Absoluto: $\epsilon = |\hat{p} - p|$
Relativo: $\varepsilon = \frac{|\hat{p} - p|}{p}$
Como a ideia é trabalhar com redes e inferências grandes, geralmente as probabilidades a serem obtidas são pequenas. Nesses casos, o erro relativo é preferível.
Inferência por amostragem simples | descrição
- Técnica simples de Monte Carlo.
- Consiste em simular da rede Bayesiana a partir de uma ordem topológica.
- A estimativa da probabilidade é a razão das proporções de resultados $M$ e $N$ que satisfazem as consultas $p(\mathbf{q},\mathbf{e})$ e $p(\mathbf{e})$, respectivamente.
Usando a lei fraca de Khintchine, podemos mostrar que
$$
M/N \overset{P}{\to} p(\mathbf{q}|\mathbf{e})
$$
Inferência por amostragem | complexidade
Seja $\hat{p}$ uma estimativa de $p = P(\mathbf{W}=\mathbf{w})$ obtida via amostragem simples com $N$ iterações. Pela desigualdade de Hoeffding, temos que
$$
P(|\hat{p} - p| > \epsilon) \leq 2e^{-2N\epsilon^2}
$$
A desigualdade sugere que o tamanho de amostra necessário para atingir um erro $\epsilon$ com probabilidade $\delta$ é
$$
N \geq \log(2/\delta) / 2\epsilon^2
$$
Inferência por amostragem | complexidade
Para trabalhar com erros relativos, trabalhamos com outra desigualdade.
Pela desigualdade de Chernoff, temos que
$$
P(\frac{|\hat{p} - p|}{p} > \epsilon) \leq 2e^{-2Np\epsilon^2/3},
$$
Nesse caso, o tamanho de amostra necessário é
$$
N \geq 3\log(2/\delta) / p\epsilon^2,
$$
que depende de $p$.
Amostragem por importância | descrição
Na lousa
Variância limitada local
Na lousa
Algoritmo da variância limitada | descrição
Na lousa
Exemplo
Exemplo
Uma consulta que podemos fazer é $p(X_0 = TRUE|X1 = LOW)$.
A probabilidade exata dessa consulta é de 37,04%. Essa consulta é interessante
pois o denominador $p(X_0 = TRUE, X1 = LOW)$ é de aproximadamente 4%, o que pode
evidenciar dificuldades nos algoritmos que não funcionam bem para valores baixos
de probabilidade.
Exemplo
Primeiramente, fizemos a consulta para uma amostra de tamanho 100, replicada quinze
vezes.
Exemplo | Amostra de tamanho 100
library(dplyr)
library(ggplot2)
d <- readRDS('../data-raw/res_100_2.rds')
lapply(seq_along(d), function(i) {
d[[i]]$iter <- i
d[[i]]
}) %>%
bind_rows() %>%
mutate(algo = ifelse(algo == '', 'GS', algo)) %>%
filter(algo != 'GS') %>%
ggplot(aes(x = algo, y = r)) +
geom_hline(yintercept = 0.3702, colour = 'red') +
geom_hline(yintercept = c(1, 0), colour = 'black', linetype = 2) +
scale_y_continuous(limits = c(0, 1)) +
geom_point() +
theme_bw() +
xlab('Algoritmo') +
ylab('Resultado')
Exemplo | Amostra de tamanho 100
É possível notar:
- Para um tamanho de amostra pequeno, os algoritmos de simulação lógica e por importância apresentam resultados e tempos similares.
- O algoritmo de variância limitada apresenta mais resultados próximos do valor real, com menor variância.
Exemplo | Amostra de tamanho 1000
library(dplyr)
library(ggplot2)
d <- readRDS('../data-raw/res_1000_2.rds')
lapply(seq_along(d), function(i) {
d[[i]]$iter <- i
d[[i]]
}) %>%
bind_rows() %>%
mutate(algo = ifelse(algo == '', 'GS', algo)) %>%
filter(algo != 'GS') %>%
ggplot(aes(x = algo, y = r)) +
geom_hline(yintercept = 0.3702, colour = 'red') +
geom_hline(yintercept = c(1, 0), colour = 'black', linetype = 2) +
scale_y_continuous(limits = c(0, 1)) +
geom_point() +
theme_bw() +
xlab('Algoritmo') +
ylab('Resultado')
Exemplo | Amostra de tamanho 1000
- Novamente, os algoritmos de amostragem lógica e por importância apresentaram tempos e resultados similares. A variância da amostragem por importância foi menor (desvio padrão de 0.04 contra desvio padrão de 0.05 da amostragem lógica e 0.06 da variância limitada)
- O algoritmo de variância limitada apresentou maior variabilidade em relação ao tempo de execução. Isso pode ter acontecido por conta dos passos "não lineares" que o algoritmo realiza.
Fim
jtrecenti/ea2 documentation built on May 20, 2019, 3:17 a.m.
R Package Documentation
Browse R Packages
We want your feedback!
Note that we can't provide technical support on individual packages. You should contact the package authors for that.
Resumo
- Redes Bayesianas são modelos flexíveis e fáceis de elicitar / interpretar.
- Existem três problemas principais a serem trabalhados: aprendizado, inferência e classificação.
- O problema de inferência em geral é NP-difícil. Técnicas de aproximação (determinísticas e estocásticas) são alternativas usuais.
- Utilizando os conhecimentos desenvolvidos em MAE5835 e assumindo uma suposição chamada variância limitada, é possível construir um algoritmo estocástico aproximado com tempo polinomial.
Motivação
- Redes Bayesianas são modelos flexíveis, capazes de representar uma série de fenômenos.
- "O diagrama de influência[rede Bayesiana] é a radiografia do problema" - C.A.B. Pereira.
- A estrutura de uma rede Bayesiana é de fácil interpretação e elicitação.
- É possível recuperar a distribuição conjunta de todas as variáveis.
- São modelos úteis para a tarefa de classificação (aprendizado de máquina).
- Os modelos de deep-learning podem ser vistos como redes Bayesianas profundas.
- São a base para o desenvolvimento moderno da teoria de causalidade (Pearl, 2009).
Conceitos
Probabilidade condicional
Pela definição de probabilidade condicional, temos
$$ P(X_1 = x_1, X_2 = x_2) = p(x_1, x_2) = p(x_1)p(x_2\,|\,x_1) $$
Para $\mathbf{X} = (X_1, \dots, X_n)^\top$, temos
$$ P(\mathbf{X} = \mathbf{x}) = p(\mathbf{x}) = \prod\limits_{j=1}^n p(x_j\,|\,x_1, \dots, x_{j-1}). $$
Probabilidade condicional
Imagine que, no seu problema, a variável $X_j$ não dependa de $X_1, \dots, X_j$, e sim de um subconjunto $\Pi_j$ dessas variáveis.
Então
$$ P(\mathbf{X} = \mathbf{x}) = p(\mathbf{x}) = \prod\limits_{j=1}^n p(x_j\,|\,\pi_j). $$
$Pi_j$ são denominados pais de $X_j$.
Grafo direcionado acíclico | DAG
Um grafo direcionado é um par $G = (V, E)$ em que cada elemento de $E$ corresponde a um par ordenado de elementos de $V$.
Os elementos de $V$ são vértices e os elementos de $E$ são setas.
Um grafo direcionado acíclico (DAG) é um grafo direcionado que não contém circuitos.
Redes Bayesianas
Uma rede Bayesiana é uma tripla $(G, \mathbf{X}, P)$ em que
- $G = (V, E)$ é um DAG.
- $\mathbf{X}$ é um vetor de variáveis aleatórias em que cada elemento $X_i$ é representado por um vértice e cada dependência condicional é representada por uma seta.
- $P$ é um conjunto de funções de probabilidade condicionais compatível com $G$.
Problemas com Redes Bayesianas
- Aprendizado
- Estrutura: dados $\rightarrow \hat{G}$
- Parâmetros: dados $\rightarrow \hat{P}$
- Inferência: $P(\mathbf{Q}=\mathbf{q}\,|\,\mathbf{E}=\mathbf{e})$
- Predição: $f(x_1, \dots, x_p) \mapsto c$
Inferência
Definição
A partir de uma rede Bayesiana completamente especificada, desejamos calcular $P(\mathbf{Q}=\mathbf{q}\,|\,\mathbf{E}=\mathbf{e}) = p(\mathbf{q}\,|\,\mathbf{e})$.
Essa expressão é teoricamente possível de se obter, já que
$$ p(\mathbf{q}\,|\,\mathbf{e}) = \frac{\sum\limits_{\mathbf{z} \in \mathbf{X}\backslash{\mathbf{Q}, \mathbf{E}}} p(\mathbf{x})}{\sum\limits_{\mathbf{z} \in \mathbf{X}\backslash {\mathbf{E}}} p(\mathbf{x})}. $$
No entanto, o número de termos dessas somas cresce exponencialmente com o tamanho da rede. O problema é intratável mesmo para redes pequenas (NP-difícil).
Algoritmos aproximados
Objetivo: obter uma estimativa eficiente que erre a inferência em no máximo $\epsilon$ com probabilidade $\delta$.
Tipos de erro
Absoluto: $\epsilon = |\hat{p} - p|$
Relativo: $\varepsilon = \frac{|\hat{p} - p|}{p}$
Como a ideia é trabalhar com redes e inferências grandes, geralmente as probabilidades a serem obtidas são pequenas. Nesses casos, o erro relativo é preferível.
Inferência por amostragem simples | descrição
- Técnica simples de Monte Carlo.
- Consiste em simular da rede Bayesiana a partir de uma ordem topológica.
- A estimativa da probabilidade é a razão das proporções de resultados $M$ e $N$ que satisfazem as consultas $p(\mathbf{q},\mathbf{e})$ e $p(\mathbf{e})$, respectivamente.
Usando a lei fraca de Khintchine, podemos mostrar que
$$ M/N \overset{P}{\to} p(\mathbf{q}|\mathbf{e}) $$
Inferência por amostragem | complexidade
Seja $\hat{p}$ uma estimativa de $p = P(\mathbf{W}=\mathbf{w})$ obtida via amostragem simples com $N$ iterações. Pela desigualdade de Hoeffding, temos que
$$ P(|\hat{p} - p| > \epsilon) \leq 2e^{-2N\epsilon^2} $$
A desigualdade sugere que o tamanho de amostra necessário para atingir um erro $\epsilon$ com probabilidade $\delta$ é
$$ N \geq \log(2/\delta) / 2\epsilon^2 $$
Inferência por amostragem | complexidade
Para trabalhar com erros relativos, trabalhamos com outra desigualdade. Pela desigualdade de Chernoff, temos que
$$ P(\frac{|\hat{p} - p|}{p} > \epsilon) \leq 2e^{-2Np\epsilon^2/3}, $$
Nesse caso, o tamanho de amostra necessário é
$$ N \geq 3\log(2/\delta) / p\epsilon^2, $$
que depende de $p$.
Amostragem por importância | descrição
Na lousa
Variância limitada local
Na lousa
Algoritmo da variância limitada | descrição
Na lousa
Exemplo
Exemplo
Uma consulta que podemos fazer é $p(X_0 = TRUE|X1 = LOW)$.
A probabilidade exata dessa consulta é de 37,04%. Essa consulta é interessante pois o denominador $p(X_0 = TRUE, X1 = LOW)$ é de aproximadamente 4%, o que pode evidenciar dificuldades nos algoritmos que não funcionam bem para valores baixos de probabilidade.
Exemplo
Primeiramente, fizemos a consulta para uma amostra de tamanho 100, replicada quinze vezes.
Exemplo | Amostra de tamanho 100
library(dplyr) library(ggplot2) d <- readRDS('../data-raw/res_100_2.rds') lapply(seq_along(d), function(i) { d[[i]]$iter <- i d[[i]] }) %>% bind_rows() %>% mutate(algo = ifelse(algo == '', 'GS', algo)) %>% filter(algo != 'GS') %>% ggplot(aes(x = algo, y = r)) + geom_hline(yintercept = 0.3702, colour = 'red') + geom_hline(yintercept = c(1, 0), colour = 'black', linetype = 2) + scale_y_continuous(limits = c(0, 1)) + geom_point() + theme_bw() + xlab('Algoritmo') + ylab('Resultado')
Exemplo | Amostra de tamanho 100
É possível notar:
- Para um tamanho de amostra pequeno, os algoritmos de simulação lógica e por importância apresentam resultados e tempos similares.
- O algoritmo de variância limitada apresenta mais resultados próximos do valor real, com menor variância.
Exemplo | Amostra de tamanho 1000
library(dplyr) library(ggplot2) d <- readRDS('../data-raw/res_1000_2.rds') lapply(seq_along(d), function(i) { d[[i]]$iter <- i d[[i]] }) %>% bind_rows() %>% mutate(algo = ifelse(algo == '', 'GS', algo)) %>% filter(algo != 'GS') %>% ggplot(aes(x = algo, y = r)) + geom_hline(yintercept = 0.3702, colour = 'red') + geom_hline(yintercept = c(1, 0), colour = 'black', linetype = 2) + scale_y_continuous(limits = c(0, 1)) + geom_point() + theme_bw() + xlab('Algoritmo') + ylab('Resultado')
Exemplo | Amostra de tamanho 1000
- Novamente, os algoritmos de amostragem lógica e por importância apresentaram tempos e resultados similares. A variância da amostragem por importância foi menor (desvio padrão de 0.04 contra desvio padrão de 0.05 da amostragem lógica e 0.06 da variância limitada)
- O algoritmo de variância limitada apresentou maior variabilidade em relação ao tempo de execução. Isso pode ter acontecido por conta dos passos "não lineares" que o algoritmo realiza.
Fim
R Package Documentation
Browse R Packages
We want your feedback!
Note that we can't provide technical support on individual packages. You should contact the package authors for that.
Embedding an R snippet on your website
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.