☘️ 🧜🏻 ♦️ Uma breve introdução às cadeias de Markov 👨‍🚀 👩🏻 🧔🏽

Em 1998, Lawrence Page, Sergey Brin, Rajiv Motwani e Terry Vinograd publicaram o artigo “O Ranking de Citação PageRank: Trazendo Ordem à Web”, que descrevia o agora famoso algoritmo PageRank, que se tornou a base do Google. Depois de pouco menos de duas décadas, o Google se tornou um gigante e, embora seu algoritmo tenha evoluído fortemente, o PageRank ainda é um “símbolo” dos algoritmos de classificação do Google (embora apenas algumas pessoas possam realmente dizer quanto peso ele tem no algoritmo hoje) .

Do ponto de vista teórico, é interessante notar que uma das interpretações padrão do algoritmo PageRank é baseada em um conceito simples, mas fundamental, das cadeias de Markov. A partir do artigo, veremos que as cadeias de Markov são ferramentas poderosas para modelagem estocástica que podem ser úteis para qualquer cientista de dados. Em particular, responderemos a perguntas básicas: o que são cadeias de Markov, que boas propriedades elas possuem e o que pode ser feito com a ajuda delas?

Breve revisão

Na primeira seção, damos as definições básicas necessárias para entender as cadeias de Markov. Na segunda seção, consideramos o caso especial de cadeias de Markov em um espaço de estados finito. Na terceira seção, consideramos algumas das propriedades elementares das cadeias de Markov e ilustramos essas propriedades com muitos pequenos exemplos. Finalmente, na quarta seção, associamos as cadeias de Markov ao algoritmo PageRank e vemos com um exemplo artificial como as cadeias de Markov podem ser usadas para classificar os nós de um gráfico.

Nota A compreensão deste post requer conhecimento dos conceitos básicos de probabilidade e álgebra linear. Em particular, serão utilizados os seguintes conceitos: probabilidade condicional , vetor próprio e fórmula de probabilidade total .

O que são cadeias de Markov?

Variáveis aleatórias e processos aleatórios

Antes de introduzir o conceito de cadeias de Markov, vamos relembrar brevemente os conceitos básicos, mas importantes da teoria das probabilidades.

Primeiro, fora da linguagem da matemática, uma variável aleatória X é uma quantidade determinada pelo resultado de um fenômeno aleatório. Seu resultado pode ser um número (ou "semelhança de um número", por exemplo, vetores) ou outra coisa. Por exemplo, podemos definir uma variável aleatória como resultado de uma rolagem (número) ou como resultado de um sorteio (não um número, a menos que designemos, por exemplo, "águia" como 0, mas "caudas" como 1). Também mencionamos que o espaço de resultados possíveis de uma variável aleatória pode ser discreto ou contínuo: por exemplo, uma variável aleatória normal é contínua e uma variável aleatória de Poisson é discreta.

Além disso, podemos definir um processo aleatório (também chamado estocástico) como um conjunto de variáveis aleatórias indexadas pelo conjunto T, que frequentemente denota diferentes pontos no tempo (no que se segue, assumiremos isso). Os dois casos mais comuns: T pode ser um conjunto de números naturais (processo aleatório com tempo discreto) ou um conjunto de números reais (processo aleatório com tempo contínuo). Por exemplo, se jogarmos uma moeda todos os dias, definiremos um processo aleatório com tempo discreto, e o valor sempre variável de uma opção na bolsa definirá um processo aleatório com tempo contínuo. Variáveis aleatórias em diferentes momentos no tempo podem ser independentes umas das outras (um exemplo com um sorteio) ou ter algum tipo de dependência (um exemplo com o valor da opção); além disso, eles podem ter um espaço de estado contínuo ou discreto (o espaço de resultados possíveis a cada momento no tempo).

Diferentes tipos de processos aleatórios (discretos / contínuos no espaço / tempo).

Propriedade Markov e cadeia Markov

Existem famílias bem conhecidas de processos aleatórios: processos gaussianos, processos de Poisson, modelos auto-regressivos, modelos de média móvel, cadeias de Markov e outros. Cada um desses casos individuais tem certas propriedades que nos permitem explorar e compreendê-los melhor.

Uma das propriedades que simplifica bastante o estudo de um processo aleatório é a propriedade Markov. Se o explicarmos em uma linguagem muito informal, a propriedade Markov nos dirá que, se soubermos o valor obtido por algum processo aleatório em um determinado momento, não receberemos nenhuma informação adicional sobre o comportamento futuro do processo, coletando outras informações sobre seu passado. Em uma linguagem mais matemática: a qualquer momento, a distribuição condicional dos estados futuros de um processo com determinados estados atuais e passados depende apenas do estado atual, e não dos estados passados ( propriedade da falta de memória ). Um processo aleatório com uma propriedade Markov é chamado de processo Markov .

A propriedade Markov significa que, se conhecermos o estado atual em um determinado momento, não precisaremos de informações adicionais sobre o futuro, coletadas do passado.

Com base nessa definição, podemos formular a definição de "cadeias de Markov homogêneas com tempo discreto" (a seguir, por simplicidade, as chamaremos de "cadeias de Markov"). A cadeia de Markov é um processo de Markov com tempo discreto e um espaço de estado discreto. Portanto, uma cadeia de Markov é uma sequência discreta de estados, cada um dos quais é retirado de um espaço de estados discreto (finito ou infinito), satisfazendo a propriedade Markov.

Matematicamente, podemos denotar a cadeia de Markov da seguinte maneira:

onde, a cada momento, o processo obtém seus valores de um conjunto E discreto, de modo que

Então a propriedade Markov implica que temos

Observe novamente que essa última fórmula reflete o fato de que, para a cronologia (onde estou agora e onde estava antes), a distribuição de probabilidade do próximo estado (onde estarei o próximo) depende do estado atual, mas não dos estados anteriores.

Nota Neste post introdutório, decidimos falar apenas sobre cadeias simples de Markov homogêneas com tempo discreto. No entanto, também existem cadeias de Markov não homogêneas (dependentes do tempo) e / ou cadeias de tempo contínuo. Neste artigo, não consideraremos essas variações do modelo. Também é importante notar que a definição acima de uma propriedade de Markov é extremamente simplificada: a verdadeira definição matemática usa o conceito de filtragem, que vai muito além do conhecimento introdutório do modelo.

Caracterizamos a dinâmica da aleatoriedade de uma cadeia de Markov

Na subseção anterior, nos familiarizamos com a estrutura geral correspondente a qualquer cadeia de Markov. Vamos ver o que precisamos para definir uma "instância" específica de um processo tão aleatório.

Primeiro, observamos que a determinação completa das características de um processo aleatório com tempo discreto que não satisfaz a propriedade de Markov pode ser difícil: a distribuição de probabilidade em um determinado momento pode depender de um ou mais momentos no passado e / ou no futuro. Todas essas dependências possíveis de tempo podem potencialmente complicar a criação de uma definição de processo.

No entanto, devido à propriedade Markov, a dinâmica da cadeia de Markov é bastante simples de determinar. E de fato. precisamos determinar apenas dois aspectos: a distribuição de probabilidade inicial (ou seja, a distribuição de probabilidade no tempo n = 0), denotada por

e a matriz de probabilidade de transição (que nos dá as probabilidades de que o estado no tempo n + 1 seja o próximo para outro estado no tempo n para qualquer par de estados), indicado por

Se esses dois aspectos são conhecidos, a dinâmica completa (probabilística) do processo é claramente definida. E, de fato, a probabilidade de qualquer resultado do processo pode ser calculada ciclicamente.

Exemplo: suponha que desejamos saber a probabilidade de que os três primeiros estados do processo tenham valores (s0, s1, s2). Ou seja, queremos calcular a probabilidade

Aqui aplicamos a fórmula da probabilidade total, que afirma que a probabilidade de obter (s0, s1, s2) é igual à probabilidade de obter o primeiro s0 vezes a probabilidade de obter s1, já que anteriormente obtivemos s0 vezes a probabilidade de obter s2, levando em consideração o fato de que chegamos mais cedo na ordem s0 e s1. Matematicamente, isso pode ser escrito como

E então a simplificação é revelada, determinada pela suposição de Markov. E, de fato, no caso de cadeias longas, obtemos probabilidades fortemente condicionais para os últimos estados. No entanto, no caso das cadeias de Markov, podemos simplificar essa expressão aproveitando o fato de que

ficando assim

Como eles caracterizam completamente a dinâmica probabilística do processo, muitos eventos complexos podem ser calculados apenas com base na distribuição de probabilidade inicial q0 e na matriz de probabilidade de transição p. Também vale mencionar mais uma conexão básica: a expressão da distribuição de probabilidade no tempo n + 1, expressa em relação à distribuição de probabilidade no tempo n

Cadeias de Markov em espaços de estados finitos

Representação de matrizes e gráficos

Aqui assumimos que o conjunto E tem um número finito de estados possíveis N:

Então a distribuição de probabilidade inicial pode ser descrita como um vetor de linha q0 do tamanho N e as probabilidades de transição podem ser descritas como uma matriz p do tamanho N por N, de modo que

A vantagem dessa notação é que, se denotarmos a distribuição de probabilidade na etapa n pelo vetor de linha qn, de modo que seus componentes sejam especificados

então, relações simples de matriz são preservadas

(aqui não consideraremos a prova, mas é muito simples reproduzi-la).

Se multiplicarmos o vetor de linha à direita, que descreve a distribuição de probabilidade em um determinado estágio de tempo, pela matriz de probabilidade de transição, obteremos a distribuição de probabilidade no próximo estágio de tempo.

Portanto, como vemos, a transição da distribuição de probabilidade de um determinado estágio para o próximo é simplesmente definida como a multiplicação correta do vetor linha de probabilidades do passo inicial pela matriz p. Além disso, isso implica que temos

A dinâmica de aleatoriedade de uma cadeia de Markov em um espaço de estados finito pode ser facilmente representada como um gráfico orientado normalizado, de modo que cada nó do gráfico seja um estado, e para cada par de estados (ei, ej) existe uma aresta que vai de ei a ej se p (ei, ej )> 0. Então o valor da aresta terá a mesma probabilidade p (ei, ej).

Exemplo: um leitor do nosso site

Vamos ilustrar tudo isso com um exemplo simples. Considere o comportamento cotidiano de um visitante fictício de um site. Todos os dias ele tem três estados possíveis: o leitor não visita o site naquele dia (N), o leitor visita o site, mas não lê o post inteiro (V), e o leitor visita o site e lê um post inteiro (R). Portanto, temos o seguinte espaço de estado:

Suponha que, no primeiro dia, esse leitor tenha 50% de chance de acessar apenas o site e 50% de chance de visitar o site e ler pelo menos um artigo. O vetor que descreve a distribuição de probabilidade inicial (n = 0) fica assim:

Imagine também que as seguintes probabilidades sejam observadas:

quando o leitor não o visita um dia, há uma probabilidade de 25% de não visitá-lo no dia seguinte, uma probabilidade de 50% apenas para visitá-lo e 25% para visitá-lo e ler o artigo
quando o leitor visita o site um dia, mas não lê, ele tem 50% de chance de visitá-lo novamente no dia seguinte e não lê o artigo, e 50% de chance de visitar e ler
quando um leitor visita e lê um artigo no mesmo dia, ele tem 33% de chance de não fazer logon no dia seguinte (espero que este post não tenha esse efeito!) , 33% de chance de fazer login apenas no site e 34% de visitar e ler o artigo novamente

Então temos a seguinte matriz de transição:

Da subseção anterior, sabemos como calcular para este leitor a probabilidade de cada estado no dia seguinte (n = 1)

A dinâmica probabilística dessa cadeia de Markov pode ser representada graficamente da seguinte forma:

Apresentação em forma de gráfico da cadeia de Markov, modelando o comportamento do nosso visitante inventado no site.

Propriedades das cadeias de Markov

Nesta seção, falaremos apenas sobre algumas das propriedades ou características mais básicas das cadeias de Markov. Não entraremos em detalhes matemáticos, mas forneceremos uma breve visão geral de pontos interessantes que devem ser estudados para usar as cadeias de Markov. Como vimos, no caso de um espaço de estados finito, a cadeia de Markov pode ser representada como um gráfico. No futuro, usaremos a representação gráfica para explicar algumas propriedades. No entanto, não esqueça que essas propriedades não estão necessariamente limitadas ao caso de um espaço de estados finito.

Decomposição, periodicidade, irrevogabilidade e recuperação

Nesta subseção, vamos começar com várias maneiras clássicas de caracterizar um estado ou uma cadeia de Markov inteira.

Primeiro, mencionamos que a cadeia de Markov é indecomponível se for possível alcançar qualquer estado de qualquer outro estado (não é necessário isso em uma etapa do tempo). Se o espaço de estados é finito e a cadeia pode ser representada como um gráfico, podemos dizer que o gráfico de uma cadeia de Markov indecomponível está fortemente conectado (teoria dos grafos).

Ilustração da propriedade da indecomposição (irredutibilidade). A corrente da esquerda não pode ser reduzida: de 3 ou 4 não podemos entrar em 1 ou 2. A corrente da direita (uma extremidade é adicionada) pode ser reduzida: cada estado pode ser alcançado a partir de qualquer outro.

Um estado possui um período k se, ao sair, para qualquer retorno a esse estado, o número de etapas de tempo for um múltiplo de k (k é o maior divisor comum de todos os comprimentos possíveis de caminhos de retorno). Se k = 1, eles dizem que o estado é aperiódico, e toda a cadeia de Markov é aperiódica se todos os seus estados forem aperiódicos. No caso de uma cadeia de Markov irredutível, também podemos mencionar que, se um estado é aperiódico, todos os outros também são aperiódicos.

Ilustração da propriedade periodicidade. A corrente à esquerda é periódica com k = 2: ao sair de qualquer estado, o retorno a ele sempre exige o número de etapas múltiplo de 2. A corrente à direita tem um período de 3.

Um estado é irrevogável se, ao sair do estado, houver uma probabilidade diferente de zero de que nunca mais voltaremos a ele. Por outro lado, um estado é considerado retornável se soubermos que depois de deixar o estado, podemos retornar a ele no futuro com probabilidade 1 (se não for irrevogável).

Ilustração da propriedade de retorno / irrevogabilidade. A cadeia da esquerda tem as seguintes propriedades: 1, 2 e 3 são irrevogáveis (ao deixar esses pontos, não podemos ter certeza absoluta de que retornaremos a eles) e têm um período de 3, e 4 e 5 são retornáveis (ao deixar esses pontos, temos certeza absoluta que um dia retornaremos a eles) e teremos um período de 2. A corrente da direita tem outra nervura, tornando toda a corrente retornável e aperiódica.

Para o estado de retorno, podemos calcular o tempo médio de retorno, que é o tempo esperado de retorno ao sair do estado. Observe que mesmo a probabilidade de um retorno é 1, isso não significa que o tempo de retorno esperado seja finito. Portanto, entre todos os estados de retorno, podemos distinguir entre estados de retorno positivo (com um tempo de retorno esperado finito) e estados de retorno zero (com um tempo de retorno esperado infinito).

Distribuição estacionária, comportamento marginal e ergodicidade

Nesta subseção, consideramos propriedades que caracterizam alguns aspectos da dinâmica (aleatória) descrita pela cadeia de Markov.

A distribuição de probabilidade π no espaço de estados E é chamada de distribuição estacionária se satisfizer a expressão

Desde que nós temos

Então a distribuição estacionária satisfaz a expressão

Por definição, a distribuição estacionária de probabilidade não muda ao longo do tempo. Ou seja, se a distribuição inicial q for estacionária, será a mesma em todos os estágios subseqüentes do tempo. Se o espaço de estados for finito, então p pode ser representado como uma matriz e π como um vetor de linha, e então obtemos

Isso novamente expressa o fato de que a distribuição estacionária de probabilidade não muda com o tempo (como vemos, multiplicar a distribuição probabilística à direita por p nos permite calcular a distribuição probabilística no próximo estágio do tempo). Lembre-se de que uma cadeia de Markov indecomponível tem uma distribuição de probabilidade estacionária se e somente se um de seus estados tiver retorno positivo.

Outra propriedade interessante relacionada à distribuição de probabilidade estacionária é a seguinte. ( ) , , , : , , , . :