Задача 1. Матрица на вероятностите за преход за дискретна верига на Марков от азти щат в й-та в една стъпка ( аз, й=1, 2). Разпределение на вероятностите по състояния в начален момент T=0 се определя от вектора =(0,1; 0,9). Намирам:

1. матрица R2верижен преход от състояние азв състояние йдве
стъпка;

2. разпределение на вероятностите по състояния в момента T=2;

3. вероятността, че в момента T=1 състоянието на веригата ще бъде A2;

4. стационарно разпределение.

Решение.За дискретна верига на Марков в случай на нейната хомогенност отношението

където P1 е матрицата на вероятностите за преход в една стъпка;
Pn - матрица на вероятностите за преход за n стъпки;

1. Намерете матрицата на прехода P2 в две стъпки

Нека разпределението на вероятността върху състоянията е включено С-та стъпка се определя от вектора
.
Познаване на матрицата PNпреход в n стъпки е възможно да се определи разпределението на вероятностите по състояния на (S+н)-та стъпка . (5)

2. Намерете разпределението на вероятностите за състоянията на системата в момента T=2. Поставяме (5) С=0 и н=2. Тогава .

Получаваме .

3. Намерете разпределението на вероятностите за състоянията на системата в момента T=1.

Поставяме (5) с=0 и н=1, тогава .
Как можете да видите, че вероятността, че в момента T=1 състоянието на веригата ще бъде A2, е равно на p2(1)=0,69.
Разпределението на вероятностите по състояния се нарича стационарно, ако не се променя от стъпка на стъпка, т.е
Тогава от връзката (5) при н=1 получаваме

4. Намерете стационарното разпределение. Тъй като =2 имаме =(p1; p2). Нека запишем системата линейни уравнения(6) в координатна форма

Последното условие се нарича нормализиране. В система (6) едно уравнение винаги е линейна комбинация от други. Следователно може да бъде изтрит. Нека решим съвместно първото уравнение на системата и нормализационното. Имаме 0,6 p1=0,3p2, това е p2=2p1. Тогава p1+2p1=1 или т.е. Следователно,.
Отговор:
1) двустепенната матрица на прехода за дадена верига на Марков има формата ;
2) разпределението на вероятностите по състоянията в момента T=2 е равно ;
3) вероятността, че в момента T=1 състоянието на веригата ще бъде A2, е равно на p2(T)=0,69;
4) стационарното разпределение има формата

Дадена е матрица интензитети на преходите на непрекъсната верига на Марков. Съставете обозначена графика на състоянието, съответстваща на матрицата Λ; начертайте система диференциални уравненияКолмогоров за вероятностите на състоянието; намерете граничното разпределение на вероятностите. Решение.Хомогенна верига на Марков с крайно числодържави A1, A2,…НОсе характеризира с матрицата на интензитета на прехода ,

където - интензивността на прехода на веригата на Марков от държавата AIв състояние Aj; рij(Δt)- вероятност за преход Ai→Ajна интервал от време Δ T.

Удобно е да се определят преходите на системата от състояние към състояние, като се използва етикетирана графика на състоянието, върху която са маркирани дъги, съответстващи на интензитетите λ ij>0. Съставете обозначена графика на състоянието за дадена матрицаинтензитети на прехода

Нека е векторът на вероятността Рj(T),
й=1, 2,…,, системата е в състояние НОйв момента T.

Очевидно е, че 0≤ Рj(T)≤1 и . Тогава по правилото за диференциране векторна функция скаларен аргументполучаваме . Вероятности Рj(T)удовлетворяват системата от диференциални уравнения на Колмогоров (SDUK), която в матрична форма има формата . (7)

Ако в началния момент системата е била в състояние Aj, тогава SDUK трябва да се реши при първоначалните условия
Раз(0)=1, рj(0)=0, j≠i,j=1, 2,…,. (8)
Множеството от SDUK (7) и начални условия (8) еднозначно описва хомогенна верига на Марков с непрекъснато времеи краен брой състояния.
Нека съставим SDUK за дадена верига на Марков. Тъй като =3, тогава й=1, 2, 3.

От съотношението (7) получаваме

.
Следователно ще имаме

Последното условие се нарича нормализиране.
Разпределението на вероятностите по състояния се нарича стационарен, ако не се променя с времето, тоест къде Рj=конст, й=1,2,…,. Оттук .

Тогава от SDUK (7) получаваме система за намиране на стационарното разпределение
(9)
За този проблем от СДУК ще имаме

От условието за нормализиране получаваме 3p2+p2+p2=1или . Следователно граничното разпределение има формата .
Обърнете внимание, че този резултат може да се получи директно от етикетираната графика на състоянието, като се използва правилото: за стационарно разпределение сумата от продуктите λ джипи, j≠аз, за стрели, излизащи от азто състояние е равно на сбора от продуктите λ джипи, j≠аз, за стрелките, включени в азта държава. Наистина ли,

Очевидно е, че получената система е еквивалентна на тази, съставена според SDUK. Следователно има същото решение.
Отговор: стационарното разпределение има формата .

Веригата на Марков е поредица от събития, в които всяко следващо събитие зависи от предишното. В статията ще анализираме тази концепция по-подробно.

Марковската верига е често срещан и доста прост начин за моделиране случайни събития. Използва се в различни области, от генериране на текст до финансово моделиране. от най-много известен примере SubredditSimulator. AT този случайВеригата на Марков се използва за автоматизиране на създаването на съдържание в целия subreddit.

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

Сценарий

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

Сега искате да научите как да прогнозирате времето за утре. Интуитивно разбирате, че времето не може да се промени драматично за един ден. Много фактори влияят върху това. Утрешното време зависи пряко от текущото и т. н. Така че, за да прогнозирате времето, събирате данни за няколко години и стигате до извода, че след облачен ден вероятността за слънчев ден е 0,25. Логично е да приемем, че вероятността за два облачни дни подред е 0,75, тъй като имаме само две възможни метеорологични условия.

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

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

Имайте предвид, че в примера разпределението на вероятностите зависи само от преходите от текущия ден към следващия. то уникален имотМарков процес - прави това без да използва памет. По правило такъв подход не е в състояние да създаде последователност, в която да се наблюдава някаква тенденция. Например, докато веригата на Марков е в състояние да симулира стил на писане въз основа на честотата на дума, тя не е в състояние да създава текстове с дълбок смисъл, тъй като може да работи само с големи текстове. Ето защо веригата на Марков не може да произведе зависимо от контекста съдържание.

Модел

Формално веригата на Марков е вероятностен автомат. Разпределението на вероятността за преход обикновено се представя като матрица. Ако веригата на Марков има N възможни състояния, тогава матрицата ще изглежда като N x N, в която записът (I, J) ще бъде вероятността за преход от състояние I към състояние J. В допълнение, такава матрица трябва да бъде стохастична , т.е. сборът на редове или колони трябва да е едно. В такава матрица всеки ред ще има собствено разпределение на вероятностите.

Общ изглед на верига на Марков със състояния под формата на кръгове и ръбове под формата на преходи.

Приблизителна матрица на прехода с три възможни състояния.

Веригата на Марков има вектор на началното състояние, представен като матрица N x 1. Той описва вероятностните разпределения за стартиране във всяко от N възможни състояния. Записът I описва вероятността за стартиране на веригата в състояние I.

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

Вече обсъдихме как да получим вероятността за преход от едно състояние в друго, но какво да кажем за получаването на тази вероятност в няколко стъпки? За да направим това, трябва да определим вероятността за преход от състояние I към състояние J в M стъпки. Всъщност е много просто. Матрицата на прехода P може да се определи чрез изчисляване (I, J) чрез повишаване на P до степента на M. За малки стойности на M това може да се направи ръчно чрез многократно умножение. Но за големи стойности M, ако сте запознати с линейната алгебра, повече ефективен начинповдигането на матрица на степен първо ще диагонализира тази матрица.

Марковска верига: заключение

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

Всички възможни състояния на системата в хомогенна верига на Марков и е стохастичната матрица, определяща тази верига, съставена от вероятности за преход (Вижте страница 381).

Означава се с вероятността системата да е в състояние в даден момент, ако е известно, че в момента системата е била в състояние (,). очевидно, . Използвайки теоремите за събиране и умножение на вероятности, можем лесно да намерим:

или в матрична нотация

Следователно, давайки последователно стойностите на , получаваме важната формула

Ако има граници

или в матрична нотация

след това количествата се наричат ​​ограничаващи или крайни преходни вероятности.

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

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

Редовната матрица се характеризира с факта, че в нормалната си форма (69) (стр. 373) матриците са примитивни. За обикновена матрица, допълнително.

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

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

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

Наистина, нека е минималният полином на редовна матрица . Тогава

Съгласно теорема 10 можем да приемем, че

Въз основа на формула (24) гл. V (страница 113)

(96)

където е редуцираната присъединена матрица и

Ако е редовна матрица, тогава

и следователно от дясната страна на формула (96) всички членове, с изключение на първия, клонят към нула като . Следователно, за редовна матрица има матрица, съставена от ограничаващи вероятности за преход и

Обратното е очевидно. Ако има пропуск

тогава матрицата не може да има характерно число, за които , и , тъй като тогава границата не би съществувала [Същата граница трябва да съществува поради съществуването на границата (97").]

Доказахме, че за правилна (и само правилна) хомогенна верига на Марков съществува матрица . Тази матрица се определя по формула (97).

Нека покажем как матрицата може да бъде изразена чрез характеристичния полином

и свързаната матрица .

От самоличността

по силата на (95), (95") и (98) следва:

Следователно формула (97) може да бъде заменена с формулата

(97)

За редовна верига на Марков, тъй като тя е специален вид правилна верига, матрицата съществува и се определя от всяка от формулите (97), (97"). В този случай формулата (97") също има формата

2. Разгледайте правилна верига от общ тип (неправилна). Записваме съответната матрица в нормална форма

(100)

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

,

напишете във формата

(101)

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

(102)

Тъй като са примитивни стохастични матрици, то матриците по формули (99) и (35) (стр. 362) са положителни

и във всяка колона на която и да е от тези матрици всички елементи са равни един на друг:

.

Обърнете внимание, че нормалната форма (100) на стохастичната матрица съответства на разделянето на състоянията на системата на групи:

Всяка група в (104) съответства на своя собствена група серии в (101). Съгласно терминологията на Л. Н. Колмогоров, състоянията на системата, включени в, се наричат ​​съществени, а състоянията, включени в останалите групи, се наричат ​​несъществени.

От формата (101) на матрицата следва, че за всеки краен брой стъпки (от момент до момент) е възможен само преходът на системата а) от съществено състояние към съществено състояние от същата група, b ) от несъществено състояние към съществено състояние и в) от незначително състояние към несъществено състояние на същата или по-ранна група.

От формата (102) на матрицата следва, че в процеса, когато преходът е възможен само от всяко състояние към съществено състояние, т.е. вероятността за преход към всяко незначително състояние клони към нула с броя на стъпките. Следователно основните състояния понякога се наричат ​​също гранични състояния.

3. От формула (97) следва:

.

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

За редовна матрица числото 1 е прост корен на характеристичното уравнение и това число съответства само на един (до скаларен фактор) матричен собствен вектор. Следователно във всяка колона th на матрицата всички елементи са равни на едно и също неотрицателно число:

По този начин, в правилна верига, ограничаващите вероятности за преход наистина зависят от първоначалното състояние.

Обратно, ако в някаква правилна хомогенна верига на Марков индивидуалните вероятности за преход не зависят от началното състояние, т.е. формулите (104) са в сила, то в схема (102) за матрицата е задължително . Но тогава веригата също е редовна.

За ациклична верига, която е специален случай на правилна верига, е примитивна матрица. Следователно, за някои (виж теорема 8 на стр. 377). Но тогава и .

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

Формулираме получените резултати под формата на следната теорема:

Теорема 11. 1. За да съществуват всички гранични вероятности за преход в хомогенна верига на Марков, е необходимо и достатъчно веригата да е регулярна. В този случай матрицата, съставена от граничните вероятности за преход, се определя по формула (95) или (98).

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

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

4. Нека въведем колони с абсолютни вероятности

(105)

където е вероятността системата да е в състояние (,) в момента. Използвайки теоремите за събиране и умножение на вероятностите, намираме:

(,),

или в матрична нотация

където е транспонираната матрица за матрицата.

Всички абсолютни вероятности (105) се определят от формула (106), ако са известни първоначалните вероятности и матрицата на вероятностите за преход

Нека да разгледаме пределните абсолютни вероятности

Преминавайки в двете части на равенството (106) до границата при , получаваме:

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

От формула (107) и от формата (102) на матрицата следва, че граничните абсолютни вероятности, съответстващи на незначителни състояния, са равни на нула.

Умножаване на двете страни на равенството на матрицата

вдясно, ние, по силата на (107), получаваме:

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

Ако дадена веригаМарков редовно, тогава е прост корен на характеристичното уравнение на матрицата . В този случай колоната на граничните абсолютни вероятности е еднозначно определена от (108) (тъй като и ).

Нека е дадена редовна верига на Марков. Тогава от (104) и от (107) следва:

(109)

В този случай граничните абсолютни вероятности не зависят от първоначалните вероятности.

Обратно, може да не зависи от при наличие на формула (107), ако и само ако всички редове на матрицата са еднакви, т.е.

,

и следователно (по Теорема 11) е правилна матрица.

Ако е примитивна матрица, тогава , и следователно поради (109)

Обратно, ако всички и не зависят от началните вероятности, тогава във всяка колона на матрицата всички елементи са еднакви и съгласно (109) , а това според теорема 11 означава, че е примитивна матрица, т.е. това веригата е ациклична.

От горното следва, че теорема 11 може да се формулира по следния начин:

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

2. За да има хомогенна верига на Марков гранични абсолютни вероятности за всякакви начални вероятности и да не зависи от тези начални вероятности, е необходимо и достатъчно веригата да е регулярна.

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

5. Помислете сега за хомогенната верига на Марков общ типс матрицата на вероятностите за преход.

Нека вземем нормалната форма (69) на матрицата и означим с индексите на импримитивност на матриците в (69). Нека е най-малкото общо кратно на цели числа. Тогава матрицата няма характерни числа, равни по абсолютна стойност на единица, но различни от единица, т.е. е правилна матрица; в същото време - най-малкият индикатор, при който - правилната матрица. Наричаме число период на дадена хомогенна верига на Марков и. Обратно, ако и определени с формули (110) и (110").

Средните гранични абсолютни вероятности, съответстващи на несъществени състояния, винаги са равни на нула.

Ако има число в нормалната форма на матрицата (и само в този случай), средните гранични абсолютни вероятности не зависят от първоначалните вероятности и се определят еднозначно от уравнение (111).

Тази статия дава Главна идеяза това как да генерирате текстове чрез моделиране на марковски процеси. По-специално ще се запознаем с вериги на Марков, а като практика ще имплементираме малък текстов генератор в Python.

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

Марков процес T T

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

Какво означава всичко това? Нека да го разберем.

Основи

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

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

И запишете броя на срещанията на всяка от връзките в текста:

Картината по-горе показва, че думата рибасе появява в текста 4 пъти по-често от всяка друга дума ( Едно, две, червено, синьо). Тоест вероятността да срещнем думата в нашия корпус риба 4 пъти по-висока от вероятността да срещнете всяка друга дума в картината. Говорейки на езика на математиката, можем да определим закона за разпределение на случайна променлива и да изчислим с каква вероятност една от думите ще се появи в текста след текущата. Вероятността се изчислява по следния начин: трябва да разделите броя на срещанията на думата, от която се нуждаем в корпуса, на общ бройвсички думи в него. За думата рибатази вероятност е 50%, тъй като се появява 4 пъти в изречение от 8 думи. За всяка от останалите връзки тази вероятност е 12,5% ​​(1/8).

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

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

Същността на определението

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

Всяко изречение съдържа тези невидими „начало“ и „край“, нека ги добавим като връзки към нашето разпространение:

Да се ​​върнем към дефиницията, дадена в началото на статията:

Марков процесе случаен процес, чиято еволюция след всяка зададена стойноствремеви параметър Tне зависи от еволюцията, която предшества T, при условие че стойността на процеса в този момент е фиксирана.

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

И така, какво означава това? Грубо казано, ние моделираме процес, при който състоянието на системата в следващия момент зависи само от нейното състояние в текущия момент и по никакъв начин не зависи от всички предишни състояния.

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

Така се образуват двойки думи (дори краят на изречението има своя двойка - празна стойност):

Нека групираме тези двойки по първата дума. Ще видим, че всяка дума има свой собствен набор от връзки, които в контекста на нашето изречение можеСледвай го:

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

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

Пример.Да започнем с думата Започнете. След това изберете дума един, тъй като по нашата схема е една дума, които могат да следват началото на изречението. Зад думата единсъщо може да последва само една дума - риба. Сега новото предложение в междинния вариант изглежда така Една риба. Освен това ситуацията се усложнява рибадумите могат да вървят с еднаква вероятност в 25% "две", "червено", "синьо"и край на изречението Край. Ако приемем, че следващата дума е - "две"реконструкцията ще продължи. Но можем да изберем връзка Край. В този случай, въз основа на нашата схема, произволно ще бъде генерирано изречение, което е много различно от корпуса - Една риба.

Току-що моделирахме марковски процес - всяка следваща дума сме определяли само на базата на знания за текущата. За пълното усвояване на материала, нека изградим диаграми, които показват зависимостите между елементите в нашия корпус. Овалите представляват връзки. Стрелките водят до потенциални връзки, които могат да следват думата в овала. До всяка стрелка - вероятността, с която следващата връзка ще се появи след текущата:

Отлично! Научихме необходимата информацияда продължим напред и да анализираме по-сложни модели.

Разширяване на речниковия запас

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

Нека вземем още четири цитата от същия автор (също на английски, няма да ни навреди):

„Днес ти си ти. Това е по-вярно от истината. Няма никой жив, който да е теб - ъ-е от теб."

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

"Колкото повече че тиПрочети, колкото повеченеща, които ще знаете. Колкото повече научите, толкова повече места ще отидете."

Мислете наляво и мислете надясно, мислете ниско и мислете високо. О, мислите, които можете да измислите, само ако опитате."

Сложността на корпуса се увеличи, но в нашия случай това е само плюс - сега текстовият генератор ще може да произвежда по-смислени изречения. Факт е, че във всеки език има думи, които се срещат в речта по-често от други (например използваме предлога „в“ много по-често от думата „криогенен“). как повече думив нашия корпус (а оттам и зависимостите между тях), толкова повече информация има генераторът за това коя дума е най-вероятно да се появи в текста след текущата.

Най-лесният начин да се обясни това е от гледна точка на програмата. Знаем, че за всяка връзка има набор от думи, които могат да я следват. Освен това всяка дума се характеризира с броя на нейните появявания в текста. Трябва по някакъв начин да съберем цялата тази информация на едно място; речник, който съхранява двойки "(ключ, стойност)" е най-подходящ за тази цел. Ключът на речника ще запише текущото състояние на системата, тоест една от връзките в корпуса (напр. "на"на снимката по-долу); и друг речник ще бъде съхранен в стойността на речника. Във вложен речник ключовете ще бъдат думи, които могат да се появяват в текста след текущата единица на корпуса ( "мисли"и Повече ▼може да влезе в текста след "на"), а стойностите - броят на срещанията на тези думи в текста след нашата връзка (думата "мисли"се появява в текста след думата "на" 1 път, дума Повече ▼след думата "на"- 4 пъти):

Прочетете отново параграфа по-горе няколко пъти, за да го разберете правилно. Моля, имайте предвид, че вложеният речник в този случай е същата хистограма, той ни помага да проследим връзките и честотата на тяхното появяване в текста спрямо други думи. Трябва да се отбележи, че дори такава речникова база е много малка за правилното генериране на текстове в естествен език- трябва да съдържа повече от 20 000 думи, а за предпочитане - повече от 100 000. И още по-добре - повече от 500 000. Но нека да разгледаме речниковата база, която имаме.

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

Повече ▼:

Тоест, ако текущата дума е думата Повече ▼, след него може да има думи с еднаква вероятност от 25% "неща"и "места", а с вероятност от 50% - думата "че". Но вероятностите могат да бъдат и всички са равни една на друга:

мисля:

Работа с прозорци

Досега сме разглеждали само прозорци с една дума. Можете да увеличите размера на прозореца, така че текстовият генератор да произвежда повече "проверени" изречения. Това означава, че колкото по-голям е прозорецът, толкова по-малко ще бъде отклонението от корпуса по време на генерирането. Увеличаването на размера на прозореца съответства на прехода на веригата на Марков към повече висок ред. Преди това изградихме верига от първи ред, за прозорец от две думи получаваме верига от втори ред, от три - от трети и т.н.

прозорецса данните в сегашно състояниесистеми, които се използват за вземане на решения. Ако комбинираме голям прозорец и малък набор от данни, вероятно ще получим едно и също изречение всеки път. Нека вземем речниковата база от нашия първи пример и разширим прозореца до размер 2:

Разширението доведе до това, че всеки прозорец вече има само една опция за следващото състояние на системата - без значение какво правим, винаги ще получаваме едно и също изречение, идентично с нашия корпус. Ето защо, за да експериментирате с прозорци и генераторът на текст да върне уникално съдържание, запасете се с речников запас от 500 000 думи или повече.

Внедряване в Python

Диктограма структура на данните

Диктограмата (dict е вграден тип речникови данни в Python) ще покаже връзката между връзките и тяхната честота на появяване в текста, т.е. тяхното разпределение. Но в същото време ще има речниковото свойство, от което се нуждаем - времето за изпълнение на програмата няма да зависи от количеството входни данни, което означава, че създаваме ефективен алгоритъм.

Импортиране на случаен клас Dictogram(dict): def __init__(self, iterable=None): # Инициализиране на нашата дистрибуция като нов клас обект, # добавяне на съществуващи елементи super(Dictogram, self).__init__() self.types = 0 # брой от уникални ключове в разпространението self.tokens = 0 # обща сумана всички думи в разпределението if iterable: self.update(iterable) def update(self, iterable): # Актуализиране на разпределението с елементи от # съществуващия итерируем набор от данни за елемент в iterable: if item in self: self += 1 self .tokens += 1 else: self = 1 self.types += 1 self.tokens += 1 def count(self, item): # Връща стойността на брояча на елемента или 0, ако елементът е в self: return self return 0 def return_random_word (self): random_key = random.sample(self, 1) # Друг начин: # random.choice(histogram.keys()) return random_key def return_weighted_random_word(self): # Генериране на псевдослучайно число между 0 и (n- 1), # където n е общият брой думи random_int = random.randint(0, self.tokens-1) index = 0 list_of_keys = self.keys() # print "random index:", random_int for i in range( 0, self.types): index += self] # печат на индекс if(index > random_int): # print list_of_keys[i] return list_of_keys[i]

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

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

Структура на веригата на Марков

от хистограми import Диктограма def make_markov_model(data): markov_model = dict() for i in range(0, len(data)-1): if data[i] in markov_model: # Просто добавете към вече съществуващо markov_model distribution].update ( ]) else: markov_model] = Диктограма(]) връща markov_model

В реализацията по-горе имаме речник, който съхранява windows като ключ в двойката „(ключ, стойност)“ и разпределения като стойности в тази двойка.

Структура на верига на Марков от N-ти ред

от хистограми import Диктограма def make_higher_order_markov_model(order, data): markov_model = dict() for i in range(0, len(data)-order): # Създаване на прозорец window = tuple(data) # Добавяне към речника, ако прозорец в markov_model: # Прикрепете към съществуващо разпространение markov_model.update(]) else: markov_model = Dictogram(]) return markov_model

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

Анализ на модела

Страхотно, въведохме речник. Но как сега да генерираме съдържание въз основа на текущото състояние и да преминем към следващото състояние? Нека да преминем през нашия модел:

От хистограми import Диктограма import random from collections import deque import re def generate_random_start(model): # За генериране на начална дума, разкоментирайте реда: # return random.choice(model.keys()) # За генериране на "правилната" начална дума , използвайте кода по-долу: # Правилно начални думиса тези, които са били началото на изречения в if "END" в моделния корпус: seed_word = "END" while seed_word == "END": seed_word = model["END"].return_weighted_random_word() return seed_word return random.choice( модел .keys()) def generate_random_sentence(length, markov_model): current_word = generate_random_start(markov_model) sentence = for i in range(0, length): current_dictogram = markov_model random_weighted_word = current_dictogram.return_weighted_random_word() current_word = random_weighted_word sentence.append(current_word) ) изречение = изречение.capitalize() return " ".join(изречение) + "." обратно изречение

Какво следва?

Опитайте се да помислите къде вие ​​сами можете да използвате текстов генератор, базиран на вериги на Марков. Само не забравяйте, че най-важното е как анализирате модела и какви специални ограничения поставяте върху генерирането. Авторът на тази статия, например, използва голям прозорец, когато създава генератора на туитове, ограничава генерираното съдържание до 140 знака и използва само „правилни“ думи, за да започне изреченията, тоест тези, които са били началото на изреченията в корпус.

Начини математически описанияМарковските стохастични процеси в система с дискретни състояния (ДС) зависят от това в кои моменти от време (предварително известни или произволни) могат да настъпят преходите на системата от състояние в състояние.
Ако преходът на системата от състояние в състояние е възможен в предварително фиксирани часове, имаме работа с случаен Марков процесс дискретно време.Ако преходът е възможен във всеки произволен момент, тогава имаме работа с случаен марковски процес с непрекъснато време.
Нека има физическа система С, което може да е в ндържави С 1 , С 2 , …, S n. Преходите от състояние в състояние са възможни само от време на време T 1 , T 2 , …, t kНека наречем тези моменти от времето стъпки. Ще разгледаме SP в системата Скато функция на целочисления аргумент 1, 2, ..., к, където аргументът е номерът на стъпката.
Пример: С 1 → С 2 → С 3 → С 2 .
Нека обозначим Si (к) е събитие, състоящо се в това, че след кстъпки системата е в състояние S аз.
За всякакви ксъбития S 1 ( к), S 2 ( к),…, С н (к) форма пълна група от събитияи са несъвместими.

Процесът в системата може да се представи като верига от събития.
Пример: С 1 (0) , С 2 (1), S 3 (2), S 5 (3),….
Такава последователност се нарича Маркова верига , ако за всяка стъпка вероятността за преход от всяко състояние Siвъв всяко състояние S jне зависи от това кога и как системата е дошла до държавата Si.
Нека по всяко време след всяко к-go step система Сможе да бъде в един от щатите С 1 , С 2 , …, S n, т.е. може да възникне едно събитие от пълна група събития: С 1 (к), S 2 ( к) , …, S n (к) . Нека обозначим вероятностите за тези събития:
П 1 (1) = П(С 1 (1)); П 2 (1) = П(С 2 (1)); …; P n(1) = П(S n (к));
П 1 (2) = П(С 1 (2)); П 2 (2) = П(S2(2)); …; P n(2) = П(S n (2));
П 1 (к) = П(С 1 (к)); П 2 (к) = П(С 2 (к)); …; P n(к) = П(S n (к)).
Лесно се вижда, че за всяка стъпка номер условието
П 1 (к) + П 2 (к) +…+ P n(к) = 1.
Нека наречем тези вероятности вероятности за състояние.следователно задачата ще звучи по следния начин: намерете вероятностите за състоянията на системата за всяко к.
Пример.Нека има някаква система, която може да бъде във всяко от шестте състояния. тогава процесите, протичащи в него, могат да бъдат изобразени или под формата на графика на промените в състоянието на системата (фиг. 7.9, а), или под формата на графика на системните състояния (фиг. 7.9, b).

а)

Ориз. 7.9
Освен това процесите в системата могат да бъдат изобразени като последователност от състояния: С 1 , С 3 , С 2 , С 2 , С 3 , С 5 , С 6 , С 2 .
Вероятност за състоянието на ( к+ 1)-та стъпка зависи само от състоянието при к- m стъпка.
За всяка стъпка кима някои вероятности за преминаване на системата от всяко състояние към всяко друго състояние, нека наречем тези вероятности вероятности за преход на верига на Марков.
Някои от тези вероятности ще бъдат 0, ако преходът от едно състояние към друго не е възможен в една стъпка.
Марковата верига се нарича хомогененако преходните състояния не зависят от номера на стъпката, в противен случай се извиква разнородни.
Нека има хомогенна верига на Марков и системата СТо има нвъзможни състояния: С 1 , …, S n. Нека за всяко състояние е известна вероятността за преминаване към друго състояние в една стъпка, т.е. P ij(от Siв S jв една стъпка), тогава можем да запишем вероятностите за преход като матрица.

. (7.1)
По диагонала на тази матрица са вероятностите системата да премине от състоянието Siв същото състояние Si.
Използване на въведените по-рано събития , вероятностите за преход могат да бъдат записани като условни вероятности:
.
Очевидно сборът от членовете във всеки ред на матрицата (1) е равно на единица, тъй като събитията образуват пълна група от несъвместими събития.

При разглеждане на вериги на Марков, както и при анализ на Марков случаен процес, се използват различни графики на състоянието (фиг. 7.10).

Ориз. 7.10

Тази система може да бъде във всяко от шест състояния, докато P ijе вероятността за преминаване на системата от състояние Siв състояние S j. За тази система пишем уравненията, че системата е била в някакво състояние и от него през времето Tне излезе:

AT общ случайверигата на Марков е нехомогенна, т.е. вероятността P ijпромени от стъпка на стъпка. Да предположим, че е дадена матрица на вероятностите за преход на всяка стъпка, тогава вероятността системата Сна к-та стъпка ще бъде в държавата Si, може да се намери с помощта на формулата

Познавайки матрицата на вероятностите за преход и Първоначално състояниесистема, можете да намерите вероятностите на състоянията след всяка к-та стъпка. Нека в началния момент системата е в състояние S m. Тогава за t = 0
.
Намерете вероятностите след първата стъпка. Извън държавата S mсистемата ще премине в състояния С 1 , С 2 и т.н. с вероятности следобед 1 , следобед 2 , …, P мм, …, Pmn. Тогава след първата стъпка вероятностите ще бъдат равни

. (7.2)
Нека намерим вероятностите на състоянието след втората стъпка: . Ще изчислим тези вероятности с помощта на формулата пълна вероятностс хипотези:
.
Хипотезите ще бъдат следните твърдения:

• след първата стъпка системата беше в състояние S 1 -H 1 ;
• след втората стъпка системата беше в състояние S 2 -H 2 ;
• след н-та стъпка системата е била в състояние S n -H n .

Вероятностите на хипотезите са известни от израза (7.2). Условни вероятностидържавен преход НОза всяка хипотеза също са известни и записани в матриците на преходното състояние. Тогава, според формулата за обща вероятност, получаваме:

Вероятност за всяко състояние след втората стъпка:

(7.3)
Формула (7.3) обобщава всички вероятности за преход P ij, но се вземат предвид само тези, различни от нула. Вероятността за всяко състояние след к-та стъпка:

(7.4)
По този начин вероятността от състоянието след к-та стъпка се определя от повтаряща се формула(7.4) по отношение на вероятностите ( к- 1)та стъпка.

Задача 6.Дадена е матрицата на вероятностите за преход за верига на Марков в една стъпка. Намерете матрицата на прехода на дадена верига в три стъпки .
Решение.Преходната матрица на една система е матрица, която съдържа всички преходни вероятности на тази система:

Всеки ред от матрицата съдържа вероятностите за събития (преход от състояние азв състояние й), които образуват пълна група, така че сумата от вероятностите за тези събития е равна на единица:

Означаваме с p ij (n) вероятността в резултат на n стъпки (тестове) системата да премине от състояние i в състояние j. Например p 25 (10) - вероятността за преход от второ състояние към пето в десет стъпки. Обърнете внимание, че за n=1 получаваме вероятности за преход p ij (1)=p ij .
Изправени сме пред задачата: знаейки вероятностите за преход p ij , да намерим вероятностите p ij (n) на прехода на системата от състоянието азв състояние йпер нстъпки. За да направим това, въвеждаме междинен (между ази й) състояние r. С други думи, ще приемем, че от първоначалното състояние азпер мстъпки, системата ще премине в междинно състояние rс вероятност p ij (n-m) , след което за останалите n-m стъпкиот междинното състояние r ще премине в крайното състояние j с вероятност p ij (n-m) . Според формулата за обща вероятност получаваме:
.
Тази формула се нарича равенство на Марков. Използвайки тази формула, можете да намерите всички вероятности p ij (n) и, следователно, самата матрица P n. Тъй като матричното смятане води до целта по-бързо, нека запишем матричното отношение, следващо от получената формула, в общ вид.
Изчислете преходната матрица на веригата на Марков в три стъпки, като използвате получената формула:

Отговор:.

Задача №1. Матрицата на вероятностите за преход за веригата на Марков е:
.
Разпределението по състояния в момент t=0 се определя от вектора:
π 0 \u003d (0,5; 0,2; 0,3)
Намирам:а) разпределение по състояния в моментите t=1,2,3,4 .
в) стационарно разпределение.