О Лингвоанализаторе 3-e

Д.В. Хмелёв

Содержание

1  Введение

Что означают эти результаты и каким образом они получены? Настоящая заметка попытается ответить на оба вопроса.

В июне 2001 года был сделан ``снимок'' состояния библиотеки Максима Мошкова (http://www.lib.ru/), из которого были извлечены 3233 произведения 353 писателей. Писатели были разбиты на несколько тематических списков. Кроме того, несколько списков (так называемые ``Устойчивая подвыборка 1'', ..., ``Устойчивая подвыборка 5'' и их дополнения) были построены с учётом совместной различимости авторов. Точнее, с помощью специальной программы были отобраны наборы авторов, наиболее отличающихся по своим стилевым характеристикам в совокупности. О построении подвыборок читайте раздел 3.

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

Когда пользователь посмотрит на результаты, у него немедленно может возникнуть вопрос: а какое, собственно, отношение имеет полученный анализ к самому произведению?

Лингвоанализатор 3-e относится к так называемым системам извлечения информации (information retrieval systems) из слабо структурированных данных. Лингвоанализатор 3-e основан на методике определения авторства текста, которая разработана недавно (всего четыре года назад: в 1998 году) [1]. Подобная методика с большой степенью достоверности действительно определяет истинного автора по тексту (пользователь может перепроверить это самостоятельно!). Методика не анализирует сюжет, фабулу и т.п. художественные достоинства. Лингвоанализатор 3-e производит свои заключения на основе некоторой оценки относительной энтропии текстов. В оценке относительной энтропии учитываются такие формальные характеристики текстов, как

а) число служебных слов (предлогов, союзов и частиц),

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

в) сложность используемых грамматических конструкций,

г) собственно словарь, используемый автором.

Более подробно принципы устройства Лингвоанализатора 3-e описаны в следующем разделе.

2  Об относительной энтропии

Наивный подход к такой задаче, которого и придерживались ранние исследователи [2,3], состоит в попытке определить некоторое расстояние d(X,Y) между любыми двумя текстами X и Y, а затем просто найти такое i, для которого d(Z,A_i) - минимально. Напомним читателю, что всякое расстояние (а в нашем случае - и расстояние между последовательностями) должно удовлетворять трём аксиомам:

1) d(X,Y) = 0 тогда и только тогда, когда X = Y,

2) 0 < d(X,Y) для несовпадающих X и Y,

3) для всех X₁, X₂, X₃ выполнено либо d(X₁,X₃) < d(X₁,X₂)+d(X₂,X₃), либо d(X₁,X₃) = d(X₁,X₂)+d(X₂,X₃)(это условие называется неравенством треугольника).

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

По мнению автора, такой подход неудачен в силу того, что неестественен. В самом деле, для определения авторства неравенство треугольника, заключённое в аксиоме 3), излишне и не используется при нахождении минимального из расстояний d(Z,A₁), ..., d(Z,A_k).

По-видимому, правильный подход к решению задачи (как показано в [1]) заключается в построении некоторой оценки относительной энтропии H(B|A) текста B относительно текста A. Затем последовательность Z соотносится последовательности A_i на которой относительная энтропия H(Z|A_i) - минимальна.

Относительная энтропия является обобщением понятия энтропии, которое вводится как к теории вероятностей, так и к теории информации [4,5] (не говоря уже и о физике). Такая широта приводит к терминологической путанице, поскольку энтропию называют по разному. В принципе, существует два подхода к определению энтропии, приводящие к разным вычислительным алгоритмам для её оценки.

Чисто информационное определение энтропии через сложность ввёл А.Н. Колмогоров [5]: сложностью последовательности букв A является длина (в двоичном алфавите) минимальной программы, которая выводит A, а энтропия A - это её сложность, делённая на длину A в битах. Определение очень математическое в том смысле, что оно абсолютно верно и абсолютно бесполезно: колмогоровская сложность является величиной невычислимой, то есть, нельзя написать программу, которая позволяла бы её вычислять для любой последовательности A. Тем не менее, существуют программы, которые, по сути, пытаются вычислить колмогоровскую сложность текста: программы сжатия текста. Действительно, текст, сжатый программой zip, представляет собой некоторую ``программу'', которая интерпретируется программой unzip таким образом, что на выходе получается исходный текст.

Поэтому с помощью программы zip можно определить оценку на относительную энтропию H(A|B) текста B относительно текста A. Для этого сожмём текст A и измерим длину получившегося архива C(A), а затем сожмём текст A+B, получившийся присоединением текста A к тексту B, и измерим длину C(A+B) получившегося архива (Внимание! Очень важно при получении A+B именно присоединять текст B к тексту A: тексты A и B должны храниться в одном файле, друг за другом!). Оценка на относительную сложность будет даваться формулой

C(B | A) = C(A+B) - C(A).

Теперь, чтобы определить правильного автора текста Z среди авторов текстов A₁, ..., A_k надо выбрать такой индекс i, что

C(Z | Ai) < C(Z | Aj) для всех j, не совпадающих с i.

Очевидно, вместо архиватора zip можно использовать gzip или rar и пр. В приложении Д. Хмелёва к статье [6] показано, что лучшие среди архиваторов результаты показывает rar. В том же приложении этот способ разобран более детально.

Описанный метод действительно работает в рамках задачи определения авторства. Но он крайне неэффективен. Дело в том, что сжатие текста - операция требующая очень большого времени. Работа Лингвоанализатора 3-e основана на другом способе оценке энтропии: вероятностном.

Традиционное вероятностное определение энтропии основано на рассмотрении цепи Маркова n-го порядка на последовательности A, исходящей из эргодического источника [4]. Для достаточно длинных A хорошая оценка энтропии даётся некоторой функцией H_n(A), которая зависит только от частот употреблений последовательной n+1 буквы в тексте [4]. Аналогично можно определить функцию относительной энтропии H_n(B|A). В [1] был получен неожиданный результат: в рамках задачи определения авторства достаточно ограничится функцией H₁(B|A), то есть, авторство текста эффективно определяется лишь информацией о частотах пар последовательно идущих букв в тексте!

Именно на этой идее [1] и основан основной алгоритм Лингвоанализатора 3-e. Вначале вычисляются энтропии H(Z|A₁), ..., H(Z|A_k) текста Z относительно текстов A₁, ..., A_k всех авторов количеством 353 из базы данных. Затем для каждой подвыборки (списка) выбирается тройка наиболее похожих. Из полученной тройки отсекаются с помощью аналогичных энтропийных соображений авторы, всё-таки, не имеющие отношения к тексту. Эмпирическая проверка показывает что ошибка первого рода составляет порядка 10-15%, то есть, с вероятностью 10-15% текст будет классифицирован неправильно. Вероятность ошибки второго рода меньше 5%.

3  Об организации подвыборок писателей

Имеется два типа выборок: тематические и устойчивые. Тематические выборки сформированы на основе какой-нибудь конкретной директории в библиотеке Максима Мошкова (http://www.lib.ru/)

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

Все авторы: http://zhurnal.lib.ru/list/default.html
Выборка из всех авторов, тоже является выборкой. Составлена на основе библиотеки Максима Мошкова по состоянию на июнь 2001 года.

История: http://zhurnal.lib.ru/list/history.html
Список составлен по разделу ``История'':
http://www.lib.ru/HISTORY/

Классика: http://zhurnal.lib.ru/list/litra.html
Список составлен по разделу ``Русская классика'':
http://www.lib.ru/LITRA/

Проза: http://zhurnal.lib.ru/list/proza.html
Список составлен по разделу ``Современная русская проза'':
http://www.lib.ru/PROZA/

Русский детектив: http://zhurnal.lib.ru/list/russ_detectiw.html
Список составлен по разделу ``Русский детектив и боевик'':
http://www.lib.ru/RUSS_DETEKTIW/

Современная проза: http://zhurnal.lib.ru/list/newproza.html
Список составлен по разделу ``Русская проза 1990-х - 2000-х годов'':
http://www.lib.ru/NEWPROZA/

Христианство: http://zhurnal.lib.ru/list/history.html
Список составлен по разделу ``Христианство и библейская литература и публицистика'':
http://www.lib.ru/HRISTIAN/

Устойчивая подвыборка 1: http://zhurnal.lib.ru/list/stable1.html
Эта подвыборка генерировалась так, чтобы в неё попало максимальное число произведений и был максимален процент верных определений авторства.

Дополнение устойчивой подвыборки 1: http://zhurnal.lib.ru/list/stable1inverse.html
Эта выборка содержит тех авторов из списка ``Все авторы'' http://zhurnal.lib.ru/list/default.html, которые не нашли в ``Устойчивую подвыборку 1''.

Устойчивая подвыборка 2: http://zhurnal.lib.ru/list/stable2.html
Минимизировался средний ранг автора на собственном произведении при максимизации числа авторов.

Дополнение устойчивой подвыборки 2: http://zhurnal.lib.ru/list/stable2inverse.html
Эта выборка содержит тех авторов из списка ``Все авторы'' http://zhurnal.lib.ru/list/default.html, которые не нашли в ``Устойчивую подвыборку 2''.

Устойчивая подвыборка 3: http://zhurnal.lib.ru/list/stable3.html
Модификация критерия, использованного для поиска устойчивой подвыборки 2 с другими весами.

Дополнение устойчивой подвыборки 3: http://zhurnal.lib.ru/list/stable3inverse.html
Эта выборка содержит тех авторов из списка ``Все авторы'' http://zhurnal.lib.ru/list/default.html, которые не нашли в ``Устойчивую подвыборку 3''.

Устойчивая подвыборка 4: http://zhurnal.lib.ru/list/stable4.html
Минимизировался средний ранг и единица, делённая на число произведений.

Дополнение устойчивой подвыборки 4: http://zhurnal.lib.ru/list/stable4inverse.html
Эта выборка содержит тех авторов из списка ``Все авторы'' http://zhurnal.lib.ru/list/default.html, которые не нашли в ``Устойчивую подвыборку 4''.

Устойчивая подвыборка 5: http://zhurnal.lib.ru/list/stable5.html
Максимальная подвыборка со 100% результатом перекрёстной проверки.

Дополнение устойчивой подвыборки 5: http://zhurnal.lib.ru/list/stable5inverse.html
Эта выборка содержит тех авторов из списка ``Все авторы'' http://zhurnal.lib.ru/list/default.html, которые не нашли в ``Устойчивую подвыборку 5''.

4  Дополнительная информация

СПИСОК ЛИТЕРАТУРЫ

[1]

Хмелёв Д.В. Распознавание автора текста с использованием цепей А.А. Маркова. Вестник МГУ, сер.9: филология, N2, 2000, с.115-126

[2]

От Нестора до Фонвизина. Новые методы определения авторства. М.: Издат. группа ``Прогресс'', 1994.

[3]

Holmes D.I. The Evolution of Stylometry in Humanities Scholarship//Literary and Linguistic Computing. 1998. V. 13. N03. P.111-117.

[4]

Яглом А.М., Яглом И.М. Вероятность и информация. М.: Наука, 1960.

[5]

Колмогоров А.Н. Три подхода к определению понятия <<количество информации>>//Пробл. передачи информ. 1965. Т.1. N⁰ 1, С.3-11.

[6]

Кукушкина О.В., Поликарпов А.А., Хмелёв Д.В. Определение авторства текста с использованием буквенной и грамматической информации//Проблемы передачи информации, 2001, т.37, вып.2, с.96-108. Translated in ``Problems of Information Transmission'', pp. 172-184.

Содержание