Классификация и разметка>>[Введение|Проект БВИ]

Классификация и разметка текстов с использованием методов сжатия данных. Краткое введение\footnote{которое получилось не совсем кратким}

Классификация и разметка текстов с использованием методов сжатия данных. Краткое введение1

Д.В.Хмелёв

Содержание

1  Введение
2  Классификация
    2.1  О классификации мышей
    2.2  О классификации текстов: обзор других методов
    2.3  Энтропийная классификация (с помощью сжатия)
    2.4  Открытые вопросы
3  Автоматическая разметка
    3.1  Краткое описание
    3.2  Открытые вопросы и задачи

1  Введение

Современные методы позволяют вплотную приблизиться к теоретической верхней границе на степень сжатия текстов. Естественная верхняя граница для текстов определяется энтропией и замечательные эксперименты Шеннона [1], некоторых наших математиков под руководством Колмогорова [2] (см. также [3]) показывают, что энтропия естественно-языковых текстов находитcя между 1-2 битами на букву как для русского, так и для английского текстов, что, в принципе, и достигается современными программами, особенно на основе метода PPM.

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

Почему решение этих задач является актуальным? Классификация текстов по их содержанию является ежедневной необходимостью любого человека, пользующегося электронной почтой: до сих пор не существует адекватной системы борьбы со спамом. Автоматическая классификация текстов на новостных лентах (по областям), автоматический тематический классификатор в сетевых библиотеках сильно облегчил бы жизнь людям, поддерживающим эти сервисы. Количество файлов, хранящихся на типичном компьютере, также стремительно увеличивается и у этих громадных коллекций также скоро возникнет необходимость в самоорганизации. Даже этот узкоспециализированный сервер, посвящённый сжатию, требует обширной работы по классификации имеющегося материала. Любой большой современный проект, связанный со взаимодействием большого количества людей (вроде Русской Фантастики http://www.rusf.ru, Самиздата http://zhurnal.lib.ru), приводит к тому, что объёмы данных становятся настолько необъятными, что просто не поддаются анализу и классификации вручную. Есть мнение, что методы сжатия и специалисты в них, имеющие большой опыт в анализе данных общей природы, могут поспособствовать выявлению различных ошибок и несовместимостей в этих гигантских текстовых базах данных.

Автоматическая разметка текста является, пожалуй, ещё более актуальной, чем классификаторы. Несмотря на то, что имеется большое количество способов разметки информации (HTML, LATEX, nroff, DOC-файлы разных версий MS Word, PDF, разметка файлов электронной почты, внутренняя разметка большинства источников новостей, библиотек и т.п.), на практике единственным устойчивым к различным преобразованиям способом хранения текста является простейший текстовый формат, в котором строки из символов ASCII (или его расширения) разделяются специальными символами (перевода строки). В большинстве сетевых библиотек (например, в библиотеке Мошкова http://www.lib.ru) текст хранится именно в таком формате, что приводит к большому количеству проблем при дальнейшей обработке этого материала. Например, не так легко написать программу, обеспечивающую форматирование текста полиграфического (или близкого к полиграфическому) качества (например, в LATEX), пригодное для его дальнейшего вывода на печать. Конечно, нетребовательные люди могут ограничиться распечаткой текста, выровненного по правой границе в 70 символов, но такие тексты занимают на печати значительно больше места, да и к комфортному чтению они практически непригодны (эти обстоятельства в значительной мере обуславливают отсутствие возражений издателей к размещению книг в сети ;). Написание такой программы является одной из целей настоящего проекта. Понятно, что совсем избежать человеческого труда не удастся, однако мы можем достичь его значительной экономии следующим образом. Предположим, что кто-нибудь разметил текст метками вроде «начало параграфа», «стихотворение», «эпиграф» и т.п. Тогда тексты того же типа скорее всего следует размечать аналогичным образом. В разделе 3 мы обсудим, как разметку «по аналогии» можно строить с использованием принципа минимизации длины результирующего сжатого текста. Для определения же типа текста можно воспользоваться классификатором текста, описанном в следующем разделе 2.

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

Необходимое замечание: это введение следует рассматривать как предварительное. Автор заранее просит прощения за пропущенные ссылки и ждёт значимых дополнений от читателей.

2  Классификация

2.1  О классификации мышей

Под классификацией каких-либо объектов имеется ввиду сопоставление каждому объекту метки или признака (или набора меток или признаков). Например, мыши бывают белыми, серыми, чёрными, синими или зелёными (мы говорим, конечно, о компьютерных мышах и имеем ввиду только чисто белых и т.д. мышей без смешанных цветов;), всякая мышь - это объект, цвет мыши - это её признак или метка. Ясно, что метки могут быть взаимоисключающими (вроде цвета мыши), или дополняющими, как например, метки «оптическая», «бесхвостая», «с колёсиком», которые могут появляться в любых комбинациях. Знание о том, что какие-либо метки несовместны, может быть нетривиальным в использовании и поэтому обычно решают задачи классификации только двух видов: многокатегориальные и многоальтернативные. В рамках многокатегориальных задач считается, что все признаки являются дополняющими друг друга, то есть, возможна «синяя белая зелёная оптическая бесхвостая» мышь. В многоальтернативных задачах все метки являются взаимоисключающими, то есть, если мышь «синяя», то она не может быть «зелёной». Важным случаем многоальтернативной задачи является задача бинарной классификации, когда имеется ровно два взаимоисключающих признака, например, признак и его дополнение, вроде пары признаков «оптическая» и «неоптическая».

Всякая многокатегориальная задача сводится к нескольким задачам бинарной классификации, когда для каждого признака определяется его наличие или отсутствие. Например, при классификации мышей по типу позиционирования и типу соединения с компьютером, решается две бинарных задачи: «оптическая/неоптическая» и «хвостатая/безхвостая». В принципе, многоальтернативную задачу тоже можно свести к задачам бинарной классификации: например, при классификации цвета можно определять для каждого цвета его наличие или отсутствие. Однако, такой подход может привести к ошибочным комбинациям типа «белая зелёная синяя», а потому такое сведение чаще всего неэффективно. В большинстве случаев классификацию по нескольким признакам можно свести к нескольким задачам бинарной и многоальтернативной классификации. Например, для классификации мышей по цвету, типу позиционирования и типу соединения с компьютером, мы используем многоальтернативный классификатор по цвету «белая/серая/чёрная/синяя/зелёная» и бинарные классификаторы по признакам «оптическая/неоптическая» и «хвостатая/безхвостая». Во избежание терминологической путаницы отметим, что классификатором мы называем какую-нибудь реализацию алгоритма, умеющую производить классификацию по какому-нибудь описанию объекта (просто иногда классификатором называют набор названий классов объектов; впрочем если кто помнит биологию, имеется классификатор растений, который представляет собой набор карточек, позволяющий по внешним характеристикам растения определить его вид, в точности по нашему определению).

Существует много разных методов классификации, причём имеется довольно чёткое деление методов на два класса по наличию или отсутствию частичной разметки исследуемых данных. В классификации с предварительным обучением некоторая доля текстов считается заранее размеченной (например, вручную) интересующей нас информацией. Например, имеется каталог «Белые мыши» с несколькими фотографиями белых мышей, каталог «Синие мыши» с несколькими фотографиями синих мышей и т.д. А задача состоит в том, чтобы правильно разложить по этим каталогам мышей из каталога «Неизвестные мыши».. Классификация без обучения наличия таких данных не предполагает. То есть, имеется только каталог «Неизвестные мыши», которых надо как-то сгруппировать, например, по близости цвета. Смысл заключается в том, чтобы человек, взглянув впоследствии на получившиеся группы, мог легко расставить метки: «Белые мыши», «Зелёные мыши» и т.д.

Ясно, что решение задач без обучения существенно сложнее классификации с предварительным обучением. Очень часто задача классификации без обучения плохо поставлена, то есть группировка данных производится на основании некоторого априорного критерия, который к данным в действительности никакого отношения не имеет. Довольно часто классификация без обучения является NP-полной задачей. Иногда, однако, данные сгруппировать как-то надо, и поэтому применяются эвристики (интересный пример применения классификации без обучения к сжатию текстов - полуадаптивный алгоритм Хаффмана, применяемый в Bzip2 для сжатия MTF-рангов [4,Глава 5, с.207]). Чаще же всего выход из создавшейся ситуации состоит в сведении задачи к классификации с обучением, поскольку усилия на подготовку качественной обучающей выборки несопостовимо малы по сравнению с трудностью решения NP-полной задачи, и умственными усилиями по изготовлению хорошей эвристики. Если не оговорено противное, в дальнейшем мы будем под классификацией иметь ввиду именно классификацию с предварительным обучением, а заинтересованный классификацией без обучения читатель отсылается к диплому Н.Тапера [5].

2.2  О классификации текстов: обзор других методов

Если мы хотим поручить классификацию объектов машине, то обычно первым шагом является описание имеющихся объектов путём выделения и количественной характеризиции легко измеримых признаков (например, получение цифровой фотографии мыши при современном уровне развития техники труда не представляет). Лёгкость получения цифровой фотографии мышки не означает, что легко написать программу, которая будет помещать файлы с белыми мышами в каталог с белыми мышами, и файлы с зелёными мышами в каталог с зелёными мышами: ведь с точки зрения машины фотография представляет собой просто гигантский прямоугольный массив чисел, характеризующих цвет и его интенсивность в каждом пикселе (элементе изображения). Заключение о том, что эти числа задают белую мышь (считая, что компьютеру известно, что на фотографии изображена именно мышь) является нетривиальной задачей искуственного интеллекта (ИИ), при том, что обычный человек легко с этой задачей справляется.

Упражнение. Определите цвет мыши на следующем рисунке.

Упражнение*. Придумайте какой-нибудь метод установления цвета мыши исходя из шестнадцатиричного дампа данных, задающих этот рисунок (дамп целиком приведён в catoncomputerwithmouse.txt): 

0000000 4947 3846 6139 00fa 0109 00d5 ff00 ffff
0000020 f7f7 f7ff f7f7 efef e1ef e1e1 caf3 d7e9
...............................................

Следует понимать, что с точки зрения машины любой текст - это такой же бессмысленный шестнадцатеричный дамп (впрочем, скорее двоичный, но из экономии места мы приводим его шестнадцатеричное представление): 

0000000 ccf3 c4c5 c5d5 20d4 cfd0 c9ce c1cd d8d4
0000020 202c d4de 20cf 20d3 cfd4 cbde 20c9 d2da
0000040 cec5 d1c9 cd20 dbc1 cec9 20d9 c0cc cfc2
0000060 20ca c5d4 d3cb 20d4 2d2d 202d d4dc 20cf
0000100 c1d4 cfcb 20ca c5d6 c20a d3c5 cdd3 d3d9
0000120 c5cc cece cad9 db20 d3c5 ced4 c4c1 c1c3
0000140 c5d4 c9d2 cede cad9 c420 cdc1 3ad0 000a

То есть, текст тоже характеризуется набором чисел, и числа эти целые. Как правило, они изменяются от 0 до 255, и каждому числу соответствует какая-нибудь буква или символ.2

Поскольку текст - это тоже некоторый объект, задаваемый числами, то задачи классификации делятся на те же два типа: многокатегориальный и многоальтернативный. В дальнейшем мы будем использовать слово документ как синоним слова текст. В случае многокатегориальной классификации каждому документу (тексту) назначается несколько меток из заранее определённого набора (вроде, «о корпорациях», «о деньгах», «о жизни» и т.д.), а задача классификации - определить эти метки автоматически с максимальной точностью. Для решения таких задач обычно строятся бинарные классификаторы, по одному на каждую возможную метку. Бинарный классификатор пытается определить, обладает ли поданный на вход документ данной меткой или нет.

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

Простейший подход к классификации текстов: по ключевым словам. Скажем, наличие слова «аранк» тесно связано с романом С.Лукьяненко «Спектр». Было бы опрометчиво, однако, делать вывод о том, что текст со словом «аранк» есть роман С.Лукьяненко, поскольку, например, текст, который вы сейчас читаете, тоже содержит это слово, так же как и многочисленные рецензии. Хорошо, тогда можно посчитать, сколько раз это слово встретилось в тексте, и большое количество употреблений слова аранк, скажем, больше ста, уж точно характеризует роман С.Лукьяненко. Но и это не гарантирует точного определения авторства, скажем, фрагмента из книги. Тем не менее, мы находимся на верном пути, поскольку качество классификатора, считающего количество «аранков» в тексте, выше, чем просто у классификатора, который ориентируется лишь на то, встретился «аранк» или нет. С другой стороны, почему мы концентрируемся на слове «аранк»? Ведь существует немало других хороших слов. И действительно, качество классификации существенно увеличивается, если мы посчитем частоты всех слов в тексте. Правда, тогда наш текст будет характеризоваться очень-очень длинным массивом чисел. Но сначала уточним задачу.

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

Коэффициенты, задающие нормаль гиперплоскости, как раз и характеризуют вклад (т.е.) важность слова в различении классов.

Теперь то же на пальцах. Вообразим, что мы пользуемься только двумя словами: «думать» и «стрелять». Тогда все документы представляются точкой (x,y) на двумерной плоскости, где x - количество употреблений слова «думать», а y - количество употреблений «стрелять». Тогда, скажем, в детективах «думать» будет превалировать над «стрелять» (x > y), а в «стрелялках» «стрелять» будут больше, чем «думать» (x < y). А чтобы их различать, следует, например, провести прямую x=y (прямая - это и есть гиперплоскость в двумерном пространстве). Часто существуют и другие прямые, разделяющие множество детективов от множества «стрелялок». Выбор разделяющей прямой неоднозначен, но существует некое «наилучшее положение». Его можно подыскать с помощью решения задачи квадратичной оптимизации. Имеются готовые программы, которые это делают. Такой программе надо на вход подать вектора из обучающей выборки (с разделением на присутствие и отсутствие в классе, которое традиционно задаётся 1 для присутствия и -1 для отуствия). Тогда программа строит разделяющую гиперплоскость, которую записывает в файл. После этого ей можно подать на вход вектора, полученные из документов, подлежащих классификации - и вперёд! Сама программа есть по адресу http://svmlight.joachims.org/.

Хотя разделение векторов с помощью плоскости представляется довольно наивным, методы классификации с помощью SVM значительно превосходят многочисленных конкурентов: кластерную классификацию (когда документ соотносится к ближайшему множеству; в зависимости от определения расстояния до множества имееся большое количество вариантов этого метода - средневзвешенный, k ближайших соседей и т.п), а также наивную Байесовскую классификацию (которая предполагает, что частоты слов в тексте являются независимыми случайными величинами).

Методы классификации с помощью SVM достигают хорошей точности за счёт извлечения и настройки на «особенности» текста, за которые они обычно принимают слова. Текст, однако, не исчерпывается словами: в нём обычно имеются знаки препинания, переводы строк и прочие форматирующие команды. Кроме того, деление на слова довольно-таки условно и не однозначно. Например, считать ли числа словами? Во избежание таких вопросов было бы идеально рассмотреть в качестве «особенностей» текста все его возможные подстроки. Проблема заключается в том, что количество особенностей возрастает быстрее, чем линейно, что делает применимость SVM проблематичной. Имеются различные трюки, позволяющие бороться с ростом размерности пространства, но их описание выходит за рамки настоящего обзора.

Прежде чем мы перейдём к описанию энтропийного подхода к классификации, ещё несколько комментариев об SVM. Методы классификации с помощью SVM играют в методах теории извлечения информации (Information Retrival) приблизительно ту же роль, что методы PPM играют в методах сжатия. В принципе, почти любой метод классификации (включая рассмотренные в следующем подпункте энтропийные методы) можно свести к построению разделяющей гиперплоскости с помощью SVM, точно также, как всегда можно настроить PPM, чтобы он давал лучшие или сравнимые результаты по сравнению с другими методами сжатия. Проблема заключается в том, что SVM должна решать задачи квадратичного выпуклого программирования, что требует больших расходов времени и неизбежного использования арифметики с плавающей запятой. Сведение же задач к SVM может привести к увеличению размерности задачи (пространства признаков). Конечно, методы оптимизации всё время улучшаются, но до сих пор SVM способна решать задачи на десятки тысяч характеристик. Если учесть, что разных слов в русском языке больше ста тысяч, и достаточно объёмная коллекция русских текстов (вроде Библиотеки Мошкова http://www.lib.ru) таких словарных объёмов достигает, то применимость SVM к классификации и обработке действительно больших объёмов текстов выглядит проблематичной (если не ограничиваться каким-нибудь подмножеством слов, что уменьшает качество классификации). Другая сложность с использованием SVM - необходимость предварительной обработки данных, что зачастую затруднено, в частности, как выделять слова в китайских текстах? Даже не говоря о китайских текстах, что делать с русскими текстами в «Fido'шной» кодировке, в которых русская Н («эн») заменена на английскую H («аш») (см. http://www.rusf.ru/books/yo/encoding.html)? Очевидно, к этим текстам необходимо применять предварительную обработку, в частности методами восстановления разметки, рассмотренным в разделе 3. Между тем на работу энтропийных методов, рассмотренных в следующем подпункте, такая замена практически не влияет (если только она была произведена во всех файлах).

2.3  Энтропийная классификация (с помощью сжатия)

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

Вкратце, суть метода состоит в том, чтобы «подклеивать» анонимный текст к текстам, характеризующим классы, и смотреть, насколько хорошо сжимается эта «добавка». Правильный исходный класс документа - это тот, на котором он жмётся лучше всего. В рамках подхода PPM правильный исходный класс документа - это тот, на чьей модели получается наилучшее сжатие.

Будем рассматривать задачу многоальтернативной классификации текста T относительно текстов, S1, ..., Sn, характеризующих n классов. Конечно, имеется много работ по адаптации SVM к решению этой задачи. Однако, весьма конкурентноспособным (и иногда побивающим SVM) является подход, основанный на применении так называемой относительной энтропии. Именно, мы определяем характеристику H(T|S), которая характеризует энтропию текста T по отношению к тексту S. Далее выбор источника текста T при наличии текстов S1, ..., Sn, представляющих n источников, должен осуществляться согласно оценке


q(T)=argminiH(T|Si).
(1)
Приемлемое значение для H(T|Si) можно получить с помощью программ сжатия текстов. Имеется совсем наивный способ, который предлагается называть «шельфовым» (off-the-shelf) алгоритмом, применимый при всяком отсутствии у вас навыков программирования. Именно, сожмите вашим любимым компрессором текст Si и измерьте длину в байтах C(Si) получившегося архива с помощью средств вашей любимой операционной системы. Теперь создайте текст SiT, склеив тексты Si и T в один файл (в системах типа ДОС с помощью команды copy /b s4.txt+text.txt s4text.txt; или в вашем любимом редакторе текстов3; можно также воспользоваться функцией Far копирования текстов с дополнением). Сожмите SiT и измерьте длину полученного сжатого текста C(SiT) в байтах. Всё! Теперь полагаем
HC(T|Si)=  1
|T|
 (C(SiT)-C(T)),
где |T| - длина текста T в байтах. Полученное число HC(T|Si) можно использовать совместно в оценке (1) вместо H(T|Si). Таким образом, для определения источника T мы вычисляем HC(T|Si), а потом определяем истинный источник T, выбирая то i, которое соответствует минимальному из чисел HC(T|Si). Насколько известно автору, первое опубликованное исследование о применимости шельфового алгоритма к классификации текстов имеется в приложении к статье [6]. Любопытно, что некоторые архиваторы, а в особенности RAR (использующий PPMd) показывают прекрасные результаты, сравнимые и даже превосходящие другие результаты других подходов в этой области.

Другой подход - непосредственное измерение энтропии текста T с использованием модели для текста S. Наиболее подходящим в этом случае является PPM, в котором моделирование текста и его статистическое кодирование разбиты на два разных этапа (см. [4]). Эксперименты [7,6] показывают, что такой подход вполне подходит для классификации, а в исследование, проведённое в работе [8] показывает, что результаты практически совпадают с результатами шельфового алгоритма с использованием RAR 3.0 (который использует PPMD для сжатия).

Третий подход - использование индекса повторяемости, впервые описанного в работе [11]. Индекс повторяемости R(T|T1,ј,Tm) текста T относительно текстов T1, ..., Tm - это нормированная на |T|(|T|+1) сумма длин всех подстрок T, повторённых где-нибудь в T1, ..., Tm:
R2(T | T1,јTm)=  2
l(l+1)
 l
е
i=1 
 Q(T[i..l] | T1,јTm),
(2)
где l=|T| - длина текста T, T[i..l] - i-тый суффикс документа T и Q(S | T1,јTm) - длина самого длинного префикса текста U, повторённого где-нибудь в T1, ..., Tm. Например, если m=2,

T=«cat sat on» и
T1=«the cat on a mat»,
T2=«the cat sat»,
то
R2(T | T1,T2)=  2
10×(10+1)
 ж
и 		(7+6+5+4+3)+(5+4+3+2+1) ц
ш 		» 0.727272
(3)
и
R(T | T1,T2)=
Ц
 
R2(T | T1,T2)
 
 » 0.852802.

Очевидно, мы можем использовать
qR(T)=argaxiR(T|Si).
(4)

Сравнение качества определения авторства при трёх разных подходах приведено в следующей таблице 1.

Таблица 1: Точность классификации (процент верного определения автора документа) на подвыборках с разной степенью повторяемости
Метод R < 0.25 R < 0.5 R < 0.75 R < 1.00 R<=1.0
R-index 82.1 86.4 87.1 87.8 89.0
SVM 80.6 83.4 83.5 84.6 85.0
Bzip 56.9 55.2 45.9 51.9 48.2
Gzip 55.7 53.5 53.9 50.1 59.4
Цепь Маркова, порядок 1 62.3 64.6 63.2 64.3 66.1
Цепь Маркова, порядок 2 60.9 64.4 61.8 64.7 64.5
Цепь Маркова, порядок 3 48.6 60.3 59.3 61.7 63.3
RAR 84.3 86.9 87.3 88.5 89.4
PPM, порядок 2 77.8 79.1 79.4 80.5 81.3
PPM, порядок 3 80.6 82.3 84.0 85.0 86.4
PPM, порядок 4 82.5 85.4 86.0 87.7 88.4
PPM, порядок 5 82.2 86.1 86.3 88.8 89.2

Эксперименты, результаты которых представлены в таблице 1, проводились на массиве новостей агенства Рейтерс (Reuters Corpus Volume 1 или RCV1). Было отобрано 50 авторов с наибольшим объёмом статей (заметим, что эти авторы отличаются от 50 с максимальным количеством статей): всего 1813 статей. Выборка случайно была разбита на 10 равных частей, одна из которых использовалась для тестирования. Процент верного определения авторства приведён в последнем столбце таблицы 1. Для исследования влияния дубликатов и плагиата на качество определения авторства были отобраны подвыборки этих статей, удовлетворяющих условию на значение индекса их повторяемости по отношению к остальному корпусу RCV1 (R < 0.25, R < 0.5, R < 0.75, R < 1.0). Результаты экспериментов для этих подвыборок приведены в других столбцах таблицы 1.

В справочных целях приведём результаты более обширного тестирования программ сжатия из [6]. В приложении Д.Хмелёва к [6] исследовались программы, представленные в таблице 2, с краткой справкой по алгоритмам, расшифровку которых читатель может найти в книге [4]. Проверка различных программ проведена на корпусе текстов, который использовался в [9,10,6]. Корпус состоял из 385 текстов 82 писателей. Общий объем текстов составляет около 128 миллионов букв. Тексты подверглись предварительной обработке. Во-первых, были склеены все слова, разделенные переносом. Далее были выкинуты все слова, начинавшиеся с прописной буквы. Оставшиеся слова помещены в том порядке, в каком они находились в исходном тексте с разделителем из символа перевода строки. У каждого из n=82 писателей было отобрано по контрольному произведению Ui. Остальные тексты были слиты в обучающие тексты Si, i=1, ..., 82. Объем каждого контрольного произведения составлял не менее 50-100 тысяч букв.

Заметим, что такая предварительная обработка позволяет сравнить результаты распознавания с марковским подходом, применённым в [9].

Таблица 2: Программы сжатия
ПрограммаАвторИспользуемые алгоритмы
1. 7zip версия 2.11Игорь Павлов арифм. кодирование, LZ + арифм. кодирование, PPM
2. arj версия 2.60 RAO Inc. LZSS + Хаффман
3. bsa версия 1.9.3 Сергей Бабичев LZ
4. bzip2 Джулиан СьюардБарроуз-Уиллер + Хаффман
5. compress Sun Inc. LZW
6. dmc Гордон В. КормакDMC
7. gzip Жан-Луи ГаилиШеннон-Фано, Хаффман
8. ha версия 0.999cГарри Хирвола Скользящее окно словаря + арифм. кодирование
9. huff1 Вильям Демас (LDS 1.1) статический Хаффман
10. lzari Харахико Окумура (LDS 1.1) LZSS+арифм. кодирование
11. lzss Харахико Окумура (LDS 1.1) LZSS
12. ppm Вильям ТеаханPPM
13. ppmd5 версия FДмитрий ШкаринPPM
14. rarw версия 2.00Евгений Рошаль вариант LZ77 + Хаффман
15. rar версия 2.70Евгений Рошаль вариант LZ77 + Хаффман
16. rk версия 1.03a Малькольм Тейлор LZ, PPMZ

Большинство из этих программ с описаниями можно получить из Индекса архиваторов http://web.act.by.net/~act/act-index.html, который поддерживает Джефф Гилхрист4. Программа compress взята из операционной системы SunOS 5.6. Программа dmc доступна по ftp http://plg.uwaterloo.ca/~ftp/dmc/. Заметим, что dmc имеет опцию максимально используемой оперативной памяти. В нашем случае использовалась опция в 100000000 байт. Пакет программ LDS 1.1 также доступен по ftp5. Программа ppm доступна с домашней страницы ее автора http://www.cs.waikato.ac.nz/~wjt/.

Результаты применения этих программ представлены в табл. 3, где в последней строке приведены данные, которые получаются при применении цепей Маркова [9] на том же материале. Вычисления, выполненные при составлении табл. 3, проводились под несколькими операционными системами на разных платформах и заняли около трех недель непрерывного счета.

Таблица 3: Точность определения авторства текста с использованием алгоритмов сжатия данных
ПрограммаРанг
01234 і 5M
7zip399323266,43
arj465272205,16
bsa449311245,30
bzip238551 3313,68
compress1211326324,37
dmc364344319,81
gzip504121244,55
ha478133205,60
huff110114425115,37
lzari1754264814,99
lzss1431136020,05
ppm22142134010,39
ppmd546662 225,96
rar58111  217,22
rarw713  2151,44
rk52931  174,20
Цепи Маркова (см. [9])69 3 2 1   7 2,35

Анализ таблиц 1 и 3 позволяет сделать любопытные предварительные выводы. Во-первых, простейший подход с использованием цепей Маркова первого порядка показывает неплохие результаты на файлах большого объёма (как представлено в таблице 3), проваливаясь по сравнению с другими методами на небольших отрывках длиной в 2-5 тысяч символов (см. таблицу 1), что в силу компактности и скорости работы позволяет рекомендовать его к использованию в демонстрационных классификаторах, вроде Лингвоанализатора на Русской Фантастике http://www.rusf.ru/books/analysis и на Самиздате http://zhurnal.lib.ru. Впрочем, точность может возрасти при применении модели PPM 1-го порядка, т.е. при комбинировании марковских цепей первого и второго порядков, при небольших дополнительных расходах. Решение вопроса полезности такого усовершенствования предоставляется читателю в качестве упражнения.

Таблица 3 также отражает заметный прогресс в моделировании текстов у архиваторов: простейшие архиваторы с небольшим словарём показывают заметно худшие результаты по сравнению с современными программами сжатия.

Тем не менее, остаются и открытые вопросы. Скажем, rarw применяющий модификацию алгоритма LZ обходит многие другие методы на файлах большого объёма (как демонстрирует таблица 3). В то же время gzip и 7zip, также применяющие некоторую модификацию LZ, значительно отстают по точности.

Дальнейшие выводы предоставляется сделать читателю самостоятельно.

2.4  Открытые вопросы

Очень многие вопросы, связанные с энтропийной классификацией, всё ещё требуют дополнительного исследования, результаты которых автор настоящего обзора с удовольствием бы узнал от других.

  1. Данные таблицы 1 показывают, что PPM превосходит остальные алгоритмы с точки зрения классификации небольших текстов. Так ли это на самом деле? Вполне возможно, что грамотная реализация LZ77 (какой она была, например в RAR 2.71, что демонстрирует таблица 3) может дать лучшее качество определения авторства, чем gzip. Преобразование Барроуза-Уилера также не стоит сбрасывать со счетов, поскольку bzip2 реализует лишь классический способ кодирования преобразованного текста, кроме того на результаты влияет блочная структура преобразования. Вполне возможно, что новые методы кодирования преобразованного текста приведут к лучшим результатам.

  2. Как использовать энтропийный подход к классификации без обучения? (некоторые начальные результаты имеются в дипломной работе [5]).

  3. Какова связь между индексом повторяемости R и относительной энтропией текстов (хотя бы на эмпирическом уровне)?

  4. Насколько велико влияние конечных буферов в gzip и bzip2 на их производительность в задаче классификации?

  5. Как непосредственно использовать алгоритмы на основе LZ77 и BWT для классификации (не используя шельфовый трюк)?

  6. Алгоритм bzip2 пользуется классификацией без обучения для группировки 50-буквенных фрагментов текста. Можно ли использовать подход к классификации без обучения с помощью индекса повторяемости, предложенный в [11] для аналогичной группировки и даёт ли это какой-нибудь выигрыш?

3  Автоматическая разметка

3.1  Краткое описание

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

Анализ естественно-языковых текстов часто относят к задачам искуственного интеллекта. Однако, после преждевременных заявлений о реальности машинного перевода в 1960-х годах, многие учёные скептически относятся к утверждениям об автоматическом «понимании» естественно-языковых текстов. Наиболее развитые исследования в этой области сфокусированы в специальных областях, на небольших словарях, специальном (и сложном!) программировании, но даже при огромных затратах труда построенные системы ИИ зачастую далеки от желаемых возможностей. Специальные корпуса текстов представляют большой шаг вперёд к статистическому подходу в автоматической разметке текста, но их построение, опять-таки наталкивается на большие сложности.

Тем не менее во многих случаях автоматическая разметка текста всё-таки возможна, поскольку понимание текста не всегда является необходимым для разметки структурированной информации, с которой мы ежедневно имеем дело в большинстве документов. Обычные документы полны очевидно структурированной информацией: телефоны, факсы, почтовые адреса, адреса электронной почты, подписи к электронным письмам, аннотации, содержания, списки ссылок на литературу, просто списки (например, новостей с датами), таблицы, даты, картинки, заголовки, адреса в интернете, и т.п. При чтении электронных книг, которые обычно хранятся в текстовом формате, отформатированными по правому краю в 70 символов, тоже возникают структурированные данные: абзацы; переносы, тире и дефисы, путающиеся друг с другом; включённые в текст отрывки поэзии; заголовки частей текста; эпиграфы; примечания; имена авторов, жанр произведения, предисловия (других авторов); различные способы выделения текста (например, парой символов подчёркивания или парой звёздочек); номера страниц, сохранившиеся от исходных текстов (приводит к ошибкам в определении переносов); примечания оцифровщика текстов (в конце или в начале текста) и т.п.

Настоящую проблему для составителей размеченных корпусов текстов представляют имена и названия. Скажем, депутата по фамилии «Носков» очень трудно стандартными методами (без понимания текста) отделить от «носков» и т.д. Имеется ли какой-нибудь выход из такой ситуации? Да, имеется, и он состоит в использовании моделей для текста, и тесно связан со сжатием данных с использованием PPM.

Напомним, что сжатие PPM разбивается на два этапа: моделирование исходного текста и его кодирование [4]. Идея подхода очень проста. Предположим, что у нас уже имеется размеченный текст S и будем для простоты считать, что при разметке использовались мета-символы, отсутствующие в стандартном представлении текстов с помощью расширений ASCII. Наша задача: восстановить разметку текста T, который никаких мета-символов не содержит. Например, в тексте S явным образом размечены начала каждого абзаца символом @, в то время как текст T таких символов не содержит.

Чтобы восстановить разметку предлагается сначала построить модель M для текста S. Далее, мы пытаемся выбрать такой вариант разметки текста T, который обеспечивает его кодирование минимальной длиной с использованием модели M. Разумеется, перебор всех вариантов не всегда возможен и его можно сузить некоторыми априорными соображениями. В нашем примере с простановкой символов абзаца @ по-видимому, достаточно перебирать варианты простановки @ только в начале строк. На практике создаётся дерево всех возможных вариантов, которое время от времени обрезается (своеобразный метод ветвей и границ). Имеются и другие хитрости, которые можно найти в [12,13,14].

3.2  Открытые вопросы и задачи

  1. Возможно ли использование алгоритмов, отличных от PPM для задач автоматической разметки текста? Пример предыдущего раздела показывает, что классификацию текстов можно проводить с использованием шельфового алгоритма с любыми алгоритмами сжатия текста. Возможно, аналогичный трюк существует и для LZ77- и BWT- методов сжатия текста.

  2. Можно улучшать сжатие за счёт использования разных моделей для разных структурных единиц текста - имён, названий и т.п. Как полученный эффект соотносится с эффектом улучшения сжатия от предварительной обработки текста, описанного в [4]?

  3. Создать дружественную пользователю систему автоматической разметки. Желающие помочь могут обращаться к автору этого сочинения.

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

[1]
C. E. Shannon. A mathematical theory of communication. Bell System Technical Journal, 27:379-423,623-656,1948, 1948.

[2]
А.Н. Колмогоров. Три подхода к определению понятия «количество информации». Пробл. Пер. Информ., 1(1):3-11, 1965.

[3]
P. F. Brown, S. A. Della Pietra, V. J. Della Pietra, J. C. Lai, and R. L. Mercer. An estimate of an upper bound for the entropy of English. Computational Linguistics, 18(1):31-40, 1992.

[4]
Д. Ватолин, А. Ратушняк, М. Смирнов, and В. Юкин. Методы сжатия данных. Устройство архиваторов, сжатие изображений и видео. Диалог-МИФИ, Москва, 2002.

[5]
N. Thaper. Using compression for source based classification of text. Master's thesis, M.I.T., February 2001.

[6]
О.В. Кукушкина, А.А. Поликарпов, and Д.В. Хмелёв. Определение авторства текста с использованием буквенной и грамматической информации. Проблемы передачи информации, 37(2):96-108, 2001.

[7]
W. J. Teahan and D. J. Harper. Using compression- based language models for text categorization. In Workshop on Lang. Modeling and Inform. Retrieval, pages 83-88, Carnegie Mellon University, May 2001.

[8]
D.Khmelev and B.Teahan. Repetition based measure for verification of text collections and text categorization. In Submitted to SIGIR'03, 2003.

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

[10]
D.V. Khmelev. Disputed Authorship Resolution through Using Relative Empirical Entropy for Markov Chains of Letters in Human Language Text. J. of Quantitative Linguistics, 7(3):201-207, 2000.

[11]
D.Khmelev and B.Teahan. Verification of text collections for text categorization and natural language processing. Technical Report AIIA 03.1, University of Bangor, School of Informatics, 2003.

[12]
W. J. Teahan, S. Inglis, J. G. Cleary, and G. Holmes. Correcting english text using ppm models. In Proc. DCC'1997, pages 289-298, Los Alamos, CA, 1997.

[13]
I. H. Witten, Z. Bray, M. Mahoui, and W. J. Teahan. Using language models for generic entity extraction. In ICML-99 Worskhop: Machine learning in text data analysis, 1999.

[14]
W. J. Teahan, Y.Y. Wen, R. McNabb, and I. H. Witten. Using compression models to segment Chinese text. Computational Linguistics, 26(3):375-393, 2000.

Содержание

1  Введение
2  Классификация
    2.1  О классификации мышей
    2.2  О классификации текстов: обзор других методов
    2.3  Энтропийная классификация (с помощью сжатия)
    2.4  Открытые вопросы
3  Автоматическая разметка
    3.1  Краткое описание
    3.2  Открытые вопросы и задачи

Примечания:

1которое получилось не совсем кратким

2Оговорка «как правило» имеет смысл, поскольку имеются более сложные способы кодирования букв, особенно, если они представляются в Уникоде (Unicode): UCS-2, UCS-4, UTF-8 и т.п.; не считая экзотических внутренних кодировок в MULE Emacs, LATEXа и прочих многоязыковых программных пакетов

3Только Ворд без ухищрений не подходит!

4Jeff Gilchrist, jeffg@cips.ca

5 ftp://garbo.uwasa.fi/pc/programming/lds\_11.zip