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

  • Harry James
  • 0
  • 3829
  • 159
Publicité

Vous avez peut-être entendu le terme “Chaîne de Markov” Avant, mais à moins que vous n'ayez suivi quelques cours sur la théorie des probabilités ou les algorithmes informatiques. Comment 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. , 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 en comprendre le 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 gratuit sur la Khan Academy (ainsi que d'autres sites de cours en ligne. Les 8 meilleurs sites pour les cours gratuits en ligne. Les 8 meilleurs sites pour les cours gratuits en ligne. Intéressé par l'accès gratuit au niveau collégial. Voici quelques-uns des meilleurs sites pour suivre des cours en ligne gratuits.).

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. - 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 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évoir 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'était un mathématicien russe qui avait eu l'idée d'un État menant directement à un autre État en fonction d'une probabilité donnée, dans laquelle aucun autre facteur n'influencait 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 donné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 Internet.. .

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 dans laquelle 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 chance de mener à la lettre “je”. Faites cela pour 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 de la chaîne de Markov est que, à mesure que la longueur de la chaîne augmente (c.-à-d. Que le nombre de transitions d'état augmente), la probabilité d'atterrir 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 lorsque 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.

Crédit d'image: 345Kai via Wikimedia

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 en provenance 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?

Taper une prédiction de mots

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 alternatives 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.) ou iOS (options de claviers alternatifs 9 Claviers alternatifs iOS pour faciliter votre frappe ou vous amuser davantage. 9 Claviers alternatifs iOS pour rendre votre frappe plus facile ou plus amusante. Quand Apple a finalement cessé d'agir en tant que parent surprotecteur et a introduit des claviers tiers, tout le monde s'est tourné au clavier. fou.), il y a de fortes 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 résumé, 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'où proviennent les données. Les types de commentaires et de titres générés par l'ensemble 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!




Personne n'a encore commenté ce post.

De la technologie moderne, simple et abordable.
Votre guide dans le monde de la technologie moderne. Apprenez à utiliser les technologies et les gadgets qui nous entourent chaque jour et à découvrir des choses intéressantes sur Internet.