Схема Бернулли. Цепи Маркова (стр. 7 из 11)

У₁=ФФ*ФФб У₂= ФФ*Фаб У₃ = ФФ*ааб У₄ = Фа*Фаб У₅= Фа*ааб У₆=

аа*ааю

Найдите граф и матрицу перехода.

Решение.

Рассмотрим, какое потомство и с какой вероятностью может быть у особей разного пола, если они выбираются из E₂.

Пусть B_i= {i-й потомок}, i= 1, 2 и B₁,B₂ - разного пола, тогда варианты потомков и их вероятности можно найти по следующему графу:

Рис. 8

Получаем, что

Аналогично, находим и вероятности других переходов:

Тогда искомый граф перехода выглядит следующим образом:

Рис. 9

а матрица перехода –

Пример 11. Матрица вероятностей перехода цепи Маркова имеет вид:

Распределение по состояниям в момент времени t= 0 определяется вектором

. Найти распределения по состояниям в момент t= 2.

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

Рис. 10

По этому графу находим распределение по состояниям в момент t= 2:

P(E1)= (0,6*(0,2)²+ 0,6*0,3*0,5+0,6*0,5*0,6)+(0,1*0,5*0,2+0,1*0,2*0,5

+0,1*0,3*0,6) +(0,3*0,6*0,2+(0,3)²*0,6)+(0,3*0,1*0,5)=0,437;

P(E2)= (0,1*(0,2)²+0,1*0,5*0,3+0,1*0,3*0,1)+0,6*0,3*0,2+0,6*0,2*0,3

+0,6*0,5*0,1)+(0,3*0,1* 0,2+(0,3)²*0,1+0,3*0,6*0,3)=0,193;

P(E3)= 0,37.

Пример 12. Доказать, что P⁽ⁿ⁾= Pⁿдля двух состояний цепи Маркова.

Решение. Пусть цепь Маркова с двумя состояниями E₁ и E₂ задана своей матрицей перехода P:

Докажем утверждение методом математической индукции.

Пусть n= 2. Тогда

Вероятности перехода за два шага удобно находить по графу перехода:

Рис. 11

Следовательно, P⁽²⁾= P², и первый шаг метода математической индукции выполняется. Предположим далее, что при проверяемое утверждение истинно, т.е. P^(k)= P^k, тогда матрица перехода за k+1 шаг P^(k+1)= P^(k)*P = P^k*P = P, что и требовалось доказать.

Глава 3. Применение цепей Маркова

3.1 Определение авторства текста

В статье посредством формального анализа текста решается задача определения авторства текста. Новый метод основывается на формальной математической модели последовательности букв текста как реализации цепи А.А. Маркова. Оказывается, частоты употребления пар букв очень хорошо характеризуют автора. Последнее утверждение проверено в объемном статистическом эксперименте на произведениях 82 писателей.

Введение опыта

В последние десятилетия наметилась тенденция поиска и выявления характерных структур авторского языка путем применения формально-количественных, статистических методов. Первые пробные шаги на этом пути предпринял еще в начале XIX века Н.А. Морозов. Интересно, что тогда же известный математик А.А. Марков выступил с критикой Н.А. Морозова. А.А. Марков критиковал Н.А. Морозова за то, что он не произвел тщательной статистической проверки утверждений относительно устойчивости некоторых элементов авторского стиля (например, частицы "не"). Примером правильного статистического подхода А.А. Марков считал свое исследование в статье, где он изучал распределение доли гласных и согласных среди первых 20000 букв "Евгения Онегина". Отметим, что работа посвящена первому применению "испытаний, связанных в цепь", получивших впоследствии название цепей А.А. Маркова. Работа удивительным образом предоставляет историческую основу методу определения авторства, изложенному в настоящей статье.

Истории вопроса определения авторства текста посвящена первая глава книги. Несмотря на то, что среди перечисленных в присутствуют весьма изощренные методики определения структуры авторского стиля, все они страдают, на взгляд автора настоящей статьи, одним общим недостатком. Ни одна из этих методик не проходила проверку на большом числе писателей. Дело в том, что многие из методик имеют трудно формализуемый этап сведения естественно-литературного произведения к предлагаемой математической модели. Например, для некоторых из них необходима классификация всех слов текста по грамматическим классам, что требует участия человека. При таком подходе большой вычислительный эксперимент с целью проверки методики на большом числе авторов практически неосуществим. Поэтому все такие методики пытались использовать на небольшом числе авторов.

Другого подхода придерживались авторы статьи. Они исследовали несколько простых параметров авторского стиля и на огромном числе произведений писателей XVIII-XX веков статистически доказали, что доля всех служебных слов в длинном прозаическом произведении является т.н. авторским инвариантом.

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

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

Такой метод оказывается удивительно точным для естественно-языковых текстов. Мы обсуждаем здесь особенности применения метода и сравниваем его с методом определения автора на основе частот употребления каждой из букв в отдельности. Проверка метода проводилась на произведениях 82 писателей, среди которых есть русские писатели как XIX, так и XX века.

Математические основания

Марковская модель

Обозначим через A некоторое множество букв. Через A^k обозначим множество слов длины k над алфавитом A. Пусть A^* = _{k > 0}A_k. Обозначим длину слова f  A^* через f.

Задачу определения автора текста можно сформулировать следующим образом. Пусть заданы n классов C_i, где i = 0, ..., n1. В каждом классе C_i находятся последовательности f_i,j  A^*, где j = 1, ..., m_i, т.е. C_i = { f_i,j  j = 1,,m_i}. Наша задача состоит в том, чтобы отнести x  A^* к одному из классов C_i.

Предположим, что последовательности букв f_i,j являются реализациями цепи Маркова с переходной матрицей ⁱ. Построим оценку Pⁱ. Обозначим через h_i,j,kl число переходов букв k l в фрагменте f_i,j, положим h_i,kl = _jh_i,j,kl, а h_i,k = _lh_i,kl. Положим Pⁱ_kl = h_i,kl/h_i,k. Возможно, некоторые Pⁱ_kl равны нулю. Обозначим через Z_i множество таких упорядоченных пар (k,l), что Pⁱ_kl > 0.

Предположим, что x также является реализацией цепи Маркова с матрицей переходных вероятностей P^ , где  неизвестный параметр, который принимает одно из значений 1, ..., n.

Обозначим через _k,l число переходов k l в x. Пусть также _k = _l _k,l. Обозначим через

L_i(x) =  (k,l) _k,l×ln(_k,l /(Pⁱ_kl×_k)),

где сумма берется по парам (k,l)  Z_i. Грубо говоря, L_i(x) равно минус логарифму вероятности x при условии, что x - реализация цепи Маркова с матрицей переходных вероятностей Pⁱ. Назовем t(x) оценкой максимального правдоподобия для неизвестного параметра 

t(x) = argmin_{i = 0,...,n1} L_i(x). (2.1)

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

Схема эксперимента

Возьмем A = {маленькие буквы кириллицы}{символ пробела}. Предположим, что у нас имеются в распоряжении достаточно длинные фрагменты произведений n авторов на русском языке. Обозначим j-тый фрагмент i-того автора через g_i,j. Можно считать, что фрагмент g_i,j является последовательностью символов некоторого расширенного алфавита B, который включает, например, знаки пунктуации, большие буквы, латинские буквы и т.д. (на персональном компьютере B обычно совпадает с расширенным множеством символов ASCII).