Uvod u Markovljeve lance s primjerima - Markovljevi lanci s Pythonom

Uvod u lance Markova:

Jeste li se ikad zapitali kako Google rangira web stranice? Ako ste proveli svoje istraživanje, morate znati da koristi algoritam PageRank koji se temelji na ideji o lancima Markova. Ovaj članak o Uvodu u lance Markov pomoći će vam da razumijete osnovnu ideju iza markovskih lanaca i kako ih se može modelirati kao rješenje problema iz stvarnog svijeta.

Evo popisa tema koje će biti obrađene u ovom blogu:

1. Što je Markov lanac?
2. Što je vlasništvo Markova?
3. Razumijevanje markovskih lanaca na primjeru
4. Što je prijelazna matrica?
5. Markov lanac u Pythonu
6. Primjene lanca Markov

Da biste stekli detaljno znanje o znanosti podataka i strojnom učenju pomoću Pythona, možete se prijaviti uživo Edureka s podrškom 24/7 i doživotnim pristupom.

Što je Markov lanac?

Andrey Markov lance Markov prvi je put predstavio 1906. godine. Objasnio je Markovljeve lance kao:

Stohastički proces koji sadrži slučajne varijable, prelazeći iz jednog stanja u drugo, ovisno o određenim pretpostavkama i određenim vjerojatnosnim pravilima.

Ovi slučajni varijable prijelaze iz jednog u drugo stanje, na temelju važnog matematičkog svojstva tzv Vlasništvo Markov.

To nas dovodi do pitanja:

Što je vlasništvo Markova?

Svojstvo markovskog diskretnog vremena navodi da izračunata vjerojatnost slučajnog procesa koji prelazi u sljedeće moguće stanje ovisi samo o trenutnom stanju i vremenu i neovisna je o nizu stanja koja su mu prethodila.

Činjenica da sljedeće moguće djelovanje / stanje slučajnog procesa ne ovisi o slijedu prethodnih stanja, čini Markovljeve lance kao proces bez memorije koji isključivo ovisi o trenutnom stanju / djelovanju varijable.

Izvedimo ovo matematički:

Neka slučajni postupak bude, {Xm, m = 0,1,2, ⋯}.

Ovaj je postupak Markovljev lanac samo ako,

Markov lanac - Uvod u Markovljeve lance - Edureka

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

Za konačan broj stanja, S = {0, 1, 2, ⋯, r}, to se naziva konačnim Markovljevim lancem.

P (Xm + 1 = j | Xm = i) ovdje predstavlja vjerojatnost prijelaza za prijelaz iz jednog stanja u drugo. Ovdje pretpostavljamo da su vjerojatnosti prijelaza neovisne o vremenu.

Što znači da P (Xm + 1 = j | Xm = i) ne ovisi o vrijednosti 'm'. Stoga možemo sažeti,

Formula lanca Markov - Uvod u lance Markov - Edureka

što je tvornica u angularjs

Dakle, ova jednadžba predstavlja lanac Markov.

Sada shvatimo što su točno lanci Markova na primjeru.

Primjer lanca Markov

Prije nego što vam dam primjer, definirajmo što je Markov model:

Što je Markov model?

Markov model je stohastički model koji modelira slučajne varijable na takav način da varijable slijede Markovljevo svojstvo.

Sada shvatimo kako Markov model funkcionira na jednostavnom primjeru.

Kao što je ranije spomenuto, lanci Markov koriste se u aplikacijama za stvaranje teksta i automatsko dovršavanje. U ovom ćemo primjeru pogledati primjer (slučajnu) rečenicu i vidjeti kako se ona može modelirati pomoću Markovljevih lanaca.

Primjer lanca Markov - Uvod u lance Markov - Edureka

Gornja rečenica je naš primjer, znam da nema puno smisla (ne mora), to je rečenica koja sadrži slučajne riječi, u kojima:

1. Ključevi označavaju jedinstvene riječi u rečenici, tj. 5 tipki (jedan, dva, tuča, sretan, edureka)

2. Žetoni označavaju ukupan broj riječi, tj. 8 tokena.

Krećući se naprijed, moramo razumjeti učestalost pojavljivanja ovih riječi, donji dijagram prikazuje svaku riječ zajedno s brojem koji označava učestalost te riječi.

Tipke i frekvencije - Uvod u Markovljeve lance - Edureka

Dakle, lijevi stupac ovdje označava tipke, a desni stupac frekvencije.

Iz gornje tablice možemo zaključiti da se tipka ‘edureka’ pojavljuje četverostruko više od bilo koje druge tipke. Važno je zaključiti o takvim informacijama jer nam mogu pomoći predvidjeti koja bi se riječ mogla pojaviti u određenom trenutku. Ako bih pretpostavio sljedeću riječ u primjeru rečenice, pristao bih na ‘edureka’ jer ona ima najveću vjerojatnost pojave.

Govoreći o vjerojatnosti, morate biti svjesni još jedne mjere ponderirane raspodjele.

U našem slučaju, ponderirana raspodjela za ‘edureka’ iznosi 50% (4/8) jer je njegova učestalost 4, od ukupno 8 žetona. Ostali ključevi (jedan, dva, tuča, sretan) svi imaju 1/8 šanse da se pojave (& asimp 13%).

Sad kad imamo razumijevanje ponderirane raspodjele i ideju kako se određene riječi javljaju češće od drugih, možemo nastaviti sa sljedećim dijelom.

Razumijevanje lanaca Markova - Uvod u lance Markova - Edureka

Na gornju sliku dodao sam dvije dodatne riječi koje označavaju početak i kraj rečenice, shvatit ćete zašto sam to učinio u donjem odjeljku.

Ajmo sada dodijeliti frekvenciju i za ove tipke:

Ažurirani ključevi i frekvencije - Uvod u Markovljeve lance - Edureka

Ajmo sada stvoriti model Markova. Kao što je ranije spomenuto, Markov model koristi se za modeliranje slučajnih varijabli u određenom stanju na takav način da buduća stanja ovih varijabli ovise isključivo o njihovom trenutnom stanju, a ne o prošlim stanjima.

Dakle, u osnovi u Markovljevom modelu, da bismo mogli predvidjeti sljedeće stanje, moramo uzeti u obzir samo trenutno stanje.

Na donjem dijagramu možete vidjeti kako svaki token u našoj rečenici vodi do drugog. To pokazuje da se buduće stanje (sljedeći token) temelji na trenutnom stanju (sadašnji token). Dakle, ovo je najosnovnije pravilo u Markovljevom modelu.

Dijagram dolje pokazuje da postoje parovi žetona gdje svaki žeton u paru vodi do drugog u istom paru.

Markovski lančani parovi - Uvod u Markovljeve lance - Edureka

U dijagramu u nastavku stvorio sam strukturni prikaz koji prikazuje svaki ključ s nizom sljedećih mogućih tokena s kojima se može upariti.

Niz markovskih lanaca - Uvod u lance Markov - Edureka

Da rezimiramo ovaj primjer, razmotrite scenarij u kojem ćete morati oblikovati rečenicu pomoću niza ključeva i tokena koje smo vidjeli u gornjem primjeru. Prije nego što prođemo kroz ovaj primjer, još jedna važna stvar je da moramo navesti dvije početne mjere:

1. Početna raspodjela vjerojatnosti (tj. Početno stanje u vremenu = 0, (tipka 'Start'))

2. Vjerojatnost prijelaza preskakanja iz jednog stanja u drugo (u ovom slučaju vjerojatnost prelaska iz jednog tokena u drugo)

Ponderiranu raspodjelu definirali smo na samom početku, tako da imamo vjerojatnosti i početno stanje, ajmo sada na primjer.

• Dakle, početak s početnim tokenom je [Start]

• Dalje, imamo samo jedan mogući žeton, tj. [Jedan]

  operator opsega c ++

• Trenutno rečenica ima samo jednu riječ, tj. „Jedna“

• Od ovog tokena, sljedeći mogući token je [edureka]

• Rečenica je ažurirana na „jedna edureka“

• Iz [edureka] možemo prijeći na bilo koji od sljedećih tokena [dva, pozdrav, sretan, kraj]

• Postoji 25% šanse da se izabere „dvoje“, to bi moglo rezultirati oblikovanjem izvorne rečenice (jedan edureka dva edureka pozdrav edureka sretni edureka). Međutim, ako se odabere 'kraj', tada se postupak zaustavlja i na kraju ćemo generirati novu rečenicu, tj. 'Jednu edureku'.

Potapšajte se po leđima jer ste upravo napravili Markov model i proveli testni slučaj. Da rezimiramo gornji primjer, u osnovi smo koristili sadašnje stanje (sadašnja riječ) za određivanje sljedećeg stanja (sljedeća riječ). A upravo je to Markov proces.

To je stohastički proces u kojem slučajne varijable prelaze iz jednog stanja u drugo na takav način da buduće stanje varijable ovisi samo o sadašnjem stanju.

Krenimo na sljedeći korak i izvucimo Markov model za ovaj primjer.

Dijagram prijelaza države - Uvod u Markovljeve lance - Edureka

Gornja je brojka poznata kao dijagram tranzicije države. O tome ćemo više govoriti u odjeljku u nastavku, zasad se samo sjetite da ovaj dijagram prikazuje prijelaze i vjerojatnost iz jednog stanja u drugo.

Primijetite da svaki oval na slici predstavlja ključ, a strelice su usmjerene prema mogućim tipkama koje ga mogu pratiti. Također, težine na strelicama označavaju vjerojatnost ili ponderirana raspodjela prijelaza iz / u odgovarajuća stanja.

Dakle, sve je bilo u tome kako djeluje Markov model. Pokušajmo sada razumjeti neke važne terminologije u Markovljevom procesu.

Što je matrica vjerojatnosti prijelaza?

U gornjem smo odjeljku na jednostavnom primjeru razgovarali o radu Markovljevog modela, ajmo sada razumjeti matematičke terminologije u Markovljevom procesu.

U Markovljevom procesu koristimo matricu za predstavljanje vjerojatnosti prijelaza iz jednog stanja u drugo. Ta se matrica naziva prijelaznom ili matricom vjerojatnosti. Obično se označava s P.

Prijelazna matrica - Uvod u Markovljeve lance - Edureka

Napomena, pij & ge0, a 'i' za sve vrijednosti je,

Formula prijelazne matrice - Uvod u Markovljeve lance - Edureka

Dopustite mi da objasnim ovo. Pod pretpostavkom da je naše trenutno stanje „i“, sljedeće ili nadolazeće stanje mora biti jedno od potencijalnih stanja. Stoga, uzimajući zbroj svih vrijednosti k, moramo dobiti jednu.

Što je dijagram prijelaza države?

Markov model predstavljen je dijagramom tranzicije države. Dijagram prikazuje prijelaze između različitih stanja u Markovljevom lancu. Razumijemo na primjeru matricu prijelaza i matricu prijelaza stanja.

Primjer matrice prijelaza

Razmotrimo Markovljev lanac s tri stanja 1, 2 i 3 i sljedećim vjerojatnostima:

Primjer prijelazne matrice - Uvod u Markovljeve lance - Edureka

Primjer dijagrama prijelaza države - Uvod u Markovljeve lance - Edureka

Gornji dijagram predstavlja dijagram prijelaza stanja za Markovljev lanac. Ovdje su 1,2 i 3 tri moguća stanja, a strelice koje pokazuju od jednog do drugog stanja predstavljaju vjerojatnosti prijelaza pij. Kada je pij = 0, to znači da nema prijelaza između stanja „i“ i stanja „j“.

Sad kad mi znajte matematiku i logiku iza Markovljevih lanaca, pokrenimo jednostavan demo i shvatimo gdje se markovski lanci mogu koristiti.

Markov lanac u Pythonu

Za pokretanje ove demonstracije koristit ću Python, pa ako ne znate Python, možete proći kroz sljedeće blogove:

2. Kako naučiti Python 3 iz ogrebotina - Vodič za početnike

Sada krenimo s kodiranjem!

Generator teksta lančanog Markova

Izjava o problemu: Primijeniti svojstvo Markova i stvoriti Markov model koji može generirati tekstualne simulacije proučavanjem skupa podataka govora Donalda Trumpa.

Opis skupa podataka: Tekstualna datoteka sadrži popis govora koje je Donald Trump održao 2016. godine.

Logika: Primijenite svojstvo Markov da biste generirali Donaldov Trumpov govor uzimajući u obzir svaku riječ koja se koristi u govoru i za svaku riječ stvorite rječnik riječi koji će se sljedeće koristiti.

Korak 1: Uvezite potrebne pakete

uvoz numpy kao np

Korak 2: Pročitajte skup podataka

trump = open ('C: //Users//NeelTemp//Desktop//demos//speeches.txt', encoding = 'utf8'). read () #prikaži ispis podataka (adut) GOVOR 1 ... Hvala ti toliko. To je tako lijepo. Nije li sjajan momak. Ne dobiva pošten tisak ne dobiva ga. To jednostavno nije pošteno. I moram vam reći da sam ovdje, i to vrlo snažno ovdje, jer izuzetno poštujem Stevea Kinga, a također poštujem Citizens United, Davida i sve ostale, i strašan čaj. Također, i ljudi u Iowi. Imaju nešto zajedničko. Vrijedni ljudi ....

Korak 3: Podijelite skup podataka u pojedinačne riječi

corpus = trump.split () # Prikaži korpusni ispis (corpus) 'moćan', 'ali', 'ne', 'moćan', 'poput', 'nas.', 'Iran', 'ima', ' zasijano ',' teror ', ...

Zatim stvorite funkciju koja generira različite parove riječi u govorima. Da bismo uštedjeli prostor, upotrijebit ćemo generator objekt.

Korak 4: Stvaranje parova za tipke i daljnje riječi

def make_pairs (corpus): za i u dometu (len (corpus) - 1): yield (corpus [i], corpus [i + 1]) parovi = make_pairs (corpus)

Dalje, inicijalizirajmo prazni rječnik za pohranu parova riječi.

U slučaju da je prva riječ u paru već ključ u rječniku, samo dodajte sljedeću potencijalnu riječ na popis riječi koje slijede riječ. Ali ako riječ nije ključ, stvorite novi unos u rječniku i dodijelite ključ jednak prvoj riječi u paru.

Korak 5: Dodavanje rječnika

word_dict = {} za word_1, word_2 u parovima: ako word_1 u word_dict.keys (): word_dict [word_1] .append (word_2) else: word_dict [word_1] = [word_2]

Dalje, nasumce odaberemo riječ iz korpusa koja će pokrenuti lanac Markov.

Korak 6: Izgradite Markov model

# slučajno odaberite prvu riječ first_word = np.random.choice (corpus) # Izaberite prvu riječ velikim slovima tako da odabrana riječ ne bude uzeta između rečenice dok first_word.islower (): # Pokrenite lanac iz odabrani lanac riječi = [first_word] #Initializirajte broj stimuliranih riječi n_words = 20

Nakon prve riječi, svaka se riječ u lancu nasumično uzorkuje s popisa riječi koje su slijedile tu određenu riječ u Trumpovim govorima uživo. To je prikazano u donjem isječku koda:

za i u rasponu (n_words): chain.append (np.random.choice (word_dict [chain [-1]]))

Korak 7: Predviđanja

Na kraju, prikažimo stimulirani tekst.

#Join vraća lanac kao ispis niza ('' .join (lanac)) Broj nevjerojatnih ljudi. A Hillary Clinton ima naše ljude i ima sjajan posao. I nećemo pobijediti Obamu

Dakle, ovo je generirani tekst koji sam dobio razmatrajući Trumpov govor. Možda neće imati puno smisla, ali dovoljno je dobro da shvatite kako se lanci Markova mogu koristiti za automatsko generiranje tekstova.

Pogledajmo sada još neke aplikacije markovskih lanaca i kako se koriste za rješavanje problema iz stvarnog svijeta.

Primjene lanca Markov

Evo popisa stvarnih aplikacija lanaca Markov:

1. Google PageRank: Čitav web može se smatrati Markovim modelom, pri čemu svaka web stranica može biti stanje, a veze ili reference između tih stranica mogu se smatrati prijelazima s vjerojatnostima. Dakle, u osnovi, bez obzira na kojoj web stranici započinjete surfanje, šansa da dođete do određene web stranice, recimo, X je fiksna vjerojatnost.

2. Predviđanje tipkanja riječi: Poznato je da se lanci Markova koriste za predviđanje nadolazećih riječi. Također se mogu koristiti za automatsko dovršavanje i davanje prijedloga.

3. Subreddit simulacija: Sigurno ste naišli na Reddit i imali interakciju s jednom od njihovih niti ili subredita. Reddit koristi subreddit simulator koji troši ogromnu količinu podataka koji sadrže sve komentare i rasprave održane u njihovim grupama. Koristeći Markovljeve lance, simulator stvara vjerojatnost od riječi do riječi za stvaranje komentara i tema.

4. Generator teksta: Lanci Markova najčešće se koriste za stvaranje lažnih tekstova ili izradu velikih eseja i sastavljanje govora. Također se koristi u generatorima imena koje vidite na webu.

Sad kad znate kako riješiti stvarni problem pomoću Markov Chains, siguran sam da ste znatiželjni da saznate više. Evo popisa blogova koji će vam pomoći da započnete s drugim statističkim konceptima:

Ovim smo došli do kraja ovog bloga Uvod u lance Markov. Ako imate pitanja u vezi s ovom temom, ostavite komentar u nastavku i javit ćemo vam se.

Pratite još blogova o trendovskim tehnologijama.

Ako tražite mrežni strukturirani trening iz znanosti znanosti, edureka! ima posebno kuriranu program koji vam pomaže da steknete stručnost u statistici, premještanju podataka, istraživačkoj analizi podataka, algoritmima strojnog učenja poput klastera K-Means, drvećima odluka, slučajnim šumama, naivnim Bayesima. Naučit ćete i koncepte vremenskih serija, rudarenja teksta te uvod u duboko učenje. Uskoro počinju nove serije za ovaj tečaj !!