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

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

 

В статье посредством формального анализа текста решается задача определения авторства текста. Новый метод основывается на формальной математической модели последовательности букв текста как реализации цепи А.А. Маркова. Оказывается, частоты употребления пар букв очень хорошо характеризуют автора. Последнее утверждение проверено в объемном статистическом эксперименте на произведениях 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).

Каждый фрагмент g_i,j  B^* можно отобразить в A^* посредством некоторой функции F: B^* A^*. Пусть, например, F превращает все заглавные буквы в маленькие, склеивает перенесенные слова, выбрасывает все знаки пунктуации и излишние знаки пробела, оставляя их по одному между словами, а также вставляет один пробел в начале и один пробел в конце фрагмента в случае отсутствия таковых.

Кроме того, мы будем рассматривать функцию G, которая устроена так же, как и функция F, с тем дополнением, что все слова, которые в фрагменте g_i,j начинались с заглавной буквы, отбрасываются. Например, если

y = "Кроме того, мы будем рассматривать функцию G,", то

F(y) = " кроме того мы будем рассматривать функцию ", а

G(y) = " того мы будем рассматривать функцию ".

Теперь предположим, что некий фрагмент текста y  B^* принадлежит одному из n авторов, и нам неизвестно, кому именно. Наша задача: определить автора фрагмента y. Мы можем найти автора, применяя оценку (2.1) к последовательности x = F(y) или к x = G(y). Следовательно, мы получаем два способа определения автора:

1) истинный автор - t(F(y)),

2) истинный автор - t(G(y)).

Важно отметить, что оценки t(F(y)) и t(G(y)) вычисляются на основе информации о частотах употребления пар букв. Поскольку между словами вставлены пробелы, оценки t(F(y)) и t(G(y)) никак не зависят от порядка самих слов. По-видимому, t(F(y)) и t(G(y)) характеризуют последовательности морфем в словоформах русского языка, но, конечно, совсем не учитывают синтаксисическую информацию (на основе последней пытались устанавливать авторство в).

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