MCMC - DME – IM – UFRJ

1.
Cadeias de Markov
1.
Cadeias de Markov
Cadeia de Markov → Sequência de variáveis aleatórias {Xj : j ∈ N +}
tal que,
p(xj | xj−1, ..., x1) = p(xj | xj−1), ∀j
S → Espaço de estados: conjunto de possı́veis valores de X.
1.
Cadeias de Markov
Cadeia de Markov → Sequência de variáveis aleatórias {Xj : j ∈ N +}
tal que,
p(xj | xj−1, ..., x1) = p(xj | xj−1), ∀j
S → Espaço de estados: conjunto de possı́veis valores de X.
Distribuição conjunta da Cadeia de Markov:
p(x1, x2, ...) =
∞
Y
j=1
com valor inicial x0
p(xj | xj−1)
1.
Cadeias de Markov
Cadeia de Markov → Sequência de variáveis aleatórias {Xj : j ∈ N +}
tal que,
p(xj | xj−1, ..., x1) = p(xj | xj−1), ∀j
S → Espaço de estados: conjunto de possı́veis valores de X.
Distribuição conjunta da Cadeia de Markov:
p(x1, x2, ...) =
∞
Y
p(xj | xj−1)
j=1
com valor inicial x0
Qj → Matriz de transição na iteração j
(j)
qi,k = p(Xj = sk | Xj−1 = si), S = {s1, s2, ...}
Cadeia Homogênea: Qj = Q, para todo j.
2.
Monte Carlo em Cadeias de Markov
2.
Monte Carlo em Cadeias de Markov
O MCMC permite a simulação de distribuições de forma indireta
2.
Monte Carlo em Cadeias de Markov
O MCMC permite a simulação de distribuições de forma indireta
A idéia é construir uma cadeia de Markov fácil de ser simulada, e com
distribuição de equilı́brio igual à de interesse
2.
Monte Carlo em Cadeias de Markov
O MCMC permite a simulação de distribuições de forma indireta
A idéia é construir uma cadeia de Markov fácil de ser simulada, e com
distribuição de equilı́brio igual à de interesse
Após um número suficientemente grande de iterações, a cadeia converge
para a distribuição de interesse
2.
Monte Carlo em Cadeias de Markov
O MCMC permite a simulação de distribuições de forma indireta
A idéia é construir uma cadeia de Markov fácil de ser simulada, e com
distribuição de equilı́brio igual à de interesse
Após um número suficientemente grande de iterações, a cadeia converge
para a distribuição de interesse
Largamente usados na estatı́stica Bayesiana para simular de p(θ | Y ) cuja
geração direta é complicada.
2.
Monte Carlo em Cadeias de Markov
O MCMC permite a simulação de distribuições de forma indireta
A idéia é construir uma cadeia de Markov fácil de ser simulada, e com
distribuição de equilı́brio igual à de interesse
Após um número suficientemente grande de iterações, a cadeia converge
para a distribuição de interesse
Largamente usados na estatı́stica Bayesiana para simular de p(θ | Y ) cuja
geração direta é complicada.
Referência: Gamerman (1999)
Algoritmo de Metropolis-Hastings
Algoritmo de Metropolis-Hastings
Utiliza uma função de transição de x para y: q(x, y)
Algoritmo de Metropolis-Hastings
Utiliza uma função de transição de x para y: q(x, y)
A função q(x, .) define uma distribuição condicional que governa as transições
do estado x
Algoritmo de Metropolis-Hastings
Utiliza uma função de transição de x para y: q(x, y)
A função q(x, .) define uma distribuição condicional que governa as transições
do estado x
Propriedades:
Algoritmo de Metropolis-Hastings
Utiliza uma função de transição de x para y: q(x, y)
A função q(x, .) define uma distribuição condicional que governa as transições
do estado x
Propriedades:
R
→ q(x, y)dy = 1;
Algoritmo de Metropolis-Hastings
Utiliza uma função de transição de x para y: q(x, y)
A função q(x, .) define uma distribuição condicional que governa as transições
do estado x
Propriedades:
R
→ q(x, y)dy = 1;
→ q(x, y) pode ser avaliada para todo x e y;
Algoritmo de Metropolis-Hastings
Utiliza uma função de transição de x para y: q(x, y)
A função q(x, .) define uma distribuição condicional que governa as transições
do estado x
Propriedades:
R
→ q(x, y)dy = 1;
→ q(x, y) pode ser avaliada para todo x e y;
→ para cada x, é possı́vel simular realizações da distribuição que tem
densidade q(x, ·).
Parâmetros do modelo: θ = (θ1, ..., θp)
Parâmetros do modelo: θ = (θ1, ..., θp)
O algoritmo é inicializado a partir de um ponto artitrário θ(0)
Parâmetros do modelo: θ = (θ1, ..., θp)
O algoritmo é inicializado a partir de um ponto artitrário θ(0)
1. Faça j = 1
Parâmetros do modelo: θ = (θ1, ..., θp)
O algoritmo é inicializado a partir de um ponto artitrário θ(0)
1. Faça j = 1
2. Simule θ(j) ∼ q(θ(j−1), ·)
Parâmetros do modelo: θ = (θ1, ..., θp)
O algoritmo é inicializado a partir de um ponto artitrário θ(0)
1. Faça j = 1
2. Simule θ(j) ∼ q(θ(j−1), ·)
3. Avalie a razão de Hastings R =
p(θ(j) )q(θ(j) ,θ(j−1) )
p(θ(j−1) )q(θ(j−1) ,θ(j) )
Parâmetros do modelo: θ = (θ1, ..., θp)
O algoritmo é inicializado a partir de um ponto artitrário θ(0)
1. Faça j = 1
2. Simule θ(j) ∼ q(θ(j−1), ·)
3. Avalie a razão de Hastings R =
p(θ(j) )q(θ(j) ,θ(j−1) )
p(θ(j−1) )q(θ(j−1) ,θ(j) )
4. O próximo ponto da cadeia é igual a θ(j) com probabilidade min(1, R),
e é igual a θ(j−1) com probabilidade complementar a essa.
Parâmetros do modelo: θ = (θ1, ..., θp)
O algoritmo é inicializado a partir de um ponto artitrário θ(0)
1. Faça j = 1
2. Simule θ(j) ∼ q(θ(j−1), ·)
3. Avalie a razão de Hastings R =
p(θ(j) )q(θ(j) ,θ(j−1) )
p(θ(j−1) )q(θ(j−1) ,θ(j) )
4. O próximo ponto da cadeia é igual a θ(j) com probabilidade min(1, R),
e é igual a θ(j−1) com probabilidade complementar a essa.
5. Faça j = j + 1 e retorne ao passo 2.
Parâmetros do modelo: θ = (θ1, ..., θp)
O algoritmo é inicializado a partir de um ponto artitrário θ(0)
1. Faça j = 1
2. Simule θ(j) ∼ q(θ(j−1), ·)
3. Avalie a razão de Hastings R =
p(θ(j) )q(θ(j) ,θ(j−1) )
p(θ(j−1) )q(θ(j−1) ,θ(j) )
4. O próximo ponto da cadeia é igual a θ(j) com probabilidade min(1, R),
e é igual a θ(j−1) com probabilidade complementar a essa.
5. Faça j = j + 1 e retorne ao passo 2.
os valores simulados após a convergência podem ser considerados como
amostras da densidade de interesse.
Metropolis-Hastings com uma variável por vez
Metropolis-Hastings com uma variável por vez
suponha que não é possı́vel (ou custoso) amostrar da densidade conjunta
de θ = (θ1, ..., θp)
Metropolis-Hastings com uma variável por vez
suponha que não é possı́vel (ou custoso) amostrar da densidade conjunta
de θ = (θ1, ..., θp)
Uma alternativa é atualizar cada parâmetro separadamente
Metropolis-Hastings com uma variável por vez
suponha que não é possı́vel (ou custoso) amostrar da densidade conjunta
de θ = (θ1, ..., θp)
Uma alternativa é atualizar cada parâmetro separadamente
1. Faça j = 1, i = 1
Metropolis-Hastings com uma variável por vez
suponha que não é possı́vel (ou custoso) amostrar da densidade conjunta
de θ = (θ1, ..., θp)
Uma alternativa é atualizar cada parâmetro separadamente
1. Faça j = 1, i = 1
(j)
(j−1)
2. Simule θi ∼ qi (θi
(j)
(j)
(j)
(j)
(j−1)
(j−1)
, ·; Θ−i ) e defina Θ−i = (θ1 , ..., θi−1 , θi+1 , ..., θp
)
Metropolis-Hastings com uma variável por vez
suponha que não é possı́vel (ou custoso) amostrar da densidade conjunta
de θ = (θ1, ..., θp)
Uma alternativa é atualizar cada parâmetro separadamente
1. Faça j = 1, i = 1
(j)
(j−1)
2. Simule θi ∼ qi (θi
(j)
(j)
(j)
(j)
(j−1)
(j−1)
, ·; Θ−i ) e defina Θ−i = (θ1 , ..., θi−1 , θi+1 , ..., θp
3. Avalie a razão de Hastings R =
(j) (j)
(j) (j−1)
(j)
;Θ−i )
(j) (j−1)
(j−1) (j)
(j)
p(Θ−i ,θi
)qi (θi
,θi ;Θ−i )
p(Θ−i ,θi )qi (θi ,θi
)
Metropolis-Hastings com uma variável por vez
suponha que não é possı́vel (ou custoso) amostrar da densidade conjunta
de θ = (θ1, ..., θp)
Uma alternativa é atualizar cada parâmetro separadamente
1. Faça j = 1, i = 1
(j)
(j−1)
2. Simule θi ∼ qi (θi
(j)
3. Avalie a razão de Hastings R =
(j)
(j)
(j)
(j)
(j)
(j−1)
(j−1)
, ·; Θ−i ) e defina Θ−i = (θ1 , ..., θi−1 , θi+1 , ..., θp
)
(j) (j)
(j) (j−1)
(j)
;Θ−i )
(j) (j−1)
(j−1) (j)
(j)
p(Θ−i ,θi
)qi (θi
,θi ;Θ−i )
p(Θ−i ,θi )qi (θi ,θi
4. (Θ−i , θi ) será o novo ponto da cadeia com probabilidade min(1, R), que per(j) (j−1)
manecerá em (Θ−i , θi
) com probabilidade complementar.
Metropolis-Hastings com uma variável por vez
suponha que não é possı́vel (ou custoso) amostrar da densidade conjunta
de θ = (θ1, ..., θp)
Uma alternativa é atualizar cada parâmetro separadamente
1. Faça j = 1, i = 1
(j)
(j−1)
2. Simule θi ∼ qi (θi
(j)
3. Avalie a razão de Hastings R =
(j)
(j)
(j)
(j)
(j−1)
(j−1)
, ·; Θ−i ) e defina Θ−i = (θ1 , ..., θi−1 , θi+1 , ..., θp
)
(j) (j)
(j) (j−1)
(j)
;Θ−i )
(j) (j−1)
(j−1) (j)
(j)
p(Θ−i ,θi
)qi (θi
,θi ;Θ−i )
p(Θ−i ,θi )qi (θi ,θi
(j)
4. (Θ−i , θi ) será o novo ponto da cadeia com probabilidade min(1, R), que per(j) (j−1)
manecerá em (Θ−i , θi
) com probabilidade complementar.
5. Se i < p faça i = i + 1 e retorne ao passo 2.
Metropolis-Hastings com uma variável por vez
suponha que não é possı́vel (ou custoso) amostrar da densidade conjunta
de θ = (θ1, ..., θp)
Uma alternativa é atualizar cada parâmetro separadamente
1. Faça j = 1, i = 1
(j)
(j−1)
2. Simule θi ∼ qi (θi
(j)
(j)
(j)
3. Avalie a razão de Hastings R =
(j)
(j)
(j)
(j−1)
(j−1)
, ·; Θ−i ) e defina Θ−i = (θ1 , ..., θi−1 , θi+1 , ..., θp
(j)
(j)
(j−1)
p(Θ−i ,θi )qi (θi ,θi
(j)
(j−1)
p(Θ−i ,θi
(j−1)
)qi (θi
(j)
)
(j)
;Θ−i )
(j)
(j)
,θi ;Θ−i )
4. (Θ−i , θi ) será o novo ponto da cadeia com probabilidade min(1, R), que per(j) (j−1)
manecerá em (Θ−i , θi
) com probabilidade complementar.
5. Se i < p faça i = i + 1 e retorne ao passo 2.
6. Faça j = j + 1 e i = 1.
Outra possibilidade é a de dividir o vetor paramétrico θ = (θ1, ..., θp) em
blocos
Outra possibilidade é a de dividir o vetor paramétrico θ = (θ1, ..., θp) em
blocos
• Parâmetros atualizados conjuntamente dentro de cada bloco
Outra possibilidade é a de dividir o vetor paramétrico θ = (θ1, ..., θp) em
blocos
• Parâmetros atualizados conjuntamente dentro de cada bloco
• Cada bloco é amostrado separadamente
Outra possibilidade é a de dividir o vetor paramétrico θ = (θ1, ..., θp) em
blocos
• Parâmetros atualizados conjuntamente dentro de cada bloco
• Cada bloco é amostrado separadamente
Terı́amos então uma mistura desses dois algoritmos.
Amostrador de Gibbs
Amostrador de Gibbs
Transição de um estado a outro feita através de distribuições condicionais
completas.
Amostrador de Gibbs
Transição de um estado a outro feita através de distribuições condicionais
completas.
Caso particular do algoritmo de Metropolis-Hastings com uma variável
(j)
(j)
por vez, fazendo qi(θi, ·; Θ−i ) = p(· | Θ−i )
Amostrador de Gibbs
Transição de um estado a outro feita através de distribuições condicionais
completas.
Caso particular do algoritmo de Metropolis-Hastings com uma variável
(j)
(j)
por vez, fazendo qi(θi, ·; Θ−i ) = p(· | Θ−i )
a razão de Hastings é igual a 1, e a proposta será sempre aceita.
Amostrador de Gibbs
Transição de um estado a outro feita através de distribuições condicionais
completas.
Caso particular do algoritmo de Metropolis-Hastings com uma variável
(j)
(j)
por vez, fazendo qi(θi, ·; Θ−i ) = p(· | Θ−i )
a razão de Hastings é igual a 1, e a proposta será sempre aceita.
arbitrando um valor inicial θ(0), a atualização é dada por:
Amostrador de Gibbs
Transição de um estado a outro feita através de distribuições condicionais
completas.
Caso particular do algoritmo de Metropolis-Hastings com uma variável
(j)
(j)
por vez, fazendo qi(θi, ·; Θ−i ) = p(· | Θ−i )
a razão de Hastings é igual a 1, e a proposta será sempre aceita.
arbitrando um valor inicial θ(0), a atualização é dada por:
1. Faça j = 1, i = 1
Amostrador de Gibbs
Transição de um estado a outro feita através de distribuições condicionais
completas.
Caso particular do algoritmo de Metropolis-Hastings com uma variável
(j)
(j)
por vez, fazendo qi(θi, ·; Θ−i ) = p(· | Θ−i )
a razão de Hastings é igual a 1, e a proposta será sempre aceita.
arbitrando um valor inicial θ(0), a atualização é dada por:
1. Faça j = 1, i = 1
(j)
(j)
2. Simule θi ∼ p(· | Θ−i )
Amostrador de Gibbs
Transição de um estado a outro feita através de distribuições condicionais
completas.
Caso particular do algoritmo de Metropolis-Hastings com uma variável
(j)
(j)
por vez, fazendo qi(θi, ·; Θ−i ) = p(· | Θ−i )
a razão de Hastings é igual a 1, e a proposta será sempre aceita.
arbitrando um valor inicial θ(0), a atualização é dada por:
1. Faça j = 1, i = 1
(j)
(j)
2. Simule θi ∼ p(· | Θ−i )
3. Se i < p faça i = i + 1 e retorne ao passo 2
Amostrador de Gibbs
Transição de um estado a outro feita através de distribuições condicionais
completas.
Caso particular do algoritmo de Metropolis-Hastings com uma variável
(j)
(j)
por vez, fazendo qi(θi, ·; Θ−i ) = p(· | Θ−i )
a razão de Hastings é igual a 1, e a proposta será sempre aceita.
arbitrando um valor inicial θ(0), a atualização é dada por:
1. Faça j = 1, i = 1
(j)
(j)
2. Simule θi ∼ p(· | Θ−i )
3. Se i < p faça i = i + 1 e retorne ao passo 2
4. Faça j = j + 1 e i = 1
Diagnósticos de convergência
Diagnósticos de convergência
Geweke(1992)
Diagnósticos de convergência
Geweke(1992)
Idéia: Após a convergência o comportamento da Cadeia deve ser estacionário
Diagnósticos de convergência
Geweke(1992)
Idéia: Após a convergência o comportamento da Cadeia deve ser estacionário
→ Amostras do inı́cio e do final da cadeia após estacionariedade devem
ser similares
Diagnósticos de convergência
Geweke(1992)
Idéia: Após a convergência o comportamento da Cadeia deve ser estacionário
→ Amostras do inı́cio e do final da cadeia após estacionariedade devem
ser similares
A diferença padronizada entre as médias amostrais tem distribuição aproximadamente N (0, 1).
Diagnósticos de convergência
Geweke(1992)
Idéia: Após a convergência o comportamento da Cadeia deve ser estacionário
→ Amostras do inı́cio e do final da cadeia após estacionariedade devem
ser similares
A diferença padronizada entre as médias amostrais tem distribuição aproximadamente N (0, 1).
Gelman e Rubin (1992)
Gelman e Rubin (1992)
Idéia: Rodar algumas cadeias em paralelo e avaliar se seus comportamentos são semelhantes, para evitar ótimos locais
Gelman e Rubin (1992)
Idéia: Rodar algumas cadeias em paralelo e avaliar se seus comportamentos são semelhantes, para evitar ótimos locais
Sugestão: Trabalhar com fator de redução potencial de escala, dado por:
Gelman e Rubin (1992)
Idéia: Rodar algumas cadeias em paralelo e avaliar se seus comportamentos são semelhantes, para evitar ótimos locais
Sugestão: Trabalhar com fator de redução potencial de escala, dado por:
F =
p
V /W , ondeV = (1 − 1/n)W + (1/n)B
Gelman e Rubin (1992)
Idéia: Rodar algumas cadeias em paralelo e avaliar se seus comportamentos são semelhantes, para evitar ótimos locais
Sugestão: Trabalhar com fator de redução potencial de escala, dado por:
F =
p
V /W , ondeV = (1 − 1/n)W + (1/n)B
W: Variância dentro das cadeias
Gelman e Rubin (1992)
Idéia: Rodar algumas cadeias em paralelo e avaliar se seus comportamentos são semelhantes, para evitar ótimos locais
Sugestão: Trabalhar com fator de redução potencial de escala, dado por:
F =
p
V /W , ondeV = (1 − 1/n)W + (1/n)B
W: Variância dentro das cadeias
B: Variância entre as cadeias
Gelman e Rubin (1992)
Idéia: Rodar algumas cadeias em paralelo e avaliar se seus comportamentos são semelhantes, para evitar ótimos locais
Sugestão: Trabalhar com fator de redução potencial de escala, dado por:
F =
p
V /W , ondeV = (1 − 1/n)W + (1/n)B
W: Variância dentro das cadeias
B: Variância entre as cadeias
Em geral, F > 1. Valores aceitáveis são menores que 1, 2
Gelman e Rubin (1992)
Idéia: Rodar algumas cadeias em paralelo e avaliar se seus comportamentos são semelhantes, para evitar ótimos locais
Sugestão: Trabalhar com fator de redução potencial de escala, dado por:
F =
p
V /W , ondeV = (1 − 1/n)W + (1/n)B
W: Variância dentro das cadeias
B: Variância entre as cadeias
Em geral, F > 1. Valores aceitáveis são menores que 1, 2
Monitoração informal da convergência
Monitoração informal da convergência
Gelfand e Smith sugerem técnicas gráficas
Monitoração informal da convergência
Gelfand e Smith sugerem técnicas gráficas
Considere m cadeias paralelas
Monitoração informal da convergência
Gelfand e Smith sugerem técnicas gráficas
Considere m cadeias paralelas
A cada k iterações fazer um histograma dos m valores
Monitoração informal da convergência
Gelfand e Smith sugerem técnicas gráficas
Considere m cadeias paralelas
A cada k iterações fazer um histograma dos m valores
Histogramas parecidos: indı́cio de convergência
Monitoração informal da convergência
Gelfand e Smith sugerem técnicas gráficas
Considere m cadeias paralelas
A cada k iterações fazer um histograma dos m valores
Histogramas parecidos: indı́cio de convergência
k pequeno : influência da autocorrelação
Monitoração informal da convergência
Gelfand e Smith sugerem técnicas gráficas
Considere m cadeias paralelas
A cada k iterações fazer um histograma dos m valores
Histogramas parecidos: indı́cio de convergência
k pequeno : influência da autocorrelação
k muito grande: desnecessário