Оценка систем текстового поиска Игорь Кураленок Яндекс, СПбГУ. - презентация

1 Оценка систем текстового поиска Игорь Кураленок Яндекс, СПбГУ

2 Чему верить? Верить Методы оценки Известные исследования Факты, подтвержденные статистикой Принять к сведенью (по желанию) Выводы о качестве того или иного эксперимента Модель того как все на самом деле и как все взаимосвязано

3 План Как люди это делают Как уменьшить количество работы Анализ и обоснование оценки Как (возможно ли?) сделать оценку статистически корректной Работа в условиях неполных и/или неточных данных Как еще можно оценить систему текстового поиска?

4 План Как люди это делают Как уменьшить количество работы Анализ и обоснование оценки Как (возможно ли?) сделать оценку статистически корректной Работа в условиях неполных и/или неточных данных Как еще можно оценить систему текстового поиска?

5 Немного истории Кренфилдские эксперименты (1966) появление пулинга (1975) Text REtrieval Conference (TREC) (1992) Исследования основ оценки на базе (TREC) ( …) NII Test Collection for IR Systems (NTCIR) (1999) Cross Language Evaluations Forum (CLEF) (2000) Российский семинар по оценке Методов Информационного Поиска (РОМИП) (2003)

6 Классическая (Cranfield) процедура оценки Составим список запросов и ограничим коллекцию документов Для каждой пары запрос/документ выставим экспертную оценку «релевантности» Будем рассматривать ответ системы не как последовательность документов, а как множество/последовательность оценок релевантности На полученной последовательности/множестве оценок релевантности построим метрики

7 Множественные оценки РелевантенНе релевантен В ответе Не в ответе

8 Отсечение на уровне Уровень меняется в зависимости от запроса Информация Оценки на последовательностях

9 Усреднение Микроусреднение Составляем общую таблицу релевантности и по ней считаем метрики на множестве Макроусреднение Усредняем значения метрик на отдельных запросах

10 График Precision/Recall (по запросу)

11 Интегральные метрики Средняя точность (AP & MAP)

12 11-точечный график TREC Значения полноты от 0 до 1 с шагом 0.5 Интерполяция точности если, то Микроусреднение одинаковых уровней полноты разных запросов

13 Многомерная модель релевантности (S. Mizzaro) Информационная потребность: Неосознанная ИП (RIN) Осознанная ИП (PIN) Сформулированная ИП (EIN) Запрос (Q) Документ Множество нужных документов (DS) Документ (D) Представление (MD) Профайл (P) Контекст: тематика, задача, атрибуты пользователя (языки, терпение) Время

14 Виды релевантности Системная релевантность = Запрос + Профайл + * Когнитивная релевантность (пертенентность) = Неосозная ИП + Документ + * Тематическая релевантность = * + Тема + (Задача?) + *

15 Шкалы релевантности Позволяет получить больше информации о мнении пользователя Иногда улучшает согласованность оценок Позволяет провести оценку на разных уровнях «требовательности пользователя» Усложняет процедуру построения оценки Не позволяет использовать классические метрики (делая результаты непонятными слушателям) Порождает проблему взаимоотношения оценок

16 Шкала оценки РОМИП Соответствует Скорее соответствует Возможно соответствует Не соответствует Не может быть оценен

17 Оценки для не бинарного случая релевантности

18 Normalized Discounted Cumulated Gain (K. Jarvelin, J. Kekalainen)

19 План Как люди это делают Как уменьшить количество работы Анализ и обоснование оценки Как (возможно ли?) сделать оценку статистически корректной Работа в условиях неполных и/или неточных данных Как еще можно оценить систему текстового поиска?

20 Пулинг Для каждого запроса: Собрать результаты систем участников глубины A Выбрать из полученных результатов B первых Удалить дубликаты Проставить оценки релевантности Не оцененные документы считать нерелевантными Оценить весь ответ системы (с глубиной А)

21 Исследование распределения релевантных документов по разным глубинам пула (J. Zobel,98)

22 Исследование распределения релевантных документов при изменении числа участников (J. Zobel,98)

23 Сложности, связанные с пулингом Взаимное усиление систем Недооценка систем, не участвовавших в оценке Получаемая оценка – оценка снизу

24 Альтернативы пулингу (G. Cormack, C. Palmer, C. Clarke) Попросить асессоров любыми способами искать релевантные документы (ISJ) Случайный выбор документов для оценки (Random) Move-to-front пулинг

25 Найдено релевантных

26 Корреляция AP

27 План Как люди это делают Как уменьшить количество работы Анализ и обоснование оценки Как (возможно ли?) сделать оценку статистически корректной Работа в условиях неполных и/или неточных данных Как еще можно оценить систему текстового поиска?

28 Анализ и обоснование классической модели Стабильность метрик Зависимость результатов от набора экспертов Информация (по Шеннону), содержащаяся в метриках

29 Стабильность оценок (C. Buckley, E. Voorhees) Цели: Как изменяется стабильность ранжирования при изменении данных на известных метриках Какие минимальные требования к данным для того, чтобы метрики оставались стабильными

30 Стабильность метрик к изменению количества запросов

31

32 Стабильность метрик к изменению уровня значимости

33 Стабильность метрик к изменению уровня значимости (50 запросов)

34 Стабильность метрик к изменению уровня значимости (25 запросов)

35 Зависимость результатов от состава экспертной группы (E. Voorhees, 98) Асессоры часто не соглашаются в своих оценках Влияет ли это несогласие на финальное ранжирование?

36 Зависимость результатов от состава экспертной группы

37

38 Информация, содержащаяся в известных метриках (J.Aslam, E. Yilmaz, V. Pavlu) Используя Метод Максимальной Энтропии вычисляем распределение вероятностей релевантности по ответу поисковой системы, исходя из информации о количестве релевантных документов и значения метрики Восстанавливаем распределение точности по разным уровням полноты Сравниваем полученный график с наблюдаемым

39 Метод Максимальной Энтропии в вычислении вероятности релевантности

40 Распределение точности построенные на разных метриках

41 Среднеквадратичное отклонение теоретических графиков от наблюдаемых

42 План Как люди это делают Как уменьшить количество работы Анализ и обоснование оценки Как (возможно ли?) сделать оценку статистически корректной Работа в условиях неполных и/или неточных данных Как еще можно оценить систему текстового поиска?

43 Известные подходы к оценке Органолептический Аналитический Косвенная оценка Интерактивная оценка Решение более общей задачи Кренфилдская оценка

44 Требования к оценке Повторяемость Интерпретируемость Переносимость Низкая стоимость

45 Что значат кренфилдские оценки с точки зрения пользователя? (A. Turpin, F. Scholer) Возьмем пользвательскую задачу Попытаемся решить ее с помощью систем разной эффективности Проанализируем корреляцию между системной и пользовательской эффективностью

46 Постановка эксперимента Сформируем ответы с заданными значениями MAP Попросим пользователя найти первый релевантный документ по каждому из представленных запросов

47 Корреляция пользовательской и системной эффективности

48 Сессии, где не нашли релевантного документа

49 Почему так получилось? Система состоит не только из алгоритма ранжирования При высоких уровнях точности на первый план выходит «быстродействие» пользователя Релевантность с точки зрения пользователя отличала от эталонной, по которой мы проводили «настройку»

50 «Правильная» оценка с точки зрения статистики Определение границ задачи (определение границ совокупности) Разработка способа создания репрезентативной выборки Построение оценки по выборке Несмещенные оценки распределены нормально (позволяет вычислить доверительные интервалы)

51 Создание коллекции документов В большинстве случаев невозможно создать репрезентативную выборку: Проблемы с копирайтом Большие объемы данных Связность Изменчивость Доступная коллекция хоть как-то относящаяся к реальным данным

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

53 Создание коллекции запросов Ресурсы оценки ограничены Запрос должен оценивать только тот, кто его создал В коллекция должна содержать ответ на запрос Хочется проводить оценку для n систем сразу (обобщение аудитории) Запросы создаются часто от балды

54 Чем отличается академическая оценка от индустриальной (Андреас Раубер) Академическая: Работает когда нет окончательного понимания о пользовательских задачах Оценивает «разумность» поведения хотя бы для какого- то пользователя Позволяет исследовать различные варианты методологии и их объективные свойства Минимизирует затраты на проведение эксперимента Не представляет практического интереса с точки зрения применения в качестве объективных данных (обратная связь,сравнение эффективности в коммерческих целях, …) Индустриальная: Пользовательские задачи строго определены рамками интерфейса Необходима оценка того, как система работает для множества пользователей (зависит от целей системы) Бюджет и доступные для исследования данные значительно богаче Должна отражать объективную реальность

55 Как проводить оценку своей системы С помощью коллекции Оценки смещены, но смещение случайно Ограничен набор метрик Доступны результаты конкурентных подходов Самостоятельно Только статистически правильно Необходима переоценка конкурентных подходов

56 Кто оценивает релевантность? Автор информационной потребности: Разбирается в области поиска ровно настолько сколько может знать человек породивший такой запрос Имеет четко выраженное представление о том, что хочет найти Может построить несколько вариантов запроса с одной и той же информационной потребностью Обученный асессор: Имеет более четкое представление о качестве документа Формирует согласованные оценки Может обрабатывать любой запрос

57 Как создать «правильную» выборку ИП? Набрать случайных запросов от пользователей Восстановить по ним наиболее частотные ИП Обобщить ИП и «объяснить» асессору что подходит к запросу, а что нет

58 Многомерная модель релевантности (S. Mizzaro) Информационная потребность: Неосознанная ИП (RIN) Осознанная ИП (PIN) Сформулированная ИП (EIN) Запрос (Q) Документ Множество нужных документов (DS) Документ (D) Представление (MD) Профайл (P) Контекст: тематика, задача, атрибуты пользователя (языки, терпение) Время

59 Преобразование запроса Запрос –> Поле информационных потребностей Поле ИП преобразуем в Полное описание Выбор представителя (случайный?) Выбор подмножества

60 Как создать «правильную» выборку документов в сети Ограничиться сильно связным сегментом сети Работать со всем интернетом

61 Что еще нам мешает применять кренфилдскую модель оценки Оценки на маленьких коллекция становятся все менее интересны На больших коллекциях (например сеть) «хвост» пулинга слишком велик Документы/запросы изменяются и коллекция быстро устаревает Мы вынуждены сравнивать абсолютные значения метрик, наблюдаемые на разных коллекциях

62 Что можно с этим поделать Разработать более стабильные к изменению оценок метрики Обеспечить малые границы изменения абсолютных значений метрик Большая согласованность оценок релевантности Научиться оценивать репрезентативную выборку запросов

63 Уменьшить разногласия асессоров Создать эталонного пользователя (коллективный разум), который скажет что такое ошибки Построить четкие правила оценки для известных эталонному пользователю случаев Обучить асессора этим правилам до оценки Смещены ли полученные оценки?

64 Полезно ли перекрытие для повышения качества оценки?

65 Оценка в уловиях неполных или неточных данных Оценки быстро устаревают Релевантные документы исчезают Все классические метрики при этом стремятся к нулю по абсолютному значению и не сохраняют порядок ранжирования систем

66 BPref (C. Buckley, E. Voorhees) Возьмем полное множество оценки Начнем последовательно выкидывать оценки релевантных документов Посчитаем что будет происходить с ранжированием систем и абсолютными значениями метрик

67 Корреляция метрик на полных данных

68 Корреляция BPref c MAP на полных данных

69 Изменения в абсолютных значениях при ухудшении данных

70 Изменение ранжирования при ухудшении данных

71 Изменение ранжирования при изменении множества документов

72 Induced Average Precision Выкинем все неизвестные документы из выдачи по каждому запросу Посчитаем MAP на основе полученных данных

73 Inferred Average Precision Любой документ выдачи принадлежит одному из трех множеств: Оцененных Неоцененных, но содержащихся в пуле Не вошедших в пул Попробуем предсказать вероятность релевантности документа на основе его положения в выдаче и данных о принадлежности к одному из множеств

74 Ожидание точности на уровне к: Если документ не попал в пул –> нерелевантен Inferred Average Precision

75 Корреляция ранжирований

76 Среднеквадратичное отклонение

77 Отклонение абсолютного значения

78 Можно ли обойтись без оценки релевантности (I. Soboroff, C. Nicholas, P. Cahan) Асессоры не всегда согласны друг с другом Набор экспертов не влияет (>0.938 T) на порядок ранжирования систем Можно попытаться смоделировать оценку релевантности

79 Модель случайной оценки Известен процент релевантных документов в пуле по запросу и его сигма Смоделируем нормальным распределением число релевантных на запрос Случайно выберем полученное количество документов из пула Будем считать что выбранные документы релевантны

80 Результаты Полные пулыС дублями Мелкие пулыПо реальным количествам релевантных документов

81 Можно ли оценить системы с помощью данных о кликах? (T. Joachims) Клики говорят о сравнительной релевантности документов: Будем представлять пользователю систему с рандомными ответами и считать клики Получились одинаковые результаты для разных систем из чего сделано предположение о «смещенности» данных в зависимости от качества Сольем результаты в один серп, тогда зависимости от качества удастся избежать

82 Сравнение результатов Google vs. MSN Google vs. Random MSN vs. Random Клики77%/63%85%/18%91%/12% Релевантность0.81/ / /0.04

83 Куда двигать оценку? Неполные данные с уровнями релевантности Взаимоотношение поведения пользователя и оценок релевантности Предварительная оценка Переносимость абсолютных результатов Связи между разными видами оценки Создание статистически «правильных коллекций»