É fácil? Eu tentei
Alexey Kuzmin, diretor de desenvolvimento de dados e trabalho da DomKlik, palestrante em ciência de dados na Netology, traduziu um artigo de Rahul Agarwal sobre como os métodos de Monte Carlo trabalham com cadeias de Markov para resolver problemas em um amplo espaço de estados.Todo mundo associado à Data Science já ouviu falar dos métodos de Monte Carlo com cadeias de Markov (MCMCs). Às vezes, o tópico é abordado ao estudar as estatísticas bayesianas, às vezes ao trabalhar com ferramentas como o Profeta.
Mas o MCMC é difícil de entender. Toda vez que li sobre esses métodos, notei que a essência do MCMC está oculta nas camadas profundas do ruído matemático, e é difícil perceber por trás desse ruído. Eu tive que passar muitas horas entendendo esse conceito.
Neste artigo, uma tentativa de explicar os métodos de Monte Carlo com cadeias de Markov está disponível, para que fique claro para que eles são usados. Vou me concentrar em mais algumas maneiras de usar esses métodos no meu próximo post.
Então, vamos começar. O MCMC consiste em dois termos: cadeias de Monte Carlo e Markov. Vamos falar sobre cada um deles.
Monte Carlo
Nos termos mais simples
, os métodos de Monte Carlo podem ser definidos como simulações simples.
Os métodos Monte Carlo receberam o nome do Monte Carlo Casino, em Mônaco. Em muitos jogos de cartas, você precisa saber a probabilidade de ganhar o dealer. Às vezes, o cálculo dessa probabilidade pode ser matematicamente complicado ou intratável. Mas sempre podemos executar uma simulação de computador para jogar o jogo inteiro muitas vezes e considerar a probabilidade como o número de vitórias dividido pelo número de jogos disputados.
É tudo o que você precisa saber sobre os métodos de Monte Carlo. Sim, é apenas uma técnica de modelagem simples com um nome sofisticado.
Cadeias de Markov
Como o termo MCMC consiste em duas partes, você ainda precisa entender o que
são as cadeias de Markov . Mas antes de passar para as cadeias de Markov, vamos falar um pouco sobre as propriedades de Markov.
Suponha que exista um sistema de M-estados possíveis e você mude de um estado para outro. Não deixe nada te confundir ainda. Um exemplo específico desse sistema é o clima, que muda de quente para frio a moderado. Outro exemplo é o mercado de ações, que está saltando de um estado de baixa para um estado de alta e estagnação.
A propriedade Markov sugere que, para um determinado processo que esteja no estado X
n em um determinado momento, a probabilidade X
n + 1 = k (onde k é qualquer um dos estados M aos quais o processo pode ir) depende apenas de qual é essa condição no momento? E não sobre como atingiu seu estado atual.
Em termos matemáticos, podemos escrever isso na forma da seguinte fórmula:
Para maior clareza, você não se importa com a sequência de condições que o mercado levou para se tornar otimista. A probabilidade de o próximo estado ser "de baixa" é determinada apenas pelo fato de o mercado estar atualmente em um estado de "alta". Também faz sentido na prática.
Um processo com uma propriedade Markov é chamado de processo Markov. Por que a cadeia de Markov é importante? Devido à sua distribuição estacionária.
O que é distribuição estacionária?
Vou tentar explicar a distribuição estacionária calculando-a para o exemplo abaixo. Suponha que você tenha um processo de Markov para o mercado de ações, como mostrado abaixo.
Você tem uma matriz de probabilidade de transição que determina a probabilidade de uma transição do estado X
i para X
j .
Matriz de Probabilidade de Transição, Q
Na matriz de probabilidade transitória Q, a probabilidade de que o próximo estado seja "bull", dado o estado atual de "bull" = 0,9; a probabilidade de que o próximo estado seja "de baixa" se o estado atual for "bull" = 0,075. E assim por diante
Bem, vamos começar com algum estado em particular. Nosso estado será definido pelo vetor [touro, urso, estagnação]. Se começarmos com um estado “de baixa”, o vetor será assim: [0,1,0]. Podemos calcular a distribuição de probabilidade para o próximo estado multiplicando o vetor de estado atual pela matriz de probabilidade de transição.
Observe que as probabilidades somam 1.A seguinte distribuição de estados pode ser encontrada pela fórmula:
E assim por diante No final, você alcançará um estado estacionário no qual o estado se estabiliza:
Para a matriz de probabilidade de transição Q descrita acima, a distribuição estacionária s é
Você pode obter uma distribuição estacionária com o seguinte código:
Q = np.matrix([[0.9,0.075,0.025],[0.15,0.8,0.05],[0.25,0.25,0.5]]) init_s = np.matrix([[0, 1 , 0]]) epsilon =1 while epsilon>10e-9: next_s = np.dot(init_s,Q) epsilon = np.sqrt(np.sum(np.square(next_s - init_s))) init_s = next_s print(init_s) ------------------------------------------------------------------ matrix([[0.62499998, 0.31250002, 0.0625 ]])
Você também pode começar de qualquer outro estado - obter a mesma distribuição estacionária. Altere o estado inicial no código se você quiser ter certeza disso.
Agora podemos responder à pergunta de por que a distribuição estacionária é tão importante.
A distribuição estacionária é importante porque pode ser usada para determinar a probabilidade de um sistema estar em um determinado estado aleatoriamente.
Para o nosso exemplo, podemos dizer que em 62,5% dos casos o mercado estará em um estado "de alta", 31,25% em um estado de "baixa" e 6,25% em estagnação.
Intuitivamente, você pode ver isso como um passeio aleatório pela cadeia.
Passeio aleatório
Você está em um determinado ponto e escolhe o próximo estado, observando a distribuição de probabilidade do próximo estado, levando em consideração o estado atual. Podemos visitar alguns nós com mais frequência do que outros, com base nas probabilidades desses nós.
Foi assim que o Google resolveu o problema de pesquisa no início da Internet. O problema era classificar as páginas, dependendo de sua importância. O Google resolveu o problema usando o algoritmo Pagerank. O algoritmo do Google Pagerank deve considerar o estado como uma página e a probabilidade de uma página em uma distribuição estacionária como sua importância relativa.
Agora nos voltamos diretamente para a consideração dos métodos MCMC.
O que são métodos de Monte Carlo com cadeias de Markov (MCMC)
Antes de responder o que é o MCMC, deixe-me fazer uma pergunta. Nós sabemos sobre a distribuição beta. Conhecemos sua função de densidade de probabilidade. Mas podemos tirar uma amostra dessa distribuição? Você pode criar uma maneira de fazer isso?
Pense ...
O MCMC permite escolher entre qualquer distribuição de probabilidade. Isso é especialmente importante quando você precisa fazer uma seleção na distribuição posterior.
A figura mostra o teorema de Bayes.
Por exemplo, você precisa fazer uma amostra de uma distribuição posterior. Mas é fácil calcular o componente posterior juntamente com a constante de normalização (evidência)? Na maioria dos casos, você pode encontrá-los na forma de um produto de probabilidade e probabilidade a priori. Mas calcular a constante de normalização (p (D)) não funciona. Porque Vamos dar uma olhada.
Suponha que H use apenas 3 valores:
p (D) = p (H = H1) .p (D | H = H1) + p (H = H2) .p (D | H = H2) + p (H = H3) .p (D | H = H3)
Nesse caso, é fácil calcular p (D). Mas e se o valor de H for contínuo? Seria possível calcular isso tão facilmente, especialmente se H assumisse valores infinitos? Para isso, uma integral complexa teria que ser resolvida.
Queremos fazer a seleção aleatória a partir da distribuição posterior, mas também queremos considerar p (D) como uma constante.
A Wikipedia
escreve :
Os métodos de Monte Carlo com cadeias de Markov são uma classe de algoritmos para amostragem de uma distribuição de probabilidade, com base na construção de uma cadeia de Markov, que como distribuição estacionária tem a forma desejada. O estado da cadeia após uma série de etapas é então usado como uma seleção da distribuição desejada. A qualidade da amostragem melhora com o aumento do número de etapas.
Vejamos um exemplo. Digamos que você precise de uma amostra da
distribuição beta . Sua densidade:
onde C é a constante de normalização. Na verdade, essa é uma função de α e β, mas quero mostrar que ela não é necessária para uma amostra da distribuição beta; portanto, a consideraremos como uma constante.
O problema de distribuição beta é realmente difícil, se não praticamente insolúvel. Na realidade, talvez você precise trabalhar com funções de distribuição mais complexas e, às vezes, não conhecerá as constantes de normalização.
Os métodos MCMC facilitam a vida, fornecendo algoritmos que poderiam criar uma cadeia de Markov com distribuição beta como distribuição estacionária, uma vez que podemos escolher uma distribuição uniforme (que é relativamente simples).
Se começarmos com um estado aleatório e passarmos para o próximo estado com base em algum algoritmo várias vezes, criaremos uma cadeia de Markov com uma distribuição beta como distribuição estacionária. E os estados em que nos encontramos há muito tempo podem ser usados como uma amostra da distribuição beta.
Um desses algoritmos MCMC é o algoritmo
Metropolis-Hastings.Algoritmo de Metropolis-Hastings
Intuição:
Então qual é o propósito?
Intuitivamente, queremos caminhar por algum pedaço de superfície (nossa cadeia de Markov) de forma que a quantidade de tempo que gastamos em cada local seja proporcional à altura da superfície naquele local (a densidade de probabilidade desejada da qual queremos fazer uma seleção).
Por exemplo, gostaríamos de gastar o dobro do tempo no topo de uma colina com 100 metros de altura do que em uma colina vizinha de 50 metros. É bom que possamos fazer isso, mesmo que não saibamos as alturas absolutas dos pontos na superfície: tudo que você precisa saber são as alturas relativas. Por exemplo, se o topo da colina A for duas vezes mais alto que o topo da colina B, gostaríamos de passar o dobro do tempo em A do que em B.
Existem esquemas mais complexos para propor novos locais e regras para sua adoção, mas a idéia principal é a seguinte:
- Escolha um novo local "sugerido".
- Descubra quanto mais alto ou mais baixo esse local é comparado ao atual.
- Permanecer no local ou mudar para um novo local com uma probabilidade proporcional à altura dos locais.
O objetivo do MCMC é selecionar entre algumas distribuições de probabilidade sem precisar saber sua altura exata a qualquer momento (não é necessário conhecer C).
Se o processo de “errância” estiver configurado corretamente, você poderá garantir que essa proporcionalidade (entre o tempo gasto e a altura da distribuição) seja alcançada .
Algoritmo:
Agora vamos definir e descrever a tarefa em termos mais formais. Seja s = (s1, s2, ..., sM) a distribuição estacionária desejada. Queremos criar uma cadeia de Markov com uma distribuição tão estacionária. Começamos com uma cadeia de Markov arbitrária com estados M com a matriz de transição P, de modo que pij representa a probabilidade de transição do estado i para j.
Intuitivamente, sabemos como percorrer a cadeia de Markov, mas a cadeia de Markov não possui a distribuição estacionária necessária. Essa cadeia tem alguma distribuição estacionária (da qual não precisamos). Nosso objetivo é mudar a maneira como passeamos pela cadeia de Markov para que a cadeia tenha a distribuição estacionária desejada.
Para fazer isso:
- Comece com um estado inicial aleatório i.
- Selecione aleatoriamente um novo estado assumido observando as probabilidades de transição na i-ésima linha da matriz de transição P.
- Calcule uma medida chamada probabilidade de decisão, que é definida como: aij = min (sj.pji / si.pij, 1).
- Agora jogue uma moeda que caia na superfície da águia com probabilidade aij. Se uma águia cair, aceite a oferta, ou seja, vá para o próximo estado, caso contrário, rejeite a oferta, ou seja, permaneça no estado atual.
- Repita várias vezes.
Após um grande número de testes, essa cadeia convergirá e terá uma distribuição estacionária s. Em seguida, podemos usar os estados da cadeia como uma amostra de qualquer distribuição.
Ao fazer isso para testar a distribuição beta, o único momento em que você precisa usar a densidade de probabilidade é procurar a probabilidade de tomar uma decisão. Para fazer isso, divida sj por si (ou seja, a constante de normalização C é cancelada).
Seleção Beta
Agora nos voltamos para o problema de amostragem da distribuição beta.
Uma distribuição beta é uma distribuição contínua em [0,1] e pode ter valores infinitos em [0,1]. Suponha que uma cadeia de Markov arbitrária P com estados infinitos em [0,1] tenha uma matriz de transição P tal que pij = pji = todos os elementos na matriz.
Não precisamos da matriz P, como veremos mais adiante, mas quero que a descrição do problema seja o mais próxima possível do algoritmo que propusemos.
- Comece com um estado inicial aleatório i obtido de uma distribuição uniforme em (0,1).
- Selecione aleatoriamente um novo estado assumido observando as probabilidades de transição na i-ésima linha da matriz de transição P. Suponha que escolha outro estado Unif (0,1) como o estado assumido j.
- Calcule a medida, que é chamada de probabilidade de tomar uma decisão:
O que simplifica para:
Como pji = pij e onde
- Agora jogue uma moeda. Com probabilidade, uma águia cairá. Se uma águia cair, você deve aceitar a oferta, ou seja, passar para o próximo estado. Caso contrário, vale a pena rejeitar a oferta, ou seja, permanecer no mesmo estado.
- Repita o teste várias vezes.
Código:
É hora de passar da teoria para a prática. Escreveremos nossa amostra beta em Python.
impo rt rand om
Compare os resultados com a distribuição beta real.
impo rt num py as np import pylab as pl import scipy.special as ss %matplotlib inline pl.rcParams['figure.figsize'] = (17.0, 4.0)
Como você pode ver, os valores são muito semelhantes à distribuição beta. Assim, a rede MCMC atingiu um estado estacionário
No código acima, criamos um amostrador beta, mas o mesmo conceito se aplica a qualquer outra distribuição a partir da qual queremos fazer uma seleção.
Conclusões
Foi um ótimo post. Parabéns se você ler até o final.
Em essência, os métodos MCMC podem ser complexos, mas fornecem uma grande flexibilidade. Você pode selecionar de qualquer função de distribuição usando a seleção através do MCMC. Normalmente, esses métodos são usados para amostrar a partir de distribuições posteriores.
Você também pode usar o MCMC para resolver problemas com um grande espaço de estado. Por exemplo, em um problema de mochila ou por descriptografia. Vou tentar fornecer exemplos mais interessantes no
próximo post. Fique atento.
Dos editores