Introduktion till Markov-kedjor med exempel - Markov-kedjor med Python

Introduktion till Markov-kedjor:

Har du någonsin undrat hur Google rankar webbsidor? Om du har gjort din forskning måste du veta att den använder PageRank-algoritmen som bygger på idén om Markov-kedjor. Den här artikeln om introduktion till Markov-kedjor hjälper dig att förstå grundidén bakom Markov-kedjor och hur de kan modelleras som en lösning på verkliga problem.

Här är en lista med ämnen som kommer att behandlas i den här bloggen:

1. Vad är en Markov-kedja?
2. Vad är Markov-egenskapen?
3. Förstå Markov-kedjor med ett exempel
4. Vad är en övergångsmatris?
5. Markov Chain In Python
6. Markov Chain-applikationer

För att få fördjupad kunskap om datavetenskap och maskininlärning med Python kan du registrera dig för live av Edureka med support dygnet runt och livstidsåtkomst.

Vad är en Markov-kedja?

Andrey Markov introducerade först Markov-kedjor år 1906. Han förklarade Markov-kedjor som:

En stokastisk process som innehåller slumpmässiga variabler som övergår från ett tillstånd till ett annat beroende på vissa antaganden och bestämda probabilistiska regler.

Dessa slumpmässiga variabler övergår från en till stat till en annan, baserat på en viktig matematisk egenskap som kallas Markov Property.

Detta leder oss till frågan:

Vad är Markov-egenskapen?

Diskret tidsmarkovegenskap anger att den beräknade sannolikheten för att en slumpmässig process övergår till nästa möjliga tillstånd endast är beroende av det aktuella tillståndet och tiden och det är oberoende av serien av tillstånd som föregick det.

Det faktum att nästa möjliga åtgärd / tillstånd för en slumpmässig process inte beror på sekvensen av tidigare tillstånd, gör Markov-kedjor som en minnesfri process som enbart beror på det aktuella tillståndet / åtgärden hos en variabel.

Låt oss härleda detta matematiskt:

Låt den slumpmässiga processen vara, {Xm, m = 0,1,2, ⋯}.

Denna process är en Markov-kedja endast om,

Markov Chain - Introduktion till Markov Chains - Edureka

för alla m, j, i, i0, i1, ⋯ im & minus1

För ett begränsat antal tillstånd, S = {0, 1, 2, ⋯, r}, kallas detta en ändlig Markov-kedja.

P (Xm + 1 = j | Xm = i) representerar här övergångssannolikheterna för övergång från ett tillstånd till ett annat. Här antar vi att övergångssannolikheterna är oberoende av tid.

Vilket innebär att P (Xm + 1 = j | Xm = i) inte beror på värdet på 'm'. Därför kan vi sammanfatta,

Markov Chain Formula - Introduktion till Markov Chains - Edureka

Så denna ekvation representerar Markov-kedjan.

Låt oss nu förstå exakt vilka Markov-kedjor är med ett exempel.

Markov Chain Exempel

Innan jag ger dig ett exempel, låt oss definiera vad en Markov-modell är:

Vad är en Markov-modell?

En Markov-modell är en stokastisk modell som modellerar slumpmässiga variabler på ett sådant sätt att variablerna följer Markov-egenskapen.

Låt oss nu förstå hur en Markov-modell fungerar med ett enkelt exempel.

Som tidigare nämnts används Markov-kedjor i applikationer för textgenerering och automatisk komplettering. För detta exempel tar vi en titt på ett exempel (slumpmässig) mening och ser hur det kan modelleras med hjälp av Markov-kedjor.

Markov Chain Exempel - Introduktion till Markov Chains - Edureka

Ovanstående mening är vårt exempel, jag vet att det inte ger mycket mening (det behöver inte), det är en mening som innehåller slumpmässiga ord, där:

1. Nycklar beteckna de unika orden i meningen, dvs 5 tangenter (en, två, hagel, glad, edureka)

2. Poletter betecknar det totala antalet ord, dvs. 8 tokens.

Framåt måste vi förstå frekvensen av dessa ord, nedanstående diagram visar varje ord tillsammans med ett nummer som anger frekvensen för det ordet.

Nycklar och frekvenser - Introduktion till Markov-kedjor - Edureka

Så den vänstra kolumnen här betecknar tangenterna och den högra kolumnen betecknar frekvenserna.

Från ovanstående tabell kan vi dra slutsatsen att nyckeln 'edureka' kommer upp fyra gånger så mycket som någon annan nyckel. Det är viktigt att härleda sådan information eftersom den kan hjälpa oss att förutsäga vilket ord som kan förekomma vid en viss tidpunkt. Om jag skulle gissa om nästa ord i exempelmeningen skulle jag gå med 'edureka' eftersom det har högsta sannolikhet för förekomst.

På tal om sannolikhet är en annan åtgärd du måste vara medveten om viktade fördelningar.

I vårt fall är den viktade fördelningen för 'edureka' 50% (4/8) eftersom dess frekvens är 4, av de totala 8 tokens. Resten av tangenterna (en, två, hagel, glad) har alla en 1/8 chans att inträffa (& asymp 13%).

Nu när vi har förståelse för den viktade fördelningen och en uppfattning om hur specifika ord förekommer oftare än andra, kan vi gå vidare med nästa del.

Förstå Markov-kedjor - Introduktion till Markov-kedjor - Edureka

I figuren ovan har jag lagt till ytterligare två ord som betecknar början och slutet av meningen, du kommer att förstå varför jag gjorde det i avsnittet nedan.

Låt oss nu också tilldela frekvensen för dessa tangenter:

Uppdaterade nycklar och frekvenser - Introduktion till Markov-kedjor - Edureka

Låt oss nu skapa en Markov-modell. Som tidigare nämnts används en Markov-modell för att modellera slumpmässiga variabler i ett visst tillstånd på ett sådant sätt att de framtida tillstånden för dessa variabler enbart beror på deras nuvarande tillstånd och inte deras tidigare tillstånd.

Så i princip i en Markov-modell, för att förutsäga nästa tillstånd, måste vi bara överväga det nuvarande tillståndet.

I nedanstående diagram kan du se hur varje symbol i vår mening leder till en annan. Detta visar att det framtida tillståndet (nästa token) baseras på det aktuella tillståndet (nuvarande token). Så detta är den mest grundläggande regeln i Markov-modellen.

Nedanstående diagram visar att det finns par tokens där varje token i paret leder till den andra i samma par.

Markov Chain Pairs - Introduction to Markov Chains - Edureka

I nedanstående diagram har jag skapat en strukturell representation som visar varje nyckel med en uppsättning nästa möjliga token som den kan para ihop med.

En rad Markov-kedjepar - Introduktion till Markov-kedjor - Edureka

För att sammanfatta detta exempel, överväg ett scenario där du måste bilda en mening med hjälp av den uppsättning nycklar och tokens vi såg i exemplet ovan. Innan vi går igenom detta exempel är en annan viktig punkt att vi måste ange två initiala åtgärder:

1. En initial sannolikhetsfördelning (dvs. starttillståndet vid tiden = 0, ('Start' -tangenten))

2. En övergångssannolikhet att hoppa från ett tillstånd till ett annat (i det här fallet sannolikheten för att övergå från en symbol till en annan)

Vi har definierat den viktade fördelningen i början av sig själv, så vi har sannolikheterna och det ursprungliga tillståndet, nu går vi vidare med exemplet.

java konvertera sträng till dags dato

• Så till att börja med den första token är [Start]

• Därefter har vi bara en möjlig token, dvs. [en]

• För närvarande har meningen bara ett ord, dvs. 'ett'

• Från denna token är nästa möjliga token [edureka]

• Meningen uppdateras till 'one edureka'

• Från [edureka] kan vi flytta till något av följande symboler [två, hagel, lycklig, slut]

• Det finns 25% chans att 'två' blir plockade, detta skulle möjligen leda till att den ursprungliga meningen bildas (en edureka två edureka hagel edureka glad edureka). Men om 'slut' väljs slutar processen och vi kommer att generera en ny mening, dvs. 'en edureka'.

Ge dig själv ett klapp på ryggen eftersom du bara bygger en Markov-modell och körde ett testfall genom den. För att sammanfatta exemplet ovan använde vi i princip nuvarande tillstånd (nuvarande ord) för att bestämma nästa tillstånd (nästa ord). Och det är precis vad en Markov-process är.

Det är en stokastisk process där slumpmässiga variabler övergår från ett tillstånd till det andra på ett sådant sätt att det framtida tillståndet för en variabel endast beror på det aktuella tillståndet.

Låt oss ta det till nästa steg och dra fram Markov-modellen för detta exempel.

Statligt övergångsdiagram - Introduktion till Markov-kedjor - Edureka

Ovanstående figur är känd som State Transition Diagram. Vi kommer att prata mer om detta i avsnittet nedan, för nu är det bara att komma ihåg att det här diagrammet visar övergångar och sannolikhet från ett tillstånd till ett annat.

Observera att varje oval i figuren representerar en nyckel och pilarna riktas mot de möjliga tangenterna som kan följa den. Även vikterna på pilarna betecknar sannolikhet eller den viktade fördelningen av övergång från / till respektive tillstånd.

Så det handlade bara om hur Markov-modellen fungerar. Låt oss nu försöka förstå några viktiga terminologier i Markov-processen.

Vad är en övergångssannolikhetsmatris?

I avsnittet ovan diskuterade vi arbetet med en Markov-modell med ett enkelt exempel. Låt oss nu förstå de matematiska terminologierna i en Markov-process.

I en Markov-process använder vi en matris för att representera övergångssannolikheterna från ett tillstånd till ett annat. Denna matris kallas övergångs- eller sannolikhetsmatris. Det betecknas vanligtvis av P.

Transition Matrix - Introduction to Markov Chains - Edureka

Observera, pij & ge0 och 'i' för alla värden är,

Transition Matrix Formula - Introduction to Markov Chains - Edureka

Låt mig förklara detta. Förutsatt att vårt nuvarande tillstånd är ”i” måste nästa eller kommande tillstånd vara en av de potentiella staterna. Därför, medan vi tar en summering av alla värden på k, måste vi få en.

Vad är ett statligt övergångsdiagram?

En Markov-modell representeras av ett statligt övergångsdiagram. Diagrammet visar övergångarna mellan de olika tillstånden i en Markov-kedja. Låt oss förstå övergångsmatrisen och tillståndsövergångsmatrisen med ett exempel.

Exempel på övergångsmatris

Tänk på en Markov-kedja med tre tillstånd 1, 2 och 3 och följande sannolikheter:

Exempel på övergångsmatris - Introduktion till Markov-kedjor - Edureka

Exempel på statligt övergångsdiagram - Introduktion till Markov-kedjor - Edureka

Ovanstående diagram representerar tillståndsövergångsdiagrammet för Markov-kedjan. Här är 1,2 och 3 de tre möjliga tillstånden, och pilarna som pekar från ett tillstånd till andra tillstånd representerar övergångssannolikheterna pij. När, pij = 0, betyder det att det inte finns någon övergång mellan tillstånd 'i' och tillstånd 'j'.

Nu när vi känna matematiken och logiken bakom Markov-kedjor, låt oss köra en enkel demo och förstå var Markov-kedjor kan användas.

Markov Chain In Python

För att köra denna demo använder jag Python, så om du inte känner till Python kan du gå igenom följande bloggar:

2. Hur man lär sig Python 3 från Scratch - En nybörjarguide

Låt oss börja med kodning!

Markov Chain Text Generator

Problemförklaring: Att tillämpa Markov Property och skapa en Markov-modell som kan generera textsimuleringar genom att studera Donald Trumps taldatauppsättning.

Datauppsättningsbeskrivning: Textfilen innehåller en lista med tal som hölls av Donald Trump 2016.

Logik: Använd Markov Property för att generera Donalds Trumps tal genom att överväga varje ord som används i talet och skapa för varje ord en ordlista med ord som används därefter.

Steg 1: Importera nödvändiga paket

importera numpy som np

Steg 2: Läs datamängden

trump = open ('C: //Users//NeelTemp//Desktop//demos//speeches.txt', encoding = 'utf8'). read () #display the data print (trump) SPEECH 1 ... Thank du så mycket. Det är så trevligt. Är han inte en bra kille. Han får inte en rättvis press han inte får det. Det är inte rättvist. Och jag måste säga att jag är här, och mycket starkt här, för jag har stor respekt för Steve King och har också stor respekt för Citizens United, David och alla, och en enorm resekt för Tea Party. Också folket i Iowa. De har något gemensamt. Hårt arbetande människor ....

Steg 3: Dela upp datauppsättningen i enskilda ord

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

Skapa sedan en funktion som genererar de olika paren av ord i talen. För att spara utrymme använder vi ett generatorobjekt.

Steg 4: Skapa par till nycklar och uppföljningsord

dataabstraktion i c ++

def make_pairs (corpus): för jag inom räckvidd (len (corpus) - 1): avkastning (corpus [i], corpus [i + 1]) par = make_pairs (corpus)

Låt oss sedan initialisera en tom ordbok för att lagra ordparen.

Om det första ordet i paret redan är en nyckel i ordboken, lägg bara till nästa potentiella ord i listan över ord som följer ordet. Men om ordet inte är en nyckel skapar du en ny post i ordboken och tilldelar nyckeln lika med det första ordet i paret.

Steg 5: Lägga till ordlistan

word_dict = {} för word_1, word_2 i par: om word_1 i word_dict.keys (): word_dict [word_1]. lägg till (word_2) annat: word_dict [word_1] = [word_2]

Därefter väljer vi slumpmässigt ett ord från corpus som startar Markov-kedjan.

Steg 6: Bygg Markov-modellen

# slumpmässigt välj det första ordet först_ord = np.random.choice (corpus) # Välj det första ordet som ett stort ord så att det plockade ordet inte tas mellan en mening medan first_word.islower (): den valda ordkedjan = [första_ord] # Initiera antalet stimulerade ord n_ord = 20

Efter det första ordet samplas varje ord i kedjan slumpmässigt från listan över ord som har följt det specifika ordet i Trumps levande tal. Detta visas i kodavsnittet nedan:

för jag inom intervallet (n_words): chain.append (np.random.choice (word_dict [chain [-1]]))

Steg 7: Förutsägelser

Slutligen, låt oss visa den stimulerade texten.

#Join returnerar kedjan som ett strängtryck (''. Gå med (kedja)) Antalet otroliga människor. Och Hillary Clinton har vårt folk och ett så bra jobb. Och vi kommer inte att slå Obama

Så det här är den genererade texten jag fick genom att överväga Trumps tal. Det är kanske inte så vettigt men det är tillräckligt bra för att du ska förstå hur Markov-kedjor kan användas för att automatiskt generera texter.

Låt oss nu titta på några fler applikationer av Markov-kedjor och hur de används för att lösa verkliga problem.

Markov Chain-applikationer

Här är en lista över verkliga applikationer från Markov-kedjor:

1. Google PageRank: Hela webben kan ses som en Markov-modell, där varje webbsida kan vara ett tillstånd och länkar eller referenser mellan dessa sidor kan betraktas som övergångar med sannolikhet. Så i princip, oavsett vilken webbsida du börjar surfa på, är chansen att komma till en viss webbsida, säg X, en fast sannolikhet.

2. Skriva ordförutsägelse: Markov-kedjor är kända för att användas för att förutsäga kommande ord. De kan också användas för automatisk komplettering och förslag.

3. Subreddit-simulering: Visst har du stött på Reddit och haft en interaktion på en av deras trådar eller subreddits. Reddit använder en subreddit-simulator som förbrukar en enorm mängd data som innehåller alla kommentarer och diskussioner som hålls i deras grupper. Genom att använda Markov-kedjor producerar simulatorn ord-till-ord-sannolikheter för att skapa kommentarer och ämnen.

4. Textgenerator: Markov-kedjor används oftast för att skapa dummytexter eller producera stora uppsatser och sammanställa tal. Det används också i de namngeneratorer som du ser på webben.

Nu när du vet hur du löser ett verkligt problem med Markov Chains är jag säker på att du är nyfiken på att lära dig mer. Här är en lista med bloggar som hjälper dig att komma igång med andra statistiska begrepp:

Med detta kommer vi till slutet av denna introduktion till Markov Chains-bloggen. Om du har frågor angående detta ämne, vänligen lämna en kommentar nedan så återkommer vi till dig.

Håll koll på fler bloggar om trendteknologierna.

Om du letar efter strukturerad utbildning online i datavetenskap, edureka! har en speciellt kuraterad program som hjälper dig att skaffa dig expertis inom statistik, datavridning, undersökande dataanalys, maskininlärningsalgoritmer som K-Means Clustering, Decision Trees, Random Forest, Naive Bayes. Du lär dig också begreppen Time Series, Text Mining och en introduktion till Deep Learning. Nya satser för denna kurs börjar snart !!