Panimula Sa Mga Chain na Markov Na May Mga Halimbawa - Markov Chains Na May Python

Panimula Sa Markov Chains:

Naisip mo ba kung paano nagranggo ang Google ng mga web page? Kung nagawa mo na ang iyong pagsasaliksik sa gayon dapat mong malaman na gumagamit ito ng PageRank Algorithm na batay sa ideya ng mga chain ng Markov. Ang artikulong ito sa Panimula Sa Markov Chains ay makakatulong sa iyo na maunawaan ang pangunahing ideya sa likod ng mga chain ng Markov at kung paano sila ma-modelo bilang isang solusyon sa mga problema sa totoong mundo.

Narito ang isang listahan ng mga paksa na sasakupin sa blog na ito:

1. Ano ang Isang Markov Chain?
2. Ano Ang Pag-aari ng Markov?
3. Pag-unawa sa Mga Chain na Markov Na May Isang Halimbawa
4. Ano ang Isang Transition Matrix?
5. Markov Chain Sa Python
6. Mga Application ng Markov Chain

Upang makakuha ng malalim na kaalaman sa Data Science at Machine Learning gamit ang Python, maaari kang magpatala nang live ni Edureka na may suporta na 24/7 at habang-buhay na pag-access.

Ano ang Isang Markov Chain?

Una nang ipinakilala ni Andrey Markov ang mga chain ng Markov noong taong 1906. Ipinaliwanag niya ang mga chain ng Markov bilang:

Isang proseso ng stochastic na naglalaman ng mga random na variable, paglipat mula sa isang estado patungo sa isa pa depende sa ilang mga pagpapalagay at tiyak na mga probabilistic na panuntunan.

Ang mga random variable na paglipat mula sa isa patungo sa isa pa, batay sa isang mahalagang pag-aari ng matematika na tinawag Pag-aari ng Markov.

Dinadala nito sa atin ang tanong:

Ano Ang Pag-aari ng Markov?

Ang Discrete Time Markov Property ay nagsasaad na ang kinakalkula na posibilidad ng isang random na proseso ng paglipat sa susunod na posibleng estado ay nakasalalay lamang sa kasalukuyang estado at oras at ito ay malaya sa mga serye ng mga estado na nauna dito.

Ang katotohanan na ang susunod na posibleng pagkilos / estado ng isang random na proseso ay hindi nakasalalay sa pagkakasunud-sunod ng mga naunang estado, binibigyan ang mga chain ng Markov bilang isang proseso na walang memorya na umaasa lamang sa kasalukuyang estado / pagkilos ng isang variable.

Kunin natin ito sa matematika:

Hayaan ang random na proseso na maging, {Xm, m = 0,1,2, ⋯}.

Ang prosesong ito ay isang kadena lamang ng Markov kung,

Markov Chain - Panimula Sa Mga Markov Chain - Edureka

para sa lahat ng m, j, i, i0, i1, ⋯ im & minus1

Para sa isang may hangganan na bilang ng mga estado, S = {0, 1, 2, ⋯, r}, ito ay tinatawag na isang may hangganan na chain ng Markov.

Ang P (Xm + 1 = j | Xm = i) ay kumakatawan sa mga probabilidad ng paglipat sa paglipat mula sa isang estado patungo sa isa pa. Dito, ipinapalagay namin na ang mga probabilidad ng paglipat ay malaya sa oras.

Na nangangahulugang ang P (Xm + 1 = j | Xm = i) ay hindi nakasalalay sa halaga ng ‘m’. Samakatuwid, maaari nating buod,

Markov Chain Formula - Panimula Sa Markov Chains - Edureka

Kaya kumakatawan ang equation na ito ang kadena ng Markov.

Ngayon ay unawain natin kung ano ang eksaktong mga kadena ng Markov na may isang halimbawa.

Halimbawa ng Markov Chain

Bago ako magbigay sa iyo ng isang halimbawa, tukuyin natin kung ano ang isang Markov Model:

Ano ang Isang Modelong Markov?

Ang isang Markov Model ay isang stochastic na modelo na nagmomodelo ng mga random na variable sa isang paraan na ang mga variable ay sumusunod sa pag-aari ng Markov.

Ngayon ay unawain natin kung paano gumagana ang isang Markov Model na may isang simpleng halimbawa.

Tulad ng nabanggit kanina, ang mga chain ng Markov ay ginagamit sa pagbuo ng teksto at mga awtomatikong pagkumpleto ng mga application. Para sa halimbawang ito, titingnan namin ang isang halimbawa (random) na pangungusap at tingnan kung paano ito maaaring pagmomodelo sa pamamagitan ng paggamit ng mga chain ng Markov.

Halimbawa ng Markov Chain - Panimula Sa Mga chain ng Markov - Edureka

Ang pangungusap sa itaas ay ang aming halimbawa, alam kong wala itong katuturan (hindi nito kailangang), ito ay isang pangungusap na naglalaman ng mga random na salita, kung saan:

1. Mga susi ipahiwatig ang natatanging mga salita sa pangungusap, ibig sabihin, 5 mga susi (isa, dalawa, hail, masaya, edureka)

   malalim na kopya vs mababaw na kopya ng java

2. Mga Token ipahiwatig ang kabuuang bilang ng mga salita, ibig sabihin, 8 mga token.

Upang magpatuloy, kailangan nating maunawaan ang dalas ng paglitaw ng mga salitang ito, ipinapakita ng diagram sa ibaba ang bawat salita kasama ang isang bilang na nagsasaad ng dalas ng salitang iyon.

Mga Susi At Frequency - Panimula Sa Markov Chains - Edureka

Kaya't ang kaliwang haligi dito ay nagpapahiwatig ng mga susi at ang kanang haligi ay tumutukoy sa mga frequency.

Mula sa talahanayan sa itaas, maaari nating tapusin na ang susi na 'edureka' ay lalabas ng 4x kasing dami ng iba pang mga susi. Mahalagang mahihinuha ang naturang impormasyon sapagkat makakatulong ito sa amin na mahulaan kung anong salita ang maaaring mangyari sa isang partikular na punto ng oras. Kung kukuha ako ng hula tungkol sa susunod na salita sa halimbawang pangungusap, sasama ako sa 'edureka' dahil ito ang may pinakamataas na posibilidad na mangyari.

Nagsasalita tungkol sa posibilidad, isa pang panukalang dapat mong magkaroon ng kamalayan ay may timbang na mga pamamahagi.

Sa aming kaso, ang bigat na pamamahagi para sa 'edureka' ay 50% (4/8) dahil ang dalas nito ay 4, mula sa kabuuang 8 mga token. Ang natitirang mga susi (isa, dalawa, hail, masaya) lahat ay may 1 / 8th pagkakataon na maganap (& asymp 13%).

Ngayon na mayroon kaming pagkaunawa sa bigat na pamamahagi at isang ideya kung paano madalas na nangyayari ang mga tukoy na salita kaysa sa iba, maaari nating magpatuloy sa susunod na bahagi.

Pag-unawa sa Mga Chain ng Markov - Panimula Sa Mga chain ng Markov - Edureka

Sa figure sa itaas, nagdagdag ako ng dalawang karagdagang mga salita na nagsasaad ng simula at pagtatapos ng pangungusap, mauunawaan mo kung bakit ko ito nagawa sa seksyon sa ibaba.

Ngayon ay italaga rin natin ang dalas para sa mga key na ito:

Nai-update na Mga Susi At Frequency - Panimula Sa Markov Chains - Edureka

Ngayon gumawa tayo ng isang modelo ng Markov. Tulad ng nabanggit kanina, ang isang modelo ng Markov ay ginagamit upang mag-modelo ng mga random na variable sa isang partikular na estado sa paraang ang mga hinaharap na estado ng mga variable na ito ay nakasalalay lamang sa kanilang kasalukuyang estado at hindi sa kanilang mga nakaraang estado.

Kaya karaniwang sa isang modelo ng Markov, upang mahulaan ang susunod na estado, dapat lamang nating isaalang-alang ang kasalukuyang estado.

Sa diagram sa ibaba, makikita mo kung paano humantong sa isa pa ang bawat token sa aming pangungusap. Ipinapakita nito na ang hinaharap na estado (susunod na token) ay batay sa kasalukuyang estado (kasalukuyang token). Kaya't ito ang pinaka pangunahing panuntunan sa Markov Model.

Ipinapakita ng diagram sa ibaba na mayroong mga pares ng mga token kung saan ang bawat token sa pares ay humahantong sa isa pa sa parehong pares.

tapusin ang isang programa sa java

Markov Chain Pairs - Panimula Sa Markov Chains - Edureka

Sa diagram sa ibaba, lumikha ako ng isang representasyon ng istruktura na nagpapakita ng bawat key na may isang hanay ng mga susunod na posibleng token na maaari nitong ipares.

Isang hanay ng Markov Chain Pairs - Panimula Sa Markov Chains - Edureka

Upang buod ang halimbawang ito isaalang-alang ang isang senaryo kung saan magkakaroon ka upang bumuo ng isang pangungusap sa pamamagitan ng paggamit ng hanay ng mga susi at token na nakita namin sa halimbawa sa itaas. Bago namin patakbuhin ang halimbawang ito, isa pang mahalagang punto ay kailangan naming tukuyin ang dalawang paunang hakbang:

1. Isang paunang pamamahagi ng posibilidad (ibig sabihin, ang estado ng pagsisimula sa oras = 0, (key na 'Start'))

2. Isang posibilidad na lumipat mula sa isang estado patungo sa isa pa (sa kasong ito, ang posibilidad ng paglipat mula sa isang token patungo sa isa pa)

Natukoy namin ang bigat na pamamahagi sa mismong simula, kaya mayroon kaming mga posibilidad at paunang estado, ngayon ay magpatuloy tayo sa halimbawa.

• Kaya upang magsimula sa paunang token ay [Start]

• Susunod, mayroon lamang kaming isang posibleng token ibig sabihin [isang]

• Sa kasalukuyan, ang pangungusap ay may isang salita lamang, ibig sabihin ay 'isa'

• Mula sa token na ito, ang susunod na posibleng token ay [edureka]

• Ang pangungusap ay na-update sa 'isang edureka'

• Mula sa [edureka] maaari kaming lumipat sa anumang isa sa mga sumusunod na token [dalawa, hail, masaya, katapusan]

• Mayroong 25% na pagkakataong mapili ang 'dalawa', posibleng magresulta ito sa pagbuo ng orihinal na pangungusap (isang edureka dalawang edureka hail edureka happy edureka). Gayunpaman, kung ang 'pagtatapos' ay pipiliin pagkatapos ay tumitigil ang proseso at magtatapos kami na bumubuo ng isang bagong pangungusap, ibig sabihin, 'isang edureka'.

Bigyan ang iyong sarili ng isang tapik sa likod dahil bumubuo ka lamang ng isang Markov Model at nagpatakbo ng isang test case sa pamamagitan nito. Upang ibuod ang halimbawa sa itaas, karaniwang ginagamit namin ang kasalukuyang estado (kasalukuyang salita) upang matukoy ang susunod na estado (susunod na salita). At iyan mismo ang proseso ng Markov.

Ito ay isang proseso ng stochastic kung saan ang mga random na variable ay lumilipat mula sa isang estado patungo sa isa pa sa paraan na ang hinaharap na estado ng isang variable ay nakasalalay lamang sa kasalukuyang estado.

Dalhin natin ito sa susunod na hakbang at iguhit ang Markov Model para sa halimbawang ito.

Diagram ng Transisyon ng Estado - Panimula Sa Mga chain ng Markov - Edureka

Ang pigura sa itaas ay kilala bilang State Transition Diagram. Pag-uusapan pa namin ang tungkol dito sa seksyon sa ibaba, sa ngayon tandaan lamang na ipinapakita ng diagram na ito ang mga paglipat at posibilidad mula sa isang estado patungo sa isa pa.

Pansinin na ang bawat hugis-itlog sa pigura ay kumakatawan sa isang susi at ang mga arrow ay nakadirekta patungo sa mga posibleng key na maaaring sundin ito. Gayundin, ang mga timbang sa mga arrow ay nagpapahiwatig ng posibilidad o ang bigat na pamamahagi ng paglipat mula sa / patungo sa kani-kanilang mga estado.

Kaya't iyon ay tungkol sa kung paano gumagana ang Markov Model. Subukan nating maunawaan ang ilang mahahalagang terminolohiya sa Proseso ng Markov.

Ano ang Isang Transition Probability Matrix?

Sa seksyon sa itaas tinalakay namin ang pagtatrabaho ng isang Markov Model na may isang simpleng halimbawa, ngayon ay maunawaan natin ang mga terminolohiya ng matematika sa isang Proseso ng Markov.

Sa isang Proseso ng Markov, gumagamit kami ng isang matrix upang kumatawan sa mga posibilidad ng paglipat mula sa isang estado patungo sa isa pa. Ang matrix na ito ay tinatawag na Transition o posibilidad matrix. Kadalasan ito ay sinasabihan ng P.

Transition Matrix - Panimula Sa Markov Chains - Edureka

Tandaan, pij & ge0, at 'i' para sa lahat ng mga halaga ay,

Transition Matrix Formula - Panimula Sa Markov Chains - Edureka

Hayaan mong ipaliwanag ko ito. Ipagpalagay na ang aming kasalukuyang estado ay 'i', ang susunod o paparating na estado ay dapat na isa sa mga potensyal na estado. Samakatuwid, habang kinukuha ang buod ng lahat ng mga halaga ng k, dapat kaming makakuha ng isa.

Ano ang Isang Diagram ng Transisyon ng Estado?

Ang isang modelo ng Markov ay kinakatawan ng isang State Transition Diagram. Ipinapakita ng diagram ang mga paglipat kasama ng iba't ibang mga estado sa isang Markov Chain. Unawain natin ang transisyon ng matrix at ang estado ng paglipat matrix na may isang halimbawa.

Halimbawa ng Transition Matrix

Isaalang-alang ang isang kadena ng Markov na may tatlong estado na 1, 2, at 3 at ang mga sumusunod na posibilidad:

Halimbawa ng Transition Matrix - Panimula Sa Mga chain ng Markov - Edureka

Halimbawa ng Transisyon ng Estado ng Estado - Panimula Sa Mga chain ng Markov - Edureka

Ang diagram sa itaas ay kumakatawan sa diagram ng paglipat ng estado para sa kadena ng Markov. Dito, 1,2 at 3 ang tatlong posibleng estado, at ang mga arrow na tumuturo mula sa isang estado patungo sa iba pang mga estado ay kumakatawan sa mga probabilidad na paglipat pij. Kailan, pij = 0, nangangahulugan ito na walang paglipat sa pagitan ng estado na 'i' at ng estado na 'j'.

Ngayon na tayo alamin ang matematika at ang lohika sa likod ng mga chain ng Markov, magpatakbo tayo ng isang simpleng demo at maunawaan kung saan maaaring magamit ang mga chain ng Markov.

Markov Chain Sa Python

Upang patakbuhin ang demo na ito, gagamit ako ng Python, kaya kung hindi mo alam ang Python, maaari kang dumaan sa mga sumusunod na blog:

2. Paano Malalaman ang Python 3 mula sa Scratch - Isang Gabay sa Mga Nagsisimula

Magsimula na tayo sa pag-coding!

Markov Chain Text Generator

Pahayag ng Suliranin: Upang mailapat ang Markov Property at lumikha ng isang Markov Model na maaaring makabuo ng mga simulation ng teksto sa pamamagitan ng pag-aaral ng hanay ng data ng pagsasalita ni Donald Trump.

Paglalarawan ng Data Set: Naglalaman ang file ng teksto ng isang listahan ng mga talumpati na ibinigay ni Donald Trump noong 2016.

Lohika: Ilapat ang Markov Property upang mabuo ang talumpati ni Donald sa pamamagitan ng pagsasaalang-alang sa bawat salitang ginamit sa pagsasalita at para sa bawat salita, lumikha ng isang diksyunaryo ng mga salitang ginamit sa susunod.

bakit dapat mong malaman ang sawa

Hakbang 1: I-import ang kinakailangang mga pakete

i-import ang numpy bilang np

Hakbang 2: Basahin ang hanay ng data

trump = open ('C: //Users//NeelTemp//Desktop//demos //speeches.txt', encoding = 'utf8'). read () #display the data print (trump) SPEECH 1 ... Salamat ikaw talaga. Maganda iyan. Hindi ba siya mahusay na tao. Hindi siya nakakakuha ng patas na press hindi niya nakuha. Hindi lang makatarungan. At kailangan kong sabihin sa iyo na naririto ako, at napakalakas dito, sapagkat malaki ang respeto ko kay Steve King at may respeto rin ako para sa Citizens United, David at lahat, at napakalaking resect para sa Tea Party. Gayundin, pati na rin ang mga tao ng Iowa. Mayroon silang isang bagay na magkatulad. Masipag na tao ....

Hakbang 3: Hatiin ang set ng data sa mga indibidwal na salita

corpus = trump.split () #Display the corpus print (corpus) 'powerful,', 'but', 'not', 'powerful', 'like', 'us.', 'Iran', 'has', ' seeded ',' terror ', ...

Susunod, lumikha ng isang pagpapaandar na bumubuo ng iba't ibang mga pares ng mga salita sa mga talumpati. Upang makatipid ng puwang, gagamit kami ng isang object ng generator.

Hakbang 4: Lumilikha ng mga pares sa mga susi at ang mga sumusunod na salita

def make_pairs (corpus): para sa ako sa saklaw (len (corpus) - 1): ani (corpus [i], corpus [i + 1]) pares = make_pairs (corpus)

Susunod, simulan natin ang isang walang laman na diksyonaryo upang maiimbak ang mga pares ng mga salita.

Kung sakaling ang unang salita sa pares ay isang susi na sa diksyunaryo, idagdag lamang ang susunod na potensyal na salita sa listahan ng mga salitang sumusunod sa salita. Ngunit kung ang salita ay hindi isang susi, pagkatapos ay lumikha ng isang bagong entry sa diksyunaryo at italaga ang key na katumbas ng unang salita sa pares.

Hakbang 5: Pagdaragdag ng diksyunaryo

word_dict = {} para sa word_1, salitang_2 sa pares: kung word_1 sa word_dict.keys (): word_dict [word_1]. magdagdag (word_2) pa: word_dict [word_1] = [word_2]

Susunod, random na pumili kami ng isang salita mula sa corpus, na magsisimula ang kadena ng Markov.

Hakbang 6: Buuin ang modelo ng Markov

#randomly pick the first word first_word = np.random.choice (corpus) #Pick ang unang salita bilang isang capitalized na salita upang ang napiling salita ay hindi makuha mula sa pagitan ng isang pangungusap habang first_word.islower (): #Start the chain from ang napiling chain ng salita = [first_word] #Ipasimula ang bilang ng mga stimulated na salita n_words = 20

Kasunod sa unang salita, ang bawat salita sa kadena ay random na na-sample mula sa listahan ng mga salita na sumunod sa partikular na salita sa mga live na talumpati ni Trump. Ipinapakita ito sa snippet ng code sa ibaba:

para ako sa saklaw (n_words): chain.append (np.random.choice (word_dict [chain [-1]]))

Hakbang 7: Mga Pagtataya

Panghuli, ipakita natin ang stimulated na teksto.

Ibinabalik ng #Join ang kadena bilang isang naka-print na string ('. Sumali (kadena)) Ang bilang ng mga hindi kapani-paniwala na tao. At si Hillary Clinton, ay mayroong ating mga tao, at napakahusay na trabaho. At hindi namin talunin si Obama

Kaya ito ang nabuong teksto na nakuha ko sa pamamagitan ng pagsasaalang-alang sa talumpati ni Trump. Maaaring hindi ito magkaroon ng maraming kahulugan ngunit sapat na mabuti upang maunawaan mo kung paano magagamit ang mga chain ng Markov upang awtomatikong makabuo ng mga teksto.

Ngayon tingnan natin ang ilang higit pang mga application ng mga chain ng Markov at kung paano ginagamit ang mga ito upang malutas ang mga problema sa totoong mundo.

Mga Application ng Markov Chain

Narito ang isang listahan ng mga application na real-world ng mga chain ng Markov:

1. Google PageRank: Ang buong web ay maaaring isipin bilang isang modelo ng Markov, kung saan ang bawat web page ay maaaring maging isang estado at ang mga link o sanggunian sa pagitan ng mga pahinang ito ay maaaring isipin bilang, mga paglipat na may mga posibilidad. Kaya't karaniwang, hindi alintana ang aling web page na magsimula kang mag-surf, ang pagkakataong makapunta sa isang tiyak na web page, sabihin nating, X ay isang nakapirming posibilidad.

2. Pagta-type ng Pagtataya ng Salita: Kilala ang mga chain ng Markov na magagamit para sa paghula ng mga paparating na salita. Maaari din silang magamit sa awtomatikong pagkumpleto at mga mungkahi.

3. Subreddit Simulation: Tiyak na nakatagpo ka ng Reddit at nagkaroon ng pakikipag-ugnayan sa isa sa kanilang mga thread o subreddits. Gumagamit ang Reddit ng isang subreddit simulator na gumagamit ng isang malaking halaga ng data na naglalaman ng lahat ng mga komento at talakayan na gaganapin sa kanilang mga pangkat. Sa pamamagitan ng paggamit ng mga chain ng Markov, gumagawa ang simulator ng mga posibilidad na salita-sa-salita, upang lumikha ng mga komento at paksa.

4. Tagabuo ng teksto: Ang mga chain ng Markov ay karaniwang ginagamit upang makabuo ng mga teksto ng dummy o makagawa ng malalaking sanaysay at mag-ipon ng mga talumpati. Ginagamit din ito sa mga tagabuo ng pangalan na nakikita mo sa web.

Ngayong alam mo kung paano malutas ang isang problema sa totoong mundo sa pamamagitan ng paggamit ng Markov Chains, sigurado akong interesado kang malaman ang higit pa. Narito ang isang listahan ng mga blog na makakatulong sa iyong makapagsimula sa iba pang mga konseptong pang-istatistika:

Sa pamamagitan nito, natapos na kami sa blog ng Panimula sa Markov Chains na ito. Kung mayroon kang anumang mga query tungkol sa paksang ito, mangyaring mag-iwan ng komento sa ibaba at babalikan ka namin.

Abangan ang higit pang mga blog sa mga nag-trend na teknolohiya.

Kung naghahanap ka para sa online na nakabalangkas na pagsasanay sa Data Science, edureka! may isang espesyal na na-curate programa na tumutulong sa iyo na makakuha ng kadalubhasaan sa Statistics, Data Wrangling, Exploratory Data Analysis, Machine Learning Algorithms tulad ng K-Means Clustering, Decision Trees, Random Forest, Naive Bayes. Malalaman mo ang mga konsepto ng Time Series, Text Mining at isang pagpapakilala din sa Deep Learning. Ang mga bagong batch para sa kursong ito ay nagsisimula na !!