АВТОМАТИЧЕСКОЕ ОБНОВЛЕНИЕ АННОТАЦИИ НОВОСТНОГО КЛАСТЕРА Автор: Алексеев Алексей

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

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

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

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

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

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

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

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

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

Автоматические ROUGE метрики - 2 Общая формула : A i – оцениваемая обзорная аннотация i- того кластера. M ij – ручные аннотации i того кластера. Ngram(D) – множество всех n- грамм из лемм соответствующего документа D. Пример : 1. Китай и Тайвань установили авиасообщение после 60- летнего перерыва. 2. После почти 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 : Мини - субмарина попала в ловушку под водой. 1. мини - субмарина... была затоплена... на дне моря маленькая... субмарина... затоплена... на глубине 625 футов. 3. мини - субмарина попала в ловушку... ниже уровня моря. 4. маленькая... субмарина... затоплена... на дне морском

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

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

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

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

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

Анализ результатов 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,s h ) – максимальная общая подстрока ( Longest Common Substring) :

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

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

The End