Quelles sont les chaînes de markov? 5 utilisations du monde réel astucieuses

Vous avez peut-être entendu le terme « chaîne de Markov » avant, mais à moins que vous avez pris quelques cours sur la théorie des probabilités ou Les algorithmes de l`informatique

, vous ne savez probablement pas ce qu`ils sont, comment ils fonctionnent, et pourquoi ils sont si importants.Comment apprendre la programmation sans tout le stressComment apprendre la programmation sans tout le stressPeut-être que vous avez 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 vous commencez à se sentir dépassés. Pas si bien. Voici une aide pour faciliter votre voyage.Lire la suite

Video: Chaine de Markov à deux états

La notion d`une chaîne de Markov est un « sous le capot » concept, qui signifie que vous ne avez pas vraiment besoin de savoir ce qu`ils sont pour en bénéficier. Cependant, vous pouvez certainement profiter de comprendre comment ils fonctionnent. Ils sont simples mais utiles à bien des égards.

Alors, voici un cours de l`accident - tout ce que vous devez savoir sur les chaînes de Markov condensés en une seule, l`article digeste. Si vous voulez plonger encore plus profond, essayez le cours de théorie de l`information gratuite sur Khan Academy (et d`envisager d`autres sites de cours en ligne aussi).

Chaînes de Markov 101

Disons que vous voulez prédire ce que le temps qu`il fera demain. Une véritable prédiction - le genre effectué par des météorologues experts - impliquerait des centaines, voire des milliers, de différentes variables qui changent constamment. Les systèmes météorologiques sont extrêmement complexes et impossibles à modéliser, au moins pour les laïcs comme vous et moi. Mais nous pouvons simplifier le problème en utilisant des estimations de probabilité.7 Meilleur gratuit Météo des applications pour Android7 Meilleur gratuit Météo des applications pour AndroidLire la suite

Imaginez que vous aviez accès à une trentaine d`années de données météorologiques. Vous commencez au début, notant que le jour 1 était ensoleillé. Vous continuez, notant que le jour 2 a également été ensoleillé, mais le jour 3 était nuageux, puis Jour 4 était pluvieux, ce qui a conduit dans un orage le jour 5, suivi par un ciel ensoleillé et clair le jour 6.

Idéalement, vous seriez plus granulaire, en optant pour une analyse heure par heure au lieu d`une analyse de jour en jour, mais cela est juste un exemple pour illustrer le concept, ainsi d`ours avec moi!

Pour ce faire, sur l`ensemble des données de 30 ans (ce qui serait un peu moins de 11.000 jours) et de calculer les probabilités de ce que le temps de demain sera basé sur la météo du jour. Par exemple, si aujourd`hui est exposé au soleil, puis:

• Une chance de 50 pour cent que demain sera à nouveau ensoleillé.
• Une chance de 30 pour cent que demain sera nuageux.
• Une chance de 20 pour cent que demain sera pluvieux.

Maintenant, répétez cela pour toutes les conditions possibles de temps. Si aujourd`hui est trouble, quelles sont les chances que demain sera ensoleillé, pluvieux, brumeux, orages, tempêtes de 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 temps demain, mais la météo du lendemain, et le lendemain.

Etats transitoires

Telle est l`essence d`une chaîne de Markov. Vous avez des états individuels (dans ce cas, les conditions météorologiques) où chaque Etat peut passer dans d`autres états (par exemple les beaux jours peut passer en temps nuageux) et les transitions sont basées sur des probabilités. Si vous voulez prédire ce que le temps est peut-être comme dans une semaine, vous pouvez explorer les diverses probabilités au cours des sept prochains jours et voir ceux qui sont les plus susceptibles. Ainsi, une Markov « chaîne ».

Qui est Markov? Il était un mathématicien russe qui est venu avec l`idée d`un Etat qui mène directement à un autre Etat fondé sur une certaine probabilité, où aucun autre facteur influent sur la chance de transition. En gros, il a inventé la chaîne de Markov, d`où la dénomination.

Comment les chaînes de Markov sont utilisés dans le monde réel

Avec l`explication de la route, nous allons explorer quelques-unes des applications du monde réel où ils sont utiles. Vous pourriez être surpris de constater que vous avez fait usage de chaînes de Markov tout ce temps sans le savoir!

nom de génération

Avez-vous déjà participé à des jeux de table, jeux MMORPG, ou même l`écriture de fiction? Vous avez peut-être angoissée sur la désignation de vos personnages (au moins à un moment ou un autre) - et quand vous semblez ne pouvais pas penser à un nom que vous voulez, vous avez probablement eu recours à un générateur de nom en ligne.Créer un nouveau Alias ​​avec les meilleurs générateurs de nom en ligne [Bizarre & Web merveilleux]Créer un nouveau Alias ​​avec les meilleurs générateurs de nom en ligne [Bizarre & Web merveilleux]Votre nom est ennuyeux. Heureusement, vous pouvez aller en ligne et choisir un nouvel alias en utilisant l`un des nombreux générateurs de noms disponibles sur le Internetz.Lire la suite

Avez-vous déjà demandé comment ces générateurs de noms travaillé? 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 existe d`autres algorithmes là-bas qui sont tout aussi efficaces, bien sûr!)

Tout ce que vous avez besoin est une collection de lettres où chaque lettre a une liste de suivi potentiels des lettres avec des probabilités. Ainsi, par exemple, la lettre « M » a une chance de 60 pour cent pour mener à la lettre « A » et une chance de 40 pour cent pour mener à la lettre « I ». Pour ce faire, pour tout un tas d`autres lettres, puis exécutez l`algorithme. Boom, vous avez un nom qui est logique! (La plupart du temps, de toute façon.)

PageRank Google

L`une des conséquences intéressantes de la théorie des chaînes de Markov est que la longueur de la chaîne augmente (le nombre de transitions d`état augmente), la probabilité que vous atterrissez 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.

Cela est extrêmement intéressant quand vous pensez du monde entier Wide Web comme un système de Markov où chaque page est un état et les liens entre les pages Web sont des transitions avec des probabilités. Ce théorème dit essentiellement que peu importe que vous commencez page Web, votre chance de l`atterrissage sur une certaine page Web X est une probabilité fixe, en supposant une « longue période » de surf.

Et ceci est la base de la façon dont Google classe les pages Web. En effet, l`algorithme de PageRank est modifié: forme (lire plus avancé) de l`algorithme de chaîne de Markov.

Plus la « probabilité fixe » d`arriver à une certaine page web, plus son PageRank. En effet, une plus grande probabilité fixe implique que la page Web a beaucoup de liens entrants provenant d`autres pages Web - et Google suppose que si une page Web a beaucoup de liens entrants, il doit être utile. Les liens entrants, plus il est précieux.

Il est plus compliqué que cela, bien sûr, mais il est logique. Pourquoi un site comme About.com obtenir une plus grande priorité sur les pages de résultats de recherche? Parce qu`il se avère que les utilisateurs ont tendance à y arriver car ils surfent sur le web. Intéressant, non?

Video: [RévisionsBac.com] - Graphe probabiliste et matrice de transition

Prévision Typing Mot

Les téléphones mobiles ont eu saisie prédictive depuis des décennies, mais pouvez-vous deviner comment ces prévisions sont faites? Que vous utilisez Android (d`autres options de clavier) Ou iOS (d`autres options de clavier), Il y a une bonne chance que votre application de choix utilise les chaînes de Markov.Qu`est-ce que le clavier meilleure alternative pour Android?Qu`est-ce que le clavier meilleure alternative pour Android?Nous examinons certains des meilleurs claviers du Play Store et les mettre à l`épreuve.Lire la suite

Video: 8 Processus stochastiques Variables aléatoires et chaînes Markov

Voilà pourquoi les applications du clavier demandent s`ils peuvent recueillir des données sur vos habitudes de frappe. Par exemple, dans Google Clavier, il y a un paramètre appelé extraits Partager qui demande aux « extraits d`actions de quoi et comment vous tapez dans Google Apps pour améliorer Google Clavier ». Essentiellement, vos mots sont analysées et intégrées dans les probabilités de la chaîne de Markov de l`application.

C`est aussi pourquoi clavier applications présentent souvent trois ou plusieurs options, généralement dans l`ordre le plus probable au moins probable. Il ne peut pas savoir avec certitude ce que vous vouliez dire taper à côté, mais il est exact le plus souvent.

subreddit Simulation

Si vous ne l`avez jamais utilisé Reddit, nous vous invitons à vérifier au moins cette expérience fascinante appelée / r / SubredditSimulator.

Autrement dit, subreddit Simulator prend dans un morceau massif de tous les commentaires et les titres en travers de nombreuses communautés de Reddit, puis analyse le mot par mot maquillage de chaque phrase. Grâce à ces données, il génère des probabilités mot à mot - utilise alors ces probabilités pour venir générer des titres et des commentaires à partir de zéro.

Une couche intéressant de cette expérience est que les commentaires et les titres sont classés par la communauté à partir de laquelle les données sont venues, de sorte que les types de commentaires et titres générés par / r / l`ensemble de données de nourriture sont très différentes des commentaires et titres génère par / r / les données de football définies.

Et le plus drôle - ou peut-être le plus inquiétant - une partie de tout cela est que les commentaires et les titres générés peuvent souvent être impossibles à distinguer de celles qui sont faites par des personnes réelles. Il est absolument fascinant.

Connaissez-vous d`autres utilisations cool pour les chaînes de Markov? Vous avez des questions qui ont encore besoin de répondre? Faites-nous savoir dans un commentaire en bas!