«Методы автоматической рубрикации текстов, основанные на машинном обучении и знаниях экспертов ...»

Московский Государственный Университет им. М.В. Ломоносова

На правах рукописи

Агеев Михаил Сергеевич

Методы автоматической рубрикации текстов,

основанные на машинном обучении

и знаниях экспертов

05.13.11 - Математическое и программное обеспечение

вычислительных машин, комплексов и компьютерных сетей

ДИССЕРТАЦИЯ

на соискание ученой степени кандидата физико-математических наук

Научные руководители: д.ф.-м.н., акад. Бахвалов Н.С., д.т.н, проф. Макаров-Землянский Н.В.

Москва, 2004

ОГЛАВЛЕНИЕ

1 ВВЕДЕНИЕ

2 ОБЗОР МЕТОДОВ АВТОМАТИЧЕСКОЙ РУБРИКАЦИИ

ТЕКСТОВ

2.1 ОСНОВНЫЕ ПОДХОДЫ К ПРЕДСТАВЛЕНИЮ ТЕКСТОВ ДЛЯ

КОМПЬЮТЕРНОЙ ОБРАБОТКИ

2.1.1 Использование морфологии

2.1.2 TF*IDF

2.1.3 Борьба с высокой размерностью: сокращение числа используемых атрибутов путем выделения наиболее значимых... 2.1.4 Использование дополнительных атрибутов документа................ 2.2 МЕТРИКИ КАЧЕСТВА РУБРИЦИРОВАНИЯ

2.3 ОЦЕНКИ МЕТОДА МАШИННОГО ОБУЧЕНИЯ НА КОЛЛЕКЦИИ

ДОКУМЕНТОВ

2.4 ОБЗОР ПУБЛИКАЦИЙ, ПОСВЯЩЕННЫХ ПРАКТИЧЕСКОМУ СРАВНЕНИЮ

МЕТОДОВ МАШИННОГО ОБУЧЕНИЯ

2.5 ОБЗОР МЕТОДОВ МАШИННОГО ОБУЧЕНИЯ

2.5.1 Метод Байеса

2.5.2 Метод k-ближайших соседей

2.5.3 Rocchio classifier

2.5.4 Нейронные сети.

2.5.5 Деревья решений

2.5.6 Построение булевых функций

2.5.7 Support Vector Machines

2.6 ОБЗОР МЕТОДОВ, ОСНОВАННЫХ НА ЗНАНИЯХ

2.6.1 Технология классификации LexisNexis

2.6.2 Технология классификации Reuters

2.6.3 Технология классификации документов на основе тезауруса УИС РОССИЯ

2.7 ВЫВОДЫ

3 МЕТОД МАШИННОГО ОБУЧЕНИЯ, ОСНОВАННЫЙ НА

МОДЕЛИРОВАНИИ ЛОГИКИ РУБРИКАТОРА

3.1 ОПИСАНИЕ АЛГОРИТМА ПФА (АЛГОРИТМА ПОСТРОЕНИЯ ФОРМУЛ)....... 3.1.1 Шаг 1: вычисление векторного представления

3.1.2 Шаг 2: построение конъюнктов

3.1.3 Шаг 3: построение дизъюнкции

3.1.4 Шаг 4: усечение формулы

3.1.5 Построение формулы с отрицаниями

3.2 АНАЛИТИЧЕСКОЕ ИССЛЕДОВАНИЕ АЛГОРИТМА

3.2.1 Описание алгоритма ПФБА

3.2.2 Свойства метрик полнота, точность, F-мера

3.2.3 Исследование сходимости алгоритма ПФБА для «идеальной»

рубрики

3.3 ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ АЛГОРИТМА ПОСТРОЕНИЯ

ФОРМУЛ ПФА

3.3.1 Описание программной реализации алгоритма

3.3.2 Эксперименты на коллекции Reuters-21578

3.3.3 Эксперименты на коллекции РОМИП-2004

3.4 ВЫВОДЫ

4 ТЕМАТИЧЕСКИЙ АНАЛИЗ КОЛЛЕКЦИИ ДОКУМЕНТОВ.... 4.1 ТЕМАТИЧЕСКИЙ АНАЛИЗ КОЛЛЕКЦИИ ДОКУМЕНТОВ ON-LINE................ 4.1.1 Анализ по тезаурусу

4.1.2 Анализ по метаданным

4.1.3 Анализ с использованием алгоритма построения формул............ 4.1.4 Применение тематического анализа в ИС

4.2 ПОВЫШЕНИЕ ЭФФЕКТИВНОСТИ РУБРИЦИРОВАНИЯ, ОСНОВАННОЕ НА

ТЕМАТИЧЕСКОМ АНАЛИЗЕ

4.2.1 Общие проблемы ручной классификации для больших рубрикаторов

4.2.2 Использование информеров при решении задач классификации.. 4.3 ВЫВОДЫ

5 ЗАКЛЮЧЕНИЕ

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

1 Введение Классификация/рубрикация информации (отнесение порции информации к одной или нескольким категориям из ограниченного множества) является традиционной задачей организации знаний и обмена информацией. В больших информационных коллекциях имеет смысл говорить только об автоматической рубрикации.

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

При применении методов машинного обучения для построения классификатора используется коллекция документов, предварительно отрубрицированная человеком. Алгоритм машинного обучения строит процедуру классификации документов на основе автоматического анализа заданного множества отрубрицированных текстов.

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

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

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

';

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

В исследованиях, посвященных применению методов машинного обучения для классификации текстов, применяются универсальные алгоритмы, которые применимы для широкого круга задач анализа и обработки информации. Например, метод SVM (Support Vector Machines, [78, 55]) успешно используется для задач распознавания образов и оценки плотности сред. Для задачи классификации текстов эти методы работают с абстрактной векторной моделью документа и не учитывают особенностей задачи тематической классификации текстов и структуры рубрикатора. Тем не менее, во многих случаях методы машинного обучения дают весьма высокие результаты. Качество рубрикации для систем, основанных на машинном обучении, является довольно высоким для небольших рубрикаторов, и сильно падает с увеличением количества рубрик и усложнением структуры рубрикатора.

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

Необходимость применения методов, основанных на знаниях, для больших рубрикаторов — 500 и более рубрик — отмечалась, в частности, нескольких докладах на семинаре по практической классификации текстов в рамках конференции SIGIR-2001 и SIGIR-2002 [71, 59]. Инженерный подход обычно обеспечивает высокое качество рубрицирования и "прозрачность" алгоритма — результаты обработки легко интерпретировать (почему такой-то документ был отнесен к рубрике). К сожалению, при использовании инженерного подхода зачастую совсем не используется ресурс, состоящий в наличии коллекции отрубрицированных текстов. Основной проблемой инженерного подхода является высокая трудоёмкость создания системы автоматической классификации (от 1 до 8 человеко-часов на одну рубрику [82, 30]).

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

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

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

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

Содержание диссертации организовано в соответствии с указанными целями:

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

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

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

Экспериментальное исследование на различных коллекциях реальных текстов позволяет утверждать что соответствуют содержанию рубрики;

2. алгоритм показывает высокое качество классификации текстов (в одном из сравнительных тестов — лучший результат по сравнению с 8 другими алгоритмами).

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

Данные средства внедрены в технологический процесс построения систем классификации текстов проекта Университетская Информационная Система РОССИЯ, разрабатываемого в НИВЦ МГУ (Научно-Исследовательском Вычислительном Центре МГУ им.

М.В. Ломоносова).

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

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

Структура обзора следующая:

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

• В разделах 2.2 и 2.3 описываются общепринятые метрики качества рубрицирования и способы вычисления метрик на коллекции документов.

• В разделе 2.4 мы дадим обзор публикаций, посвященных практическому сравнению различных методов классификации текстов, основанных на машинном обучении. Основным выводом из нескольких независимых публикаций является преимущество одного из методов — SVM (Support Vector Machines, описание в разделе 2.5.7) — над другими методами машинного обучения. Это позволяет нам выбрать SVM в качестве отправной точки для сравнения разрабатываемых нами методов с другими методами машинного обучения. Основным недостатком метода SVM является сложность в интерпретации правил отнесения документов к рубрике, которые используются SVM. Это означает, что для достижения целей диссертации — взаимной интеграции методов машинного обучения и методов, основанных на знаниях — SVM мало пригоден и требуются иные подходы.

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

• В разделе 2.6 мы опишем методы автоматической классификации тестов, основанные на знаниях.

• В последнем разделе 2.7 мы опишем выводы из данного раздела.

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

Вторым этапом является построение классифицирующей функции при помощи обучения на примерах.

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

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

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

Существуют примеры систем, которые учитывают более сложные факторы:

порядок слов в тексте [69], структура текста, содержащего разметку [43, 37].

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

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

Опишем основные приемы, применяемые для преобразования текстов в векторы пространства признаков.

2.1.1 Использование морфологии Для того чтобы объединять различные морфологические формы слова в одну координату пространства признаков, каждое слово исходного текста приводится к своей нормализованной форме (лемме). Для английского языка обычно применяется процедура нормализации слов, которая заключается в отсечении окончания слова (stemming). Для русского языка процедура нормализации слов является более сложной, но на данный момент существуют распространённые методы её решения [20]. Отдельной проблемой является тот факт, что в естественном языке одному слову текста может соответствовать несколько различных начальных форм. Например, слову "суда" можно сопоставить две начальные формы: "суд" и "судно". В таких случаях имеет смысл добавлять к тексту обе начальные формы слова.

Существуют методы разрешения многозначности слов в тексте [32], которые позволяют определять, какое из значений слова следует использовать в данном случае, однако мы не будем рассматривать эти методы в рамках данной работы.

2.1.2 TF*IDF Отдельной задачей при преобразовании текста в вектор является признакам, также называемых весами признаков. Выбор весов признаков существенно влияет на качество рубрицирования. В статье [75] приводится подробное исследование различных подходов к выбору весов признаков.

Результаты экспериментов, описанных в этой статье, показывают, что одной из лучших формул вычисления весов является Где wi - вес i-го слова, tfi - частота встречаемости i-го слова в данном документе (term frequency), idfi = log - логарифм отношения количества всех документов в коллекции к количеству документов, в которых встречается i-е слово (inverse document frequency).

Такой выбор формулы можно обосновать теоретически следующими соображениями:

1) Чем чаще слово встречается в документе, тем оно важней. Этот факт учитывает множитель tfi.

2) Если слово встречается во многих или во всех документах, то это слово документа рубрике и его вес следует понизить. Наоборот, если слово встречается в малом количестве документов, то его вес следует повысить. Множитель idfi учитывает это соображение и соответствует весу слова ("контрастности") в данной коллекции документов.

3) Для того чтобы учесть различную длину текстов документов в формуле (1) веса нормализуются так, чтобы сумма квадратов весов каждого документа была равна 1.

Существуют также другие варианты формулы tf*idf, которые дают близкие по качеству результаты. В наших экспериментах мы использовали TF*IDF в формулировке INQUERY [56, 14]:

где dl — мера длины документа, avg_dl – средняя длина документа, = 0.4, где N — количество документов в коллекции, n — количество документов, где встретилось i-е слово.

В некоторых случаях для вычисления веса слова в тексте привлекается также дополнительная информация [37]. Например, можно учитывать информацию о структуре текста и словам, встреченным в заголовке, присваивать больший вес [54].

используемых атрибутов путем выделения наиболее значимых.

Даже после приведения всех слов документа к нормализованной уменьшить без ухудшения качества рубрицирования, если выкинуть слова, слабо влияющие на результаты рубрицирования [81].

Во-первых, обычно из списка признаков удаляют так называемые "стоп-слова" — предлоги, союзы и т.п. Это не сильно сокращает размерность пространства признаков (список стоп-слов составляется вручную и обычно является небольшим). Но зато удаление стоп-слов обычно улучшает качество рубрицирования за счет удаления информационного шума.

Во-вторых, из списка признаков можно удалить слишком редко встречающиеся слова.

Опишем эксперимент по обработке коллекции русскоязычных текстов было обработано 10372 документа общим объемом около 65 мегабайт.

После приведения слов к нормальной форме получилось 202584 различных слов, из которых около 80% встречались всего только в одном документе.

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

Кроме удаления редко встречающихся слов часто применяется методы выделения слов с использованием критерия информационного веса слова в рубрике (mutual information gain). Информационный вес слова в рубрике определяется по формуле Здесь P( xi, c) - вероятности совместного распределения слов и рубрики. Легко видеть, что если распределения слова xi и рубрики c статистически независимы, то MI ( xi, c) = 0. Если же между встречаемостью слова xi и рубрики имеется строгая логическая зависимость, то MI ( xi, c) c максимально. Метод сокращения размерности на основе выделения наиболее информационно-значимых слов применяется, например, в работе [58].

2.1.4 Использование дополнительных атрибутов документа В некоторых случаях, кроме слов, в векторное представление текста включаются также дополнительные атрибуты документа. Это позволяет улучшить качество рубрицирования [54]. В разделе 2.6.3 мы опишем подход к построению векторного представления документов, основанный на терминологическом индексе.

2.2 Метрики качества рубрицирования Основным критерием оценки качества работы методов автоматической классификации текстов является сравнение результатов работы метода с оценками экспертов. При этом "идеальным" алгоритмом считается тот, для которого выводы, сделанные системой, согласуются с мнением экспертов оценщиков [9, 74, 42].

Для проведения таких оценок существуют, с одной стороны, свободно доступные коллекции отрубрицированных документов [70]. С другой стороны, ежегодно проводятся конференции по практической оценке методов классификации: международная TREC (Text REtrieval Conference, http://trec.nist.gov) и российская РОМИП (Российский семинар по Оценке Методов Информационного Поиска, http://romip.narod.ru [51]).

Наиболее широко применяемыми оценками качества рубрицирования являются полнота и точность. Введём определения. Пусть C — множество документов, принадлежащих рубрике и u — множество документов, автоматически приписанных рубрике.

Определение (полнота классификации документов по рубрике):

полнота (recall) классификации документов по рубрике вычисляется как (автоматически) к рубрике к общему количеству документов, относящихся к данной рубрике:

рубрике): точность (precision) классификации документов по рубрике вычисляется как отношение количества документов, правильно приписанных (автоматически) к рубрике к общему количеству документов, приписанных к данной рубрике:

Полнота и точность классификации обычно измеряются в процентах.

Для идеального алгоритма и полнота, и точность равны 100%.

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

В некоторых случаях для оценки качества классификации требуется оценка в виде одного числа. Существует несколько известных формул для такой оценки [79, 77], одной из наиболее часто используемых является так называемая F-measure:

Или, в общем случае, Здесь > 0 — параметр, устанавливающий отношение важности параметров В случае если производится классификация документов по нескольким рубрикам, для получения сводных оценок качества рубрицирования применяются различные методы усреднения характеристик по всем рубрикам. Так как различные рубрики имеют разную частотность, выбор метода усреднения представляет собой отдельную задачу [79]. Приведем здесь два наиболее часто применяемых метода усреднения: microaverage и macroaverage.

документы u1,…,u n. Тогда сводные оценки полноты и точности можно определить как Аналогично можно определить макро- и микроусредненные оценки F.

Макроусреднение применяется чаще, так как отражает поведение метода в среднем по рубрикам.

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

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

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

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

Естественно, что качество рубрицирования зависит от того, как было разбито множество отрубрицированных документов на обучающее и тестовое множество. Здесь важно отметить два момента:

• Чем больше обучающее множество, тем лучше можно обучить алгоритм. В то же время, на малом тестовом множестве оценки качества могут быть слишком грубыми.

документов может сильно повлиять на результаты и привести к повышению или, наоборот, понижению оценок качества.

Обычно для опытов по сравнению различных алгоритмов машинного обучения разбиение выполняют случайно либо по некоторому признаку, не зависящему от содержания документа (например, дате). Для опытов по сравнению различных методов обучения разбиение фиксируют. Для коллекции документов Reuters-21578 [70], например, существуют фиксированные разбиения на обучающее и тестовое множество, которые рекомендуют использовать разработчикам методов машинного обучения для тестирования своих методов и опубликования экспериментов по сравнению с другими методами. Эти разбиения описаны в документе, сопровождающем коллекцию Reuters [70].

Кроме тестирования методов на фиксированном разбиении часто используется метод усреднения метрик качества по различным разбиениям.

Такой метод называется кросс-валидацией. Опишем алгоритм кроссвалидации:

разбивается на k частей (k - параметр кросс-валидации).

2.1.Составляется тестовое множество из i-й части (в нем N/k 2.2.Составляется обучающее множество из всех остальных документов (в нем N-N/k документов).

2.3.Алгоритм обучается на обучающем множестве, и вычисляются оценки качества работы на тестовом множестве.

3. Вычисляются усредненные оценки качества по всем k тестам.

Алгоритм кросс-валидации позволяет получить весьма точные оценки качества работы алгоритма. Чем больше k, тем больше получается множество для обучения и выше качество работы. С другой стороны, чем больше k, тем ниже скорость работы.

В конференциях по оценке методов классификации текстов, таких как TREC и РОМИП, применяется фиксированное разбиение множества документов. Участники получают отрубрицированную коллекцию документов для обучения плюс коллекцию документов, которые необходимо отрубрицировать (без указания классификации). После того, как участники присылают результаты классификации, оргкомитет вычисляет оценки качества рубрицирования и публикует результаты.

2.4 Обзор публикаций, посвященных практическому сравнению методов машинного обучения Задача сравнения различных методов классификации текстов очень важна с практической точки зрения. Существует множество проблем, которые приходится решать для получения достоверных результатов сравнения. Одной из таких проблем является выбор коллекции документов, на которой должно производиться сравнение. Эта коллекция документов должна обладать следующими свойствами:

1. Достаточно большой объем отрубрицированных документов.

2. Высокое качество рубрикации (малое количество ошибок).

3. Доступность коллекции.

Некоторым стандартом сейчас считается коллекция документов Reuters [70]. Опишем некоторые результаты сравнения методов машинного обучения на задаче классификации текстов.

В статье [63] сравниваются следующие методы машинного обучения на задаче классификации текстов коллекции Reuters:

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

В статье [58] исследуются различные методы усечения пространства признаков, и производится сравнение методов машинного обучения на задаче классификации текстов коллекции Reuters. Сравниваются следующие методы:

• FindSimilar (аналог k-ближайших соседей) • метод Байеса • Байесовы сети • деревья решений Результаты показали, что метод SVM имеет преимущество над другими исследуемыми методами машинного обучения.

В статье [80] производится сравнение нескольких методов машинного обучения на той же коллекции документов Reuters:

• метод Байеса • метод k-ближайших соседей • LLSF (линейная регрессия) • нейронные сети В этой статье автор отмечает, что его результаты рубрицирования отличаются от опубликованных в [63]. А именно: результаты рубрицирования SVM несколько хуже, а результаты рубрицирования при помощи метода Байеса и метода k-ближайших соседей лучше, чем опубликованные в [63]. Тем не менее, выводы делаются те же: SVM имеет (хоть и небольшое) преимущество перед другими методами машинного обучения.

Также стоит отметить статью [68]. Автор этой статьи участвовал в конференции TREC-2001 и получил высокие результаты в конкурсе batch filtering (классификация текстов). В предисловии автор статьи пишет следующее: "Моя цель в TREC-2001 была проста: запустить задания по некоторым конкурсам (чтобы поучаствовать в конференции), потратить минимум времени (так как я был занят в этом году большим проектом) и получить достойный результат (маркетинг!)". Льюис использовал программу SVM_light с небольшими модификациями и получил то, чего добивался. В трех номинациях результаты Льюиса были лучшими на большинстве рубрик.

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

Методы классификации объектов, основанные на обучении, впервые введены в рассмотрение в 1960-е годы [48, 52, 19, 35]. В настоящее время разработано множество методов машинного обучения, которые применяются при решении широкого круга задач [78, 27, 36, 23, 26, 53]. Многие из этих опубликованы результаты применения для задач классификации текстов.

2.5.1 Метод Байеса признаков документа и категорий [80]. Документу сопоставляется наиболее вероятная апостериори категория по формуле В задаче классификации текстов метод Байеса применяется отдельно для каждой категории и принимается решение, принадлежит документ категории или нет.

вычисляется по формуле Байеса, связывающей априорную вероятность с апостериорной:

Подставляя (2.5) в (2.4), получаем:

Так как знаменатель не зависит от категории, его можно сократить:

Условные вероятности P( x1 = d1, x2 = d 2,…, xn = d n | c) можно вычислить в предположении условной независимости переменных x1, x2,…, xn. В этом случае, формула для определения наиболее вероятной категории будет выглядеть следующим образом:

P( xi = di | c) вычисляются по формуле Добавление единицы в числителе нужно для того, чтобы документы, уникальные слова), имели отличную от нуля вероятность для всех рубрик. В статье [64] рассматриваются различные формулы для аппроксимации P( xi = di | c) и их влияние на качество рубрикации.

Конечно, предположение о независимости переменных x1, x2,…, xn является слишком сильным (поэтому метод Байеса иногда называют «наивным» — naive bayes classifier). На самом деле это предположение практически никогда не выполняется. Тем не менее, метод Байеса дает на удивление высокие результаты в задаче классификации текстов. [80, 79, 63].

Метод Байеса обладает высокой скоростью работы и простотой математической модели. Этот метод часто используется в качестве базового метода при сравнении различных методов машинного обучения.

2.5.2 Метод k-ближайших соседей Метод k-ближайших соседей (k-nearest neighbours, k-NN), в отличие от других, не требует фазы обучения. Для того чтобы найти рубрики, релевантные документу d, этот документ сравнивается со всеми документами из обучающей выборки. Для каждого документа e из обучающей выборки, находится расстояние - косинус угла между векторами признаков:

Далее из обучающей выборки выбираются k документов, ближайших к d (k - параметр). Для каждой рубрики вычисляется релевантность по формуле Рубрики с релевантностью выше некоторого заданного порога считаются соответствующими документу. Параметр k обычно выбирается в интервале от 1 до 100.

Данный метод показывает довольно высокую эффективность [80], но требует довольно больших вычислительных затрат на этапе рубрикации.

2.5.3 Rocchio classifier Классификатор Роше (Rocchio) — один из самых простых методов классификации. Для каждой категории вычисляется взвешенный центроид по формуле Здесь Rc - множество документов, принадлежащих категории; Rc,k - k документов, не принадлежащих категории, наиболее близких к центроиду d ; — параметр, указывающий относительную важность учета | Rc | dRc отрицательных примеров (обычно используется < 1 ).

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

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

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

2.5.4 Нейронные сети.

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

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

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

Архитектура ИНС позволяет эффективно распараллеливать процесс обучения и применения НС. Имеется ряд экспериментов по использованию нейронных сетей для классификации текстов. В статье [80] отмечается очень долгое время обучения ИНС. Это связано с тем, что для задач высокой размерности требуется ИНС с большим количеством узлов.

2.5.5 Деревья решений.

Деревья решений (decision trees) разбивают данные на группы на основе значений переменных пространства признаков, в результате чего возникает иерархия операторов "ЕСЛИ-ТО", которые классифицируют данные [33, 25]. Для принятия решения, к какой категории отнести данный документ, требуется ответить на вопросы, стоящие в узлах этого дерева, начиная с его корня. Вопросы имеют вид "значение переменной xi больше порога bi ?". Если ответ положительный, осуществляется переход к правому узлу этого дерева, если отрицательный - к левому узлу. Затем следует вопрос, связанный с соответствующим узлом.

Для автоматического построения деревьев решений при помощи обучения на примерах разработан ряд алгоритмов [73, 33]. Рассмотрим один из таких алгоритмов - CLS [24]. Этот алгоритм циклически разбивает обучающие примеры на классы в соответствии с переменной, имеющей наибольшую классифицирующую силу. Каждое подмножество примеров, использованием переменной с наибольшей классифицирующей способностью и т.д. Разбиение заканчивается тогда, когда в подмножестве оказываются лишь элементы из одного класса. В ходе процесса образуется дерево решений.

Для определения переменной с наибольшей классифицирующей силой используется критерий информационного веса слова в рубрике (раздел 2.1. формула (2.2)).

Обычно после построения «точного» дерева решений к полученному дереву применяются различные процедуры усечения и преобразования дерева для того, чтобы обеспечить баланс между сложностью дерева (количеством узлов) и качеством обучения. Классическим подходом для преобразования деревьев решений является алгоритм C4.5 [73].

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

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

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

проблемой повторения (replication problem) [72]. Пусть рубрика описывается простой формулой вида где А, Б, В и Г — некоторые множества документов, соответствующие одному из признаков. В этом случае дерево решений для рубрики С (описывающее рубрику без ошибок) будет обязательно повторять некоторые из элементов А, Б, В, Г (см. рис 1). Всего в дереве решений для формулы (2.10) имеется 6 узлов. Для более сложных дизъюнктивных формул, аналогичных (2.10), проблема повторения узлов усугубляется: размер дерева решений может экспоненциально расти при увеличении длины формулы.

Рис. 1. Дерево решений для формулы (2.10). Листья В и Г повторяются по два раза.

Ещё одним недостатком деревьев решений для задач классификации текстов является тот факт, что алгоритм построения деревьев решений даёт одинаковый вес «положительным» и «отрицательным» ветвлениям в узлах.

Большое количество «отрицательных» веток в описании рубрики может приводить к трудно интерпретируемым правилам и «переобучению»

алгоритма классификации [72].

2.5.6 Построение булевых функций классификации в виде «если выполняется формула, то рубрика A». К основным методам построения правил классификации можно отнести • построение правил вывода на основе деревьев решений;

• методы ограниченного перебора для правил заданного вида.

Первым способом является построение правил на основе деревьев решений. Действительно, каждому пути по дереву решений от корня до листа соответствует правило вида где fi — некоторый признак (значение булевской переменной), i {0,1} (то есть fi может входить в формулу с отрицанием или без), C — некоторая рубрика или множество документов, к которым не относится ни одной рубрики. Таким образом, для одной рубрики можно преобразовать дерево решений в следующую формулу:

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

раздел 2.5.5).

Другим способом построения правил является перебор всевозможных правил в виде формул заданного вида. В нашей стране впервые методы такого типа были разработаны М.М. Бонгардом в 1960-е годы [23, 26, 45]. В алгоритме «Кора» выполняется полный перебор формул определённого вида и отбираются формулы, подходящие для описания заданного класса объектов.

В статье [72] описывается алгоритм построения формул вида C = fi, ji, j для задач медицинской диагностики. В описываемой задаче пространство признаков состоит из различных симптомов и медицинских показателей и имеет размерность порядка одного-трёх десятков. Приводится алгоритм перебора различных формул и оценивается время его работы.

Количество шагов алгоритма, требуемое для полного перебора, экспоненциально зависит от размерности пространства признаков.

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

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

2.5.7 Support Vector Machines.

Метод опорных векторов (Support Vector Machines, SVM) разработан В. Вапником на основе принципа структурной минимизации риска — одновременного контроля количества ошибок классификации на множестве для обучения и «степени обобщения» обнаруженных зависимостей [78, 55, 27].

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

Нахождение оптимальной плоскости методом SVM сводится к решению оптимизационной задачи с линейными ограничениями типа равенств и неравенств [78]:

Здесь K ( xi, x j ) - функция ядра SVM, которая в простейшем случае равна евклидову скалярному произведению векторов xi и x j. Для задачи (2.13) предложены эффективные методы решения [65, 66].

Существуют также обобщения метода SVM для случая, когда разделяющей гиперплоскости не существует. В этом случае SVM ищет разделяющую гиперплоскость, одновременно минимизируя количество ошибок и максимизируя зазор между разделяющей гиперплоскостью и ближайшими примерами. SVM также может искать отделяющее рубрику правило в классе нелинейных нелинейных разделяющих поверхностей. Для этого используются нелинейные функции ядра [78, 55].

Метод SVM работает с абстрактной векторной моделью предметной области. Это позволяет применять SVM для решения различных задач машинного обучения. SVM используется для задач распознавания образов, распознавания речи, классификации текстов.

2.5.7.1 Программные реализации SVM подробный список можно найти в интернете на http://www.kernelmachines.org/software.html. Один из свободно распространяемых пакетов, SVM_light [65], специально приспособлен для задач высокой размерности, которые возникают в задаче автоматической классификации текстов. Этот пакет использовался несколькими исследователями для обработки текстовых массивов [63, 68].

Для наших исследований мы использовали SVM_light v. 3.50 [65].

2.5.7.2 Оптимизация параметров SVM В 2002 году нами были проведены исследования по улучшению результатов работы SVM для задач автоматической классификации текстов, которые показали, что для практического применения необходимо оптимизировать стандартную методику применения SVM. В статьях [6, 11] описывается метод оптимизации параметров SVM, разработанный нами для улучшения скорости и качества классификации документов методом SVM.

Эксперименты показали, что лишь параметр «относительный вес ошибок 1-го и 2-го рода» существенно влияет на качество классификации, а другие параметры не существенно влияют на качество классификации текстов.

Был разработан метод оптимизации параметра «относительный вес ошибок 1-го и 2-го рода» (будем обозначать его j), основанный на переборе значений данного параметра в некотором интервале. Были получены экспериментальные оценки зависимости границ оптимального интервала перебора от количества релевантных (pos_ex) и нерелевантных (neg_ex) рубрике документов в коллекции для обучения:

классификации по сравнению с другими методами [68] оптимизации параметров SVM.

оптимизации параметра j следующим образом:

1. Коллекция отрубрицированных документов разбивалась на две подколлекции — для обучения (70% документов) и для оценки качества результатов (30% документов).

2. Осуществлялся перебор из 10 значений параметра j в интервале (2.14).

Для каждого j SVM обучалась на подколлекции обучения. Обученная SVM применялась к подколлекции тестирования и вычислялись значения полноты, точности и F-меры рубрицирования на подколекции тестирования. Определялось оптимальное значение j, для которого достигался максимум F-меры.

отрубрицированных документов и применялась к документам, которые необходимо отрубрицировать.

SVM применялась только для тех рубрик, для которых было не менее четырёх документов в коллекции для обучения.

Для того чтобы проверить корректность полученных результатов, были также воспроизведены эксперименты [63, 58] по применению SVM для рубрицирования документов из коллекции Reuters21578 [70]. Результаты рубрицирования согласуются с опубликованными данными.

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

Полученное описание затем используется для автоматического отнесения документов к той или иной рубрике.

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

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

Мы рассмотрим три системы классификации, основанные на знаниях:

1. технологию классификации компании LexisNexis;

2. технология классификации, разработанную для агентства новостей 3. технологию классификации, разработанную в рамках проекта УИС Методы классификации в УИС РОССИЯ мы рассмотрим подробно так как, во-первых, для неё имеются достаточно подробные описания, и, вовторых, далее наше исследование будет базироваться на этих методах.

2.6.1 Технология классификации LexisNexis рубрицирования документов, применяемая в большой электронной библиотеке LexisNexis (http://www.lexisnexis.com). В описываемой технологии в основном используется ручное описание рубрик. Гибкий механизм описания правил приписывания рубрик поддерживает следующие поисковые возможности:

словоизменения (для английского языка) • Учет частотности слов с ручным заданием пороговых значений • Учет местоположения слов в документе: заголовок, аннотация, текст в начале документа, основной текст • Поддерживается задание круга источников получения информации для данной рубрики Описание одной рубрики требует 4-8 часов ручной работы без учета времени тестирования. Для большинства рубрик качество классификации находится на уровне более 90% полноты и точности (к сожалению, в указанной статье методика получения данных оценок не приводится).

2.6.2 Технология классификации Reuters В статье [60] описывается система классификации документов CONSTRUE/TIS (Categorization of News Stories, Rapidly, Uniformly and Extensibly/Topic Identification System). Система CONSTRUE/TIS использовалась агентством Reuters для классификации потоков новостных сообщений. Для отнесения документов к той или иной рубрике эксперт описывает правила в виде булевских формул. В качестве элементов выступают слова. Вот пример правила, описывающего рубрику wheat:

тезауруса УИС РОССИЯ В статье [30] описывается технология классификации документов УИС РОССИЯ ([16, 34], http://www.cir.ru). Опишем (отчасти цитируя [30]) данный алгоритм классификации.

Для решения задачи рубрицирования по большим классификаторам в УИС РОССИЯ применяется комплекс из нескольких компонентов:

• большой лингвистический ресурс – тезаурус по общественнополитической тематике, специально предназначенный для автоматической обработки и автоматических выводов о содержании • специальное программное обеспечение АЛОТ (Автоматической Лингвистической Обработки Текста), позволяющее строить модель тематического содержания текста;

• специальная технология описания смысла рубрики посредством понятий тезауруса.

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

• является прообразом свободного от субъективизма комментария к рубрикатору, который может пополняться и уточняться;

• позволяет в помощь эксперту для каждого термина в тексте определить список соответствующих рубрик;

• при выводе рубрики всегда можно показать/объяснить, почему была выведена та или иная рубрика, что позволяет быстро уточнять описание рубрик, анализируя замеченные ошибки рубрикации.

2.6.3.1 База знаний Общественно-политический тезаурус РуТез (далее — Тезаурус РуТез) является основой тематического анализа в рамках Автоматизированной лингвистической обработки текстов (АЛОТ), используемого в Информационных Исследований.

Общественно-политический тезаурус как ресурс для автоматической обработки текстов обладает следующими основными особенностями.

Во-первых, Тезаурус — это иерархическая сеть понятий, которая включает значительно больше понятий, отношений, синонимов, чем традиционные тезаурусы для ручного индексирования (75 тысяч терминов, 29 тысяч понятий, связанных более чем 100 тысячами непосредственных отношений в Общественно-политическом тезаурусе против 9.8 тысяч терминов, 6.8 тысяч понятий, связанных 15 тысячами отношениями в близком по тематике тезаурусе LIV — тезаурусе исследовательской службы Библиотеки Конгресса США [67]). Во-вторых, важнейшей особенностью является интеграция Тезауруса в процесс автоматической обработки текстов, что позволяет организовать обратную связь, анализируя результаты обработки.

Понятийная сеть Тезауруса включает до 10 уровней иерархии. Ценным свойством Тезауруса является возможность использовать транзитивность иерархических отношений (с учетом иерархии – 850 тысяч отношений, то есть в среднем каждое понятие связано с 28 другими).

2.6.3.2 Тематическое представление содержания документа Значимость термина для содержания текста определяется в результате построения так называемого тематического представления текста, слабо зависящего от величины и типа текстов. Основные этапы построения тематического представления текста таковы (подробнее см. [30, 39]):

• Сопоставление текста с Тезаурусом создает для текста «понятийный индекс», в котором указывается, какие понятия Тезауруса и в каком месте текста обнаружены;

• Для каждого понятия текста нахождение по тезаурусным связям тематически близких понятий и отражение этой информации в так называемой тезаурусной проекции текста;

• Использование связей понятий в тезаурусной проекции для разрешения многозначности терминов;

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

• Построение тематических узлов — групп близких по смыслу понятий.

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

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

В зависимости от того, элементом какой структуры тематического представления оказывается понятие d тезауруса, формируется оценка значимости (d;D). Типичные значения — 0.9 для центра основного тематического узла, 0.7 — для элемента основного тематического узла, 0.75 — для центра «локального тематического узла» и т.д. Окончательно вес понятия для текста определяется добавлением стабилизирующего фактора, учитывающего частотность понятия в документе:

2.6.3.3 Описание смысла рубрики понятиями тезауруса Каждая рубрика C описывается дизъюнкцией альтернатив, каждый дизъюнкт Di представляет собой конъюнкцию:

Конъюнкты K i, j в свою очередь описываются экспертами с помощью так называемых «опорных» понятий тезауруса di, j,k. Для каждого опорного понятия задается правило его расширения f(·), определяющее каким образом вместе с опорным понятием учитывать подчиненные ему по иерархии понятия. Выделяются три случая — без расширения, полное расширение по дереву иерархии тезауруса и расширение только по родо-видовым связям.

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

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

Типичные цифры о параметрах описания: на одну рубрику рубрикатора в среднем приходится 1-2 дизъюнкта, 2-3 конъюнкта, 10-20 опорных понятия («положительных» и «отрицательных»), 200-400 понятий полного описания, то есть 400-800 текстовых входов.

2.6.3.4 Автоматическое рубрицирование на тематическом Оценка релевантности содержания текста рубрике (вес рубрики) рассчитывается путём соотнесения документа с булевской формулой описания рубрики (2.16), с учётом информации о весах понятий в тексте, входящих в описание рубрики.

В УИС РОССИЯ вес конъюнкта рассчитывается по формуле:

где di, j,k — понятия, не требующие подтверждения; pi, j,m – понятия, требующие подтверждения; — множитель, равный единице, если имеются понятия, не требующие подтверждения, и нулю иначе.

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

Пороги, указанные в пунктах 2-4, являются параметрами алгоритма. Их можно менять в зависимости от задачи.

3.1.4 Шаг 4: усечение формулы Размер получающейся формулы, полнота и точность получающегося описания, и степень "подгонки" формулы под конкретную выборку документов зависят от соотношения параметров алгоритма. Наиболее важными являются параметры, встречающиеся в формуле (3.7).

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

3.1.5 Построение формулы с отрицаниями Одно из возможных расширений алгоритма ПФА строит формулы с отрицаниями вида (3.4):

то есть описание рубрики состоит из «положительной» части и описания «ошибок» рубрицирования. Описание рубрики U можно представить в виде разности двух формул вида (3.2), которые строит алгоритм ПФА:

Для построения такой формулы сначала применяется алгоритм ПФА к документам рубрики C. Полученную формулу обозначим U1. Затем составляется новая «псевдорубрика», состоящая из документов К псевдорубрике C' применяется алгоритм ПФА (возможно, с другими параметрами алгоритма) и получается описание псевдорубрики U 2.

3.2 Аналитическое исследование алгоритма В этом разделе мы исследуем работу алгоритма ПФА при некоторых предположениях относительно задачи и реализации алгоритма [3]. Мы рассмотрим некоторую «идеальную» ситуацию, когда рассматриваемая рубрика описывается некоторой формулой U = ti, j с полнотой и точностью, равной единице. Такая ситуация соответствует случаю, когда краткое вербальное описание рубрики может точно моделироваться булевской формулой. Кроме того, мы рассмотрим несколько упрощенную версию алгоритма, уменьшив в алгоритме ПФА количество параметров (порогов и весовых коэффициентов). Мы рассмотрим поведение алгоритма ПФА на шаге 3 — построении дизъюнкции, считая векторное представление документа и набор конъюнктов фиксированными. Упрощенный алгоритм будем называть ПФБА — «построение формул, базовый алгоритм». Все результаты, верные для упрощенного алгоритма ПФБА, верны и для полной версии алгоритма при определенном задании параметров и предположении, что список конъюнктов, вычисленных на шаге 2 алгоритма ПФА, содержит все конъюнкты формулы U*.

Основным результатом этого раздела является математически строгое доказательство того, что алгоритм ПФБА при условии существования точной формулы и достаточно «жестких» параметрах алгоритма получит хорошую формулу. Основная теорема этого раздела устанавливает связь между параметрами алгоритма и качеством i-го конъюнкта. Следствия из этой теоремы позволяют оценить скорость сходимости алгоритма и вычислить значения параметров алгоритма, для которых алгоритм за N шагов получит формулу, полнота и точность которой не менее 1 (для любого наперед заданного параметра > 0 ). Для получения оценок используются методы, аналогичные [18].

Структура данного раздела следующая:

1. в разделе 3.2.1 мы опишем алгоритм ПФБА и его отличие от «полной версии» алгоритма построения формул;

2. затем, в разделе 3.2.2 опишем некоторые свойства метрик, которые нужны для доказательства теоремы;

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

3.2.1 Описание алгоритма ПФБА Рассмотрим третий шаг алгоритма ПФА — построение дизъюнкции.

Пусть задана рубрика С — непустое множество документов и множество конъюнктов Каждый конъюнкт представляет собой непустое множество документов.

Алгоритм ПФА собирает формулу последовательно выбирая конъюнкты по шагам.

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

Обозначим текущую формулу, выбранную на шаге k как U k. На нулевом шаге U 0 =. На шаге k выбирается элементарный конъюнкт и добавляется к формуле U k 1 : U k = U k 1 u k.

Алгоритм заканчивает работу, когда достигнут 100% уровень полноты либо когда для всех конъюнктов-кандидатов F, ( v j | U k 1 ) = 0.

3.2.2 Свойства метрик полнота, точность, F-мера Для исследования свойств алгоритма ПФБА необходимо доказать участвующих в построении алгоритма.

Напомним определения функций полноты, точности и F-меры (раздел 2.2). Пусть C — множество документов, принадлежащих рубрике и u — множество документов, автоматически приписанных рубрике. Тогда Алгоритм ПФБА также использует следующие функции. Пусть v и w – некоторые множества документов. Тогда непокрытой u части рубрики на непокрытой u части рубрики 0 определяется следующим образом:

Утверждение 1 (свойства полноты):

Доказательство: свойства 1-4 и 10 тривиально следуют из определений полноты и дополняющей полноты. Свойство 6 следует из свойств 5, 1 и 2. Докажем свойство 5:

Свойство 5 доказано.

Докажем свойство 7.

Свойство 7 доказано. Аналогично доказывается свойство 8.

Докажем свойство 9. Если r ( u ) = 1 то C u. Следовательно, Свойство 9 доказано.

Утверждение доказано.

Утверждение 2 (свойства точности):

Доказательство: свойства 1-3 тривиально следуют из определения точности и дополняющей точности. Докажем свойство 4.

Можно выразить точность через эти величины следующим образом:

Так как свойство 4 симметрично относительно замены p ( u ) p ( v | u ), то без ограничения общности можно считать, что Так как, по предположению, p ( u ) p ( v | u ), то из этого следует, что Утверждение доказано.

Утверждение 3 (свойства F-меры):

Доказательство: свойства 1 и 3 следуют свойства 2. Свойство следует из свойства 4. Докажем свойство 2.

В случае если p ( u ) = 0 либо r ( u ) = 0 утверждение тривиально. Иначе, Свойство 2 доказано.

Докажем теперь свойство 4. Для этого докажем, что разность левой и правой части неравенства свойства 4 неположительна.

Свойство 4 доказано.

Утверждение 3 доказано.

«идеальной» рубрики описывающая рубрику с полнотой и точностью, равной единице. Оценим метрики качества i-го конъюнкта в формуле, которую построит алгоритм ПФБА с параметрами > 0 и 0. Эти оценки сформулированы в виде следующей теоремы:

Теорема 1: Пусть существует формула U* = u1 u * … u *, u *j V длины n, описывающая рубрику C с полнотой и точностью, равной единице.

Обозначим = min r ( u *j ), > 0.

Пусть на шаге i 1 алгоритмом ПФБА с параметрами > 0 и построена формула U i = u1 u 2 … u i. Тогда выполняются следующие неравенства:

Для доказательства Теоремы 1 докажем следующую лемму:

Лемма 1: На каждом шаге i 1 алгоритма ПФБА, если r ( U i1 ) < 1, то для Доказательство: Из условия теоремы 1 r ( U* ) = 1. Из свойств полноты (Утверждение 1 раздела 3.2.2) следует, что Из свойств полноты также следует, что Из (3.10) и (3.11) следует, что доказать.

построенная формула U i 1 и u i = arg max ( F, ( u | U i 1 ) ).

U*, то p ( u *j | U i1 ) = 1 и r ( u *j ). Следовательно, Учитывая, что числители и знаменатели правой и левой части положительны, получим 1. Для доказательства нижней оценки для дополняющей точности выделим p ( u i | U i1 ) из неравенства (1.12):

и воспользуемся неравенствами r ( u i | U i1 ) 1 и r ( u i ) 1. Получим:

Первая часть Теоремы 1 доказана.

2. Для доказательства нижней оценки для дополняющей полноты выделим r ( u i | U i1 ) из неравенства (1.12):

и воспользуемся неравенствами p ( u i | U i1 ) 1 и r ( u i ) 1. Получим:

Вторая часть Теоремы 1 доказана.

Для доказательства нижней оценки для полноты выделим r ( u i ) из неравенства (1.12) (это можно сделать при условии wr > 0 в условии теоремы):

Получим:

Или, преобразовав, получим:

Третья часть Теоремы 1 доказана.

Теорема 1 доказана.

Воспользуемся теоремой 1 для того, чтобы оценить оптимальный выбор параметров алгоритма ПФБА для получения формулы заданного качества. Пусть алгоритм ПФБА строит по шагам формулу U = u i Следствие 1: Пусть выполняются условия теоремы 1 и задан параметр Доказательство: Если = 1, то утверждение теоремы тривиально.

Иначе, пусть Так как правая часть последнего неравенства положительна, то из теоремы 1 пункта 3 следует, что Подставляя (1.13) в (1.14), получаем Что и требовалось доказать.

Следствие 2: Пусть выполняются условия теоремы 1 и задан параметр ( 0,1). Тогда, если то для любого i = 1..N Доказательство: Пусть выполняется условие (1.15) Из теоремы 1 пункта 1 следует, что параметре x > 0 и > 0, то, подставляя (1.15) в (1.16), получаем искомое неравенство:

Теперь докажем по индукции, что p ( U i ) 1.

2. Из свойства точности (Утверждение 2 раздела 3.2.2) следует, что Следствие 2 доказано.

Следствие 3: Пусть выполняются условия теоремы 1 и задан параметр ( 0,1). Тогда для любого i = 1..N Доказательство: Обозначим Из теоремы 1 пункта 2 следует, что r ( u i | U i 1 ). Из определения Запишем рекуррентные соотношения:

Решая рекуррентное соотношение, получаем Преобразовывая, получаем:

Первое утверждение следствия доказано.

Теперь докажем второе утверждение следствия. Выражение (1.19) эквивалентно получим Это эквивалентно Вторая часть утверждения доказана.

Следствие 3 доказано.

Следствия 1 и 2 позволяют утверждать, что, если существует формула, которая точно описывает заданное множество документов (рубрику), то алгоритм ПФБА, при достаточно «жестких» параметрах (т.е. больших значениях и ) построит формулу, описывающую рубрику с заданным уровнем качества. А именно: для любого, сколь угодно малого параметра > 0 можно выбрать параметры алгоритма так, что 1. точность полученной формулы будет не менее 2. каждый конъюнкт будет иметь покрытие (полноту) почти как у Следствие 3 позволяет вычислить длину формулы, которая описывает рубрику с заданным уровнем полноты.

Есть несколько моментов, связанных с доказанными утверждениями об алгоритме, которые необходимо отметить:

1. Алгоритм ПФБА может не найти точной формулы, а только формулу, полнота и точность которой близка к 100%.

2. Согласно следствию 3, ограничение на длину полученной формулы не зависит от параметра — веса важности точности относительно полноты. Алгоритм всегда может получить достаточно короткую формулу, вне зависимости от, если короткая точная формула 3. Согласно следствию 3, длина найденной формулы может быть существенно больше длины оптимальной формулы.

Эти свойства алгоритма являются побочным эффектом, связанным с тем, что основная задача алгоритма и цель его разработки — построение «хорошей» формулы для реальных задач. Обычно для реальных задач точной формулы, описывающей рубрику, не существует, либо точная формула имеет неприемлемо большую длину. Предположения, при которых верна теорема — в некотором смысле предельный случай реальной задачи. Аналитически исследовать реальную задачу не представляется возможным. Поэтому исследование алгоритма на реальных задачах проводилось экспериментально.

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

Если бы задача состояла в том, чтобы строить только точную формулу (в предположении существования таковой), то можно было бы обойтись более простым алгоритмом. А именно: на каждом шаге выбирать точный конъюнкт с максимальной дополняющей полнотой Отметим, что такой алгоритм является предельным случаем алгоритма ПФБА при.

Покажем на примерах конкретные значения параметров алгоритма ПФБА, которые обеспечивают получение формулы с заданной точностью.

Пусть существует точная формула U* длины n и требуется построить формулу, описывающую рубрику с полнотой и точностью не ниже 1.

Параметр можно установить равным нулю (не требуется высокая полнота каждого отдельного конъюнкта). В таблице 1 для различных значений n и 1 приведены значения параметра алгоритма ПФБА и количество шагов N (длина построенной формулы), которые обеспечивают заданные полноту и точность. Строки таблицы соответствуют различным значениям длины точной формулы n, а столбцы — уровням полноты/точности 1.

Таблица 1. Значения параметра построенной формулы) в зависимости от длины точной формулы n и заданного уровня построения формул ПФА В этом разделе мы исследуем алгоритм построения формул на реальных задачах классификации текстов. Исследование основано на общедоступных коллекциях текстов, размеченных экспертами по заданному результатами работы других методов классификации текстов. В результате сравнения можно утверждать, что алгоритм ПФА показывает качество классификации, сравнимое с результатами других алгоритмов. Кроме того, мы продемонстрируем формулы, полученные алгоритмом, и покажем, что построенные формулы действительно отражают смысл рубрики (а это как раз и являлось основной целью создания алгоритма).

Для одной из рубрик коллекции Reuters-21578 мы исследуем влияние различных параметров и модификаций алгоритма на вид получаемых формул и качество обучения. Мы покажем, что, в зависимости от требований к получаемому результату, алгоритм может создать описание рубрики различной степени подробности.

Исследование проводилось на следующих коллекциях документов:

1. Reuters-21578 — коллекция финансовых новостей агентства Reuters (на английском языке). 21578 документов, 135 рубрик.

2. РОМИП-2004 Legal — коллекция нормативных актов РФ из БД "Кодекс" (на русском языке). 60015 документов, 170 рубрик.

Подробное описание данных коллекций и экспериментов на них приводится в разделах 3.3.2 и 3.3.3 соответственно.

3.3.1 Описание программной реализации алгоритма Опишем вкратце технологии, на основе которых реализована программа построения формул на основе машинного обучения. Алгоритм реализован в виде программы на языке Java с использованием реляционной СУБД Oracle 9i и средств информационной системы УИС РОССИЯ [13, 12, 16].

Для проведения эксперимента коллекция документов загружается в УИС РОССИЯ стандартными средствами информационной системы. При этом в СУБД Oracle создаётся схема данных, содержащая информацию о каждом документе. Каждому документу присваивается уникальный идентификатор, и загружаются словарный и тематический индексы документов. Приведение слов к нормальной форме и выделение понятий осуществляется программой Автоматической Лингвистической Обработки Текстов [29, 30]. Словарный и тематический индекс, а также формальные атрибуты документов (в том числе приписанные рубрики) загружаются при помощи АРМ загрузки данных. Схема данных, используемая программой построения формул, представлена на рис. 2.

Рис. 2. Схема данных в СУБД Oracle9i, используемая программой построения формул.

Программа, реализующая алгоритм построения формул получает на вход 1. параметры подключения к СУБД Oracle;

2. номер рубрики, для которой нужно построить формулу;

3. параметры алгоритма построения формул.

Основные операции по обработке данных производятся средствами SQL в СУБД Oracle. Для построения формул используются таблицы conjuncts и cur_formula (см. рис. 2). Таблица conjuncts хранит список вычисленных конъюнктов и метрики качества конъюнктов. В таблице cur_formula формулу, в порядке их добавления в формулу. В процессе построения формулы значения метрик для этих таблиц обновляются при помощи операторов SQL и PL/SQL-процедур.

Для проводимых экспериментов время работы алгоритма составляло 3минут на одну рубрику.

3.3.2 Эксперименты на коллекции Reuters- Коллекция Reuters-21578 создана новостным агентством Рейтерс и предоставлена в свободный доступ для проведения исследований в области автоматической обработки текстов [70]. Коллекция состоит из документов — финансовых новостей агентства Рейтерс, выпущенных в году. Все документы отрубрицированы экспертами агентства Рейтерс и компании Carnegie Group по рубрикатору, состоящему из 135 рубрик.

Коллекция была адаптирована для тестирования методов машинного обучения Д. Льюисом [70] — документы переведены в удобный для автоматической обработки формат, а классификация документов — уточнена. Некоторым документам был присвоен статус "классификация не точна". Кроме того, множество документов было разбито на коллекцию, рекомендуемую для обучения (9603 документа, 74%) и коллекцию, рекомендуемую для тестирования метода машинного обучения ( документов, 26%), всего — 12902 документа. Такое разбиение называется ModApte split. Именно это разбиение рекомендуется использовать исследователям для тестирования своих методов и публикации результатов.

Использование такого разбиения способствует воспроизводимости публикуемых результатов.

Коллекция получила очень широкое распространение в научном сообществе. Для многих методов машинного обучения опубликованы результаты тестирования на коллекции Reuters-21578 ModApte split.

http://www.daviddlewis.com/resources/testcollections/reuters21578/.

Мы провели тестирование нашего метода построения формул на коллекции Reuters-21578 ModApte split [1]. Использовались следующие параметры алгоритма построения формул:

1. Шаг 1. В качестве векторного представления использовалось документах, были приведены к нормальной форме. Слова, встречающиеся менее чем в 5 документах, были усечены.

2. Шаг 2. Для набора конъюнктов перебирались все конъюнкции, состоящие из 100 слов с наибольшей F-мерой. Из списка полученных конъюнктов откидывались те, полнота которых ниже порога 20% или точность ниже порога 3%.

3. Шаг 3. Для основного теста использовались параметры формул количество дизъюнктов больше 20; prec90%;

recl>99%. Кроме того, для исследования поведения алгоритма при вариации параметров, использовались различные значения В таблице 2 приводятся сравнение результатов нашего метода с SVM (Support Vector Machines) [63, 78]. Результаты приведены для рубрик с количеством документов более 100 (столбец doc_cnt). В столбцах "Joachims P/R b.p." и "Dumais et.al. P/R b.p." приводятся результаты, опубликованные в [63] и [58] соответственно.

К сожалению, в указанных работах опубликованы результаты только для наиболее частотных 10 рубрик [57]. В столбце "Our SVM" мы приводим результаты нашей реализации тестов SVM (см. раздел 2.5.7.2, [6, 11]). В столбце "disj formulae" приводятся результаты работы нашего алгоритма построения формул. Использовались формулы вида (3.2).

Таблица 2. Результаты сравнения метода построения формул с SVM на рубриках ReutersРезультаты позволяют утверждать, что алгоритм построения формул показывает результаты классификации, сравнимые с SVM, хотя в среднем – несколько хуже.

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

Например:

Для некоторых рубрик формулы получились весьма длинными.

Например:

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

В то же время рубрики, которые сложно описать одним-двумя словами имеют менее четкие, менее формальные границы определения и описать принадлежность рубрике в виде булевской формулы сложно.

3.3.2.2 Анализ влияния различных параметров На примере рубрики "gold" рассмотрим, как некоторые параметры алгоритма влияют на качество описания рубрики. Мы применяли алгоритм построения формулы на рубрике "gold" с различными параметрами и вычисляли метрики качества рубрицирования — полноту и точность — на коллекции обучения и на коллекции тестирования.

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

Варьируя параметр "вес дополняющей полноты" в формуле (3.7) можно получать формулы различной длины:

Короткую формулу можно получить, задав следующие параметры формулы (3.7): ( w ap = 10, w ar = 15, w r = 2 ). Вес дополняющей полноты w ar большой, поэтому получается короткая формула:

TRAIN TRAIN TEST TEST

Попытки повышения полноты путем простого добавления конъюнктов ведут обычно к существенному уменьшению точности:

TRAIN TRAIN TEST TEST

В данном случае лемма "GOLD" дает сильное улучшение полноты (до 100%) предыдущей формулы, но при этом точность резко падает.

Можно добиться хороших результатов «набирая» дизъюнкциями частные случаи. Слово "gold" встречается в конъюнкции с другими словами.

Такую формулу можно получить, установив параметр "вес дополняющей полноты" малым ( w ap = 10, w ar = 0.1, w r = 2 ), и установив более жесткие условия на точность первого конъюнкта в формуле (3.6):

OR (/Лемма="OUNCE" AND /Лемма="GOLD") OR (/Лемма="GOLD" AND /Лемма="DEPOSIT") OR (/Лемма="GOLD" AND /Лемма="UNDERGROUND") OR (/Лемма="GRADE" AND /Лемма="GOLD") OR (/Лемма="SILVER" AND /Лемма="SHORT") OR (/Лемма="BULLION" AND /Лемма="GOLD")

TRAIN TRAIN TEST TEST

Можно сгруппировать элементы формулы так, чтобы формула имела «трёхуровневый» вид, аналогичный используемому экспертами:

TRAIN TRAIN TEST TEST

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

конъюнктов мы испытали возможность построения формул с отрицанием вида (3.3) и (3.4).

Построение формулы с отрицанием вида (3.3) позволяет получить более короткую (по количеству слов) формулу с высокими результатами:

TRAIN TRAIN TEST TEST

При этом имеет место большое различие результатов на коллекции обучения и коллекции тестирования.

Модификация алгоритма (3.4) дает формулу

TRAIN TRAIN TEST TEST

рубрицирования не сильно различаются на коллекции обучения и коллекции тестирования.

Полученная формула отражает известный факт [61] что эксперты, рубрицирующие документы Reuters не относят тематику "золотые резервы" к рубрике gold. Соответственно, некоторые конъюнкты, содержащие слово "reserves" вычитаются из описания рубрики.

3.3.3 Эксперименты на коллекции РОМИП- Российский семинар по Оценке Методов Информационного Поиска (РОМИП, http://romip.narod.ru) — открытая инициатива группы российских ученых для проведения независимой оценки методов информационного поиска, ориентированных на работу с русскоязычной информацией [51].

Инициатива имеет некоммерческий характер, однако в РОМИП принимают участие исследователи как из научных организаций, так и исследовательские подразделения ведущих российских компаний в области построения информационного поиска и формат семинара базируется на опыте аналогичных международных конференциях, таких как TREC (Text REtrieval Conference, http://trec.nist.gov), SUMMAC (TIPSTER Text Summarization http://www.itl.nist.gov/iaui/894.02/related_projects/tipster_summac/) и CLEF (Cross-Language Evaluation Forum, http://clef.iei.pi.cnr.it:2002/).

Первый семинар РОМИП проводился в 2003 году. Мы приняли участие результатов показало [14], что классические методы поиска TF*IDF показывают весьма высокие (один из лучших) результаты.

В 2004 году набор дорожек РОМИП был расширен. Мы приняли участие в трёх дорожках: дорожке поиска по web-коллекции, поиска по коллекции нормативных документов и дорожке тематической классификации нормативных документов.

В этом разделе мы опишем результаты, полученные на дорожке классификации текстов.

законодательства Российской Федерации из БД СПС «Кодекс». Рубрикатор иерархического рубрикатора нормативных документов. Для обучения процедуры классификации предлагается коллекция из 4496 документов, отрубрицированных по данному классификатору экспертами компании «Кодекс». Для тестирования предоставлены 55519 документов, для которых необходимо автоматически определить рубрики, к которым эти документы относятся. Для некоторых рубрик нет документов в коллекции обучения, всего рубрик с ненулевым количеством документов для обучения — 170.

Всего для дорожки классификации было прислано 9 прогонов от участников [47, 50, 46, 22, 7] (т.е. сравнивалось 9 различных алгоритмов классификации текстов), в том числе наши 3 прогона.

Мы подготовили три прогона. Два прогона основаны на алгоритме машинного обучения SVM (см. раздел 2.5.7). Третий прогон основан на алгоритме построения формул ПФА (раздел 3.1).

Целью первого прогона было получение «отправной точки» для дорожки классификации тестов. Первый прогон основан на широко распространённых технологиях — свободно распространяемой версии SVM, нормализации слов и формуле TF*IDF, с минимальными дополнениями.

Во втором прогоне мы попытались улучшить результаты «отправной точки» при помощи расширенного векторного представления документов.

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

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

3.3.3.1 Прогон 1: SVM по леммам Для прогона 1 мы использовали векторную модель документа, основанную на нормализованных словах. Все слова, встречающиеся в документе, были приведены к нормальной форме (лемме). Документ представляется множеством лемм, которые в него входят. Вес леммы вычисляется по формуле TF*IDF [14, 56]. Леммы, встречающиеся менее чем в четырёх документах, были усечены.

В результате получилось 21746 различных лемм и 1203087 пар леммадокумент для обучающей выборки из 4496 документов.

Для оптимизации параметров SVM применялся метод, описанный в разделе 2.5.7.2 и в [6, 11].

SVM применялась только для тех рубрик, для которых было не менее четырёх документов в коллекции для обучения.

3.3.3.2 Прогон 2: SVM по леммам+понятиям Для прогона 2 применялся метод SVM. Разница между прогоном 1 и прогоном 2 состоит лишь в использовании другого векторного представления документов.

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

Терминологический индекс документа строится на этапе предварительной обработки программой Автоматической Лингвистической Обработки Текстов (АЛОТ) [29, 30].

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

В расширенном индексе обучающей выборки документов получилось 29918 различных лемм/понятий и 1569958 пар «лемма/понятие»-документ.

3.3.3.3 Прогон 3: Метод машинного обучения, основанный на моделировании логики рубрикатора В прогоне 3 использовался метод построения формул ПФА со следующими параметрами (раздел 3.1):

1. Шаг 1. В качестве векторного представления использовалось терминологическое представление на основе понятий Тезауруса.

Термы, встречающиеся менее чем в четырёх документах, были 2. Шаг 2. Для набора конъюнктов перебирались все конъюнкции, состоящие из 50 термов с наибольшей F-мерой. Из списка полученных конъюнктов откидывались те, частотность которых 3. Шаг 3. Для основного теста использовались параметры формул количество дизъюнктов больше 50; prec90%;

3.3.3.4 Методика оценки результатов Оценка результатов производилась по 50 случайно отобранным классификации [7]. Для вычисления оценок результаты автоматической классификации сравнивались с оценками, проставленными экспертами ИС «Кодекс».

В качестве основной метрики качества рубрицирования используется макроусреднение).

проанализировали распределение частотности документов для выбранных рубрик по сравнению с другими рубриками. На рисунке 3 показан график зависимости количества документов для обучения от номера рубрики.

Рубрики, выбранные для оценки результатов (50 рубрик), выделены кругами.

График показывает, что выбранные рубрики распределены в целом равномерно на множестве всех рубрик.

Рис. 3 Зависимость количества документов для обучения от номера рубрики в логарифмической шкале (рубрики упорядочены по убыванию частотности).

Кругами выделены рубрики, выбранные для оценки.

3.3.3.5 Таблицы результатов На рис. 4 представлены результаты прогонов участников. Наши прогоны обозначены “svm_lem”, “svm_thes” и “formul” соответственно. Из рисунка видно, что прогон 3 — алгоритм построения формул — показывает лучшие результаты по F-мере и по полноте, хотя и проигрывает по точности SVM и ещё двум алгоритмам. SVM показывает лучшие результаты по точности, но сильно проигрывает по полноте. В результате — более низкие результаты по F-мере, чем у прогона 3 и ещё одного алгоритма. Можно также отметить, что использование расширенного терминологического представления документов повышает результаты SVM, но ненамного.

значения метрик (выражаемого F-мерой) от количества документов для обучения. Для этого множество рубрик было разбито на 4 части в зависимости от количества документов для обучения. Результаты показаны на рис. 5.

Можно отметить, что для метода SVM наблюдается резкая зависимость качества классификации от количества примеров для обучения — чем больше примеров, тем выше качество классификации. Для рубрик с частотностью выше 100 SVM показывает лучшие результаты. Для малочастотных рубрик качество классификации SVM падает до нуля (для рубрик с частотностью менее 4 SVM мы просто не запускали). Стоит отметить, что для некоторых алгоритмов наблюдается обратная зависимость.

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

Для алгоритма построения формул зависимость результатов от количества примеров выражена неярко. Однако для малочастотных рубрик (1-14 примеров) качество очень низкое. Возможно, это отчасти связано с тем, что на рубриках с частотностью менее 3 мы алгоритм построения формул не запускали (таких рубрик 5 из 17 в первом интервале).

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

Мы выбрали 6 рубрик с различными значениями количества документов для обучения. В таблице 3 представлены названия рубрик и правила, построенные алгоритмом (запросы к поисковой системе). Для каждой рубрики указано количество документов для обучения и значения Fмеры для следующих алгоритмов:

• алгоритм построения формул на множестве обучения (обозначается train (t));

• алгоритм построения формул на множестве тестирования — то есть полученный результат на дорожке классификации (formul (f));

• SVM с расширенным векторным представлением — наш прогон (svm_thes (s));

• наилучший результат, показанный участниками на этой рубрике (best (b)).

901800651 Основы государственного управления t 37% /Термин="ГОСУДАРСТВЕННЫЙ КОМИТЕТ ПО СТАНДАРТИЗАЦИИ" OR (/Термин="ТЕРРИТОРИАЛЬНОЕ УПРАВЛЕНИЕ" AND /Термин="УТВЕРДИТЬ (ОКОНЧАТЕЛЬНО УСТАНОВИТЬ, OR /Термин="ЛИЦЕНЗИРОВАНИЕ" OR /Термин="ФЕДЕРАЛЬНЫЙ ОРГАН ИСПОЛНИТЕЛЬНОЙ ВЛАСТИ" OR (/Термин="СТАТИСТИКА" AND /Термин="ИНФОРМАЦИЯ") OR (/Термин="ЗАМЕСТИТЕЛЬ МИНИСТРА" AND /Термин="КОНТРОЛЬ" AND /Термин="КОДЕКС") OR (/Термин="АННУЛИРОВАТЬ (ОБЪЯВИТЬ НЕДЕЙСТВ., ОТМЕНИТЬ)" AND /Термин="ПОЛОЖЕНИЕ (СВОД ПРАВИЛ, ЗАКОНОВ, AND /Термин="ПРАВИТЕЛЬСТВО РОССИИ") 9001375 Здравоохранение (208 документов) t 68% /Термин="МЕДИЦИНСКОЕ ОБОРУДОВАНИЕ" OR /Термин="МИНИСТЕРСТВО ЗДРАВООХРАНЕНИЯ" /Термин="ГОСУДАРСТВЕННЫЙ КОМИТЕТ ПО СТАТИСТИКЕ" 901716530 Право международных договоров (44 документа) t 64% /Термин="РАТИФИКАЦИЯ" OR (/Термин="ПОСТАНОВИТЬ" AND /Термин="СССР" AND /Термин="КРЕМЛЬ") OR /Термин="КОНСУЛЬСКАЯ КОНВЕНЦИЯ" /Термин="ЮРИДИЧЕСКАЯ ЭКСПЕРТИЗА" OR /Термин="МИНИСТР ЮСТИЦИИ" OR /Термин="ГЛАВНОЕ УПРАВЛЕНИЕ ИСПОЛНЕНИЯ НАКАЗАНИЙ" OR (/Термин="КЛАССНЫЙ ЧИН" AND /Термин="НОТАРИАТ") OR /Термин="ЭЛЕКТРОННО-ЦИФРОВАЯ ПОДПИСЬ" /Термин="ПРИЕМНАЯ СЕМЬЯ" OR /Термин="ПРИЕМНЫЙ РОДИТЕЛЬ" OR (/Термин="РОДИТЕЛЬСКОЕ ПОПЕЧЕНИЕ" AND /Термин="СВИДЕТЕЛЬСТВО О РОЖДЕНИИ") OR (/Термин="ПОСОБИЕ ПО БЕРЕМЕННОСТИ И РОДАМ" AND /Термин="УСЫНОВЛЕНИЕ" AND /Термин="РОЖДЕНИЕ РЕБЕНКА") Таблица 3. Описания рубрик, полученные алгоритмом построения формул. Для каждой рубрики указаны результаты различных алгоритмов (описание см. выше) На основе анализа таблицы 3 можно сделать следующие выводы:

1. Для большинства рубрик (строки 2, 3, 4, 5, то есть 4 из 6) алгоритм создаёт формулы, соответствующие названию рубрики.

2. Для этих рубрик алгоритм показывает результаты, близкие к 3. Качество результатов на множестве обучения и множестве 4. Для двух рубрик алгоритм построил «плохие» формулы:

5. На первой рубрике «Основы государственного управления»

алгоритм даёт длинную и довольно бессмысленную формулу.

Однако на этой рубрике ВСЕ примененные алгоритмы показали невысокий результат — максимум 38%.

6. На последней рубрике алгоритм показал плохие результаты (отставание от лидера 26% против 42%, переобучение 58% train / 26% test, формула не соответствует рубрике). Возможно, это связано с недостаточным количеством документов для обучения 7. Примечательно, что формальное «качество» формулы (низкое значение F-меры) кореллирует с плохой оценкой построенной 3.4 Выводы автоматической классификации текстов. Данный алгоритм строит описания рубрики в виде булевской формулы фиксированной структуры. В отличие от распространённых алгоритмов классификации текстов, используемое представление рубрики пригодно для анализа и модификации человеком и аналогично используемому экспертами при инженерном подходе.

На практике алгоритм может применяться для:

1. автоматической классификации текстов, аналогично другим алгоритмам машинного обучения;

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

4. создания наглядных описаний (аннотации) коллекции документов, документирования принципов отнесения документов к рубрикам (автоматизированного создания комментариев к рубрикаторам).

Проведено аналитическое и экспериментальное исследование алгоритма.

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

1. рубрика описывается короткой формулой заданной структуры;

2. документы отрубрицированы без ошибок;

3. заданы достаточно «жёсткие» параметры алгоритма.

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

Экспериментальное исследование алгоритма проводилось на двух коллекциях документов: широко известной англоязычной коллекции Reutersи русскоязычной коллекции нормативных документов РОМИП’2004.

Эксперименты показали высокую эффективность алгоритма и соответствие получаемых формул содержанию рубрики. В экспериментах на коллекции РОМИП’2004 алгоритм построения формул показал лучший результат, обогнав по качеству классификации SVM и алгоритмы других участников РОМИП’2004 — ещё 6 алгоритмов.

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