'

Оценка систем информационного поиска

Понравилась презентация – покажи это...





Слайд 0

Оценка систем информационного поиска Игорь Некрестьянов Санкт-Петербургский Государственный Университет http://meta.math.spbu.ru/~igor


Слайд 1

Зачем оценивать? Как понять метод хорош или плох? Для того чтобы улучшать, надо определить что значит «лучше» «Можно сделать так» или «Это решение лучше»: «Мне кажется так будет лучше …» «Мы делаем так …» «Наш метод использует семантику …» «Мне нравятся результаты поиска …» Критерий истины. Важно в любой науке. Есть способ оценки – есть возможность сравнения => соревновательный эффект!


Слайд 2

Что оценивать? Насколько быстро выполняются запросы? Сколько занимает индекс? Насколько хорошо удовлетворяются информационные потребности? Сколько информации удалось получить по данной теме? Насколько полезна коллекция по которой идет поиск? Насколько удобно пользоваться системой? …


Слайд 3

Критерии оценки Объем и состав коллекции Способ представления результатов (поиска) Простота обучения и использования Экономическая выгода Быстродействие Качество ответа (точность, полнота) Удовлетворенность пользователя в контексте решаемой задачи Для количественной оценки используются меры. Критерии и метрики могут быть лишь предполагаемо связаны!


Слайд 4

Отступление: оценка инновации Эта схема безусловно применима не только к системам информационного поиска.


Слайд 5

Метрики на множествах Насколько близки искомый и реальный ответ? Точность = |Ra| / |A| Полнота = |Ra| / |R| AveragePrecision Усреднение значений точности на уровнях релевантных документов F-мера – смесь точности и полноты Искомые ответы |R| Ответ системы |A| коллекция Ra


Слайд 6

Микро- и Макро- усреднение Макроусреднение вычислить метрики по каждому запросу отдельно и затем их усреднить Усреднение независимо от «мощности» запроса Микроусреднение найти общий размер всех ответов, правильных ответов, искомых ответов и на их основе вычислить искомую метрику Полезно в задачах классификации и фильтрации


Слайд 7

Метрики на последовательностях Ответ системы ранжирован, эталон - нет Точность/Полнота на уровне N (среди первых N) R-точность – точность на уровне, равном общему числу релевантных документов Позволяет сравнивать запросы разных мощностей «Ценность ответа» (reciprocal rank) – функция от позиции первого релевантного документа Оценка усилий пользователя для нахождения ответа на свой вопрос Обычно задается дискретной шкалой


Слайд 8

Метрики: пример Пусть только d1 и d2 – релевантные 2 варианта ранжирования D3 D1 D4 D4 D1 D3 D5 D5 D2 D6 D6 D2 D7 D7 Какой вариант ранжирования лучше? Точность P1: 0 и 1 P5: 0.4 и 0.2 Полнота R5: 1 и 0.5 R-точность 0 и 0.5 AveragePrecision (1/3+2/5)/2 и (1/1+2/6)/2 Ценность ответа по шкале (1, .7, .5, .3, .1) 0.5 и 1


Слайд 9

11-точечный график TREC Интерполированные значения точности на заданных уровнях полноты (0, 0.1, 0.2, …., 1.0) Показывает что будет потеряно при достижении заданного уровня полноты/точности AveragePrecision – площадь под графиком полнота точность Какая система лучше?


Слайд 10

Способы оценки Аналитическое доказательство Например, оценка сложности алгоритма Зачастую, сложно описать целевую функцию, точно характеризующую критерий оценки. Эксперимент Почему наблюдаемый результат закономерность, а не случайность? Абсолютная оценка не имеет значения. Только относительная.


Слайд 11

Что такое «хороший» ответ? Полный? Частичный? Содержащий сведения по этой теме? Дающий идеи для дальнейшего поиска? Пример: ответы на запрос «сколько см в дюйме» металл толщиной 1 дюйм (2,5 см) … при вершине 2,5 дюйма (6.4 см) … амортизатором с ходом 11,1 дюйма (28,2 см) … Примеры других «четких» запросов: Почему украинцы воруют российский газ? На чем ездят россияне? Куда поехать отдыхать? Релевантный по мнению пользователя


Слайд 12

Релевантность Формально: степень соответствия ответа информационной потребности пользователя. Субъективное понятие Можно говорить лишь о приблизительном измерении Разные люди часто имеют разные представления о том, что такое релевантный документ для этого запроса Есть много разных подвидов релевантности


Слайд 13

Релевантность: классификация по Mizzaro 4 оси – Relevance(IR, IN, C, T) Информационные ресурсы (IR) Информационная потребность (IN) Контекст (C) Время (T) Источник: S. Mizzaro. How many relevances in information retrieval? 1997. http://www.dimi.uniud.it/~mizzaro/research/papers/IwC.pdf Замечание: Это не догма, а демонстрация сложности понятия релевантность.


Слайд 14

Ось: Информационные ресурсы Набор документов Которые вместе удовлетворяют потребность пользователя Документ Атомарная единица, из которых состоит ответ системы. Суррогат Производная от документа. Например, название + аннотация. Информация Результат чтения документа пользователем (что если документ на неизвестном языке)


Слайд 15

Ось: Информационная потребность Реальная неосознанная истинная информационная потребность пользователя Осознанная внутреннее понимание реальной потребности Сформулированная описание средствами естественного языка Формализованная описание на языке запросов


Слайд 16

Информационная потребность «Осознание» - проблема, если не очень понятно, что хочется найти «Формулирование» Использование ключевых слов, а не связных предложений. Проблема словаря – слова в документах и в запросе могут быть разными. Формализация Не все хорошо владеют языком запросов Переходы между состояниями вносят погрешность!


Слайд 17

Пример Задание: practical application of neural networks to information filtering Его поняли как: practical application of neural networks to information retrieval Словами описали как: нейронные сети в задачах информационного поиска Запрос: neural network AND information search


Слайд 18

Ось: Контекст Тема Предметная область Задача Зачем эта информация нужна Примеры: информационный поиск (узнать), транзакционный (купить), навигационный (найти домашнюю страницу), … Атрибуты пользователя Предыдущие знания Документы, которые не сможет понять Время, которое он может посвятить поиску


Слайд 19

Ось: Время Примеры: Пользователь выясняет что-то, что позволяет ему лучше понять документ (например, узнает про непонятный термин) Информационная потребность изменяется в процессе изучения результата (например, поняв что search != retrieval) Знания и атрибуты пользователя изменяются (это уже не новая информация) Важна для моделирования интерактивности поиска.


Слайд 20

То, что хочется оценить, != тому, что реально оценивается.


Слайд 21

Лабораторная парадигма оценки Проект Cranfield-2 в 1970-х Сравнительное тестирование Какая из систем A или B лучше решает данную поисковую задачу? Возможность повторения эксперимента Предположения: Релевантность можно аппроксимировать тематической схожестью. Набор оценок асессора репрезентативно представляет пользователя ИПС. Для каждого задания известны все релевантные документы


Слайд 22

Базовый подход Альтернативными методами выполняются одинаковые задания Фиксируется задача+коллекция+набор заданий Задача фиксирует критерий оценки Оценка на основе сравнения с «эталоном» «Эталон» обычно строится с помощью асессоров, которые оценивают ответы на правильность Идея: варьировать отдельные компоненты и смотреть как меняется результат Новые запросы Расширенная коллекция Другая цель поиска (купить, а не найти информацию)


Слайд 23

TREC/CLEF/РОМИП/… «Открытые» форумы для оценки методов информационного поиска: TREC = Text Retrieval Conference, с 1992, US В основном англоязычный поиск CLEF = Cross Language Evaluation Forum, 2000, Europe Многоязычный поиск, в основном европейские NTCIR, с 1999, Japan Фокус на CJK (Chinese, Japanese, Korean) РОМИП – Российский семинар по оценке методов информационного поиска, с 2003 Русскоязычные коллекции и заданий


Слайд 24

Особенности Большие объемы коллекций Невозможно оценить все документы Частичная оценка результатов Оценивается подмножество заданий Не все ответы, но одинаково для разных систем Соблюдение анонимности результатов Защита от персональных предпочтений асессоров Более одной оценки от асессоров


Слайд 25

Коллекции РОМИП’2006


Слайд 26

Коллекции Результат эксперимента зависит от коллекции (русскоязычный движок и коллекция на японском) Нельзя просто переносить выводы с одной коллекции на другую Неправильно тестировать метод на одной коллекции Что важно в коллекции? Размер важен, но это не единственный параметр Свойства, которые использует ваш метод Язык, тип документов, связи между ними, …


Слайд 27

Пример: коллекция Narod.Ru Случайная выборка из домена Narod.ru Довольно большая (1.5Гб в архиве) Содержит много разных типов сайтов Но: Больше мусора, чем в среднем в Рунет Типовые шаблоны оформления страниц Нет ряда категорий сайтов (корпоративные сайты, магазины, …) Граф ссылок непохож на Веб


Слайд 28

Дорожки РОМИП’2006 Много заданий для систем - защита от ручной настройки результата


Слайд 29

Метод «общего котла» (pooling) Котел – объединение первых N (50-100) документов из результатов каждой системы. Асессор оценивает все документы в котле. Плюсы: Контролируемый объем работы (не вся коллекция) Убираются дубликаты => выгодно участникам Можно собирать >1 оценки Асессор не знает какая система вернула этот результат и на какой позиции Нет личных предпочтений Позволяет точно вычислить ряд оценок Например, точность на уровне (по первым 10 документам)


Слайд 30

Метод «общего котла» Точное число релевантных ответов не известно Оценка полноты приблизительная – учитываем то, что попало в котел Вопросы: Насколько хорошо приближение полноты? Что если коллекция/задания будут другими? Асессор – хорошая модель пользователя? Как оценить не участвовавшую систему?


Слайд 31

Выгода от совместной оценки Число прогонов Коэффициент выгоды Выгода – отношение объема работы при оценке «котла» к объему работы при оценке результатов независимо.


Слайд 32

Новых документов Рост размера котла (РОМИП2004) Глубина котла Значение в точке k – разница между суммарным объемом котлов (по всем запросам) глубины k и k-1. Упражнение: Как бы выглядел бы график, если бы системы возвращали случайные результаты?


Слайд 33

Новых релевантных Число релевантных документов Глубина котла Предполагаемая аналитическая модель Похоже на данных TREC и РОМИП (коэффициенты C и S отличаются) Можно оценить выгоду от увеличения глубины с 50 до 100 – на 30-50% больше релевантных (РОМИП 2004) Неточная оценка – нельзя узнать общее число


Слайд 34

Можно ли верить выводам? Проблема: Метод A лучше B (на d). Будет ли так в другом эксперименте? На результат влияют: Размер и состав набора заданий Глубина «котла» Субъективность оценки асессора Величина «допуска» d, которая используется при принятии решения «лучше»/«хуже» Аналитически доказать нельзя, но можно поставить эксперимент Упражнение: добавление еще одного ответа системы в котел не влияет на выводы.


Слайд 35

Оценка стабильности Идея: оценить вероятность ошибки Гипотеза (|Q1|=|Q2|, и Q1 и Q2 не пересекаются): A > B на наборе Q1 => A > B на наборе Q2 Повторение эксперимента на разных наборах запросов Не более половины оценивавшихся Что можно узнать: Вероятность в ошибки в выводе A>B Найти d при котором приемлемая вероятность ошибки Способы повышения стабильности: Увеличить число заданий или глубину котла, повысить d


Слайд 36

Стабильность выводов с увеличением числа заданий Число заданий Ошибка (%) По данным РОМИП’2004 Вероятность, что третье место лучше первого 3-11% На данных TREC графики более гладкие (больше систем)


Слайд 37

Роль асессора Открытая проблема: Соответствуют ли выводы на основе оценок асессора оценкам реальных пользователей? Известные факты Абсолютный результат оценки зависит от асессора Несогласие асессоров есть всегда и довольно высоко Дублирование оценок повышает стабильность Альтернатива – увеличение числа заданий Случайные ошибки (до 5%) слабо влияют на выводы «Ошибочно релевантен» опаснее, чем «ошибочно нерелевантен» сложнее задача => выше «шум»


Слайд 38

История неудачного эксперимента Задача: структурировать поток новостей в набор событийных сюжетов, связанных между собой. Событие: отражение события из реального мира в потоке новостных сообщений («смерть папы римского») Сюжеты – события, связанные между собой нетематическими связями («перенос футбольного тура в связи с кончиной папы») Оценка: полная разметка потока вручную Хорошо позволяет оценить полноту (и точность) Собранные оценки легко повторно использовать


Слайд 39

Инструмент оценки


Слайд 40

Результат Мало выделенных кластеров Распределение кластеров не совпадает с ожиданиями (основанных на природе данных) Очень большие отличия у разных асессоров Внутренняя структура сюжетов часто недоработана (очевидные дубли не склеены) Почему? Очень сложная задача для асессора Выбор между сотнями готовых кластеров Невозможно быстро понять о чем этот сюжет не просмотрев сообщения еще раз Контекст быстро забывается, если асессор отвлекся на что-то другое Концептуально: оценивалась позиция «редактора», а не «читателя»!


Слайд 41

Рецепт: оценка самостоятельно Формализуйте задачу и ограничения Определите критерий оценки ОДНО числовое значение, а не много! С чем вы будете сравнивать? Есть ли готовые наборы данных? Продемонстрируйте, что ваш метод лучше Простого базового Вернуть все. Вернуть случайно. Использовать Яндекс /Google/…. Наилучшего известного метода Почему выводам можно верить? Оцените стабильность Перепроверьте обоснование критериев оценки


Слайд 42

Сравнение поисковых систем в Веб У каждой системы своя коллекция Методы TREC прямо не применимы Специализированные задачи: Сравнение размеров Какая система «больше» Свежесть индекса Доля актуальных документов Чистота Доля уникальных документов Размер «интернет» Оценка суммарного размера Веб Рассмотрим пример задачи по оценке не связанный с понятием релевантность


Слайд 43

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


Слайд 44

Как сравнить размеры? (2) Альтернативный подход: Выбираем случайный URL из машины A и проверяем наличие в машине B. (так оцениваем Pr(A&B|A)) Как выбрать действительно «случайный»? (хотим получить однородную выборку) Общий подход к реализации: Выбор «случайного» URL Строим словарь Генерируем запросы Выбираем URL на основе ответа на запрос Как проверить наличие? Надо найти этот документ Доказать, что это он


Слайд 45

Немного математики Дано: системы A и В Допустим мы научились оценивать Pr(A&B|A). Что дальше? Pr(A&B|A) = Size(A&B)/Size(A) Pr(A&B|B) = Size(A&B)/Size(B) следовательно Size(A)/Size(B) = Pr(A&B|B) / Pr(A&B|A)


Слайд 46

Как оценить размер Веб? Идея: Если индексы систем A и B независимы, то |A&B|/|B| = |A|/|Web| Умеем вычислять |A&B|/|B|, а |A| можно взять из публичных источников А независимы ли? Вероятно не совсем Но: |A&B|/|B| по факту совпадают для разных B Это оценка размера индексируемого Веб


Слайд 47

Детали реализации Словарь Можно построить на основе подмножества Веб Генерация запросов Запросы OR из 4 слов (одинаковые по частоте) Запросы AND из 2 слов (равноудаленных от концов отсортированного по частоте словаря) Однословные запросы 1,3,5,7-словные фразы Возможные проблемы: Большое число результатов => сильно влияние ранжирования Перекос документы с большим словарем => теряем маленькие документы AND-запросы – находят «словники»


Слайд 48

Детали реализации (2) Выбор URL Случайный из первой сотни результатов Любознательным: Ziv Bar-Yossef, Maxim Gurevich. Random Sampling from a Search Engine’s Index. Труды WWW’2006. http://www2006.org/programme/files/pdf/3047.pdf котел запросов (взвешенный) случайное блуждание => более однородная выборка


Слайд 49

Есть ли URL в индексе? Идея: задать запрос для которого этот url должен быть в ответе «строгий» запрос: 8 слов с лучшим IDF оператор «URL:» и подобные Сложности: Одна и та же страница может быть проиндексирована под разными URL Многие системы не показывают частичные дубликаты Как убедится что документ тот же? Сравнить содержимое (совпадение на 85%)


Слайд 50

Развитие «наивного» подхода Запросы Небольшое число ответов во всех системах Минимизация влияния «продвинутых» возможностей системы Без стоп слов Грамматически корректные С простым словоизменением (или неизменяемые) Проверка Скачиваются все ответы Проверяются на совпадение текста Плюсы: Позволяет оценить свежесть и чистоту Невысокая трудоемкость (120-600 запросов) (устойчивая оценка начинается с 60-70)


Слайд 51

Развитие «наивного» подхода (2) Плюсы: Позволяет оценить свежесть и чистоту Невысокая трудоемкость известные эксперименты - 300-600 запросов (устойчивая оценка начинается с 60-70) Возможность ежедневного мониторинга Почему выборка репрезентативна? Строгого доказательства нет По данным Яндекс: размер известного набора документов с редкими словами растет пропорционально размеру Веб


Слайд 52

Пример результата оценки Система Размер Чистота Свежесть Яндекс 829m 0.901 0.839 Рамблер 1020m 0.759 0.801 Google 547m 0.884 0.806 Yahoo! 406m 0.907 0.904 MSN 348m 0.950 .920 Рунет – 2600m документов По данным «Автолюба» - autoluba.narod.ru Сегалович И.В, Зеленков Ю.Г., Нагорнов Д.О. Методы сравнительного анализа современных поисковых систем и определения объема Рунета. Труды RCDL’2006.


Слайд 53

Напоминание Рецепт: оценка самостоятельно Формализуйте задачу и ограничения Определите критерий оценки ОДНО числовое значение, а не много! С чем вы будете сравнивать? Есть ли готовые наборы данных? Продемонстрируйте, что ваш метод лучше Простого базового Вернуть все. Вернуть случайно. Использовать Яндекс/Google/… . Наилучшего известного метода Почему выводам можно верить? Оцените стабильность Перепроверьте обоснование критериев оценки


Слайд 54

Что можно по этой теме почитать? S. Mizzaro. How many relevances in information retrieval? 1997. http://www.dimi.uniud.it/~mizzaro/research/papers/IwC.pdf М. Агеев, И. Кураленок, И. Некрестьянов. Официальные метрики РОМИП’2006. http://romip.narod.ru/docs/romip_metrics.pdf Кураленок И.Е., Некрестьянов И.С. Оценка систем текстового поиска. Программирование, 2002. http://meta.math.spbu.ru/~igor/papers/exp-survey/ D. Harman. What we have learned, and not learned from TREC. Труды BCS IRSG, 2000. http://citeseer.ist.psu.edu/432755.html Karen Sparck Jones, What's the value of TREC - is there a gap to jump or a chasm to bridge? SIGIR Forum, 2006. http://sigir.org/forum/2006J/ Ian Soboroff. Do TREC Web Collections Look Like the Web? SIGIR Forum, 2002. http://www.sigir.org/forum/F2002/soboroff.pdf


Слайд 55

Что можно по этой теме почитать? (2) И. Некрестьянов, М. Некрестьянова, А. Нозик. Анализ «лабораторной» парадигмы оценки систем поиска. Интернет-математика 2005. http://company.yandex.ru/grant/list.xml Amit Singhal, Marcin Kaszkiel. A Case Study in Web Search using TREC Algorithms. Труды WWW10. http://www10.org/cdrom/papers/317/ Сегалович И.В, Зеленков Ю.Г., Нагорнов Д.О. Методы сравнительного анализа современных поисковых систем и определения объема Рунета. Труды RCDL’2006. http://www.rcdl2006.uniyar.ac.ru/papers/paper_76_v1.pdf Сайт РОМИП: http://romip.narod.ru Сайт TREC: http://trec.nist.gov И еще масса интересных статей – смотрите на что ссылаются авторы и читайте их тоже!


×

HTML:





Ссылка: