Introducere în lanțurile Markov cu exemple - Lanțuri Markov cu Python

Introducere în lanțurile Markov:

V-ați întrebat vreodată cum clasează Google paginile web? Dacă ați făcut cercetarea, atunci trebuie să știți că folosește algoritmul PageRank care se bazează pe ideea lanțurilor Markov. Acest articol despre Introducere în lanțurile Markov vă va ajuta să înțelegeți ideea de bază din spatele lanțurilor Markov și cum pot fi modelate ca o soluție la problemele din lumea reală.

Iată o listă de subiecte care vor fi acoperite în acest blog:

1. Ce este un lanț Markov?
2. Ce este proprietatea Markov?
3. Înțelegerea lanțurilor Markov cu un exemplu
4. Ce este o matrice de tranziție?
5. Lanțul Markov în Python
6. Aplicații pentru lanțul Markov

Pentru a obține cunoștințe aprofundate despre știința datelor și învățarea automată folosind Python, vă puteți înscrie pentru live de Edureka cu suport 24/7 și acces pe viață.

Ce este un lanț Markov?

Andrey Markov a introdus pentru prima dată lanțurile Markov în anul 1906. El a explicat lanțurile Markov astfel:

Un proces stocastic care conține variabile aleatorii, trecând de la o stare la alta în funcție de anumite ipoteze și reguli probabilistice definite.

Acestea aleatorii variabilele trec de la o stare la alta, pe baza unei importante proprietăți matematice numite Proprietatea Markov.

Acest lucru ne aduce la întrebarea:

Ce este proprietatea Markov?

Proprietatea discretă Markov Time afirmă că probabilitatea calculată a unui proces aleatoriu care trece la următoarea stare posibilă depinde doar de starea și timpul curent și este independentă de seria de stări care l-au precedat.

Faptul că următoarea posibilă acțiune / stare a unui proces aleatoriu nu depinde de secvența stărilor anterioare, face ca lanțurile Markov să fie un proces fără memorie care depinde doar de starea / acțiunea curentă a unei variabile.

Să derivăm acest lucru matematic:

Fie procesul aleatoriu să fie, {Xm, m = 0,1,2, ⋯}.

Acest proces este un lanț Markov numai dacă,

Lanțul Markov - Introducere în lanțurile Markov - Edureka

pentru toate m, j, i, i0, i1, ⋯ im & minus1

Pentru un număr finit de stări, S = {0, 1, 2, ⋯, r}, aceasta se numește lanț finit Markov.

P (Xm + 1 = j | Xm = i) reprezintă aici probabilitățile de tranziție la trecerea de la o stare la alta. Aici, presupunem că probabilitățile de tranziție sunt independente de timp.

Ceea ce înseamnă că P (Xm + 1 = j | Xm = i) nu depinde de valoarea ‘m’. Prin urmare, putem rezuma,

Formula lanțului Markov - Introducere în lanțurile Markov - Edureka

Deci această ecuație reprezintă lanțul Markov.

Acum, să înțelegem exact ce sunt lanțurile Markov cu un exemplu.

Exemplu de lanț Markov

Înainte de a vă oferi un exemplu, să definim ce este un model Markov:

Ce este un model Markov?

Un model Markov este un model stochastic care modelează variabilele aleatorii în așa fel încât variabilele să urmeze proprietatea Markov.

Acum să înțelegem cum funcționează un model Markov cu un exemplu simplu.

După cum sa menționat mai devreme, lanțurile Markov sunt utilizate în aplicațiile de generare a textului și completare automată. Pentru acest exemplu, vom arunca o privire la un exemplu (aleatoriu) de propoziție și vom vedea cum poate fi modelat prin utilizarea lanțurilor Markov.

Exemplu de lanț Markov - Introducere în lanțurile Markov - Edureka

Propoziția de mai sus este exemplul nostru, știu că nu are prea mult sens (nu trebuie), este o propoziție care conține cuvinte aleatorii, în care:

1. Taste denotați cuvintele unice din propoziție, adică 5 taste (una, două, grindină, fericit, edureka)

2. Jetoane indicați numărul total de cuvinte, adică 8 jetoane.

Mergând mai departe, trebuie să înțelegem frecvența apariției acestor cuvinte, diagrama de mai jos arată fiecare cuvânt împreună cu un număr care denotă frecvența acelui cuvânt.

Chei și frecvențe - Introducere în lanțurile Markov - Edureka

Deci coloana din stânga aici indică tastele, iar coloana din dreapta indică frecvențele.

Din tabelul de mai sus, putem concluziona că tasta „edureka” apare de 4 ori la fel de mult ca orice altă cheie. Este important să deducem astfel de informații, deoarece ne pot ajuta să prezicem ce cuvânt ar putea apărea într-un anumit moment al timpului. Dacă ar fi să ghicesc despre cuvântul următor din propoziția de exemplu, aș merge cu „edureka”, deoarece are cea mai mare probabilitate de apariție.

Vorbind despre probabilitate, o altă măsură de care trebuie să fii conștient este distribuții ponderate.

În cazul nostru, distribuția ponderată pentru „edureka” este de 50% (4/8) deoarece frecvența sa este de 4, din totalul de 8 jetoane. Restul tastelor (una, două, grindină, fericite) au toate o șansă de 8/8 să apară (& asymp 13%).

Acum, că avem o înțelegere a distribuției ponderate și o idee despre modul în care cuvintele specifice apar mai frecvent decât altele, putem continua cu partea următoare.

Înțelegerea lanțurilor Markov - Introducere în lanțurile Markov - Edureka

În figura de mai sus, am adăugat două cuvinte suplimentare care denotă începutul și sfârșitul propoziției, veți înțelege de ce am făcut acest lucru în secțiunea de mai jos.

Acum, să atribuim și frecvența acestor taste:

Taste și frecvențe actualizate - Introducere în lanțurile Markov - Edureka

Acum să creăm un model Markov. După cum sa menționat mai devreme, un model Markov este utilizat pentru a modela variabile aleatorii într-o anumită stare, astfel încât stările viitoare ale acestor variabile să depindă doar de starea lor actuală și nu de stările lor anterioare.

Deci, practic, într-un model Markov, pentru a prezice următoarea stare, trebuie să luăm în considerare doar starea actuală.

În diagrama de mai jos, puteți vedea cum fiecare simbol din propoziția noastră duce la altul. Aceasta arată că starea viitoare (token-ul următor) se bazează pe starea actuală (token-ul actual). Deci, aceasta este regula cea mai de bază din modelul Markov.

Diagrama de mai jos arată că există perechi de jetoane în care fiecare jeton din pereche duce la celălalt din aceeași pereche.

Perechi de lanțuri Markov - Introducere în lanțurile Markov - Edureka

În diagrama de mai jos, am creat o reprezentare structurală care arată fiecare cheie cu o serie de jetoane posibile următoare cu care se poate împerechea.

cum se setează classpath în java

O serie de perechi de lanțuri Markov - Introducere în lanțurile Markov - Edureka

Pentru a rezuma acest exemplu, luați în considerare un scenariu în care va trebui să formați o propoziție utilizând matricea de chei și jetoane pe care le-am văzut în exemplul de mai sus. Înainte de a parcurge acest exemplu, un alt punct important este că trebuie să specificăm două măsuri inițiale:

1. O distribuție de probabilitate inițială (adică starea de pornire la timp = 0, (tasta „Start”))

2. O probabilitate de tranziție de a trece de la o stare la alta (în acest caz, probabilitatea de a trece de la un jeton la altul)

Am definit distribuția ponderată la începutul propriu-zis, deci avem probabilitățile și starea inițială, acum să continuăm cu exemplul.

• Deci, pentru a începe cu simbolul inițial este [Start]

• Apoi, avem un singur simbol posibil, adică [unul]

• În prezent, propoziția are un singur cuvânt, adică „unul”

• Din acest simbol, următorul simbol posibil este [edureka]

• Propoziția este actualizată la „one edureka”

• Din [edureka] putem trece la oricare dintre următoarele jetoane [două, grindină, fericit, sfârșit]

• Există 25% șanse ca „doi” să fie selectați, acest lucru ar duce eventual la formarea propoziției inițiale (o edureka două edureka hail edureka happy edureka). Cu toate acestea, dacă se alege „sfârșitul”, atunci procesul se oprește și vom ajunge să generăm o propoziție nouă, adică „o singură edureka”.

Dă-ți o palmă pe spate pentru că tocmai ai construit un model Markov și ai rulat un caz de testare prin el. Pentru a rezuma exemplul de mai sus, am folosit practic starea actuală (cuvânt prezent) pentru a determina starea următoare (cuvântul următor). Și exact asta este un proces Markov.

Este un proces stochastic în care variabilele aleatoare trec de la o stare la alta în așa fel încât starea viitoare a unei variabile depinde doar de starea actuală.

Să trecem la pasul următor și să desenăm modelul Markov pentru acest exemplu.

Diagrama tranziției de stat - Introducere în lanțurile Markov - Edureka

Figura de mai sus este cunoscută sub numele de diagrama de tranziție de stat. Vom vorbi mai multe despre acest lucru în secțiunea de mai jos, deocamdată nu uitați că această diagramă arată tranzițiile și probabilitatea de la o stare la alta.

Observați că fiecare oval din figură reprezintă o cheie și săgețile sunt direcționate către posibilele chei care o pot urmări. De asemenea, greutățile de pe săgeți denotă probabilitatea sau distribuția ponderată a tranziției de la / la stările respective.

Deci, totul a fost despre modul în care funcționează modelul Markov. Acum, să încercăm să înțelegem câteva terminologii importante din procesul Markov.

Ce este o matrice de probabilitate de tranziție?

În secțiunea de mai sus am discutat despre funcționarea unui model Markov cu un exemplu simplu, acum să înțelegem terminologiile matematice dintr-un proces Markov.

Într-un proces Markov, folosim o matrice pentru a reprezenta probabilitățile de tranziție de la o stare la alta. Această matrice se numește matrice de tranziție sau probabilitate. De obicei este notat cu P.

Matricea de tranziție - Introducere în lanțurile Markov - Edureka

Notă, pij & ge0 și „i” pentru toate valorile este,

Formula de matrice de tranziție - Introducere în lanțurile Markov - Edureka

Lasă-mă să explic asta. Presupunând că starea noastră actuală este „i”, următoarea sau următoarea stare trebuie să fie una dintre stările potențiale. Prin urmare, în timp ce luăm însumarea tuturor valorilor lui k, trebuie să obținem una.

Ce este o diagramă de tranziție de stat?

Un model Markov este reprezentat de o diagramă de tranziție de stat. Diagrama prezintă tranzițiile între diferitele stări dintr-un lanț Markov. Să înțelegem matricea de tranziție și matricea de tranziție a stării cu un exemplu.

Exemplu de matrice de tranziție

Luați în considerare un lanț Markov cu trei stări 1, 2 și 3 și următoarele probabilități:

Exemplu de matrice de tranziție - Introducere în lanțurile Markov - Edureka

Exemplu de diagramă de tranziție de stat - Introducere în lanțurile Markov - Edureka

Diagrama de mai sus reprezintă diagrama de tranziție a stării pentru lanțul Markov. Aici, 1,2 și 3 sunt cele trei stări posibile, iar săgețile care indică de la o stare la cealaltă stare reprezintă probabilitățile de tranziție pij. Când, pij = 0, înseamnă că nu există o tranziție între starea ‘i’ și starea ‘j’.

Acum că noi cunoașteți matematica și logica din spatele lanțurilor Markov, să desfășurăm o demonstrație simplă și să înțelegem unde pot fi utilizate lanțurile Markov.

Lanțul Markov în Python

Pentru a rula această demonstrație, voi folosi Python, deci dacă nu știți Python, puteți parcurge următoarele bloguri:

2. Cum să înveți Python 3 din Scratch - Un ghid pentru începători

Acum să începem cu codarea!

Markov Chain Text Generator

Declarație problemă: Pentru a aplica proprietatea Markov și a crea un model Markov care poate genera simulări de text prin studierea setului de date de vorbire Donald Trump.

Descrierea setului de date: Fișierul text conține o listă de discursuri susținute de Donald Trump în 2016.

diferența dintre c c # și c ++

Logică: Aplicați Markov Property pentru a genera discursul lui Donald’s Trump luând în considerare fiecare cuvânt folosit în discurs și pentru fiecare cuvânt, creați un dicționar de cuvinte care sunt folosite în continuare.

Pasul 1: Importați pachetele necesare

import numpy ca np

Pasul 2: Citiți setul de date

trump = open ('C: //Users//NeelTemp//Desktop//demos//speeches.txt', encoding = 'utf8'). read () #display the data print (trump) SPEECH 1 ... Mulțumesc tu foarte mult. E atât de frumos. Nu este un tip grozav. Nu primește o presă corectă, nu o primește. Nu este corect. Și trebuie să vă spun că sunt aici și foarte puternic aici, pentru că am un mare respect pentru Steve King și un mare respect, de asemenea, pentru Citizens United, David și toată lumea și un rezect extraordinar pentru Tea Party. De asemenea, oamenii din Iowa. Au ceva în comun. Oameni harnici ....

Pasul 3: împărțiți setul de date în cuvinte individuale

corpus = trump.split () #Display corpus print (corpus) 'puternic', 'dar', 'nu', 'puternic', 'ca', 'noi', 'Iran', 'are', ' însămânțat ',' teroare ', ...

Apoi, creați o funcție care generează diferitele perechi de cuvinte din discursuri. Pentru a economisi spațiu, vom folosi un obiect generator.

Pasul 4: Crearea perechilor de taste și a cuvintelor următoare

def make_pairs (corpus): pentru i în interval (len (corpus) - 1): randament (corpus [i], corpus [i + 1]) perechi = make_pairs (corpus)

Apoi, să inițializăm un dicționar gol pentru a stoca perechile de cuvinte.

În cazul în care primul cuvânt din pereche este deja o cheie în dicționar, adăugați următorul cuvânt potențial la lista de cuvinte care urmează cuvântului. Dar dacă cuvântul nu este o cheie, atunci creați o nouă intrare în dicționar și atribuiți cheia egală cu primul cuvânt din pereche.

Pasul 5: adăugarea dicționarului

word_dict = {} pentru word_1, word_2 în perechi: dacă word_1 în word_dict.keys (): word_dict [word_1] .append (word_2) altceva: word_dict [word_1] = [word_2]

Apoi, alegem aleatoriu un cuvânt din corpus, care va începe lanțul Markov.

Pasul 6: Construiți modelul Markov

# alegeți în mod aleatoriu primul cuvânt first_word = np.random.choice (corpus) # Alegeți primul cuvânt ca un cuvânt cu majuscule, astfel încât cuvântul ales să nu fie preluat între o propoziție în timp ce first_word.islower (): # Începeți lanțul din lanțul de cuvinte ales = [first_word] #Initialize the number of stimulated words n_words = 20

După primul cuvânt, fiecare cuvânt din lanț este eșantionat aleatoriu din lista de cuvinte care au urmat acel cuvânt specific în discursurile live ale lui Trump. Acest lucru este afișat în fragmentul de cod de mai jos:

pentru i în interval (n_words): chain.append (np.random.choice (word_dict [chain [-1]]))

Pasul 7: Predicții

În cele din urmă, să afișăm textul stimulat.

#Join returnează lanțul sub formă de șir de caractere ('.join (lanț)) Numărul de persoane incredibile. Și Hillary Clinton, are oamenii noștri și o treabă atât de grozavă. Și nu îl vom bate pe Obama

Deci, acesta este textul generat pe care l-am primit luând în considerare discursul lui Trump. S-ar putea să nu aibă mult sens, dar este suficient de bun pentru a vă face să înțelegeți cum pot fi utilizate lanțurile Markov pentru a genera automat texte.

Acum să analizăm câteva aplicații a lanțurilor Markov și a modului în care sunt utilizate pentru rezolvarea problemelor din lumea reală.

Aplicații pentru lanțul Markov

Iată o listă a aplicațiilor din lumea reală a lanțurilor Markov:

1. Google PageRank: Întregul web poate fi considerat un model Markov, în care fiecare pagină web poate fi o stare și legăturile sau referințele dintre aceste pagini pot fi considerate ca tranziții cu probabilități. Deci, practic, indiferent de pagina web pe care începeți să navigați, șansa de a ajunge la o anumită pagină web, să zicem, X este o probabilitate fixă.

2. Predicția cuvântului de tastare: Se știe că lanțurile Markov sunt folosite pentru prezicerea cuvintelor viitoare. Ele pot fi, de asemenea, utilizate în completarea automată și sugestii.

3. Simulare Subreddit: Cu siguranță ați întâlnit Reddit și ați avut o interacțiune pe unul dintre subiectele sau subreditările lor. Reddit folosește un simulator de subreditare care consumă o cantitate imensă de date care conține toate comentariile și discuțiile purtate între grupurile lor. Folosind lanțurile Markov, simulatorul produce probabilități de la un cuvânt la altul, pentru a crea comentarii și subiecte.

4. Generator de text: Lanțurile Markov sunt utilizate cel mai frecvent pentru a genera texte inexact sau pentru a produce eseuri mari și pentru a compila discursuri. Este, de asemenea, utilizat în generatoarele de nume pe care le vedeți pe web.

Acum, că știi cum să rezolvi o problemă din lumea reală folosind Markov Chains, sunt sigur că ești curios să afli mai multe. Iată o listă de bloguri care vă vor ajuta să începeți cu alte concepte statistice:

Cu aceasta, ajungem la sfârșitul acestui blog Introducere în lanțurile Markov. Dacă aveți întrebări cu privire la acest subiect, vă rugăm să lăsați un comentariu mai jos și vă vom răspunde.

Rămâneți la curent cu mai multe bloguri despre tehnologiile de trend.

Dacă sunteți în căutarea unei formări structurate online în știința datelor, edureka! are un curator special program care vă ajută să câștigați expertiză în statistici, lupte de date, analize exploratorii de date, algoritmi de învățare automată precum K-Means Clustering, arbori de decizie, pădure aleatorie, Naive Bayes. Veți învăța și conceptele Time Series, Text Mining și o introducere în Deep Learning. Noile loturi pentru acest curs încep în curând !!