Introduction aux chaînes de Markov avec des exemples - Chaînes de Markov avec Python

Introduction aux chaînes de Markov:

Vous êtes-vous déjà demandé comment Google classe les pages Web? Si vous avez effectué vos recherches, sachez qu'il utilise l'algorithme de PageRank basé sur l'idée des chaînes de Markov. Cet article sur l'introduction aux chaînes de Markov vous aidera à comprendre l'idée de base des chaînes de Markov et comment elles peuvent être modélisées comme solution à des problèmes du monde réel.

Voici une liste de sujets qui seront abordés dans ce blog:

1. Qu'est-ce qu'une chaîne de Markov?
2. Qu'est-ce que la propriété Markov?
3. Comprendre les chaînes de Markov avec un exemple
4. Qu'est-ce qu'une matrice de transition?
5. Chaîne de Markov en Python
6. Applications de la chaîne de Markov

Pour obtenir des connaissances approfondies sur la science des données et l'apprentissage automatique à l'aide de Python, vous pouvez vous inscrire en direct par Edureka avec une assistance 24/7 et un accès à vie.

Qu'est-ce qu'une chaîne de Markov?

Andrey Markov a introduit pour la première fois les chaînes de Markov en 1906. Il a expliqué les chaînes de Markov comme suit:

Processus stochastique contenant des variables aléatoires, passant d'un état à un autre en fonction de certaines hypothèses et de règles probabilistes définies.

Ces aléatoires la transition des variables d'un état à l'autre, basée sur une propriété mathématique importante appelée Propriété Markov.

Cela nous amène à la question:

Qu'est-ce que la propriété Markov?

La propriété de Markov à temps discret indique que la probabilité calculée d'un processus aléatoire de passer à l'état possible suivant dépend uniquement de l'état et de l'heure actuels et qu'elle est indépendante de la série d'états qui l'ont précédée.

Le fait que la prochaine action / état possible d'un processus aléatoire ne dépend pas de la séquence des états antérieurs, rend les chaînes de Markov comme un processus sans mémoire qui dépend uniquement de l'état / action actuel d'une variable.

Calculons cela mathématiquement:

Soit le processus aléatoire, {Xm, m = 0,1,2, ⋯}.

Ce processus est une chaîne de Markov uniquement si,

Chaîne de Markov - Introduction aux chaînes de Markov - Edureka

pour tout m, j, i, i0, i1, ⋯ im & minus1

Pour un nombre fini d'états, S = {0, 1, 2, ⋯, r}, cela s'appelle une chaîne de Markov finie.

P (Xm + 1 = j | Xm = i) représente ici les probabilités de transition pour passer d'un état à l'autre. Ici, nous supposons que les probabilités de transition sont indépendantes du temps.

Ce qui signifie que P (Xm + 1 = j | Xm = i) ne dépend pas de la valeur de «m». Par conséquent, nous pouvons résumer,

Formule de chaîne de Markov - Introduction aux chaînes de Markov - Edureka

Donc cette équation représente la chaîne de Markov.

Voyons maintenant ce que sont exactement les chaînes de Markov avec un exemple.

Exemple de chaîne de Markov

Avant de vous donner un exemple, définissons ce qu'est un modèle de Markov:

Qu'est-ce qu'un modèle Markov?

Un modèle de Markov est un modèle stochastique qui modélise des variables aléatoires de telle manière que les variables suivent la propriété de Markov.

Voyons maintenant comment fonctionne un modèle de Markov avec un exemple simple.

Comme mentionné précédemment, les chaînes de Markov sont utilisées dans les applications de génération de texte et de saisie semi-automatique. Pour cet exemple, nous allons examiner une phrase d'exemple (aléatoire) et voir comment elle peut être modélisée à l'aide de chaînes de Markov.

Exemple de chaîne de Markov - Introduction aux chaînes de Markov - Edureka

La phrase ci-dessus est notre exemple, je sais que cela n’a pas beaucoup de sens (ce n’est pas nécessaire), c’est une phrase contenant des mots aléatoires, dans laquelle:

1. Clés désignent les mots uniques dans la phrase, c'est-à-dire 5 clés (un, deux, grêle, heureux, edureka)

2. Jetons désignent le nombre total de mots, soit 8 jetons.

Pour aller de l'avant, nous devons comprendre la fréquence d'occurrence de ces mots, le diagramme ci-dessous montre chaque mot avec un nombre qui indique la fréquence de ce mot.

Clés et fréquences - Introduction aux chaînes de Markov - Edureka

Ainsi, la colonne de gauche désigne ici les clés et la colonne de droite les fréquences.

À partir du tableau ci-dessus, nous pouvons conclure que la clé «edureka» est 4x plus élevée que toute autre clé. Il est important de déduire de telles informations, car elles peuvent nous aider à prédire quel mot pourrait apparaître à un moment donné. Si je devais deviner le mot suivant dans la phrase d’exemple, je choisirais «edureka» car il a la plus grande probabilité d’occurrence.

En parlant de probabilité, une autre mesure dont vous devez être conscient est distributions pondérées.

Dans notre cas, la distribution pondérée pour «edureka» est de 50% (4/8) car sa fréquence est de 4, sur un total de 8 jetons. Le reste des touches (une, deux, grêle, heureux) ont toutes 1 / 8ème de chance de se produire (& asymp 13%).

Maintenant que nous avons une compréhension de la distribution pondérée et une idée de la façon dont des mots spécifiques se produisent plus fréquemment que d'autres, nous pouvons passer à la partie suivante.

Comprendre les chaînes de Markov - Introduction aux chaînes de Markov - Edureka

Dans la figure ci-dessus, j'ai ajouté deux mots supplémentaires qui désignent le début et la fin de la phrase, vous comprendrez pourquoi j'ai fait cela dans la section ci-dessous.

Maintenant, attribuons également la fréquence à ces touches:

Clés et fréquences mises à jour - Introduction aux chaînes de Markov - Edureka

Créons maintenant un modèle de Markov. Comme mentionné précédemment, un modèle de Markov est utilisé pour modéliser des variables aléatoires à un état particulier de telle sorte que les états futurs de ces variables dépendent uniquement de leur état actuel et non de leurs états passés.

Donc, fondamentalement, dans un modèle de Markov, pour prédire l'état suivant, nous ne devons considérer que l'état actuel.

Dans le diagramme ci-dessous, vous pouvez voir comment chaque jeton de notre phrase en mène à un autre. Cela montre que l'état futur (jeton suivant) est basé sur l'état actuel (jeton actuel). C'est donc la règle la plus élémentaire du modèle de Markov.

Le diagramme ci-dessous montre qu'il existe des paires de jetons où chaque jeton de la paire mène à l'autre de la même paire.

Paires de chaînes de Markov - Introduction aux chaînes de Markov - Edureka

Dans le diagramme ci-dessous, j'ai créé une représentation structurelle qui montre chaque clé avec un tableau des prochains jetons possibles avec lesquels elle peut s'associer.

Une gamme de paires de chaînes de Markov - Introduction aux chaînes de Markov - Edureka

Pour résumer cet exemple, considérez un scénario dans lequel vous devrez former une phrase en utilisant le tableau de clés et de jetons que nous avons vu dans l'exemple ci-dessus. Avant de parcourir cet exemple, un autre point important est que nous devons spécifier deux mesures initiales:

1. Une distribution de probabilité initiale (c'est-à-dire l'état de départ au temps = 0, (touche «Start»))

2. Une probabilité de transition de sauter d'un état à un autre (dans ce cas, la probabilité de passer d'un jeton à l'autre)

Nous avons défini la distribution pondérée au début même, donc nous avons les probabilités et l’état initial, passons maintenant à l’exemple.

• Donc, pour commencer avec le jeton initial, c'est [Start]

• Ensuite, nous n'avons qu'un seul jeton possible, c'est-à-dire [un]

• Actuellement, la phrase ne comporte qu’un seul mot, c’est-à-dire «un»

• À partir de ce jeton, le prochain jeton possible est [edureka]

• La phrase est mise à jour en «one edureka»

• Depuis [edureka], nous pouvons passer à l’un des jetons suivants [deux, salut, heureux, fin]

• Il y a 25% de chances que «deux» soit choisi, cela aboutirait probablement à la formation de la phrase originale (un edureka deux edureka grêle edureka happy edureka). Cependant, si «fin» est choisi, le processus s'arrête et nous finirons par générer une nouvelle phrase, c'est-à-dire «une edureka».

Donnez-vous une tape dans le dos parce que vous venez de créer un modèle de Markov et d'exécuter un cas de test. Pour résumer l'exemple ci-dessus, nous avons essentiellement utilisé l'état actuel (mot présent) pour déterminer l'état suivant (mot suivant). Et c’est exactement ce qu’est un processus de Markov.

Il s'agit d'un processus stochastique dans lequel les variables aléatoires passent d'un état à l'autre de telle sorte que l'état futur d'une variable ne dépend que de l'état présent.

Passons à l'étape suivante et dessinons le modèle de Markov pour cet exemple.

Diagramme de transition d'état - Introduction aux chaînes de Markov - Edureka

La figure ci-dessus est connue sous le nom de diagramme de transition d'état. Nous en parlerons plus en détail dans la section ci-dessous, pour l'instant rappelez-vous que ce diagramme montre les transitions et la probabilité d'un état à un autre.

Notez que chaque ovale de la figure représente une clé et les flèches sont dirigées vers les touches possibles qui peuvent la suivre. De plus, les poids sur les flèches indiquent le la probabilité ou la distribution pondérée de la transition de / vers les états respectifs.

C'était donc tout sur le fonctionnement du modèle de Markov. Essayons maintenant de comprendre certaines terminologies importantes du processus de Markov.

Qu'est-ce qu'une matrice de probabilité de transition?

Dans la section ci-dessus, nous avons discuté du fonctionnement d'un modèle de Markov avec un exemple simple, comprenons maintenant les terminologies mathématiques dans un processus de Markov.

Dans un processus de Markov, nous utilisons une matrice pour représenter les probabilités de transition d'un état à un autre. Cette matrice est appelée la matrice de transition ou de probabilité. Il est généralement désigné par P.

Matrice de transition - Introduction aux chaînes de Markov - Edureka

Remarque, pij & ge0, et «i» pour toutes les valeurs est,

Formule de matrice de transition - Introduction aux chaînes de Markov - Edureka

Laissez-moi vous expliquer. En supposant que notre état actuel est «i», l’état suivant ou à venir doit être l’un des états potentiels. Par conséquent, tout en prenant la somme de toutes les valeurs de k, nous devons en obtenir une.

Qu'est-ce qu'un diagramme de transition d'état?

Un modèle de Markov est représenté par un diagramme de transition d'état. Le diagramme montre les transitions entre les différents états d'une chaîne de Markov. Comprenons la matrice de transition et la matrice de transition d’état avec un exemple.

Exemple de matrice de transition

Considérons une chaîne de Markov avec trois états 1, 2 et 3 et les probabilités suivantes:

Exemple de matrice de transition - Introduction aux chaînes de Markov - Edureka

Exemple de diagramme de transition d'état - Introduction aux chaînes de Markov - Edureka

Le diagramme ci-dessus représente le diagramme de transition d'état pour la chaîne de Markov. Ici, 1, 2 et 3 sont les trois états possibles, et les flèches pointant d'un état vers les autres états représentent les probabilités de transition pij. Lorsque, pij = 0, cela signifie qu’il n’y a pas de transition entre l’état «i» et l’état «j».

Maintenant que nous connaître les mathématiques et la logique derrière les chaînes de Markov, exécutons une démonstration simple et comprenons où les chaînes de Markov peuvent être utilisées.

Chaîne de Markov en Python

Pour exécuter cette démo, j'utiliserai Python, donc si vous ne connaissez pas Python, vous pouvez consulter les blogs suivants:

2. Comment apprendre Python 3 à partir de zéro - Un guide du débutant

Commençons maintenant avec le codage!

Générateur de texte de chaîne de Markov

Énoncé du problème: Pour appliquer la propriété de Markov et créer un modèle de Markov qui peut générer des simulations de texte en étudiant l'ensemble de données vocales de Donald Trump.

Description de l'ensemble de données: Le fichier texte contient une liste des discours prononcés par Donald Trump en 2016.

Logique: Appliquez la propriété Markov pour générer le discours de Donald Trump en considérant chaque mot utilisé dans le discours et pour chaque mot, créez un dictionnaire de mots qui seront utilisés ensuite.

Étape 1: importez les packages requis

importer numpy comme np

Étape 2: lire l'ensemble de données

configurer eclipse pour java

trump = open ('C: //Users//NeelTemp//Desktop//demos//speeches.txt', encoding = 'utf8'). read () #afficher les données print (trump) SPEECH 1 ... Merci vous tellement. C'est tellement bien. N'est-il pas un gars formidable. Il n'a pas une bonne presse, il ne comprend pas. C'est pas juste. Et je dois vous dire que je suis ici, et très fortement ici, parce que j'ai un grand respect pour Steve King et j'ai aussi un grand respect pour Citizens United, David et tout le monde, et un énorme résect pour le Tea Party. Aussi, aussi les habitants de l'Iowa. Ils ont quelque chose en commun. Travailleur acharné....

Étape 3: divisez l'ensemble de données en mots individuels

corpus = trump.split () #Afficher le corpus print (corpus) 'puissant', 'mais', 'pas', 'puissant', 'comme', 'nous.', 'Iran', 'a', ' semé ',' terreur ', ...

Ensuite, créez une fonction qui génère les différentes paires de mots dans les discours. Pour économiser de l'espace, nous utiliserons un objet générateur.

Étape 4: Création de paires de clés et de mots de suivi

def make_pairs (corpus): for i in range (len (corpus) - 1): yield (corpus [i], corpus [i + 1]) pairs = make_pairs (corpus)

Ensuite, initialisons un dictionnaire vide pour stocker les paires de mots.

Si le premier mot de la paire est déjà une clé du dictionnaire, ajoutez simplement le mot potentiel suivant à la liste des mots qui suivent le mot. Mais si le mot n'est pas une clé, créez une nouvelle entrée dans le dictionnaire et attribuez la clé égale au premier mot de la paire.

Étape 5: Ajout du dictionnaire

word_dict = {} pour mot_1, mot_2 par paires: if word_1 dans word_dict.keys (): word_dict [word_1] .append (word_2) else: word_dict [word_1] = [word_2]

Ensuite, nous choisissons au hasard un mot du corpus, qui commencera la chaîne de Markov.

Étape 6: Construisez le modèle de Markov

# choisir au hasard le premier mot first_word = np.random.choice (corpus) #Choisir le premier mot en majuscule pour que le mot choisi ne soit pas pris entre une phrase tandis que first_word.islower (): #Démarrer la chaîne à partir la chaîne de mots sélectionnés = [first_word] #Initialize le nombre de mots stimulés n_words = 20

Après le premier mot, chaque mot de la chaîne est échantillonné au hasard dans la liste des mots qui ont suivi ce mot spécifique dans les discours en direct de Trump. Ceci est illustré dans l'extrait de code ci-dessous:

pour i dans la plage (n_words): chain.append (np.random.choice (word_dict [chain [-1]]))

Étape 7: Prédictions

Enfin, affichons le texte stimulé.

#Join renvoie la chaîne sous forme de chaîne print ('' .join (chain)) Le nombre de personnes incroyables. Et Hillary Clinton, a nos gens, et un excellent travail. Et nous ne battrons pas Obama

Voilà donc le texte généré que j'ai obtenu en considérant le discours de Trump. Cela n'a peut-être pas beaucoup de sens, mais c'est suffisant pour vous faire comprendre comment les chaînes de Markov peuvent être utilisées pour générer automatiquement des textes.

Voyons maintenant quelques autres applications des chaînes de Markov et comment elles sont utilisées pour résoudre des problèmes du monde réel.

Applications de la chaîne de Markov

Voici une liste d'applications réelles des chaînes de Markov:

1. PageRank Google: L'ensemble du Web peut être considéré comme un modèle de Markov, où chaque page Web peut être un état et les liens ou références entre ces pages peuvent être considérés comme des transitions avec des probabilités. Donc, en gros, quelle que soit la page Web sur laquelle vous commencez à surfer, la chance d'accéder à une certaine page Web, disons X, est une probabilité fixe.

2. Prédiction de mots de frappe: Les chaînes de Markov sont connues pour être utilisées pour prédire les mots à venir. Ils peuvent également être utilisés pour la saisie semi-automatique et les suggestions.

3. Simulation Subreddit: Vous avez sûrement rencontré Reddit et avez eu une interaction sur l'un de leurs fils ou sous-reddit. Reddit utilise un simulateur de sous-reddit qui consomme une énorme quantité de données contenant tous les commentaires et discussions tenus dans leurs groupes. En utilisant des chaînes de Markov, le simulateur produit des probabilités mot à mot, pour créer des commentaires et des sujets.

4. Générateur de texte: Les chaînes de Markov sont le plus souvent utilisées pour générer des textes factices ou produire de grands essais et compiler des discours. Il est également utilisé dans les générateurs de noms que vous voyez sur le Web.

Maintenant que vous savez comment résoudre un problème réel en utilisant les chaînes de Markov, je suis sûr que vous êtes curieux d’en savoir plus. Voici une liste de blogs qui vous aideront à vous familiariser avec d’autres concepts statistiques:

Avec cela, nous arrivons à la fin de ce blog Introduction aux chaînes de Markov. Si vous avez des questions concernant ce sujet, veuillez laisser un commentaire ci-dessous et nous vous répondrons.

Restez à l'écoute pour plus de blogs sur les technologies de pointe.

Si vous recherchez une formation structurée en ligne en Data Science, edureka! a un spécialement organisé programme qui vous aide à acquérir une expertise dans les statistiques, la lutte contre les données, l'analyse de données exploratoire, les algorithmes d'apprentissage automatique tels que le clustering K-Means, les arbres de décision, la forêt aléatoire, Naive Bayes. Vous apprendrez également les concepts de séries temporelles, d'exploration de texte et une introduction au Deep Learning. De nouveaux lots pour ce cours commencent bientôt !!