Introdução às cadeias de Markov:
Você já se perguntou como o Google classifica as páginas da web? Se você fez sua pesquisa, você deve saber que ele usa o algoritmo PageRank que é baseado na ideia de cadeias de Markov. Este artigo sobre Introdução às Cadeias de Markov ajudará você a entender a ideia básica por trás das cadeias de Markov e como elas podem ser modeladas como uma solução para problemas do mundo real.
Aqui está uma lista de tópicos que serão abordados neste blog:
- O que é uma cadeia de Markov?
- O que é a propriedade Markov?
- Compreendendo as cadeias de Markov com um exemplo
- O que é uma matriz de transição?
- Cadeia de Markov em Python
- Aplicações de cadeia de Markov
Para obter conhecimento aprofundado sobre ciência de dados e aprendizado de máquina usando Python, você pode se inscrever para por Edureka com suporte 24 horas por dia, 7 dias por semana e acesso vitalício.
O que é uma cadeia de Markov?
Andrey Markov introduziu as cadeias de Markov no ano de 1906. Ele explicou as cadeias de Markov como:
Um processo estocástico contendo variáveis aleatórias, passando de um estado para outro dependendo de certas suposições e regras probabilísticas definidas.
Estes aleatórios transição de variáveis de um para outro estado, com base em uma importante propriedade matemática chamada Propriedade de Markov.
Isso nos leva à questão:
O que é a propriedade Markov?
A propriedade de Markov de tempo discreto afirma que a probabilidade calculada de um processo aleatório transitar para o próximo estado possível depende apenas do estado e do tempo atuais e é independente da série de estados que o precedeu.
O fato de que a próxima ação / estado possível de um processo aleatório não depende da sequência de estados anteriores, renderiza as cadeias de Markov como um processo sem memória que depende exclusivamente do estado / ação atual de uma variável.
Vamos deduzir isso matematicamente:
Seja o processo aleatório, {Xm, m = 0,1,2, ⋯}.
Este processo é uma cadeia de Markov apenas se,
Cadeia de Markov - Introdução às Cadeias de Markov - Edureka
para todo m, j, i, i0, i1, ⋯ im e menos1
Para um número finito de estados, S = {0, 1, 2, ⋯, r}, isso é chamado de cadeia de Markov finita.
P (Xm + 1 = j | Xm = i) aqui representa as probabilidades de transição para a transição de um estado para o outro. Aqui, estamos assumindo que as probabilidades de transição são independentes do tempo.
O que significa que P (Xm + 1 = j | Xm = i) não depende do valor de 'm'. Portanto, podemos resumir,
Fórmula da Cadeia de Markov - Introdução às Cadeias de Markov - Edureka
Portanto, esta equação representa a cadeia de Markov.
Agora vamos entender o que exatamente são as cadeias de Markov com um exemplo.
Exemplo de cadeia de Markov
Antes de dar um exemplo, vamos definir o que é um modelo de Markov:
O que é um modelo de Markov?
Um modelo de Markov é um modelo estocástico que modela variáveis aleatórias de forma que as variáveis sigam a propriedade de Markov.
Agora vamos entender como um modelo de Markov funciona com um exemplo simples.
Conforme mencionado anteriormente, as cadeias de Markov são usadas em aplicativos de geração de texto e preenchimento automático. Para este exemplo, vamos dar uma olhada em uma frase de exemplo (aleatória) e ver como ela pode ser modelada usando cadeias de Markov.
Exemplo de cadeia de Markov - Introdução às cadeias de Markov - Edureka
A frase acima é nosso exemplo, eu sei que não faz muito sentido (não tem que fazer), é uma frase contendo palavras aleatórias, em que:
Chaves denotam as palavras únicas na frase, ou seja, 5 chaves (uma, duas, saudação, feliz, edureka)
Tokens denotam o número total de palavras, ou seja, 8 tokens.
Seguindo em frente, precisamos entender a frequência de ocorrência dessas palavras, o diagrama abaixo mostra cada palavra junto com um número que denota a frequência dessa palavra.
Chaves e frequências - Introdução às cadeias de Markov - Edureka
Portanto, a coluna da esquerda aqui denota as chaves e a coluna da direita denota as frequências.
A partir da tabela acima, podemos concluir que a chave ‘edureka’ aumenta 4x mais do que qualquer outra chave. É importante inferir essas informações porque pode nos ajudar a prever que palavra pode ocorrer em um determinado momento. Se eu tivesse que adivinhar a próxima palavra na frase de exemplo, escolheria ‘edureka’, uma vez que tem a maior probabilidade de ocorrência.
Falando sobre probabilidade, outra medida que você deve estar ciente é distribuições ponderadas.
Em nosso caso, a distribuição ponderada para 'edureka' é de 50% (4/8) porque sua frequência é 4, de um total de 8 tokens. O resto das chaves (uma, duas, saudação, feliz) todas têm 1/8 de chance de ocorrer (& asymp 13%)
Agora que temos uma compreensão da distribuição ponderada e uma ideia de como palavras específicas ocorrem com mais frequência do que outras, podemos prosseguir para a próxima parte.
Compreendendo as Cadeias de Markov - Introdução às Cadeias de Markov - Edureka
Na figura acima, adicionei duas palavras adicionais que denotam o início e o fim da frase, você entenderá por que fiz isso na seção abaixo.
Agora vamos atribuir a frequência a essas chaves também:
Chaves e frequências atualizadas - Introdução às cadeias de Markov - Edureka
Agora vamos criar um modelo de Markov. Conforme mencionado anteriormente, um modelo de Markov é usado para modelar variáveis aleatórias em um determinado estado de forma que os estados futuros dessas variáveis dependam exclusivamente de seu estado atual e não de seus estados anteriores.
Então, basicamente, em um modelo de Markov, para prever o próximo estado, devemos considerar apenas o estado atual.
No diagrama abaixo, você pode ver como cada token em nossa frase leva a outro. Isso mostra que o estado futuro (próximo token) é baseado no estado atual (token presente). Portanto, esta é a regra mais básica do Modelo de Markov.
O diagrama abaixo mostra que existem pares de tokens em que cada token do par leva ao outro do mesmo par.
Pares de Cadeia de Markov - Introdução às Cadeias de Markov - Edureka
usando namespace c ++
No diagrama abaixo, criei uma representação estrutural que mostra cada chave com uma matriz dos próximos tokens possíveis com os quais ela pode ser pareada.
Uma matriz de pares de cadeia de Markov - Introdução às cadeias de Markov - Edureka
Para resumir este exemplo, considere um cenário em que você terá que formar uma frase usando a matriz de chaves e tokens que vimos no exemplo acima. Antes de percorrermos este exemplo, outro ponto importante é que precisamos especificar duas medidas iniciais:
Uma distribuição de probabilidade inicial (ou seja, o estado inicial no tempo = 0, (tecla ‘Iniciar’))
Uma probabilidade de transição de saltar de um estado para outro (neste caso, a probabilidade de transição de um token para outro)
Definimos a distribuição ponderada no próprio início, então temos as probabilidades e o estado inicial, agora vamos continuar com o exemplo.
Então, para começar, o token inicial é [Start]
Em seguida, temos apenas um token possível, ou seja, [um]
Atualmente, a frase tem apenas uma palavra, ou seja, 'uma'
A partir desse token, o próximo token possível é [edureka]
A frase é atualizada para ‘um edureka’
De [edureka], podemos passar para qualquer um dos seguintes tokens [dois, saudação, feliz, fim]
Há 25% de chance de que 'dois' sejam escolhidos, o que possivelmente resultaria na formação da frase original (um edureka dois edureka hail edureka edureka feliz). No entanto, se ‘fim’ for escolhido, o processo será interrompido e acabaremos gerando uma nova frase, ou seja, ‘uma edureka’.
Dê a si mesmo um tapinha nas costas porque você acabou de construir um modelo de Markov e executou um caso de teste por meio dele. Para resumir o exemplo acima, basicamente usamos o estado presente (palavra presente) para determinar o próximo estado (palavra seguinte). E isso é exatamente o que é um processo de Markov.
É um processo estocástico em que variáveis aleatórias passam de um estado para o outro de tal forma que o estado futuro de uma variável depende apenas do estado presente.
Vamos passar para a próxima etapa e desenhar o Modelo de Markov para este exemplo.
Diagrama de transição de estado - Introdução às cadeias de Markov - Edureka
A figura acima é conhecida como Diagrama de Transição de Estado. Falaremos mais sobre isso na seção abaixo, por enquanto, basta lembrar que este diagrama mostra as transições e a probabilidade de um estado para outro.
Observe que cada oval na figura representa uma chave e as setas são direcionadas para as possíveis chaves que podem segui-la. Além disso, os pesos nas setas denotam o probabilidade ou a distribuição ponderada de transição de / para os respectivos estados.
Então, era tudo sobre como o modelo de Markov funciona. Agora, vamos tentar entender algumas terminologias importantes do Processo de Markov.
O que é uma matriz de probabilidade de transição?
Na seção acima, discutimos o funcionamento de um Modelo de Markov com um exemplo simples, agora vamos entender as terminologias matemáticas em um Processo de Markov.
Em um Processo de Markov, usamos uma matriz para representar as probabilidades de transição de um estado para outro. Essa matriz é chamada de transição ou matriz de probabilidade. Geralmente é denotado por P.
Matriz de transição - Introdução às cadeias de Markov - Edureka
Observe, pij & ge0, e ‘i’ para todos os valores é,
Fórmula da matriz de transição - Introdução às cadeias de Markov - Edureka
Deixe-me explicar isso. Supondo que nosso estado atual seja 'i', o próximo ou futuro estado tem que ser um dos estados potenciais. Portanto, enquanto fazemos a soma de todos os valores de k, devemos obter um.
O que é um diagrama de transição de estado?
Um modelo de Markov é representado por um diagrama de transição de estado. O diagrama mostra as transições entre os diferentes estados em uma Cadeia de Markov. Vamos entender a matriz de transição e a matriz de transição de estado com um exemplo.
Exemplo de matriz de transição
Considere uma cadeia de Markov com três estados 1, 2 e 3 e as seguintes probabilidades:
Exemplo de matriz de transição - Introdução às cadeias de Markov - Edureka
Exemplo de diagrama de transição de estado - Introdução às cadeias de Markov - Edureka
O diagrama acima representa o diagrama de transição de estado para a cadeia de Markov. Aqui, 1,2 e 3 são os três estados possíveis, e as setas apontando de um estado para o outro representam as probabilidades de transição pij. Quando, pij = 0, significa que não há transição entre o estado ‘i’ e o estado ‘j’.
Agora que nós conheça a matemática e a lógica por trás das cadeias de Markov, vamos fazer uma demonstração simples e entender onde as cadeias de Markov podem ser usadas.
Cadeia de Markov em Python
Para executar esta demonstração, estarei usando Python, então, se você não conhece Python, pode consultar estes blogs:
Agora vamos começar com a codificação!
Gerador de texto em cadeia de Markov
Declaração do problema: Aplicar a propriedade de Markov e criar um modelo de Markov que possa gerar simulações de texto estudando o conjunto de dados de fala de Donald Trump.
Descrição do conjunto de dados: O arquivo de texto contém uma lista de discursos proferidos por Donald Trump em 2016.
Lógica: Aplique a propriedade de Markov para gerar o discurso de Donald's Trump, considerando cada palavra usada no discurso e, para cada palavra, crie um dicionário de palavras que serão usadas a seguir.
Etapa 1: importar os pacotes necessários
importar numpy como np
Etapa 2: leia o conjunto de dados
trump = open ('C: //Users//NeelTemp//Desktop//demos//speeches.txt', encoding = 'utf8'). read () #display the data print (trump) SPEECH 1 ... Obrigado muito você. Isso é tão legal. Ele não é um cara ótimo. Ele não consegue uma imprensa justa, ele não consegue. Isso não é justo. E eu tenho que dizer que estou aqui, e muito fortemente aqui, porque eu tenho grande respeito por Steve King e também tenho grande respeito pelo Citizens United, David e todos, e tremenda ressecção pelo Tea Party. Além disso, também o povo de Iowa. Eles têm algo em comum. Pessoas que trabalham duro....Etapa 3: divida o conjunto de dados em palavras individuais
corpus = trump.split () #Exibir o corpus print (corpus) 'poderoso,', 'mas', 'não', 'poderoso', 'como', 'nós.', 'Irã', 'tem', ' semeado ',' terror ', ...
Em seguida, crie uma função que gere os diferentes pares de palavras nos discursos. Para economizar espaço, usaremos um objeto gerador.
Etapa 4: criando pares para as chaves e as palavras de acompanhamento
def make_pairs (corpus): para i no intervalo (len (corpus) - 1): yield (corpus [i], corpus [i + 1]) pares = make_pairs (corpus)
A seguir, vamos inicializar um dicionário vazio para armazenar os pares de palavras.
Caso a primeira palavra do par já seja uma chave no dicionário, basta acrescentar a próxima palavra potencial à lista de palavras que seguem a palavra. Mas se a palavra não for uma chave, crie uma nova entrada no dicionário e atribua a chave igual à primeira palavra do par.
Etapa 5: anexar o dicionário
word_dict = {} para word_1, word_2 em pares: if word_1 in word_dict.keys (): word_dict [word_1] .append (word_2) else: word_dict [word_1] = [word_2]Em seguida, escolhemos aleatoriamente uma palavra do corpus, que iniciará a cadeia de Markov.
Etapa 6: construir o modelo de Markov
# escolha aleatoriamente a primeira palavra first_word = np.random.choice (corpus) #Escolha a primeira palavra como uma palavra em maiúscula para que a palavra escolhida não seja retirada do meio de uma frase enquanto first_word.islower (): #Iniciar a cadeia de a cadeia de palavras escolhidas = [first_word] #Inicialize o número de palavras estimuladas n_words = 20
Após a primeira palavra, cada palavra na cadeia é amostrada aleatoriamente a partir da lista de palavras que seguiram aquela palavra específica nos discursos ao vivo de Trump. Isso é mostrado no snippet de código abaixo:
para i no intervalo (n_words): chain.append (np.random.choice (word_dict [chain [-1]]))
Etapa 7: previsões
Finalmente, vamos exibir o texto estimulado.
#Join retorna a cadeia como uma string print ('' .join (cadeia)) O número de pessoas incríveis. E Hillary Clinton tem nosso pessoal e um ótimo trabalho. E não vamos derrotar ObamaPortanto, este é o texto gerado que obtive considerando o discurso de Trump. Pode não fazer muito sentido, mas é bom o suficiente para fazer você entender como as cadeias de Markov podem ser usadas para gerar textos automaticamente.
Agora vamos dar uma olhada em mais alguns aplicativos de cadeias de Markov e como elas são usadas para resolver problemas do mundo real.
Aplicações de cadeia de Markov
Aqui está uma lista de aplicativos do mundo real das cadeias de Markov:
Google PageRank: A web inteira pode ser pensada como um modelo de Markov, onde cada página da web pode ser um estado e os links ou referências entre essas páginas podem ser pensados como transições com probabilidades. Então, basicamente, independentemente da página da web em que você comece a navegar, a chance de chegar a uma determinada página da web, digamos, X é uma probabilidade fixa.
Previsão de palavras de digitação: Cadeias de Markov são conhecidas por serem usadas para prever palavras futuras. Eles também podem ser usados para preenchimento automático e sugestões.
Simulação de Subreddit: Certamente você encontrou o Reddit e teve uma interação em um de seus tópicos ou subreddits. O Reddit usa um simulador de subreddit que consome uma grande quantidade de dados contendo todos os comentários e discussões realizadas em seus grupos. Fazendo uso de cadeias de Markov, o simulador produz probabilidades palavra a palavra, para criar comentários e tópicos.
Gerador de texto: As cadeias de Markov são mais comumente usadas para gerar textos fictícios ou produzir grandes ensaios e compilar discursos. Ele também é usado nos geradores de nome que você vê na web.
Agora que você sabe como resolver um problema do mundo real usando cadeias de Markov, tenho certeza que está curioso para saber mais. Aqui está uma lista de blogs que o ajudarão a começar com outros conceitos estatísticos:
Com isso, chegamos ao final deste blog de introdução às cadeias de Markov. Se você tiver alguma dúvida sobre este tópico, deixe um comentário abaixo e entraremos em contato com você.
Fique ligado para mais blogs sobre as tecnologias de tendência.
Se você está procurando um treinamento estruturado online em Data Science, edureka! tem uma curadoria especial programa que ajuda você a ganhar experiência em estatística, organização de dados, análise exploratória de dados, algoritmos de aprendizado de máquina como agrupamento de médias K, árvores de decisão, floresta aleatória, Bayes ingênuo. Você aprenderá os conceitos de Séries Temporais, Mineração de Texto e também uma introdução ao Aprendizado Profundo. Novos lotes para este curso começarão em breve !!