Uvod v Markove verige s primeri - Markovske verige s Pythonom



Ta članek o Uvodu v verige Markov vam bo pomagal razumeti osnovno idejo za verige Markov in kako jih je mogoče modelirati s pomočjo Pythona.

Uvod v verige Markov:

Ste se kdaj vprašali, kako Google uvršča spletne strani? Če ste raziskovali, morate vedeti, da uporablja algoritem PageRank, ki temelji na ideji o verigah Markov. Ta članek o Uvodu v Markovske verige vam bo pomagal razumeti osnovno idejo, ki stoji za Markovimi verigami, in kako jih je mogoče modelirati kot rešitev za resnične probleme.

Tu je seznam tem, ki bodo obravnavane v tem blogu:





  1. Kaj je veriga Markov?
  2. Kaj je lastnina Markov?
  3. Razumevanje Markovskih verig na primeru
  4. Kaj je prehodna matrica?
  5. Markova veriga v Pythonu
  6. Markov verižne aplikacije

Če želite pridobiti poglobljeno znanje o znanosti o podatkih in strojnem učenju s pomočjo Pythona, se lahko prijavite v živo Edureka s 24-urno podporo in življenjskim dostopom.

Kaj je veriga Markov?

Andrey Markov je verige Markov prvič predstavil leta 1906. Markovske verige je razložil kot:



Stohastični proces, ki vsebuje naključne spremenljivke, ki prehajajo iz enega stanja v drugega, odvisno od določenih predpostavk in določenih verjetnostnih pravil.

Ti naključni spremenljivke prehajajo iz enega v drugo stanje na podlagi pomembne matematične lastnosti, imenovane Nepremičnina Markov.

To nas pripelje do vprašanja:



Kaj je lastnina Markov?

Lastnost diskretnega časa Markova navaja, da je izračunana verjetnost prenosa naključnega procesa v naslednje možno stanje odvisna samo od trenutnega stanja in časa ter je neodvisna od niza stanj, ki so bila pred njim.

Dejstvo, da naslednje možno dejanje / stanje naključnega procesa ni odvisno od zaporedja predhodnih stanj, predstavlja Markove verige kot proces brez pomnilnika, ki je odvisen izključno od trenutnega stanja / delovanja spremenljivke.

Izvedimo to matematično:

Naj bo naključni postopek {Xm, m = 0,1,2, ⋯}.

Ta postopek je Markova veriga le, če:

Formula verige Markov - Uvod v verige Markov - Edureka

Markov veriga - Uvod v verige Markov - Edureka

za vse m, j, i, i0, i1, ⋯ im & minus1

Za končno število stanj, S = {0, 1, 2, ⋯, r}, se to imenuje končna Markova veriga.

kako uporabljati tostring v javi -

P (Xm + 1 = j | Xm = i) tukaj predstavlja verjetnost prehoda za prehod iz enega stanja v drugo. Tu predpostavljamo, da so verjetnosti prehoda neodvisne od časa.

Kar pomeni, da P (Xm + 1 = j | Xm = i) ni odvisna od vrednosti ‘m’. Zato lahko povzamemo,

Formula verige Markov - Uvod v verige Markov - Edureka

Ta enačba torej predstavlja verigo Markov.

Zdaj pa razumimo, kaj točno so verige Markov s primerom.

Primer Markove verige

Preden vam dam primer, določimo, kaj je Markov model:

Kaj je Markov model?

Markov model je stohastični model, ki naključne spremenljivke modelira na tak način, da spremenljivke sledijo Markovovi lastnosti.

Zdaj pa razumimo, kako Markov model deluje s preprostim primerom.

Kot smo že omenili, se verige Markov uporabljajo v aplikacijah za ustvarjanje besedila in samodejno dokončanje. Za ta primer si bomo ogledali primer (naključni) stavek in videli, kako ga je mogoče modelirati z uporabo Markovskih verig.

Primer Markovske verige - Uvod v Markovske verige - Edureka

Zgornji stavek je naš primer, vem, da nima veliko smisla (ni nujno), je stavek, ki vsebuje naključne besede, pri čemer:

  1. Ključi označujejo edinstvene besede v stavku, tj. 5 tipk (ena, dve, toča, srečna, edureka)

  2. Žetoni označujejo skupno število besed, to je 8 žetonov.

Ko gremo naprej, moramo razumeti pogostost pojavljanja teh besed, spodnji diagram prikazuje vsako besedo skupaj s številko, ki označuje pogostost te besede.

Tipke in frekvence - Uvod v Markove verige - Edureka

Torej levi stolpec tukaj označuje tipke, desni stolpec pa frekvence.

Iz zgornje tabele lahko sklepamo, da je tipka ‘edureka’ štirikrat večja kot katera koli druga tipka. Takšne informacije je pomembno sklepati, ker nam lahko pomagajo napovedati, katera beseda se lahko pojavi v določenem trenutku. Če bi ugibal o naslednji besedi v primeru stavka, bi šel z 'edureko', saj ima največjo verjetnost pojava.

Če govorimo o verjetnosti, je še en ukrep, ki se ga morate zavedati tehtane porazdelitve.

V našem primeru je utežena porazdelitev za 'edureka' 50% (4/8), ker je njena frekvenca 4, od skupno 8 žetonov. Preostali ključi (ena, dve, toča, srečni) imajo vsi 1/8 možnosti, da se pojavijo (& asimp 13%).

Zdaj, ko razumemo tehtano porazdelitev in si predstavljamo, kako se določene besede pojavljajo pogosteje kot druge, lahko nadaljujemo z naslednjim delom.

Razumevanje Markovskih verig - Uvod v Markove verige - Edureka

Na zgornji sliki sem dodal dve dodatni besedi, ki označujeta začetek in konec stavka, v spodnjem razdelku boste razumeli, zakaj sem to storil.

Zdaj določimo frekvenco tudi za te tipke:

Posodobljeni ključi in frekvence - Uvod v verige Markov - Edureka

Zdaj pa ustvarimo model Markova. Kot smo že omenili, se Markov model uporablja za modeliranje naključnih spremenljivk v določenem stanju tako, da so prihodnja stanja teh spremenljivk odvisna izključno od njihovega trenutnega stanja in ne od preteklih.

V bistvu v Markovem modelu moramo za napovedovanje naslednjega stanja upoštevati le trenutno stanje.

Na spodnjem diagramu lahko vidite, kako vsak žeton v našem stavku vodi do drugega. To kaže, da prihodnje stanje (naslednji žeton) temelji na trenutnem stanju (sedanji žeton). To je torej najosnovnejše pravilo v Markovem modelu.

Spodnji diagram kaže, da obstajajo pari žetonov, pri katerih vsak žeton v paru vodi do drugega v istem paru.

Markov verižni pari - Uvod v Markovske verige - Edureka

V spodnjem diagramu sem ustvaril strukturno predstavitev, ki prikazuje vsak ključ z vrsto naslednjih možnih žetonov, s katerimi se lahko seznani.

Niz Markovskih verižnih parov - Uvod v Markovske verige - Edureka

Če povzamemo ta primer, razmislite o scenariju, v katerem boste morali oblikovati stavek z uporabo niza ključev in žetonov, ki smo jih videli v zgornjem primeru. Preden se lotimo tega primera, je še ena pomembna točka, da moramo določiti dva začetna ukrepa:

  1. Začetna porazdelitev verjetnosti (tj. Začetno stanje ob času = 0, (tipka »Start«))

  2. Verjetnost prehoda za preskok iz enega stanja v drugega (v tem primeru verjetnost prehoda iz enega žetona v drugega)

Na začetku smo definirali tehtano porazdelitev, zato imamo verjetnosti in začetno stanje, zdaj nadaljujmo s primerom.

  • Za začetek z začetnim žetonom je [Start]

  • Nato imamo samo en možen žeton, tj. [En]

  • Trenutno ima stavek samo eno besedo, tj.

  • Od tega žetona je naslednji možni žeton [edureka]

  • Stavek je posodobljen na „ena edureka“

  • Iz [edureka] se lahko premaknemo na katerega koli od naslednjih žetonov [dva, toča, vesel, konec]

  • Obstaja 25% verjetnosti, da se izbere „dva“, kar bi lahko privedlo do oblikovanja prvotnega stavka (en edureka dva edureka toča edureka srečna edureka). Če pa izberemo 'end', se postopek ustavi in ​​na koncu bomo ustvarili nov stavek, to je 'one edureka'.

Privoščite si trepljanje po hrbtu, ker ste pravkar izdelali Markov model in skozi njega izvedli testni primer. Če povzamemo zgornji primer, smo v osnovi uporabili sedanje stanje (sedanja beseda) za določitev naslednjega stanja (naslednjo besedo). In prav to je Markov proces.

Gre za stohastični proces, pri katerem naključne spremenljivke prehajajo iz enega stanja v drugo tako, da je prihodnje stanje spremenljivke odvisno samo od sedanjega stanja.

Pojdimo na naslednji korak in za ta primer narišimo Markov model.

Diagram prehoda države - Uvod v verige Markova - Edureka

Zgornja slika je znana kot diagram prehoda države. O tem bomo govorili več v spodnjem razdelku, za zdaj samo zapomnite si, da ta diagram prikazuje prehode in verjetnost iz enega stanja v drugega.

Upoštevajte, da vsak oval na sliki predstavlja ključ, puščice pa so usmerjene proti možnim tipkam, ki mu lahko sledijo. Tudi uteži na puščicah označujejo verjetnost ali tehtana porazdelitev prehoda iz / v posamezna stanja.

Torej je bilo vse v tem, kako deluje Markov model. Zdaj poskusimo razumeti nekaj pomembnih terminologij v Markovem procesu.

Kaj je matrika verjetnosti prehoda?

V zgornjem poglavju smo na preprost primer razpravljali o delovanju Markovega modela, zdaj pa razumimo matematične terminologije v Markovem procesu.

V Markovem procesu z matrico predstavljamo verjetnosti prehoda iz enega stanja v drugo. Ta matrica se imenuje matrica prehoda ali verjetnosti. Običajno ga označujemo s P.

kaj naredi init v pythonu

Prehodna matrica - Uvod v Markove verige - Edureka

Opomba, pij & ge0 in 'i' za vse vrednosti je,

Formula prehodne matrice - Uvod v Markove verige - Edureka

Naj to razložim. Ob predpostavki, da je naše trenutno stanje 'i', mora biti naslednje ali prihajajoče stanje eno od potencialnih držav. Zato moramo med seštevanjem vseh vrednosti k dobiti eno.

Kaj je diagram prehoda države?

Markov model predstavlja državni prehodni diagram. Diagram prikazuje prehode med različnimi stanji v Markovi verigi. Razložimo s primerom matriko prehoda in matriko prehoda stanja.

Primer matrice prehoda

Razmislite o Markovi verigi s tremi stanji 1, 2 in 3 in naslednjimi verjetnostmi:

Primer tranzicijske matrice - Uvod v Markove verige - Edureka

Primer diagrama prehoda države - Uvod v Markove verige - Edureka

Zgornji diagram predstavlja diagram prehoda stanja za verigo Markov. Tu sta 1,2 in 3 tri možna stanja, puščice, ki kažejo iz enega stanja v drugo, pa predstavljajo verjetnost prehoda pij. Kadar je pij = 0, to pomeni, da ni prehoda med stanjem 'i' in stanjem 'j'.

Zdaj, ko smo poznamo matematiko in logiko za Markovimi verigami, zaženimo preprost demo in razumemo, kje se lahko uporabljajo Markovske verige.

Markova veriga v Pythonu

Če želite zagnati to predstavitev, bom uporabil Python, tako da, če ne poznate Pythona, lahko obiščete te spletne dnevnike:

  1. Kako se naučiti Python 3 iz Scratch - vodnik za začetnike

Zdaj pa začnimo s kodiranjem!

Generator besedila Markov Chain

Izjava o težavi: Če želite uporabiti lastnost Markova in ustvariti model Markova, ki lahko ustvari simulacije besedila s preučevanjem nabora podatkov govora Donalda Trumpa.

Opis nabora podatkov: Besedilna datoteka vsebuje seznam govorov, ki jih je imel Donald Trump leta 2016.

Logika: Uporabite lastnost Markov, da ustvarite Donaldov Trumpov govor, tako da upoštevate vsako besedo, uporabljeno v govoru, in za vsako besedo ustvarite slovar besed, ki se uporabljajo v nadaljevanju.

kaj je navidezna metoda

1. korak: Uvozite zahtevane pakete

uvozi numpy kot np

2. korak: preberite nabor podatkov

trump = open ('C: //Users//NeelTemp//Desktop//demos//speeches.txt', encoding = 'utf8'). read () #prikaži izpis podatkov (adut) GOVOR 1 ... hvala ti toliko. To je tako lepo. Ali ni dober fant. Ne dobi poštenega tiska, ne dobi ga. Preprosto ni pošteno. In moram vam povedati, da sem tukaj in zelo močno tukaj, ker zelo spoštujem Stevea Kinga in zelo spoštujem Citizens United, Davida in vse, ter izjemno spoštovanje do čajanke. Prav tako tudi prebivalci Iove. Imajo nekaj skupnega. Pridni ljudje ....

3. korak: Nabor podatkov razdelite na posamezne besede

corpus = trump.split () # Prikažite tisk korpusa (corpus) 'močan', 'ampak', 'ne', 'močan', 'kot', 'mi.', 'Iran', 'ima', ' zasejan ',' teror ', ...

Nato ustvarite funkcijo, ki generira različne pare besed v govorih. Da prihranimo prostor, bomo uporabili objekt generator.

4. korak: Ustvarjanje parov za tipke in nadaljnje besede

def make_pairs (corpus): za i v obsegu (len (corpus) - 1): donos (corpus [i], corpus [i + 1]) parovi = make_pairs (corpus)

Nato inicializiramo prazen slovar za shranjevanje parov besed.

Če je prva beseda v paru že ključ v slovarju, preprosto dodajte naslednjo potencialno besedo na seznam besed, ki sledijo besedi. Če pa beseda ni ključ, ustvarite nov vnos v slovar in dodelite ključ, ki je enak prvi besedi v paru.

5. korak: Dodajanje slovarja

word_dict = {} za word_1, word_2 v parih: če word_1 v word_dict.keys (): word_dict [word_1] .apend (word_2) else: word_dict [word_1] = [word_2]

Nato naključno izberemo besedo iz korpusa, ki bo začela verigo Markov.

6. korak: Zgradite model Markova

#naključno izberite prvo besedo first_word = np.random.choice (corpus) # Prvo besedo izberite z veliko začetnico, tako da izbrana beseda ne bo vzeta med stavkom, medtem ko first_word.islower (): # Začnite verigo izbrana besedna veriga = [prva_beseda] # Inicializirajte število stimuliranih besed n_besed = 20

Po prvi besedi je vsaka beseda v verigi naključno vzorčena s seznama besed, ki so sledile tej določeni besedi v Trumpovih govorih v živo. To je prikazano v spodnjem delčku kode:

za i v obsegu (n_words): chain.append (np.random.choice (word_dict [veriga [-1]]))

7. korak: Napovedi

Za konec pa še prikazano spodbudeno besedilo.

#Join vrne verigo kot niz (''.join (chain)) Število neverjetnih ljudi. In Hillary Clinton ima naše ljudi in tako izvrstno delo. In ne bomo premagali Obame

To je torej ustvarjeno besedilo, ki sem ga dobil ob upoštevanju Trumpovega govora. Morda nima veliko smisla, vendar je dovolj dobro, da razumete, kako lahko Markove verige uporabljamo za samodejno ustvarjanje besedil.

Zdaj pa poglejmo še nekaj aplikacij markovskih verig in kako se uporabljajo za reševanje resničnih problemov.

Markov verižne aplikacije

Tu je seznam resničnih aplikacij verig Markov:

  1. Google PageRank: Celotno spletno stran si lahko predstavljamo kot Markov model, kjer je vsaka spletna stran lahko stanje, povezave ali reference med temi stranmi pa lahko predstavljamo kot prehode z verjetnostmi. V bistvu je ne glede na to, na kateri spletni strani začnete brskati, možnost, da pridete do določene spletne strani, recimo, X, določena verjetnost.

  2. Napovedovanje tipkanja besed: Znano je, da se verige Markov uporabljajo za napovedovanje prihajajočih besed. Uporabljajo se lahko tudi pri samodejnem dokončanju in predlogih.

  3. Subreddit Simulacija: Zagotovo ste že naleteli na Reddit in imeli interakcijo z eno od njihovih niti ali podreditami. Reddit uporablja simulator subreddit, ki porabi ogromno podatkov, ki vsebujejo vse komentarje in razprave v njihovih skupinah. Z uporabo verig Markov simulator ustvari verjetnost od besede do besede, da ustvari komentarje in teme.

  4. Ustvarjalnik besedila: Markovske verige se najpogosteje uporabljajo za ustvarjanje navideznih besedil ali izdelavo velikih esejev in sestavljanje govorov. Uporablja se tudi v generatorjih imen, ki jih vidite v spletu.

Zdaj, ko veste, kako rešiti resnični problem z uporabo Markov Chains, sem prepričan, da vas zanima več. Tu je seznam spletnih dnevnikov, ki vam bodo pomagali začeti z drugimi statističnimi koncepti:

S tem smo prišli do konca tega bloga Uvod v verige Markov. Če imate kakršna koli vprašanja v zvezi s to temo, pustite komentar spodaj in odgovorili vam bomo.

Spremljajte več blogov o trendovskih tehnologijah.

Če iščete spletno strukturirano izobraževanje iz znanosti znanosti, edureka! ima posebej kurirano program, ki vam pomaga pridobiti strokovno znanje s področja statistike, premeščanja podatkov, raziskovalne analize podatkov, algoritmov strojnega učenja, kot so grozdi K-Means, drevesa odločanja, naključni gozd, naivni Bayes. Spoznali boste koncepte časovnih vrst, rudarjenja besedil in uvod v globoko učenje. Kmalu se začenjajo nove serije za ta tečaj !!