Автоматическое составление обзорных (сводных) рефератов новостных сюжетов

Автоматизация реферирования текстовой информации
SDS (Однодокументное реферирование)
MDS (Многодокументное реферирование) – как минимум с 2001 года
Конференции: TREC, DUC, TSC.
Практические реализации:
http://news.google.ru/
http://news.yandex.ru/
http://www.newsblaster.com/

Метод Луна
[Luhn, 1958] G. Luhn. The Automatic Creation of Literature Abstracts (context). http://citeseer.ist.psu.edu/context/74679/0
Vs -значимость предложения;
Nimportant - число значимых слов в предложении (длина последовательности значимых слов);
Nall - полное число слов в предложении.

Manifold Ranking Algorithm
Может быть использован для ранжирования любых информационных примитивов: текстов, предложений, изображений, звуков. В этом случае любой вид информации должен быть представлен в векторном пространстве.
В задачах ранжирования результатов информационного поиска «отправной точкой» алгоритма является запрос, и ранг предложений определяется как мера их «информационной близости» запросу.
В задаче автоматического реферирования «отправной точкой» алгоритма можно считать «тему» кластера.

Manifold Ranking Algorithm
Позволяет описать связную структуру текста
Для описания связной структуры текста используется математический аппарат векторов и матриц.

Manifold Ranking Algorithm
Вычисление ранга каждого предложения (Информационная значимость)
Применение алгоритма отсечения предложений, наиболее похожих на те, что уже попали в обзорный реферат (Информационная новизна)

Алгоритм
Задается набор структур:
x0 – предложение, которое формулирует тему кластера

Алгоритм
Вводится отображение:
которое ставит в соответствие каждому xi некоторый ранг fi

Алгоритм
Задается вектор:
Согласно алгоритму y0=1, т.к. x0– тема кластера (в задачах информационного поиска соответствует фразе поискового запроса), и yi=0 для всех остальных предложений (1

Алгоритм
Каждое предложение (объект) представляется в векторном пространстве следующим образом:
где tfk - стандартная TF_ISF мера относительной важности терма tk

Алгоритм
Набор предложений представляет собой взвешенный граф с матрицей весов W. Для каждой пары xi и xj предложений вычисляется вес их «лексической близости» при помощи стандартной евклидовы меры:

«Мама мыла раму»

«Мама мыла раму»

«Мама мыла раму»
Матрица весов в этом случае будет выглядеть:

«Мама мыла раму»
Граф связности текста:

Алгоритм
Матрица весов подвергается симметричной нормализации:

Алгоритм
F вычисляется как результат итеративного процесса: :

«Мама мыла раму»
Расчет вектора F:

«Мама мыла раму»
Граф связности текста:

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

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

Инициализируются два множества A и B. Все предложения помещаются в B. Для каждого предложения B текущий ранг принимается равным fi.
Предложения множества B сортируются в соответствии с их текущим рангом в порядке убывания.
Алгоритм усечения сходных предложений

Полагая, что предложение xi имеет наивысший ранг, оно перемещается из B в A. Ранг оставшихся в B предложений рассчитывается как:
Алгоритм усечения сходных предложений
- фактор усечения сходных предложений

Реализация
Web-интерфейс
PHP
Расширение php_math
MTL
AOT
Подбор параметров
http://openthesaurus.ru/manifold/

On-line сервис

On-line сервис

Исходные данные
В качестве исходных данных для оценки работы алгоритма был взят набор кластеров новостной тематики, любезно предоставленный НИВЦ МГУ.

Пример аннотации
Для кластера «На севере Омской области выпал разноцветный снег» содержащего 8 документов (всего 61 предложение) был получен обзорный реферат из 4 предложений:
«Представители властей заявили, что если вдруг выяснится, что разноцветный снег в Сибири выпал из-за промышленных выбросов, нарушителей привлекут к уголовной ответственности. Пока специалисты только говорят, что аномальные осадки не опасны для здоровья. Кроме того, необычный снег выпал в Томской и Тюменской областях. Вчера были обнародованы первые лабораторные исследования выпавшего 31 января в Омской области желто-оранжевого снега».

Оценка
На основе ручных аннотаций, любезно предоставленных НИВЦ МГУ проведена оценка качества системы реферирования при помощи меры ROUGE.

Результаты оценки

Сравнение с DUC

Итоги
Алгоритм реализован в виде “on-line” Web-сервиса. Сводные рефераты могут быть получены «на лету»
Алгоритм апробирован на русскоязычных новостных кластерах
Произведена оценка качества работы алгоритма по мере ROUGE. Выполнено сравнение результатов с DUC
Сформулирован список возможных направлений по улучшению качества аннотирования