terça-feira, 11 de junho de 2013

A história do MCMC

Nicholas Metropolis (www.lanl.gov)

Esse conjunto de técnicas tão importantes para a inferência Bayesiana tem uma história singular quanto ao seu desenvolvimento e sua disseminação. Relembrando, MCMC é a sigla para Monte Carlo via cadeia de Markov. portanto, é natural que MCMC tenha surgido a partir de Monte Carlo. E assim foi.

Os métodos de Monte Carlo tiveram um grande impulso durante a 2a Guerra Mundial com os esforços conhecidos como Projeto Manhattan que acabaram, entre outras coisas, levando ao desenvolvimento das  armas nuclares usadas pelos americanos. Vários avanços teóricos foram realizados e foram devidamente publicados em periódicos científicos após a Guerra.

Um desses trabalhos foi uma técnica iterativa usada para lidar com distribuições de sistemas com um número grande de componentes, como composto químicos. A idéia de abordagem Monte Carlo direta para simular esses sistemas não funcionava e por isso técnicas Monte Carlo iterativas foram necessárias. Esse trabalho foi publicado por 5 cientistas (matemáticos, físicos e químicos) e o primeiro autor foi Nicholas Metropolis, talvez por ser o matemático do grupo, talvez pela ordem alfabética dos sobrenomes. O artigo intitulado Equation of State Calculations by Fast Computing Machines foi publicado no periódico científico Journal of Chemical Physics em 1953. Essa técnica ficou conhecida como algoritmo de Metropolis.

Vamos agora fazer um corte no tempo e viajar até o ano de 1984, quando os irmãos Stuart e Donal Geman, pesquisadores do Depto de Engenharia Elétrica da Universidade de Massachussets, publicaram o artigo Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images na revista de Engenharia IEEE Transactions on Pattern Analysis and Machine Intelligence.  Esse artigo novamente era sobre Monte Carlo iterativo em distribuições com um grande número de componentes. No caso deles, o interesse era em reconstruções de imagens, que são constituídas de várias unidades chamadas de pixels. Como a distribuição de interesse é conhecida como distribuição de Gibbs e a técnica deles era de amostragem dessa distribuição, eles cunharam a técnica como amostrador de Gibbs. Essa técnica consistia na atualização sucessiva dos pixels segundo o que acontecia com os pixels vizinhos.

Ambos os casos chamam a atenção por terem sido produzidos por grupos de pesquisadores que, apesar de saberem Estatística, não eram estatísticos. A salvação dos estatísticos veio com W. Keith Hastings, um estatístico canadense da Universidade de Toronto. Hastings publicou O trabalho chave sobre MCMC. O artigo entitulado Monte Carlo sampling methods using Markov chains and their applications foi publicado em 1970 no Biometrika, um dos mais importantes periódicos de Estatística. Esse trabalho foi o primeiro a entender e formalizar todo o ferramental por trás do que o grupo de Metropolis e até mesmo os irmãos Geman faziam. A partir do trabalho de Hastings, ficou claro que esses trabalhos nada mais eram do que casos particulares da uma estrutura geral que ele tinha percebido. Após esse trabalho, Hastings orientou um único aluno de doutorado (Peter Peskun), publicou mais 2 artigos a seguir e se transferiu para a Universidade de Victoria, também no Canadá, onde não publicou mais nada ném orientou mais nenhum aluno de doutorado!

Passaram-se 2 décadas sem que o trabalho pioneiro de Hastings fosse percebido pela comunidade estatística. (Por exemplo, o igualmente inovador artigo dos irmãos Geman não cita o trabalho de Hastings.) Esse é um daqueles trabalhos que estava muito à frente do seu tempo. Em 1990, os estatísticos Adrian Smith e Alan Gelfand publicaram um artigo comparando as propriedades do amostrados de Gibbs com outros métodos de simulação Monte Carlo e falando de seus usos na Estatística Bayesiana. O artigo era intitutlado Sampling-Based Approaches to Calculating Marginal Densities e foi publicado no Journal of the American Statistical Association, outro dos mais importantes periódicos de Estatística. Somente a partir desse artigo é que os estatísticos (especialmente os Bayesianos) perceberam a potencialidade do MCMC na resolução de problemas de Estatística com estrutura complexa e/ou muitas componentes. O que se viu foi uma verdadeira revoada na direção do MCMC com todos tentando usar essa técnica em seus problemas. Além disso, houve um fortalecimento na compreensão teórica dos métodos MCMC.

A relação do amostrador de Gibbs com o MCMC de Hastings é óbvia nos dias de hoje. Mas isso não foi sempre assim. Os irmãos Geman não perceberam isso, ném mesmo o trabalho de Gelfand e Smith percebeu isso. Não sei quem foi o primeiro a perceber. Se eu tivesse que chutar diria que foi algum dos estatísticos que trabalhavam com tratamento de imagens, como os britânicos Julian Besag, Peter Green ou Brian Ripley. Eles já usavam o amostrador de Gibbs em problemas estatísticos antes do artigo de Gelfand e Smith. Mas o estabelecimento dessa conexão era inevitável após tanta atenção que passou a ser devotada ao assunto. Hoje em dia é impensável abordar um problema de estatística não-trivial sem pensar em MCMC. Nesse meio tempo, foram propostas algumas outras técnicas de aproximação com bons resultados. Mas a generalidade do MCMC aliada à sua simplicidade me fazem acreditar que essa técnica sobreviverá por pelo menos mais algumas décadas como a principal ferramenta de aproximação no contexto Bayesiano.


4 comentários:

  1. Eu acho q o acesso cada vez maior a computadores mais rapidos e ao desenvolvimento de softwares como o BUGS, em particular o winBUGS, tem um papel importantissimo na velocidade do uso da inferencia bayesiana.

    ResponderExcluir
  2. Dani, este seu post parece uma história de mistério.. Descobri que "Hastings retired from the University of Victoria in 1992. As of this writing, he still lives in Victoria". Lembra o caso do J. D. Salinger, que, após escrever diversas obras primas, se retirou para o campo e nunca mais (ou quase nunca) falou com os jornalistas ou publicou algo. Mas, e o Hastings, qual foi a dele? Solucione essa parte do mistério do MCMC, por favor! Abraços!

    ResponderExcluir
  3. Oi Edson, não sei dizer o que passou com ele e é pouco provável que o encontremos para saber o que houve, a menos que a Camila, que visita este blog e está em Vancouver, possa desvendar esse enigma para nós. Enquanto isso não acontece, ofereço a seguinte versão: após publicar esse artigo fundamental mas muito à frente do seu tempo ele concluiu que sua missão como pesquisador estava completa e que ele deveria partir para outro ramo.

    ResponderExcluir
    Respostas
    1. Vou tentar desvendar este mistério!

      Excluir