Quais são cadeias de markov? 5 usos mundo real bacana

Você pode ter ouvido o termo “cadeia de Markov” antes, mas a menos que você tenha tomado algumas aulas sobre teoria da probabilidade ou algoritmos de ciência da computação

, você provavelmente não sabe o que são, como funcionam, e por que eles são tão importantes.Como aprender programação sem todo o stressComo aprender programação sem todo o stressTalvez você decidiu seguir a programação, seja para uma carreira ou apenas como um hobby. Ótimo! Mas talvez você está começando a sentir-se oprimido. Não tão grande. Aqui está a ajuda para facilitar sua viagem.consulte Mais informação

A noção de uma cadeia de Markov é um “sob o capô” conceito, ou seja, você realmente não precisa saber o que eles são, a fim de se beneficiar deles. No entanto, você pode certamente beneficiar de entender como eles funcionam. Eles são simples, mas útil em muitas maneiras.

Então aqui está um curso intensivo - tudo o que você precisa saber sobre cadeias de Markov condensadas para baixo em um único artigo, digerível. Se você quiser mergulhar ainda mais fundo, tente o curso de teoria de informação livre em Khan Academy (e considerar outros sites de cursos online também).

Video: Cadeias de Markov - Introdução

Cadeias de Markov 101

Vamos dizer que você quer prever o que o tempo vai ser amanhã. Um verdadeiro previsão - o tipo realizada por meteorologistas especializados - envolveria centenas, ou mesmo milhares, de diferentes variáveis ​​que estão mudando constantemente. sistemas meteorológicos são incrivelmente complexo e impossível de modelar, pelo menos para os leigos como eu e você. Mas podemos simplificar o problema usando estimativas de probabilidade.7 Melhores Aplicativos grátis Tempo para Android7 Melhores Aplicativos grátis Tempo para Androidconsulte Mais informação

Imagine que você teve acesso a trinta anos de dados meteorológicos. Você começar no início, lembrando que dia 1 foi ensolarado. Você continuar, notando que o Dia 2 também estava ensolarado, mas dia 3 estava nublado, então Dia 4 estava chuvoso, o que levou a uma tempestade no dia 5, seguido de céu ensolarado e claras no dia 6.

Idealmente, você seria mais granular, optando por uma análise de hora em hora em vez de uma análise do dia-a-dia, mas este é apenas um exemplo para ilustrar o conceito, para ter comigo!

Video: Cadeia de Markov

Você pode fazer isso ao longo de todo o conjunto de dados de 30 anos (o que seria apenas tímido de 11.000 dias) e calcular as probabilidades de que o tempo de amanhã será como baseado em tempo de hoje. Por exemplo, se hoje está ensolarado, então:

Video: Cadeia de Markov (2º exercício resolvido)

• A chance de 50 por cento que amanhã será ensolarado novamente.
• A chance de 30 por cento que amanhã será nublado.
• A chance de 20 por cento que amanhã será chuvoso.

Agora repita isso para cada condição de tempo possível. Se hoje está nublado, quais são as chances de que amanhã será ensolarado, chuvoso, nebuloso, temporais, chuvas de granizo, tornados, etc? Muito em breve, você tem todo um sistema de probabilidades que você pode usar para prever não só o tempo de amanhã, mas o tempo do dia seguinte, e no dia seguinte.

Unidos transitórias

Esta é a essência de uma cadeia de Markov. Tem estados individuais (neste caso, as condições de tempo) em que cada estado pode transitar para outros estados (por exemplo, dias de sol pode transição para dias nublados) e essas transições são com base em probabilidades. Se você quer prever o que o tempo pode ser como em uma semana, você pode explorar as várias probabilidades ao longo dos próximos sete dias e ver quais são as mais provável. Assim, uma “cadeia” de Markov.

Quem é Markov? Ele era um matemático russo que surgiu com a idéia de um estado que leva diretamente para outro estado com base em uma certa probabilidade, onde há outros fatores influenciam a chance de transição. Basicamente, ele inventou a cadeia de Markov, daí a nomenclatura.

Como Cadeias de Markov são utilizados no mundo real

Com a explicação fora do caminho, vamos explorar algumas das aplicações do mundo real onde eles vêm a calhar. Você pode se surpreender ao descobrir que você foi fazer uso de cadeias de Markov todo esse tempo sem saber!

Video: Me Salva! O famoso Problema de Monty Hall!

nome Generation

Você já participou em jogos de mesa, jogos de MMORPG, ou mesmo escrever ficção? Você pode ter agonizado com a nomeação de seus personagens (pelo menos em um ponto ou outro) - e quando você simplesmente não conseguia pensar em um nome que você gosta, você provavelmente recorreu a um gerador de nome on-line.Criar um novo alias Com os melhores geradores Nome online [Estranho & Wonderful Web]Criar um novo alias Com os melhores geradores Nome online [Estranho & Wonderful Web]Seu nome é chato. Felizmente, você pode ir online e escolher um novo alias usando um dos inúmeros geradores de nomes disponíveis no Internetz.consulte Mais informação

Alguma vez você já se perguntou como os geradores de nomes trabalhou? Como se vê, muitos deles usam cadeias de Markov, tornando-se uma das soluções mais utilizadas. (Existem outros algoritmos lá fora, que são tão eficaz, é claro!)

Tudo que você precisa é uma coleção de cartas em que cada letra tem uma lista de potenciais letras de acompanhamento com probabilidades. Assim, por exemplo, a letra “M” tem uma chance de 60 por cento, para levar ao pé da letra “A” e uma chance de 40 por cento, para levar ao pé da letra “I”. Faça isso por um monte de outras letras, em seguida, executar o algoritmo. Boom, você tem um nome que faz sentido! (Na maioria das vezes, de qualquer maneira.)

Google PageRank

Uma das implicações interessantes da teoria da cadeia de Markov é que, como o comprimento da corrente aumenta (ou seja, o número de transições de estado aumenta), a probabilidade de que você pousar em um determinado estado converge para um número fixo, e essa probabilidade é independente de onde você começa no sistema.

Isto é extremamente interessante quando você pensa de toda a world wide web como um sistema de Markov, onde cada página é um estado e as ligações entre páginas são transições com probabilidades. Este teorema basicamente diz que não importa qual página que você começar em, sua chance de desembarque em uma determinada página da web X é uma probabilidade fixa, assumindo um “longo tempo” do surf.

E esta é a base de como o Google classifica páginas. Com efeito, o algoritmo PageRank é uma modificado (leia-se: mais avançado) forma do algoritmo cadeia de Markov.

Quanto maior a “probabilidade fixa” de chegar a uma determinada página web, maior sua PageRank. Isso ocorre porque uma maior probabilidade fixa implica que o site tem um monte de ligações recebidas de outras páginas da web - e Google assume que se uma página Web tem um monte de ligações recebidas, então deve ser valiosa. Os links mais entrada, mais valioso ele é.

É mais complicado do que isso, é claro, mas faz sentido. Por que um site como o About.com obter maior prioridade nas páginas de resultados de busca? Pois verifica-se que os usuários tendem a chegar lá como eles navegam na web. Interessante, não é?

Typing Palavra Prediction

Os telefones móveis têm tido digitação preditiva durante décadas agora, mas você pode imaginar como essas previsões são feitas? Se você está usando o Android (opções de teclado alternativos) Ou iOS (opções de teclado alternativos), Há uma boa chance de que seu aplicativo de escolha utiliza cadeias de Markov.Qual é o teclado melhor alternativa para Android?Qual é o teclado melhor alternativa para Android?Vamos dar uma olhada em alguns dos melhores teclados na Play Store e colocá-los à prova.consulte Mais informação

É por isso que aplicativos de teclado perguntar se eles podem coletar dados sobre seus hábitos de digitação. Por exemplo, no Google teclado, há uma configuração chamada trechos Partilhar que pede para “compartilhar trechos do que e como você digita em aplicativos do Google para melhorar o Google Keyboard”. Em essência, suas palavras são analisadas e incorporadas em probabilidades da cadeia de Markov do aplicativo.

Isso é também porque teclado aplicativos muitas vezes apresentam três ou mais opções, normalmente na ordem do mais provável para o menos provável. Não podemos saber com certeza o que você significou para digitar seguinte, mas ele está correto na maioria das vezes.

Simulação subreddit

Se você nunca usou o Reddit, nós encorajamos você a, pelo menos, confira esta experiência fascinante chamado / r / SubredditSimulator.

Simplificando, subreddit Simulator leva em um pedaço enorme de todos os comentários e títulos feitas através numerosas comunidades do Reddit, em seguida, analisa a composição palavra por palavra de cada frase. Usando esses dados, ele gera probabilidades palavra-a-palavra - então usa essas probabilidades de vir gerar títulos e comentários a partir do zero.

Uma camada interessante desta experiência é que os comentários e títulos são classificados pela comunidade de onde vieram os dados, para os tipos de comentários e títulos gerado pelo conjunto de dados / r / de alimentos são totalmente diferentes dos comentários e títulos gera pelo / r / dados do futebol ajustado.

E o mais engraçado - ou talvez o mais preocupante - parte de tudo isso é que os comentários e títulos gerados podem ser frequentemente indistinguíveis daqueles feitos por pessoas reais. É absolutamente fascinante.

Sabe de quaisquer outros usos legais para cadeias de Markov? Tem alguma dúvida que ainda precisam de respostas? Deixe-nos saber nos comentários abaixo!