Você pode ter ouvido o termo "cadeia Markov" antes, mas a menos que você tenha tomado algumas aulas sobre teoria da probabilidade ou algoritmos de ciência da computação Como aprender programação sem todo o estresse Como aprender programação sem todo o estresse Talvez você tenha decidido Prosseguir a programação, seja para uma carreira ou apenas como um hobby. Ótimo! Mas talvez você esteja começando a se sentir sobrecarregado. Não é tão bom. Aqui está a ajuda para facilitar sua jornada. Leia mais, você provavelmente não sabe o que são, como funcionam e por que são tão importantes.
A noção de uma cadeia de Markov é um conceito “sob o capô”, o que significa que você não precisa realmente saber o que é para se beneficiar deles. No entanto, você certamente pode se beneficiar da compreensão de como eles funcionam. Eles são simples, mas úteis de muitas maneiras.
Então aqui está um curso intensivo - tudo o que você precisa saber sobre cadeias de Markov condensadas em um único artigo digerível. Se você quiser se aprofundar ainda mais, experimente o curso gratuito de teoria da informação na Khan Academy (e considere outros sites de cursos on-line também. 8 Sites incríveis para fazer cursos universitários gratuitos on-line 8 sites incríveis para receber gratuitamente cursos universitários on-line).
Cadeias de Markov 101
Digamos que você queira prever como estará o tempo amanhã. Uma previsão verdadeira - o tipo realizado por meteorologistas especialistas em melhores aplicativos de clima livre para o Android - envolverá centenas, ou até milhares, de diferentes variáveis que estão em constante mudança. Os sistemas climáticos são incrivelmente complexos e impossíveis de modelar, pelo menos para leigos como você e eu. Mas podemos simplificar o problema usando estimativas de probabilidade.
Imagine que você tivesse acesso a trinta anos de dados meteorológicos. Você começa no começo, observando que o dia 1 estava ensolarado. Você continua, observando que o Dia 2 também estava ensolarado, mas o Dia 3 estava nublado, depois o Dia 4 estava chuvoso, o que levou a uma tempestade no Dia 5, seguido de céu ensolarado e claro no Dia 6.
O ideal seria que você fosse mais detalhista, optando por uma análise hora a hora em vez de uma análise diária, mas isso é apenas um exemplo para ilustrar o conceito, por isso, tenha paciência comigo!
Você faz isso ao longo de todo o conjunto de dados de 30 anos (que seria pouco mais de 11.000 dias) e calcula as probabilidades de como será o tempo de amanhã com base no tempo de hoje. Por exemplo, se hoje estiver ensolarado, então:
- Uma chance de 50% de que o amanhã esteja ensolarado novamente.
- Uma chance de 30 por cento de que amanhã seja nublado.
- 20% de chance de que amanhã seja chuvoso.
Agora repita isso para todas as condições climáticas possíveis. Se hoje está nublado, quais são as chances de que amanhã seja ensolarado, chuvoso, nublado, trovoadas, tempestades de granizo, tornados, etc? Muito em breve, você tem todo um sistema de probabilidades que você pode usar para prever não apenas o clima de amanhã, mas o clima do dia seguinte, e no dia seguinte.
Estados transitórios
Essa é a essência de uma cadeia de Markov. Você tem estados individuais (neste caso, condições climáticas), onde cada estado pode fazer a transição para outros estados (por exemplo, dias ensolarados podem fazer a transição para dias nublados) e essas transições são baseadas em probabilidades. Se você quiser prever como poderá estar o tempo em uma semana, poderá explorar as várias probabilidades nos próximos sete dias e ver quais são mais prováveis. Assim, uma "cadeia" de Markov.
Quem é Markov? Ele era um matemático russo que surgiu com a ideia de que um estado leva diretamente a outro estado com base em uma certa probabilidade, onde nenhum outro fator influencia o acaso transitório. Basicamente, ele inventou a cadeia de Markov, daí a nomenclatura.
Como as cadeias de Markov são usadas no mundo real
Com a explicação fora do caminho, vamos explorar algumas das aplicações do mundo real onde elas são úteis. Você pode se surpreender ao descobrir que esteve fazendo uso das cadeias de Markov todo esse tempo sem saber!
Geração de Nomes
Você já participou de jogos de mesa, jogos MMORPG ou até mesmo de ficção? Você pode ter agoniado 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 o nome Os melhores geradores de nomes on-line [Weird & Wonderful Web] Crie um novo alias com os melhores geradores de nomes on-line [Weird & 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 na Internet. Consulte Mais informação .
Você já se perguntou como esses geradores de nomes funcionavam? Acontece que muitos deles usam cadeias de Markov, tornando-se uma das soluções mais usadas. (Existem outros algoritmos lá fora que são tão eficazes, é claro!)
Tudo o que você precisa é de uma coleção de cartas em que cada letra tenha uma lista de potenciais cartas de acompanhamento com probabilidades. Assim, por exemplo, a letra “M” tem 60% de chance de levar à letra “A” e 40% de chance de levar à letra “I”. Faça isso para um monte de outras letras e, em seguida, execute 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 à medida que o comprimento da cadeia aumenta (ou seja, o número de transições de estado aumenta), a probabilidade de você pousar em um determinado estado converge em um número fixo, e essa probabilidade é independente de onde você começa no sistema.
Isso é extremamente interessante quando se pensa em toda a world wide web como um sistema Markov, em que cada página da Web é um estado e os links entre páginas da Web são transições com probabilidades. Este teorema diz basicamente que não importa em qual página da Web você começa, sua chance de aterrissar em uma determinada página da web X é uma probabilidade fixa, assumindo um “longo tempo” de navegação .
E esta é a base de como o Google classifica as páginas da web. De fato, o algoritmo PageRank é uma forma modificada (leia-se: mais avançada) do algoritmo da cadeia de Markov.
Quanto maior a "probabilidade fixa" de chegar a uma determinada página, maior será seu PageRank. Isso ocorre porque uma probabilidade fixa mais alta implica que a página da Web tenha muitos links de entrada de outras páginas da Web - e o Google pressupõe que, se uma página da Web tiver muitos links de entrada, ela deverá ser valiosa. Quanto mais links entrantes, mais valioso é.
É mais complicado que isso, claro, mas faz sentido. Por que um site como o About.com tem maior prioridade nas páginas de resultados de pesquisa? Porque acontece que os usuários tendem a chegar lá enquanto navegam na web. Interessante, não é?
Digitando Previsão de Palavras
Telefones celulares têm digitação preditiva há décadas, mas você consegue adivinhar como essas previsões são feitas? Se você está usando o Android (opções alternativas de teclado Qual é o melhor teclado alternativo para Android? Qual é o melhor teclado alternativo para Android? Vamos dar uma olhada em alguns dos melhores teclados da Play Store e colocá-los à prova. Leia Mais) ou iOS (opções alternativas de teclado 9 Teclados iOS alternativos para tornar sua digitação mais fácil ou mais divertida 9 Teclados iOS alternativos para tornar sua digitação mais fácil ou mais divertida Quando a Apple finalmente parou de agir como um pai superprotetor e introduziu teclados de terceiros, crazy-keyboard. Leia mais), há uma boa chance de que seu aplicativo de escolha usa cadeias de Markov.
É por isso que os aplicativos de teclado perguntam se podem coletar dados sobre seus hábitos de digitação. Por exemplo, no Teclado do Google, há uma configuração chamada Fragmentos de compartilhamento que pede para "compartilhar snippets do que e como você digita nos aplicativos do Google para melhorar o teclado do Google". Em essência, suas palavras são analisadas e incorporadas nas probabilidades da cadeia de Markov do aplicativo.
É também por isso que os aplicativos de teclado geralmente apresentam três ou mais opções, geralmente na ordem do mais provável ao mínimo provável. Ele não pode ter certeza do que você quis dizer em seguida, mas está correto na maioria das vezes.
Simulação de subdistrito
Se você nunca usou o Reddit, recomendamos que você, pelo menos, confira este experimento fascinante chamado / r / SubredditSimulator.
Simplificando, o Subreddit Simulator recebe uma grande quantidade de TODOS os comentários e títulos feitos nas inúmeras comunidades do Reddit, depois analisa a composição palavra por palavra de cada sentença. Usando esses dados, gera probabilidades palavra-a-palavra - então, usa essas probabilidades para gerar títulos e comentários do zero.
Uma camada interessante para este experimento é que os comentários e títulos são categorizados pela comunidade de onde vieram os dados, então os tipos de comentários e títulos gerados pelo conjunto de dados / r / food são muito diferentes dos comentários e títulos gerados por / r / conjunto de dados do futebol.
E a parte mais engraçada - ou talvez a mais perturbadora - de tudo isso é que os comentários e títulos gerados podem freqüentemente ser indistinguíveis daqueles feitos por pessoas reais. É absolutamente fascinante.
Você conhece algum outro uso legal para cadeias de Markov? Tem alguma dúvida que ainda precisa ser respondida? Deixe-nos saber em um comentário abaixo!