Problem 1. Matrica prijelaznih vjerojatnosti za diskretni Markovljev lanac iz ja th država u j-th u jednom koraku ( ja, j=1, 2). Distribucija vjerojatnosti po stanjima u početni trenutak t=0 određen je vektorom =(0,1; 0,9). Pronaći:

1. matrica R2 lančani prijelaz iz stanja ja u stanje j dva
korak;

2. distribucija vjerojatnosti po stanjima u trenutku t=2;

3. vjerojatnost da u trenutku t=1 stanje sklopa će biti A2;

4. stacionarna distribucija.

Riješenje. Za diskretni Markovljev lanac u slučaju njegove homogenosti relacija

gdje je P1 matrica prijelaznih vjerojatnosti u jednom koraku;
Pn - matrica prijelaznih vjerojatnosti za n koraka;

1. Nađite prijelaznu matricu P2 u dva koraka

Neka je distribucija vjerojatnosti po stanjima on S-ti korak je određen vektorom
.
Poznavanje matrice PN prijelaz u n koraka, moguće je odrediti distribuciju vjerojatnosti po stanjima na (S+n)-ti korak . (5)

2. Naći distribuciju vjerojatnosti stanja sustava u ovom trenutku t=2. Stavili smo (5) S=0 i n=2. Zatim .

Dobivamo .

3. Naći distribuciju vjerojatnosti stanja sustava u trenutku t=1.

Stavili smo (5) s=0 i n=1, tada .
Kako možete vidjeti da je vjerojatnost da u ovom trenutku t=1 stanje sklopa će biti A2, jednako je p2(1)=0,69.
Distribucija vjerojatnosti po stanjima naziva se stacionarnom ako se ne mijenja od koraka do koraka, tj
Tada iz relacije (5) pri n=1 dobivamo

4. Pronađite stacionarnu distribuciju. Kako je =2 imamo =(p1; p2). Zapišimo sustav linearne jednadžbe(6) u koordinatnom obliku

Posljednji uvjet naziva se normalizacija. U sustavu (6) jedna jednadžba je uvijek linearna kombinacija drugih. Stoga se može izbrisati. Riješimo zajedno prvu jednadžbu sustava i normalizacijsku. Imamo 0,6 p1=0,3p2, to je p2=2p1. Zatim p1+2p1=1 ili , tj. Posljedično,.
Odgovor:
1) matrica prijelaza u dva koraka za dati Markovljev lanac ima oblik ;
2) distribuciju vjerojatnosti po stanjima u trenutku t=2 jednako ;
3) vjerojatnost da u trenutku t=1 stanje sklopa će biti A2, jednako je p2(t)=0,69;
4) stacionarna raspodjela ima oblik

S obzirom na matricu intenziteti prijelaza kontinuiranog Markovljevog lanca. Sastavite označeni graf stanja koji odgovara matrici Λ; izraditi sustav diferencijalne jednadžbe Kolmogorov za vjerojatnosti stanja; pronaći graničnu distribuciju vjerojatnosti. Riješenje. Homogeni Markovljev lanac sa konačan broj Države A1, A2,…ALI karakteriziran matricom intenziteta prijelaza ,

gdje - intenzitet prijelaza Markovljevog lanca iz stanja AI u stanje aj; rij(Δt)- vjerojatnost prijelaza Ai →aj po vremenskom intervalu Δ t.

Prikladno je specificirati prijelaze sustava iz stanja u stanje pomoću označenog grafa stanja, na kojem su označeni lukovi koji odgovaraju intenzitetima λ i J>0. Sastavite označeni grafikon stanja za zadana matrica intenziteti prijelaza

Neka je vektor vjerojatnosti Rj(t),
j=1, 2,…,, sustav je u stanju ALIj u trenutku t.

Očito je da je 0≤ Rj(t)≤1 i . Zatim po pravilu diferenciranja vektorska funkcija skalarni argument dobivamo . Vjerojatnosti Rj(t) zadovoljavaju Kolmogorov sustav diferencijalnih jednadžbi (SDUK), koji u matričnom obliku ima oblik . (7)

Ako je u početnom trenutku sustav bio u stanju aj, tada SDUK treba riješiti pod početnim uvjetima
Rja(0)=1, rj(0)=0, j≠i,j=1, 2,…,. (8)
Skup SDUK (7) i početnih uvjeta (8) jedinstveno opisuje homogeni Markovljev lanac s neprekidno vrijeme i konačan broj stanja.
Sastavimo SDUK za dati Markovljev lanac. Budući da je =3, dakle j=1, 2, 3.

Iz relacije (7) dobivamo

.
Stoga ćemo imati

Posljednji uvjet naziva se normalizacija.
Distribucija vjerojatnosti po stanjima naziva se stacionarni, ako se s vremenom ne mijenja, odnosno gdje Rj=konst, j=1,2,…,. Odavde .

Tada iz SDUK-a (7) dobivamo sustav za pronalaženje stacionarne distribucije
(9)
Za ovaj problem iz SDUK-a ćemo imati

Iz uvjeta normalizacije dobivamo 3p2+p2+p2=1 ili . Stoga granična distribucija ima oblik .
Imajte na umu da se ovaj rezultat može dobiti izravno iz označenog grafikona stanja korištenjem pravila: za stacionarnu distribuciju, zbroj umnožaka λ jipi, j≠ja, za strijele koje izlaze iz ja stanje jednako je zbroju umnožaka λ jipi, j≠ja, za strelice uključene u ja th stanje. Stvarno,

Očito je da je dobiveni sustav ekvivalentan onom sastavljenom prema SDUK-u. Stoga ima isto rješenje.
Odgovor: stacionarna distribucija ima oblik .

Markovljev lanac je niz događaja u kojem svaki sljedeći događaj ovisi o prethodnom. U članku ćemo detaljnije analizirati ovaj koncept.

Markovljev lanac je uobičajen i prilično jednostavan način modeliranja slučajni događaji. Koristi se u različitim područjima, od generiranja teksta do financijskog modeliranja. po najviše poznati primjer je SubredditSimulator. NA ovaj slučaj Markovljev lanac koristi se za automatizaciju stvaranja sadržaja kroz subreddit.

Markovljev lanac je jasan i jednostavan za korištenje jer se može implementirati bez upotrebe bilo kakvih statističkih ili matematičkih koncepata. Markovljev lanac idealan je za proučavanje probabilističkog modeliranja i znanosti o podacima.

Scenarij

Zamislite da postoje samo dva vremenski uvjeti: može biti sunčano ili oblačno. Uvijek možete točno odrediti vrijeme u ovaj trenutak. Garantirano vedro ili oblačno.

Sada želite naučiti kako predvidjeti vrijeme za sutra. Intuitivno shvaćate da se vrijeme ne može dramatično promijeniti u jednom danu. Mnogi faktori utječu na to. Sutrašnje vrijeme izravno ovisi o trenutnom i tako dalje.Dakle, da biste predvidjeli vrijeme, skupljate podatke nekoliko godina i dolazite do zaključka da je nakon oblačnog dana vjerojatnost sunčanog dana 0,25. Logično je pretpostaviti da je vjerojatnost dva oblačna dana zaredom 0,75, budući da imamo samo dva moguća vremenska uvjeta.

Sada možete predvidjeti vrijeme za nekoliko dana unaprijed na temelju trenutnog vremena.

Ovaj primjer pokazuje ključni koncepti Markovljevi lanci. Markovljev lanac sastoji se od skupa prijelaza definiranih distribucijom vjerojatnosti, koji zauzvrat zadovoljavaju Markovljevo svojstvo.

Imajte na umu da u primjeru distribucija vjerojatnosti ovisi samo o prijelazima iz tekućeg dana u sljedeći. to jedinstveno svojstvo Markovljev proces - to radi bez korištenja memorije. Takav pristup u pravilu ne može stvoriti slijed u kojem bi se uočio bilo kakav trend. Na primjer, iako Markovljev lanac može simulirati stil pisanja na temelju učestalosti riječi, on nije u stanju stvoriti tekstove s duboko značenje, budući da može raditi samo s velikim tekstovima. Zbog toga Markovljev lanac ne može proizvesti sadržaj ovisan o kontekstu.

Model

Formalno, Markovljev lanac je probabilistički automat. Distribucija vjerojatnosti prijelaza obično se prikazuje kao matrica. Ako Markovljev lanac ima N mogućih stanja, tada će matrica izgledati kao N x N, u kojoj će unos (I, J) biti vjerojatnost prijelaza iz stanja I u stanje J. Osim toga, takva matrica mora biti stohastička , odnosno zbroj redaka ili stupaca trebao bi biti jedan. U takvoj matrici, svaki red će imati vlastitu distribuciju vjerojatnosti.

Opći pogled na Markovljev lanac sa stanjima u obliku krugova i rubovima u obliku prijelaza.

Približna prijelazna matrica s tri moguća stanja.

Markovljev lanac ima vektor početnog stanja, predstavljen kao matrica N x 1. On opisuje distribuciju vjerojatnosti početka u svakom od N mogućih stanja. Unos I opisuje vjerojatnost pokretanja lanca u stanju I.

Ove dvije strukture su dovoljne da predstavljaju Markovljev lanac.

Već smo raspravljali o tome kako dobiti vjerojatnost prijelaza iz jednog stanja u drugo, ali što je s dobivanjem te vjerojatnosti u nekoliko koraka? Da bismo to učinili, moramo odrediti vjerojatnost prijelaza iz stanja I u stanje J u M koraka. Zapravo je vrlo jednostavno. Prijelazna matrica P može se odrediti izračunavanjem (I, J) podizanjem P na potenciju M. Za male vrijednosti M, to se može učiniti ručno ponovljenim množenjem. Ali za velike vrijednosti M ako ste upoznati s linearnom algebrom, više učinkovit način dizanje matrice na potenciju prvo će dijagonalizirati tu matricu.

Markovljev lanac: zaključak

Sada, znajući što je Markovljev lanac, možete ga lako implementirati u jednom od programskih jezika. Jednostavni Markovljevi lanci temelj su za učenje više složene metode modeliranje.

Sva moguća stanja sustava u homogenom Markovljevom lancu, te je stohastička matrica koja definira ovaj lanac, sastavljena od prijelaznih vjerojatnosti (Vidi stranicu 381).

Označimo s vjerojatnošću da je sustav u određenom trenutku ako je poznato da je u to vrijeme sustav bio u stanju (,). Očito, . Koristeći teoreme o zbrajanju i množenju vjerojatnosti, lako možemo pronaći:

ili u matričnom zapisu

Stoga, dajući uzastopno vrijednosti , dobivamo važnu formulu

Ako postoje granice

ili u matričnom zapisu

zatim količine nazivaju se granične ili konačne prijelazne vjerojatnosti.

Da bismo saznali u kojim slučajevima postoje ograničavajuće vjerojatnosti prijelaza i da bismo izveli odgovarajuće formule, uvodimo sljedeću terminologiju.

Stohastičku matricu i odgovarajući homogeni Markovljev lanac nazvat ćemo regularnim ako matrica nema karakteristične brojeve različite od jedinice i jednake po modulu jedinici, a regularnim ako je dodatno jedinica jednostavan korijen karakteristična jednadžba matrice.

Regularna matrica je karakterizirana činjenicom da su u svom normalnom obliku (69) (str. 373) matrice primitivne. Za regularnu matricu dodatno .

Osim toga, homogeni Markovljev lanac naziva se nerazgradivim, razgradljivim, acikličkim, cikličkim, ako je za taj lanac stohastička matrica, odnosno, nerazgradiva, razgradljiva, primitivna, imprimitivna.

Budući da je primitivna stohastička matrica posebna vrsta regularne matrice, aciklički Markovljev lanac je posebna vrsta regularnog lanca.

Pokazat ćemo da granične prijelazne vjerojatnosti postoje samo za regularne homogene Markovljeve lance.

Doista, neka je minimalni polinom regularne matrice . Zatim

Prema teoremu 10 možemo pretpostaviti da

Na temelju formule (24) Ch. V (stranica 113)

(96)

gdje je reducirana adjungirana matrica i

Ako je regularna matrica, onda

i stoga na desnoj strani formule (96) svi članovi, osim prvog, teže nuli kao . Stoga, za regularnu matricu, postoji matrica sastavljena od graničnih prijelaznih vjerojatnosti, i

Suprotno je očito. Ako postoji praznina

tada matrica ne može imati karakterističan broj, za koje , i , budući da tada granica ne bi postojala [Ista granica mora postojati zbog postojanja granice (97").]

Dokazali smo da za ispravan (i jedino ispravan) homogen Markovljev lanac postoji matrica . Ova matrica je određena formulom (97).

Pokažimo kako se matrica može izraziti u terminima karakterističnog polinoma

i pridruženu matricu .

Od identiteta

na temelju (95), (95") i (98) slijedi:

Stoga se formula (97) može zamijeniti formulom

(97)

Za regularni Markovljev lanac, budući da se radi o posebnoj vrsti regularnog lanca, matrica postoji i određena je bilo kojom od formula (97), (97"). U ovom slučaju formula (97") također ima oblik

2. Razmotrimo pravilan lanac općeg tipa (nepravilan). Pripadajuću matricu zapišemo u normalnom obliku

(100)

gdje su primitivne stohastičke matrice, a nerastavljive matrice imaju maksimalne karakteristične brojeve . Pretpostavljajući

,

upiši u obrazac

(101)

Ali , budući da su svi karakteristični brojevi matrice manji od jedinice u apsolutnoj vrijednosti. Zato

(102)

Budući da su primitivne stohastičke matrice, onda su matrice prema formulama (99) i (35) (str. 362) pozitivne

i u svakom stupcu bilo koje od ovih matrica, svi elementi su međusobno jednaki:

.

Imajte na umu da normalni oblik (100) stohastičke matrice odgovara podjeli stanja sustava u grupe:

Svaka grupa u (104) odgovara svojoj grupi serija u (101). Prema terminologiji L. N. Kolmogorova, stanja sustava uključena u nazivaju se bitna, a stanja uključena u preostale skupine nazivaju se nebitna.

Iz oblika (101) matrice slijedi da je za bilo koji konačni broj koraka (od trenutka do trenutka) moguć samo prijelaz sustava a) iz bitnog stanja u bitno stanje iste skupine, b ) iz beznačajnog stanja u bitno stanje i c) iz beznačajnog stanja u nebitno stanje iste ili ranije skupine.

Iz oblika (102) matrice proizlazi da u procesu kada je prijelaz moguć samo iz bilo kojeg stanja u bitno stanje, tj. vjerojatnost prijelaza u bilo koje beznačajno stanje s brojem koraka teži nuli. Stoga se bitna stanja ponekad nazivaju i graničnim stanjima.

3. Iz formule (97) slijedi:

.

Ovo pokazuje da je svaki stupac matrice svojstveni vektor stohastičke matrice za karakteristični broj.

Za regularnu matricu, broj 1 je jednostavan korijen karakteristične jednadžbe, a ovaj broj odgovara samo jednom (do skalarnog faktora) svojstvenom vektoru matrice. Dakle, u bilo kojem th stupcu matrice svi elementi su jednaki istom nenegativnom broju:

Stoga, u pravilnom lancu, granične prijelazne vjerojatnosti ovise o početnom stanju.

Obrnuto, ako u nekom pravilnom homogenom Markovljevom lancu pojedinačne prijelazne vjerojatnosti ne ovise o početnom stanju, tj. vrijede formule (104), tada je u shemi (102) za matricu obvezno . Ali tada je i lanac pravilan.

Jer aciklički lanac, koji je poseban slučaj pravilnog lanca, je primitivna matrica. Stoga, za neke (vidi Teorem 8 na str. 377). Ali onda i .

Obrnuto, iz toga slijedi da za neke , a to, prema teoremu 8, znači da je matrica primitivna i, prema tome, dani homogeni Markovljev lanac je aciklički.

Dobivene rezultate formuliramo u obliku sljedećeg teorema:

Teorem 11. 1. Da bi u homogenom Markovljevom lancu postojale sve granične prijelazne vjerojatnosti, potrebno je i dovoljno da lanac bude regularan. U ovom slučaju, matrica, sastavljena od graničnih prijelaznih vjerojatnosti, određena je formulom (95) ili (98).

2. Da bi granične prijelazne vjerojatnosti bile neovisne o početnom stanju u pravilnom homogenom Markovljevom lancu, potrebno je i dovoljno da lanac bude regularan. U ovom slučaju, matrica je određena formulom (99).

3. Da bi sve granične prijelazne vjerojatnosti bile različite od nule u pravilnom homogenom Markovljevom lancu, potrebno je i dovoljno da lanac bude acikličan.

4. Uvedimo stupce apsolutnih vjerojatnosti

(105)

gdje je vjerojatnost da je sustav trenutno u stanju (,). Koristeći teoreme zbrajanja i množenja vjerojatnosti, nalazimo:

(,),

ili u matričnom zapisu

gdje je transponirana matrica za matricu .

Sve apsolutne vjerojatnosti (105) određuju se iz formule (106) ako su poznate početne vjerojatnosti i matrica prijelaznih vjerojatnosti

Uvedimo u razmatranje granične apsolutne vjerojatnosti

Prelaskom u oba dijela jednakosti (106) do granice na , dobivamo:

Imajte na umu da postojanje matrice ograničavajućih prijelaznih vjerojatnosti implicira postojanje ograničavajućih apsolutnih vjerojatnosti za sve početne vjerojatnosti i obrnuto.

Iz formule (107) i oblika (102) matrice slijedi da su granične apsolutne vjerojatnosti koje odgovaraju beznačajnim stanjima jednake nuli.

Množenje obje strane jednakosti matrice

desno, na temelju (107) dobivamo:

tj. stupac graničnih apsolutnih vjerojatnosti je svojstveni vektor matrice za karakteristični broj .

Ako a dati lanac Markov regularan, tada je jednostavan korijen karakteristične jednadžbe matrice . U tom je slučaju stupac graničnih apsolutnih vjerojatnosti jednoznačno određen iz (108) (jer i ).

Neka je dan pravilan Markovljev lanac. Tada iz (104) i (107) slijedi:

(109)

U ovom slučaju granične apsolutne vjerojatnosti ne ovise o početnim vjerojatnostima.

Nasuprot tome, ne mora ovisiti o u prisutnosti formule (107) ako i samo ako su svi redovi matrice isti, tj.

,

te je stoga (prema teoremu 11) regularna matrica.

Ako je primitivna matrica, tada je , i stoga zbog (109)

Obrnuto, ako sve i ne ovise o početnim vjerojatnostima, tada su u svakom stupcu matrice svi elementi isti i prema (109), a to prema teoremu 11 znači da je primitivna matrica, tj. lanac je acikličan.

Iz navedenog slijedi da se teorem 11 može formulirati na sljedeći način:

Teorem 11. 1. Da bi sve granične apsolutne vjerojatnosti postojale u homogenom Markovljevom lancu za bilo koje početne vjerojatnosti, potrebno je i dovoljno da lanac bude regularan.

2. Da bi homogeni Markovljev lanac imao granične apsolutne vjerojatnosti za bilo koje početne vjerojatnosti i da ne bi ovisio o tim početnim vjerojatnostima, potrebno je i dovoljno da lanac bude regularan.

3. Da bi homogeni Markovljev lanac imao pozitivne granične apsolutne vjerojatnosti za bilo koje početne vjerojatnosti i da te granične vjerojatnosti ne bi ovisile o početnim, potrebno je i dovoljno da lanac bude acikličan.

5. Razmotrimo sada homogeni Markovljev lanac opći tip s matricom prijelaznih vjerojatnosti .

Uzmimo normalni oblik (69) matrice i označimo s indeksima imprimitivnosti matrice u (69). Dopustiti biti najmanji zajednički višekratnik cijelih brojeva . Tada matrica nema karakteristične brojeve jednake u apsolutnoj vrijednosti jedinici, već različite od jedinice, tj. regularna je matrica; u isto vrijeme - najmanji pokazatelj, na kojem - ispravna matrica. Broj nazivamo periodom danog homogenog Markovljevog lanca i. Obrnuto, ako je i definirana formulama (110) i (110").

Prosječne granične apsolutne vjerojatnosti koje odgovaraju neesencijalnim stanjima uvijek su jednake nuli.

Ako u normalnom obliku matrice postoji broj (i samo u tom slučaju), prosječne granične apsolutne vjerojatnosti ne ovise o početnim vjerojatnostima i jednoznačno su određene iz jednadžbe (111).

Ovaj članak daje Generalna ideja o tome kako generirati tekstove modeliranjem Markovljevih procesa. Posebno ćemo se upoznati s Markovljevim lancima, a kao praksu ćemo implementirati mali generator teksta u Pythonu.

Za početak ispisujemo definicije koje su nam potrebne, ali nam još ne baš jasne sa stranice Wikipedije, kako bismo barem otprilike zamislili s čime imamo posla:

Markovljev proces t t

Markovljev lanac

Što sve ovo znači? Hajdemo shvatiti.

Osnove

Prvi primjer je krajnje jednostavan. Koristeći rečenicu iz dječje knjige, savladat ćemo osnovni koncept Markovljevog lanca, kao i definirati što je u našem kontekstu korpus, veze, distribucija vjerojatnosti i histogrami. Iako je prijedlog Engleski jezik, biti će lako shvatiti bit teorije.

Ova ponuda je okvir, odnosno baza na temelju koje će se u budućnosti generirati tekst. Sastoji se od osam riječi, ali u isto vrijeme jedinstvene riječi samo pet je poveznice(govorimo o Markovu lanci). Radi jasnoće, obojajmo svaku vezu u svoju boju:

I zapišite broj pojavljivanja svake od poveznica u tekstu:

Gornja slika pokazuje da riječ riba pojavljuje se u tekstu 4 puta češće od svake druge riječi ( Jedan, dva, crveno, plavo). Odnosno, vjerojatnost susreta u našem korpusu riječi riba 4 puta veća od vjerojatnosti susreta sa svakom drugom riječi na slici. Govoreći jezikom matematike, možemo odrediti zakon raspodjele slučajne varijable i izračunati s kojom vjerojatnošću će se jedna od riječi pojaviti u tekstu nakon trenutne. Vjerojatnost se izračunava na sljedeći način: potrebno je podijeliti broj pojavljivanja riječi koja nam je potrebna u korpusu s ukupni broj sve riječi u njemu. Za riječ riba ova je vjerojatnost 50% jer se pojavljuje 4 puta u rečenici od 8 riječi. Za svaku od preostalih veza ta je vjerojatnost 12,5% (1/8).

Grafički predstavite distribuciju slučajne varijable moguće uz pomoć histogrami. U ovom slučaju jasno je vidljiva učestalost pojavljivanja svake od poveznica u rečenici:

Dakle, naš se tekst sastoji od riječi i jedinstvenih poveznica, a distribuciju vjerojatnosti pojavljivanja svake od poveznica u rečenici prikazali smo na histogramu. Ako vam se čini da se ne biste trebali petljati sa statistikom, pročitajte. I možda spasiti svoj život.

Suština definicije

Dodajmo sada našem tekstu elemente koji se uvijek podrazumijevaju, ali se ne čuju u svakodnevnom govoru - početak i kraj rečenice:

Bilo koja rečenica sadrži ove nevidljive "početak" i "kraj", dodajmo ih kao poveznice na našu distribuciju:

Vratimo se na definiciju s početka članka:

Markovljev proces je slučajan proces čija evolucija nakon bilo koje postavljena vrijednost vremenski parametar t ne ovisi o evoluciji koja je prethodila t, pod uvjetom da je vrijednost procesa u ovom trenutku fiksna.

Markovljev lanac - poseban slučaj Markovljev proces, kada je prostor njegovih stanja diskretan (tj. ne više nego prebrojiv).

Dakle, što ovo znači? Ugrubo rečeno, modeliramo proces u kojem stanje sustava u sljedećem trenutku vremena ovisi samo o njegovom stanju u trenutnom trenutku, a ne ovisi ni na koji način o svim prethodnim stanjima.

Zamislite što je ispred vas prozor, koji prikazuje samo trenutno stanje sustava (u našem slučaju to je jedna riječ), a vi samo na temelju podataka prikazanih u ovom prozoru trebate odrediti koja će biti sljedeća riječ. U našem korpusu riječi se nižu jedna za drugom po sljedećem obrascu:

Tako nastaju parovi riječi (čak i kraj rečenice ima svoj par - praznu vrijednost):

Grupirajmo ove parove prema prvoj riječi. Vidjet ćemo da svaka riječ ima svoj skup poveznica, koje u kontekstu naše rečenice svibanj prati ga:

Predstavimo ovu informaciju na drugačiji način - svakoj vezi će biti dodijeljen niz svih riječi koje se mogu pojaviti u tekstu nakon ove veze:

Pogledajmo pobliže. Vidimo da svaka veza ima riječi koje svibanj doći iza njega u rečenici. Kad bismo gornji dijagram pokazali nekom drugom, ta bi osoba mogla, s određenom vjerojatnošću, rekonstruirati naš početna ponuda, odnosno korpus.

Primjer. Počnimo s riječju Početak. Zatim odaberite riječ Jedan, budući da prema našoj shemi jest jedna riječ, koji može slijediti početak rečenice. Iza riječi Jedan također može slijediti samo jedna riječ - riba. Sada izgleda novi prijedlog u srednjoj verziji Jedna riba. Dalje, situacija postaje kompliciranija riba riječi mogu ići s jednakom vjerojatnošću u 25% "dva", "crveno", "plavo" i kraj rečenice Kraj. Ako pretpostavimo da je sljedeća riječ - "dva" rekonstrukcija će se nastaviti. Ali možemo izabrati vezu Kraj. U ovom slučaju, na temelju naše sheme, nasumično će se generirati rečenica koja se jako razlikuje od korpusa - Jedna riba.

Upravo smo modelirali Markovljev proces - svaku sljedeću riječ odredili smo samo na temelju znanja o trenutnoj. Za potpunu asimilaciju materijala, napravimo dijagrame koji pokazuju ovisnosti između elemenata unutar našeg korpusa. Ovali predstavljaju karike. Strelice vode do mogućih poveznica koje mogu pratiti riječ u ovalu. U blizini svake strelice - vjerojatnost da će se sljedeća veza pojaviti nakon trenutne:

izvrsno! Naučili smo potrebne informacije kako bi krenuli dalje i analizirali složenije modele.

Širenje baze rječnika

U ovom dijelu članka izgradit ćemo model prema istom principu kao i prije, ali ćemo izostaviti neke korake u opisu. Ako imate poteškoća, vratite se na teoriju u prvom bloku.

Uzmimo još četiri citata od istog autora (također na engleskom, neće nam škoditi):

“Danas si ti ti. To je više od istine. Ne postoji nitko živ tko je ti-er od tebe."

“Imaš pameti u glavi. Imaš noge u cipelama. Možete se usmjeriti u kojem god smjeru odaberete. Sam si."

"Više da tičitati, više stvari koje ćete znati. Što više naučiš, više ćeš mjesta otići."

Misli lijevo i desno i misli nisko i misli visoko. Oh, misli koje možeš smisliti ako samo pokušaš."

Složenost korpusa je povećana, ali u našem slučaju to je samo plus - sada će generator teksta moći proizvesti smislenije rečenice. Činjenica je da u bilo kojem jeziku postoje riječi koje se u govoru pojavljuju češće od drugih (na primjer, mnogo češće koristimo prijedlog "u" nego riječ "kriogeno"). Kako više riječi u našem korpusu (a time i ovisnosti među njima), generator ima više informacija o tome koja će se riječ najvjerojatnije pojaviti u tekstu nakon trenutne.

Najlakše je to objasniti s gledišta programa. Znamo da za svaku vezu postoji skup riječi koje je mogu pratiti. Također, svaku riječ karakterizira i broj pojavljivanja u tekstu. Moramo nekako uhvatiti sve ove informacije na jednom mjestu; rječnik koji pohranjuje parove "(ključ, vrijednost)" je najprikladniji za ovu svrhu. Ključ rječnika će zabilježiti trenutno stanje sustava, odnosno jednu od poveznica u korpusu (npr. "the" na slici ispod); a drugi rječnik će biti pohranjen u vrijednosti rječnika. U ugniježđenom rječniku ključevi će biti riječi koje se mogu pojaviti u tekstu nakon trenutne jedinice korpusa ( "misli" i više može ići u tekstu nakon "the"), a vrijednosti - broj pojavljivanja ovih riječi u tekstu nakon našeg linka (riječ "misli" pojavljuje se u tekstu iza riječi "the" 1 put, riječ više nakon riječi "the"- 4 puta):

Ponovno pročitajte gornji odlomak nekoliko puta kako biste ga dobro shvatili. Imajte na umu da je ugniježđeni rječnik u ovom slučaju isti histogram, pomaže nam pratiti poveznice i učestalost njihovog pojavljivanja u tekstu u odnosu na druge riječi. Treba napomenuti da je čak i takva vokabularna baza vrlo mala za pravilno generiranje tekstova u prirodni jezik- trebao bi sadržavati više od 20 000 riječi, a po mogućnosti više od 100 000. I još bolje - više od 500 000. Ali pogledajmo rječničku bazu koju imamo.

Markovljev lanac u ovom je slučaju konstruiran slično kao u prvom primjeru - svaka sljedeća riječ odabire se samo na temelju znanja o trenutnoj riječi, sve ostale riječi se ne uzimaju u obzir. Ali zbog pohranjivanja u rječniku podataka o tome koje se riječi pojavljuju češće od drugih, možemo odlučiti prihvatiti ponderirana odluka. Pogledajmo konkretan primjer:

Više:

Odnosno, ako je trenutna riječ riječ više, iza njega mogu biti riječi s jednakom vjerojatnošću u 25% "stvari" i "mjesta", a s vjerojatnošću od 50% - riječ "da". Ali vjerojatnosti mogu biti i sve su međusobno jednake:

razmišljati:

Rad s prozorima

Do sada smo razmatrali samo prozore od jedne riječi. Možete povećati veličinu prozora tako da generator teksta proizvodi više "provjerenih" rečenica. To znači da što je veći prozor, to će biti manje odstupanja od trupa tijekom generiranja. Povećanje veličine prozora odgovara prijelazu Markovljevog lanca na više visokog reda. Prethodno smo izgradili lanac prvog reda, za prozor od dvije riječi dobivamo lanac drugog reda, od tri - trećeg i tako dalje.

Prozor su podaci u Trenutna država sustave koji se koriste za donošenje odluka. Ako kombiniramo veliki prozor i mali skup podataka, tada ćemo vjerojatno svaki put dobiti istu rečenicu. Uzmimo bazu rječnika iz našeg prvog primjera i proširimo prozor na veličinu 2:

Proširenje je rezultiralo time da svaki prozor sada ima samo jednu opciju za sljedeće stanje sustava - što god radili, uvijek ćemo dobiti istu rečenicu, identičnu našem korpusu. Stoga, kako biste eksperimentirali s prozorima i kako bi generator teksta vratio jedinstveni sadržaj, opskrbite se vokabularom od 500 000 riječi ili više.

Implementacija u Pythonu

Diktografska struktura podataka

Diktogram (dict je ugrađeni rječnički tip podataka u Pythonu) prikazat će odnos između poveznica i njihovu učestalost pojavljivanja u tekstu, odnosno njihovu distribuciju. Ali u isto vrijeme, imat će svojstvo rječnika koje nam je potrebno - vrijeme izvršenja programa neće ovisiti o količini ulaznih podataka, što znači da stvaramo učinkovit algoritam.

Uvezi slučajnu klasu Diktogram(dikt): def __init__(self, iterable=None): # Inicijaliziraj našu distribuciju kao novi objekt klase, # dodaj postojeće elemente super(Diktogram, samo).__init__() self.types = 0 # broj jedinstveni ključevi u distribuciji self.tokens = 0 # ukupno svih riječi u distribuciji if iterable: self.update(iterable) def update(self, iterable): # Ažurirajte distribuciju sa stavkama iz # postojećeg iterable skupa podataka za stavku u iterable: if item in self: self += 1 self .tokens += 1 else: self = 1 self.types += 1 self.tokens += 1 def count(self, item): # Vrati vrijednost brojača stavke ili 0 ako je stavka u sebi: return self return 0 def return_random_word (self): random_key = random.sample(self, 1) # Drugi način: # random.choice(histogram.keys()) return random_key def return_weighted_random_word(self): # Generiraj pseudoslučajni broj između 0 i (n- 1), # gdje je n ukupan broj riječi random_int = random.randint(0, self.tokens-1) index = 0 list_of_keys = self.keys() # print "random index:", random_int for i in range( 0, self.types): index += self] # ispis indeksa if(index > random_int): # ispis popisa_ključeva[i] povratak popis_ključeva[i]

Bilo koji objekt koji se može iterirati može se proslijediti konstruktoru strukture Diktograma. Elementi ovog objekta bit će riječi za inicijalizaciju diktagrama, na primjer, sve riječi iz neke knjige. U ovom slučaju, brojimo elemente tako da za pristup bilo kojem od njih ne bi bilo potrebno svaki put prolaziti kroz cijeli skup podataka.

Napravili smo i dvije povratne funkcije nasumična riječ. Jedna funkcija odabire slučajni ključ u rječniku, a druga, uzimajući u obzir broj pojavljivanja svake riječi u tekstu, vraća riječ koja nam je potrebna.

Struktura Markovljevog lanca

from histograms import Diktogram def make_markov_model(data): markov_model = dict() for i in range(0, len(data)-1): if data[i] in markov_model: # Samo dodajte već postojećoj distribuciji markov_model].update ( ]) else: markov_model] = Diktogram(]) vrati markov_model

U gornjoj implementaciji imamo rječnik koji pohranjuje prozore kao ključ u paru "(ključ, vrijednost)" i distribucije kao vrijednosti u tom paru.

Struktura Markovljevog lanca N-tog reda

from histograms import Diktogram def make_higher_order_markov_model(order, data): markov_model = dict() for i in range(0, len(data)-order): # Create window window = tuple(data) # Add to dictionary if window in markov_model: # Priložite postojećoj distribuciji markov_model.update(]) else: markov_model = Diktogram(]) return markov_model

Vrlo sličan Markovljevom lancu prvog reda, ali u ovom slučaju spremamo tuple kao ključ u paru "(ključ, vrijednost)" u rječniku. Koristimo ga umjesto popisa, jer je tuple zaštićen od bilo kakvih promjena, a to nam je važno - uostalom, ključevi u rječniku se ne bi trebali mijenjati.

Raščlanjivanje modela

Super, implementirali smo rječnik. Ali kako sada generirati sadržaj na temelju trenutnog stanja i preći na sljedeće stanje? Prođimo kroz naš model:

From histograms import Diktogram import random from collections import deque import re def generate_random_start(model): # Za generiranje bilo koje početne riječi, skinite komentar s retka: # return random.choice(model.keys()) # Za generiranje "ispravne" početne riječi , upotrijebite kod ispod: # Ispravno početne riječi su one koje su bile početak rečenica u if "END" u korpusu modela: seed_word = "END" while seed_word == "END": seed_word = model["END"].return_weighted_random_word() return seed_word return random.choice( model .keys()) def generate_random_sentence(length, markov_model): current_word = generate_random_start(markov_model) sentence = for i in range(0, length): current_dictogram = markov_model random_weighted_word = current_dictogram.return_weighted_random_word() current_word = random_weighted_word sentence.append(current_word) ) rečenica = rečenica.capitalize() return " ".join(rečenica) + "." povratna rečenica

Što je sljedeće?

Pokušajte smisliti gdje sami možete koristiti generator teksta temeljen na Markovljevim lancima. Samo nemojte zaboraviti da je najvažnije kako analizirate model i koja ste posebna ograničenja postavili na generiranje. Autor ovog članka, primjerice, koristio je veliki prozor prilikom izrade generatora tweetova, ograničio generirani sadržaj na 140 znakova, a za početak rečenica koristio samo “ispravne” riječi, odnosno one koje su bile početak rečenice u korpus.

Načini matematički opisi Markovljevi stohastički procesi u sustavu s diskretnim stanjima (DS) ovise o tome u kojim vremenskim točkama (unaprijed poznatim ili slučajnim) se mogu dogoditi prijelazi sustava iz stanja u stanje.
Ako je prijelaz sustava iz stanja u stanje moguć u unaprijed određenim vremenima, imamo posla s slučajan Markovljev proces s diskretnim vremenom. Ako je prijelaz moguć u bilo kojem nasumičnom trenutku, onda imamo posla s slučajni Markovljev proces s kontinuiranim vremenom.
Neka bude fizički sustav S, koji može biti u n Države S 1 , S 2 , …, S n. Prijelazi iz stanja u stanje mogući su samo povremeno t 1 , t 2 , …, t k Nazovimo te trenutke vremena koracima. Razmotrit ćemo SP u sustavu S kao funkcija argumenta cijelog broja 1, 2, ..., k, gdje je argument broj koraka.
Primjer: S 1 → S 2 → S 3 → S 2 .
Označimo Si (k) je događaj koji se sastoji u činjenici da nakon k koraka sustav je u stanju S ja.
Za bilo koje k događaji S 1 ( k), S 2 ( k),…, S n (k) obrazac puna grupa događaja i jesu nekompatibilan.

Proces u sustavu može se prikazati kao lanac događaja.
Primjer: S 1 (0) , S 2 (1) , S 3 (2) , S 5 (3) ,….
Takav se niz naziva Markovljev lanac , ako je za svaki korak vjerojatnost prijelaza iz bilo kojeg stanja Si u bilo kojoj državi S j ne ovisi o tome kada je i kako sustav došao u stanje Si.
Neka bilo kada nakon bilo kojeg k-go step sustav S može biti u jednoj od država S 1 , S 2 , …, S n, tj. može se dogoditi jedan događaj iz kompletne grupe događaja: S 1 (k), S 2 ( k) , …, S n (k) . Označimo vjerojatnosti ovih događaja:
P 1 (1) = P(S 1 (1)); P 2 (1) = P(S 2 (1)); …; P n(1) = P(S n (k));
P 1 (2) = P(S 1 (2)); P 2 (2) = P(S2(2)); …; P n(2) = P(S n (2));
P 1 (k) = P(S 1 (k)); P 2 (k) = P(S 2 (k)); …; P n(k) = P(S n (k)).
Lako je vidjeti da je za svaki korak broj uvjet
P 1 (k) + P 2 (k) +…+ P n(k) = 1.
Nazovimo ove vjerojatnosti vjerojatnosti stanja.zbog toga će zadatak zvučati ovako: pronaći vjerojatnosti stanja sustava za bilo koje k.
Primjer. Neka postoji neki sustav koji može biti u bilo kojem od šest stanja. tada se procesi koji se u njemu odvijaju mogu prikazati ili u obliku grafikona promjena stanja sustava (sl. 7.9, a), ili u obliku grafa stanja sustava (Sl. 7.9, b).

a)

Riža. 7.9
Također, procesi u sustavu mogu se prikazati kao niz stanja: S 1 , S 3 , S 2 , S 2 , S 3 , S 5 , S 6 , S 2 .
Vjerojatnost stanja na ( k+ 1)-ti korak ovisi samo o stanju at k- m korak.
Za bilo koji korak k postoje neke vjerojatnosti prijelaza sustava iz bilo kojeg stanja u bilo koje drugo stanje, nazovimo to vjerojatnostima prijelazne vjerojatnosti Markovljevog lanca.
Neke od tih vjerojatnosti bit će 0 ako prijelaz iz jednog stanja u drugo nije moguć u jednom koraku.
Markovljev lanac se zove homogena ako prijelazna stanja ne ovise o broju koraka, inače se zove heterogena.
Neka postoji homogen Markovljev lanac i neka sustav S Ima n moguća stanja: S 1 , …, S n. Neka je za svako stanje poznata vjerojatnost prijelaza u drugo stanje u jednom koraku, tj. P ij(iz Si u S j u jednom koraku), tada vjerojatnosti prijelaza možemo napisati kao matricu.

. (7.1)
Na dijagonali ove matrice nalaze se vjerojatnosti da sustav prelazi iz stanja Si u istoj državi Si.
Koristeći prethodno uvedene događaje , prijelazne vjerojatnosti mogu se napisati kao uvjetne vjerojatnosti:
.
Očito, zbroj pojmova u svakom retku matrice (1) jednak je jedan, budući da događaji čine potpunu skupinu nekompatibilnih događaja.

Pri razmatranju Markovljevih lanaca, kao i pri analizi Markovljevih lanaca slučajni proces, koriste se različiti grafikoni stanja (slika 7.10).

Riža. 7.10

Ovaj sustav može biti u bilo kojem od šest stanja, dok P ij je vjerojatnost prijelaza sustava iz stanja Si u stanje S j. Za ovaj sustav pišemo jednadžbe da je sustav bio u nekom stanju i iz njega tijekom vremena t nije izašao:

NA opći slučaj Markovljev lanac je nehomogen, tj. vjerojatnost P ij mijenja se iz koraka u korak. Pretpostavimo da je dana matrica prijelaznih vjerojatnosti na svakom koraku, tada je vjerojatnost da sustav S na k-th korak će biti u državi Si, može se pronaći pomoću formule

Poznavajući matricu prijelaznih vjerojatnosti i početno stanje sustava, možete pronaći vjerojatnosti stanja nakon bilo kojeg k-ti korak. Neka je u početnom trenutku sustav u stanju Sm. Tada je za t = 0
.
Nađite vjerojatnosti nakon prvog koraka. Izvan države Sm sustav će ići u stanja S 1 , S 2 itd. s vjerojatnostima Pm 1 , Pm 2 , …, Pmm, …, Pmn. Tada će nakon prvog koraka vjerojatnosti biti jednake

. (7.2)
Nađimo vjerojatnosti stanja nakon drugog koraka: . Te ćemo vjerojatnosti izračunati pomoću formule puna vjerojatnost sa hipotezama:
.
Hipoteze će biti sljedeće izjave:

• nakon prvog koraka sustav je bio u stanju S 1 -H 1 ;
• nakon drugog koraka sustav je bio u stanju S 2 -H 2 ;
• nakon n-tom koraku sustav je bio u stanju S n -H n .

Vjerojatnosti hipoteza poznate su iz izraza (7.2). Uvjetne vjerojatnosti prijelaz stanja ALI za svaku hipotezu također su poznati i zabilježeni u matricama prijelaznog stanja. Tada, prema formuli ukupne vjerojatnosti, dobivamo:

Vjerojatnost bilo kojeg stanja nakon drugog koraka:

(7.3)
Formula (7.3) sažima sve vjerojatnosti prijelaza P ij, ali se u obzir uzimaju samo oni koji nisu nula. Vjerojatnost bilo kojeg stanja nakon k- korak:

(7.4)
Dakle, vjerojatnost stanja nakon k-th korak je određen rekurentna formula(7.4) u smislu vjerojatnosti ( k- 1) korak.

Zadatak 6. Dana je matrica prijelaznih vjerojatnosti za Markovljev lanac u jednom koraku. Pronađite prijelaznu matricu zadanog sklopa u tri koraka .
Riješenje. Prijelazna matrica sustava je matrica koja sadrži sve prijelazne vjerojatnosti tog sustava:

Svaki redak matrice sadrži vjerojatnosti događaja (prijelaza iz stanja ja u stanje j), koji čine potpunu skupinu, pa je zbroj vjerojatnosti tih događaja jednak jedan:

Označimo s p ij (n) vjerojatnost da će kao rezultat n koraka (testova) sustav prijeći iz stanja i u stanje j . Na primjer p 25 (10) - vjerojatnost prijelaza iz drugog stanja u peto u deset koraka. Uočimo da za n=1 dobivamo prijelazne vjerojatnosti p ij (1)=p ij .
Suočeni smo sa zadatkom: poznavajući vjerojatnosti prijelaza p ij , pronaći vjerojatnosti p ij (n) prijelaza sustava iz stanja ja u stanje j po n korake. Da bismo to učinili, uvodimo posrednik (između ja i j) stanje r. Drugim riječima, pretpostavit ćemo da iz početnog stanja ja po m koraka, sustav će prijeći u srednje stanje r s vjerojatnošću p ij (n-m) , nakon čega, za preostalo n-m koraka iz međustanja r prijeći će u konačno stanje j s vjerojatnošću p ij (n-m) . Prema formuli ukupne vjerojatnosti dobivamo:
.
Ova formula se naziva Markovljeva jednakost. Pomoću ove formule možete pronaći sve vjerojatnosti p ij (n) i, ​​prema tome, samu matricu P n. Budući da matrični račun brže vodi do cilja, zapišimo matričnu relaciju koja proizlazi iz dobivene formule u općem obliku.
Izračunajte prijelaznu matricu Markovljevog lanca u tri koraka pomoću dobivene formule:

Odgovor:.

Zadatak #1. Matrica prijelazne vjerojatnosti za Markovljev lanac je:
.
Raspodjela stanja u trenutku t=0 određena je vektorom:
π 0 \u003d (0,5; 0,2; 0,3)
Pronaći: a) raspodjela po stanjima u trenucima t=1,2,3,4 .
c) stacionarna raspodjela.