Ievads Markova ķēdēs ar piemēriem - Markova ķēdes ar Python

Ievads Markova ķēdēs:

Vai esat kādreiz aizdomājušies, kā Google ierindo tīmekļa lapas? Ja esat veicis pētījumu, jums jāzina, ka tajā tiek izmantots PageRank algoritms, kura pamatā ir Markova ķēžu ideja. Šis raksts par Markova ķēžu ievadu palīdzēs jums saprast Markova ķēžu pamatideju un to, kā tās var modelēt kā reālu problēmu risinājumu.

Šeit ir saraksts ar tēmām, kuras tiks apskatītas šajā emuārā:

1. Kas ir Markova ķēde?
2. Kas ir Markova īpašums?
3. Izpratne par Markova ķēdēm ar piemēru
4. Kas ir pārejas matrica?
5. Markova ķēde pitonā
6. Markova ķēdes lietojumi

Lai iegūtu padziļinātas zināšanas par datu zinātni un mašīnmācīšanos, izmantojot Python, varat reģistrēties tiešraidē autors Edureka ar diennakts atbalstu un piekļuvi mūža garumā.

Kas ir Markova ķēde?

Andrejs Markovs pirmo reizi ieviesa Markova ķēdes 1906. gadā. Viņš skaidroja Markova ķēdes šādi:

Stohastisks process, kas satur nejaušus mainīgos, pārejot no viena stāvokļa uz citu atkarībā no noteiktiem pieņēmumiem un noteiktiem varbūtības noteikumiem.

Šie nejauši mainīgie mainās no viena stāvokļa uz otru, pamatojoties uz svarīgu matemātisko īpašību, ko sauc Markova īpašums.

Tādējādi mēs nonākam pie jautājuma:

Kas ir Markova īpašums?

Diskrētais laiks Markova rekvizīts apgalvo, ka aprēķinātā nejaušā procesa pārejas varbūtība uz nākamo iespējamo stāvokli ir atkarīga tikai no pašreizējā stāvokļa un laika un tā nav atkarīga no stāvokļu virknes, kas bija pirms tā.

Fakts, ka nejaušā procesa nākamā iespējamā darbība / stāvoklis nav atkarīgs no iepriekšējo stāvokļu secības, padara Markova ķēdes par procesu bez atmiņas, kas atkarīgs tikai no mainīgā pašreizējā stāvokļa / darbības.

Iegūsim to matemātiski:

Ļaujiet nejaušam procesam būt {Xm, m = 0,1,2, ⋯}.

Šis process ir Markova ķēde tikai tad, ja

Markova ķēde - ievads Markova ķēdēm - Edureka

visiem m, j, i, i0, i1, ⋯ im & mīnus1

Galīgam skaitam stāvokļu, S = {0, 1, 2, ⋯, r}, to sauc par ierobežotu Markova ķēdi.

P (Xm + 1 = j | Xm = i) šeit apzīmē pārejas varbūtības pārejai no viena stāvokļa uz otru. Šeit mēs pieņemam, ka pārejas varbūtības nav atkarīgas no laika.

Tas nozīmē, ka P (Xm + 1 = j | Xm = i) nav atkarīgs no ‘m’ vērtības. Tāpēc mēs varam apkopot,

system.exit (0)

Markova ķēžu formula - ievads Markova ķēdēm - Edureka

Tātad šis vienādojums pārstāv Markova ķēde.

Tagad sapratīsim, kādas tieši ir Markova ķēdes ar piemēru.

Markova ķēdes piemērs

Pirms sniegšu jums piemēru, definēsim, kas ir Markova modelis:

Kas ir Markova modelis?

Markova modelis ir stohastisks modelis, kas modelē nejaušus mainīgos tādā veidā, lai mainīgie sekotu Markova īpašībai.

Tagad sapratīsim, kā darbojas Markova modelis, izmantojot vienkāršu piemēru.

Kā minēts iepriekš, Markova ķēdes tiek izmantotas teksta ģenerēšanas un automātiskās pabeigšanas lietojumprogrammās. Šajā piemērā mēs aplūkosim (izlases) teikuma piemēru un redzēsim, kā to var modelēt, izmantojot Markova ķēdes.

Markova ķēžu piemērs - ievads Markova ķēdēm - Edureka

Iepriekšējais teikums ir mūsu piemērs, es zinu, ka tam nav lielas jēgas (tam nav jābūt), tas ir teikums, kurā ir nejauši vārdi, kur:

1. Atslēgas apzīmē teikumā unikālos vārdus, t.i., 5 taustiņus (viens, divi, krusa, laimīgs, edureka)

2. Žetoni apzīmē vārdu kopējo skaitu, t.i., 8 žetonus.

Virzoties uz priekšu, mums jāsaprot šo vārdu sastopamības biežums, zemāk redzamajā diagrammā parādīts katrs vārds kopā ar skaitli, kas apzīmē šī vārda biežumu.

Atslēgas un frekvences - ievads Markova ķēdēm - Edureka

Tātad kreisā kolonna šeit apzīmē taustiņus, bet labā kolonna - frekvences.

No iepriekš minētās tabulas mēs varam secināt, ka atslēga ‘edureka’ parādās četrreiz vairāk nekā jebkura cita atslēga. Ir svarīgi secināt par šādu informāciju, jo tā var mums palīdzēt paredzēt, kāds vārds varētu rasties noteiktā laika brīdī. Ja es uzminētu minējumu par nākamo vārdu teikuma piemērā, es eju ar vārdu ‘edureka’, jo tam ir vislielākā varbūtība.

Runājot par varbūtību, ir vēl viens pasākums, par kuru jums jāzina svērtie sadalījumi.

Mūsu gadījumā “edureka” svērtais sadalījums ir 50% (4/8), jo tā biežums ir 4 no kopējiem 8 žetoniem. Pārējiem taustiņiem (viens, divi, krusa, laimīgi) visiem ir 1/8 iespēja parādīties (& asimps 13%).

Tagad, kad mums ir izpratne par svērto sadalījumu un priekšstats par to, kā konkrēti vārdi parādās biežāk nekā citi, mēs varam turpināt nākamo daļu.

Izpratne par Markova ķēdēm - ievads Markova ķēdēm - Edureka

Iepriekš redzamajā attēlā es esmu pievienojis divus papildu vārdus, kas apzīmē teikuma sākumu un beigas. Jūs sapratīsit, kāpēc es to izdarīju tālāk esošajā sadaļā.

Tagad piešķirsim arī šo taustiņu biežumu:

Atjauninātas atslēgas un frekvences - ievads Markova ķēdēm - Edureka

Tagad izveidosim Markova modeli. Kā minēts iepriekš, Markova modeli izmanto, lai modelētu nejaušus mainīgos konkrētā stāvoklī tādā veidā, ka šo mainīgo nākotnes stāvokļi ir atkarīgi tikai no to pašreizējā stāvokļa, nevis no pagātnes stāvokļiem.

Tātad būtībā Markova modelī, lai prognozētu nākamo stāvokli, mums jāņem vērā tikai pašreizējais stāvoklis.

Zemāk redzamajā diagrammā jūs varat redzēt, kā katrs mūsu teikuma marķieris noved pie cita. Tas parāda, ka nākotnes stāvoklis (nākamais marķieris) ir balstīts uz pašreizējo stāvokli (pašreizējais marķieris). Tātad tas ir pats pamatnoteikums Markova modelī.

Zemāk redzamā diagramma parāda, ka ir žetonu pāri, kur katrs žetons pārī ved uz otru tajā pašā pārī.

Markova ķēžu pāri - ievads Markova ķēdēm - Edureka

Zemāk redzamajā diagrammā esmu izveidojis strukturālu attēlojumu, kas parāda katru atslēgu ar nākamo iespējamo žetonu masīvu, ar kuru to var savienot pārī.

Markova ķēžu pāru masīvs - ievads Markova ķēdēm - Edureka

Apkopojot šo piemēru, apsveriet scenāriju, kurā jums būs jāveido teikums, izmantojot iepriekšminētajā piemērā redzēto atslēgu un žetonu masīvu. Pirms mēs izskatām šo piemēru, vēl viens svarīgs moments ir tas, ka mums jānorāda divi sākotnējie pasākumi:

1. Sākotnējais varbūtības sadalījums (t.i. sākuma stāvoklis brīdī = 0, (taustiņš ‘Sākt’))

2. Pārejas varbūtība pāriet no viena stāvokļa uz citu (šajā gadījumā varbūtība pāriet no viena marķiera uz otru)

Mēs esam definējuši svērto sadalījumu pašā sākumā, tāpēc mums ir varbūtības un sākotnējais stāvoklis, tagad turpināsim ar piemēru.

• Tātad, lai sāktu ar sākotnējo pilnvaru, ir [Sākt]

• Tālāk mums ir tikai viens iespējamais marķieris, t.i., [viens]

• Pašlaik teikumā ir tikai viens vārds, t.i., “viens”

• No šī marķiera nākamais iespējamais marķieris ir [edureka]

• Teikums tiek atjaunināts uz “viena edureka”

• No [edureka] mēs varam pāriet uz jebkuru no šiem žetoniem [divi, krusa, laimīgs, beigas]

• Pastāv 25% iespēja, ka tiek izvēlēti ‘divi’, tas, iespējams, radīs sākotnējo teikumu (viens edureka divi edureka krusa edureka laimīgs edureka). Tomēr, ja tiek izvēlēts ‘beigas’, process apstājas, un mēs galu galā ģenerēsim jaunu teikumu, t.i., ‘viena edureka’.

Paglaudiet sev muguru, jo jūs vienkārši uzbūvējat Markova modeli un caur to izskrējāt testa lietu. Apkopojot iepriekš minēto piemēru, mēs pamatā izmantojām pašreizējo stāvokli (pašreizējais vārds), lai noteiktu nākamo stāvokli (nākamo vārdu). Un tieši tas ir Markova process.

Tas ir stohastisks process, kurā nejauši mainīgie mainās no viena stāvokļa uz otru tādā veidā, ka mainīgā lieluma nākotnes stāvoklis ir atkarīgs tikai no pašreizējā stāvokļa.

Pārejam uz nākamo soli un šim piemēram uzzīmēsim Markova modeli.

Valsts pārejas diagramma - ievads Markova ķēdēm - Edureka

Šis skaitlis ir pazīstams kā valsts pārejas diagramma. Mēs par to vairāk runāsim zemāk esošajā sadaļā, tagad tikai atcerieties, ka šī diagramma parāda pārejas un varbūtību no viena stāvokļa uz otru.

Ievērojiet, ka katrs ovāls attēlā attēlo atslēgu un bultiņas ir vērstas uz iespējamiem taustiņiem, kas tam var sekot. Arī svars uz bultiņām apzīmē varbūtība vai svērtais sadalījums pārejai no / uz attiecīgajiem stāvokļiem.

Tātad viss bija par to, kā darbojas Markova modelis. Tagad mēģināsim izprast dažas svarīgas Markova procesa terminoloģijas.

Kas ir pārejas varbūtības matrica?

Iepriekšējā sadaļā mēs apspriedām Markova modeļa darbību ar vienkāršu piemēru, tagad sapratīsim matemātiskās terminoloģijas Markova procesā.

Markova procesā mēs izmantojam matricu, lai attēlotu pārejas varbūtības no viena stāvokļa uz otru. Šo matricu sauc par Pārejas jeb varbūtības matricu. To parasti apzīmē ar P.

Pārejas matrica - ievads Markova ķēdēs - Edureka

Piezīme: pij & ge0 un ‘i’ visām vērtībām ir

kā klonēt objektu Java

Pārejas matricas formula - ievads Markova ķēdēm - Edureka

Ļaujiet man to paskaidrot. Pieņemot, ka mūsu pašreizējais stāvoklis ir ‘i’, nākamajam vai gaidāmajam stāvoklim jābūt vienam no potenciālajiem stāvokļiem. Tāpēc, ņemot visu k vērtību summēšanu, mums tā jāsaņem.

Kas ir valsts pārejas diagramma?

Markova modeli attēlo stāvokļa pārejas diagramma. Diagramma parāda pārejas starp dažādiem stāvokļiem Markova ķēdē. Sapratīsim pārejas matricu un stāvokļa pārejas matricu ar piemēru.

Pārejas matricas piemērs

Apsveriet Markova ķēdi ar trim stāvokļiem 1, 2 un 3 un šādām varbūtībām:

Pārejas matricas piemērs - ievads Markova ķēdēs - Edureka

Valsts pārejas diagrammas piemērs - ievads Markova ķēdēm - Edureka

Iepriekš minētā diagramma attēlo Markova ķēdes stāvokļa pārejas diagrammu. Šeit 1,2 un 3 ir trīs iespējamie stāvokļi, un bultiņas, kas norāda no viena stāvokļa uz citiem stāvokļiem, apzīmē pārejas varbūtības pij. Kad, pij = 0, tas nozīmē, ka nav pārejas starp stāvokli ‘i’ un stāvokli ‘j’.

Tagad, kad mēs zināt matemātiku un Markova ķēžu loģiku, palaidīsim vienkāršu demonstrāciju un sapratīsim, kur var izmantot Markova ķēdes.

Markova ķēde pitonā

Lai palaistu šo demonstrāciju, es izmantoju Python, tādēļ, ja nezināt Python, varat apskatīt šādus emuārus:

2. Kā iemācīties Python 3 no Scratch - ceļvedis iesācējiem

Tagad sāksim ar kodēšanu!

Markova ķēdes teksta ģenerators

Problēmas izklāsts: Lai lietotu Markova īpašumu un izveidotu Markova modeli, kas var ģenerēt teksta simulācijas, pētot Donalda Trampa runas datu kopu.

Datu kopas apraksts: Teksta failā ir saraksts ar Donalda Trampa 2016. gada runām.

Loģika: Lietojiet Markova īpašumu, lai ģenerētu Donalda Trampa runu, ņemot vērā katru runā izmantoto vārdu un katram vārdam, izveidojiet nākamo vārdu vārdnīcu.

ir kotlins labaks par java

1. darbība: importējiet nepieciešamos iepakojumus

importēt numpy kā np

2. darbība: izlasiet datu kopu

trump = open ('C: //Users//NeelTemp//Desktop//demos//speeches.txt', encoding = 'utf8'). read () #display data print (trump) SPEECH 1 ... Paldies tu tik daudz. Tas ir tik jauki. Vai viņš nav lielisks puisis. Viņš nesaņem godīgu presi, viņš to nedara. Tas vienkārši nav godīgi. Un man jāsaka, ka esmu šeit un ļoti spēcīgi šeit, jo es ļoti cienu Stīvu Kingu, tāpat ļoti cienu arī Citizens United, Deividu un visus, kā arī milzīgu pretestību tējas ballītei. Arī arī Aiovas iedzīvotāji. Viņiem ir kaut kas kopīgs. Cītīgi cilvēki ....

3. darbība: sadaliet datu kopu atsevišķos vārdos

corpus = trump.split () # Parādiet korpusa druku (korpusu) 'spēcīgs', 'bet', 'nav', 'spēcīgs', 'līdzīgs', 'mums', 'Irāna', 'ir', ' sēklas ”,“ terors ”, ...

Pēc tam izveidojiet funkciju, kas runās ģenerē dažādus vārdu pārus. Lai ietaupītu vietu, mēs izmantosim ģeneratora objektu.

4. solis: Pāru izveide atslēgām un papildu vārdiem

def make_pairs (corpus): i diapazonā (len (corpus) - 1): raža (corpus [i], corpus [i + 1]) pāri = make_pairs (corpus)

Pēc tam inicializēsim tukšu vārdnīcu, lai glabātu vārdu pārus.

Gadījumā, ja pirmais pāra vārds jau ir atslēgvārds vārdnīcā, vienkārši pievienojiet nākamo potenciālo vārdu vārdu sarakstam, kas seko vārdam. Bet, ja vārds nav atslēga, tad vārdnīcā izveidojiet jaunu ierakstu un piešķiriet atslēgu vienādai ar pāra pirmo vārdu.

5. darbība: pievienojiet vārdnīcu

word_dict = {} vārdam_1, vārds_2 pāros: ja vārds_1 vārdos_dikt.atslēgas (): vārds_dikts [vārds_1] .pievienot (vārds_2) cits: vārds_dikts [vārds_1] = [vārds_2]

Tālāk mēs nejauši izvēlamies vārdu no korpusa, kas sāks Markova ķēdi.

6. darbība: izveidojiet Markova modeli

# nejauši izvēlieties pirmo vārdu first_word = np.random.choice (corpus) # Izvēlieties pirmo vārdu kā lielo burtu, lai izvēlētais vārds netiktu ņemts no teikuma starplaika, kamēr first_word.islower (): # Sāciet ķēdi no izvēlētā vārda ķēde = [pirmais_vārds] #Inicializējiet stimulēto vārdu skaitu n_words = 20

Pēc pirmā vārda katrs ķēdes vārds tiek nejauši atlasīts no to vārdu saraksta, kuri sekojuši šim konkrētajam vārdam Trampa tiešajās runās. Tas ir parādīts zemāk esošajā koda fragmentā:

i diapazonā (n_words): chain.append (np.random.choice (word_dict [ķēde [-1]]))

7. solis: prognozes

Visbeidzot, parādīsim stimulēto tekstu.

#Join atgriež ķēdi kā virknes druku ('' .join (chain)) Neticamo cilvēku skaits. Un Hilarijai Klintonei ir mūsu cilvēki, un tik lielisks darbs. Un mēs nepārspēsim Obamu

Tātad šis ir ģenerētais teksts, ko ieguvu, ņemot vērā Trampa runu. Tam var nebūt lielas jēgas, bet tas ir pietiekami labs, lai jūs saprastu, kā Markova ķēdes var izmantot, lai automātiski ģenerētu tekstus.

Tagad apskatīsim vēl dažas lietojumprogrammas un kā tās tiek izmantotas reālu problēmu risināšanā.

Markova ķēdes lietojumi

Šeit ir saraksts ar Markova ķēžu reālajām lietojumprogrammām:

1. Google PageRank: Visu tīmekli var uzskatīt par Markova modeli, kur katra tīmekļa lapa var būt stāvoklis, un saites vai atsauces starp šīm lapām var uzskatīt par pārejām ar varbūtību. Tātad būtībā, neatkarīgi no tā, kurā tīmekļa lapā sākat sērfot, iespēja nokļūt noteiktā tīmekļa vietnē, teiksim, X ir fiksēta varbūtība.

2. Rakstīt vārdu paredzēšanu: Ir zināms, ka gaidāmo vārdu prognozēšanai tiek izmantotas Markova ķēdes. Tos var izmantot arī automātiskajā pabeigšanā un ieteikumos.

3. Subreddit simulācija: Protams, jūs esat saskāries ar Reddit un esat mijiedarbojies ar kādu no viņu pavedieniem vai subreddits. Reddit izmanto subreddit simulatoru, kas patērē milzīgu daudzumu datu, kas satur visus viņu grupās notikušos komentārus un diskusijas. Izmantojot Markova ķēdes, simulators rada vārdu varbūtību, lai izveidotu komentārus un tēmas.

4. Teksta ģenerators: Markova ķēdes visbiežāk izmanto, lai ģenerētu fiktīvus tekstus vai veidotu lielas esejas un apkopotu runas. To lieto arī vārdu ģeneratoros, kurus redzat tīmeklī.

Tagad, kad jūs zināt, kā atrisināt reālās problēmas, izmantojot Markova ķēdes, esmu pārliecināts, ka vēlaties uzzināt vairāk. Šeit ir saraksts ar emuāriem, kas palīdzēs jums sākt izmantot citus statistikas jēdzienus:

Ar to mēs esam nonākuši pie šī Markov Chains bloga Ievads beigām. Ja jums ir kādi jautājumi par šo tēmu, lūdzu, atstājiet komentāru zemāk, un mēs ar jums sazināsimies.

Sekojiet līdzi jaunākajiem emuāriem par populārākajām tehnoloģijām.

Ja jūs meklējat tiešsaistes strukturētas apmācības datu zinātnē, edureka! ir īpaši kurēts programma, kas palīdz jums iegūt zināšanas statistikas, datu apstrādes, izpētes datu analīzes, mašīnmācīšanās algoritmu, piemēram, K-Means Cluster, lēmumu koku, Random Forest, Naive Bayes jomā. Jūs uzzināsiet arī laika sērijas, teksta ieguves jēdzienus un ievadu dziļai mācībai. Drīz sākas jaunas sērijas šim kursam !!