Uma introdução suave à cadeia de Markov Monte Carlo para a Probabilidade

Inferência probabilística envolve a estimativa de um valor ou densidade esperada usando um modelo probabilístico.

A maioria das vezes, a inferência directa de valores não é rastreável com modelos probabilísticos, e em vez disso, devem ser utilizados métodos de aproximação.

Amostras de Monte Carlo em cadeia Markov fornece uma classe de algoritmos para a amostragem aleatória sistemática a partir de distribuições de probabilidade de alta dimensão. Ao contrário dos métodos de amostragem Monte Carlo que são capazes de retirar amostras independentes da distribuição, os métodos de Markov Chain Monte Carlo retiram amostras onde a amostra seguinte depende da amostra existente, denominada Markov Chain. Isto permite que os algoritmos diminuam a quantidade que está a ser aproximada da distribuição, mesmo com um grande número de variáveis aleatórias.

Neste post, descobrirá uma introdução suave à Markov Chain Monte Carlo para aprendizagem de máquinas.

Após a leitura deste post, saberá:

• Amostras de Monte Carlo não é eficaz e pode ser intratável para modelos probabilísticos de alta dimensão.
• Markov Chain Monte Carlo fornece uma abordagem alternativa à amostragem aleatória uma distribuição de probabilidade de alta dimensão onde a amostra seguinte depende da amostra actual.
• Gibbs Sampling e o algoritmo mais geral Metropolis-Hastings são as duas abordagens mais comuns à amostragem Markov Chain Monte Carlo.

Kick- start your project with my new book Probability for Machine Learning, including step-by-step tutorials and the Python source code files for all examples.

P>Vamos começar.

Overvisão

Este tutorial está dividido em três partes; são elas

1. Desafio da Inferência Probabilística
2. O que é a cadeia de Markov Monte Carlo
3. Algoritmos da cadeia de Markov Monte Carlo

Desafio da Inferência Probabilística

Calcular uma quantidade a partir de um modelo probabilístico é referido de forma mais geral como inferência probabilística, ou simplesmente inferência.

Por exemplo, podemos estar interessados em calcular uma probabilidade esperada, estimando a densidade, ou outras propriedades da distribuição da probabilidade. Este é o objectivo do modelo probabilístico, e o nome da inferência realizada assume frequentemente o nome do modelo probabilístico, por exemplo, Bayesian Inference é realizado com um modelo probabilístico Bayesiano.

O cálculo directo da quantidade desejada a partir de um modelo de interesse é intratável para todos, excepto para os modelos probabilísticos mais triviais. Em vez disso, a probabilidade ou densidade esperada deve ser aproximada por outros meios.

Para a maioria dos modelos probabilísticos de interesse prático, a inferência exacta é intratável, pelo que temos de recorrer a alguma forma de aproximação.

– Página 523, Pattern Recognition and Machine Learning, 2006.

O cálculo desejado é tipicamente uma soma de uma distribuição discreta de muitas variáveis aleatórias ou integral de uma distribuição contínua de muitas variáveis e é intratável de calcular. Este problema existe em ambas as escolas de probabilidade, embora seja talvez mais prevalecente ou comum com a probabilidade Bayesiana e integrando sobre uma distribuição posterior para um modelo.

p>Bayesianos, e por vezes também frequentadores, precisam de se integrar sobre distribuições de probabilidade possivelmente de alta dimensão para fazer inferências sobre parâmetros do modelo ou para fazer previsões. Os Bayesianos precisam de se integrar sobre a distribuição posterior dos parâmetros do modelo dado os dados, e os frequentadores podem precisar de se integrar sobre a distribuição dos observáveis dado os valores dos parâmetros.

– Página 1, Markov Chain Monte Carlo in Practice, 1996.

A solução típica é retirar amostras independentes da distribuição de probabilidade, depois repetir este processo muitas vezes para aproximar a quantidade desejada. Isto é referido como amostragem Monte Carlo ou integração Monte Carlo, nome da cidade do Mónaco que tem muitos casinos.

O problema com a amostragem Monte Carlo é que ela não funciona bem em grandes dimensões. Isto deve-se em primeiro lugar à maldição da dimensionalidade, onde o volume do espaço de amostragem aumenta exponencialmente com o número de parâmetros (dimensões).

Segundamente, e talvez de forma mais crítica, isto deve-se ao facto de a amostragem de Monte Carlo assumir que cada amostra aleatória retirada da distribuição alvo é independente e pode ser retirada de forma independente. Este não é tipicamente o caso ou intratável para inferência com modelos probabilísticos Bayesianos estruturados ou gráficos.

Quer aprender Probabilidade para Aprendizagem por Máquina

Realizar agora o meu curso de 7 dias grátis por correio electrónico (com código de amostra).

Clique para se inscrever e obter também uma versão PDF Ebook gratuita do curso.

Download Your FREE Mini-Course

O que é Markov Chain Monte Carlo

A solução para as distribuições de probabilidade de amostragem em grandes dimensões é usar Markov Chain Monte Carlo, ou MCMC para abreviar.

O método mais popular para a amostragem a partir de distribuições em altas dimensões é a cadeia de Markov Monte Carlo ou MCMC

– Página 837, Aprendizagem de Máquina: A Probabilistic Perspective, 2012.

Métodos Monte Carlo, Markov Chain Monte Carlo foi desenvolvido pela primeira vez ao mesmo tempo que o desenvolvimento dos primeiros computadores e foi utilizado em cálculos para a física de partículas necessária como parte do projecto de Manhattan para o desenvolvimento da bomba atómica.

Monte Carlo

Monte Carlo é uma técnica para a amostragem aleatória de uma distribuição de probabilidade e a aproximação de uma quantidade desejada.

algoritmos de Monte Carlo, são utilizados em muitos ramos da ciência para estimar quantidades que são difíceis de calcular exactamente.

– Página 530, Inteligência Artificial: A Modern Approach, 3ª edição, 2009.

Monte Carlo métodos tipicamente assumem que podemos retirar eficazmente amostras da distribuição alvo. A partir das amostras que são retiradas, podemos então estimar a soma ou quantidade integral como a média ou variância das amostras retiradas.

Uma forma útil de pensar sobre um processo de amostragem Monte Carlo é considerar uma forma bidimensional complexa, tal como uma espiral. Não podemos facilmente definir uma função para descrever a espiral, mas podemos ser capazes de retirar amostras do domínio e determinar se elas fazem ou não parte da espiral. Em conjunto, um grande número de amostras retiradas do domínio permitir-nos-á resumir a forma (densidade de probabilidade) da espiral.

Markov Chain

Markov chain é um método sistemático para gerar uma sequência de variáveis aleatórias em que o valor actual depende probabilisticamente do valor da variável anterior. Especificamente, a selecção da variável seguinte depende apenas da última variável da cadeia.

Uma cadeia de Markov é um tipo especial de processo estocástico, que trata da caracterização de sequências de variáveis aleatórias. São pagos juros especiais à dinâmica e aos comportamentos limitantes da sequência.

– Página 113, Markov Chain Monte Carlo: Simulação Estocástica para Inferência Bayesiana, 2006.

Considerar um jogo de tabuleiro que envolve lançar dados, tais como serpentes e escadas (ou calhas e escadotes). O lançamento de um dado tem uma distribuição de probabilidade uniforme em 6 etapas (números inteiros 1 a 6). Tem uma posição no tabuleiro, mas a sua próxima posição no tabuleiro é baseada apenas na posição actual e no lançamento aleatório dos dados. As suas posições específicas no tabuleiro formam uma corrente Markov.

Outro exemplo de uma corrente Markov é uma caminhada aleatória numa dimensão, onde os movimentos possíveis são 1, -1, escolhidos com igual probabilidade, e o próximo ponto na linha do número na caminhada depende apenas da posição actual e do movimento escolhido aleatoriamente.

A um nível elevado, uma cadeia de Markov é definida em termos de um gráfico de estados sobre os quais o algoritmo de amostragem faz um passeio aleatório.

– Página 507, Modelos Gráficos Probabilísticos: Princípios e Técnicas, 2009.

Cadeia Markov Monte Carlo

Combinando estes dois métodos, Cadeia Markov e Monte Carlo, permite a amostragem aleatória de distribuições de probabilidade de alta dimensão que honram a dependência probabilística entre amostras através da construção de uma Cadeia Markov que compreende a amostra Monte Carlo.

p>MCMC é essencialmente uma integração Monte Carlo utilizando cadeias Markov. A integração Monte Carlo retira amostras da distribuição necessária, e depois forma médias de amostras para aproximar as expectativas. A cadeia de Markov Monte Carlo extrai estas amostras executando uma cadeia de Markov inteligentemente construída durante muito tempo.

– Página 1, Markov Chain Monte Carlo in Practice, 1996.

Especificamente, o MCMC é para realizar inferências (por exemplo, estimar uma quantidade ou uma densidade) para distribuições de probabilidade onde amostras independentes da distribuição não podem ser extraídas, ou não podem ser extraídas facilmente.

Como tal, a amostragem Monte Carlo não pode ser utilizada.

Em vez disso, as amostras são retiradas da distribuição de probabilidade através da construção de uma cadeia de Markov, onde a amostra seguinte que é retirada da distribuição de probabilidade depende da última amostra que foi retirada. A ideia é que a cadeia irá assentar (encontrar o equilíbrio) na quantidade desejada que estamos a inferir.

Yet, ainda estamos a recolher amostras da distribuição de probabilidade alvo com o objectivo de aproximar uma quantidade desejada, pelo que é apropriado referir a recolha resultante de amostras como uma amostra Monte Carlo, por exemplo, a extensão das amostras recolhidas forma frequentemente uma longa cadeia de Markov.

A ideia de impor uma dependência entre amostras pode parecer estranha no início, mas pode fazer mais sentido se considerarmos domínios como o passeio aleatório ou os jogos de serpentes e escadas, onde tal dependência entre amostras é necessária.

Algoritmos de Markov Chain Monte Carlo

Existem muitos algoritmos de Markov Chain Monte Carlo que, na sua maioria, definem diferentes formas de construção da Cadeia de Markov ao executar cada amostra Monte Carlo.

A caminhada aleatória fornece uma boa metáfora para a construção da cadeia de amostras de Markov, mas é muito ineficiente. Considere o caso em que podemos querer calcular a probabilidade esperada; é mais eficiente fazer zoom sobre essa quantidade ou densidade, em vez de vaguear pelo domínio. Os algoritmos da cadeia de Markov Monte Carlo são tentativas de aproveitar cuidadosamente as propriedades do problema, a fim de construir a cadeia de forma eficiente.

Esta sequência é construída de modo a que, embora a primeira amostra possa ser gerada a partir da anterior, sejam geradas amostras sucessivas a partir de distribuições que provavelmente se aproximam cada vez mais do posterior desejado.

– Página 505, Modelos Gráficos Probabilísticos: Princípios e Técnicas, 2009.

algoritmosMCMC são sensíveis ao seu ponto de partida, e muitas vezes requerem uma fase de aquecimento ou de burn-in para se deslocarem para uma parte frutífera do espaço de pesquisa, após o que amostras anteriores podem ser descartadas e amostras úteis podem ser recolhidas.

Adicionalmente, pode ser um desafio saber se uma cadeia convergiu e recolheu um número suficiente de passos. Muitas vezes é necessário um número muito grande de amostras e uma corrida é interrompida dado um número fixo de passos.

… é necessário descartar algumas das amostras iniciais até a cadeia de Markov ter entrado em combustão, ou entrar na sua distribuição estacionária.

– Página 838, Aprendizagem da Máquina: A Probabilistic Perspective, 2012.

O algoritmo geral mais comum da cadeia de Markov Monte Carlo chama-se Gibbs Sampling; uma versão mais geral deste amostrador chama-se Metropolis-Hastings algoritmo.

Vamos dar uma olhada mais atenta a ambos os métodos.

Algoritmo de Amostragem Gibbs

O algoritmo de Amostragem Gibbs é uma abordagem à construção de uma cadeia de Markov onde a probabilidade da próxima amostra é calculada como a probabilidade condicional dada à amostra anterior.

As amostras são construídas alterando uma variável aleatória de cada vez, o que significa que as amostras subsequentes estão muito próximas no espaço de pesquisa, por exemplo, local. Como tal, existe algum risco da cadeia ficar presa.

A ideia por detrás da amostragem de Gibbs é a de que nós amostramos cada variável por sua vez, condicionada aos valores de todas as outras variáveis na distribuição.

– Página 838, Machine Learning: A Probabilistic Perspective, 2012.

Gibbs A amostragem é apropriada para aqueles modelos probabilísticos onde esta probabilidade condicional pode ser calculada, por exemplo, a distribuição é discreta em vez de contínua.

… A amostragem Gibbs é aplicável apenas em determinadas circunstâncias; em particular, devemos ser capazes de amostrar a partir da distribuição P(Xi | x-i). Embora esta etapa de amostragem seja fácil para modelos gráficos discretos, em modelos contínuos, a distribuição condicional pode não ser uma que tenha uma forma paramétrica que permita a amostragem, pelo que Gibbs não é aplicável.

– Página 515, Modelos Gráficos Probabilísticos: Principles and Techniques, 2009.

Metropolis-Hastings Algorithm

O Algoritmo Metropolis-Hastings é apropriado para aqueles modelos probabilísticos onde não podemos amostrar directamente a chamada próxima distribuição de probabilidade estatal, tal como a distribuição de probabilidade condicional utilizada por Gibbs Amostragem.

Não parecido com a cadeia de Gibbs, o algoritmo não assume que possamos gerar amostras do estado seguinte a partir de uma determinada distribuição alvo.

– Página 517, Modelos Gráficos Probabilísticos: Princípios e Técnicas, 2009.

Em vez disso, o algoritmo Metropolis-Hastings envolve a utilização de uma distribuição de probabilidade substituta ou proposta que é amostrada (por vezes chamada de núcleo), depois um critério de aceitação que decide se a nova amostra é aceite na cadeia ou descartada.

São baseados numa cadeia de Markov cuja dependência do predecessor é dividida em duas partes: uma proposta e uma aceitação da proposta. As propostas sugerem um próximo passo arbitrário na trajectória da cadeia e a aceitação assegura a manutenção da direcção limite apropriada, rejeitando movimentos indesejados da cadeia.

– Página 6, Markov Chain Monte Carlo: Stochastic Simulation for Bayesian Inference, 2006.

O critério de aceitação é probabilístico com base na probabilidade de a distribuição da proposta diferir da verdadeira distribuição da probabilidade do próximo estado.

O Algoritmo Metropolis-Hastings é um algoritmo mais geral e flexível da cadeia de Markov Monte Carlo, subsumindo muitos outros métodos.

Por exemplo, se a distribuição de probabilidade condicional da próxima etapa for usada como distribuição da proposta, então o Algoritmo Metropolis-Hastings é geralmente equivalente ao Algoritmo de Amostragem de Gibbs. Se uma distribuição de proposta simétrica for usada como um Gaussian, o algoritmo é equivalente a outro método MCMC chamado algoritmo de Metropolis.

Outra Leitura

Esta secção fornece mais recursos sobre o tópico se estiver a procurar ir mais fundo.

Livros

• Markov Chain Monte Carlo in Practice, 1996.
• Markov Chain Monte Carlo: Stochastic Simulation for Bayesian Inference, 2006.
• Handbook of Markov Chain Monte Carlo, 2011.
• Modelos Gráficos Probabilísticos: Princípios e Técnicas, 2009.

Capítulos

• Capítulo 24 da Cadeia de Markov Monte Carlo (MCMC) inferência, Aprendizagem de Máquina: A Probabilistic Perspective, 2012.
• Secção 11.2. Markov Chain Monte Carlo, Padrão de Reconhecimento e Aprendizagem Mecânica, 2006.

Secção 17.3 Markov Chain Monte Carlo Methods, Deep Learning, 2016.

Artigos

• Método Monte Carlo, Wikipedia.
• Cadeia de Markov, Wikipedia.
• Corrente de Markov Monte Carlo, Wikipedia.
• Amostragem de Gibbs, Wikipedia.

algoritmo Metropolis-Hastings, Wikipedia.li> Amostragem de MCMC para manequins, 2015.li> Como explicaria a corrente de Markov Monte Carlo (MCMC) a um leigo?

Sumário

Neste post, descobriu uma introdução gentil à Markov Chain Monte Carlo para aprendizagem de máquinas.

Específica, aprendeu:

• Amostras de Markov Chain Monte Carlo não é eficaz e pode ser intratável para modelos probabilísticos de alta dimensão.
• Markov Chain Monte Carlo fornece uma abordagem alternativa à amostragem aleatória uma distribuição de probabilidade de alta dimensão em que a amostra seguinte depende da amostra actual.
• Amostragem de Gibbs e o algoritmo mais geral Metropolis-Hastings são as duas abordagens mais comuns à amostragem de Markov Chain Monte Carlo.

Tem alguma questão?
Saber as vossas questões nos comentários abaixo e farei o meu melhor para responder.