1 Автоматическое составление обзорных рефератов новостных сюжетов RCDL октября 2007 г. к.т.н. Абрамова Н.Н., аспирант Абрамов В.Е. ФГУП «НИЦИ при МИД России»

2 Предлагается рассмотреть 1. Проблемы реферирования набора документов. 2. Метод автоматического составления обзорных рефератов документов, относящихся к определенному новостному сюжету. 3. Вопросы связности текста в обзорном реферате. 4. Примеры практического применения метода. 5. Оценка качества реферирования. 6. Выводы и направления дальнейших исследований.

3 Проблемы реферирования набора документов Составление обзорных рефератов (Multi-Document Summarization) относится к новым сферам применения автоматического реферирования, в отличие от классического реферирования отдельных документов, известного с конца 50-х годов прошлого века. Эти вопросы рассматриваются на конференциях по проблемам автоматического аннотирования DUC (Document Understanding Conference) и текстового реферирования TSC (Text Summarization Challenge). Реферирование кластера новостных сообщений в рамках задачи слежения за потоком сообщений (TDT- topic detection and tracking). В Колумбийском университете (США) разработана система Newsblaster для поиска и обработки новостей, в которой есть возможность аннотирования новостной информации. В Колумбийском университете в этой области работают John Chen, Ani Nenkova, Regina Barzilay, David Evans и др. В Чикагском университете – Dragomir Radev, Sasha Blair- Goldensohn, Zhu Zhang.

4 Основные цели и задачи Цель исследования - разработка нового формата представления новостных сюжетов в системе Яндекс.Новости в виде обзора, текст которого разбит на блоки, снабженные ссылками на полные тексты сообщений, в которых имеется близкая по смыслу информация. По данным Информационного бюллетеня Яндекса "СМИ российского интернета" (осень 2006 года) 20% от объема информационных сообщений составляют новости, копируемые одними изданиями у других. Часто сообщения содержат перефразированный текст или являются рефератами более развернутых сообщений. Поэтому нецелесообразно представлять пользователям для просмотра все сообщения сюжета в виде последовательного списка, никак не связанных между собой сообщений.

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

6 Тема и подтема новостного сюжета Тема: Расширение НАТО и планы военного строительства в России. Подтемы : Реакция России на неприсоединение к ДОВСЕ стран-новичков НАТО. Встреча Совета Россия-НАТО на уровне министров иностранных дел. Соглашение между Россией и НАТО "О статусе сил". Соглашение между Россией и НАТО о сотрудничестве по борьбе с международным терроризмом. Защита воздушного пространства России в связи с приближением к российским границам натовской инфраструктуры. Выход в море флагмана Северного флота "Петр Великий".

7 Основные задачи, требующие решения при автоматическом составлении обзоров Выделить подтемы в каждом новостном сообщении.Подтемы определяются выделенными из текста документа наименованиями понятий, представляемыми частотными словосочетаниями. Отождествить близкие по смыслу подтемы из разных сообщений сюжета. Выбрать фрагменты текста, выражающие все отобранные подтемы. Предложения, несущие наибольшую смысловую нагрузку, определяются по максимальной сумме частот входящих в них значимых словосочетаний. Представить информацию в виде обзора со ссылками на списки сообщений, в которых рассматривается та или иная подтема.

8 Метод обзорного реферирования Этап 1. Морфологический анализ Этап 2. Автоматическое выделение словосочетаний и формирование частотных словарей в каждом документе кластера. Этап 3. Определение значимых предложений в каждом документе кластера. Этап 4. Формирование общего списка тем кластера. Этап 5. Построение итогового обзорного реферата.

9 Принципы выделения словосочетаний из русских текстов 1. Слова в словосочетании располагаются контактно. 2. Словосочетание не начинается с предлогов или союзов и ими не оканчивается. 3. Границами словосочетаний являются: знаки препинания (исключая запятую между однородными членами и точку после инициалов, цифр и сокращений и в интернет-адресах); скобки разного рода (круглые, квадратные, косые, фигурные); глаголы и подчинительные союзы; существительные или прилагательные в именительном или винительном падеже без предшествующего предлога. 4. Имена и фамилии, географические названия, названия организаций, партий и т.п. должны распознаваться в текстах с помощью специальных словарей.

Алгоритм выделения именных словосочетаний 10 Шаблон. Точка, стоящая после инициалов, сокращений, интернет-адресов и цифр, не считалась границей предложения. На основе принципов выделения словосочетаний для русского языка. С помощью словаря стоп-слов (служебные слова, местоимения, имена, отчества и т.д.). Ограничение на длину словосочетания до 10 слов. Оставшиеся цепочки слов являются искомыми словосочетаниями. Среди них также могут быть отдельные слова.

Примеры работы алгоритма выделения словосочетаний Текст. Большинство россиян живут за чертой бедности, тогда как мировой опыт говорит о том, что рента - главный источник национального богатства стран, обеспеченных природными ресурсами, отметил глава Счетной палаты. Выделенные словосочетания

12 Формирование поисковых образов словосочетаний (ПОС) ПОС это последовательность словоизменительных основ слов, входящих в словосочетание, с сохранением порядка следования. ПОС необходим при формировании частотного словаря для отождествления словосочетаний, отличающихся только формами слов. Фрагмент частотного словаря Структура: ПОС словосочетания#текст словосочетания#частота большинств россиян#большинство россиян#1 большинств#большинство#1 бюджет государств сумм млрд доллар#бюджет государства на сумму до 8 млрд долларов#1 бюджет государств сумм млрд#бюджет государства на сумму до 8 млрд#1 бюджет государств сумм#бюджет государства на сумму#1 бюджет государств#бюджет государства#1 бюджет#бюджет#4

13 Определение значимых предложений в каждом документе кластера

14 Критерии отбора наиболее значимых предложений в каждом документе кластера

15 Распознавание синтаксических анафорических связей Выбор предложения с весом, удовлетворяющим критерию отбора Выделение начальной части предложения (до первой запятой) [Нет запятых в оставшейся части предложения] Выбор предложения целиком [Есть запятые в оставшейся части] [Найдены анафорические местоимения][Не найдены анафорические местоимения] Удаление вводных слов и оборотов Занесение предшествующего предложения в массив предложений- кандидатов для включения в реферат

16 Формирование общего списка тем кластера Предложения, выбранные из каждого документа кластера, объединялись в один список с сохранением информации о номере документа. С помощью тезауруса выявлялись близкие по смыслу предложения, выделенные из разных сообщений кластера. Во всех предложениях, относящихся к списку тем кластера, проводился поиск слов и словосочетаний из тезауруса, и найденные словарные единицы заменялись на заглавные дескрипторы тезауруса. Словарные статьи в тезаурусе отсортированы в алфавитном порядке ПОС-ов и по количеству основ слов в них. Фрагмент тезауруса: балансировани на гран войн#холодн войн билет на одн поездк#разов билет борьб за отмен рабств#аболиционизм возрастн состав рабоч сил#возрастн дифференциаци населени встреч на высш уровн#встреч в верх

Построение итогового обзорного реферата Установлен параметр объема реферата (по умолчанию 3 кб). После формирования окончательного списка предложений для включения в реферат проверялся его объем, и если он превышал установленное значение, то происходил возврат к этапу выбора наиболее значимых предложений с новым критерием отбора. Если снова не удавалось достигнуть установленного объема реферата, итерация повторялась с еще более сильным критерием и т.д. В процессе формирования окончательного текста реферата должна быть решена задача расстановки предложений, выражающих темы, в логически связанной последовательности. Нами был разработан алгоритм для упорядочивания предложений. 17

18 Экран интерфейса экспериментальной системы автоматического реферирования новостных сюжетов (1) (2)

19 Исходные данные Выборка из трех коллекций документов Яндекс. Новости за 24 дня из 16 источников. Отобрано 160 кластеров с числом документов более семи: "Обычная неделя" – 95 кластеров; "Неделя Шеварднадзе"– 69 кластеров; "Неделя выборов" – 96 кластеров. 95% кластеров содержат менее 50 документов, 3 кластера имеют более 100 документов. Большинство кластеров содержат документы размером от 1 до 3 Кб. Максимальный размер- 61 Кб. Трудности: ошибки кластеризации, ошибки разбиения на предложения в документах кластера, наличие документов, не подлежащих реферированию (например, списки мероприятий и памятных событий, происшедших в какой-либо день).

20 Пример обзорного реферата

21 Пример обзорного реферата

22 Оценки работы метода Тестирование проводилось по всем трем исходным коллекциям документов. Для каждого кластера определялась степень покрытия его полученным рефератом, выраженная в процентах, - процент частотной лексики из документа кластера, попадающей в реферат. Методика оценки 1. По тексту реферата составлялся частотный словарь слов и словосочетаний. Учитывались все словарные единицы. 2. Для каждого документа кластера по такому же методу составлялся словарь слов и словосочетаний, и выбирались словарные единицы с частотой f>=2. 3. Для i-го документа кластера c i - количество совпадений словарных единиц в обоих словарях, k i - количество словарных единиц с частотой f>=2 в словаре, составленном по тексту документа, n - количество документов в кластере. Степень покрытия документа рефератом, где i=1,....,n. 4. Для всего кластера степень покрытия :

23 Распределение кластеров по степени покрытия Количество кластеров с одинаковой степенью покрытия Покрытие выше 80% имеют 73% кластеров набора "Неделя выборов", 64% кластеров «Обычной недели» и 68% кластеров "Недели Шеварднадзе". По всем кластерам трех коллекций усредненная величина покрытия равна ~ 80%.

24 Зависимость покрытия от объема кластера

25 Зависимость объема реферата от объема кластера и количества документов в кластере

26 1.Метод составления обзорных рефератов, рассматриваемый в данной работе, может быть применим на практике для представления новостных сюжетов в системе Яндекс.Новости. 2. Проведенная автоматическая оценка качества рефератов показала, что они, в основном, отражают содержание кластеров. Оценка качества реферирования независимыми экспертами не проводилась. 3.Эксперименты показали, что степень покрытия кластера рефератом зависит от объема кластера. При объеме кластера до 10 Кб наблюдается устойчивое хорошее покрытие. 4.Исследование зависимости объема реферата от объема кластера и количества документов в кластере показало, что реферат небольшого объема (до 2 Кб) можно получить только при объеме кластера до 20 Кб, а при объеме кластера >80 Кб все рефераты получаются большими и сокращаются искусственно до 3 Кб. Выводы

27 Планы продолжения исследований Совершенствование используемых алгоритмов: распознавание анафор; отождествление предложений, извлеченных из разных документов кластера; упорядочивание предложений при окончательном формировании обзора. Разработка новых алгоритмов и методов: выявление полных и кратких названий одних и тех же объектов ( стран, организаций, персон и т.д.) и замена их друг на друга с соблюдением правил предшествования в тексте обзора; реферирование кластеров, содержащих сотни документов.

Благодарности Компании "Яндекс" за финансовую поддержку работы в рамках проекта «Интернет-математика 2007» 28

29 Автоматическое составление обзорных рефератов новостных сюжетов Спасибо за внимание! к.т.н. Абрамова Н.Н., аспирант Абрамов В.Е. ФГУП «НИЦИ при МИД России»