Марковский процесс - протекающий в системе случайный процесс, который обладает свойством: для каждого момента времени t 0 вероятность любого состояния системы в будущем (при t>t 0) зависит только от ее состояния в настоящем (при t= t 0) и не зависит от того, когда и каким образом система пришла в это состояние (т.е. как развивался процесс в прошлом).

На практике часто встречаются случайные процессы, которые с той или иной степенью приближения можно считать Марковскими.

Любой марковский процесс описывают с помощью вероятностей состояний и переходных вероятностей.

Вероятности состояний P k (t) марковского процесса – это вероятности того, что случайный процесс (система) в момент времени t находится в состоянии S k:

Переходные вероятности марковского процесса – это вероятности перехода процесса (системы) из одного состояния в другое:

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

Наиболее простым процессом является цепь Маркова – марковский случайный процесс с дискретным временем и дискретным конечным множеством состояний.

При анализе цепи Маркова составляют граф состояний , на котором отмечают все состояния цепи (системы) и ненулевые вероятности за один шаг.

Марковскую цепь можно представить себе так, как будто точка, изображающая систему, случайным образом перемещается по графу состояний, перетаскивая за один шаг из состояния в состояние или задерживаясь на несколько шагов в одном и том же состоянии.

Переходные вероятности цепи Маркова за один шаг записывают в виде матрицы P=||P ij ||, которую называют матрицей вероятностей перехода или просто переходной матрицей.

Пример: множество состояний студентов специальности следующие:

S 1 – первокурсник;

S 2 – второкурсник …;

S 5 – студент 5 курса;

S 6 –специалист, окончивший вуз;

S 7 – человек, обучавшийся в вузе, но не окончивший его.

Из состояния S 1 за год возможны переходы в состояние S 2 с вероятностью r 1 ; S 1 с вероятностью q 1 и S 7 с вероятностью p 1 , причем:

r 1 +q 1 +p 1 =1.

Построим граф состояний данной цепи Маркова и разметим его переходными вероятностями (отличными от нуля).

Составим матрицу вероятностей переходов:

Переходные матрицы обладают свойством:

Все их элементы неотрицательны;

Их суммы по строкам равны единице.

Матрицы с таким свойством называют стохастическими.

Матрицы переходов позволяют вычислить вероятность любой траектории цепи Маркова с помощью теоремы умножения вероятностей.

Для однородных цепей Маркова матрицы переходов не зависят от времени.

При изучении цепей Маркова наибольший интерес представляют:

Вероятности перехода за m шагов;

Распределение по состояниям на шаге m→∞;

Среднее время пребывания в определенном состоянии;

Среднее время возвращения в это состояние.

Рассмотрим однородную цепь Маркова с n состояниями. Для получения вероятности перехода из состояния S i в состояние S j за m шагов в соответствии с формулой полной вероятности следует просуммировать произведения вероятности перехода из состояния Siв промежуточное состояние Sk за l шагов на вероятность перехода из Sk в Sj за оставшиеся m-l шагов, т.е.

Это соотношение для всех i=1, …, n; j=1, …,n можно представить как произведение матриц:

P(m)=P(l)*P(m-l).

Таким образом, имеем:

P(2)=P(1)*P(1)=P 2

P(3)=P(2)*P(1)=P(1)*P(2)=P 3 и т.д.

P(m)=P(m-1)*P(1)=P(1)*P(M-1)=P m ,

что дает возможность найти вероятности перехода между состояниями за любое число шагов, зная матрицу переходов за один шаг, а именно P ij (m) – элемент матрицы P(m) есть вероятность перейти из состояния S i в состояние S j за m шагов.

Пример : Погода в некотором регионе через длительные периоды времени становится то дождливой, то сухой. Если идет дождь, то с вероятностью 0,7 он будет идти на следующий день; если в какой-то день сухая погода, то с вероятностью 0,6 она сохраниться и на следующий день. Известно, что в среду погода была дождливая. Какова вероятность того, что она будет дождливой в ближайшую пятницу?

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

Построим граф состояний:

Ответ: р 11 =р(Д пят |Д ср) =0,61.

Пределы вероятностей р 1 (m), р 2 (m),…, р n (m) при m→∞, если они существуют, называются предельными вероятностями состояний .

Можно доказать следующую теорему: если в цепи Маркова из +каждого состояния можно перейти (за то или иное число шагов) в каждое другое, то предельные вероятности состояний существуют и не зависят от начального состояния системы.

Таким образом, при m→∞ в системе устанавливается некоторый предельный стационарный режим, при котором каждое из состояний осуществляется с некоторой постоянной вероятностью.

Вектор р, составленный из предельных вероятностей, должен удовлетворять соотношению: р=p*P.

Среднее время пребывания в состоянии S i за время T равно p i *T, где p i - предельная вероятность состояния S i . Среднее время возвращения в состояние S i равно .

Пример.

Для многих экономических задач необходимо знать чередование годов с определенными значениями годовых стоков рек. Конечно, это чередование не может быть определено абсолютно точно. Для определения вероятностей чередования (перехода) разделим стоки, введя четыре градации (состояния системы): первую (самый низкий сток), вторую, третью, четвертую (самый высокий сток). Будем для определенности считать, что за первой градацией никогда не следует четвертая, а за четвертой – первая из-за накопления влаги (в земле, водохранилище и т.д.). Наблюдения показали, что в некоторой области остальные переходы возможны, и:

а) из первой градации можно переходить в каждую из средних вдвое чаще, чем опять в первую, т.е.

p 11 =0,2; p 12 =0,4; p 13 =0,4; p 14 =0;

б) из четвертой градации переходы во вторую и третью градации бывают в четыре и пять раз чаще, чем возвращениеекак д во вторую, т.е.

твертую, т.е.

в четвертую, т.е.

p 41 =0; p 42 =0,4; p 43 =0,5; p 44 =0,1;

в) из второй в другие градации могут быть только реже: в первую - в два раза, в третью на 25%, в четвертую - в четыре раза реже, чем переход во вторую, т.е.

p 21 =0,2;p 22 =0,4; p 23 =0,3; p 24 =0,1;

г) из третьей градации переход во вторую градацию столь же вероятен, как возвращение в третью градацию, а переходы в первую и четвертую градации бывают в четыре раза реже, т.е.

p 31 =0,1; p 32 =0,4; p 33 =0,4; p 34 =0,1;

Построим граф:

Составим матрицу вероятностей перехода:

Найдем среднее время между засухами и полноводными годами. Для этого нужно найти предельное распределение. Оно существует, т.к. условие теоремы выполняется (матрица Р 2 не содержит нулевых элементов, т.е. за два шага можно перейти из любого состояния системы в любое другое).

Откуда p 4 =0.08; p 3 =; p 2 =; p 1 =0.15

Периодичность возвращения в состояние S i равна .

Следовательно, периодичность засушливых лет в среднем равна 6.85, т.е. 6-7 лет, а дождливых 12 лет.

Цепи Маркова

Введение

§ 1. Цепь Маркова

§ 2. Однородная цепь Маркова. Переходные вероятности. Матрица перехода

§3. Равенство Маркова

§4. Стационарное распределение. Теорема о предельных вероятностях

§5. Доказательство теоремы о предельных вероятностях в цепи Маркова

§6. Области применения цепей Маркова

Заключение

Список использованной литературы

Введение

Тема нашей курсовой работы цепи Маркова. Цепи Маркова названы так в честь выдающегося русского математика, Андрея Андреевича Маркова, который много занимался случайными процессами и внес большой вклад в развитие этой области. В последнее время можно услышать о применении цепей Маркова в самых разных областях: современных веб-технологиях, при анализе литературных текстов или даже при разработке тактики игры футбольной команды. У тех, кто не знает что такое цепи Маркова, может возникнуть ощущение, что это что-то очень сложное и почти недоступное для понимания.

Нет, все как раз наоборот. Цепь Маркова это один из самых простых случаев последовательности случайных событий. Но, несмотря на свою простоту, она часто может быть полезной даже при описании довольно сложных явлений. Цепью Маркова называют такую последовательность случайных событий, в которой вероятность каждого события зависит только от предыдущего, но не зависит от более ранних событий.

Прежде чем углубиться, нужно рассмотреть несколько вспомогательных вопросов, которые общеизвестны, но совершенно необходимы для дальнейшего изложения.

Задача моей курсовой работы – более подробно изучить приложения цепей Маркова, постановку задачи и проблемы Маркова.

§1. Цепь Маркова

Представим, что производится последовательность испытаний.

Определение. Цепью Маркова называют последовательность испытаний, в каждом из которых появляется одно и только одно из

несовместных событий полной группы, причем условная вероятность того, что в -м испытании наступит событие , при условии, что в -м испытании наступило событие , не зависит от результатов предшествующих испытаний.

Например, если последовательность испытаний образует цепь Маркова и полная группа состоит из четырех несовместных событий

, причем известно, что в шестом испытании появилось событие , то условная вероятность того, что в седьмом испытании наступит событие , не зависит от того, какие события появились в первом, втором, …, пятом испытаниях.

Заметим, что независимые испытания являются частным случаем цепи Маркова. Действительно, если испытания независимы, то появление некоторого определенного события в любом испытании не зависит от результатов ранее произведенных испытаний. Отсюда следует, что понятие цепи Маркова является обобщением понятия независимых испытаний.

Часто при изложении теории цепей Маркова придерживаются иной терминология и говорят о некоторой физической системе

, которая в каждый момент времени находится в одном из состояний: , и меняет свое состояние только в отдельные моменты времени то есть система переходит из одного состояния в другое (например из в ). Для цепей Маркова вероятность перейти в какое-либо состояние в момент зависит только от того, в каком состоянии система находилась в момент , и не изменяется от того, что становятся известными ее состояния в более ранние моменты. Так же в частности, после испытания система может остаться в том же состоянии («перейти» из состояния в состояние ).

Для иллюстрации рассмотрим пример.

Пример 1. Представим, что частица, находящаяся на прямой, движется по этой прямой под влиянием случайных толчков, происходящих в моменты

. Частица может находиться в точках с целочисленными координатами: ; в точках и находятся отражающие стенки. Каждый толчок перемещает частицу вправо с вероятностью и влево с вероятностью , если только частица не находится у стенки. Если же частица находится у стенки, то любой толчок переводит ее на единицу внутрь промежутка между стенками. Здесь мы видим, что этот пример блуждания частицы представляет собой типичную цепь Маркова.

Таким образом, события называют состояниями системы, а испытания – изменениями ее состояний.

Дадим теперь определение цепи Маркова, используя новую терминологию.

Цепью Маркова с дискретным временем называют цепь, изменение состояний которой происходит в определенные фиксированные моменты времени.

Цепью Маркова с непрерывным временем называют цепь, изменение состояний которой происходит в любые случайные возможные моменты времени.

§2. Однородная цепь Маркова. Переходные вероятности. Матрица перехода

Определение. Однородной называют цепь Маркова, если условная вероятность

(переход из состояния в состоянии ) не зависит от номера испытания. Поэтому вместо пишут просто .

Пример 1. Случайное блуждание. Пусть на прямой

в точке с целочисленной координатой находится материальная частица. В определенные моменты времени частица испытывает толчки. Под действием толчка частица с вероятностью смещается на единицу вправо и с вероятностью – на единицу влево. Ясно, что положение (координата) частицы после толчка зависит от того, где находилась частица после непосредственно предшествующего толчка, и не зависит от того, как она двигалась под действием остальных предшествующих толчков.

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

Регулярные цепи Маркова. При описании поведения систем марковскими процессами интересно знать, любое ли состояние может быть достигнуто в процессе функционирования системы. Если рассматривать матрицу переходных вероятностей, то она показывает вероятности перехода из одних состояний в другие. Следовательно, если какая-то степень матрицы переходных вероятностей имеет нулевые элементы, то переход в эти состояния на соответствующем шаге становится невозможным.

Цепь Маркова называется регулярной , если все состояния цепи могут быть достигнуты из любого другого . Если цепь регулярная, то в любой момент времени мы можем оказаться в любом состоянии независимо от начального состояния. Однородная марковская цепь называется регулярной , если любая степень ее матрицы вероятностей перехода П не содержит нулевых элементов. Как известно, матрица, удовлетворяющая этому условию, называется положительной .

В процессе функционирования система сервиса принимает на я-м шаге то или иное состояние с безусловной вероятностью

В некоторых случаях эти вероятности не изменяются для каждого состояния от шага к шагу, т.е.

Однородная цепь Маркова, для которой вероятности состояния одинаковы, т.е. не зависят от п, называется стационарной. В противном случае цепь называется нестационарной. Вероятность состояний называется стационарной вероятностью состояний.

Отметим, что обратная цепь...,5 ,S„,S n l ,... стационарной марковской цепи...,5 j ,S n ,S х ,... также является стационарной цепью Маркова . Стационарная цепь Маркова обратима, если и только если существует набор положительных чисел p(j), сумма которых равна 1, удовлетворяющих условиям баланса

для всех состояний.

Для однородной стационарной цепи справедлива формула

которая показывает, что на каждом шаге вероятности состояний стационарной цепи Маркова не изменяются и перемножение на матрицу переходных вероятностей не дает никакого эффекта. Как видно, вектор в (12.32) является собственным (неподвижным) вектором матрицы П 5 , принадлежащим характеристическому числу А,=1. Матрица П 5 будет положительной.

Часто на первых шагах система ведет себя как нестационарная, а после некоторого числа шагов приобретает свойства стационарности. Стационарный режим работы системы называют установившимся режимом, а нестационарный - переходным режимом.

Для цепи Маркова с конечным числом состояний при выполнении условия n rk {п) > 0, г, к = 1, К, начиная с некоторого п существуют предельные (финальные или стационарные) вероятности состояний

Следовательно,

Условие: , означает, что П является матрицей

вероятностей перехода регулярной цепи. В таком случае матрицы П" сходятся к некоторой матрице П,:

где величины , называются предельными, или финаль

ными, переходными вероятностями. Отсюда

В то же время

Объединяя два последних уравнения, получаем (12.32).

Если в качестве вектора начальных вероятностей Р т (О)для однородной цепи Маркова выбрать собственный вектор Р/ стохастической матрицы, то цепь Маркова стационарная начиная с момента t 0 .

Строки П у образуют одинаковый вероятностный вектор Р/, компоненты которого положительны. Матрица П у также является стохастической:

Так как строки П у одинаковы, то при умножении слева на любой вероятностный вектор получается, согласно (12.7), строка матрицы. Следовательно, финальные вероятности не зависят от начального состояния.

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

Предельные переходные вероятности существуют только у правильных однородных цепей Маркова.

Характеристическое число стохастической матрицы всегда лежит в круге | А|

Если матрица П 5 существует, то желательно вычислить ее без нахождения степени матрицы П" и ее предела lim П" = П°°.

п -*? оо

Для правильной матрицы существует матрица П, которую можно вычислить по формуле :

где С(А) = (А1- л) -1 ср(А) - приведенная присоединенная матрица; ср(А) - минимальный многочлен правильной матрицы; ср"(Х) - производная многочлена.

Для регулярной матрицы ф(А) = Д(А) и С(Х) = В(А). Следовательно,

где - присоединенная матрица; А(Х) - характеристический многочлен регулярной матрицы.

Рассмотрим регулярную цепь Маркова с двумя состояниями с матрицей переходных вероятностей (12.28). Вычисленные характеристические числа матрицы (12.29) различны. Существует только одно характеристическое число, равное 1, и оно является простым (не кратным) корнем характеристического уравнения (12.29). Для вычисления финальных вероятностей используем ранее найденную присоединенную матрицу (12.30). Для характеристического корня Xj = 1

Производная по X уравнения (12.29) откуда

Согласно (12.34),

Строки полученной матрицы одинаковы и должны быть равны финальным вероятностям состояний. При умножении слева этой матрицы на любой вероятностный вектор (сумма элементов вероятностного вектора равна 1) получим строку матрицы.

Для рассмотренного ранее численного примера нахождения вероятности заказа клиентом в каждом месяце

Матрица финальных вероятностей вычисляется по (12.35) как

Подставляя численные значения а = 0,3, a (3 = 0,4, получаем Следовательно, финальная вероятность заказа Финальная вероятность незаказа

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

Эргодические цепи Маркова. Марковские цепи, для которых существуют финальные вероятности, называются эргодическими. Если марковская цепь эргодическая, то из каждого ее состояния можно попасть в любое другое. Регулярная цепь всегда эргодическая, т.е. она не содержит невозвратных состояний и имеет единственное эргодическое множество состояний. Система, описываемая эрго- дической цепью Маркова, называется статистически устойчивой.

Если цепь Маркова эргодическая и стационарные вероятности состояний существуют, то необходимо их вычислить. Перед этим были приведены способы определения стационарных вероятностей путем вычисления Игл П" = П°° и П°°.

п-> ОС

Однако можно вычислить эти вероятности и без нахождения стационарной матрицы переходных вероятностей.

Финальные вероятности р к, к = 1,К, являются решением системы уравнений

В матричной записи (12.36) имеет вид

Так как уравнения (12.36) и (12.37) вероятностные, они должны удовлетворять условию нормировки

или в матричной записи

Система (12.38) - линейно зависимая матрица П размером пх п является сингулярной и имеет ранг (п - 1). Поэтому для нахождения К неизвестных финальных вероятностей необходимо заменить одно из уравнений системы (12.36) на уравнение (12.38) .

Уравнение (12.37) может быть представлено в виде

Следовательно, для нахождения решения необходимо решить систему линейных уравнений типа

При решении необходимо использовать условие нормировки (12.39), поэтому один из столбцов матрицы В надо заменить на единичный вектор 1, в результате чего получится матрица С. Если заменяется последний столбец матрицы, система (12.40) преобразуется в систему

где

Рассмотрим систему с двумя состояниями. Согласно (12.36), Заменим последнее уравнение системы на условие нормировки:

В матричной записи (12.41) элементы уравнения будут равны:

Если существует обратная матрица С -1 , то решение можно найти в виде

Для рассматриваемого примера обратная матрица существует: поэтому

Так как п п = 1-7т 12 , п 21 = 1-тг 22 , найденное решение можно также записать как

что соответствует полученным ранее решениям.

Покажем, что если в качестве вектора начальных состояний выбрать вектор стационарных состояний, то процесс сразу же на 1-м шаге перейдет в стационарное состояние.

Создаем генератор текста на основе цепей Маркова: теория и практика

Эта статья дает общее представление о том, как генерировать тексты при помощи моделирования марковских процессов. В частности, мы познакомимся с цепями Маркова, а в качестве практики реализуем небольшой генератор текста на Python.

Для начала выпишем нужные, но пока не очень понятные нам определения со страницы в Википедии , чтобы хотя бы примерно представлять, с чем мы имеем дело:

Марковский процесс t t

Марковская цепь

Что все это значит? Давайте разбираться.

Основы

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

Это предложение и есть корпус , то есть база, на основе которой в дальнейшем будет генерироваться текст. Оно состоит из восьми слов, но при этом уникальных слов только пять - это звенья (мы ведь говорим о марковской цепи ). Для наглядности окрасим каждое звено в свой цвет:

И выпишем количество появлений каждого из звеньев в тексте:

На картинке выше видно, что слово «fish» появляется в тексте в 4 раза чаще, чем каждое из других слов («One», «two», «red», «blue» ). То есть вероятность встретить в нашем корпусе слово «fish» в 4 раза выше, чем вероятность встретить каждое другое слово из приведенных на рисунке. Говоря на языке математики, мы можем определить закон распределения случайной величины и вычислить, с какой вероятностью одно из слов появится в тексте после текущего. Вероятность считается так: нужно разделить число появлений нужного нам слова в корпусе на общее число всех слов в нем. Для слова «fish» эта вероятность - 50%, так как оно появляется 4 раза в предложении из 8 слов. Для каждого из остальных звеньев эта вероятность равна 12,5% (1/8).

Графически представить распределение случайных величин можно с помощью гистограммы . В данном случае, наглядно видна частота появления каждого из звеньев в предложении:

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

Суть определения

Теперь добавим к нашему тексту элементы, которые всегда подразумеваются, но не озвучиваются в повседневной речи - начало и конец предложения:

Любое предложение содержит эти невидимые «начало» и «конец», добавим их в качестве звеньев к нашему распределению:

Вернемся к определению, данному в начале статьи:

Марковский процесс - случайный процесс, эволюция которого после любого заданного значения временного параметра t не зависит от эволюции, предшествовавшей t , при условии, что значение процесса в этот момент фиксировано.

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

Так что же это значит? Грубо говоря, мы моделируем процесс, в котором состояние системы в следующий момент времени зависит только от её состояния в текущий момент, и никак не зависит от всех предыдущих состояний .

Представьте, что перед вами окно , которое отображает только текущее состояние системы (в нашем случае, это одно слово), и вам нужно определить, каким будет следующее слово, основываясь только на данных, представленных в этом окне. В нашем корпусе слова следуют одно за другим по такой схеме:

Таким образом, формируются пары слов (даже у конца предложения есть своя пара - пустое значение):

Сгруппируем эти пары по первому слову. Мы увидим, что у каждого слова есть свой набор звеньев, которые в контексте нашего предложения могут за ним следовать:

Представим эту информацию другим способом - каждому звену поставим в соответствие массив из всех слов, которые могут появиться в тексте после этого звена:

Разберем подробнее. Мы видим, что у каждого звена есть слова, которые могут стоять после него в предложении. Если бы мы показали схему выше кому-то еще, этот человек с некоторой вероятностью мог бы реконструировать наше начальное предложение, то есть корпус.

Пример. Начнем со слова «Start» . Далее выбираем слово «One» , так как по нашей схеме это единственное слово, которое может следовать за началом предложения. За словом «One» тоже может следовать только одно слово - «fish» . Теперь новое предложение в промежуточном варианте выглядит как «One fish» . Дальше ситуация усложняется - за «fish» могут с равной вероятностью в 25% идти слова «two», «red», «blue» и конец предложения «End» . Если мы предположим, что следующее слово - «two» , реконструкция продолжится. Но мы можем выбрать и звено «End» . В таком случае на основе нашей схемы будет случайно сгенерировано предложение, сильно отличающееся от корпуса - «One fish» .

Мы только что смоделировали марковский процесс - определили каждое следующее слово только на основании знаний о текущем. Давайте для полного усвоения материала построим диаграммы, отображающие зависимости между элементами внутри нашего корпуса. Овалы представляют собой звенья. Стрелки ведут к потенциальным звеньям, которые могут идти за словом в овале. Около каждой стрелки - вероятность, с которой следующее звено появится после текущего:

Отлично! Мы усвоили необходимую информацию, чтобы двигаться дальше и разбирать более сложные модели.

Расширяем словарную базу

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

Возьмем еще четыре цитаты того же автора (также на английском, нам это не помешает):

«Today you are you. That is truer than true. There is no one alive who is you-er than you.»

«You have brains in your head. You have feet in your shoes. You can steer yourself any direction you choose. You’re on your own.»

«The more that you read, the more things you will know. The more that you learn, the more places you’ll go.»

«Think left and think right and think low and think high. Oh, the thinks you can think up if only you try.»

Сложность корпуса увеличилась, но в нашем случае это только плюс - теперь генератор текста сможет выдавать более осмысленные предложения. Дело в том, что в любом языке есть слова, которые встречаются в речи чаще, чем другие (например, предлог «в» мы используем гораздо чаще, чем слово «криогенный»). Чем больше слов в нашем корпусе (а значит, и зависимостей между ними), тем больше у генератора информации о том, какое слово вероятнее всего должно появиться в тексте после текущего.

Проще всего это объясняется с точки зрения программы. Мы знаем, что для каждого звена существует набор слов, которые могут за ним следовать. А также, каждое слово характеризуется числом его появлений в тексте. Нам нужно каким-то образом зафиксировать всю эту информацию в одном месте; для этой цели лучше всего подойдет словарь, хранящий пары «(ключ, значение)». В ключе словаря будет записано текущее состояние системы, то есть одно из звеньев корпуса (например, «the» на картинке ниже); а в значении словаря будет храниться еще один словарь. Во вложенном словаре ключами будут слова, которые могут идти в тексте после текущего звена корпуса («thinks» и «more» могут идти в тексте после «the» ), а значениями - число появлений этих слов в тексте после нашего звена (слово «thinks» появляется в тексте после слова «the» 1 раз, слово «more» после слова «the» - 4 раза):

Перечитайте абзац выше несколько раз, чтобы точно разобраться. Обратите внимание, что вложенный словарь в данном случае - это та же гистограмма, он помогает нам отслеживать звенья и частоту их появления в тексте относительно других слов. Надо заметить, что даже такая словарная база очень мала для надлежащей генерации текстов на естественном языке - она должна содержать более 20 000 слов, а лучше более 100 000. А еще лучше - более 500 000. Но давайте рассмотрим ту словарную базу, которая получилась у нас.

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

More:

То есть если текущим словом является слово «more» , после него могут с равной вероятностью в 25% идти слова «things» и «places» , и с вероятностью 50% - слово «that» . Но вероятности могут быть и все равны между собой:

Think:

Работа с окнами

До настоящего момента мы с вами рассматривали только окна размером в одно слово. Можно увеличить размер окна, чтобы генератор текста выдавал более «выверенные» предложения. Это значит, что чем больше окно, тем меньше будет отклонений от корпуса при генерации. Увеличение размера окна соответствует переходу цепи Маркова к более высокому порядку. Ранее мы строили цепь первого порядка, для окна из двух слов получится цепь второго порядка, из трех - третьего, и так далее.

Окно - это те данные в текущем состоянии системы, которые используются для принятия решений. Если мы совместим большое окно и маленький набор данных, то, скорее всего, каждый раз будем получать одно и то же предложение. Давайте возьмем словарную базу из нашего первого примера и расширим окно до размера 2:

Расширение привело к тому, что у каждого окна теперь только один вариант следующего состояния системы - что бы мы ни делали, мы всегда будем получать одно и то же предложение, идентичное нашему корпусу. Поэтому, чтобы экспериментировать с окнами, и чтобы генератор текста возвращал уникальный контент, запаситесь словарной базой от 500 000 слов.

Реализация на Python

Структура данных Dictogram

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

Import random class 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): # Обновляем распределение элементами из имеющегося # итерируемого набора данных for item in iterable: if item in self: self += 1 self.tokens += 1 else: self = 1 self.types += 1 self.tokens += 1 def count(self, item): # Возвращаем значение счетчика элемента, или 0 if item in 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() # вывести "случайный индекс:", random_int for i in range(0, self.types): index += self] # вывести индекс if(index > random_int): # вывести list_of_keys[i] return list_of_keys[i]

В конструктор структуре Dictogram можно передать любой объект, по которому можно итерироваться. Элементами этого объекта будут слова для инициализации Dictogram, например, все слова из какой-нибудь книги. В данном случае мы ведем подсчет элементов, чтобы для обращения к какому-либо из них не нужно было пробегать каждый раз по всему набору данных.

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

Структура цепи Маркова

from histograms import Dictogram def make_markov_model(data): markov_model = dict() for i in range(0, len(data)-1): if data[i] in markov_model: # Просто присоединяем к уже существующему распределению markov_model].update(]) else: markov_model] = Dictogram(]) return markov_model

В реализации выше у нас есть словарь, который хранит окна в качестве ключа в паре «(ключ, значение)» и распределения в качестве значений в этой паре.

Структура цепи Маркова N-го порядка

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

Очень похоже на цепь Маркова первого порядка, но в данном случае мы храним кортеж в качестве ключа в паре «(ключ, значение)» в словаре. Мы используем его вместо списка, так как кортеж защищен от любых изменений, а для нас это важно - ведь ключи в словаре меняться не должны.

Парсинг модели

Отлично, мы реализовали словарь. Но как теперь совершить генерацию контента, основываясь на текущем состоянии и шаге к следующему состоянию? Пройдемся по нашей модели:

From histograms import Dictogram import random from collections import deque import re def generate_random_start(model): # Чтобы сгенерировать любое начальное слово, раскомментируйте строку: # return random.choice(model.keys()) # Чтобы сгенерировать "правильное" начальное слово, используйте код ниже: # Правильные начальные слова - это те, что являлись началом предложений в корпусе if "END" in model: seed_word = "END" while seed_word == "END": seed_word = model["END"].return_weighted_random_word() return seed_word return random.choice(model.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) sentence = sentence.capitalize() return " ".join(sentence) + "." return sentence

Что дальше?

Попробуйте придумать, где вы сами можете использовать генератор текста на основе марковских цепей. Только не забывайте, что самое главное – это то, как вы парсите модель и какие особые ограничения устанавливаете на генерацию. Автор этой статьи, например, при создании генератора твитов использовал большое окно, ограничил генерируемый контент до 140 символов и использовал для начала предложений только «правильные» слова, то есть те, которые являлись началом предложений в корпусе.

Марковский случайный процесс с дискретными состояниями и дискретным временем называют марковской цепью . Для такого процесса моменты t 1 , t 2 , когда система S может менять свое состояние, рассматривают как последовательные шаги процесса, а в качестве аргумента, от которого зависит процесс, выступает не время t , а номер шага 1, 2, k , Случайный процесс в этом случае характеризуется последовательностью состояний S(0) , S(1) , S(2) , S(k) , где S(0) - начальное состояние системы (перед первым шагом); S(1) - состояние системы после первого шага; S(k) - состояние системы после k -го шага...

Событие {S(k) = S i }, состоящее в том, что сразу после k -го шага система находится в состоянии S i (i = 1, 2,), является случайным событием. Последовательность состояний S(0) , S(1) , S(k) , можно рассматривать как последовательность случайных событий. Такая случайная последовательность событий называется марковской цепью , если для каждого шага вероятность перехода из любого состояния S i в любое S j не зависит от того, когда и как система пришла в состояние S i . Начальное состояние S(0) может быть заданным заранее или случайным.

Вероятностями состояний цепи Маркова называются вероятности P i (k) того, что после k -го шага (и до (k + 1)-го) система S будет находиться в состоянии S i (i = 1, 2, n ). Очевидно, для любою k .

Начальным распределением вероятностей Марковской цепи называется распределение вероятностей состояний в начале процесса:

P 1 (0), P 2 (0), P i (0), P n (0).

В частном случае, если начальное состояние системы S в точности известно S(0) = S i , то начальная вероятность Р i (0) = 1, а все остальные равны нулю.

Вероятностью перехода (переходной вероятностью) на k -м шаге из состояния S i в состояние S j называется условная вероятность того, что система S после k -го шага окажется в состоянии S j при условии, что непосредственно перед этим (после k - 1 шага) она находилась в состоянии S i .

Поскольку система может пребывать в одном из n состояний, то для каждого момента времени t необходимо задать n 2 вероятностей перехода P ij , которые удобно представить в виде следующей матрицы:

где Р ij - вероятность перехода за один шаг из состояния S i в состояние S j ;

Р ii - вероятность задержки системы в состоянии S i .

Такая матрица называется переходной или матрицей переходных вероятностей.

Если переходные вероятности не зависят от номера шага (от времени), а зависят только от того, из какого состояния в какое осуществляется переход, то соответствующая цепь маркова называется однородной .

Переходные вероятности однородной Марковской цепи Р ij образуют квадратную матрицу размера n m .

Отметим некоторые ее особенности:

1. Каждая строка характеризует выбранное состояние системы, а ее элементы представляют собой вероятности всех возможных переходов за один шаг из выбранного (из i -го) состояния, в том числе и переход в самое себя.

2. Элементы столбцов показывают вероятности всех возможных переходов системы за один шаг в заданное (j -е) состояние (иначе говоря, строка характеризует вероятность перехода системы из состояния, столбец - в состояние).

3. Сумма вероятностей каждой строки равна единице, так как переходы образуют полную группу несовместных событий:

4. По главной диагонали матрицы переходных вероятностей стоят вероятности Р ii того, что система не выйдет из состояния S i , а останется в нем.

Если для однородной Марковской цепи заданы начальное распределение вероятностей и матрица переходных вероятностей , то вероятности состояний системы P i (k) (i, j = 1, 2, n ) определяются по рекуррентной формуле:

Пример 1. Рассмотрим процесс функционирования системы - автомобиль. Пусть автомобиль (система) в течение одной смены (суток) может находиться в одном из двух состояний: исправном (S 1 ) и неисправном (S 2 ). Граф состояний системы представлен на рис. 3.2.

Рис. 3.2.Граф состояний автомобиля

В результате проведения массовых наблюдений за работой автомобиля составлена следующая матрица вероятностей перехода:

где P 11 = 0,8 - вероятность того, что автомобиль останется в исправном состоянии;

P 12 = 0,2 - вероятность перехода автомобиля из состояния «исправен» в состояние «неисправен»;

P 21 = 0,9 - вероятность перехода автомобиля из состояния «неисправен» в состояние «исправен»;

P 22 = 0,1 - вероятность того, что автомобиль останется в состоянии «неисправен».

Вектор начальных вероятностей состояний автомобиля задан , т.е. Р 1 (0) = 0 и Р 2 (0) =1.

Требуется определить вероятности состояний автомобиля через трое суток.

Используя матрицу переходных вероятностей и формулу (3.1), определим вероятности состояний P i (k) после первого шага (после первых суток):

P 1 (1) = P 1 (0)×P 11 + P 2 (0)×P 21 = 0?0,8 + 1?0,9 = 0,9;

P 2 (1) = P 1 (0)×P 12 + P 2 (0)×P 22 = 0?0,2 + 1?0,1 = 0,2.

Вероятности состояний после второго шага (после вторых суток) таковы:

P 1 (2) = P 1 (1)×P 11 + P 2 (1)×P 21 = 0,9×0,8 + 0,1×0,9 = 0,81;

= 0,9×0,2 + 0,1×0,1 = 0,19.

Вероятности состояний после третьего шага (после третьих суток) равны:

P 1 (3) = P 1 (2)×P 11 + P 2 (2)×P 21 = 0,81×0,8 + 0,19×0,9 = 0,819;

= 0,81×0,2 + 0,19×0,1 = 0,181.

Таким образом, после третьих суток автомобиль будет находиться в исправном состоянии с вероятностью 0,819 и в состоянии «неисправен» с вероятностью 0,181.

Пример 2. В процессе эксплуатации ЭВМ может рассматриваться как физическая система S , которая в результате проверки может оказаться в одном из следующих состояний: S 1 - ЭВМ полностью исправна; S 2 - ЭВМ имеет неисправности в оперативной памяти, при которых она может решать задачи; S 3 - ЭВМ имеет существенные неисправности и может решать ограниченный класс задач; S 4 - ЭВМ полностью вышла из строя.

В начальный момент времени ЭВМ полностью исправна (состояние S 1 ). Проверка ЭВМ производится в фиксированные моменты времени t 1 , t 2 , t 3 . Процесс, протекающий в системе S , может рассматриваться как однородная марковская цепь с тремя шагами (первая, вторая, третья проверки ЭВМ). Матрица переходных вероятностей имеет вид

Определить вероятности состояний ЭВМ после трех проверок.

Решение . Граф состояний имеет вид, показанный на рис. 3.3. Против каждой стрелки проставлена соответствующая вероятность перехода. Начальные вероятности состояний P 1 (0) = 1, P 2 (0) = P 3 (0) = P 4 (0) = 0.

Рис. 3.3. Граф состояний ЭВМ

По формуле (3.1), учитывая в сумме вероятностей только те состояния, из которых возможен непосредственный переход в данное состояние, находим:

P 1 (1) = P 1 (0)×P 11 = 1×0,3 = 0,3;

P 2 (1) = P 1 (0)×P 12 = 1×0,4 = 0,4;

P 3 (1) = P 1 (0)×P 13 = 1×0,1 = 0,1;

P 4 (1) = P 1 (0)×P 14 = 1×0,2 = 0,2;

P 1 (2) = P 1 (1)×P 11 = 0,3×0,3 = 0,09;

P 2 (2) = P 1 (1)×P 12 + P 2 (1)×P 22 = 0,3×0,4 + 0,4×0,2 = 0,20;

P 3 (2) = P 1 (1)×P 13 + P 2 (1)×P 23 + P 3 (1)×P 33 = 0,27;

P 4 (2) = P 1 (1)×P 14 + P 2 (1)×P 24 + P 3 (1)×P 34 + P 4 (1)×P 44 = 0,44;

P 1 (3) = P 1 (2)×P 11 = 0,09×0,3 = 0,027;

P 2 (3) = P 1 (2)×P 12 + P 2 (2)×P 22 = 0,09×0,4 + 0,20×0,2 = 0,076;

P 3 (3) = P 1 (2)×P 13 + P 2 (2)×P 23 + P 3 (2)×P 33 = 0,217;

P 4 (3) = P 1 (2)×P 14 + P 2 (2)×P 24 + P 3 (2)×P 34 + P 4 (2)×P 44 = 0,680.

Итак, вероятности состояний ЭВМ после трех проверок следующие: P 1 (3) = 0,027; P 2 (3) = 0,076; P 3 (3) = 0,217; P 4 (3) = 0,680.

Задача 1. По некоторой цели ведется стрельба четырьмя выстрелами в моменты времени t 1 , t 2 , t 3 , t 4 .

Возможные состояния системы: S 1 - цель невредима; S 2 - цель незначительно повреждена; S 3 - цель получила значительные повреждения; S 4 - цель полностью поражена. В начальный момент времени цель находится в состоянии S 1 . Определить вероятности состояний цели после четырех выстрелов если матрица переходных вероятностей имеет вид.