Увод у Марковљеве ланце са примерима - Марковљеви ланци са Питхоном

Увод у ланце Маркова:

Да ли сте се икада запитали како Гоогле рангира веб странице? Ако сте обавили своје истраживање, морате знати да оно користи ПагеРанк алгоритам који је заснован на идеји о ланцима Маркова. Овај чланак о Уводу у ланце Марков помоћи ће вам да разумете основну идеју која стоји иза марковских ланаца и како се они могу моделирати као решење проблема из стварног света.

Ево листе тема које ће бити обрађене у овом блогу:

1. Шта је ланац Маркова?
2. Шта је власништво Маркова?
3. Разумевање марковских ланаца на примеру
4. Шта је транзициона матрица?
5. Марков ланац у Питхону
6. Марков ланац апликација

Да бисте стекли детаљно знање о науци података и машинском учењу помоћу Питхона, можете се пријавити за уживо Едурека са 24/7 подршком и доживотним приступом.

Шта је ланац Маркова?

Андреи Марков је ланце Марков први пут представио 1906. године. Објаснио је Марковске ланце као:

Стохастички процес који садржи случајне променљиве, прелазак из једног стања у друго у зависности од одређених претпоставки и одређених вероватноћних правила.

Ови случајни променљиве прелазе из једног у друго стање, на основу важног математичког својства тзв Марков имање.

Ово нас доводи до питања:

Шта је власништво Маркова?

Својство марковског дискретног времена наводи да израчуната вероватноћа преласка случајног процеса у следеће могуће стање зависи само од тренутног стања и времена и независна је од низа стања која су му претходила.

Чињеница да следеће могуће дејство / стање случајног процеса не зависи од низа претходних стања, чини Марковљеве ланце као процес без меморије који искључиво зависи од тренутног стања / деловања променљиве.

Изведимо ово математички:

Нека случајни процес буде, {Ксм, м = 0,1,2, ⋯}.

Овај процес је марковски ланац само ако,

Марков ланац - Увод у ланце Марков - Едурека

за све м, ј, и, и0, и1, ⋯ им & минус1

За коначан број стања, С = {0, 1, 2, ⋯, р}, ово се назива коначним Марковљевим ланцем.

П (Ксм + 1 = ј | Ксм = и) овде представља вероватноћу преласка за прелазак из једног стања у друго. Овде претпостављамо да су вероватноће транзиције независне од времена.

Што значи да П (Ксм + 1 = ј | Ксм = и) не зависи од вредности „м“. Стога можемо резимирати,

Формула ланца Марков - Увод у ланце Марков - Едурека

Дакле, ова једначина представља ланац Марков.

Сада да разумемо шта су тачно ланци Маркова на примеру.

Пример ланца Марков

Пре него што вам дам пример, дефинишемо шта је Марков модел:

Шта је Марков модел?

Марков модел је стохастички модел који моделира случајне променљиве на такав начин да променљиве прате својство Маркова.

Сада да разумемо како Марков модел функционише на једноставном примеру.

Као што је раније поменуто, ланци Марков се користе у апликацијама за генерисање текста и аутоматско довршавање. За овај пример ћемо погледати пример (случајне) реченице и видети како се она може моделирати помоћу Марковљевих ланаца.

Пример марковског ланца - Увод у ланце Марков - Едурека

Горња реченица је наш пример, знам да нема пуно смисла (не мора), то је реченица која садржи случајне речи, у којима:

1. Кључеви означавају јединствене речи у реченици, тј. 5 тастера (један, два, хаил, хаппи, едурека)

2. Жетони означавају укупан број речи, односно 8 лексема.

Крећући се напред, морамо да разумемо учесталост појављивања ових речи, доњи дијаграм приказује сваку реч заједно са бројем који означава учесталост те речи.

Тастери и фреквенције - Увод у Марковљеве ланце - Едурека

Дакле, лева колона овде означава тастере, а десна колона фреквенције.

Из горње табеле можемо закључити да се кључ „едурека“ појављује четвороструко више од било ког другог тастера. Важно је закључити о таквим информацијама јер нам могу помоћи да предвидимо која реч се може појавити у одређеном тренутку. Ако бих претпоставио следећу реч у примеру реченице, пристао бих на „едурека“, јер има највећу вероватноћу појаве.

Говорећи о вероватноћи, још једна мера које морате бити свесни је пондерисане расподеле.

У нашем случају, пондерисана расподела за „едурека“ је 50% (4/8), јер је њена учесталост 4, од укупно 8 жетона. Остали кључеви (један, два, туча, срећни) сви имају 1/8 шансе да се појаве (& асимп 13%).

Сада када имамо разумевање пондерисане расподеле и идеју како се одређене речи јављају чешће од других, можемо да наставимо са следећим делом.

Разумевање ланаца Маркова - Увод у ланце Маркова - Едурека

На горњој слици додао сам две додатне речи које означавају почетак и крај реченице, разумећете зашто сам то учинио у одељку испод.

Сад ћемо доделити фреквенцију и за ове тастере:

Ажурирани тастери и фреквенције - Увод у ланце Маркова - Едурека

Хајде сада да направимо Марков модел. Као што је раније поменуто, Марков модел се користи за моделирање случајних променљивих у одређеном стању на такав начин да будућа стања ових променљивих зависе искључиво од њиховог тренутног стања, а не од прошлих стања.

Дакле, у основи Марковљевог модела, да бисмо предвидели следеће стање, морамо узети у обзир само тренутно стање.

На доњем дијаграму можете видети како сваки токен у нашој реченици води до другог. То показује да се будуће стање (следећи токен) заснива на тренутном стању (садашњи токен). Дакле, ово је најосновније правило у Марковљевом моделу.

Дијаграм испод показује да постоје парови жетона где сваки жетон у пару води до другог у истом пару.

Марковски ланчани парови - Увод у марковске ланце - Едурека

У дијаграму испод, креирао сам структурну представу која приказује сваки кључ са низом следећих могућих токена са којима се може упарити.

Низ парова ланаца Марков - Увод у ланце Марков - Едурека

Да резимирамо овај пример, размотрите сценарио у којем ћете морати да формирате реченицу користећи низ кључева и токена које смо видели у горњем примеру. Пре него што прођемо кроз овај пример, још једна важна тачка је да морамо да одредимо две почетне мере:

1. Почетна расподела вероватноће (тј. Почетно стање у тренутку = 0, (тастер „Старт“))

2. Вероватноћа преласка из једног стања у друго (у овом случају вероватноћа преласка из једног у други жетон)

Пондерисану расподелу смо дефинисали на самом почетку, тако да имамо вероватноће и почетно стање, хајде да наставимо са примером.

• Дакле, почетак са почетним токеном је [Старт]

• Даље, имамо само један могући жетон, тј. [Један]

• Тренутно реченица има само једну реч, тј. „Једна“

• Од овог токена, следећи могући знак је [едурека]

• Реченица је ажурирана на „једна едурека“

• Из [едурека] можемо прећи на било који од следећих токена [два, поздрав, срећан, крај]

• Постоји 25% шансе да се изабере „двоје“, то би вероватно резултирало формирањем оригиналне реченице (један едурека два едурека поздрав едурека срећна едурека). Међутим, ако се изабере „крај“, процес се зауставља и на крају ћемо генерисати нову реченицу, тј. „Једну едуреку“.

Потапшајте се по леђима јер сте управо направили Марков модел и провели тест случаја. Да резимирамо горњи пример, у основи смо користили садашње стање (садашња реч) за одређивање следећег стања (следећа реч). И управо то је процес Маркова.

То је стохастички процес у којем случајне променљиве прелазе из једног стања у друго на такав начин да будуће стање променљиве зависи само од садашњег стања.

Идемо на следећи корак и извуцимо Марков модел за овај пример.

Дијаграм транзиције државе - Увод у ланце Маркова - Едурека

Горња слика је позната као дијаграм транзиције државе. О овоме ћемо говорити више у одељку испод, за сада само запамтите да овај дијаграм приказује прелазе и вероватноћу из једног стања у друго.

Приметите да сваки овал на слици представља кључ, а стрелице су усмерене ка могућим тастерима који могу да га прате. Такође, тежине на стрелицама означавају вероватноћа или пондерисана расподела преласка из / у одговарајућа стања.

Дакле, све је било у томе како Марков модел функционише. Покушајмо сада да разумемо неке важне терминологије у Марковљевом процесу.

Шта је матрица вероватноће транзиције?

У горњем одељку смо разговарали о раду Марковљевог модела са једноставним примером, сада ћемо разумети математичке терминологије у Марковљевом процесу.

У Марковљевом процесу користимо матрицу да представимо вероватноће преласка из једног стања у друго. Ова матрица се назива транзицијска или матрица вероватноће. Обично га означавају П.

Прелазна матрица - Увод у ланце Маркова - Едурека

Напомена, пиј & ге0, а „и“ за све вредности је,

Формула транзиционе матрице - Увод у Марковљеве ланце - Едурека

Да објасним ово. Под претпоставком да је наше тренутно стање „и“, следеће или предстојеће стање мора бити једно од потенцијалних стања. Према томе, док узимамо збир свих вредности к, морамо добити једну.

Шта је дијаграм транзиције државе?

Марков модел представљен је дијаграмом транзиције државе. Дијаграм приказује прелазе између различитих стања у ланцу Маркова. Хајде да разумемо матрицу транзиције и матрицу транзиције стања на примеру.

Пример транзиционе матрице

Размотримо Марков ланац са три стања 1, 2 и 3 и следећим вероватноћама:

програм заказивања кругова у ц

Пример транзиционе матрице - Увод у ланце Маркова - Едурека

Пример дијаграма транзиције државе - Увод у ланце Маркова - Едурека

Горњи дијаграм представља дијаграм транзиције стања за ланац Марков. Овде су 1,2 и 3 три могућа стања, а стрелице које показују од једног до другог стања представљају вероватноће транзиције пиј. Када је пиј = 0, то значи да не постоји прелаз између стања „и“ и стања „ј“.

Сад кад ми знајте математику и логику иза Марков ланаца, хајде да покренемо једноставан демо и схватимо где Марков ланци могу да се користе.

Марков ланац у Питхону

Да бих покренуо ову демонстрацију, користићу Питхон, па ако не знате Питхон, можете да прођете кроз следеће блогове:

2. Како научити Питхон 3 из огреботина - водич за почетнике

Сада кренимо са кодирањем!

Генератор текста ланца Марков

Изјава о проблему: Да примени својство Маркова и створи Марков модел који може генерисати симулације текста проучавањем скупа података говора Доналда Трампа.

Опис скупа података: Текстуална датотека садржи списак говора које је Доналд Трамп одржао 2016. године.

Логика: Примените својство Марков да бисте генерисали Доналдов Трампов говор узимајући у обзир сваку реч која се користи у говору и за сваку реч, направите речник речи које ће се даље користити.

Корак 1: Увезите потребне пакете

увоз нумпи као нп

Корак 2: Прочитајте скуп података

трумп = опен ('Ц: //Усерс//НеелТемп//Десктоп//демос//спеецхес.ткт', енцодинг = 'утф8'). реад () #прикажи испис података (адут) ГОВОР 1 ... Хвала толико. То је тако лепо. Зар није сјајан момак. Не добија поштену штампу не добија је. То једноставно није фер. И морам вам рећи да сам овде, и то веома снажно овде, јер изузетно поштујем Стеве Кинг-а и такође поштујем Цитизенс Унитед, Давида и све остале, и страшно чаштамство за чајанку. Такође, и људи из Ајове. Имају нешто заједничко. Вредни људи ....

Корак 3: Поделите скуп података у појединачне речи

цорпус = трумп.сплит () # Прикажите отисак корпуса (корпус) „моћан“, „али“, „не“, „моћан“, „попут“, „нас.“, „Иран“, „има“, „ посејани ',' терор ', ...

Затим створите функцију која генерише различите парове речи у говорима. Да бисмо уштедели простор, користићемо објекат генератора.

Корак 4: Стварање парова за кључеве и наредне речи

деф маке_паирс (цорпус): за и у опсегу (лен (цорпус) - 1): ииелд (цорпус [и], цорпус [и + 1]) парови = маке_паирс (цорпус)

Даље, иницијализујмо празан речник за чување парова речи.

У случају да је прва реч у пару већ кључ у речнику, само додајте следећу потенцијалну реч на листу речи које следе реч. Али ако реч није кључ, направите нови унос у речнику и доделите кључ једнак првој речи у пару.

Корак 5: Додавање речника

ворд_дицт = {} за ворд_1, ворд_2 у паровима: ако ворд_1 у ворд_дицт.кеис (): ворд_дицт [ворд_1] .апенд (ворд_2) елсе: ворд_дицт [ворд_1] = [ворд_2]

Даље, насумично бирамо реч из корпуса која ће покренути ланац Марков.

Корак 6: Изградите Марков модел

#накључно одаберите прву реч фирст_ворд = нп.рандом.цхоице (цорпус) # Изаберите прву реч као почетну реч тако да одабрана реч не буде узета између реченице док фирст_ворд.исловер (): # Покрените ланац из изабрани ланац речи = [прва_реч] # Иницијализуј број стимулисаних речи н_речи = 20

Након прве речи, свака реч у ланцу насумично се узима из листе речи које су пратиле ту одређену реч у Трамповим говорима уживо. Ово је приказано у доњем исечку кода:

за и у опсегу (н_вордс): цхаин.аппенд (нп.рандом.цхоице (ворд_дицт [цхаин [-1]]))

Корак 7: Предвиђања

На крају, прикажимо стимулисани текст.

#Јоин враћа ланац као испис низа ('' .јоин (ланац)) Број невероватних људи. А Хиллари Цлинтон има наше људе и тако сјајан посао. И нећемо победити Обаму

Дакле, ово је генерисани текст који сам добио узимајући у обзир Трампов говор. То можда неће имати пуно смисла, али је довољно добро да схватите како се ланци Маркова могу користити за аутоматско генерисање текстова.

Погледајмо сада још неке апликације марковских ланаца и како се користе за решавање проблема из стварног света.

Марков ланац апликација

Ево листе стварних примена ланаца Марков:

1. Гоогле ПагеРанк: Читав веб може се сматрати Марковим моделом, при чему свака веб страница може бити стање, а везе или референце између ових страница могу се сматрати прелазима са вероватноћама. Дакле, у основи, без обзира на којој веб страници започињете сурфовање, шанса да дођете до одређене веб странице, рецимо, Кс је фиксна вероватноћа.

2. Предвиђање куцања речи: Познато је да се ланци Маркова користе за предвиђање предстојећих речи. Такође се могу користити за аутоматско допуњавање и предлоге.

3. Субреддит Симулација: Сигурно сте наишли на Реддит и имали интеракцију са једном од њихових нити или субредита. Реддит користи симулатор субреддита који троши огромну количину података који садрже све коментаре и дискусије вођене у њиховим групама. Користећи Марковљеве ланце, симулатор ствара вероватноћу од речи до речи, како би створио коментаре и теме.

4. Генератор текста: Ланци Маркова најчешће се користе за стварање лажних текстова или израду великих есеја и састављање говора. Такође се користи у генераторима имена које видите на мрежи.

Сад кад знате како да решите стварни проблем помоћу Марков ланаца, сигуран сам да сте знатижељни да сазнате више. Ево листе блогова који ће вам помоћи да започнете са другим статистичким концептима:

Овим смо дошли до краја овог блога Увод у ланце Марков. Ако имате питања у вези са овом темом, оставите коментар испод и јавићемо вам се.

Пратите још блогова о модерним технологијама.

Ако тражите структурирану обуку на мрежи из науке о подацима, едурека! има посебно курирану програм који вам помаже да стекнете стручност у статистици, премештању података, истраживачкој анализи података, алгоритмима машинског учења попут кластера К-Меанс, дрвећима одлука, случајним шумама, наивним Баиес-има. Научићете и концепте временских серија, рударања текста и увод у дубоко учење. Нове серије за овај курс почињу ускоро !!