Въведение в веригите на Марков с примери - Веригите на Марков с Python

Въведение в веригите на Марков:

Замисляли ли сте се как Google класира уеб страниците? Ако сте направили изследването си, трябва да знаете, че той използва алгоритъма PageRank, който се основава на идеята за веригите на Марков. Тази статия за Въведение в веригите на Марков ще ви помогне да разберете основната идея зад веригите на Марков и как те могат да бъдат моделирани като решение на реални проблеми.

Ето списък с теми, които ще бъдат разгледани в този блог:

1. Какво е верига на Марков?
2. Какво представлява собствеността на Марков?
3. Разбиране на веригите на Марков с пример
4. Какво е преходна матрица?
5. Марков верига в Python
6. Марковски верижни приложения

За да получите задълбочени познания по наука за данни и машинно обучение с помощта на Python, можете да се регистрирате за живо от Edureka с денонощна поддръжка и доживотен достъп.

Какво е верига на Марков?

Андрей Марков представи за първи път веригите на Марков през 1906 г. Той обясни веригите на Марков като:

Стохастичен процес, съдържащ случайни променливи, преминаващ от едно състояние в друго в зависимост от определени предположения и определени вероятностни правила.

Тези случайни променливите преминават от едното в друго състояние, базирано на важно математическо свойство, наречено Марков имот.

Това ни води до въпроса:

Какво представлява собствеността на Марков?

Дискретно време Марков имот заявява, че изчислената вероятност за случаен процес, преминаващ в следващото възможно състояние, зависи само от текущото състояние и времето и е независима от поредицата състояния, които са го предшествали.

Фактът, че следващото възможно действие / състояние на случаен процес не зависи от последователността на предходни състояния, прави веригите на Марков като процес без памет, който зависи единствено от текущото състояние / действие на променлива.

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

Нека случайният процес да бъде {Xm, m = 0,1,2, ⋯}.

Този процес е марковска верига само ако,

Markov Chain - Въведение в Markov Chains - Edureka

за всички m, j, i, i0, i1, ⋯ im & minus1

За краен брой състояния, S = {0, 1, 2, ⋯, r}, това се нарича крайна верига на Марков.

P (Xm + 1 = j | Xm = i) тук представлява вероятностите за преход от едно състояние в друго. Тук приемаме, че вероятностите за преход са независими от времето.

Което означава, че P (Xm + 1 = j | Xm = i) не зависи от стойността на ‘m’. Следователно можем да обобщим,

Формула на веригата на Марков - Въведение в веригите на Марков - Edureka

Това уравнение представлява веригата Марков.

Сега нека разберем какво точно представляват веригите на Марков с един пример.

Пример за верига на Марков

Преди да ви дам пример, нека дефинираме какво представлява Марков модел:

Какво е модел на Марков?

Моделът на Марков е стохастичен модел, който моделира случайни променливи по такъв начин, че променливите да следват свойството на Марков.

Сега нека разберем как работи модел на Марков с един прост пример.

Както бе споменато по-рано, веригите на Марков се използват в приложения за генериране на текст и автоматично допълване. За този пример ще разгледаме примерно (произволно) изречение и ще видим как то може да бъде моделирано с помощта на вериги на Марков.

Пример за верига на Марков - Въведение в веригите на Марков - Edureka

Горното изречение е нашият пример, знам, че няма много смисъл (не е задължително), това е изречение, съдържащо произволни думи, при което:

1. Ключове означават уникалните думи в изречението, т.е. 5 клавиша (един, два, градушка, щастлив, edureka)

2. Токени означават общия брой думи, т.е. 8 жетона.

Продължавайки напред, трябва да разберем честотата на появата на тези думи, диаграмата по-долу показва всяка дума заедно с число, което обозначава честотата на тази дума.

Клавиши и честоти - Въведение във веригите на Марков - Edureka

Така че лявата колона тук означава клавишите, а дясната колона честотите.

От горната таблица можем да заключим, че ключът „edureka“ се появява четири пъти повече от всеки друг ключ. Важно е да заключим за такава информация, защото тя може да ни помогне да предскажем каква дума може да се появи в определен момент от времето. Ако трябваше да предположа за следващата дума в примерното изречение, щях да отида с „edureka“, тъй като има най-голяма вероятност за поява.

Говорейки за вероятността, трябва да знаете още една мярка претеглени разпределения.

В нашия случай претегленото разпределение за „edureka“ е 50% (4/8), тъй като честотата му е 4 от общо 8 жетона. Останалите ключове (един, два, градушка, щастлив) имат 1/8 шанс да се появят (& асимп 13%).

Сега, когато имаме разбиране за претегленото разпределение и представа за това как конкретни думи се срещат по-често от други, можем да продължим със следващата част.

Разбиране на веригите на Марков - Въведение в веригите на Марков - Edureka

В горната фигура съм добавил две допълнителни думи, които означават началото и края на изречението, ще разберете защо направих това в долния раздел.

Сега нека определим честотата и за тези клавиши:

Актуализирани клавиши и честоти - Въведение във веригите на Марков - Edureka

Сега нека създадем модел на Марков. Както бе споменато по-рано, модел на Марков се използва за моделиране на случайни променливи в определено състояние по такъв начин, че бъдещите състояния на тези променливи зависят единствено от тяхното текущо състояние, а не от миналите им състояния.

Така че основно в един модел на Марков, за да предскажем следващото състояние, трябва да разгледаме само текущото състояние.

На диаграмата по-долу можете да видите как всеки знак в нашето изречение води до друг. Това показва, че бъдещото състояние (следващ маркер) се основава на текущото състояние (настоящ маркер). Така че това е най-основното правило в модела на Марков.

Диаграмата по-долу показва, че има двойки жетони, при които всеки жетон в двойката води до другия в същата двойка.

Марковски верижни двойки - Въведение в Марковските вериги - Edureka

В диаграмата по-долу създадох структурно представяне, което показва всеки ключ с масив от следващи възможни символи, с които може да се сдвои.

Масив от двойки вериги на Марков - Въведение в веригите на Марков - Edureka

За да обобщим този пример, разгледайте сценарий, при който ще трябва да формирате изречение, като използвате масива от ключове и символи, които видяхме в горния пример. Преди да преминем през този пример, друг важен момент е, че трябва да посочим две първоначални мерки:

1. Начално разпределение на вероятността (т.е. началното състояние във времето = 0, (клавиш ‘Старт’))

2. Вероятност за преход от прескачане от едно състояние в друго (в този случай вероятността за преминаване от един знак в друг)

   карта страна се присъедини в кошер

Определихме претегленото разпределение в самото начало, така че имаме вероятностите и началното състояние, сега нека продължим с примера.

• Така че да започнем с първоначалния знак е [Старт]

• След това имаме само един възможен знак, т.е. [един]

• Понастоящем изречението има само една дума, т.е. „една“

• От този знак следващият възможен знак е [edureka]

• Изречението е актуализирано до „един edureka“

• От [edureka] можем да преминем към някой от следните символи [два, градушка, щастлив, край]

• Има 25% шанс „две“ да бъдат избрани, това може да доведе до формиране на оригиналното изречение (един edureka два edureka здравей edureka щастлив edureka). Ако обаче е избрано „end“, процесът спира и ние в крайна сметка ще генерираме ново изречение, т.е. „one edureka“.

Потупайте се по гърба, защото просто сте изградили модел на Марков и сте проверили тестов случай. За да обобщим горния пример, ние основно използвахме настоящото състояние (настояща дума), за да определим следващото състояние (следващата дума). И точно това е процесът на Марков.

Това е стохастичен процес, при който случайни променливи преминават от едно състояние в друго по такъв начин, че бъдещото състояние на променлива да зависи само от настоящото състояние.

Нека да преминем към следващата стъпка и да извадим модела на Марков за този пример.

Диаграма на прехода на държавата - Въведение в веригите на Марков - Edureka

Горната фигура е известна като диаграма на държавния преход. Ще говорим повече за това в раздела по-долу, засега не забравяйте, че тази диаграма показва преходите и вероятността от едно състояние в друго.

Забележете, че всеки овал на фигурата представлява ключ и стрелките са насочени към възможните клавиши, които могат да го следват. Също така, тежестите на стрелките означават вероятност или претегленото разпределение на преминаване от / към съответните състояния.

Така че всичко беше свързано с това как работи Марковският модел. Сега нека се опитаме да разберем някои важни терминологии в Марковския процес.

Какво е матрица на вероятността за преход?

В горния раздел обсъдихме работата на един марковски модел с прост пример, сега нека разберем математическите терминологии в един марковски процес.

В Марков процес използваме матрица, за да представим вероятностите за преход от едно състояние в друго. Тази матрица се нарича Преходна или вероятностна матрица. Обикновено се обозначава с P.

Преходна матрица - Въведение в веригите на Марков - Edureka

Забележете, pij & ge0 и „i“ за всички стойности е,

Формула на преходна матрица - Въведение в веригите на Марков - Edureka

Позволете ми да обясня това. Ако приемем, че сегашното ни състояние е „i“, следващото или предстоящото състояние трябва да бъде едно от потенциалните състояния. Следователно, докато вземаме сумирането на всички стойности на k, трябва да получим едно.

Какво представлява диаграмата за преход на държавата?

Модел на Марков е представен от диаграма на прехода на държавата. Диаграмата показва преходите между различните състояния във верига на Марков. Нека разберем матрицата за преход и матрицата за преход на състоянието с пример.

Пример за матрица на прехода

Да разгледаме верига на Марков с три състояния 1, 2 и 3 и следните вероятности:

Пример за матрица на прехода - Въведение във веригите на Марков - Edureka

Пример за диаграма на прехода на държавата - Въведение във веригите на Марков - Edureka

Горната диаграма представлява диаграмата за преход на състоянието за веригата на Марков. Тук 1,2 и 3 са трите възможни състояния, а стрелките, сочещи от едно състояние в друго състояние, представляват вероятностите за преход pij. Когато pij = 0, това означава, че няма преход между състояние „i“ и състояние „j“.

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

Марков верига в Python

За да стартирам тази демонстрация, ще използвам Python, така че ако не познавате Python, можете да преминете през следните блогове:

2. Как да научим Python 3 от Scratch - Ръководство за начинаещи

Сега да започнем с кодирането!

Марков верижен генератор на текст

Декларация за проблема: За да приложите свойството на Марков и да създадете модел на Марков, който може да генерира симулации на текст чрез изучаване на набора от данни на речта на Доналд Тръмп.

Описание на набора от данни: Текстовият файл съдържа списък с речи, изнесени от Доналд Тръмп през 2016 г.

Логика: Приложете Markov Property, за да генерирате речта на Donald’s Trump, като разгледате всяка дума, използвана в речта, и за всяка дума създайте речник от думи, които се използват по-нататък.

Стъпка 1: Импортирайте необходимите пакети

импортиране на numpy като np

Стъпка 2: Прочетете набора от данни

trump = open ('C: //Users//NeelTemp//Desktop//demos//speeches.txt', encoding = 'utf8'). read () #display the data print (trump) ГОВОР 1 ... Благодаря ти толкова много. Това е толкова хубаво. Не е ли страхотен човек. Той не получава честна преса, той не го получава. Просто не е честно. И трябва да ви кажа, че съм тук и много силно тук, защото изпитвам голямо уважение към Стив Кинг и също така уважавам гражданите на Обединените, Дейвид и всички, и огромна респект към чаеното парти. Също така, и хората от Айова. Те имат нещо общо. Трудолюбиви хора ....

Стъпка 3: Разделете набора от данни на отделни думи

corpus = trump.split () # Показване на печата на корпуса (корпус) „мощно“, „но“, „не“, „мощно“, „като“, „нас.“, „Иран“, „има“, „ засято ',' терор ', ...

След това създайте функция, която генерира различните двойки думи в речите. За да спестим място, ще използваме обект генератор.

Стъпка 4: Създаване на двойки към ключове и последващи думи

def make_pairs (корпус): за i в обхват (len (корпус) - 1): добив (корпус [i], корпус [i + 1]) двойки = make_pairs (корпус)

След това нека инициализираме празен речник, за да съхраним двойките думи.

В случай, че първата дума от двойката вече е ключ в речника, просто добавете следващата потенциална дума към списъка с думи, които следват думата. Но ако думата не е ключ, създайте нов запис в речника и задайте ключа, равен на първата дума в двойката.

Стъпка 5: Добавяне на речника

word_dict = {} за word_1, word_2 по двойки: ако word_1 в word_dict.keys (): word_dict [word_1] .append (word_2) else: word_dict [word_1] = [word_2]

След това избираме произволно дума от корпуса, която ще започне веригата на Марков.

Стъпка 6: Изграждане на модела на Марков

#randomly изберете първата дума first_word = np.random.choice (корпус) # Изберете първата дума като главна дума, така че избраната дума да не е взета от между изречението докато first_word.islower (): # Стартирайте веригата от избраната дума верига = [first_word] # Инициализира броя на стимулираните думи n_words = 20

След първата дума всяка дума от веригата се избира на случаен принцип от списъка с думи, последвали тази конкретна дума в речите на Тръмп на живо. Това е показано в кодовия фрагмент по-долу:

за i в обхват (n_words): chain.append (np.random.choice (word_dict [верига [-1]]))

Стъпка 7: Прогнози

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

#Join връща веригата като низ отпечатък ('' .join (верига)) Броят на невероятните хора. А Хилари Клинтън има наши хора и такава страхотна работа. И няма да бием Обама

Това е генерираният текст, който получих, като разгледах речта на Тръмп. Може да няма много смисъл, но е достатъчно добър, за да разберете как веригите на Марков могат да се използват за автоматично генериране на текстове.

Сега нека разгледаме още някои приложения на веригите на Марков и как те се използват за решаване на реални проблеми.

Марковски верижни приложения

Ето списък с реални приложения на веригите на Марков:

1. Google PageRank: Цялата мрежа може да се разглежда като модел на Марков, където всяка уеб страница може да бъде състояние, а връзките или препратките между тези страници могат да се разглеждат като преходи с вероятности. Така че по принцип, независимо на коя уеб страница започвате да сърфирате, шансът да стигнете до определена уеб страница, да речем, X е фиксирана вероятност.

2. Прогноза за въвеждане на думи: Известно е, че веригите на Марков се използват за предсказване на предстоящи думи. Те могат да се използват и при автоматично попълване и предложения.

3. Subreddit симулация: Със сигурност сте попаднали на Reddit и сте имали взаимодействие с една от техните нишки или подредки. Reddit използва симулатор на subreddit, който консумира огромно количество данни, съдържащи всички коментари и дискусии, проведени в техните групи. Използвайки веригите на Марков, симулаторът създава вероятности от дума на дума, за да създава коментари и теми.

4. Генератор на текст: Марковските вериги най-често се използват за генериране на фиктивни текстове или за създаване на големи есета и съставяне на речи. Той се използва и в генераторите на имена, които виждате в мрежата.

Сега, след като знаете как да решите проблем от реалния свят с помощта на Markov Chains, съм сигурен, че сте любопитни да научите повече. Ето списък с блогове, които ще ви помогнат да започнете с други статистически понятия:

С това стигнахме до края на този блог „Въведение в веригите на Марков“. Ако имате въпроси по тази тема, моля, оставете коментар по-долу и ние ще се свържем с вас.

Следете за повече блогове за модерните технологии.

Ако търсите онлайн структурирано обучение по Data Science, edureka! има специално подготвен програма, която ви помага да придобиете експертни познания в областта на статистиката, преборването на данни, изследователския анализ на данни, алгоритмите за машинно обучение като K-Means Clustering, дървета за вземане на решения, случайна гора, наивни Bayes. Ще научите понятията за времеви редове, извличане на текст и въведение в дълбокото обучение. Скоро започват нови партиди за този курс !!