Que sont les chaînes de Markov? 5 astuces du monde réel

Vous avez peut-être entendu le terme “Chaîne de Markov” Apprendre à programmer sans stresser Comment apprendre à programmer sans stress Peut-être avez-vous décidé de poursuivre la programmation, que ce soit pour une carrière ou 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 “sous la capuche” concept, 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 la compréhension de leur fonctionnement. Ils sont simples mais utiles à bien des égards.

Alors, voici un cours intensif - tout ce que vous devez savoir sur les chaînes de Markov résumées en un seul article digeste. Si vous voulez aller encore plus loin, essayez le cours théorique d'information gratuit sur Khan Academy (et envisagez également d'autres sites de cours en ligne. 8 Sites Web impressionnants pour suivre des cours universitaires gratuits en ligne 8 Sites Web impressionnants pour suivre des cours universitaires gratuits en ligne, en savoir plus).

Chaînes de Markov 101

Disons que vous voulez prédire le temps qu'il fera demain. Une véritable prédiction - le genre réalisé par les météorologues experts Les 7 meilleures applications météo gratuites pour Android Les 7 meilleures applications météo gratuites pour Android Ces applications météo gratuites vous aideront à rester au top des conditions météorologiques avec votre appareil Android. En savoir plus - impliquerait des centaines, voire des milliers de variables différentes en constante évolution. 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 ayez accès à trente ans de données météorologiques. Vous commencez au début, en notant que le jour 1 était ensoleillé. 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 d'un ciel clair et ensoleillé le jour 6..

Dans l'idéal, vous seriez plus précis, optant pour une analyse heure par heure plutôt que pour une analyse quotidienne, mais il ne s'agit que d'un exemple pour illustrer le concept.!

Vous effectuez cette opération sur l'ensemble des données sur 30 ans (ce qui représenterait un peu moins de 11 000 jours) et calculez les probabilités de la météo de demain en fonction du temps qu'il fera. Par exemple, si le temps est ensoleillé, alors:

• 50% de chances que demain soit à nouveau ensoleillé.
• 30 pour cent de chances que demain soit nuageux.
• 20 pour cent de chances que demain soit pluvieux.

Répétez cette opération pour toutes les conditions météorologiques possibles. Si le temps est nuageux, quelles sont les chances pour que demain soit ensoleillé, pluvieux, brumeux, orages, tempêtes de grêle, tornades, etc.? Bientôt, vous avez tout un système de probabilités que vous pouvez utiliser pour prédire non seulement le temps qu'il fera demain, mais aussi le temps qu'il fera le lendemain et le lendemain..

États transitoires

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 se transformer en temps nuageux) et ces transitions sont basées sur des probabilités. Si vous voulez prédire le temps qu'il pourrait faire dans une semaine, vous pouvez explorer les différentes probabilités au cours des sept prochains jours et voir celles qui sont les plus probables. Ainsi, un Markov “chaîne”.

Qui est Markov? C'est un mathématicien russe qui a eu l'idée d'un État menant directement à un autre État en fonction d'une probabilité donnée, 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

Une fois l'explication terminée, explorons certaines des applications du monde réel où elles s'avèrent utiles. Vous pourriez être surpris de constater que vous utilisez des chaînes de Markov depuis tout ce temps sans le savoir.!

Nom Génération

Avez-vous déjà participé à des jeux sur table, à des jeux MMORPG ou même à de la fiction? Vous avez peut-être été angoissé par le nom de vos personnages (au moins à un moment ou à un autre) - et lorsque vous sembliez incapable de penser à un nom que vous aimiez, vous avez probablement eu recours à un générateur de noms en ligne Créer un nouvel alias avec le Meilleurs générateurs de noms en ligne [Weird & Wonderful Web] Créez 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 Internetz. Lire la suite .

Vous êtes-vous déjà demandé comment fonctionnaient ces générateurs de noms? Il s'avère que beaucoup d'entre eux utilisent des chaînes de Markov, ce qui en fait l'une des solutions les plus utilisées. (Il existe bien sûr d'autres algorithmes tout aussi efficaces!)

Tout ce dont vous avez besoin est une collection de lettres où chaque lettre contient une liste de lettres de suivi potentielles avec des probabilités. Ainsi, par exemple, la lettre “M” a 60 pour cent de chances d'aboutir à la lettre “UNE” et 40 pour cent de chances de mener à la lettre “je”. Faites cela 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

L’une des implications intéressantes de la théorie de la chaîne de Markov est que, à mesure que la longueur de la chaîne augmente (c’est-à-dire que le nombre de transitions d’états augmente), la probabilité que vous tombiez sur un certain état converge sur un nombre fixe, et cette probabilité est indépendante de l’endroit où vous commencez dans le système.

Ceci est extrêmement intéressant si vous considérez le Web comme un système de Markov où chaque page Web est un état et où les liens entre les pages Web sont des transitions avec des probabilités. Ce théorème dit essentiellement que quelle que soit la page Web sur laquelle vous démarrez, votre chance d’atteindre une certaine page Web X est une probabilité fixe, dans l’hypothèse “Longtemps” de surf.

Et c’est la base sur laquelle 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 le “probabilité fixe” d’atteindre une certaine page Web, plus son PageRank est élevé. En effet, une probabilité fixe plus élevée implique que la page Web contienne de nombreux liens entrants provenant d'autres pages Web - et Google suppose que, si une page Web contient de nombreux liens entrants, elle doit être utile. Plus il y a de liens entrants, plus il est précieux.

C'est plus compliqué que ça, bien sûr, mais c'est logique. Pourquoi un site comme About.com a-t-il une priorité plus élevée sur les pages de résultats de recherche? Parce qu'il s'avère que les utilisateurs ont tendance à y arriver lorsqu'ils surfent sur le Web. Intéressant, n'est-ce pas?

Prédiction de mots de frappe

La saisie prédictive est en cours sur les téléphones mobiles depuis des décennies, mais pouvez-vous deviner comment ces prédictions sont faites? Que vous utilisiez Android (options de clavier alternatif Quel est le meilleur clavier alternatif pour Android? Quel est le meilleur clavier alternatif pour Android? Nous examinons quelques-uns des meilleurs claviers du Play Store et les mettons à l'essai. Lire Plus) ou iOS (options de clavier alternatives 9 Claviers iOS alternatifs pour faciliter votre frappe ou pour vous amuser plus facilement 9 Claviers iOS alternatifs pour rendre votre frappe plus facile ou pour vous rendre plus amusant Clavier fou. Lire la suite), il y a de bonnes chances que votre application de choix utilise les chaînes de Markov.

C'est pourquoi les applications de clavier demandent si elles 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 demande à “partager des extraits de quoi et comment vous tapez dans les applications Google pour améliorer Google Keyboard”. Essentiellement, vos mots sont analysés et intégrés aux probabilités de chaîne de Markov de l'application..

C'est également pour cette raison que les applications de clavier présentent souvent trois options ou plus, généralement dans l'ordre des plus probables aux moins probables. Il ne peut pas savoir avec certitude ce que vous vouliez taper ensuite, mais c'est correct le plus souvent..

Subreddit Simulation

Si vous n'avez jamais utilisé Reddit, nous vous encourageons au moins à découvrir cette expérience fascinante appelée / r / SubredditSimulator..

En termes simples, Subreddit Simulator prend en compte une grande partie de TOUS les commentaires et les titres formulés dans les nombreuses communautés de Reddit, puis analyse la composition mot par mot de chaque phrase. En utilisant ces données, il génère des probabilités mot à mot - puis utilise ces probabilités pour générer des titres et des commentaires à partir de rien..

Une couche intéressante de cette expérience est que les commentaires et les titres sont classés par la communauté d’origine des données. Les types de commentaires et de titres générés par le jeu de données de / r / food sont donc très différents des commentaires et des titres générés par / r /. ensemble de données du football.

Et le plus drôle - ou peut-être le plus dérangeant - est que les commentaires et les titres générés sont souvent indiscernables de ceux de personnes réelles. C'est absolument fascinant.

Connaissez-vous d'autres utilisations intéressantes des chaînes de Markov? Vous avez des questions qui nécessitent encore une réponse? Faites-nous savoir dans un commentaire en bas!

En savoir plus sur: Algorithmes.