Johdanto Markov-ketjuihin esimerkkeillä - Markov-ketjut Pythonilla

Johdanto Markov-ketjuihin:

Oletko koskaan miettinyt, miten Google sijoittaa verkkosivut? Jos olet tehnyt tutkimuksen, sinun on tiedettävä, että siinä käytetään PageRank-algoritmia, joka perustuu Markov-ketjujen ideaan. Tämä Markov-ketjujen esittely -artikkeli auttaa sinua ymmärtämään Markov-ketjujen perusajatuksen ja kuinka ne voidaan mallintaa ratkaisuna todellisiin ongelmiin.

Tässä on luettelo aiheista, joita käsitellään tässä blogissa:

1. Mikä on Markov-ketju?
2. Mikä on Markovin omaisuus?
3. Markov-ketjujen ymmärtäminen esimerkillä
4. Mikä on siirtymämatriisi?
5. Markov-ketju Pythonissa
6. Markov-ketjusovellukset

Jos haluat saada syvällistä tietoa datatieteestä ja koneoppimisesta Pythonin avulla, voit ilmoittautua livenä kirjoittanut Edureka 24/7 tuella ja käyttöikä.

Mikä on Markov-ketju?

Andrey Markov esitteli Markov-ketjut ensimmäisen kerran vuonna 1906. Hän selitti Markov-ketjut seuraavasti:

Stokastinen prosessi, joka sisältää satunnaisia ​​muuttujia, siirtymällä tilasta toiseen riippuen tietyistä oletuksista ja selkeistä todennäköisyyssäännöistä.

Nämä satunnaiset muuttujat siirtyvät tilasta toiseen perustuen tärkeään matemaattiseen ominaisuuteen, jota kutsutaan Markov-kiinteistö.

Tämä johtaa meidät kysymykseen:

Mikä on Markovin omaisuus?

Diskreetti aika Markov-ominaisuus toteaa, että satunnaisen prosessin laskettu todennäköisyys siirtyä seuraavaan mahdolliseen tilaan riippuu vain nykyisestä tilasta ja ajasta ja on riippumaton sitä edeltäneistä tilasarjoista.

Se tosiasia, että satunnaisen prosessin seuraava mahdollinen toiminta / tila ei riipu aikaisempien tilojen järjestyksestä, tekee Markov-ketjuista muistittomana prosessina, joka riippuu vain muuttujan nykyisestä tilasta / toiminnasta.

Johdetaan tämä matemaattisesti:

Olkoon satunnaisprosessi {Xm, m = 0,1,2, ⋯}.

Tämä prosessi on Markov-ketju vain, jos

Markov-ketju - Johdanto Markov-ketjuihin - Edureka

kaikille m, j, i, i0, i1, ⋯ im & miinus1

Rajoitetulle joukolle tiloja, S = {0, 1, 2, ⋯, r}, tätä kutsutaan rajalliseksi Markov-ketjuksi.

P (Xm + 1 = j | Xm = i) edustaa tässä siirtymän todennäköisyyksiä siirtyä tilasta toiseen. Oletamme tässä, että siirtymätodennäköisyydet ovat riippumattomia ajasta.

Mikä tarkoittaa, että P (Xm + 1 = j | Xm = i) ei riipu m: n arvosta. Siksi voimme tiivistää

Markov-ketjukaava - Johdanto Markov-ketjuihin - Edureka

Joten tämä yhtälö edustaa Markov-ketju.

Ymmärretään nyt, mitä Markov-ketjut tarkalleen ovat esimerkin avulla.

Markov-ketjuesimerkki

Ennen kuin annan sinulle esimerkin, määritellään mikä Markov-malli on:

Mikä on Markov-malli?

Markov-malli on stokastinen malli, joka mallintaa satunnaismuuttujia siten, että muuttujat seuraavat Markov-ominaisuutta.

Ymmärretään nyt, kuinka Markov-malli toimii yksinkertaisella esimerkillä.

Kuten aiemmin mainittiin, Markov-ketjuja käytetään tekstinluonti- ja automaattisen täydennysohjelmissa. Tässä esimerkissä tarkastelemme esimerkinomaista (satunnaista) lausetta ja kuinka se voidaan mallintaa käyttämällä Markov-ketjuja.

Markov-ketjuesimerkki - Johdanto Markov-ketjuihin - Edureka

Yllä oleva lause on esimerkkimme, tiedän, että sillä ei ole paljon järkeä (sen ei tarvitse), se on lause, joka sisältää satunnaisia ​​sanoja, jossa:

1. Avaimet merkitse lauseen ainutlaatuisia sanoja, ts. 5 näppäintä (yksi, kaksi, raekuuro, onnellinen, edureka)

2. Tunnukset merkitsevät sanojen kokonaismäärää, ts. 8 merkkiä.

Edetessä meidän on ymmärrettävä näiden sanojen esiintymistiheys, alla olevassa kaaviossa on esitetty kukin sana sekä luku, joka ilmaisee sanan taajuuden.

Avaimet ja taajuudet - Johdanto Markov-ketjuihin - Edureka

Joten vasen sarake tarkoittaa tässä näppäimiä ja oikea sarake taajuuksia.

Yllä olevasta taulukosta voidaan päätellä, että avain 'edureka' tulee esiin 4x yhtä paljon kuin mikä tahansa muu avain. On tärkeää päätellä tällaisesta tiedosta, koska se voi auttaa meitä ennustamaan, mikä sana saattaa esiintyä tietyssä ajankohdassa. Jos tekisin arvauksen esimerkkilauseen seuraavasta sanasta, jatkaisin sanalla 'edureka', koska sillä on suurin todennäköisyys esiintyä.

Puhuessasi todennäköisyydestä, toinen mitta, jonka sinun on oltava tietoinen, on painotetut jakaumat.

Meidän tapauksessamme ’edurekan’ painotettu jakauma on 50% (4/8), koska sen taajuus on 4 8 merkin kokonaismäärästä. Muilla näppäimillä (yksi, kaksi, raekuurot, onnelliset) on kaikilla 1/8 mahdollisuus esiintyä (& asymp 13%).

Nyt kun meillä on käsitys painotetusta jakaumasta ja käsitys siitä, kuinka tiettyjä sanoja esiintyy useammin kuin toiset, voimme jatkaa seuraavaa osaa.

Markov-ketjujen ymmärtäminen - Johdanto Markov-ketjuihin - Edureka

Yllä olevaan kuvaan olen lisännyt kaksi lisäsanaa, jotka merkitsevät lauseen alkua ja loppua. Ymmärrät, miksi tein tämän alla olevassa osassa.

Määritetään nyt myös näiden näppäinten taajuus:

Päivitetyt avaimet ja taajuudet - Johdanto Markov-ketjuihin - Edureka

Luodaan nyt Markov-malli. Kuten aiemmin mainittiin, Markov-mallia käytetään satunnaismuuttujien mallintamiseen tietyssä tilassa siten, että näiden muuttujien tulevat tilat riippuvat yksinomaan niiden nykytilasta eikä menneisyydestä.

Joten pohjimmiltaan Markov-mallissa, jotta voimme ennustaa seuraavan tilan, meidän on otettava huomioon vain nykyinen tila.

Alla olevasta kaaviosta näet, kuinka jokainen lauseemme lause johtaa toiseen. Tämä osoittaa, että tuleva tila (seuraava tunnus) perustuu nykyiseen tilaan (nykyinen tunnus). Joten tämä on Markov-mallin perussääntö.

Alla oleva kaavio osoittaa, että on olemassa merkkipareja, joissa kukin parissa oleva merkki johtaa toiseen samassa parissa olevaan.

Markov-ketjuparit - Johdanto Markov-ketjuihin - Edureka

Alla olevassa kaaviossa olen luonut rakenteellisen esityksen, joka näyttää jokaisen avaimen joukolla seuraavia mahdollisia merkkejä, joihin se voi muodostaa parin.

Joukko Markov-ketjupareja - Johdanto Markov-ketjuihin - Edureka

Yhteenvetona tästä esimerkistä tarkastellaan skenaariota, jossa joudut muodostamaan lauseen käyttämällä yllä olevassa esimerkissä näkemääsi avainten ja tunnusten ryhmää. Ennen kuin käytämme tätä esimerkkiä, toinen tärkeä asia on se, että meidän on määriteltävä kaksi alkuvaihetta:

1. Alkuperäinen todennäköisyysjakauma (ts. Alkutila ajankohtana = 0, (aloitusnäppäin))

2. Siirtymän todennäköisyys hypätä tilasta toiseen (tässä tapauksessa todennäköisyys siirtyä yhdestä tunnuksesta toiseen)

Olemme määrittäneet painotetun jakauman itse alussa, joten meillä on todennäköisyydet ja alkutila, nyt jatketaan esimerkkiä.

• Joten aluksi alkutunnus on [Käynnistä]

• Seuraavaksi meillä on vain yksi mahdollinen tunnus eli [yksi]

• Tällä hetkellä lauseessa on vain yksi sana eli yksi

• Tästä tunnuksesta seuraava mahdollinen tunnus on [edureka]

• Lause päivitetään muotoon ”yksi edureka”

• Kohteesta [edureka] voimme siirtyä mihin tahansa seuraavista tunnuksista [kaksi, hail, happy, end]

• On 25% mahdollisuus, että 'kaksi' valitaan, tämä johtaisi mahdollisesti alkuperäisen lauseen muodostamiseen (yksi edureka kaksi edureka hail edureka onnellinen edureka). Jos kuitenkin valitaan loppu, prosessi pysähtyy ja muodostamme uuden lauseen eli yhden edurekan.

Tee itsellesi taputus, koska rakennat vain Markov-mallin ja juoksit sen läpi. Yhteenvetona yllä olevasta esimerkistä käytimme periaatteessa nykyistä tilaa (nykyinen sana) seuraavan tilan (seuraava sana) määrittämiseen. Ja juuri tämä on Markov-prosessi.

Se on stokastinen prosessi, jossa satunnaismuuttujat siirtyvät tilasta toiseen siten, että muuttujan tuleva tila riippuu vain nykyisestä tilasta.

Otetaan se seuraavaan vaiheeseen ja piirretään Markov-malli tälle esimerkille.

Tilan siirtymäkaavio - Johdanto Markov-ketjuihin - Edureka

Yllä oleva kuva tunnetaan valtion siirtymäkaaviona. Puhumme tästä tarkemmin alla olevassa osiossa, toistaiseksi vain muista, että tämä kaavio näyttää siirtymät ja todennäköisyydet tilasta toiseen.

Huomaa, että jokainen soikio kuvassa edustaa avainta ja nuolet on suunnattu mahdollisiin näppäimiin, jotka voivat seurata sitä. Nuolien painot tarkoittavat myös vastaavista tiloista / tiloihin siirtymisen todennäköisyys tai painotettu jakauma.

Joten kyse oli siitä, kuinka Markov-malli toimii. Yritetään nyt ymmärtää joitain tärkeitä termejä Markov-prosessissa.

Mikä on siirtymätodennäköisyysmatriisi?

Yllä olevassa osiossa keskusteltiin Markov-mallin toiminnasta yksinkertaisella esimerkillä, nyt ymmärretään Markov-prosessin matemaattiset terminologiat.

Markov-prosessissa käytämme matriisia edustamaan siirtymätodennäköisyyksiä tilasta toiseen. Tätä matriisia kutsutaan siirtymä- tai todennäköisyysmatriisiksi. Se on yleensä merkitty P.

Siirtymämatriisi - Johdanto Markov-ketjuihin - Edureka

Huomaa, että pij & ge0 ja 'i' kaikille arvoille ovat

Siirtymämatriisikaava - Johdanto Markov-ketjuihin - Edureka

Anna minun selittää tämä. Olettaen, että nykyinen tilamme on ”i”, seuraavan tai tulevan tilan on oltava yksi potentiaalisista tiloista. Siksi, kun otetaan k: n kaikkien arvojen summa, meidän on saatava yksi.

kuinka asentaa php ikkunaan

Mikä on valtion siirtymäkaavio?

Markov-mallia edustaa tilan siirtymäkaavio. Kaavio näyttää siirtymät eri valtioiden välillä Markov-ketjussa. Ymmärretään siirtymämatriisi ja tilansiirtomatriisi esimerkillä.

Esimerkki siirtymämatriisista

Tarkastellaan Markov-ketjua, jossa on kolme tilaa 1, 2 ja 3 ja seuraavat todennäköisyydet:

Esimerkki siirtymämatriisista - Johdanto Markov-ketjuihin - Edureka

Esimerkki valtion siirtymäkaaviosta - Johdanto Markov-ketjuihin - Edureka

Yllä oleva kaavio edustaa Markov-ketjun tilasiirtymäkaaviota. Tässä 1,2 ja 3 ovat kolme mahdollista tilaa, ja yhdestä tilasta toiseen tilaan osoittavat nuolet edustavat siirtymätodennäköisyyksiä pij. Kun pij = 0, se tarkoittaa, että tilan 'i' ja tilan 'j' välillä ei ole siirtymistä.

Nyt kun me osaa matematiikka ja Markov-ketjujen logiikka, suoritetaan yksinkertainen esittely ja ymmärretään, missä Markov-ketjuja voidaan käyttää.

Markov-ketju Pythonissa

Tämän demon suorittamiseen käytän Pythonia, joten jos et tunne Pythonia, voit käydä läpi seuraavat blogit:

2. Kuinka oppia Python 3 Scratchista - Aloittelijan opas

Aloitetaan nyt koodauksesta!

Markov-ketjutekstigeneraattori

Ongelma: Markov Property -sovelluksen käyttäminen ja Markov-mallin luominen, joka voi luoda tekstisimulaatioita tutkimalla Donald Trumpin puhetietojoukkoa.

Tietojoukon kuvaus: Tekstitiedosto sisältää luettelon Donald Trumpin vuonna 2016 pitämistä puheista.

Logiikka: Luo Donald's Trumpin puhe Markov Property -sovelluksella ottamalla huomioon kaikki puheessa käytettävät sanat ja luomalla jokaiselle sanalle sanasto, jota käytetään seuraavaksi.

Vaihe 1: Tuo vaaditut paketit

tuo numerotunnus nimellä np

Vaihe 2: Lue tietojoukko

trump = open ('C: //Users//NeelTemp//Desktop//demos//speeches.txt', encoding = 'utf8'). read () #display data print (trump) SPEECH 1 ... Kiitos sinua niin paljon. Tuo on niin mukavaa. Eikö hän ole hieno kaveri. Hän ei saa reilua lehdistöä eikä saa sitä. Se ei ole vain oikeudenmukaista. Ja minun on sanottava, että olen täällä ja erittäin voimakkaasti täällä, koska kunnioitan suuresti Steve Kingiä ja kunnioitan samalla tavalla myös Citizens Unitedia, Davidia ja kaikkia ja valtavaa kunnioitusta teepuolueeseen. Myös Iowan asukkaat. Heillä on jotain yhteistä. Ahkera ihminen ....

Vaihe 3: Jaa tietojoukko yksittäisiksi sanoiksi

corpus = trump.split () # Näytä corpus print (corpus) 'voimakas', 'mutta', 'ei', 'voimakas', 'kuten', 'me', 'Iran', 'on', ' kylvetty ',' kauhu ', ...

Luo seuraavaksi toiminto, joka tuottaa erilaiset sanaparit puheisiin. Tilan säästämiseksi käytämme generaattoriobjektia.

Vaihe 4: Parien luominen avaimille ja jatkosanoille

def make_pairs (corpus): i: lle alueella (len (corpus) - 1): tuotto (corpus [i], corpus [i + 1]) parit = make_parit (corpus)

Alustetaan seuraavaksi tyhjä sanakirja sanaparien tallentamiseksi.

Jos parin ensimmäinen sana on jo avain sanakirjassa, liitä vain seuraava potentiaalinen sana sanaa seuraavien sanojen luetteloon. Mutta jos sana ei ole avain, luo uusi merkintä sanakirjaan ja määritä avain yhtä parin ensimmäisen sanan kanssa.

Vaihe 5: Liitä sanakirja

word_dict = {} sanalle_1, word_2 pareittain: jos word_1 sanassa_dict.keys (): word_dict [word_1]. append (word_2) else: word_dict [word_1] = [word_2]

Seuraavaksi valitsemme korpusesta sanan, joka käynnistää Markov-ketjun.

Vaihe 6: Rakenna Markov-malli

# Valitse satunnaisesti ensimmäinen sana first_word = np.andom.choice (corpus) # Valitse ensimmäinen sana isoin kirjaimin, jotta valitsemaasi sanaa ei oteta lauseen välistä kun first_word.islower (): #Aloita ketju valittu sanaketju = [first_word] # Alusta stimuloitujen sanojen määrä n_words = 20

Ensimmäisen sanan jälkeen ketjun jokaisesta sanasta otetaan satunnaisotanta niiden sanojen luettelosta, jotka ovat seuranneet kyseistä sanaa Trumpin suorissa puheissa. Tämä näkyy alla olevassa koodinpätkässä:

alueella i (n_words): chain.append (np.random.choice (word_dict [ketju [-1]]))

Vaihe 7: Ennusteet

Katsotaanpa lopuksi stimuloitu teksti.

#Join palauttaa ketjun merkkijonona ('' .join (chain)) Uskomattomien ihmisten määrä. Ja Hillary Clintonilla on ihmisiä, ja niin hyvää työtä. Emmekä lyö Obamaa

Joten tämä on luotu teksti, jonka sain tarkastelemalla Trumpin puhetta. Sillä ei ehkä ole paljon järkeä, mutta se on tarpeeksi hyvä saadaksesi ymmärtämään, kuinka Markov-ketjuja voidaan käyttää tekstien automaattiseen luomiseen.

Katsotaan nyt lisää sovelluksia Markov-ketjuista ja kuinka niitä käytetään ratkaisemaan todellisia ongelmia.

Markov-ketjusovellukset

Tässä on luettelo Markov-ketjujen reaalimaailman sovelluksista:

1. Google PageRank: Koko verkko voidaan ajatella Markov-malliksi, jossa jokainen verkkosivu voi olla tila ja näiden sivujen väliset linkit tai viitteet voidaan ajatella siirtyminä todennäköisyydellä. Joten periaatteessa, riippumatta siitä, millä verkkosivulla aloitat surffaamisen, mahdollisuus päästä tietylle verkkosivulle, sanoa, X on kiinteä todennäköisyys.

2. Kirjoitus sanan ennustus: Markov-ketjuja tiedetään käytettävän tulevien sanojen ennustamiseen. Niitä voidaan käyttää myös automaattiseen täydennykseen ja ehdotuksiin.

3. Subreddit-simulointi: Olet varmasti törmännyt Redditiin ja ollut vuorovaikutuksessa heidän ketjunsa tai ala-alansa kanssa. Reddit käyttää subreddit-simulaattoria, joka kuluttaa valtavan määrän tietoa, joka sisältää kaikki ryhmiensä väliset kommentit ja keskustelut. Käyttämällä Markov-ketjuja simulaattori tuottaa sanasta sanaan todennäköisyyksiä kommenttien ja aiheiden luomiseen.

4. Tekstigeneraattori: Markov-ketjuja käytetään yleisimmin nuken teksteihin tai suurten esseiden tuottamiseen ja puheiden kokoamiseen. Sitä käytetään myös nimien generaattoreissa, jotka näet verkossa.

Nyt kun tiedät kuinka ratkaista todellinen ongelma Markov-ketjujen avulla, olet varma, että olet kiinnostunut oppimaan lisää. Tässä on luettelo blogeista, joiden avulla pääset alkuun muiden tilastollisten käsitteiden kanssa:

Tämän myötä olemme päässeet tämän Markov-ketjujen esittelyblogin loppuun. Jos sinulla on kysyttävää tästä aiheesta, jätä kommentti alla ja palaamme sinuun.

Pysy kuulolla lisää blogeja trenditekniikoista.

Jos etsit online-rakenteista koulutusta datatieteessä, edureka! on erityisesti kuratoitu ohjelma, joka auttaa sinua hankkimaan asiantuntemusta tilastoista, tietojen käsittelemisestä, tutkivasta tietojen analysoinnista, koneoppimisalgoritmeista, kuten K-Means Clustering, päätöksentekopuut, Random Forest, Naive Bayes. Opit myös aikasarjan, tekstinlouhinnan ja syvällisen oppimisen käsitteet. Uudet erät tälle kurssille alkavat pian !!