Vous avez peut-être entendu le terme "chaîne de Markov" avant, mais à moins que vous ayez suivi quelques cours sur la théorie des probabilités ou les algorithmes informatiques. Comment apprendre sans tout stress Comment apprendre sans tout le stress Peut-être avez-vous décidé de poursuivre la programmation, que ce soit pour une carrière ou tout simplement comme un passe-temps. Génial! Mais peut-être que vous commencez à vous sentir dépassé. Pas si bien. Voici de l'aide pour faciliter votre voyage. En savoir plus, vous ne savez probablement pas ce qu'ils sont, comment ils fonctionnent et pourquoi ils sont si importants.
La notion de chaîne de Markov est un concept «sous le capot», ce qui signifie que vous n'avez pas vraiment besoin de savoir ce qu'ils sont pour en tirer profit. Cependant, vous pouvez certainement bénéficier de comprendre comment ils fonctionnent. Ils sont simples mais utiles à bien des égards.
Voici donc un cours intensif: tout ce que vous devez savoir sur les chaînes de Markov condensées en un seul article digeste. Si vous voulez plonger encore plus profond, essayez le cours de théorie de l'information gratuit sur Khan Academy (et envisager d'autres sites de cours en ligne trop 8 sites Web Awesome pour suivre des cours gratuits en ligne).
Chaînes de Markov 101
Disons que vous voulez prédire quel sera le temps demain. Une véritable prédiction - le genre effectué par les météorologues experts 7 Best Best Weather Apps pour Android 7 Meilleures applications météo gratuites pour Android Lire la suite - impliquerait des centaines, voire des milliers, de différentes variables qui changent constamment. Les systèmes météorologiques sont incroyablement complexes et impossibles à modéliser, du moins pour les profanes comme vous et moi. Mais nous pouvons simplifier le problème en utilisant des estimations de probabilité.
Imaginez que vous avez accès à trente années de données météorologiques. Vous commencez au début, en notant que le premier jour était ensoleillé. Vous continuez, notant que le jour 2 était aussi ensoleillé, mais le jour 3 était nuageux, puis le jour 4 était pluvieux, ce qui a conduit à un orage le jour 5, suivi par un ciel ensoleillé et clair le jour 6.
Idéalement, vous seriez plus granuleux, optant pour une analyse heure par heure au lieu d'une analyse au jour le jour, mais ce n'est qu'un exemple pour illustrer le concept, alors supportez-moi!
Vous faites cela sur l'ensemble des données sur 30 ans (ce qui serait juste un peu moins de 11 000 jours) et calculez les probabilités de la météo de demain en fonction de la météo d'aujourd'hui. Par exemple, si aujourd'hui est ensoleillé, alors:
- Une chance de 50 pour cent que demain sera à nouveau ensoleillé.
- Une chance de 30% que demain sera nuageux.
- Une chance de 20% que demain sera pluvieux.
Maintenant répétez ceci pour toutes les conditions météorologiques possibles. Si aujourd'hui le ciel est nuageux, quelles sont les chances que demain soit ensoleillé, pluvieux, brumeux, orages, grêle, tornades, etc? Très bientôt, vous avez tout un système de probabilités que vous pouvez utiliser pour prédire non seulement la météo de demain, mais aussi la météo du lendemain et le jour suivant.
États de transition
C'est l'essence d'une chaîne de Markov. Vous avez des états individuels (dans ce cas, les conditions météorologiques) où chaque état peut passer à d'autres états (par exemple, les jours ensoleillés peuvent passer à des jours nuageux) et ces transitions sont basées sur des probabilités. Si vous voulez prédire la météo en une semaine, vous pouvez explorer les différentes probabilités au cours des sept prochains jours et voir lesquelles sont les plus probables. Ainsi, une "chaîne" de Markov.
Qui est Markov? Il était un mathématicien russe qui a eu l'idée d'un état menant directement à un autre état basé sur une certaine probabilité, où aucun autre facteur n'influence le hasard de la transition. Fondamentalement, il a inventé la chaîne de Markov, d'où le nom.
Comment les chaînes de Markov sont utilisées dans le monde réel
Avec l'explication à l'écart, explorons quelques-unes des applications du monde réel où elles sont utiles. Vous pourriez être surpris de constater que vous avez utilisé des chaînes de Markov tout le temps sans le savoir!
Génération de nom
Avez-vous déjà participé à des jeux sur table, des jeux MMORPG ou même de la fiction? Vous pouvez avoir agonisé sur la dénomination de vos personnages (au moins à un moment ou un autre) - et quand vous ne pouvez pas sembler penser à un nom que vous aimez, vous avez probablement recours à un générateur de noms en ligne Créer un nouvel alias avec Meilleurs générateurs de noms en ligne [Weird & Wonderful Web] Créer un nouvel alias avec les meilleurs générateurs de noms en ligne [Weird & Wonderful Web] Votre nom est ennuyeux. Heureusement, vous pouvez aller en ligne et choisir un nouvel alias en utilisant l'un des innombrables générateurs de noms disponibles sur Internet. Lire la suite .
Vous êtes-vous déjà demandé comment fonctionnaient ces générateurs de noms? Comme il se trouve, beaucoup d'entre eux utilisent des chaînes de Markov, ce qui en fait l'une des solutions les plus utilisées. (Il y a d'autres algorithmes qui sont tout aussi efficaces, bien sûr!)
Tout ce dont vous avez besoin est une collection de lettres où chaque lettre a une liste de lettres de suivi potentielles avec des probabilités. Ainsi, par exemple, la lettre «M» a 60% de chance de conduire à la lettre «A» et 40% de chance de conduire à la lettre «I». Faites-le pour tout un tas d'autres lettres, puis exécutez l'algorithme. Boom, vous avez un nom qui a du sens! (La plupart du temps, de toute façon.)
Google PageRank
Une des implications intéressantes de la théorie des chaînes de Markov est que lorsque la longueur de la chaîne augmente (le nombre de transitions d'états augmente), la probabilité que vous atterrissiez sur un certain état converge vers un nombre fixe, et cette probabilité est indépendante vous commencez dans le système.
Ceci est extrêmement intéressant lorsque vous considérez tout le web comme un système de Markov où chaque page est un état et les liens entre les pages sont des transitions avec des probabilités. Ce théorème dit essentiellement que peu importe la page Web sur laquelle vous commencez, votre chance d'atterrir sur une certaine page Web X est une probabilité fixe, en supposant un «long temps» de surfer .
Et c'est la base de la façon dont Google classe les pages Web. En effet, l'algorithme PageRank est une forme modifiée (lire: plus avancée) de l'algorithme de la chaîne de Markov.
Plus la "probabilité fixe" d'arriver à une certaine page est élevée, plus son PageRank est élevé. C'est parce qu'une probabilité fixe plus élevée implique que la page Web a beaucoup de liens entrants d'autres pages Web - et Google suppose que si une page Web a beaucoup de liens entrants, alors elle doit être valable. Plus il y a de liens entrants, plus c'est précieux.
C'est plus compliqué que cela, bien sûr, mais c'est logique. Pourquoi un site comme About.com est-il prioritaire sur les pages de résultats de recherche? Parce qu'il s'avère que les utilisateurs ont tendance à y arriver lorsqu'ils naviguent sur le Web. Intéressant, n'est-ce pas?
Typing Word Prédiction
Les téléphones mobiles ont eu un typage prédictif depuis des décennies maintenant, mais pouvez-vous deviner comment ces prédictions sont faites? Que vous utilisiez Android (options de clavier alternatives Quel est le meilleur clavier alternatif pour Android? Quel est le meilleur clavier alternatif pour Android? Nous jetons un oeil à certains des meilleurs claviers dans le Play Store et les mettre à l'épreuve. Plus) ou iOS (options de clavier alternatives 9 claviers iOS alternatifs pour rendre votre dactylographie plus facile ou plus amusant 9 claviers iOS alternatifs pour rendre votre dactylographie plus facile ou plus amusant Quand Apple a finalement cessé d'agir comme un parent surprotecteur et introduit des claviers tiers, tout le monde clavier-fou Lire la suite), il y a de bonnes chances que votre application de choix utilise des chaînes de Markov.
C'est pourquoi les applications clavier demandent s'ils peuvent collecter des données sur vos habitudes de frappe. Par exemple, dans Google Keyboard, il existe un paramètre appelé Partager des extraits qui vous demande de "partager des extraits de ce que vous tapez et de la manière dont vous tapez dans les applications Google pour améliorer le clavier Google". En substance, vos mots sont analysés et intégrés dans les probabilités de la chaîne de Markov de l'application.
C'est aussi pourquoi les applications clavier présentent souvent trois options ou plus, généralement dans l'ordre du plus probable au moins probable. Il ne peut pas savoir avec certitude ce que vous avez l'intention de taper ensuite, mais c'est correct le plus souvent.
Subreddit Simulation
Si vous n'avez jamais utilisé Reddit, nous vous encourageons à consulter au moins cette expérience fascinante appelée / r / SubredditSimulator.
Simplement dit, Subreddit Simulator prend en compte une grande partie de tous les commentaires et titres faits dans les nombreuses communautés de Reddit, puis analyse la composition mot à mot de chaque phrase. En utilisant ces données, il génère des probabilités de mot à mot - puis utilise ces probabilités pour venir générer des titres et des commentaires à partir de zéro.
Une couche intéressante de cette expérience est que les commentaires et les titres sont catégorisés par la communauté dont proviennent les données, de sorte que les commentaires et les titres générés par l'ensemble de données de / r / food sont très différents des commentaires et titres générés par / r / jeu de données du football.
Et la partie la plus drôle - ou peut-être la plus dérangeante - de tout cela est que les commentaires et les titres générés peuvent souvent être indiscernables de ceux des personnes réelles. C'est absolument fascinant.
Connaissez-vous d'autres utilisations cool pour les chaînes de Markov? Vous avez des questions auxquelles vous devez toujours répondre? Faites-nous savoir dans un commentaire ci-dessous!