Определение новизны информации в новостном кластере

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

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

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

Постановка задачи «Определение новизны» в TREC
Данная задача разрабатывалась в TREC в 2002 – 2004 годах
Постановка задачи: Дано упорядоченное множество документов, разделённое на предложения, и краткое описание(топик) к данному множеству.
Задача: Найти важные(релевантные) и новые предложения.

Постановка задачи-1
То есть по сути задача делится на две части:
Обнаружение значимых (важных) предложений.
(identifying relevant sentences)
2. Выявление из этих значимых предложений, предложений несущих новую информацию.
(novelty detection)

Постановка задачи-2
4 дисциплины:
Task 1. Дан набор документов и топик, определить все релевантные и новые предложения.
Task 2. Даны релевантные предложения во всех документах, определить все новые предложения.
Task 3. Даны релевантные и новые предложения в первых 5 документах, найти все релевантные и новые предложения в остальных документах.
Task 4. Даны релевантные предложения во всех документах и новые предложения в первых пяти, найти новые предложения в остальных документах.

Входные данные-1
AQUAINT collection.
New York Times News Service (Jun 1998 – Sep 2000),
AP (also Jun 1998 – Sep 2000),
Xinhua News Service (Jan 1996 – Sep 2000).
Данная коллекция содержит сильную избыточность информации, и таким образом мы имеем меньше новой информации, повышая реализм задачи.

Входные данные-2
Специалисты NIST сделали 50 кратких описаний новостей из данной коллекции.
Новости были 2-ух типов: События (events) и Мнения (opinions).
В описании топика содержался тег с его типом (участники заранее знали тип топика).
Документы были хронологически упорядочены и разбиты на предложения.
Предложения объединялись вместе, представляя собой единое множество документов к топику.

Оценка результатов-1
Каждый топик был проанализирован двумя независимыми экспертами из NIST.
Эксперты из набора документов выбрали релевантные предложения, и из этих предложений выбрали те, которые являются новыми.
Некоторое преимущество экспертов перед системами, ввиду присутствия нерелевантных документов.

Оценка результатов-2

Оценка результатов-3
Введём следующие обозначения:
M – число «правильных» предложений, то есть предложений, выбранных обоими экспертами и системой участником.
A – число предложений выбранных экспертами.
S – число предложений выбранных системой.

Оценка результатов-4
Тогда:
R = M / A – эффективность поиска. (Recall)
P = M / S – точность поиска. (Precision)
Проблемы:
R = 1 , P -> 0
P = 1 , R -> 0
=> Среднее значение R и P не является объективным критерием.

Оценка результатов-5
Вариант решения: F-мера (F-measure)
Общий вид:
F-measure, используемая на Novelty track:

Оценка результатов-6

Участники

Результаты - 1
В целом не очень высокие абсолютные результаты.
Среднее значение F – меры:
0.36 - 0.4 для задач обнаружения релевантных предложений.
0.18 - 0.21 для задач обнаружения новой информации.
Топики типа «Событие» оказались заметно проще топиков типа «Мнение».

Результаты - 2

Результаты - 3

Результаты - 4

Анализ результатов TREC
Task 2. Даны релевантные предложения во всех документах, определить все новые предложения.
Данная дисциплина ближе всего нашей задаче.
Колумбийский университет и система SumSeg:
Основное направление – извлечение новой информации.
Большое количество новых идей и подходов к решению задачи.
Высокие результаты:

Особенности и основные идеи системы SumSeg-1
Новая информация может появляться в сегментах больше или меньше одного предложения.
Уход от прямого сравнения предложений на «похожесть».
Новое слово – новая информация.
Классификация предложений (работа с предложением в его контексте)
Тщательная работа с местоимениями.

Особенности и основные идеи системы SumSeg-2
Большое количество различных весов и порогов.
База данных частотных характеристик слов.
Анализ контекстных характеристик слов и корректировка весов с их учётом.
Машинное обучение (автоматический подбор оптимальных коэффициентов, порогов и весов)
Векторно - пространственная модель представления информации.

Векторно-пространственная модель-1
Алгебраическая модель представления текстовых документов (в общем случае любых объектов) в виде вектора идентификаторов.
Каждое пространство соответствует отдельному терму. Если терм встретился в документе, то его значение в векторе не равно нулю.
Существует много методов по вычислению весов термов в векторе.
Сравнения близости векторов по косинусу угла между ними:

Векторно-пространственная модель-2
Пример: Пусть есть два предложения. «Мама мыла раму» и «Папа мыл автомобиль». Сравним предложения на «похожесть» при помощи ВПМ.
«Мама мыла раму»
«Папа мыл автомобиль»

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