Introduzione alle catene di Markov con esempi - Catene di Markov con Python

Introduzione alle catene di Markov:

Ti sei mai chiesto come Google classifica le pagine web? Se hai fatto la tua ricerca, devi sapere che utilizza l'algoritmo PageRank che si basa sull'idea delle catene di Markov. Questo articolo sull'introduzione alle catene di Markov ti aiuterà a capire l'idea di base dietro le catene di Markov e come possono essere modellate come soluzione ai problemi del mondo reale.

Ecco un elenco di argomenti che verranno trattati in questo blog:

1. Cos'è una catena di Markov?
2. Cos'è la proprietà Markov?
3. Capire le catene di Markov con un esempio
4. Cos'è una matrice di transizione?
5. Markov Chain In Python
6. Applicazioni della catena di Markov

Per ottenere una conoscenza approfondita di Data Science e Machine Learning utilizzando Python, puoi iscriverti a live di Edureka con supporto 24 ore su 24, 7 giorni su 7 e accesso a vita.

Cos'è una catena di Markov?

Andrey Markov ha introdotto per la prima volta le catene Markov nel 1906. Ha spiegato le catene Markov come:

Un processo stocastico contenente variabili casuali, che passa da uno stato all'altro in base a determinati presupposti e regole probabilistiche definite.

Questi casuali le variabili passano da uno a uno stato all'altro, in base a un'importante proprietà matematica chiamata Proprietà Markov.

Questo ci porta alla domanda:

Cos'è la proprietà Markov?

La proprietà Discrete Time Markov afferma che la probabilità calcolata che un processo casuale passi al successivo stato possibile dipende solo dallo stato e dal tempo correnti ed è indipendente dalla serie di stati che lo hanno preceduto.

Il fatto che la successiva azione / stato possibile di un processo casuale non dipenda dalla sequenza di stati precedenti, rende le catene di Markov come un processo senza memoria che dipende esclusivamente dallo stato / azione corrente di una variabile.

Deriviamo matematicamente:

Sia il processo casuale {Xm, m = 0,1,2, ⋯}.

Questo processo è una catena di Markov solo se,

Markov Chain - Introduzione a Markov Chains - Edureka

per tutti m, j, i, i0, i1, ⋯ im e meno1

Per un numero finito di stati, S = {0, 1, 2, ⋯, r}, questa è chiamata catena di Markov finita.

P (Xm + 1 = j | Xm = i) qui rappresenta le probabilità di transizione per passare da uno stato all'altro. Qui, supponiamo che le probabilità di transizione siano indipendenti dal tempo.

Il che significa che P (Xm + 1 = j | Xm = i) non dipende dal valore di 'm'. Pertanto, possiamo riassumere,

Markov Chain Formula - Introduzione alle catene Markov - Edureka

Quindi questa equazione rappresenta la catena Markov.

Ora capiamo cosa sono esattamente le catene di Markov con un esempio.

Esempio di catena di Markov

Prima di farti un esempio, definiamo cos'è un modello di Markov:

Cos'è un modello Markov?

Un modello di Markov è un modello stocastico che modella variabili casuali in modo tale che le variabili seguano la proprietà di Markov.

Ora vediamo come funziona un modello di Markov con un semplice esempio.

Come accennato in precedenza, le catene di Markov vengono utilizzate nella generazione di testo e nelle applicazioni di completamento automatico. Per questo esempio, daremo un'occhiata a una frase di esempio (casuale) e vedremo come può essere modellata utilizzando catene di Markov.

Esempio di catena di Markov - Introduzione alle catene di Markov - Edureka

La frase sopra è il nostro esempio, so che non ha molto senso (non è necessario), è una frase contenente parole casuali, in cui:

1. Chiavi denota le parole uniche nella frase, cioè 5 tasti (uno, due, hail, happy, edureka)

2. Gettoni denotano il numero totale di parole, cioè 8 gettoni.

Andando avanti, dobbiamo capire la frequenza di occorrenza di queste parole, il diagramma sottostante mostra ogni parola insieme a un numero che denota la frequenza di quella parola.

Keys And Frequencies - Introduzione alle catene di Markov - Edureka

Quindi la colonna di sinistra qui indica le chiavi e la colonna di destra indica le frequenze.

Dalla tabella sopra, possiamo concludere che la chiave 'edureka' è 4 volte maggiore di qualsiasi altra chiave. È importante dedurre tali informazioni perché possono aiutarci a prevedere quale parola potrebbe verificarsi in un determinato momento. Se dovessi indovinare la parola successiva nella frase di esempio, sceglierei 'edureka' poiché ha la più alta probabilità di occorrenza.

Parlando di probabilità, un'altra misura di cui devi essere consapevole è distribuzioni ponderate.

Nel nostro caso, la distribuzione ponderata per 'edureka' è del 50% (4/8) perché la sua frequenza è 4, su un totale di 8 gettoni. Il resto delle chiavi (uno, due, grandine, felice) hanno tutte 1/8 di probabilità che si verifichino (e asymp 13%).

Ora che abbiamo una comprensione della distribuzione ponderata e un'idea di come parole specifiche ricorrono più frequentemente di altre, possiamo andare avanti con la parte successiva.

Capire le catene di Markov - Introduzione alle catene di Markov - Edureka

Nella figura sopra, ho aggiunto due parole aggiuntive che denotano l'inizio e la fine della frase, capirai perché l'ho fatto nella sezione seguente.

Ora assegniamo anche la frequenza a questi tasti:

Tasti e frequenze aggiornate - Introduzione alle catene di Markov - Edureka

Ora creiamo un modello Markov. Come accennato in precedenza, un modello di Markov viene utilizzato per modellare variabili casuali in un particolare stato in modo tale che gli stati futuri di queste variabili dipendono esclusivamente dal loro stato attuale e non dai loro stati passati.

Quindi fondamentalmente in un modello di Markov, per prevedere lo stato successivo, dobbiamo considerare solo lo stato corrente.

Nel diagramma sottostante, puoi vedere come ogni gettone nella nostra frase porta a un altro. Ciò mostra che lo stato futuro (token successivo) è basato sullo stato corrente (token presente). Quindi questa è la regola più basilare nel modello di Markov.

Il diagramma seguente mostra che ci sono coppie di gettoni in cui ogni gettone nella coppia conduce all'altro nella stessa coppia.

Markov Chain Pairs - Introduzione alle catene Markov - Edureka

Nel diagramma sottostante, ho creato una rappresentazione strutturale che mostra ogni chiave con una serie di possibili token successivi con cui può essere accoppiata.

Una serie di coppie di catene di Markov - Introduzione alle catene di Markov - Edureka

Per riassumere questo esempio, considera uno scenario in cui dovrai formare una frase utilizzando l'array di chiavi e token che abbiamo visto nell'esempio precedente. Prima di eseguire questo esempio, un altro punto importante è che dobbiamo specificare due misure iniziali:

1. Una distribuzione di probabilità iniziale (ovvero lo stato iniziale all'ora = 0, (chiave 'Start'))

2. Una probabilità di transizione di saltare da uno stato a un altro (in questo caso, la probabilità di passare da un token all'altro)

Abbiamo definito la distribuzione ponderata all'inizio stessa, quindi abbiamo le probabilità e lo stato iniziale, ora andiamo avanti con l'esempio.

• Quindi, per iniziare con il token iniziale è [Start]

• Successivamente, abbiamo solo un possibile token, ovvero [uno]

• Attualmente, la frase contiene una sola parola, ovvero 'una'

• Da questo token, il prossimo token possibile è [edureka]

• La frase è aggiornata a 'one edureka'

• Da [edureka] possiamo passare a uno qualsiasi dei seguenti gettoni [due, salve, felice, fine]

• C'è una probabilità del 25% che 'due' vengano scelti, questo potrebbe portare a formare la frase originale (un edureka due edureka hail edureka happy edureka). Tuttavia, se viene selezionato 'end', il processo si interrompe e finiremo per generare una nuova frase, ovvero 'one edureka'.

Datti una pacca sulla spalla perché hai appena costruito un modello Markov e hai eseguito un test case attraverso di esso. Per riassumere l'esempio precedente, abbiamo fondamentalmente utilizzato lo stato attuale (parola presente) per determinare lo stato successivo (parola successiva). Ed è esattamente ciò che è un processo Markov.

È un processo stocastico in cui le variabili casuali passano da uno stato all'altro in modo tale che lo stato futuro di una variabile dipende solo dallo stato presente.

Andiamo al passaggio successivo e disegniamo il modello di Markov per questo esempio.

Diagramma di transizione di stato - Introduzione alle catene di Markov - Edureka

La figura sopra è nota come diagramma di transizione di stato. Ne parleremo di più nella sezione seguente, per ora ricorda che questo diagramma mostra le transizioni e la probabilità da uno stato all'altro.

Si noti che ogni ovale nella figura rappresenta una chiave e le frecce sono dirette verso le possibili chiavi che possono seguirla. Inoltre, i pesi sulle frecce indicano il probabilità o distribuzione ponderata della transizione da / verso i rispettivi stati.

Quindi era tutto su come funziona il modello Markov. Ora proviamo a capire alcune importanti terminologie nel processo di Markov.

Che cos'è una matrice delle probabilità di transizione?

Nella sezione precedente abbiamo discusso il funzionamento di un modello di Markov con un semplice esempio, ora comprendiamo le terminologie matematiche in un processo di Markov.

In un processo di Markov, usiamo una matrice per rappresentare le probabilità di transizione da uno stato all'altro. Questa matrice è chiamata matrice di transizione o probabilità. Di solito è indicato da P.

ha una relazione in java

Matrice di transizione - Introduzione alle catene di Markov - Edureka

Nota, pij & ge0 e 'i' per tutti i valori è,

Transition Matrix Formula - Introduzione alle catene di Markov - Edureka

Lasciatemi spiegare questo. Supponendo che il nostro stato attuale sia 'i', lo stato successivo o imminente deve essere uno degli stati potenziali. Pertanto, pur prendendo la somma di tutti i valori di k, dobbiamo ottenerne uno.

Che cos'è un diagramma di transizione di stato?

Un modello di Markov è rappresentato da un diagramma di transizione di stato. Il diagramma mostra le transizioni tra i diversi stati in una catena di Markov. Comprendiamo la matrice di transizione e la matrice di transizione di stato con un esempio.

Esempio di matrice di transizione

Considera una catena di Markov con tre stati 1, 2 e 3 e le seguenti probabilità:

Esempio di matrice di transizione - Introduzione alle catene di Markov - Edureka

Esempio di diagramma di transizione di stato - Introduzione alle catene di Markov - Edureka

Il diagramma sopra rappresenta il diagramma di transizione di stato per la catena di Markov. Qui, 1,2 e 3 sono i tre stati possibili e le frecce che puntano da uno stato all'altro rappresentano le probabilità di transizione pij. Quando, pij = 0, significa che non c'è transizione tra lo stato 'i' e lo stato 'j'.

Ora che noi conoscere la matematica e la logica alla base delle catene di Markov, eseguiamo una semplice demo e capiamo dove è possibile utilizzare le catene di Markov.

Markov Chain In Python

Per eseguire questa demo, userò Python, quindi se non conosci Python, puoi consultare i seguenti blog:

2. Come imparare Python 3 da zero - Una guida per principianti

Ora iniziamo con la programmazione!

Markov Chain Text Generator

Dichiarazione problema: Per applicare la proprietà Markov e creare un modello Markov in grado di generare simulazioni di testo studiando il set di dati vocali di Donald Trump.

Descrizione set di dati: Il file di testo contiene un elenco di discorsi pronunciati da Donald Trump nel 2016.

Logica: Applica la proprietà Markov per generare il discorso di Trump di Donald considerando ogni parola usata nel discorso e per ogni parola, crea un dizionario di parole che verranno utilizzate successivamente.

Passaggio 1: importare i pacchetti richiesti

importa numpy come np

Passaggio 2: leggere il set di dati

trump = open ('C: //Users//NeelTemp//Desktop//demos//speeches.txt', encoding = 'utf8'). read () #display the data print (trump) SPEECH 1 ... Thank tu così tanto. È così carino. Non è un bravo ragazzo. Non ottiene una stampa equa, non la ottiene. È semplicemente ingiusto. E devo dirti che sono qui, e molto fortemente qui, perché ho un grande rispetto per Steve King e allo stesso modo ho un grande rispetto per Citizens United, David e tutti, e un grande rispetto per il Tea Party. Inoltre, anche la gente dell'Iowa. Hanno qualcosa in comune. Persone laboriose ...

Passaggio 3: dividi il set di dati in singole parole

corpus = trump.split () # Visualizza il corpus print (corpus) 'potente', 'ma', 'non', 'potente', 'mi piace', 'noi.', 'Iran', 'ha', ' seminato ',' terrore ', ...

Successivamente, crea una funzione che generi le diverse coppie di parole nei discorsi. Per risparmiare spazio, utilizzeremo un oggetto generatore.

Passaggio 4: creazione di coppie di chiavi e parole di follow-up

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

Quindi inizializziamo un dizionario vuoto per memorizzare le coppie di parole.

Nel caso in cui la prima parola della coppia sia già una chiave nel dizionario, aggiungi semplicemente la prossima parola potenziale all'elenco di parole che seguono la parola. Ma se la parola non è una chiave, crea una nuova voce nel dizionario e assegna la chiave uguale alla prima parola della coppia.

Passaggio 5: aggiunta del dizionario

word_dict = {} per word_1, word_2 in coppia: if word_1 in word_dict.keys (): word_dict [word_1] .append (word_2) else: word_dict [word_1] = [word_2]

Successivamente, selezioniamo a caso una parola dal corpus, che inizierà la catena di Markov.

Passaggio 6: costruire il modello Markov

# scegli in modo casuale la prima parola first_word = np.random.choice (corpus) #Scegli la prima parola come una parola in maiuscolo in modo che la parola selezionata non venga presa tra una frase mentre first_word.islower (): #Inizia la catena da la catena di parole selezionata = [prima_parola] #Inizializza il numero di parole stimolate n_parole = 20

Dopo la prima parola, ogni parola della catena viene campionata in modo casuale dall'elenco di parole che hanno seguito quella parola specifica nei discorsi dal vivo di Trump. Questo è mostrato nello snippet di codice seguente:

for i in range (n_words): chain.append (np.random.choice (word_dict [chain [-1]]))

Passaggio 7: previsioni

Infine, visualizziamo il testo stimolato.

#Join restituisce la catena sotto forma di stringa print ('' .join (chain)) Il numero di persone incredibili. E Hillary Clinton, ha la nostra gente e un ottimo lavoro. E non batteremo Obama

Quindi questo è il testo generato che ho ottenuto considerando il discorso di Trump. Potrebbe non avere molto senso, ma è abbastanza buono da farti capire come le catene di Markov possono essere utilizzate per generare automaticamente i testi.

Ora diamo un'occhiata ad altre applicazioni delle catene di Markov e come vengono utilizzate per risolvere i problemi del mondo reale.

Applicazioni della catena di Markov

Ecco un elenco di applicazioni del mondo reale delle catene di Markov:

1. PageRank di Google: L'intero web può essere pensato come un modello markoviano, in cui ogni pagina web può essere uno stato e i collegamenti o riferimenti tra queste pagine possono essere pensati come transizioni con probabilità. Quindi, in pratica, indipendentemente dalla pagina web su cui inizi a navigare, la possibilità di arrivare a una determinata pagina web, diciamo, X è una probabilità fissa.

2. Previsione di parole di digitazione: Le catene di Markov sono note per essere utilizzate per prevedere le parole imminenti. Possono anche essere utilizzati nell'auto-completamento e nei suggerimenti.

3. Simulazione di subreddit: Sicuramente ti sei imbattuto in Reddit e hai avuto un'interazione su uno dei loro thread o subreddit. Reddit utilizza un simulatore di subreddit che consuma un'enorme quantità di dati contenenti tutti i commenti e le discussioni tenuti nei loro gruppi. Facendo uso delle catene di Markov, il simulatore produce probabilità parola per parola, per creare commenti e argomenti.

4. Generatore di testo: Le catene di Markov sono più comunemente utilizzate per generare testi fittizi o produrre grandi saggi e compilare discorsi. Viene utilizzato anche nei generatori di nomi che vedi sul web.

Ora che sai come risolvere un problema del mondo reale utilizzando le catene di Markov, sono sicuro che sei curioso di saperne di più. Ecco un elenco di blog che ti aiuteranno a iniziare con altri concetti statistici:

Con questo, arriviamo alla fine di questo blog Introduzione alle catene di Markov. Se hai domande su questo argomento, lascia un commento qui sotto e ti ricontatteremo.

Restate sintonizzati per altri blog sulle tecnologie di tendenza.

Se stai cercando una formazione strutturata online in Data Science, edureka! ha un programma che ti aiuta ad acquisire esperienza in statistica, data wrangling, analisi esplorativa dei dati, algoritmi di machine learning come clustering K-Means, alberi decisionali, foresta casuale, bayes naive. Imparerai anche i concetti di serie temporali, estrazione di testo e un'introduzione al deep learning. Presto inizieranno nuovi lotti per questo corso !!