Como você explicaria a Markov Chain Monte Carlo (MCMC) a um leigo?

Talvez o conceito, por que é usado, e um exemplo.

Primeiro, precisamos entender o que é uma cadeia de Markov. Considere o seguinte exemplo meteorológico da Wikipedia. Suponha que o clima em qualquer dia possa ser classificado apenas em dois estados: ensolarado e chuvoso. Com base na experiência passada, sabemos o seguinte:

$P(\text{Next day is Sunny}\,\vert \,\text{Given today is Rainy)}=0.50$

Como o tempo do dia seguinte é ensolarado ou chuvoso, segue-se que:

$P(\text{Next day is Rainy}\,\vert \,\text{Given today is Rainy)}=0.50$

Da mesma forma, deixe:

$P(\text{Next day is Rainy}\,\vert \,\text{Given today is Sunny)}=0.10$

Portanto, segue-se que:

$P(\text{Next day is Sunny}\,\vert \,\text{Given today is Sunny)}=0.90$

Os quatro números acima podem ser representados de maneira compacta como uma matriz de transição que representa as probabilidades de o clima passar de um estado para outro, da seguinte maneira:

$P = \begin{bmatrix} & S & R \\ S& 0.9 & 0.1 \\ R& 0.5 & 0.5 \end{bmatrix}$

Podemos fazer várias perguntas cujas respostas se seguem:

Q1: se o tempo estiver ensolarado hoje, qual é o tempo provável para amanhã?

A1: Como não sabemos com certeza o que vai acontecer, o melhor que podemos dizer é que há uma probabilidade de probabilidade de estar ensolarado e chuva.10 $90\%$$10\%$

P2: E daqui a dois dias?

A2: Previsão de um dia: ensolarado, chuvoso. Portanto, daqui a dois dias:10 $90\%$$10\%$

Primeiro dia pode fazer sol e no dia seguinte também pode fazer sol. As chances disso acontecer são: .$0.9 \times 0.9$

Ou

Primeiro dia pode estar chuvoso e segundo dia pode estar ensolarado. As chances disso acontecer são: .$0.1 \times 0.5$

Portanto, a probabilidade de o tempo ficar ensolarado em dois dias é:

$P(\text{Sunny 2 days from now} = 0.9 \times 0.9 + 0.1 \times 0.5 = 0.81 + 0.05 = 0.86$

Da mesma forma, a probabilidade de chover é:

$P(\text{Rainy 2 days from now} = 0.1 \times 0.5 + 0.9 \times 0.1 = 0.05 + 0.09 = 0.14$

Na álgebra linear (matrizes de transição), esses cálculos correspondem a todas as permutações nas transições de uma etapa para a seguinte (ensolarado para ensolarado ( ), ensolarado para chuvoso ( ), chuvoso para ensolarado ( ) ou chuvoso a chuvoso ( )) com suas probabilidades calculadas:S 2 R R 2 S R 2$S_2S$$S_2R$$R_2S$$R_2R$

Na parte inferior da imagem, vemos como calcular a probabilidade de um estado futuro ( ou ), dadas as probabilidades (função massa de probabilidade, ) para cada estado (ensolarado ou chuvoso) no tempo zero (agora ou ) como multiplicação simples de matriz.t + 2 P M F t $t+1$$t+2$$PMF$$t_0$

Se você continuar prevendo condições meteorológicas como essa, notará que, eventualmente, a previsão do dia, em que é muito grande (por exemplo, ), resolve as seguintes probabilidades de 'equilíbrio':n $n$$n$$30$

$P(\text{Sunny}) = 0.833$

e

$P(\text{Rainy}) = 0.167$

Em outras palavras, sua previsão para o ésimo dia e para o dia permanece a mesma. Além disso, você também pode verificar se as probabilidades de 'equilíbrio' não dependem do tempo hoje. Você obteria a mesma previsão para o tempo se começar assumindo que o tempo hoje está ensolarado ou chuvoso.n + $n$$n+1$

O exemplo acima só funcionará se as probabilidades de transição de estado satisfizerem várias condições que não serão discutidas aqui. Mas observe os seguintes recursos dessa cadeia de Markov 'legal' (agradável = probabilidades de transição satisfazem as condições):

Independentemente do estado inicial inicial, alcançaremos uma distribuição de probabilidade de equilíbrio dos estados.

A cadeia de Markov Monte Carlo explora o recurso acima da seguinte maneira:

Queremos gerar sorteios aleatórios a partir de uma distribuição de destino. Em seguida, identificamos uma maneira de construir uma cadeia de Markov 'agradável', de modo que sua distribuição de probabilidade de equilíbrio seja nossa distribuição alvo.

Se conseguirmos construir uma cadeia desse tipo, arbitrariamente iniciaremos a partir de algum ponto e iteraremos a cadeia de Markov várias vezes (como a previsão do tempo vezes). Eventualmente, os empates que geramos pareceriam como se fossem da nossa distribuição de destino.$n$

Em seguida, aproximamos as quantidades de interesse (por exemplo, média), tomando a média amostral dos sorteios após descartar alguns sorteios iniciais, que é o componente de Monte Carlo.

Existem várias maneiras de construir cadeias de Markov 'legais' (por exemplo, amostrador de Gibbs, algoritmo Metropolis-Hastings).

Eu acho que existe uma intuição agradável e simples a partir do algoritmo Metropolis-Hastings (da cadeia de independência).

Primeiro, qual é o objetivo? O objetivo do MCMC é coletar amostras de alguma distribuição de probabilidade sem precisar saber sua altura exata a qualquer momento. A maneira como o MCMC consegue isso é "passear" nessa distribuição de maneira que a quantidade de tempo gasto em cada local seja proporcional à altura da distribuição. Se o processo "vagando" estiver configurado corretamente, você poderá garantir que essa proporcionalidade (entre o tempo gasto e a altura da distribuição) seja alcançada.

Intuitivamente, o que queremos fazer é caminhar sobre uma superfície (irregular) de tal maneira que a quantidade de tempo que gastamos (ou # amostras coletadas) em cada local seja proporcional à altura da superfície naquele local. Por exemplo, gostaríamos de gastar o dobro do tempo no topo de uma colina, a uma altitude de 100m, como fazemos em uma colina próxima, a uma altitude de 50m. O bom é que podemos fazer isso mesmo que não saibamos as alturas absolutas dos pontos na superfície: tudo o que precisamos saber são as alturas relativas . por exemplo, se um morro A for duas vezes mais alto que o morro B, gostaríamos de passar o dobro do tempo em A do que em B.

A variante mais simples do algoritmo Metropolis-Hastings (amostragem em cadeia da independência) alcança o seguinte: suponha que em cada etapa (discreta) do tempo, escolhemos um novo local "proposto" aleatório (selecionado uniformemente em toda a superfície). Se o local proposto for mais alto do que onde estamos agora, vá para ele. Se o local proposto for mais baixo, vá para o novo local com probabilidade p, onde p é a razão entre a altura desse ponto e a altura do local atual. (ou seja, jogue uma moeda com uma probabilidade p de ganhar cara; se ela aparecer cara, vá para o novo local; se ela aparecer coroa, fique onde estamos). Mantenha uma lista dos locais em que você esteve em todas as etapas, e essa lista (assintoticamente) terá a proporção certa de tempo gasto em cada parte da superfície.

Existem esquemas mais complicados para propor novos locais e as regras para aceitá-los, mas a idéia básica ainda é: (1) escolha um novo local "proposto"; (2) descobrir quanto mais alto ou mais baixo esse local é comparado ao seu local atual; (3) probabilisticamente, permaneça parado ou mova-se para esse local de maneira a respeitar o objetivo geral de passar um tempo proporcional à altura do local.

Para que isso é útil? Suponha que tenhamos um modelo probabilístico do clima que permita avaliar A * P (clima), onde A é uma constante desconhecida. (Isso geralmente acontece - muitos modelos são convenientes para formular de uma maneira que você não possa determinar o que A é). Portanto, não podemos avaliar exatamente P ("chuva amanhã"). No entanto, podemos executar o amostrador MCMC por um tempo e depois perguntar: qual fração das amostras (ou "localizações") acabou no estado "chuva amanhã". Essa fração será a previsão do tempo probabilística (baseada em modelo).

Eu provavelmente diria algo assim:

"Sempre que queremos falar sobre probabilidades, estamos realmente integrando uma densidade. Na análise bayesiana, muitas das densidades que criamos não são analiticamente tratáveis: você só pode integrá-las - se é que pode integrá-las. - com muito sofrimento. Então, o que fazemos é simular muito a variável aleatória e, em seguida, descobrir probabilidades de nossos números aleatórios simulados. Se quisermos saber a probabilidade de que X seja menor que 10, contamos o proporção de variáveis ​​aleatórias simuladas resulta em menos de 10 e usa isso como nossa estimativa. Essa é a parte "Monte Carlo", é uma estimativa de probabilidade baseada em números aleatórios. Com números aleatórios simulados suficientes, a estimativa é muito boa, mas ainda é inerentemente aleatório.

"Então, por que" cadeia de Markov "? Porque, sob certas condições técnicas, você pode gerar um processo sem memória (também conhecido como Markoviano) que possui a mesma distribuição limitadora que a variável aleatória que você está tentando simular. número de tipos diferentes de processos de simulação que geram números aleatórios correlacionados (com base apenas no valor atual desses números) e você garante que, depois de reunir resultados suficientes, você terá uma pilha de números com aparência " como se "você tivesse conseguido, de alguma forma, colher amostras independentes da distribuição complicada que queria conhecer.

"Então, por exemplo, se eu quiser estimar a probabilidade de que uma variável aleatória normal normal seja menor que 0,5, eu poderia gerar dez mil realizações independentes a partir de uma distribuição normal padrão e contar o número menor que 0,5; digamos que obtive 6905 que foram menos de 0,5 de 10000 amostras no total; minha estimativa para P (Z <0,5) seria 0,6905, o que não está muito longe do valor real, seria uma estimativa de Monte Carlo.

a lista de números que recebo do procedimento será distribuída como um grande número de empates de algo que gera variáveis ​​aleatórias normais. Isso me daria uma simulação de Markov Chain Monte Carlo para uma variável aleatória normal padrão. Se eu usasse isso para estimar probabilidades, seria uma estimativa do MCMC. "

Imagine que você quer encontrar uma estratégia melhor para derrotar seus amigos no jogo de tabuleiro Monopoly. Simplifique o que importa no jogo para a pergunta: em quais propriedades as pessoas mais pousam? A resposta depende da estrutura do tabuleiro, das regras do jogo e dos arremessos de dois dados.

Uma maneira de responder à pergunta é essa. Basta seguir uma única peça ao redor do tabuleiro enquanto joga os dados e segue as regras. Conte quantas vezes você pousa em cada propriedade (ou programa um computador para fazer o trabalho por você). Eventualmente, se você tiver paciência suficiente ou tiver programado as regras suficientemente bem em seu computador, criará uma boa imagem de quais propriedades geram mais negócios. Isso deve ajudá-lo a ganhar com mais frequência.

O que você fez é uma análise de Markov Chain Monte Carlo (MCMC). O conselho define as regras. O local onde você pousa em seguida depende apenas de onde você está agora, não de onde esteve antes e as probabilidades específicas são determinadas pela distribuição dos arremessos de dois dados. O MCMC é a aplicação dessa idéia a sistemas matemáticos ou físicos, como o clima de amanhã ou onde um grão de pólen sendo aleatoriamente batido por moléculas de gás terminará.

OK, aqui está minha melhor tentativa de uma explicação informal e grosseira.

Uma cadeia de Markov é um processo aleatório que possui a propriedade de que o futuro depende apenas do estado atual do processo e não do passado, ou seja, sem memória. Um exemplo de um processo aleatório pode ser a bolsa de valores. Um exemplo de uma cadeia de Markov seria um jogo de tabuleiro como Monopoly ou Snakes and Ladders, em que sua posição futura (após rolar o dado) dependeria apenas de onde você começou antes do lançamento, e não de nenhuma das posições anteriores. Um exemplo de livro de uma cadeia de Markov é a "caminhada dos bêbados". Imagine alguém que está bêbado e pode se mover apenas para a esquerda ou direita em um ritmo. O bêbado se move para a esquerda ou direita com igual probabilidade. Esta é uma cadeia de Markov em que a posição futura / próxima do bêbado depende apenas de onde ele está atualmente.

Os métodos de Monte Carlo são algoritmos computacionais (simplesmente conjuntos de instruções) que amostram aleatoriamente de algum processo em estudo. Eles são uma maneira de estimar algo que é muito difícil ou demorado para encontrar deterministicamente. Eles são basicamente uma forma de simulação por computador de algum processo matemático ou físico. O apelido de Monte Carlo vem da analogia entre um cassino e a geração aleatória de números. Voltando ao nosso exemplo de jogo de tabuleiro anteriormente, talvez desejemos saber se algumas propriedades no tabuleiro Monopólio são visitadas com mais frequência do que outras. Um experimento em Monte Carlo envolveria rolar os dados repetidamente e contar o número de vezes que você pousaria em cada propriedade. Também pode ser usado para calcular integrais numéricas. (Muito informalmente, podemos pensar em uma integral como a área sob o gráfico de alguma função. ) A integração de Monte Carlo funciona muito bem em funções de alta dimensão, pegando uma amostra aleatória de pontos da função e calculando algum tipo de média nesses vários pontos. Ao aumentar o tamanho da amostra, a lei de grandes números nos diz que podemos aumentar a precisão de nossa aproximação cobrindo cada vez mais a função.

Esses dois conceitos podem ser reunidos para resolver alguns problemas difíceis em áreas como inferência bayesiana, biologia computacional etc. onde integrais multidimensionais precisam ser calculadas para resolver problemas comuns. A idéia é construir uma Cadeia de Markov que converja para a distribuição de probabilidade desejada após várias etapas. O estado da cadeia após um grande número de etapas é então usado como uma amostra da distribuição desejada e o processo é repetido. Existem muitos algoritmos MCMC diferentes que usam técnicas diferentes para gerar a cadeia de Markov. Os mais comuns incluem o Metropolis-Hastings e o Gibbs Sampler.

Trecho de Métodos Bayesianos para Hackers

A paisagem bayesiana

$N$$N$$p_1$$p_2$

$\text{Exp}(3)$$\text{Exp}(10)$

A visualização abaixo demonstra isso. Quanto mais vermelho escuro a cor, maior a probabilidade prévia de que as incógnitas estejam nesse local. Por outro lado, áreas com azul mais escuro representam que nossos priores atribuem uma probabilidade muito baixa aos desconhecidos que estão lá.

Estes são exemplos simples no espaço 2D, onde nossos cérebros podem entender bem as superfícies. Na prática, os espaços e superfícies gerados por nossos priores podem ter dimensões muito mais altas.

$X$$X$empurra a superfície original para formar montanhas altas . A quantidade de empurrar para cima é resistida pela probabilidade anterior, de modo que menos probabilidade anterior significa mais resistência. Assim, no duplo caso exponencial-anterior acima, uma montanha (ou várias montanhas) que pode entrar em erupção perto do canto (0,0) seria muito mais alta do que as montanhas que entrarem em erupção mais perto de (5,5), pois há mais resistência perto (5,5) A montanha, ou talvez mais geralmente, as cadeias de montanhas, refletem a probabilidade posterior de onde os verdadeiros parâmetros provavelmente serão encontrados.

$\lambda$

$\text{Uniform}(0,5)$

O ponto preto representa os parâmetros verdadeiros. Mesmo com 1 ponto de amostra, como o que foi simulado acima, as montanhas tentam conter o parâmetro true. Obviamente, a inferência com um tamanho de amostra igual a 1 é incrivelmente ingênua, e a escolha de um tamanho de amostra tão pequeno foi apenas ilustrativa.

Explorando a Paisagem Usando o MCMC

$N$$N$$N$da distribuição posterior, não da distribuição em si. Estendendo nossa analogia montanhosa ao limite, o MCMC executa uma tarefa semelhante a perguntar repetidamente "Qual a probabilidade de encontrar esta pedra da montanha que estou procurando?" E conclui sua tarefa retornando milhares de pedras aceitas na esperança de reconstruir a montanha original. No jargão MCMC e PyMC, a sequência retornada de "seixos" são as amostras, mais frequentemente chamadas de rastreios .

Quando digo MCMC inteligentemente procura, quer dizer MCMC vai espero que convergem para as áreas de alta probabilidade posterior. O MCMC faz isso explorando posições próximas e movendo-se para áreas com maior probabilidade. Novamente, talvez "convergir" não seja um termo preciso para descrever a progressão do MCMC. A convergência geralmente implica avançar em direção a um ponto no espaço, mas o MCMC se move em direção a uma área mais ampla no espaço e caminha aleatoriamente nessa área, coletando amostras dessa área.

A princípio, devolver milhares de amostras ao usuário pode parecer uma maneira ineficiente de descrever as distribuições posteriores. Eu diria que isso é extremamente eficiente. Considere as possibilidades alternativas:

1. O retorno de uma fórmula matemática para as "cadeias de montanhas" envolveria a descrição de uma superfície N-dimensional com picos e vales arbitrários.
2. Retornar o "pico" da paisagem, embora matematicamente possível e uma coisa sensata a ser feita, pois o ponto mais alto corresponde à estimativa mais provável das incógnitas, ignora a forma da paisagem, que anteriormente argumentamos ser muito importante para determinar a confiança posterior em incógnitas.

Além de razões computacionais, provavelmente a razão mais forte para o retorno de amostras é que podemos facilmente usar a Lei dos Grandes Números para resolver problemas que de outra forma seriam intratáveis. Adio essa discussão para o próximo capítulo.

Algoritmos para executar o MCMC

Há uma grande família de algoritmos que executam o MCMC. De maneira mais simples, a maioria dos algoritmos pode ser expressa em um nível alto da seguinte maneira:

1. Start at current position.
2. Propose moving to a new position (investigate a pebble near you ).
3. Accept the position based on the position's adherence to the data 
and prior distributions (ask if the pebble likely came from the mountain).
4. If you accept: Move to the new position. Return to Step 1.
5. After a large number of iterations, return the positions.

Dessa maneira, avançamos na direção geral em direção às regiões onde existem as distribuições posteriores e coletamos amostras com moderação na jornada. Quando atingimos a distribuição posterior, podemos coletar facilmente amostras, pois provavelmente todas pertencem à distribuição posterior.

Se a posição atual do algoritmo MCMC estiver em uma área de probabilidade extremamente baixa, o que geralmente ocorre quando o algoritmo inicia (normalmente em um local aleatório no espaço), o algoritmo se moverá em posições que provavelmente não são da parte posterior. mas melhor do que tudo nas proximidades. Assim, os primeiros movimentos do algoritmo não refletem o posterior.

Portanto, há muitas respostas aqui parafraseadas em livros de estatística / probabilidade, Wikipedia, etc. Acredito que temos "leigos" onde trabalho; Eu acho que eles estão no departamento de marketing. Se eu tiver que explicar algo técnico a eles, aplico a regra "show don't tell". Com essa regra em mente, eu provavelmente mostraria algo assim.

A idéia aqui é tentar codificar um algoritmo que eu possa ensinar a soletrar - não aprendendo todas as centenas (milhares?) De regras como Ao adicionar um final a uma palavra que termina com um e silencioso, solte o e final se o final começa com uma vogal . Uma razão que não funcionará é que eu não conheço essas regras (nem tenho certeza de que a que acabei de recitar está correta). Em vez disso, vou ensiná-lo a soletrar mostrando-lhe um monte de palavras escritas corretamente e deixando extrair as regras dessas palavras, que é mais ou menos a essência do aprendizado de máquina, independentemente do algoritmo - extração e reconhecimento de padrões .

O critério de sucesso está soletrando corretamente uma palavra que o algoritmo nunca viu antes (eu percebo que isso pode acontecer por puro acaso, mas isso não ocorrerá para o pessoal de marketing, então eu vou ignorar - mais eu vou ter o algoritmo tente soletrar não uma palavra, mas muitas, por isso não é provável que sejamos enganados por algumas suposições).

Há uma hora, baixei (como um arquivo de texto sem formatação) do excelente site Project Gutenberg, o romance de Herman Hesse, Siddhartha . Usarei as palavras deste romance para ensinar ao algoritmo como soletrar.

Então, codifiquei o algoritmo abaixo que digitalizou este romance, três letras de cada vez (cada palavra tem um caractere adicional no final, que é 'espaço em branco' ou o fim da palavra). Seqüências de três letras podem lhe dizer muito - por exemplo, a letra 'q' é quase sempre seguida por 'u'; a sequência 'ty' geralmente ocorre no final de uma palavra; z raramente acontece e assim por diante. (Nota: eu poderia facilmente ter alimentado palavras inteiras para treiná-lo para falar em frases completas - exatamente a mesma idéia, apenas alguns ajustes no código.)

Porém, nada disso envolve o MCMC, o que ocorre após o treinamento, quando damos ao algoritmo algumas letras aleatórias (como uma semente) e ele começa a formar 'palavras'. Como o algoritmo constrói palavras? Imagine que ele tem o bloco 'qua'; que letra ele adiciona a seguir? Durante o treinamento, o algoritmo construiu uma enorme matriz de frequência l-éter-sequência * a partir de todas as milhares de palavras do romance. Em algum lugar nessa matriz está o bloco de três letras 'qua' e as frequências dos caracteres que podem seguir a sequência. O algoritmo seleciona uma letra com base nas frequências que poderiam segui-la. Portanto, a letra que o algoritmo seleciona a seguir depende - e apenas dos - os três últimos em sua fila de construção de palavras.

Então esse é um algoritmo de Markov Chain Monte Carlo.

Acho que talvez a melhor maneira de ilustrar como funciona seja mostrar os resultados com base em diferentes níveis de treinamento. O nível de treinamento varia de acordo com a alteração do número de passes que o algoritmo faz no romance - quanto mais passes, maior a fidelidade de suas matrizes de frequência de sequência de letras. Abaixo estão os resultados - na forma de seqüências de 100 caracteres emitidos pelo algoritmo - após o treinamento no romance 'Siddharta'.

Uma única passagem pelo romance, Sidarta :

então whoicks ger wiff todos os motivos estão em você lívido theartim sullintionexpraid seu sible dele

(Imediatamente, aprendemos a falar o galês quase perfeito; eu não esperava isso.)

Depois de duas passagens pelo romance:

o show ack wor prenskinith foi um par de pessoas que notaram que a terra estava cheia

Após 10 passes:

apesar, mas o deve orar com ack agora tem água seu cão alavanca dor pés cada um não a memória fraca

E aqui está o código (em Python, estou quase certo de que isso poderia ser feito no R usando um pacote MCMC, dos quais existem vários, em apenas 3-4 linhas)

def create_words_string(raw_string) :
  """ in case I wanted to use training data in sentence/paragraph form; 
      this function will parse a raw text string into a nice list of words;
      filtering: keep only words having  more than 3 letters and remove 
      punctuation, etc.
  """
  pattern = r'\b[A-Za-z]{3,}\b'
  pat_obj = re.compile(pattern)
  words = [ word.lower() for word in pat_obj.findall(raw_string) ]
  pattern = r'\b[vixlm]+\b'
  pat_obj = re.compile(pattern)
  return " ".join([ word for word in words if not pat_obj.search(word) ])

def create_markov_dict(words_string):
  # initialize variables
  wb1, wb2, wb3 = " ", " ", " "
  l1, l2, l3 = wb1, wb2, wb3
  dx = {}
  for ch in words_string :
    dx.setdefault( (l1, l2, l3), [] ).append(ch)
    l1, l2, l3 = l2, l3, ch
  return dx

def generate_newtext(markov_dict) :
  simulated_text = ""
  l1, l2, l3 = " ", " ", " "
  for c in range(100) :
    next_letter = sample( markov_dict[(l1, l2, l3)], 1)[0]
    simulated_text += next_letter
    l1, l2, l3 = l2, l3, next_letter
  return simulated_text

if __name__=="__main__" :
  # n = number of passes through the training text
  n = 1
  q1 = create_words_string(n * raw_str)
  q2 = create_markov_dict(q1)
  q3 = generate_newtext(q2)
  print(q3)

O MCMC é normalmente usado como uma alternativa às técnicas brutas de simulação de Monte Carlo. Tanto o MCMC quanto outras técnicas de Monte Carlo são usadas para avaliar integrais difíceis, mas o MCMC pode ser usado de maneira mais geral.

Por exemplo, um problema comum em estatística é calcular o resultado médio relacionado a algum modelo probabilístico / estocástico. As técnicas de MCMC e Monte Carlo resolveriam esse problema gerando uma sequência de resultados simulados que poderíamos usar para estimar a média real.

Tanto o MCMC quanto as técnicas brutas de Monte Carlo funcionam como a proporção de longo prazo de simulações iguais a um determinado resultado será igual * à probabilidade modelada desse resultado. Portanto, gerando simulações suficientes, os resultados produzidos pelos dois métodos serão precisos.

Eu digo igual, embora em geral eu deva falar sobre conjuntos mensuráveis. Um leigo, no entanto, provavelmente não estaria interessado nisso *

No entanto, enquanto Monte Carlo bruto envolve a produção de muitas simulações independentes, cada uma das quais é distribuída de acordo com a distribuição modelada, o MCMC envolve a geração de um passeio aleatório que, a longo prazo, "visita" cada resultado com a frequência desejada.

O truque para o MCMC, portanto, é escolher um passeio aleatório que "visite" cada resultado com as frequências de longo prazo desejadas.

Um exemplo simples pode ser simular a partir de um modelo que diz que a probabilidade do resultado "A" é 0,5 e do resultado "B" é 0,5. Nesse caso, se eu iniciasse o passeio aleatório na posição "A" e prescrevesse que em cada etapa ele alternasse para a outra posição com probabilidade 0,2 (ou qualquer outra probabilidade maior que 0), eu poderia ter certeza de que, após uma grande número de etapas que o passeio aleatório teria visitado cada um de "A" e "B" em aproximadamente 50% das etapas - consistente com as probabilidades prescritas pelo nosso modelo.

Este é obviamente um exemplo muito chato. No entanto, verifica-se que o MCMC é frequentemente aplicável em situações em que é difícil aplicar Monte Carlo padrão ou outras técnicas.

Você pode encontrar um artigo que aborda os conceitos básicos do que é e por que funciona aqui:

http://wellredd.uk/basics-markov-chain-monte-carlo/

Sou um analista de DNA que usa um software de genotipagem probabilística totalmente contínuo para interpretar evidências de DNA e tenho que explicar como isso funciona para um júri. É certo que simplificamos demais e percebo que parte disso simplifica a precisão de detalhes específicos em nome da melhoria do entendimento geral. Mas, no contexto de um júri que entende como esse processo é usado na interpretação do DNA sem graus acadêmicos e anos de experiência profissional, eles entendem a essência :)

Antecedentes: O software usa a metrópole Hastings MCMC e um modelo biológico que imita o comportamento conhecido dos perfis de DNA (o modelo é construído com base nos dados de validação gerados pelo laboratório, analisando muitos perfis de DNA de condições conhecidas que representam o intervalo encontrado na investigação desconhecida). Existem 8 cadeias independentes e avaliamos a convergência para determinar se é necessário executar novamente o aumento da gravação e a aceitação de postagens (a gravação padrão 100k aceita e a aceitação 400k aceita)

Quando perguntado pela promotoria / defesa sobre o MCMC: explicamos que significa cadeia de markov Monte Carlo e representa uma classe / tipo de algoritmo especial usado para solução de problemas complexos e que um algoritmo é apenas uma palavra sofisticada referente a uma série de procedimentos ou rotinas. realizado por um computador ... os algoritmos mcmc operam propondo uma solução, simulando essa solução e avaliando até que ponto essa simulação reflete os dados reais das evidências observadas ... uma simulação que se encaixa bem na observação de evidências tem uma probabilidade mais alta do que uma simulação que não se encaixa bem na observação ... ao longo de muitas amostragens / suposições repetidas das soluções propostas, as cadeias de Markov se afastam das soluções de baixa probabilidade para as soluções de alta probabilidade que melhor se ajustam / explicam o perfil de evidência observado, até que, eventualmente, o equilíbrio seja alcançado. alcançado,o que significa que o algoritmo tem capacidade limitada de amostrar novas propostas, gerando probabilidades significativamente maiores

Quando perguntados sobre a metrópole Hastings: explicamos que é um refinamento do algoritmo do MCMC que descreve seu processo de tomada de decisão aceitando ou rejeitando uma proposta ... geralmente isso é explicado com uma analogia do jogo infantil "quente / frio", mas eu posso ter considerado o uso " deslize para a direita ou para a esquerda "quando o júri for especialmente jovem !! : p Mas, usando nossa analogia quente / frio, sempre aceitamos um palpite quente e, ocasionalmente, aceitamos um palpite frio uma fração do tempo e explicamos o propósito de algumas vezes aceitar o palpite frio é garantir que as cadeias obtenham uma gama mais ampla de possibilidades, em vez de ficar preso em torno de uma proposta em particular antes do equilíbrio real

Editado para acrescentar / esclarecer: com a analogia quente / fria, explicamos que, no jogo infantil, o líder escolhe um objeto / área-alvo dentro da sala e os jogadores se revezam tentando adivinhar qual direção mover em relação à sua posição / posição atual. O líder diz para eles mudarem de posição / fazerem a jogada se for um palpite quente e eles perderem a vez / permanecerem na posição se for um palpite frio. Da mesma forma, dentro do nosso software, a decisão de mover / aceitar depende apenas da probabilidade da proposta em comparação com a probabilidade da posição atualmente ocupada ... Entretanto, o objetivo é predefinido / conhecido pelo líder no jogo infantil, enquanto o O alvo no nosso software não é predefinido - é completamente desconhecido (também por que '

Como eu disse, super super básico e absolutamente sem detalhes técnicos para melhorar a compreensão - nós nos esforçamos para explicar sobre o nível de ensino médio. Sinta-se livre para fazer sugestões. Vou incorporá-los.

Essa pergunta é ampla, mas as respostas são muitas vezes bastante casuais. Como alternativa, você pode ver este artigo que fornece uma descrição matemática concisa de uma ampla classe de algoritmos MCMC, incluindo os algoritmos Metropolis-Hastings, amostragem Gibbs, Metropolis-dentro-Gibbs e métodos de variáveis ​​auxiliares, amostragem por fatia, propostas recursivas, amostragem direcional, Langevin e Monte Carlo Hamiltoniano, amostragem NUTS, algoritmos pseudo-marginais de Metropolis-Hastings e Monte Carlo Hamiltoniano pseudo-marginal, conforme discutido pelos autores.

Uma revisão confiável é dada aqui

Encontrarei mais tempo para elaborar seu conteúdo no formato de stackexchange.

$f(x,y)=z=x^2+2*x*y$$(x,y)$$f(x,y)$$f(x,y)$

$f(x,y,z,t,s,...,zzz)$

Este vídeo (a partir das 5:50) tem uma muito boa declaração de intuição.

Imagine que você queira provar pontos que estão nos galhos verdes (multidimensionais) desta figura. Se você jogar pontos por todo o superespaço preto e verificar seu valor, estará desperdiçando muita energia de amostragem (pesquisa). Portanto, faria mais sentido controlar sua estratégia de amostragem (que pode ser automatizada) para selecionar pontos mais próximos dos ramos verdes (onde é importante). Os galhos verdes podem ser encontrados ao serem atingidos acidentalmente (ou controlados), e o restante do esforço de amostragem (pontos vermelhos) será gerado posteriormente. A razão pela qual o vermelho é atraído para a linha verde é por causa da matriz de transição em cadeia de Markov, que funciona como seu mecanismo de amostragem.

Portanto, em termos leigos, o MCMC é um método de amostragem de baixo custo, especialmente quando se trabalha em um espaço maciço e "escuro" (multidimensional).