Sissejuhatus Markovi ahelatesse näidetega - Markovi ketid Pythoniga

Sissejuhatus Markovi ketidesse:

Kas olete kunagi mõelnud, kuidas Google veebisaite järjestab? Kui olete oma uurimistöö teinud, peate teadma, et see kasutab Markovi ahelate ideel põhinevat PageRanki algoritmi. See artikkel Markovi ahelate sissejuhatuse kohta aitab teil mõista Markovi kettide põhiideed ja seda, kuidas neid saab modelleerida reaalsete probleemide lahendusena.

Siin on loetelu käsitletavatest teemadest selles blogis:

1. Mis on Markovi kett?
2. Mis on Markovi vara?
3. Markovi ahelate mõistmine näitega
4. Mis on siirdemaatriks?
5. Markovi kett Pythonis
6. Markovi keti rakendused

Põhjalike teadmiste saamiseks andmeteaduse ja masinõppe kohta Pythoni abil saate registreeruda otseülekandeks autor Edureka 24/7 toe ja eluaegse juurdepääsuga.

Mis on Markovi kett?

Andrei Markov tutvustas Markovi kette esimest korda aastal 1906. Ta selgitas Markovi kette järgmiselt:

Stohhastiline protsess, mis sisaldab juhuslikke muutujaid, üleminek ühest olekust teise, sõltuvalt teatud eeldustest ja kindlatest tõenäosusreeglitest.

Need juhuslikud muutujate üleminek ühelt olekule teisele, tuginedes olulisele matemaatilisele omadusele, mida nimetatakse Markovi kinnisvara.

See viib meid küsimuse juurde:

Mis on Markovi vara?

Diskreetne aeg Markovi omadus väidab, et juhusliku protsessi arvutatud tõenäoline üleminek järgmisse võimalikku olekusse sõltub ainult hetkeseisust ja ajast ning see ei sõltu sellele eelnenud seisundiseeriast.

Asjaolu, et juhusliku protsessi järgmine võimalik toiming / olek ei sõltu eelnevate olekute järjestusest, muudab Markovi ahelad mäluvaba protsessiks, mis sõltub ainult muutuja hetkeseisust / toimest.

Tuletame selle matemaatiliselt:

Olgu juhuslik protsess {Xm, m = 0,1,2, ⋯}.

See protsess on Markovi kett ainult siis, kui

Markovi kett - sissejuhatus Markovi ketidesse - Edureka

kõigi m, j, i, i0, i1, ⋯ im & miinus1 jaoks

Lõpliku arvu olekute korral, S = {0, 1, 2, ⋯, r}, nimetatakse seda lõplikuks Markovi ahelaks.

P (Xm + 1 = j | Xm = i) tähistab siin ülemineku tõenäosust ühest olekust teise üleminekuks. Siin eeldame, et ülemineku tõenäosus on ajast sõltumatu.

Mis tähendab, et P (Xm + 1 = j | Xm = i) ei sõltu ‘m’ väärtusest. Seetõttu võime kokku võtta

Markovi ketivalem - sissejuhatus Markovi ketidesse - Edureka

Nii et see võrrand tähistab Markovi kett.

Nüüd saame näitega aru, mis täpselt on Markovi ketid.

Markovi keti näide

Enne kui toon teile näite, määratleme, mis on Markovi mudel:

Mis on Markovi mudel?

Markovi mudel on stohhastiline mudel, mis modelleerib juhuslikke muutujaid nii, et muutujad järgiksid Markovi omadust.

Nüüd mõistame lihtsa näitega, kuidas Markovi mudel töötab.

Nagu varem mainitud, kasutatakse Markovi kette teksti genereerimise ja automaatse täiendamise rakendustes. Selle näite puhul vaatleme näite (juhuslikku) lauset ja näeme, kuidas seda saab Markovi ahelate abil modelleerida.

Markovi keti näide - sissejuhatus Markovi ketidesse - Edureka

Ülaltoodud lause on meie näide, ma tean, et sellel pole palju mõtet (see ei peagi olema), see on lause, mis sisaldab juhuslikke sõnu, kus:

1. Võtmed tähistage lauses ainulaadseid sõnu, st 5 klahvi (üks, kaks, rahe, õnnelik, edureka)

2. Märgid tähistavad sõnade koguarvu, s.o 8 märki.

Edasi liikudes peame mõistma nende sõnade esinemissagedust, allpool toodud diagramm näitab iga sõna koos numbriga, mis tähistab selle sõna sagedust.

Võtmed ja sagedused - sissejuhatus Markovi ketidesse - Edureka

Nii et vasak veerg tähistab siin klahve ja parem veerg sagedusi.

__init__ python 3

Ülaltoodud tabelist võime järeldada, et võti ‘edureka’ tuleb 4x üles sama palju kui mis tahes muu võti. Sellist teavet on oluline järeldada, sest see aitab meil ennustada, milline sõna võib teatud ajahetkel esineda. Kui peaksin näitelause järgmise sõna kohta aimama, läheksin sõnaga „edureka”, kuna selle esinemise tõenäosus on kõige suurem.

Tõenäosusest rääkides on veel üks meede, mida peate teadma kaalutud jaotused.

Meie puhul on „edureka” kaalutud jaotus 50% (4/8), kuna selle sagedus on 4 kogu 8 märgist. Ülejäänud võtmetel (üks, kaks, rahe, õnnelik) on kõigil 1/8 võimalus esineda (& asümp 13%).

Nüüd, kui meil on arusaam kaalutud jaotusest ja idee selle kohta, kuidas konkreetseid sõnu teistest sagedamini esineb, võime jätkata järgmise osaga.

Markovi ahelate mõistmine - sissejuhatus Markovi ketidesse - Edureka

Ülaltoodud joonisel olen lisanud kaks täiendavat sõna, mis tähistavad lause algust ja lõppu, saate aru, miks ma seda tegin, järgmises jaotises.

Nüüd määrame ka nende klahvide sageduse:

Uuendatud võtmed ja sagedused - sissejuhatus Markovi ketidesse - Edureka

Nüüd loome Markovi mudeli. Nagu varem mainitud, kasutatakse Markovi mudelit juhuslike muutujate modelleerimiseks konkreetses olekus nii, et nende muutujate tulevased olekud sõltuvad ainult nende hetkeseisundist, mitte mineviku olekutest.

Nii et põhimõtteliselt Markovi mudelis peame järgmise oleku ennustamiseks arvestama ainult praeguse olekuga.

Alloleval skeemil näete, kuidas iga meie lauses olev märk viib teise juurde. See näitab, et tulevane olek (järgmine märk) põhineb praegusel olekul (praegune märk). Nii et see on Markovi mudeli põhireegel.

Allpool olev diagramm näitab, et on olemas märgimepaare, kus iga paaris olev märgis viib teise samas paaris oleva märgini.

Markovi ketipaarid - sissejuhatus Markovi ketidesse - Edureka

Alloleval skeemil olen loonud struktuurse kujutise, mis näitab iga võtit koos võimalike järgmiste märkide massiiviga, millega see saab paaristada.

Massiiv Markovi ketipaare - sissejuhatus Markovi ketidesse - Edureka

Selle näite kokkuvõtteks kaaluge stsenaariumi, kus peate moodustama lause, kasutades võtmete ja märkide massiivi, mida nägime ülaltoodud näites. Enne selle näite läbivaatamist on veel üks oluline punkt, et peame määrama kaks esialgset meedet:

peakokk vs nukk vs sool

1. Esialgne tõenäosusjaotus (s.t algusolek ajal = 0, (võti ‘Start’))

2. Ülemineku tõenäosus ühest olekust teise hüpata (antud juhul ühelt märgilt teisele ülemineku tõenäosus)

Oleme määratlenud kaalutud jaotuse alguses ise, nii et meil on tõenäosused ja algseisund, jätkame nüüd näitega.

• Nii et algse märgiga on [Start]

• Järgmisena on meil ainult üks võimalik märk, st [üks]

• Praegu on lausel ainult üks sõna, st ‘üks’

• Sellest märgist on järgmine võimalik märk [edureka]

• Lause ajakohastatakse sõnaga „üks edureka”

• [Edurekast] saame liikuda ükskõik millisele järgmistest märkidest [kaks, rahe, õnnelik, lõpp]

• On 25% tõenäosus, et ‘kaks’ valitakse, selle tulemuseks võib olla algse lause moodustamine (üks edureka kaks edureka rahe edureka õnnelik edureka). Kui aga valida ‘lõpp’, siis protsess peatub ja lõpuks genereerime uue lause, st ‘ühe edureka’.

Tee endale pai, sest sa lihtsalt ehitad Markovi mudeli ja viisid selle läbi proovikoja. Ülaltoodud näite kokkuvõtteks kasutasime järgmise oleku (järgmise sõna) määramiseks põhimõtteliselt praegust olekut (olev sõna). Ja täpselt see on Markovi protsess.

See on stohhastiline protsess, kus juhuslikud muutujad lähevad ühest olekust teise nii, et muutuja tulevane olek sõltub ainult praegusest olekust.

Võtame selle järgmise sammu ja joonistame selle näite jaoks välja Markovi mudeli.

Riiklik üleminekudiagramm - sissejuhatus Markovi ketidesse - Edureka

Ülaltoodud joonist nimetatakse riigi üleminekudiagrammiks. Sellest räägime allpool jaotises rohkem, pidage nüüd meeles, et see diagramm näitab üleminekuid ja tõenäosust ühest olekust teise.

Pange tähele, et joonisel kujutatud iga ovaal tähistab võtit ja nooled on suunatud võimalike klahvide suunas, mis võivad seda järgida. Samuti tähistavad noolte kaalud vastavatest olekutest / nendesse siirdumise tõenäosus või kaalutud jaotus.

Nii et see puudutas kõike seda, kuidas Markovi mudel töötab. Proovime nüüd mõista mõnda olulist terminoloogiat Markovi protsessis.

Mis on ülemineku tõenäosuse maatriks?

Ülaltoodud jaotises käsitlesime Markovi mudeli töötamist lihtsa näitega, mõistame nüüd Markovi protsessi matemaatilisi terminoloogiaid.

Markovi protsessis kasutame maatriksit ühest olekust teise siirdumise tõenäosuste esitamiseks. Seda maatriksit nimetatakse siirde- või tõenäosusmaatriksiks. Seda tähistatakse tavaliselt P.

Siirdemaatriks - sissejuhatus Markovi ketidesse - Edureka

Pange tähele, et kõigi väärtuste pij & ge0 ja 'i' on

Siirdemaatriksi valem - sissejuhatus Markovi ahelatesse - Edureka

Las ma seletan seda. Eeldades, et meie praegune seisund on „i”, peab järgmine või eelseisev seisund olema üks potentsiaalsetest seisunditest. Seega, kui võtame kõigi k väärtuste liitmise, peame selle saama.

Mis on riigi ülemineku skeem?

Markovi mudelit esindab oleku ülemineku skeem. Diagramm näitab üleminekuid Markovi keti erinevate olekute vahel. Mõistame siirdemaatriksit ja olekuülekandemaatriksit näitega.

Siirdemaatriksi näide

Vaatleme Markovi ketti, kus on kolm olekut 1, 2 ja 3 ning järgmised tõenäosused:

Siirdemaatriksi näide - sissejuhatus Markovi ahelatesse - Edureka

Riigi üleminekuskeemi näide - sissejuhatus Markovi ketidesse - Edureka

Ülaltoodud diagramm tähistab Markovi keti olekuseire diagrammi. Siin on 1,2 ja 3 kolm võimalikku olekut ning ühest olekust teise olekusse suunatud nooled tähistavad üleminekutõenäosusi pij. Kui, pij = 0, tähendab see, et oleku ‘i’ ja oleku ’j’ vahel pole üleminekut.

Nüüd, kui meie tundke matemaatikat ja Markovi ahelate taga olevat loogikat, laseme läbi lihtsa demo ja mõistame, kus saab kasutada Markovi kette.

Markovi kett Pythonis

Selle demo käitamiseks kasutan Pythoni, nii et kui te ei tunne Pythoni, võite läbida järgmised blogid:

2. Kuidas õppida Python 3 rakendust Scratch - juhend algajatele

Alustame nüüd kodeerimisega!

Markovi keti tekstigeneraator

Probleemipüstituses: Markovi omaduse rakendamiseks ja Markovi mudeli loomiseks, mis saab tekitada Donald Trumpi kõneandmete kogumit uurides tekstisimulatsioone.

Andmekomplekti kirjeldus: Tekstifail sisaldab loetelu kõnedest, mille pidas Donald Trump 2016. aastal.

Loogika: Rakendage Markovi vara Donaldi Trumpi kõne genereerimiseks, võttes arvesse kõiki kõnes kasutatud sõnu ja iga sõna jaoks, looge sõnad, mida kasutatakse järgmisena.

informaatika teisenduste tüübid

1. samm: importige vajalikud paketid

impordi numpy nimega np

2. samm: lugege andmekomplekti

trump = open ('C: //Users//NeelTemp//Desktop//demos//speeches.txt', encoding = 'utf8'). read () #näita andmete print (trump) SPEECH 1 ... Täname sa nii palju. See on nii tore. Eks ta ole vahva tüüp. Ta ei saa ausat ajakirjandust, ta ei saa seda. See pole lihtsalt õiglane. Ja ma pean teile ütlema, et olen siin ja väga tugevalt siin, sest austan väga Steve Kingi ja austan ka Citizens Unitedit, Davidit ja kõiki ning tohutut suhtumist teepeo vastu. Samuti ka Iowa inimesed. Neil on midagi ühist. Töökad inimesed ....

3. samm: jagage andmekogum üksikuteks sõnadeks

korpus = trump.split () # Kuva korpuse trükk (korpus) 'võimas', 'aga', 'mitte', 'võimas', 'nagu', 'meie', 'Iraan', 'on', ' külvatud ”,„ terror ”, ...

Järgmisena looge funktsioon, mis genereerib kõnedes erinevad sõnapaarid. Ruumi kokkuhoiuks kasutame generaatori objekti.

4. samm: klahvide ja järelsõnade paaride loomine

def make_pairs (korpus): i jaoks vahemikus (len (korpus) - 1): saagikus (korpus [i], korpus [i + 1]) paarid = make_pairs (korpus)

Järgmisena lähtestagem sõnapaaride salvestamiseks tühi sõnastik.

Kui paari esimene sõna on juba sõnaraamatu võti, lisage lihtsalt järgmine potentsiaalne sõna sõnale järgnevate sõnade loendisse. Kuid kui see sõna pole võti, siis looge sõnastikus uus kirje ja määrake võti võrdseks paari esimese sõnaga.

5. samm: sõnastiku lisamine

word_dict = {} sõnale_1, sõna_2 paarides: kui word_1 sõnale_dict.keys (): word_dict [word_1] .app (word_2) else: word_dict [word_1] = [word_2]

Järgmisena valime korpusest juhuslikult sõna, mis käivitab Markovi keti.

6. samm: ehitage Markovi mudel

# juhuslikult vali esimene sõna first_word = np.random.choice (korpus) # Valige esimene sõna suurtähega, nii et valitud sõna ei võeta lause vahelt, samas kui first_word.islower (): # Alustage ketti valitud sõna ahel = [esimene_sõna] #Initsialiseerige stimuleeritud sõnade arv n_words = 20

Esimese sõna järel valitakse ahela igast sõnast juhuslikult nende sõnade loend, mis on Trumpi otsekõnedes sellele konkreetsele sõnale järgnenud. Seda näitab allolev koodilõik:

i vahemikus (n_words): kett.append (np.juhuslik.valik (sõna_dik [ahel [-1]]))

7. samm: ennustused

Lõpuks kuvame stimuleeritud teksti.

#Join tagastab keti stringitrükina ('' .join (kett)) Uskumatute inimeste arv. Ja Hillary Clintonil on meie inimesed ja nii hea töö. Ja me ei peksa Obamat

Nii et see on loodud tekst, mille sain Trumpi kõnet arvestades. Sellel ei pruugi olla palju mõtet, kuid see on piisavalt hea, et mõista, kuidas Markovi ahelaid saab kasutada tekstide automaatseks genereerimiseks.

Vaatame nüüd veel mõnda rakendust Markovi ketid ja kuidas neid kasutatakse reaalsete probleemide lahendamiseks.

Markovi keti rakendused

Siin on nimekiri Markovi kettide reaalsetest rakendustest:

1. Google PageRank: Kogu veebi võib käsitleda kui Markovi mudelit, kus iga veebileht võib olla olek ja nende lehtede vahelisi linke või viiteid võib pidada tõenäoliste üleminekutena. Nii et põhimõtteliselt, olenemata sellest, millisel veebilehel surfama hakkate, on võimalus pääseda kindlale veebilehele, näiteks X on kindel tõenäosus.

2. Sõnaennustamise tippimine: Tulevaste sõnade ennustamiseks kasutatakse teadaolevalt Markovi ahelaid. Neid saab kasutada ka automaatse täitmise ja soovituste tegemisel.

3. Subredditi simulatsioon: Kindlasti olete Redditiga kokku puutunud ja olete suhelnud nende ühe lõimega või alamreditsiga. Reddit kasutab subredditi simulaatorit, mis kulutab tohutul hulgal andmeid, mis sisaldavad kõiki nende gruppides peetud kommentaare ja arutelusid. Kasutades Markovi ahelaid, loob simulaator sõna-sõnalt tõenäosuse kommentaaride ja teemade loomiseks.

4. Tekstigeneraator: Markovi ahelaid kasutatakse kõige sagedamini näivate tekstide loomiseks või suurte esseede koostamiseks ja kõnede koostamiseks. Seda kasutatakse ka nimegeneraatorites, mida näete veebis.

Nüüd, kui teate, kuidas lahendada reaalses maailmas Markovi ketid, olen kindel, et soovite rohkem teada saada. Siin on loetelu blogidest, mis aitavad teil alustada teiste statistiliste mõistetega:

Sellega jõuame selle Markovi ketid sissejuhatava ajaveebi lõpuni. Kui teil on selle teema kohta küsimusi, jätke palun allpool kommentaar ja võtame teiega ühendust.

Jälgige rohkem populaarseimate tehnoloogiate ajaveebe.

Kui otsite struktureeritud veebikoolitust andmeteaduses, edureka! on spetsiaalselt kureeritud programm, mis aitab teil omandada teadmisi statistikas, andmete töötlemises, uurimuslikus andmeanalüüsis, masinõppe algoritmides nagu K-vahendite klasterdamine, otsustuspuud, juhuslik mets, naiivsed lahed Õpite ka aegridade, tekstikaevanduse ja süvendatud õppimise sissejuhatuse kontseptsioone. Varsti algavad selle kursuse uued partiid !!