Проблемы автоматической рубрикации текстов Лукашевич Н.В. [email protected]

План презентации
Методы автоматической рубрикации текстов
Проблемы ручной и автоматической рубрикации
Наши исследования
Лаборатория анализа информационных ресурсов НИВЦ МГУ
АНО Центр информационных исследований
УИС РОССИЯ (www.cir.ru)

Рубрикация текстов
Классификация/рубрикация информации - отнесение порции информации к одной или нескольким категориям из конечного множества рубрик.
Применение:
Навигация по коллекции документов
Поиск информации
Замена сложного запроса
Иерархическое упорядочение знаний предметной области
Анализ распределения документов по тематике
Фильтрация потока текстов:
Тематический сбор новостей
Персонализированная фильтация потока текстов
Фильтрация спама
Тематический сбор информации из интернет

Примеры рубрикаторов
Каталог Интернет-сайтов: Open Directory Project – dmoz.org
4,830,584 sites, 75,151 editors, over 590,000 categories
Сетевая структура, ссылки между рубриками

Каталог Яндекс - Фасетная классификация
Тематическая
Иерархический классификатор, имеет порядка 600 значений и описывает предметную область интернет-ресурса
Регион
230 географических областей. Определяется географическим расположением представляемого объекта, сферой управления и влияния, потенциальной аудиторией информации или информационным содержанием ресурса
Жанр
художественная литература; научно-техническая литература; научно-популярная литература; нормативные документы; советы; публицистика
Источник информации
Официальный, СМИ, Неформальный, Персональный Анонимный
Адресат информации
Партнеры, Инвесторы, Потребители, Коллеги
Сектор экономики
Государственный, Коммерческий, Некоммерческий

Рубрикатор нормативно-правовых актов
Президентский классификатор (Указ №511 15.03.2000)
Иерархия рубрик - 1168 рубрик
Все НПА рубрицируются экспертами в обязательном порядке

Коллекция и рубрикатор Reuters для автоматического рубрицирования
Более 21 тысячи информационных сообщений из области биржевой торговли и слияния предприятий
Массив разделен на две части: документы для обучения, документы для тестирования
Большинство текстов имеют рубрики, проставленные людьми
Основные рубрики: 135 без иерархии
Примеры рубрик: Золото (товар), Свинец (товар), Кофе и др. товары, Торговля
Средняя длина текста - 133 слова
156 публикаций по автоматическому рубрицировнаю на сайте CiteCeer

Методы рубрицирования текстов
Ручное рубрицирование
Полуавтоматическое
Автоматическое
Инженерный подход (=методы, основанные на знаниях, экспертные методы)
Методы машинного обучения

Методы оценки эффективности автоматического рубрицирования
Основа: сравнение результатов автоматического и ручного рубрицирования

Ручное рубрицирование
Высокая точность рубрицирования
Обычно процент документов, в которых проставлена явно неправильная рубрика, чрезвычайно мал
Низкая полнота рубрицирования
одна-две основных рубрики, характеризующие основное содержание документа, хотя документ может быть отнесен и к ряду других рубрик.
В результате получается, что
Процент совпадения результатов рубрицирования различных экспертов весьма низкий - 60 %.
В результате похожие документы могут получить достаточно разные наборы рубрик
Непоследовательность ручного рубрицирования
Низкая скорость обработки документов

Субъективизм экспертов
Совпадение при ручной рубрикации
между разными экспертами 60%

Инженерный подход
Основное предположение: рубрикатор создается осмысленно, содержание рубрики можно выразить ограниченным количеством понятий в виде формулы
Эксперты описывают смысл рубрики в виде булевских выражений, правил продукции
Construe system (Hayes)
Reuter news story
674 рубрики: 135 тематических рубрик + география…
4 человеко-года
94 % полноты и 84 % точности на 723 текстах

Reuters: пример описания рубрики
if (wheat & farm) or
(wheat & commodity) or (bushels & export) or
(wheat & tonnes) or
(wheat & winter and (¬ soft))
then
WHEAT
else
(not WHEAT)

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

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

Ошибки: появление лишних рубрик (2)
Лексическая многозначность - текст может быть отнесен не к той рубрике из-за того, что некоторые слова, сопоставленные рубрике, в конкретном тексте употреблены в таком значении, которое не соответствует данной рубрике.
МОРСКИЕ СУДА; РЕШЕНИЕ СУДА; СТАРИННОЕ ЗДАНИЕ СУДА
ПРОИЗВОДСТВО ТОВАРОВ; ПРОИЗВОДСТВО ПО УГОЛОВНОМУ ДЕЛУ

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

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

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

Положительные и отрицательные примеры: как лучше отделить

Векторная модель: основные этапы
Задача: преобразовать множество текстов в векторы пространства Rn
Пословная модель – bag of words
Удаление стоп-слов (предлоги, союзы…),
которые заданы списком
Приведение к нормальной морфологической форме (stemming, лемматизация – приведение к словарной форме)
Определение весов слов
Построение вектора слов документа

Вычисление весов слов
Частота встречаемости слова в документе
Количество документов коллекции, содержащих данное слово
Длина документа, средняя длина документов коллекции
=> формула TF*IDF
Расположение слова в тексте, заголовках?

TF*IDF
Наиболее общепринятый способ вычисления веса терма: tf • idf
tf – частотность терма в документе (term frequency)
idf – величина, обратная к количеству документов, содержащих терм (inverse document frequency)
tfD(t) = freqD(t)
idf(t) = log( |c|/df(t) )

Формула tf•idf [Okapi BM25 – cir.ru]
Stephen E. Robertson, Steve Walker, Susan Jones, Micheline Hancock-Beaulieu, and Mike Gatford. Okapi at TREC-3. In Proceedings of the Third Text REtrieval Conference (TREC 1994). Gaithersburg, USA, November 1994.

Отсечение по центрам тяжести

Отсечение по ближайшим соседям
(kNN)

Оптимальный линейный сепаратор
SVM (Support Vector Machines)
Максимизация
расстояния между
двумя
параллельными
поддерживающими
плоскостями

Reuters-21578, применяем SVM
[1] Joachims T. Text Categorization with Support Vector Machines: Learning with Many Relevant
Features. // Proceedings of ECML-98, 10th European Conference on Machine Learning — 1998.
[2] Dumais S., Platt J, Heckerman D., Sahami M. Inductive learning algorithms and representations
for text categorization. // In Proc. Int. Conf. on Inform. and Knowledge Manage., 1998.

An Analysis of the Relative Hardness of
Reuters-21578 Subsets
Franca Debole and Fabrizio Sebastiani. //In proc. of LREC-04, 4th int. conf. on Language Resources and Evaluation, pp.971--974, Lisbon, PT, 2004.
90 из 135 категорий имеют хотя бы один положительный пример для обучения и для тестирования
Лучший результат на R(90): в среднем 50% F-меры

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

Множество примеров отсутствует и не может быть создано в короткое время
Российский социологический архив (www.socialpolicy.ru)
Данные соцопросов разных организаций
350 рубрик, 4 уровня иерархии
Новый проект => отсутствие примеров

Множество примеров существует,
но отсутствовали требования к качеству
Международное научное сообщество RePec (www.repec.org (www.repec.org), SocioNet (www.socionet.ru)
Архив исследовательских материалов по экономике и социологии
Рубрикатор: Journal of Economic Literature Classification System (JEL)
Более 700 рубрик
Автор сам приписывает рубрики к своей работе

Множество примеров противоречиво и недостаточно для
большинства рубрик (очень большие классификаторы)
Российские правовые документы
Президентский классификатор (Указ №511 15.03.2000) - 1168 рубрик
Множество примеров – 10,000 документов классифицированных вручную
Только для 47 рубрик – более чем 100 док.,
только для 200 рубрик – более чем 20 док.
Inconsistency: мало отличающиеся документы имеют разные наборы рубрик

Мало отличающиеся документы
имеют разные наборы рубрик: как обучаться?

Множество примеров для обучения
из другой коллекции
Примеры: документы федерального уровня Проблема: рубрицирование 600,000 региональных документов
Тот же рубрикатор
Похожие документы, похожая проблема
НО!!!
Стандартный метод SVM-light, обученный на федеральных документах не приписывает ни одной рубрики для 50% документов

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

Основные направления исследований по автоматической рубрикации
Лаборатория (ЛАИР) НИВЦ МГУ
УИС РОССИЯ (www.cir.ru) - 1 млн. современных российских документов
Инженерный подход – использование знаний Общественно-политического тезауруса
Машинное обучение - автоматическое формирование формул
Смешанные подходы
Современные техники: bagging, boosting

Технологии автоматической классификации
на основе УИС РОССИЯ
По общему тематическому правовому классификатору
Центральной избирательной комиссии РФ
(450 рубрик, 4 уровня)
По терминам верхнего уровня тезауруса Исследовательской службы Конгресса США (80 рубрик)
По правовому рубрикатору Центра информационных
исследований (180 рубрик, 3 уровня)
По Классификатору правовых актов РФ
(Указ Президента РФ N511 от 15 марта 2000 г., 1169 рубрик)
По Классификатору НПП «Гарант» (3200 рубрик)
Journal of Economic Literature Classification System (JEL), более 700 рубрик

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

Схема описания рубрики
Рубрика
Альтернатива1
Альтернатива2
У11
У12
У13
У21
Условие22
ИЛИ
И
И
И
+
+
+
-
ИЛИ
ИЛИ

Представление смысла рубрики
опорными понятиями

Расширенное представление рубрики понятиями тезауруса

Алгоритм строит формулы вида:
где — множество документов, содержащих некоторое понятие тезауруса. Конъюнкции, составляющие формулу, имеют длину Ji от 1 до 3.
Пример (рубрика «Право международных договоров»)
Метод машинного обучения, основанный на моделировании логики рубрикатора
/Термин="РАТИФИКАЦИЯ"
OR (/Термин="ПОСТАНОВИТЬ"
AND /Термин="СССР"
AND /Термин="КРЕМЛЬ")
OR /Термин="КОНСУЛЬСКАЯ КОНВЕНЦИЯ"

РОМИП’2007
дорожка классификации web-страниц
Рубрикатор: DMOZ, 247 рубрик 2го уровня Top/World/Russian/*/*
Коллекция обучения «DMOZ»
300 000 документов с 2100 сайтов
Русскоязычные сайты, упоминающиеся в категориях второго уровня, на страницах которых не было явного запрещения копирования содержимого этих сайтов. Для снижения размеров коллекции до разумных пределов для каждого сайта в коллекцию включалось не более 500 страниц, полученных обходом в ширину, начиная со стартовой страницы.
Собрано и предоставлено компанией Рамблер в 2004 году.
Коллекция тестирования «BY.web»
1 500 000 документов c 19 000 сайтов
построена компанией Яндекс как выборка из страниц домена .by, присутствовавших в индексе поисковой системы Яндекс по состоянию на май 2007 года. С каждого известного сайта из домена .by брались все страницы на глубину 3 ссылки от стартовой.

Машинное обучение: метод ПФА
Рубрика 135 «Боевые искусства»
Recall = 0.52 Precision = 0.88 FMeasure = 0.82
[Тип = в дереве | Имя = БОЕВЫЕ ИСКУССТВА ]
Recall = 0.82 Precision = 0.98 FMeasure = 0.96
( [Тип = лемма | Имя = КАРАТЭ ])
OR ( { [Тип = в тексте | Имя = ХОККЕЙНЫЙ КЛУБ ]
OR [Тип = в дереве | Имя = ОХРАННОЕ ПРЕДПРИЯТИЕ ]}
AND
[Тип = в дереве | Имя = БЕДСТВИЕ ])
OR ( { [Тип = в тексте | Имя = КУЛЬТУРА ]
OR [Тип = в тексте | Имя = СЕВЕРО-ЗАПАДНАЯ ЧАСТЬ ]}
AND
[Тип = в тексте | Имя = ОДЕЖДА ]
AND
[Тип = в дереве | Имя = ВЕРОВАТЬ ])
OR ( { [Тип = в тексте | Имя = МЕДИЦИНСКОЕ УЧРЕЖДЕНИЕ ]
OR [Тип = в тексте | Имя = КРЫЛАТСКОЕ ] }
AND [Тип = в дереве | Имя = ВОСТОЧНЫЕ ЕДИНОБОРСТВА ])
OR ( [Тип = в тексте | Имя = МАСЛЕНИЦА ])
OR ( [Тип = лемма | Имя = ДЗЭНИН ])
OR ( [Тип = в тексте | Имя = САМООБОРОНА ]
AND [Тип = в дереве | Имя = ИСТОРИЧЕСКИЕ НАУКИ ])

Инженерный подход (8 чел*час): пример простого описания рубрики
Рубрика 135 «Боевые искусства» (F1-мера [OR] = 0.97, R=0.98, P= 0.96)
Опорное булевское выражение состоит из одного понятия
БОЕВЫЕ ИСКУССТВА (Е)
с меткой «Е» полного расширения по тезаурусу.
В состав расширенного булевского выражения входят помимо исходного следующие понятия:
АЙКИДО, ДЖИУ-ДЖИТСУ, ДЗЮДО, КАРАТЭ, САМБО, ДЗЮДОИСТ, КАРАТИСТ, САМБИСТ.
Понятия тезауруса, соответствующие людям (ДЗЮДОИСТ, КАРАТИСТ, САМБИСТ) входят в рубрику с пометкой подтверждения, поскольку появление соответствующих слов в тексте еще не означает, что текст посвящен боевым искусствам

РОМИП2007: классификация веб-страниц