Introduktion til Markov-kæder med eksempler - Markov-kæder med Python

Introduktion til Markov-kæder:

Har du nogensinde spekuleret på, hvordan Google rangerer websider? Hvis du har foretaget din forskning, skal du vide, at den bruger PageRank-algoritmen, som er baseret på ideen om Markov-kæder. Denne artikel om introduktion til Markov-kæder hjælper dig med at forstå den grundlæggende idé bag Markov-kæder, og hvordan de kan modelleres som en løsning på problemer i den virkelige verden.

Her er en liste over emner, der vil blive dækket i denne blog:

1. Hvad er en Markov-kæde?
2. Hvad er Markov-ejendommen?
3. Forståelse af Markov-kæder med et eksempel
4. Hvad er en overgangsmatrix?
5. Markov-kæde i Python
6. Markov Chain-applikationer

For at få dybdegående viden om datalogi og maskinindlæring ved hjælp af Python kan du tilmelde dig live af Edureka med support døgnet rundt og adgang til hele livet.

Hvad er en Markov-kæde?

Andrey Markov introducerede først Markov-kæder i år 1906. Han forklarede Markov-kæder som:

En stokastisk proces, der indeholder tilfældige variabler, der går fra en tilstand til en anden afhængig af visse antagelser og bestemte sandsynlighedsregler.

hvordan man bruger anaconda python

Disse tilfældige variabler overgår fra den ene til den anden til den anden, baseret på en vigtig matematisk egenskab kaldet Markov ejendom.

Dette bringer os til spørgsmålet:

Hvad er Markov-ejendommen?

Diskret tid Markov-egenskab angiver, at den beregnede sandsynlighed for, at en tilfældig proces overgår til den næste mulige tilstand kun afhænger af den aktuelle tilstand og tid, og den er uafhængig af den række stater, der gik forud for den.

Det faktum, at den næste mulige handling / tilstand for en tilfældig proces ikke afhænger af sekvensen af ​​tidligere tilstande, gør Markov-kæder som en hukommelsesfri proces, der udelukkende afhænger af den aktuelle tilstand / handling af en variabel.

Lad os udlede dette matematisk:

Lad den tilfældige proces være, {Xm, m = 0,1,2, ⋯}.

Denne proces er kun en Markov-kæde, hvis,

Markov Chain - Introduktion til Markov Chains - Edureka

for alle m, j, i, i0, i1, ⋯ im & minus1

For et endeligt antal stater, S = {0, 1, 2, ⋯, r}, kaldes dette en endelig Markov-kæde.

P (Xm + 1 = j | Xm = i) repræsenterer her overgangssandsynlighederne for overgang fra en tilstand til en anden. Her antager vi, at sandsynligheden for overgangen er uafhængig af tid.

Hvilket betyder, at P (Xm + 1 = j | Xm = i) ikke afhænger af værdien af ​​'m'. Derfor kan vi sammenfatte,

Markov Chain Formula - Introduktion til Markov Chains - Edureka

Så denne ligning repræsenterer Markov-kæden.

Lad os nu forstå, hvad præcis Markov-kæder er med et eksempel.

Markov-kædeeksempel

Før jeg giver dig et eksempel, skal vi definere, hvad en Markov-model er:

Hvad er en Markov-model?

En Markov-model er en stokastisk model, der modellerer tilfældige variabler på en sådan måde, at variablerne følger Markov-egenskaben.

Lad os nu forstå, hvordan en Markov-model fungerer med et simpelt eksempel.

Som tidligere nævnt anvendes Markov-kæder i applikationer til generering af tekst og automatisk udfyldning. I dette eksempel vil vi se på et eksempel (tilfældig) sætning og se, hvordan det kan modelleres ved hjælp af Markov-kæder.

Markov Chain Eksempel - Introduktion til Markov Chains - Edureka

Ovenstående sætning er vores eksempel, jeg ved, at det ikke giver meget mening (det behøver ikke), det er en sætning, der indeholder tilfældige ord, hvor:

1. Nøgler betegne de unikke ord i sætningen, dvs. 5 nøgler (en, to, hagl, glad, edureka)

2. Poletter betegner det samlede antal ord, dvs. 8 tokens.

Fortsat skal vi forstå hyppigheden af ​​disse ords forekomst, nedenstående diagram viser hvert ord sammen med et tal, der angiver hyppigheden af ​​dette ord.

Nøgler og frekvenser - Introduktion til Markov-kæder - Edureka

Så den venstre kolonne her angiver nøglerne, og den højre kolonne angiver frekvenserne.

Fra ovenstående tabel kan vi konkludere, at nøglen 'edureka' kommer op 4 gange så meget som enhver anden nøgle. Det er vigtigt at udlede sådanne oplysninger, fordi det kan hjælpe os med at forudsige, hvilket ord der kan forekomme på et bestemt tidspunkt. Hvis jeg gætter på det næste ord i eksempelsætningen, ville jeg gå med 'edureka', da det har størst sandsynlighed for forekomst.

Når vi taler om sandsynlighed, er en anden foranstaltning, du skal være opmærksom på vægtede fordelinger.

I vores tilfælde er den vægtede fordeling for 'edureka' 50% (4/8), fordi dens frekvens er 4 ud af de samlede 8 tokens. Resten af ​​tasterne (en, to, hagl, glade) har alle en 1/8. Chance for at forekomme (& asymp 13%).

Nu hvor vi har en forståelse af den vægtede fordeling og en idé om, hvordan specifikke ord forekommer oftere end andre, kan vi gå videre med den næste del.

Forståelse af Markov-kæder - Introduktion til Markov-kæder - Edureka

I ovenstående figur har jeg tilføjet to yderligere ord, der betegner starten og slutningen af ​​sætningen, du vil forstå, hvorfor jeg gjorde det i nedenstående afsnit.

Lad os nu også tildele frekvensen for disse taster:

Opdaterede nøgler og frekvenser - Introduktion til Markov-kæder - Edureka

Lad os nu oprette en Markov-model. Som tidligere nævnt bruges en Markov-model til at modellere tilfældige variabler i en bestemt tilstand på en sådan måde, at de fremtidige tilstande for disse variabler udelukkende afhænger af deres nuværende tilstand og ikke deres tidligere tilstande.

Så grundlæggende i en Markov-model skal vi kun overveje den nuværende tilstand for at forudsige den næste tilstand.

I nedenstående diagram kan du se, hvordan hvert token i vores sætning fører til en anden. Dette viser, at den fremtidige tilstand (næste token) er baseret på den aktuelle tilstand (nuværende token). Så dette er den mest grundlæggende regel i Markov-modellen.

Nedenstående diagram viser, at der er par tokens, hvor hvert token i parret fører til det andet i det samme par.

Markov-kædepar - Introduktion til Markov-kæder - Edureka

I nedenstående diagram har jeg oprettet en strukturel repræsentation, der viser hver nøgle med en række næste mulige tokens, den kan parre sig med.

En række Markov-kædepar - Introduktion til Markov-kæder - Edureka

For at opsummere dette eksempel skal du overveje et scenarie, hvor du bliver nødt til at danne en sætning ved hjælp af den række nøgler og tokens, vi så i ovenstående eksempel. Før vi gennemgår dette eksempel, er et andet vigtigt punkt, at vi skal specificere to indledende foranstaltninger:

1. En indledende sandsynlighedsfordeling (dvs. starttilstanden på tidspunktet = 0, ('Start' -tasten))

2. En overgangssandsynlighed for at hoppe fra en tilstand til en anden (i dette tilfælde sandsynligheden for at overgå fra det ene symbol til det andet)

Vi har defineret den vægtede fordeling i begyndelsen, så vi har sandsynlighederne og den oprindelige tilstand. Lad os nu fortsætte med eksemplet.

• Så til at begynde med det første token er [Start]

• Dernæst har vi kun et muligt token, dvs. [en]

• I øjeblikket har sætningen kun ét ord, dvs. 'en'

• Fra dette token er det næste mulige token [edureka]

• Sætningen opdateres til 'one edureka'

• Fra [edureka] kan vi flytte til et hvilket som helst af følgende tokens [to, hagl, glad, slut]

• Der er 25% chance for, at 'to' bliver valgt, dette vil muligvis resultere i dannelse af den originale sætning (en edureka to edureka hagl edureka happy edureka). Men hvis 'slut' vælges, stopper processen, og vi vil ende med at generere en ny sætning, dvs. 'en edureka'.

  hvordan man bruger pakker i java

Giv dig selv et klapp på ryggen, fordi du bare bygger en Markov-model og kørte en testkasse igennem den. For at opsummere ovenstående eksempel brugte vi grundlæggende den nuværende tilstand (nuværende ord) til at bestemme den næste tilstand (næste ord). Og det er præcis, hvad en Markov-proces er.

Det er en stokastisk proces, hvor tilfældige variabler overgår fra den ene tilstand til den anden på en sådan måde, at den fremtidige tilstand for en variabel kun afhænger af den nuværende tilstand.

Lad os tage det til næste trin og tegne Markov-modellen til dette eksempel.

Statlig overgangsdiagram - Introduktion til Markov-kæder - Edureka

Ovenstående figur er kendt som State Transition Diagram. Vi taler mere om dette i nedenstående afsnit, for nu skal du bare huske at dette diagram viser overgange og sandsynlighed fra en tilstand til en anden.

Bemærk, at hver ovale i figuren repræsenterer en nøgle, og pilene er rettet mod de mulige taster, der kan følge den. Vægtene på pilene angiver også sandsynlighed eller den vægtede fordeling af overgang fra / til de respektive stater.

Så det handlede kun om, hvordan Markov-modellen fungerer. Lad os nu prøve at forstå nogle vigtige terminologier i Markov-processen.

Hvad er en matrix for sandsynlighedsovergang?

I ovenstående afsnit diskuterede vi arbejdet med en Markov-model med et simpelt eksempel, lad os nu forstå de matematiske terminologier i en Markov-proces.

I en Markov-proces bruger vi en matrix til at repræsentere overgangssandsynlighederne fra en tilstand til en anden. Denne matrix kaldes overgangs- eller sandsynlighedsmatrix. Det er normalt betegnet med P.

Overgangsmatrix - Introduktion til Markov-kæder - Edureka

Bemærk, pij & ge0 og 'i' for alle værdier er,

Transition Matrix Formula - Introduction to Markov Chains - Edureka

Lad mig forklare dette. Forudsat at vores nuværende tilstand er 'i', skal den næste eller kommende stat være en af ​​de potentielle stater. Derfor, mens vi tager summeringen af ​​alle værdier af k, skal vi få en.

Hvad er et statsovergangsdiagram?

En Markov-model er repræsenteret af et statsovergangsdiagram. Diagrammet viser overgangene mellem de forskellige tilstande i en Markov-kæde. Lad os forstå overgangsmatrixen og tilstandsovergangsmatrixen med et eksempel.

Overgangsmatrixeksempel

Overvej en Markov-kæde med tre tilstande 1, 2 og 3 og følgende sandsynligheder:

Overgangsmatrixeksempel - Introduktion til Markov-kæder - Edureka

Eksempel på statsovergangsdiagram - Introduktion til Markov-kæder - Edureka

Ovenstående diagram repræsenterer tilstandsovergangsdiagrammet for Markov-kæden. Her er 1,2 og 3 de tre mulige tilstande, og pilene, der peger fra en tilstand til de andre stater, repræsenterer overgangssandsynlighederne pij. Når, pij = 0, betyder det, at der ikke er nogen overgang mellem tilstand 'i' og tilstand 'j'.

Nu hvor vi kend matematikken og logikken bag Markov-kæder, lad os køre en simpel demo og forstå, hvor Markov-kæder kan bruges.

Markov-kæde i Python

For at køre denne demo bruger jeg Python, så hvis du ikke kender Python, kan du gå gennem følgende blogs:

2. Sådan lærer du Python 3 fra Scratch - En begyndervejledning

Lad os nu komme i gang med kodning!

Markov Chain Text Generator

Problemformulering: At anvende Markov Property og oprette en Markov-model, der kan generere tekstsimuleringer ved at studere Donald Trumps talesæt.

Beskrivelse af datasæt: Tekstfilen indeholder en liste over taler holdt af Donald Trump i 2016.

Logik: Anvend Markov Property for at generere Donalds Trumps tale ved at overveje hvert ord, der bruges i talen, og opret en ordbog med ord, der bruges derefter for hvert ord.

binært søgningsprogram i java

Trin 1: Importer de nødvendige pakker

importer numpy som np

Trin 2: Læs datasættet

trump = open ('C: //Users//NeelTemp//Desktop//demos//speeches.txt', encoding = 'utf8'). læs () #display dataudskrivningen (trumf) TALE 1 ... Tak dig så meget. Det er så rart. Er han ikke en god fyr. Han får ikke en fair presse, han får det ikke. Det er bare ikke retfærdigt. Og jeg er nødt til at fortælle dig, at jeg er her, og meget stærkt her, fordi jeg har stor respekt for Steve King og også har stor respekt for Citizens United, David og alle, og en enorm resekt for teselskabet. Også også folket i Iowa. De har noget til fælles. Hårdtarbejdende mennesker ....

Trin 3: Opdel datasættet i individuelle ord

corpus = trump.split () #Vis corpusprint (corpus) 'stærk', 'men', 'ikke', 'kraftig', 'ligesom', 'os.', 'Iran', 'har', ' seeded ',' terror ', ...

Opret derefter en funktion, der genererer de forskellige ordpar i talerne. For at spare plads bruger vi et generatorobjekt.

Trin 4: Oprettelse af par til nøgler og opfølgende ord

def make_pairs (corpus): for i inden for rækkevidde (len (corpus) - 1): udbytte (corpus [i], corpus [i + 1]) par = make_pairs (corpus)

Lad os derefter initialisere en tom ordbog for at gemme ordparrene.

Hvis det første ord i parret allerede er en nøgle i ordbogen, skal du blot tilføje det næste mulige ord til listen over ord, der følger ordet. Men hvis ordet ikke er en nøgle, skal du oprette en ny post i ordbogen og tildele nøglen svarende til det første ord i parret.

Trin 5: Tilføjelse af ordbogen

word_dict = {} for word_1, word_2 i par: hvis word_1 i word_dict.keys (): word_dict [word_1]. tilføj (word_2) andet: word_dict [word_1] = [word_2]

Dernæst vælger vi tilfældigt et ord fra corpus, der starter Markov-kæden.

Trin 6: Byg Markov-modellen

# tilfældigt vælg det første ord first_word = np.random.choice (corpus) # Vælg det første ord som et stort bogstav, så det valgte ord ikke tages imellem en sætning, mens first_word.islower (): # Start kæden fra den valgte ordkæde = [første_ord] #Initialiser antallet af stimulerede ord n_ord = 20

Efter det første ord samples hvert ord i kæden tilfældigt fra listen over ord, der har fulgt det specifikke ord i Trumps levende taler. Dette vises i nedenstående kodestykke:

for jeg inden for rækkevidde (n_words): chain.append (np.random.choice (word_dict [chain [-1]]))

Trin 7: Forudsigelser

Lad os endelig vise den stimulerede tekst.

#Deltag returnerer kæden som en strengprint (''. Sammenføjning (kæde)) Antallet af utrolige mennesker. Og Hillary Clinton har vores folk og sådan et godt stykke arbejde. Og vi vil ikke slå Obama

Så dette er den genererede tekst, jeg fik ved at overveje Trumps tale. Det giver måske ikke meget mening, men det er godt nok til at få dig til at forstå, hvordan Markov-kæder kan bruges til automatisk at generere tekster.

Lad os nu se på nogle flere applikationer af Markov-kæder, og hvordan de bruges til at løse problemer i den virkelige verden.

Markov Chain-applikationer

Her er en liste over virkelige applikationer fra Markov-kæder:

1. Google PageRank: Hele Internettet kan betragtes som en Markov-model, hvor hver webside kan være en tilstand, og links eller referencer mellem disse sider kan betragtes som overgange med sandsynlighed. Så grundlæggende, uanset hvilken webside du begynder at surfe på, er chancen for at komme til en bestemt webside, siger, X en fast sandsynlighed.

2. Indtastning af ordforudsigelse: Markov-kæder er kendt for at blive brugt til at forudsige kommende ord. De kan også bruges til autofuldførelse og forslag.

3. Subreddit Simulation: Du er helt sikkert stødt på Reddit og haft en interaktion på en af ​​deres tråde eller underreddits. Reddit bruger en subreddit-simulator, der bruger en enorm mængde data, der indeholder alle de kommentarer og diskussioner, der holdes på tværs af deres grupper. Ved at bruge Markov-kæder producerer simulatoren ord-til-ord sandsynligheder for at skabe kommentarer og emner.

4. Tekstgenerator: Markov-kæder bruges mest til at generere dummy-tekster eller producere store essays og kompilere taler. Det bruges også i de navnegeneratorer, som du ser på internettet.

Nu hvor du ved, hvordan du løser et virkeligt problem ved hjælp af Markov Chains, er jeg sikker på, at du er nysgerrig efter at lære mere. Her er en liste over blogs, der hjælper dig med at komme i gang med andre statistiske begreber:

Med dette kommer vi til slutningen af ​​denne introduktion til Markov Chains-blog. Hvis du har spørgsmål vedrørende dette emne, bedes du give en kommentar nedenfor, så vender vi tilbage til dig.

Hold øje med flere blogs om de mest populære teknologier.

Hvis du leder efter online struktureret træning i datalogi, edureka! har en specielt kurateret program, der hjælper dig med at få ekspertise inden for statistik, datavridning, sonderende dataanalyse, maskinindlæringsalgoritmer som K-Means Clustering, beslutningstræer, Random Forest, Naive Bayes. Du lærer også begreberne Time Series, Text Mining og en introduktion til Deep Learning. Nye partier til dette kursus starter snart !!