Introdução às Correntes Markov

As cadeias Markov são uma forma bastante comum, e relativamente simples, de modelar estatisticamente processos aleatórios. Elas têm sido usadas em muitos domínios diferentes, desde a geração de textos até a modelagem financeira. Um exemplo popular é o r/SubredditSimulator, que usa cadeias Markov para automatizar a criação de conteúdo para todo um subreddit. Em geral, as Cadeias Markov são conceptualmente bastante intuitivas, e são muito acessíveis, pois podem ser implementadas sem o uso de quaisquer conceitos estatísticos ou matemáticos avançados. Elas são uma ótima maneira de começar a aprender sobre modelagem probabilística e técnicas de ciência de dados.

Cenário

Para começar, vou descrevê-las com um exemplo muito comum:

Imagine that there were two possible states for weather: sunny or cloudy. You can always directly observe the current weather state, and it is guaranteed to always be one of the two aforementioned states.Now, you decide you want to be able to predict what the weather will be like tomorrow. Intuitively, you assume that there is an inherent transition in this process, in that the current weather has some bearing on what the next day's weather will be. So, being the dedicated person that you are, you collect weather data over several years, and calculate that the chance of a sunny day occurring after a cloudy day is 0.25. You also note that, by extension, the chance of a cloudy day occurring after a cloudy day must be 0.75, since there are only two possible states.You can now use this distribution to predict weather for days to come, based on what the current weather state is at the time.

Este exemplo ilustra muitos dos conceitos chave de uma cadeia de Markov. Uma cadeia de Markov consiste essencialmente de um conjunto de transições, que são determinadas por alguma distribuição de probabilidade, que satisfazem a propriedade Markov.

Observe como no exemplo, a distribuição de probabilidade é obtida apenas pela observação das transições do dia corrente para o dia seguinte. Isto ilustra a propriedade Markov, a característica única dos processos de Markov que os torna sem memória. Isso normalmente os deixa incapazes de produzir com sucesso seqüências nas quais se espera que alguma tendência subjacente ocorra. Por exemplo, enquanto uma cadeia de Markov pode ser capaz de imitar o estilo de escrita de um autor baseado em freqüências de palavras, ela seria incapaz de produzir texto que contenha significado profundo ou significado temático, uma vez que estes são desenvolvidos ao longo de seqüências de texto muito mais longas. Falta-lhes, portanto, a capacidade de produzir conteúdo dependente do contexto, uma vez que não podem levar em conta toda a cadeia de estados anteriores.

>

>

O Modelo

Formalmente, uma cadeia de Markov é um autômato probabilístico. A distribuição de probabilidade de transições de estado é tipicamente representada como a matriz de transição da cadeia de Markov. Se a cadeia de Markov tem N estados possíveis, a matriz será uma matriz N x N, de modo que a entrada (I, J) é a probabilidade de transição do estado I para o estado J. Além disso, a matriz de transição deve ser uma matriz estocástica, uma matriz cujas entradas em cada linha devem somar exatamente 1. Isto faz todo o sentido, já que cada linha representa sua própria distribuição de probabilidade.

Adicionalmente, uma cadeia de Markov também tem um vector de estados iniciais, representado como uma matriz N x 1 (um vector), que descreve a distribuição de probabilidade de começar em cada um dos N estados possíveis. A entrada I do vetor descreve a probabilidade de a cadeia começar no estado I.

>

Estas duas entidades são tipicamente tudo o que é necessário para representar uma cadeia de Markov.

Agora sabemos como obter a chance de transição de um estado para outro, mas que tal encontrar a chance de essa transição ocorrer em múltiplos passos? Para formalizar isto, queremos agora determinar a probabilidade de passar do estado I para o estado J sobre os passos M. Acontece que isto é muito simples de se descobrir. Dada uma matriz de transição P, isto pode ser determinado calculando o valor de entrada (I, J) da matriz obtida elevando P para a potência de M. Para valores pequenos de M, isto pode ser feito facilmente à mão com multiplicação repetida. Entretanto, para valores grandes de M, se você estiver familiarizado com Álgebra Linear simples, uma maneira mais eficiente de elevar uma matriz para uma potência é primeiro diagonalizar a matriz.

Conclusão

Agora que você conhece os conceitos básicos das cadeias de Markov, você deve agora ser capaz de implementá-las facilmente em uma linguagem de sua escolha. Se a codificação não é o seu forte, há também muitas outras propriedades avançadas das cadeias de Markov e dos processos de Markov para você mergulhar. Na minha opinião, a progressão natural ao longo da rota teórica seria em direção aos Processos Markov Escondidos ou MCMC. Cadeias Markov simples são os blocos de construção de outras técnicas de modelagem mais sofisticadas, então com este conhecimento, você pode agora passar para várias técnicas dentro de tópicos como modelagem de crenças e amostragem.