Автоматическое обновление аннотации новостного кластера

Определение новизны информации
Определение новизны информации – важная и нерешённая задача.
Проблема в общем виде:
поток информации и пользователь
в некоторый момент времени есть известная информация (известная пользователю)
Задача: извлечение новой информации из потока и предъявление пользователю
*

Конкретная задача
Новостной кластер – набор документов по поводу некоторого события.
Аннотация – краткое описание события, составленное из предложений документов кластера.
В некоторый момент времени в кластер приходит ещё N документов.
Вопросы:
Что нового произошло?
Как должна измениться аннотация?
Как новое отобразить в аннотации?
Какие предложения аннотации должны быть заменены?
*

Конференция TAC
Создана при поддержке и спонсируется Национальным Институтом Стандартов и Технологий (NIST) и Департаментом Защиты США.
Проект был запущен в 2008 как продолжение конференции DUC.
Участники – более 30 команд со всего мира.
Назначение: поддержка исследований в области извлечения информации при помощи обеспечения инфраструктуры, необходимой для крупномасштабной оценки методов извлечения информации.
*

Постановка задачи «Обновление аннотации» в TAC - 1
Данная задача впервые была поставлена в TAC в 2008 году и продолжает развиваться.
Постановка задачи: Даны два упорядоченных и связанных множества документов (по 10 документов в каждом) и запрос пользователя.
Задача: Сделать две аннотации, размером не более 100 слов, такие что:
Первая аннотация покрывает первое множество документов.
Вторая аннотация покрывает второе множество документов, при условии что пользователь уже ознакомлен с документами первого множества.
*

Постановка задачи «Обновление аннотации» в TAC - 2
То есть по сути задача делилась на две основные и формально независимые подзадачи:
Создание аннотации набора документов (Initial Summary)
Создание обновлённой аннотации (Update Summary)
Некоторые детали:
Аннотации свыше 100 символов обрезались.
Документы упорядочены по времени.
Документы релевантные запросу пользователя.
Независимая оценка аннотаций.
*

Входные данные для задачи «Обновление аннотации» в TAC - 1
AQUAINT-2 collection
New York Times
Associated Press
Los Angeles Times-Washington Post News Service
Xinhua News Agency
Agence France Presse
Central News Agency (Taiwan)
…
2.5 Гб текста – около 900.000 документов.
Октябрь 2004 – Март 2006.
Все документы на английском языке.
Данная коллекция идеально подходит для поставленной задачи.
*

Входные данные для задачи «Обновление аннотации» в TAC - 2
Специалисты NIST сделали 48 различных топиков.
Каждому топику было отобрано по 20 релевантных документов.
Документы были хронологически упорядочены и разделены на 2 множества, так что документы множества Б следовали за A хронологически.
К каждому топику был составлен запрос, ответ на который содержался в предложенных документах.
Запросы могли содержать вопросительные предложения и избыточную информацию.
*

Оценка результатов задачи «Обновление аннотации» в TAC
Специалисты NIST сделали вручную по 4 «идеальных» аннотации к каждому топику.
Применялось несколько различных и независимых способов оценки результатов:
Автоматические ROUGE метрики.
Оценка содержания аннотации методом «Пирамиды».
Ручная оценка полноты, связности и читабельности.
Все системы были независимо оценены каждым из представленных способов.
*

Автоматические ROUGE метрики - 1
ROUGE или Recall-Oriented Understudy for Gisting Evaluation – набор метрик и комплекс программ для оценки автоматического аннотирования и машинного перевода текстов.
Основная идея – сравнение генерированного текста с “эталонным”, сделанным человеком.
Существуют различные формы метрики, сравнивающие:
n-граммы (ROUGE-N)
минимальные общие подстроки (ROUGE-L и ROUGE-W)
монограммы и биграммы (ROUGE-1 and ROUGE-2)
*

Автоматические ROUGE метрики - 2
Общая формула:
Ai – оцениваемая обзорная аннотация i-того кластера.
Mij – ручные аннотации i‑того кластера.
Ngram(D) – множество всех n-грамм из лемм соответствующего документа D.
Пример:
Китай и Тайвань установили авиасообщение после 60-летнего перерыва.
После почти 60-летнего перерыва открылось регулярное авиасообщение между Тайванем и материковым Китаем.
Rouge-1 = 7/12 = 0.58(3)
*

Метод «Пирамиды» - 1 (Pyramid Evaluation)
Разработан в 2005 году Колумбийским университетом.
Эксперты выделяют из «эталонных» аннотаций «информационные единицы» - Summary Content Units (SCUs).
Каждый SCU получает вес, равный количеству «эталонных» аннотаций, где она встречалась.
Оценка – суммарный вес входящих SCU.
Неоднократное вхождение SCU в автоматическую аннотацию не поощряется.
*

Метод «Пирамиды» - 2 (Pyramid Evaluation)
Итоговый результат:
[Суммарный вес найденных SCU]
[ Суммарный вес всех определённых SCU для данного топика]
Пример:
SCU: Мини-субмарина попала в ловушку под водой.
мини-субмарина... была затоплена... на дне моря...
маленькая... субмарина... затоплена... на глубине 625 футов.
мини-субмарина попала в ловушку... ниже уровня моря.
маленькая... субмарина... затоплена... на дне морском...
*

Ручная оценка результатов на TAC
Каждая автоматическая аннотация была прочитана несколькими экспертами NIST.
Две оценки:
- Содержание
- Читабельность
Пятибалльная система оценка – от 1 до 5.
Результаты – заметный разрыв между автоматическими и «эталонными» аннотациями.
Данная система оценки наиболее важна для нас, так как цель автоматического реферирования – человек, а не компьютер.
*

Сравнение методов оценки
ROUGE:
+ Малое участие человека, лёгкость применения
- Отсутствие оценки читабельности, результат не всегда идеален с точки зрения человека
Метод «Пирамиды»:
+ Наиболее объективная оценка содержания аннотации
- Отсутствие оценки читабельности, большое участие человека
Ручная оценка:
+ Оценка «пользователем», лучшая оценка читабельности
- Огромное участие человека
*

Результаты TAC 2008 – 1
В целом не очень высокие результаты – заметный разрыв между «эталонными» и автоматическими аннотациями.
Рассматриваем ручную оценку результатов.
Лучший результат по содержанию:
2.7917 - для 1-ой аннотации, 2.6042 – для второй.
Лучший результат по читабельности:
3.0000 – для 1-ой аннотации, 3.2083 – для второй.
(не учитывая «базовую» аннотацию NIST)
Худшие результаты ~ 1.2000.
*

Результаты TAC 2008 – 2
Худшие результаты ~ 1.2000.
Результаты по содержанию аннотации
*

Результаты TAC 2008 – 3
Худшие результаты ~ 1.2000.
Результаты по читабельности аннотации
*

Анализ результатов TAC 2008
Одна из лучших – система канадского университета Монтреаль для франкоговорящих. (Universit´e de Montreal)
Стабильно высокие результаты для содержания аннотации и читабельности.
Третье участие данной команды в DUC-TAC конференциях.
Базовый алгоритм:
«Максимальная граничная значимость»
Maximal Marginal Relevance (MMR)
*

Maximal Marginal Relevance (MMR) - 1
Итеративный метод.
На каждой итерации производится ранжирование предложений-кандидатов.
В итоговую аннотацию отбирается одно с самым высоким рангом.
Давно используется для запрос - ориентированного аннотирования.
Модификации алгоритма для «базовой» и «обновлённой» аннотаций.
*

Maximal Marginal Relevance (MMR) - 2
Для «базовой» аннотации:
Пусть:
Q – запрос к системе.
S – множество предложений кандидатов.
s – рассматриваемое предложение кандидат.
Е – множество выбранных предложений.
Тогда:
*

Maximal Marginal Relevance (MMR) - 3
Для «обновлённой» аннотации:
Пусть:
Q – запрос к системе.
s – рассматриваемое предложение кандидат.
H – рассмотренные документы (история).
f(H) –> 0 при увеличении H.
Тогда:
*

Maximal Marginal Relevance (MMR) - 4
Sim1(s,Q) – стандартная косинусовая мера угла между векторами:
Sim2(s,sh) – максимальная общая подстрока (Longest Common Substring):
*

Постпроцессинг (Post-processing)
После отбора предложений производится улучшение связности и читаемости аннотации:
Замена аббревиатур
Приведение номеров и дат к стандартному виду
Замена временных ссылок:
«в конце следующего года» ? «в конце 2010»
Замена двусмысленностей и дискурсивных форм:
«Но, это значит...» ? «Это значит...»
Конечная сортировка предложений
*

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