Inleiding tot Markov-ketens met voorbeelden - Markov-ketens met Python

Inleiding tot Markov-ketens:

Heeft u zich ooit afgevraagd hoe Google webpagina's rangschikt? Als u uw onderzoek heeft gedaan, moet u weten dat het het PageRank-algoritme gebruikt dat is gebaseerd op het idee van Markov-ketens. Dit artikel over Inleiding tot Markov-ketens zal je helpen het basisidee achter Markov-ketens te begrijpen en hoe ze kunnen worden gemodelleerd als een oplossing voor echte problemen.

Hier is een lijst met onderwerpen die aan bod komen in deze blog:

model view controller in java

1. Wat is een Markov-ketting?
2. Wat is het eigendom van Markov?
3. Markov-ketens begrijpen met een voorbeeld
4. Wat is een transitiematrix?
5. Markov-ketting in Python
6. Markov-kettingtoepassingen

Om diepgaande kennis te krijgen van Data Science en Machine Learning met Python, kun je je live inschrijven door Edureka met 24/7 ondersteuning en levenslange toegang.

Wat is een Markov-ketting?

Andrey Markov introduceerde Markov-ketens voor het eerst in het jaar 1906. Hij legde Markov-ketens uit als:

Een stochastisch proces dat willekeurige variabelen bevat en van de ene toestand naar de andere overgaat, afhankelijk van bepaalde aannames en welomlijnde probabilistische regels.

Deze willekeurige variabelen gaan over van de ene naar de andere staat, gebaseerd op een belangrijke wiskundige eigenschap genaamd Markov eigendom.

Dit brengt ons bij de vraag:

Wat is het eigendom van Markov?

Discrete tijd Markov Property stelt dat de berekende kans dat een willekeurig proces overgaat naar de volgende mogelijke toestand alleen afhankelijk is van de huidige toestand en tijd en onafhankelijk is van de reeks toestanden die eraan voorafgingen.

Het feit dat de volgende mogelijke actie / toestand van een willekeurig proces niet afhangt van de opeenvolging van eerdere toestanden, maakt Markov-ketens als een geheugenloos proces dat uitsluitend afhangt van de huidige toestand / actie van een variabele.

Laten we dit wiskundig afleiden:

Laat het willekeurige proces zijn, {Xm, m = 0,1,2, ⋯}.

Dit proces is alleen een Markov-keten als,

Markov Chain - Inleiding tot Markov Chains - Edureka

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

Voor een eindig aantal toestanden, S = {0, 1, 2, ⋯, r}, wordt dit een eindige Markov-keten genoemd.

P (Xm + 1 = j | Xm = i) vertegenwoordigt hier de overgangskansen om van de ene toestand naar de andere over te gaan. Hier gaan we ervan uit dat de overgangskansen onafhankelijk zijn van de tijd.

Wat betekent dat P (Xm + 1 = j | Xm = i) niet afhankelijk is van de waarde van ‘m’. Daarom kunnen we samenvatten,

Markov Chain Formula - Inleiding tot Markov-ketens - Edureka

Dus deze vergelijking vertegenwoordigt de Markov-keten.

Laten we nu eens kijken wat Markov-ketens precies zijn met een voorbeeld.

Markov Chain Voorbeeld

Laten we, voordat ik u een voorbeeld geef, definiëren wat een Markov-model is:

Wat is een Markov-model?

Een Markov-model is een stochastisch model dat willekeurige variabelen zo modelleert dat de variabelen de Markov-eigenschap volgen.

Laten we nu eens kijken hoe een Markov-model werkt met een eenvoudig voorbeeld.

Zoals eerder vermeld, worden Markov-ketens gebruikt in toepassingen voor het genereren van tekst en automatisch aanvullen. Voor dit voorbeeld bekijken we een (willekeurige) voorbeeldzin en zien we hoe deze kan worden gemodelleerd door Markov-ketens te gebruiken.

Markov Chain-voorbeeld - Inleiding tot Markov-ketens - Edureka

De bovenstaande zin is ons voorbeeld, ik weet dat het niet veel zin heeft (het hoeft niet), het is een zin met willekeurige woorden, waarin:

1. Sleutels duiden de unieke woorden in de zin aan, d.w.z. 5 sleutels (één, twee, hagel, gelukkig, edureka)

2. Munten geven het totale aantal woorden aan, d.w.z. 8 tokens.

Om verder te gaan, moeten we de frequentie van het voorkomen van deze woorden begrijpen, het onderstaande diagram toont elk woord samen met een nummer dat de frequentie van dat woord aangeeft.

Toetsen en frequenties - Inleiding tot Markov-ketens - Edureka

Dus de linkerkolom geeft hier de toetsen aan en de rechterkolom geeft de frequenties aan.

Uit de bovenstaande tabel kunnen we concluderen dat de sleutel ‘edureka’ 4x zo vaak wordt weergegeven als elke andere sleutel. Het is belangrijk om dergelijke informatie af te leiden, omdat het ons kan helpen voorspellen welk woord op een bepaald moment kan voorkomen. Als ik een gok zou wagen over het volgende woord in de voorbeeldzin, zou ik voor ‘edureka’ kiezen, aangezien dit de grootste kans heeft dat het voorkomt.

Over waarschijnlijkheid gesproken, een andere maatregel waar u zich bewust van moet zijn, is gewogen uitkeringen.

In ons geval is de gewogen distributie voor ‘edureka’ 50% (4/8) omdat de frequentie 4 is van de in totaal 8 tokens. De rest van de sleutels (een, twee, hagel, gelukkig) hebben allemaal een 1 / 8ste kans om te voorkomen (& asymp 13%).

Nu we inzicht hebben in de gewogen verdeling en een idee hebben hoe bepaalde woorden vaker voorkomen dan andere, kunnen we doorgaan met het volgende deel.

Markov-ketens begrijpen - Inleiding tot Markov-ketens - Edureka

In de bovenstaande afbeelding heb ik twee extra woorden toegevoegd die het begin en het einde van de zin aangeven. U zult begrijpen waarom ik dit deed in het onderstaande gedeelte.

Laten we nu ook de frequentie voor deze toetsen toewijzen:

Bijgewerkte sleutels en frequenties - Inleiding tot Markov-ketens - Edureka

Laten we nu een Markov-model maken. Zoals eerder vermeld, wordt een Markov-model gebruikt om willekeurige variabelen in een bepaalde toestand zodanig te modelleren dat de toekomstige toestanden van deze variabelen uitsluitend afhangen van hun huidige toestand en niet van hun vroegere toestand.

Dus in een Markov-model moeten we, om de volgende toestand te voorspellen, alleen de huidige toestand in overweging nemen.

In het onderstaande diagram kun je zien hoe elk token in onze zin naar een ander token leidt. Dit toont aan dat de toekomstige status (volgende token) is gebaseerd op de huidige status (huidige token). Dit is dus de meest basale regel in het Markov-model.

Het onderstaande diagram laat zien dat er paren tokens zijn waarbij elk token in het paar naar het andere in hetzelfde paar leidt.

Markov-kettingparen - Inleiding tot Markov-kettingen - Edureka

In het onderstaande diagram heb ik een structurele weergave gemaakt die elke sleutel laat zien met een reeks volgende mogelijke tokens waarmee deze kan worden gekoppeld.

Een reeks Markov-kettingparen - Inleiding tot Markov-kettingen - Edureka

Om dit voorbeeld samen te vatten, beschouw een scenario waarin u een zin moet vormen met behulp van de reeks sleutels en tokens die we in het bovenstaande voorbeeld hebben gezien. Voordat we dit voorbeeld doornemen, is een ander belangrijk punt dat we twee initiële maten moeten specificeren:

1. Een initiële kansverdeling (d.w.z. de startstatus op tijd = 0, (‘Start’ -toets))

2. Een overgangskans om van de ene toestand naar de andere te springen (in dit geval de kans op overgang van het ene token naar de andere)

We hebben de gewogen verdeling aan het begin zelf gedefinieerd, dus we hebben de kansen en de begintoestand, laten we nu verder gaan met het voorbeeld.

• Dus om te beginnen is het eerste token [Start]

• Vervolgens hebben we slechts één mogelijk token, namelijk [één]

• Momenteel heeft de zin slechts één woord, namelijk ‘één’

• Van dit token is het volgende mogelijke token [edureka]

  hoe je een dubbel cast naar een int

• De zin is bijgewerkt naar ‘one edureka’

• Van [edureka] kunnen we naar een van de volgende tokens gaan [twee, hagel, gelukkig, einde]

• Er is een kans van 25% dat ‘twee’ wordt gekozen, dit zou mogelijk resulteren in het vormen van de oorspronkelijke zin (één edureka twee edureka hagel edureka happy edureka). Als echter ‘end’ wordt gekozen, stopt het proces en zullen we uiteindelijk een nieuwe zin genereren, d.w.z. ‘one edureka’.

Geef jezelf een schouderklopje, want je hebt zojuist een Markov-model gebouwd en er een testcase doorheen gelopen. Om het bovenstaande voorbeeld samen te vatten, hebben we in feite de huidige toestand (huidig ​​woord) gebruikt om de volgende toestand (volgend woord) te bepalen. En dat is precies wat een Markov-proces is.

Het is een stochastisch proces waarbij willekeurige variabelen zodanig overgaan van de ene toestand naar de andere dat de toekomstige toestand van een variabele alleen afhangt van de huidige toestand.

Laten we naar de volgende stap gaan en het Markov-model voor dit voorbeeld uittekenen.

State Transition Diagram - Inleiding tot Markov-ketens - Edureka

De bovenstaande afbeelding staat bekend als het State Transition Diagram. We zullen hier meer over praten in het onderstaande gedeelte, maar onthoud nu dat dit diagram de overgangen en waarschijnlijkheid van de ene staat naar de andere laat zien.

Merk op dat elk ovaal in de afbeelding een sleutel vertegenwoordigt en dat de pijlen zijn gericht op de mogelijke toetsen die erop kunnen volgen. Ook geven de gewichten op de pijlen de waarschijnlijkheid of de gewogen verdeling van de overgang van / naar de respectieve staten.

Dus dat was alles over hoe het Markov-model werkt. Laten we nu eens proberen enkele belangrijke terminologieën in het Markov-proces te begrijpen.

Wat is een overgangswaarschijnlijkheidsmatrix?

In de bovenstaande sectie hebben we de werking van een Markov-model besproken met een eenvoudig voorbeeld, laten we nu de wiskundige terminologieën in een Markov-proces begrijpen.

In een Markov-proces gebruiken we een matrix om de overgangskansen van de ene staat naar de andere weer te geven. Deze matrix wordt de overgangs- of waarschijnlijkheidsmatrix genoemd. Het wordt meestal aangeduid met P.

Transitiematrix - Inleiding tot Markov-ketens - Edureka

Let op, pij & ge0, en ‘i’ voor alle waarden is,

Transition Matrix Formula - Inleiding tot Markov-ketens - Edureka

Laat me dit uitleggen. Ervan uitgaande dat onze huidige toestand ‘i’ is, moet de volgende of aankomende toestand een van de mogelijke toestanden zijn. Daarom, terwijl we de som van alle waarden van k nemen, moeten we er een krijgen.

Wat is een toestandsovergangsdiagram?

Een Markov-model wordt weergegeven door een State Transition Diagram. Het diagram toont de overgangen tussen de verschillende staten in een Markov-keten. Laten we de overgangsmatrix en de toestandsovergangsmatrix met een voorbeeld bekijken.

Transition Matrix Voorbeeld

Beschouw een Markov-ketting met drie staten 1, 2 en 3 en de volgende kansen:

Voorbeeld overgangsmatrix - Inleiding tot Markov-ketens - Edureka

Voorbeeld van toestandsovergangsschema - Inleiding tot Markov-ketens - Edureka

Het bovenstaande diagram vertegenwoordigt het toestandsovergangsdiagram voor de Markov-keten. Hier zijn 1,2 en 3 de drie mogelijke toestanden, en de pijlen die van de ene naar de andere toestand wijzen, vertegenwoordigen de overgangskansen pij. Wanneer, pij = 0, betekent dit dat er geen overgang is tussen toestand ‘i’ en toestand ‘j’.

Nu dat we ken de wiskunde en de logica achter Markov-ketens, laten we een eenvoudige demo uitvoeren en begrijpen waar Markov-ketens kunnen worden gebruikt.

Markov-ketting in Python

Om deze demo uit te voeren, gebruik ik Python, dus als je Python niet kent, kun je deze volgende blogs doornemen:

2. Hoe Python 3 van Scratch te leren - een gids voor beginners

Laten we nu aan de slag gaan met coderen!

Markov Chain Text Generator

Probleemstelling: Markov Property toepassen en een Markov-model maken dat tekstsimulaties kan genereren door de spraakgegevensverzameling van Donald Trump te bestuderen.

Beschrijving dataset: Het tekstbestand bevat een lijst met toespraken van Donald Trump in 2016.

Logica: Pas de Markov-eigenschap toe om de toespraak van Donald Trump te genereren door rekening te houden met elk woord dat in de toespraak wordt gebruikt en maak voor elk woord een woordenboek met woorden die vervolgens worden gebruikt.

wat is een token java

Stap 1: Importeer de vereiste pakketten

importeer numpy als np

Stap 2: Lees de dataset

trump = open ('C: //Users//NeelTemp//Desktop//demos//speeches.txt', encoding = 'utf8'). read () #display the data print (trump) SPRAAK 1 ... Bedankt Jou zo veel. Dat is zo aardig. Is hij geen geweldige kerel. Hij krijgt geen eerlijke pers, hij krijgt het niet. Het is gewoon niet eerlijk. En ik moet je zeggen dat ik hier ben, en heel sterk hier, omdat ik groot respect heb voor Steve King en ook groot respect heb voor Citizens United, David en iedereen, en een enorme resect voor de Tea Party. Ook de mensen van Iowa. Ze hebben iets gemeen. Hard werkende mensen....

Stap 3: Splits de dataset in afzonderlijke woorden

corpus = trump.split () #Geef de corpus print (corpus) 'krachtig', 'maar', 'niet', 'krachtig', 'zoals', 'ons.', 'Iran', 'heeft', 'weer gezaaid ',' terreur ', ...

Maak vervolgens een functie die de verschillende woordparen in de toespraken genereert. Om ruimte te besparen, gebruiken we een generatorobject.

Stap 4: Creëren van paren met sleutels en de vervolgwoorden

def make_pairs (corpus): voor i binnen bereik (len (corpus) - 1): yield (corpus [i], corpus [i + 1]) paren = make_pairs (corpus)

Laten we vervolgens een leeg woordenboek initialiseren om de woordparen op te slaan.

Als het eerste woord van het paar al een sleutel in het woordenboek is, voegt u het volgende potentiële woord toe aan de lijst met woorden die op het woord volgen. Maar als het woord geen sleutel is, maak dan een nieuw item in het woordenboek en wijs de sleutel toe die gelijk is aan het eerste woord van het paar.

Stap 5: het woordenboek toevoegen

word_dict = {} voor woord_1, woord_2 in paren: if word_1 in word_dict.keys (): word_dict [word_1] .append (word_2) else: word_dict [word_1] = [word_2]

Vervolgens kiezen we willekeurig een woord uit het corpus, waarmee de Markov-keten wordt gestart.

Stap 6: Bouw het Markov-model

# kies willekeurig het eerste woord first_word = np.random.choice (corpus) #Kies het eerste woord als een woord met een hoofdletter zodat het gekozen woord niet tussen een zin in wordt genomen terwijl first_word.islower (): #Start de keten vanaf de gekozen woordketen = [first_word] #Initialiseer het aantal gestimuleerde woorden n_words = 20

Na het eerste woord wordt elk woord in de keten willekeurig bemonsterd uit de lijst met woorden die op dat specifieke woord zijn gevolgd in de live toespraken van Trump. Dit wordt weergegeven in het onderstaande codefragment:

voor i binnen bereik (n_words): chain.append (np.random.choice (word_dict [chain [-1]]))

Stap 7: Voorspellingen

Laten we tot slot de gestimuleerde tekst weergeven.

#Join retourneert de ketting als een string print ('' .join (chain)) Het aantal ongelooflijke mensen. En Hillary Clinton, heeft onze mensen, en zo'n geweldige baan. En we zullen Obama niet verslaan

Dit is dus de gegenereerde tekst die ik heb gekregen door de toespraak van Trump te beschouwen. Het is misschien niet zo logisch, maar het is goed genoeg om u te laten begrijpen hoe Markov-ketens kunnen worden gebruikt om automatisch teksten te genereren.

Laten we nu eens kijken naar wat meer toepassingen van Markov-ketens en hoe ze worden gebruikt om echte problemen op te lossen.

Markov-kettingtoepassingen

Hier is een lijst met real-world toepassingen van Markov-ketens:

1. Google PageRank: Het hele web kan worden gezien als een Markov-model, waarbij elke webpagina een toestand kan zijn en de links of verwijzingen tussen deze pagina's kunnen worden beschouwd als overgangen met waarschijnlijkheden. Dus in principe, ongeacht op welke webpagina u begint te surfen, is de kans om naar een bepaalde webpagina te gaan, bijvoorbeeld X, een vaste waarschijnlijkheid.

2. Woordvoorspelling typen: Het is bekend dat Markov-ketens worden gebruikt voor het voorspellen van aanstaande woorden. Ze kunnen ook worden gebruikt bij automatische aanvulling en suggesties.

3. Subreddit-simulatie: Je bent zeker Reddit tegengekomen en had een interactie op een van hun threads of subreddits. Reddit gebruikt een subreddit-simulator die een enorme hoeveelheid gegevens verbruikt met alle opmerkingen en discussies die in hun groepen worden gehouden. Door gebruik te maken van Markov-ketens, produceert de simulator woord-tot-woord-waarschijnlijkheden, om opmerkingen en onderwerpen te creëren.

4. Tekstgenerator: Markov-ketens worden meestal gebruikt om dummyteksten te genereren of grote essays te produceren en toespraken samen te stellen. Het wordt ook gebruikt in de naamgeneratoren die u op internet ziet.

Nu je weet hoe je een echt probleem kunt oplossen door Markov Chains te gebruiken, ben ik er zeker van dat je nieuwsgierig bent naar meer. Hier is een lijst met blogs waarmee je aan de slag kunt gaan met andere statistische concepten:

Hiermee komen we aan het einde van deze Introduction To Markov Chains blog. Als je vragen hebt over dit onderwerp, laat dan hieronder een reactie achter en we nemen zo snel mogelijk contact met je op.

Blijf ons volgen voor meer blogs over de trending-technologieën.

Als je op zoek bent naar online gestructureerde training in Data Science, edureka! heeft een speciaal samengesteld programma dat u helpt expertise op te doen in statistiek, gegevenswrangling, verkennende gegevensanalyse, machine learning-algoritmen zoals K-Means Clustering, beslissingsbomen, Random Forest, Naive Bayes. Je leert ook de concepten van Time Series, Text Mining en een inleiding tot Deep Learning. Nieuwe batches voor deze cursus beginnen binnenkort !!