Įvadas į Markovo grandines su pavyzdžiais - Markovo grandinės su „Python“

Šis straipsnis apie „Markov“ grandinių įvadą padės suprasti pagrindinę „Markov“ grandinių idėją ir tai, kaip jas galima modeliuoti naudojant „Python“.

Įvadas į Markovo grandines:

Ar kada susimąstėte, kaip „Google“ reitinguoja tinklalapius? Jei atlikote tyrimą, turite žinoti, kad jis naudoja „PageRank“ algoritmą, pagrįstą „Markov“ grandinių idėja. Šis straipsnis apie „Markov“ grandinių įvadą padės suprasti pagrindinę „Markov“ grandinių idėją ir tai, kaip jas galima modeliuoti kaip realaus pasaulio problemų sprendimą.

Pateiksime temų, kurios bus aptartos, sąrašą šiame tinklaraštyje:

  1. Kas yra Markovo grandinė?
  2. Kas yra Markovo nuosavybė?
  3. Suprasti Markovo grandines pavyzdžiu
  4. Kas yra perėjimo matrica?
  5. Markovo grandinė „Python“
  6. „Markov“ grandinės programos

Norėdami gauti išsamių žinių apie duomenų mokslą ir mašininį mokymąsi naudojant „Python“, galite užsiregistruoti tiesioginiam pokalbiui sukūrė „Edureka“ su parą visą parą ir visą gyvenimą.

Kas yra Markovo grandinė?

Pirmą kartą Andrejus Markovas pristatė „Markov“ grandines 1906 m. Jis paaiškino „Markov“ grandines taip:

sekli vs giluminė kopija java

Stochastinis procesas, apimantis atsitiktinius kintamuosius, pereinantis iš vienos būsenos į kitą, priklausomai nuo tam tikrų prielaidų ir apibrėžtų tikimybinių taisyklių.

Šie atsitiktiniai kintamieji pereina iš vienos į būseną į kitą, remdamiesi svarbia matematine savybe, vadinama Markovo nuosavybė.

Tai priveda prie klausimo:

Kas yra Markovo nuosavybė?

Diskretus laikas Markovo ypatybė teigia, kad apskaičiuota atsitiktinio proceso perėjimo į kitą galimą būseną tikimybė priklauso tik nuo esamos būsenos ir laiko ir ji nepriklauso nuo prieš tai buvusių būsenų serijos.

Tai, kad kitas galimas atsitiktinio proceso veiksmas / būsena nepriklauso nuo ankstesnių būsenų sekos, daro Markovo grandines kaip procesą be atminties, kuris priklauso tik nuo dabartinės kintamojo būsenos / veiksmo.

Išveskime tai matematiškai:

Tegu atsitiktinis procesas yra {Xm, m = 0,1,2, ⋯}.

Šis procesas yra Markovo grandinė tik tuo atveju,

Markovo grandinės formulė - įvadas į Markovo grandines - „Edureka“

Markovo grandinė - įvadas į Markovo grandines - „Edureka“

visiems m, j, i, i0, i1, ⋯ im & minus1

Esant ribotam būsenų skaičiui, S = {0, 1, 2, ⋯, r}, tai vadinama baigtine Markovo grandine.

P (Xm + 1 = j | Xm = i) čia reiškia perėjimo iš vienos būsenos į kitą tikimybę. Čia darome prielaidą, kad perėjimo tikimybės nepriklauso nuo laiko.

Tai reiškia, kad P (Xm + 1 = j | Xm = i) nepriklauso nuo ‘m’ vertės. Todėl galime apibendrinti,

Markovo grandinės formulė - įvadas į Markovo grandines - „Edureka“

Taigi ši lygtis atstovauja Markovo grandinė.

Dabar supraskime, kas tiksliai yra Markovo grandinės su pavyzdžiu.

Markovo grandinės pavyzdys

Prieš pateikdamas jums pavyzdį, apibrėžkime, kas yra Markovo modelis:

Kas yra Markovo modelis?

Markovo modelis yra stochastinis modelis, kuris modeliuoja atsitiktinius kintamuosius taip, kad kintamieji atitiktų Markovo savybę.

Dabar supraskime, kaip veikia „Markov Model“, pateikdami paprastą pavyzdį.

Kaip minėta anksčiau, „Markov“ grandinės naudojamos teksto generavimo ir automatinio užbaigimo programose. Šiame pavyzdyje mes pažvelgsime į pavyzdinį (atsitiktinį) sakinį ir pamatysime, kaip jį galima modeliuoti naudojant Markovo grandines.

Markovo grandinės pavyzdys - įvadas į Markovo grandines - „Edureka“

Ankstesnis sakinys yra mūsų pavyzdys, aš žinau, kad jis neturi daug prasmės (to nereikia), tai sakinys, kuriame yra atsitiktiniai žodžiai, kuriuose:

  1. Raktai pažymėkite unikalius sakinio žodžius, t. y. 5 raktus (vienas, du, kruša, laimingas, edureka)

  2. Žetonai žymi bendrą žodžių skaičių, t. y. 8 žetonus.

Žengdami į priekį, turime suprasti šių žodžių atsiradimo dažnumą, žemiau esančioje diagramoje parodytas kiekvienas žodis kartu su skaičiumi, kuris žymi to žodžio dažnumą.

Raktai ir dažniai - įvadas į Markovo grandines - „Edureka“

Taigi kairysis stulpelis čia žymi klavišus, o dešinysis - dažnius.

Iš pirmiau pateiktos lentelės galime padaryti išvadą, kad raktas 'edureka' atsiranda 4 kartus daugiau nei bet kuris kitas raktas. Svarbu padaryti tokią informaciją, nes tai gali padėti mums numatyti, koks žodis gali atsirasti tam tikru laiko momentu. Jei spėčiau apie kitą žodį pavyzdiniame sakinyje, eitume su „edureka“, nes jo atsiradimo tikimybė yra didžiausia.

Kalbant apie tikimybę, yra dar viena priemonė, kurią turite žinoti svertiniai paskirstymai.

Mūsų atveju „edureka“ svertinis paskirstymas yra 50% (4/8), nes jo dažnis yra 4 iš visų 8 žetonų. Likę raktai (vienas, du, kruša, laimingi) visi turi 1/8-ąją galimybę atsirasti (& asymp 13%).

Dabar, kai turime supratimą apie svertinį pasiskirstymą ir idėją, kaip konkretūs žodžiai atsiranda dažniau nei kiti, galime tęsti kitą dalį.

Suprasti Markovo grandines - įvadas į Markovo grandines - „Edureka“

Pirmiau pateiktame paveikslėlyje aš pridėjau du papildomus žodžius, kurie žymi sakinio pradžią ir pabaigą. Jūs suprasite, kodėl aš tai padariau tolesniame skyriuje.

Dabar priskirkime ir šių klavišų dažnį:

Atnaujinti raktai ir dažniai - „Markov“ grandinių įvadas - „Edureka“

Dabar sukurkime Markovo modelį. Kaip minėta anksčiau, atsitiktinių kintamųjų tam tikroje būsenoje modeliavimui naudojamas Markovo modelis taip, kad šių kintamųjų būsimos būsenos priklauso tik nuo dabartinės, o ne nuo jų praeities būsenų.

Taigi iš esmės pagal Markovo modelį, norėdami numatyti kitą būseną, turime atsižvelgti tik į dabartinę būseną.

Žemiau pateiktoje diagramoje galite pamatyti, kaip kiekvienas mūsų sakinio raktas veda prie kito. Tai rodo, kad būsima būsena (kitas prieigos raktas) remiasi dabartine būsena (esamas prieigos raktas). Taigi tai yra pagrindinė Markovo modelio taisyklė.

Žemiau pateiktoje diagramoje parodyta, kad yra žetonų porų, kur kiekvienas žetonas poroje veda prie kito toje pačioje poroje.

Markovo grandinių poros - įvadas į Markovo grandines - „Edureka“

Žemiau pateiktoje schemoje aš sukūriau struktūrinį vaizdą, kuriame kiekvienas raktas parodomas su kitų galimų žetonų masyvu, su kuriuo galima susieti.

Markovo grandinių porų masyvas - įvadas į Markovo grandines - „Edureka“

Apibendrindami šį pavyzdį, apsvarstykite scenarijų, kuriame turėsite suformuoti sakinį naudodami raktų ir žetonų masyvą, kurį matėme aukščiau pateiktame pavyzdyje. Prieš pradedant nagrinėti šį pavyzdį, dar vienas svarbus dalykas yra tai, kad turime nurodyti dvi pradines priemones:

  1. Pradinis tikimybių pasiskirstymas (t. Y. Pradinė būsena laiku = 0, (raktas „Pradėti“))

  2. Perėjimo iš vienos būsenos į kitą tikimybė (šiuo atveju tikimybė pereiti iš vieno ženklo į kitą)

Apibrėžėme svertinį paskirstymą pačioje pradžioje, taigi turime tikimybes ir pradinę būseną, dabar pereikime prie pavyzdžio.

  • Taigi, pradedant nuo pradinio prieigos rakto yra [Pradėti]

  • Toliau mes turime tik vieną galimą prieigos raktą, t. Y. [Vieną]

  • Šiuo metu sakinyje yra tik vienas žodis, t. Y. „Vienas“

  • Iš šio prieigos rakto kitas galimas prieigos raktas yra [edureka]

  • Sakinys atnaujinamas į „viena edureka“

  • Iš [edureka] galime pereiti prie bet kurio iš šių žetonų [du, kruša, laimingas, pabaiga]

  • Yra 25% tikimybė, kad bus išrinkti „du“, todėl galbūt susidarys pradinis sakinys (viena edureka du edureka kruša edureka laiminga edureka). Tačiau, jei bus pasirinkta „pabaiga“, procesas sustos ir mes sukursime naują sakinį, ty „vieną edureką“.

Paglostykite sau per nugarą, nes jūs tiesiog pastatėte „Markov Model“ ir paleidote bandomąjį atvejį. Apibendrinant pirmiau pateiktą pavyzdį, mes iš esmės naudojome esamą būseną (dabartinis žodis), norėdami nustatyti kitą būseną (kitą žodį). Ir būtent tai yra Markovo procesas.

Tai yra stochastinis procesas, kai atsitiktiniai kintamieji pereina iš vienos būsenos į kitą taip, kad būsima kintamojo būsena priklauso tik nuo esamos būsenos.

Pažvelkime į kitą žingsnį ir nupieškime šio pavyzdžio Markovo modelį.

Valstybinė perėjimo schema - įvadas į Markovo grandines - „Edureka“

Aukščiau pateiktas paveikslas yra žinomas kaip būsenos perėjimo schema. Apie tai daugiau pakalbėsime žemiau esančiame skyriuje, kol kas tiesiog nepamirškite, kad ši schema rodo perėjimus ir tikimybę iš vienos būsenos į kitą.

Atkreipkite dėmesį, kad kiekvienas paveikslo ovalas reiškia raktą, o rodyklės nukreiptos į galimus raktus, kurie gali jį sekti. Taip pat rodyklių svoriai žymi tikimybė arba svertinis pasiskirstymas iš / į atitinkamas būsenas.

Taigi viskas buvo apie tai, kaip veikia „Markov Model“. Dabar pabandykime suprasti kai kurias svarbias Markovo proceso terminologijas.

Kas yra perėjimo tikimybės matrica?

Ankstesniame skyriuje aptarėme Markovo modelio veikimą su paprastu pavyzdžiu, dabar supraskime Markovo proceso matematines terminologijas.

Markovo procese matricą naudojame perėjimo iš vienos būsenos į kitą tikimybei atspindėti. Ši matrica vadinama perėjimo arba tikimybės matrica. Paprastai tai žymima P.

Pereinamoji matrica - įvadas į Markovo grandines - „Edureka“

Atkreipkite dėmesį, kad pij & ge0 ir „i“ visoms reikšmėms yra

Pereinamosios matricos formulė - įvadas į Markovo grandines - „Edureka“

Leiskite man tai paaiškinti. Darant prielaidą, kad dabartinė mūsų būsena yra „i“, kita arba būsima būsena turi būti viena iš potencialių būsenų. Todėl imdami visų k reikšmių sumą, turime ją gauti.

Kas yra valstybės perėjimo schema?

Markovo modelį vaizduoja būsenos perėjimo schema. Diagrama rodo perėjimus tarp skirtingų būsenų Markovo grandinėje. Supraskime perėjimo matricą ir būsenos perėjimo matricą su pavyzdžiu.

Pereinamosios matricos pavyzdys

Apsvarstykite Markovo grandinę su trimis būsenomis 1, 2 ir 3 ir šiomis tikimybėmis:

Pereinamosios matricos pavyzdys - įvadas į Markovo grandines - „Edureka“

Valstybės perėjimo schemos pavyzdys - įvadas į Markovo grandines - „Edureka“

Pirmiau pateikta diagrama rodo Markovo grandinės būsenos perėjimo schemą. Čia 1,2 ir 3 yra trys galimos būsenos, o rodyklės, nukreiptos iš vienos būsenos į kitas, rodo perėjimo tikimybes pij. Kai, pij = 0, tai reiškia, kad nėra būsenos „i“ ir „j“ perėjimo.

Dabar mes žinokite matematiką ir Markovo grandinių logiką, paleiskime paprastą demonstracinę versiją ir supraskime, kur galima naudoti Markovo grandines.

Markovo grandinė „Python“

Norėdami paleisti šią demonstracinę versiją, naudosiu „Python“, taigi, jei nežinote „Python“, galite peržiūrėti šiuos tinklaraščius:

  1. Kaip išmokti „Python 3“ iš „Scratch“ - vadovas pradedantiesiems

Dabar pradėkime nuo kodavimo!

Markovo grandinės teksto generatorius

Problemos pareiškimas: Norėdami pritaikyti „Markov Property“ ir sukurti „Markov“ modelį, kuris gali generuoti teksto modeliavimą, tyrinėdamas Donaldo Trumpo kalbos duomenų rinkinį.

Duomenų rinkinio aprašymas: Teksto faile yra sąrašas kalbų, kurias pasakė Donaldas Trumpas 2016 m.

Logika: Taikydami „Markov Property“, sugeneruokite Donaldo Trumpo kalbą, atsižvelgdami į kiekvieną kalboje vartojamą žodį ir kiekvienam žodžiui, sukurkite toliau vartojamų žodžių žodyną.

1 veiksmas: importuokite reikalingas pakuotes

importuoti numerį kaip np

2 žingsnis: perskaitykite duomenų rinkinį

trump = open ('C: //Users//NeelTemp//Desktop//demos//speeches.txt', encoding = 'utf8'). read () #display data print (trump) SPEECH 1 ... Thank Jūs tiek daug. Tai taip malonu. Argi ne puikus vaikinas. Jis negauna teisingos spaudos, jis to negauna. Tai tiesiog neteisinga. Turiu pasakyti, kad esu čia ir labai stipriai, nes labai gerbiu Steve'ą Kingą, taip pat labai gerbiu „Citizens United“, Davidą ir visus, taip pat nepaprastai vertinu arbatos vakarėlį. Taip pat Ajovos gyventojai. Jie turi kažką bendro. Darbštūs žmonės ....

3 žingsnis: padalykite duomenų rinkinį į atskirus žodžius

korpusas = trump.split () # Parodykite korpuso spausdinimą (korpusą) „galingas“, „bet“, „ne“, „galingas“, „panašus“, „mus“, „Iranas“, „turi“, „ pasėtas “,„ teroras “, ...

Tada sukurkite funkciją, kuri generuoja skirtingas žodžių poras kalbose. Norėdami sutaupyti vietos, naudosime generatoriaus objektą.

4 žingsnis: porų kūrimas raktams ir tolesniems žodžiams

def make_pairs (korpusas): i diapazone (len (corpus) - 1): derlius (corpus [i], corpus [i + 1]) poros = make_pairs (korpusas)

Tada pradėkime tuščią žodyną žodžių poroms laikyti.

Jei pirmasis žodis poroje jau yra raktinis žodynas, tiesiog pridėkite kitą galimą žodį prie žodžių, einančių po žodžio, sąrašo. Bet jei žodis nėra raktas, tada sukurkite naują įrašą žodyne ir priskirkite raktą, lygų pirmajam poros žodžiui.

5 veiksmas: pridėkite žodyną

word_dict = {} žodžiui_1, žodis_2 poromis: jei word_1 žodyje_dict.keys (): word_dict [word_1] .append (word_2) else: word_dict [word_1] = [word_2]

Tada atsitiktinai pasirenkame žodį iš korpuso, kuris pradės Markovo grandinę.

6 žingsnis: Sukurkite „Markov“ modelį

# atsitiktinai pasirinkite pirmąjį žodį first_word = np.random.choice (korpusas) #Pasirinkite pirmąjį žodį didžiosiomis raidėmis, kad pasirinktas žodis nebūtų paimtas iš sakinio, o first_word.islower (): #Pradėkite grandinę nuo pasirinkta žodžio grandinė = [pirmas_žodis] # Inicializuokite stimuliuojamų žodžių skaičių n_words = 20

Po pirmo žodžio kiekvienas grandinės žodis yra atsitiktinai atrenkamas iš žodžių, kurie sekė tą konkretų žodį tiesioginėse D.Trumpo kalbose, sąrašo. Tai parodyta žemiau esančiame kodo fragmente:

i diapazone (n_words): chain.append (np.random.choice (word_dict [grandinė [-1]]))

7 žingsnis: prognozės

Galiausiai atvaizduokime stimuliuojamą tekstą.

#Join grąžina grandinę kaip eilutės atspaudą ('' .join (chain)) Neįtikėtinų žmonių skaičius. Hillary Clinton turi savo žmones ir tokį puikų darbą. O Obamos mes nemušime

Taigi tai yra sugeneruotas tekstas, kurį gavau atsižvelgdamas į D.Trumpo kalbą. Tai gali neturėti daug prasmės, tačiau yra pakankamai gera, kad suprastumėte, kaip Markovo grandinės gali būti naudojamos automatiškai generuoti tekstus.

Dabar pažvelkime į dar keletą programų iš Markovo grandinių ir kaip jie naudojami sprendžiant realaus pasaulio problemas.

„Markov“ grandinės programos

Štai realių „Markov“ tinklų programų sąrašas:

  1. „Google PageRank“: Visas internetas gali būti laikomas Markovo modeliu, kur kiekvienas tinklalapis gali būti būsena, o nuorodos ar nuorodos tarp šių puslapių gali būti laikomos perėjimais su tikimybe. Taigi iš esmės, nepaisant to, kuriame tinklalapyje pradėsite naršyti, galimybė patekti į tam tikrą tinklalapį, tarkim, X yra fiksuota tikimybė.

  2. Žodžio nuspėjimas: Žinoma, kad Markovo grandinės naudojamos numatant būsimus žodžius. Jie taip pat gali būti naudojami automatiniam pildymui ir pasiūlymams.

  3. „Subreddit“ modeliavimas: Tikrai susidūrėte su „Reddit“ ir bendravote vienoje iš jų gijų ar subredditų. „Reddit“ naudoja „subreddit“ treniruoklį, kuris sunaudoja didžiulį kiekį duomenų, kuriuose yra visi jų grupėse vykę komentarai ir diskusijos. Naudodamas Markovo grandines, treniruoklis sukuria tikimybę žodis į žodį, kad sukurtų komentarus ir temas.

  4. Teksto generatorius: Markovo grandinės dažniausiai naudojamos manekenių tekstams generuoti arba didelėms esė ir kalboms rengti. Jis taip pat naudojamas vardų generatoriuose, kuriuos matote internete.

Dabar, kai žinote, kaip išspręsti realaus pasaulio problemą naudojant „Markov Chains“, esu tikras, kad norite sužinoti daugiau. Pateikiame tinklaraščių, kurie padės jums pradėti naudoti kitas statistikos sąvokas, sąrašą:

Tuo mes baigiame šį „Markov Chains“ tinklaraščio įvadą. Jei turite klausimų dėl šios temos, palikite komentarą žemiau ir mes susisieksime su jumis.

Stebėkite daugiau tinklaraščių apie populiarias technologijas.

Jei ieškote internetinių struktūrizuotų duomenų mokslo mokymų, edureka! turi specialiai kuruotą programa, padedanti įgyti statistikos, duomenų apdorojimo, tiriamosios duomenų analizės, mašininio mokymosi algoritmų, tokių kaip „K-Means Clustering“, sprendimų medžių, atsitiktinių miškų, „Naive Bayes“, patirties. Sužinosite ir laiko eilučių, teksto gavybos bei gilaus mokymosi įvadų sąvokas. Netrukus prasidės naujos šio kurso partijos !!