Использование энтропии в определении авторства текста

В продолжение первой части. 


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

Для начала повторю теоретический бэкграунд такого эксперимента.

В теории информации энтропия — это мера неопределённости информации. Она вычисляется по формуле (1)

   (1)

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

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

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

Для эксперимента были выбраны несколько сказок Ганса-Христиана Андерсена. Из начального списка более 25 произведений были умышленно вычеркнуты малые по объему (менее 10 кБайт), поскольку небольшой объем обрабатываемого текста, скорее всего, приведет к нерепрезентативности - банально не наберется необходимое для исследования количество слов. Список использованных в работе сказок с номерами, под которыми они будут встречаться далее, представлен ниже:

0 - Тень 

1 - Аисты
2 - Бабушка
3 - Девочка со спичками
4 - Девочка, которая наступила на хлеб

5 - Дикие лебеди

6 - Дочь болотного царя

7 - Дюймовочка

8 - Красные башмаки

9 - Огниво

10 - Оле-Лукойе

11 - Русалочка

12 - Снежная королева

13 - Сон

Для каждой из них были проведены следующие преобразования:

1. были вырезаны знаки препинания,
2. все слова были приведены в начальную форму.

Затем для каждой из них были проведены необходимые подсчеты. Например, рассмотрим первую их них - Тень. Сначала для нее было подсчитано (рис.1):

• количество слов в тексте
• количество разных (уникальных) слов тексте
• значение энтропии
• список наиболее часто встречающихся слов

Рисунок 1. Расчет энтропии первого порядка.

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

Рисунок 2. Расчет энтропии второго порядка.

Аналогичная процедура была проведена со всеми доступными текстами, так что скопилась полная база, содержащая:

• энтропии первого порядка для текстов
• списки наиболее часто встречающихся слов текстов
• энтропии второго порядка для текстов

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

Энтропия первого порядка для рассматриваемого отрывка равна 8,92974. Теперь посчитаем значения энтропий второго порядка для всех означенных ранее слов каждого из текстов. В случае, если совпадения будут явны, можно сделать вывод, что данный текст является частью первого. В ходе проверки было выявлено, что только для одного набора наиболее часто встречающихся слов все слова повторились в данном отрывке с заметной регулярностью, однако значения энтропии для отрывка оказались несколько меньшими (примерно на 15% меньше при том, что размер отрывка составил 50% размера сверяемого изначального текста). Это можно объяснить тем, что существует зависимость энтропии от размера выборки. К слову, это действительно оказался текст, из которого был взят изучаемый отрывок. 

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

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

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

Глава	Энтропия
Вступление+Заключение	8,19287
Первая глава	8,84601
Вторая глава	8,90423

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

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

Приложение. Описание работы утилиты.

В основе работы написанной утилиты лежит формула энтропии Шеннона. Для подсчета численного значения энтропии высчитываются вероятностные оценки появления слов в тексте. Такие оценки строятся в зависимости от частот, с которыми слова встречаются в тексте. Для подсчета текст проходит предварительную обработку:

1. из текста удаляются все знаки препинания,
2. все слова приводятся в начальную форму.

Утилита позволяет выбрать сразу несколько текстов к обработке, все слова из которых переносятся в отдельные файлы в папке с программой. Так же для всех файлов генерируется .bat файл, при запуске которого происходит создание новых файлов, в которых вместо каждого слова будут записаны начальные формы этого слова. Этот .bat файл в ходе своей работы вызывает специальную утилиту mystem.exe, написанную в компании Яндекс. Описание программы с официального сайта:"Программа mystem производит морфологический анализ текста на русском языке. Для слов, отсутствующих в словаре, порождаются гипотезы." В сгенерированном .bat файле вызов этой программы прописан с такими параметрами, что та находит начальную форму для встреченных слов и выписывает их в файл.

Затем, с созданным таким образом новым файлом уже можно работать. Происходит это следующим образом:

1. Для каждой начальной формы, имеющейся в файле, утилита подсчитывает количество повторений
2. Затем, на базу этого количества, утилита рассчитывает вероятности,
3. которые потом подставляются в формулу энтропии.

Параллельно ведется учет общего количества слов в тексте и количества уникальных слов в тексте.

Утилита позволяет вывести на экран 15 наиболее часто встречаемых слов в тексте.

Для подсчета энтропии второго порядка утилита требует ввода списка слов, для которых ее необходимо считать. Затем она:

1. Для каждого слова строит список слов, которые следуют за ним в различных местах текста,
2. Для такого списка слов повторяется описанный выше алгоритм.

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

Так же в этот момент генерируется таблица с отчетом по заданным словам в формате excel.