Introduksjon til Markov-kjeder med eksempler - Markov-kjeder med python

Introduksjon til Markov-kjeder:

Har du noen gang lurt på hvordan Google rangerer nettsider? Hvis du har gjort undersøkelsene dine, må du vite at den bruker PageRank-algoritmen som er basert på ideen om Markov-kjeder. Denne artikkelen om Introduksjon til Markov-kjeder vil hjelpe deg med å forstå den grunnleggende ideen bak Markov-kjeder og hvordan de kan modelleres som en løsning på virkelige problemer.

Her er en liste over emner som vil bli dekket i denne bloggen:

1. Hva er en Markov-kjede?
2. Hva er Markov-eiendommen?
3. Forstå Markov-kjeder med et eksempel
4. Hva er en overgangsmatrise?
5. Markov Chain In Python
6. Markov Chain-applikasjoner

For å få grundig kunnskap om datavitenskap og maskinlæring ved hjelp av Python, kan du registrere deg for live av Edureka med 24/7 support og levetidstilgang.

Hva er en Markov-kjede?

Andrey Markov introduserte første gang Markov-kjeder i år 1906. Han forklarte Markov-kjeder som:

En stokastisk prosess som inneholder tilfeldige variabler, som går fra en tilstand til en annen, avhengig av visse antagelser og bestemte sannsynlighetsregler.

Disse tilfeldige variabler overgang fra en til stat til den andre, basert på en viktig matematisk egenskap som kalles Markov Eiendom.

Dette bringer oss til spørsmålet:

Hva er Markov-eiendommen?

Diskret tid Markov-egenskap sier at den beregnede sannsynligheten for at en tilfeldig prosess går over til neste mulige tilstand, bare er avhengig av den nåværende tilstanden og tiden, og den er uavhengig av serien av stater som gikk foran den.

Det faktum at den neste mulige handlingen / tilstanden til en tilfeldig prosess ikke avhenger av sekvensen av tidligere tilstander, gjør Markov-kjeder som en minneløs prosess som bare avhenger av den aktuelle tilstanden / handlingen til en variabel.

La oss utlede dette matematisk:

La den tilfeldige prosessen være, {Xm, m = 0,1,2, ⋯}.

Denne prosessen er en Markov-kjede bare hvis,

Markov Chain - Introduksjon til Markov Chains - Edureka

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

For et endelig antall stater, S = {0, 1, 2, ⋯, r}, kalles dette en endelig Markov-kjede.

P (Xm + 1 = j | Xm = i) representerer her overgangssannsynlighetene for overgang fra en tilstand til en annen. Her antar vi at overgangssannsynlighetene er uavhengige av tid.

Noe som betyr at P (Xm + 1 = j | Xm = i) ikke er avhengig av verdien til ‘m’. Derfor kan vi oppsummere,

Markov Chain Formula - Introduksjon til Markov Chains - Edureka

Så denne ligningen representerer Markov-kjeden.

La oss nå forstå nøyaktig hva Markov-kjeder er med et eksempel.

Markov Chain Eksempel

Før vi gir deg et eksempel, la oss definere hva en Markov-modell er:

Hva er en Markov-modell?

En Markov-modell er en stokastisk modell som modellerer tilfeldige variabler på en slik måte at variablene følger Markov-egenskapen.

La oss nå forstå hvordan en Markov-modell fungerer med et enkelt eksempel.

Som nevnt tidligere, brukes Markov-kjeder i applikasjoner for generering av tekst og autofullføring. For dette eksemplet ser vi på et eksempel (tilfeldig) setning og ser hvordan det kan modelleres ved hjelp av Markov-kjeder.

Markov Chain Eksempel - Introduksjon til Markov Chains - Edureka

Ovennevnte setning er vårt eksempel, jeg vet at det ikke gir mye mening (det trenger ikke), det er en setning som inneholder tilfeldige ord, der:

1. Nøkler betegne de unike ordene i setningen, dvs. 5 nøkler (en, to, hagl, lykkelig, edureka)

2. Tokens betegner det totale antallet ord, dvs. 8 tokens.

Fortsatt må vi forstå hyppigheten av forekomst av disse ordene, diagrammet nedenfor viser hvert ord sammen med et tall som angir frekvensen til dette ordet.

Nøkler og frekvenser - Introduksjon til Markov-kjeder - Edureka

Så venstre kolonne her betegner nøklene og høyre kolonne betegner frekvensene.

Fra tabellen ovenfor kan vi konkludere med at nøkkelen ‘edureka’ kommer opp 4 ganger så mye som enhver annen nøkkel. Det er viktig å utlede slik informasjon fordi det kan hjelpe oss med å forutsi hvilket ord som kan forekomme på et bestemt tidspunkt. Hvis jeg skulle gjette meg om neste ord i eksempelsetningen, ville jeg gått med ‘edureka’ siden det har størst sannsynlighet for forekomst.

Når vi snakker om sannsynlighet, er et annet tiltak du må være klar over vektede fordelinger.

I vårt tilfelle er den vektede fordelingen for ‘edureka’ 50% (4/8) fordi frekvensen er 4, av de totalt 8 tokens. Resten av tastene (en, to, hagl, lykkelige) har alle en 1/8 sjanse for å oppstå (& asymp 13%).

Nå som vi har forståelse for den vektede fordelingen og en ide om hvordan spesifikke ord forekommer oftere enn andre, kan vi gå videre med neste del.

Forstå Markov Chains - Introduksjon til Markov Chains - Edureka

I figuren ovenfor har jeg lagt til to ekstra ord som betegner starten og slutten av setningen. Du vil forstå hvorfor jeg gjorde dette i avsnittet nedenfor.

La oss nå tildele frekvensen for disse tastene også:

Oppdaterte nøkler og frekvenser - Introduksjon til Markov-kjeder - Edureka

La oss nå lage en Markov-modell. Som nevnt tidligere brukes en Markov-modell til å modellere tilfeldige variabler i en bestemt tilstand på en slik måte at de fremtidige tilstandene til disse variablene bare avhenger av deres nåværende tilstand og ikke deres tidligere tilstander.

Så i utgangspunktet i en Markov-modell, for å forutsi neste tilstand, må vi bare vurdere den nåværende tilstanden.

I diagrammet nedenfor kan du se hvordan hvert token i setningen vår fører til en annen. Dette viser at den fremtidige tilstanden (neste token) er basert på den nåværende tilstanden (nåværende token). Så dette er den mest grunnleggende regelen i Markov-modellen.

Fibonacci-serie c ++

Diagrammet nedenfor viser at det er par tokens der hvert token i paret fører til det andre i samme par.

Markov Chain Pairs - Introduksjon til Markov Chains - Edureka

I diagrammet nedenfor har jeg laget en strukturell representasjon som viser hver nøkkel med en rekke neste mulige tokens den kan kobles sammen med.

En rekke Markov Chain Pairs - Introduksjon til Markov Chains - Edureka

For å oppsummere dette eksemplet, vurder et scenario hvor du må danne en setning ved å bruke matrisen med nøkler og tokens vi så i eksemplet ovenfor. Før vi går gjennom dette eksemplet, er et annet viktig poeng at vi må spesifisere to innledende tiltak:

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

2. En overgangssannsynlighet for å hoppe fra en tilstand til en annen (i dette tilfellet sannsynligheten for å gå fra det ene token til det andre)

Vi har definert den vektede fordelingen i begynnelsen, så vi har sannsynlighetene og den opprinnelige tilstanden. La oss nå fortsette med eksemplet.

• Så til å begynne med det første tokenet er [Start]

• Deretter har vi bare ett mulig token, dvs. [en]

• For tiden har setningen bare ett ord, dvs. 'ett'

• Fra dette symbolet er det neste mulige symbolet [edureka]

• Setningen er oppdatert til 'one edureka'

• Fra [edureka] kan vi flytte til et av følgende tokens [to, hagl, lykkelig, slutt]

• Det er 25% sjanse for at ‘to’ blir plukket, dette kan muligens resultere i å danne den originale setningen (en edureka to edureka hagl edureka happy edureka). Men hvis 'end' er valgt, stopper prosessen, og vi vil ende opp med å generere en ny setning, dvs. 'one edureka'.

Gi deg selv et klapp på ryggen fordi du bare bygger en Markov-modell og kjørte en testkasse gjennom den. For å oppsummere eksemplet ovenfor brukte vi i utgangspunktet nåværende tilstand (nåværende ord) for å bestemme neste tilstand (neste ord). Og det er akkurat hva en Markov-prosess er.

Det er en stokastisk prosess der tilfeldige variabler overgår fra en tilstand til den andre på en slik måte at den fremtidige tilstanden til en variabel bare avhenger av den nåværende tilstanden.

La oss ta det til neste trinn og tegne Markov-modellen for dette eksemplet.

Statlig overgangsdiagram - Introduksjon til Markov-kjeder - Edureka

Ovenstående figur er kjent som State Transition Diagram. Vi vil snakke mer om dette i delen nedenfor, for nå bare husk at dette diagrammet viser overganger og sannsynlighet fra en tilstand til en annen.

Legg merke til at hver ovale i figuren representerer en nøkkel, og pilene er rettet mot de mulige tastene som kan følge den. Vektene på pilene betegner også sannsynlighet eller vektet fordeling av overgang fra / til respektive stater.

Så alt handlet om hvordan Markov-modellen fungerer. La oss nå prøve å forstå noen viktige terminologier i Markov-prosessen.

Hva er en overgangssannsynlighetsmatrise?

I avsnittet ovenfor diskuterte vi arbeidet med en Markov-modell med et enkelt eksempel. La oss nå forstå de matematiske terminologiene i en Markov-prosess.

I en Markov-prosess bruker vi en matrise for å representere overgangssannsynlighetene fra en tilstand til en annen. Denne matrisen kalles overgangs- eller sannsynlighetsmatrisen. Det er vanligvis betegnet av P.

Transition Matrix - Introduction to Markov Chains - Edureka

Merk, pij & ge0, og ‘i’ for alle verdier er,

Transition Matrix Formula - Introduction to Markov Chains - Edureka

La meg forklare dette. Forutsatt at vår nåværende tilstand er ‘i’, må den neste eller kommende staten være en av de potensielle statene. Derfor, mens vi tar summeringen av alle verdier av k, må vi få en.

Hva er et statlig overgangsdiagram?

En Markov-modell er representert med et statlig overgangsdiagram. Diagrammet viser overgangene mellom de forskjellige tilstandene i en Markov-kjede. La oss forstå overgangsmatrisen og tilstandsovergangsmatrisen med et eksempel.

Overgangsmatriseeksempel

Tenk på en Markov-kjede med tre tilstander 1, 2 og 3 og følgende sannsynligheter:

Overgangsmatriseeksempel - Introduksjon til Markov-kjeder - Edureka

Eksempel på statlig overgangsdiagram - Introduksjon til Markov-kjeder - Edureka

Ovenstående diagram representerer tilstandsovergangsdiagrammet for Markov-kjeden. Her er 1,2 og 3 de tre mulige tilstandene, og pilene som peker fra en tilstand til de andre statene representerer overgangssannsynlighetene pij. Når, pij = 0, betyr det at det ikke er noen overgang mellom tilstand ‘i’ og tilstand ‘j’.

Nå som vi kjenn matematikken og logikken bak Markov-kjeder, la oss kjøre en enkel demo og forstå hvor Markov-kjeder kan brukes.

Markov Chain In Python

For å kjøre denne demoen bruker jeg Python, så hvis du ikke kjenner Python, kan du gå gjennom følgende blogger:

2. Hvordan lære Python 3 fra Scratch - en nybegynnerveiledning

La oss komme i gang med koding!

Markov Chain Text Generator

Problemstilling: Å bruke Markov Property og lage en Markov-modell som kan generere tekstsimuleringer ved å studere Donald Trumps talesett.

Beskrivelse av datasett: Tekstfilen inneholder en liste over taler holdt av Donald Trump i 2016.

Logikk: Bruk Markov Property for å generere Donalds Trumps tale ved å vurdere hvert ord som brukes i talen, og opprett en ordbok med ord som blir brukt neste for hvert ord.

Trinn 1: Importer de nødvendige pakkene

importer nummen som np

Trinn 2: Les datasettet

trump = open ('C: //Users//NeelTemp//Desktop//demos//speeches.txt', encoding = 'utf8'). read () #display the data print (trump) SPEECH 1 ... Thank deg så mye. Det er så fint. Er han ikke en flott fyr? Han får ikke en rettferdig presse, han får det ikke. Det er bare ikke rettferdig. Og jeg må si deg at jeg er her, og veldig sterkt her, fordi jeg har stor respekt for Steve King og har også stor respekt for Citizens United, David og alle, og enorm respekt for teselskapet. Også også folket i Iowa. De har noe til felles. Hardtarbeidende mennesker ....

Trinn 3: Del datasettet i individuelle ord

corpus = trump.split () #Display corpus print (corpus) 'kraftig', 'men', 'ikke', 'kraftig', 'som', 'oss.', 'Iran', 'har', ' seeded ',' terror ', ...

Deretter oppretter du en funksjon som genererer de forskjellige ordparene i talene. For å spare plass bruker vi et generatorobjekt.

Trinn 4: Opprette par til nøkler og oppfølgingsordene

def make_pairs (corpus): for i i rekkevidde (len (corpus) - 1): yield (corpus [i], corpus [i + 1]) par = make_pairs (corpus)

La oss deretter initialisere en tom ordbok for å lagre ordparene.

I tilfelle det første ordet i paret allerede er en nøkkel i ordboken, er det bare å legge til det neste potensielle ordet i listen over ord som følger ordet. Men hvis ordet ikke er en nøkkel, så opprett en ny oppføring i ordboken og tilordne nøkkelen lik det første ordet i paret.

Trinn 5: Legge til ordboken

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

Deretter velger vi tilfeldig et ord fra corpus, som vil starte Markov-kjeden.

Trinn 6: Bygg Markov-modellen

# tilfeldig velg det første ordet first_word = np.random.choice (corpus) # Plukk det første ordet som et stort ord slik at det valgte ordet ikke blir tatt mellom en setning mens first_word.islower (): # Start kjeden fra den valgte ordkjeden = [første_ord] #Initialiser antall stimulerte ord n_ord = 20

Etter det første ordet blir hvert ord i kjeden stikkprøver fra listen over ord som har fulgt det spesifikke ordet i Trumps levende taler. Dette vises i kodebiten nedenfor:

for jeg innen rekkevidde (n_words): chain.append (np.random.choice (word_dict [chain [-1]]))

Trinn 7: Spådommer

Til slutt, la oss vise den stimulerte teksten.

#Join returnerer kjeden som en strengutskrift (''. Join (chain)) Antall utrolige mennesker. Og Hillary Clinton har vårt folk, og en så god jobb. Og vi vil ikke slå Obama

Så dette er den genererte teksten jeg fikk ved å vurdere Trumps tale. Det gir ikke mye mening, men det er bra nok til at du forstår hvordan Markov-kjeder kan brukes til å automatisk generere tekster.

La oss nå se på noen flere applikasjoner av Markov-kjeder og hvordan de brukes til å løse virkelige problemer.

Markov Chain-applikasjoner

Her er en liste over virkelige applikasjoner fra Markov-kjeder:

1. Google PageRank: Hele nettet kan betraktes som en Markov-modell, der hver webside kan være en tilstand og lenkene eller referansene mellom disse sidene kan betraktes som overganger med sannsynlighet. Så i utgangspunktet, uavhengig av hvilken webside du begynner å surfe på, er sjansen for å komme til en bestemt webside, for eksempel, X en fast sannsynlighet.

2. Skrive ordforutsigelse: Markov-kjeder er kjent for å brukes til å forutsi kommende ord. De kan også brukes til autofullføring og forslag.

3. Subreddit-simulering: Du har sikkert kommet over Reddit og hatt en interaksjon på en av trådene eller underreddene deres. Reddit bruker en subreddit-simulator som bruker en enorm mengde data som inneholder alle kommentarene og diskusjonene som holdes i gruppene deres. Ved å benytte seg av Markov-kjeder produserer simulatoren ord-til-ord-sannsynlighet for å lage kommentarer og emner.

4. Tekstgenerator: Markov-kjeder brukes oftest til å generere dummytekster eller produsere store essays og kompilere taler. Den brukes også i navnegeneratorene som du ser på nettet.

Nå som du vet hvordan du kan løse et reelt problem ved å bruke Markov Chains, er jeg sikker på at du er nysgjerrig på å lære mer. Her er en liste over blogger som hjelper deg med å komme i gang med andre statistiske konsepter:

Med dette kommer vi til slutten av denne introduksjonen til Markov Chains-bloggen. Hvis du har spørsmål angående dette emnet, kan du legge igjen en kommentar nedenfor, så kommer vi tilbake til deg.

Følg med for flere blogger om trendteknologiene.

Hvis du er ute etter online strukturert opplæring i Data Science, edureka! har en spesielt kuratert program som hjelper deg med å skaffe deg kompetanse innen statistikk, dataknusing, utforskende dataanalyse, maskinlæringsalgoritmer som K-Means Clustering, Decision Trees, Random Forest, Naive Bayes. Du lærer også begrepene Time Series, Text Mining og en introduksjon til Deep Learning. Nye batcher for dette kurset starter snart !!