Смекни!
smekni.com

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

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

Кроме того, мы будем рассматривать функцию G, которая устроена так же, как и функция F, с тем дополнением, что все слова, которые в фрагменте gi,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). Статистический эксперимент показывает, что авторы определяются очень уверенно.

Анализ частот употреблений букв (схема Бернулли)

Схемой Бернулли в теории вероятностей называется последовательность независимых одинаково распределенных случайных величин. Формально мы можем предположить, что последовательности fi,j и x являются реализациями последовательности независимых одинаково распределенных случайных величин, принимающих значения в A, а x распределен как величины класса , где  - неизвестный параметр. Тогда оценка (2.1) принимает вид

e(x) = argmini Gi(x), (2.2)

где

Gi(x) =  k k ln((k×hi)/(hi,k×)),

где сумма вычисляется по таким k, что k > 0, а  = kk, hi = k hi,k и. Грубо говоря, производя оценку (x) мы производим частотный анализ текста. Статистический эксперимент показывает, что оценка e(x) существенно хуже оценки t(x).

Модельный эксперимент

Сначала проведем проверку нашей методики на следующем примере. Рассмотрим следующие произведения К. Булычева, А. Волкова, Н.В. Гоголя и В. Набокова.

Мы хотим проверить эффективность оценки t(F(y)). Предлагается следующий способ: выбрать каждого автора i (i = 0,1,2,3) по одному контрольному произведению y i, оценить матрицы i по другим произведениям fi,j, а затем найти t(F(yi)). Если оценка работает хорошо, то для каждого автора i должно быть t(F(yi)) = i.

0) К. Булычев: Умение кидать мяч ( y0); Белое платье золушки (g0,1); Великий дух и беглецы (g0,2); Глубокоуважаемый микроб (g0,3); Закон для дракона (g0,4); Любимец [Спонсоры] (g0,5); Марсианское зелье (g0,6); Миниатюры (g0,7); "Можно попросить Нину?" (g0,8); На днях землетрясение в Лигоне (g0,9); Перевал (g0,10); Показания Оли Н. (g0,11); Поминальник XX века (g0,12); Раскопки курганов в долине Репеделкинок (g0,13); Тринадцать лет пути (g0,14); Смерть этажом ниже (g0,15);

1) А. Волков: Семь подземных королей ( y1); Волшебник изумрудного города (g1,1); Урфин Джюс и его деревянные солдаты (g1,2); Огненный бог Марранов (g1,3); Гениальный пень (g1,4); На войне, как на войне (g1,5); О чем молчали газеты... (g1,6); Преступление и наказание (g1,7); Эпилог (g1,8); Желтый Туман (g1,9); Тайна заброшенного замка (g1,10);

2) Н.В. Гоголь: Рассказы и повести (y2, названия повестей: "Повесть о том, как поссорился Иван Иванович с Иваном Никифоровичем", "Старосветские помещики", "Вий", "Записки сумасшедшего"); Ревизор (g2,1); Тарас Бульба (g2,2); Вечера на хуторе близ Диканьки (g2,3);

3) В. Набоков: Другие берега (y3); Король, дама, валет (g3,1); Лолита (g3,2); Машенька (g3,3); Рассказы (g3,4); Незавершенный роман (g3,5).

Например, у А. Волкова контрольным произведением является y1, т.е. "Семь подземных королей" Все остальные произведения используются для вычисления i. Результаты вычислений представляются следующей таблицей.

Таблица 1

N Автор c1 c2 c3 c4
0 К. Булычев 0 15 2345689 75161
1 А. Волков 0 8 1733165 233418
2 Н.В. Гоголь 0 3 723812 243767
3 В. Набоков 0 5 1658626 367179

Столбец c2 содержит общее число файлов, в которых хранятся произведения автора. Заметим, что число файлов может не совпадать с числом произведений по двум причинам: во-первых, несколько произведений одного автора могут находится в одном файле (здесь такое произошло с А. Волковым - три повести "Желтый Туман", "Тайна заброшенного замка" и "Огненный бог Марранов" были в одном файле); во-вторых, одно большое произведение может разбиваться на несколько частей (последнее необходимо учитывать при изучении таблицы 2).

В колонке c3 содержится суммарное число символов (букв и пробелов) в F(gi,j): c3 = j F(gi,j). В колонке c4 содержится число символов в F(yi), т.е. c4 = F( yi). Например, для К. Булычева общий объем текстов jF(g0,j) составляет 2'345'689. Общий объем F(y1), т.е. число символов A в повести "Умение кидать мяч", выбранной в качестве контрольного текста, равно 75'161.

В столбце c1 в строке j находится ранг числа Lj(F( yj)) среди чисел {Li(F( yj))  i = 0,1,2,3}. Под рангом мы подразумеваем номер Lj(F(yj)) среди чисел {Li(F( yj))  i = 0,1,2,3}, расположенных в порядке невозрастания. Например, если j = 1 и Li расположились в порядке L0  L3  L2  L1, то рангом L1 будет 3. А если j = 0 и Li расположились в том же порядке L0  L3  L2  L1, то рангом L0 будет 0. Ранг Lj(F(yj)), среди чисел {Li(F( yj)  i = 0,1,2,3} совпадает с рангом Lj(F(yj))/F(yj), среди чисел {Li(F(yj))/F(yj) | i = 0,1,2,3}. Расположим в строках j = 0,1,2,3 следующей матрицы по 4 числа Li(F( yj))/F( yj), i = 0,1,2,3:

В каждой строке найдем ранги чисел Li:

3
2
1
2
0
3
1
2
3
0
1
2
1
3
0
ö÷÷÷÷ø .

Искомые числа столбца c1 стоят на диагонали. Вспоминая формулу (2.1), мы заключаем, что t(F( yj)) = j тогда и только тогда, когда ранг Lj(F(yj))/F( yj) среди чисел {Li(F( yj))/F( yj) i = 0,1,2,3} просто равен 0. Следовательно, если в какой-либо строке в столбце c1 таблицы 1 стоит 0, то авторство контрольного текста определено правильно. Из таблицы 1 мы видим, что у всех писателей авторство определено верно.

Прежде, чем обсудить этот результат, поясним, почему столбец c1 задан таким образом. Дело в том, что если авторство определено неверно (т.е., оказалось t(F(yj))  j), то нас может интересовать, насколько мы были близки к правильному ответу. Если ранг Lj(F(yj))/F( yj) среди чисел {Li(F( yj))/F( yj) i = 0,1,2,3} равен 1, то мы ошиблись всего на одного писателя. Такой случай существенно лучше случая ранга Lj(F( yj))/F( yj) равного 3, поскольку тут правильный писатель оказывается в списке претендентов на его собственное произведение последним, что свидетельствует о большей ошибке.

Кроме того, матрица R сама по себе допускает интересные интерпретации. Например, из первой строки мы видим, что контрольное произведение К. Булычева "Умение кидать мяч" после самого К. Булычева больше походит на В. Набокова, затем на Н. Гоголя, и в последнюю очередь на произведения А. Волкова. Из последующих двух строк можно сделать вывод, что контрольные произведения А. Волкова и Н. Гоголя также в первую очередь походят на произведения В. Набокова. Может быть, это вызвано тем, что сам Набоков исторически находится между Н. Гоголем и парой писателей: А. Волковым и К. Булычевым? Если эта гипотеза верна, то наша метод чувствителен к исторической эпохе, в которую создано произведение. Некоторое подтверждение тому мы находим в последней строке матрицы R: контрольное произведение В. Набокова похоже в первую очередь на пару А. Волкова и К. Булычева, и лишь затем - на Н. Гоголя. Если бы пара А. Волкова и К. Булычева разбивалась Н. Гоголем. то мы имели бы аргумент против нашей гипотезы. Впрочем, возможны другие интерпретации матрицы R, и автор нисколько не настаивает на выше приведенной.