Автоматическое составление обзорных (сводных) рефератов новостных сюжетов С.Д.Тарасов Балтийский Государственный Технический Университет им. Д.Ф.Устинова «ВОЕНМЕХ»

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

Метод Луна [Luhn, 1958] G. Luhn. The Automatic Creation of Literature Abstracts (context). V s -значимость предложения; N important - число значимых слов в предложении (длина последовательности значимых слов); N all - полное число слов в предложении.

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

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

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

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

Алгоритм 2.Вводится отображение: которое ставит в соответствие каждому x i некоторый ранг f i

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

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

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

«Мама мыла раму» Обозн.Текст 0X0Мама мыла раму 1X1Первого октября мама мыла раму 2X2 Мама мыла раму 3X3Мама мыла раму тряпкой

«Мама мыла раму» МАМАМЫТЬОКТЯБРЬПЕРВОЕРАМАТРЯПКА 00,33 0,00 0,330,00 10,20 0,48 0,200,00 20,33 0,00 0,330,00 30,25 0,00 0,250,60

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

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

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

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

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

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

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

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

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

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

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

On-line сервис

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

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

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

Результаты оценки Тема кластераROUGE-1ROUGE-2ROUGE-3 1 В Гальском районе Абхазии неизвестные похитили главу районной избирательной комиссии Китай успешно запустил на орбиту навигационный спутник "Бэйдоу" Секретаршу из Coca-Cola признали виновной в краже секретов компании На севере Омской области выпал разноцветный снег

Сравнение с DUC DUC 2003DUC 2005 Построенная система ROUGE ROUGE

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

Будущая работа Улучшить алгоритм распознавания и разрешения анафор Добавить в систему синонимию. Провести более основательную оценку качества работы системы на основе большего количества ручных рефератов. Реализовать Multi-Topic MDS для новостных кластеров Исследовать алгоритм для реферирования кластеров другой тематики (например, описания фильмов)