Содержание к диссертации
Введение
1 Анализ состояния области 9
1.1 Оценка систем информационного поиска 11
1.2 Предмет оценки 14
1.2.1 Поисковая система 14
1.2.2 Наборы данных 16
1.3 Критерии 21
1.3.1 Релевантность 21
1.4 Меры, используемые в оценке 26
1.4.1 Меры на уровне обработки 27
1.4.2 Меры на уровне выхода 33
1.4.3 Другие меры 34
1.5 Инструменты измерения 35
1.5.1 Теоретические подходы 35
1.5.2 Реальные пользователи 36
1.5.3 Экспертные оценки 37
1.5.4 Косвенные оценки 41
1.6 Методы оценки 42
1.6.1 Процедура проведения оценки 42
1.6.2 Анализ результатов 43
1.6.3 Методология 45
1.7 Заключение 51
Теоретические основы предлагаемого подхода 52
2.1 Основные понятия 52
2.1.1 Вероятностное представление релевантности 52
2.1.2 Относительная релевантность 54
2.1.3 Относительная эффективность 55
2.2 Используемые метрики 55
2.2.1 Требования 56
2.2.2 Кандидаты 56
2.3 Построение оценки относительной эффективности 57
2.3.1 Полнота ответа эталонной системы 59
2.3.2 Оценка относительной релевантности 61
2.3.3 Сглаживание зависимости вероятности релевантности
от индекса документа в ответе тестируемой системы . 62
2.4 Построение мета-поисковой системы на основе оценки относительной релевантности 63
Инициатива РОМИП 65
3.1 Организация семинара 67
3.1.1 Методология оценки 68
3.1.2 Оргкомитет 69
3.2 Дорожка по поиску 70
3.2.1 Правила проведения 70
3.2.2 Выбор заданий для оценки 71
3.2.3 Сбор оценок асессоров 72
3.2.4 Таблицы релевантности 75
3.2.5 Метрики для вычисления оценок результатов прогонов 76
3.2.6 Сводные результаты систем 79
3.3 Дорожка по классификации 79
3.4 Наблюдения и планы 81
4 Экспериментальные исследования
4.1 Исследование зависимости относительной релевантности от ранга документа 82
4.1.1 Постановка эксперимента 83
4.1.2 Результаты 84
4.1.3 Анализ 84
4.2 Устойчивость характеристик ИПС к изменению входных данных 85
4.2.1 Постановка эксперимента 88
4.2.2 Результаты 90
4.2.3 Анализ 93
4.3 Оценка относительной эффективности 95
4.3.1 Постановка эксперимента 96
4.3.2 Результаты 97
4.3.3 Анализ 98
4.4 Мета-поисковая система, построенная на основе оценки относительной релевантности 100
Заключение 102
Литература 10
- Оценка систем информационного поиска
- Вероятностное представление релевантности
- Метрики для вычисления оценок результатов прогонов
- Устойчивость характеристик ИПС к изменению входных данных
Введение к работе
Актуальность проблемы поиска и обработки текстовой информации сегодня не вызывает сомнений. Ежедневно мы сталкиваемся с необходимостью ее эффективного решения на работе и дома. Многие сферы нашей деятельности зачастую тесно связаны с электронными технологиями, получившими за последние два десятка лет широкое распространение в нашей стране. Так, для того чтобы найти необходимую книгу или ноты не обязательно выходить из дома, а для того, чтобы узнать курс валют или акций идти на биржу. Большинство информации можно найти в общедоступных сетях (internet, fidonet, домашние сети (homenet) и т.п.), однако большинство этих сетей содержат информацию неупорядоченно, что приводит к необходимости ее поиска. Так как большинство информации представлено в тексте, наиболее часто встающей перед пользователем является задача полнотекстового поиска.
Текстовый поиск — одна из самых первых задач компьютерной эры. История исследований в этой области берет свое начало в 50-х годах, когда создавались первые поисковые системы (Н. Luhn, 1958 [29]). Наиболее масштабные же исследования в области информационного поиска относятся к 90 годам и продолжаются по сей день. Столь долгий период невостребованности исследований широким кругом пользователей (практически до конца 80-х) в первую очередь связан с тем, что большинство предлагаемых методов эффективны на больших объемах данных, которые не могут быть подвергнуты анализу по выделению структуры (поиск в структурированных данных — решенная задача), а такие данные были просто недоступны широкому пользователю из-за малой мощности существовавших вычисли-
Содержание
тельных машин. В конце 80-х широкое распространение получили сетевые технологии, которые позволили распределить информацию по множеству машин, это и привело к расцвету текстового поиска.
Несмотря на богатую историю исследований полнотекстового поиска, широкое распространение получили лишь несколько наиболее простых технологий: простые векторные и вероятностные модели, что связано в первую очередь с простотой их реализации. Спрос на поисковые системы столь велик, что большинство реализаций написаны непрофессионалами в поиске, для которых фактор простоты реализации является определяющим. Но даже в том случае, когда работу выполняет человек, осведомленный о достижениях в этой области, он все равно скорее всего изберет один из проверенных и зарекомендовавших себя методов. Этот факт связан с первую очередь с тем, что зачастую методы, показывающие хорошие результаты на одних данных, оказываются много хуже тех же классических моделей на других данных. Эти две проблемы приводят к сегодняшней ситуации, когда 95% всех поисковых систем используют различные вариации векторных моделей, эффективность которых оставляет желать лучшего, что приводит к заслуженному недоверию пользователя к результатам поиска.
Если первая обозначенная причина ситуации вряд ли может быть как-либо исправлена средствами науки, то вторая напрямую связана с провалом методологий оценки, принятых в поиске. Несмотря на то, что область оценки имеет почти столь же богатую историю как и сама область поиска (точкой отсчета можно считать вторые Кренфилдские эксперименты 1963 г.), продвижения в этой области до 1992 г. минимальны, и лишь с появлением TREC (Text REtrival Conference) ситуация несколько изменилась. В 1998 г. выяснилось, что технологии хорошо зарекомендовавшие себя в TREC абсолютно не применимы в среде Internet, что показывает "эффективность" тестирования при переносе на другие данные. С тех пор в TREC были добавлены новые коллекции, в том числе Web и VLT, исследованы многие важные проблемы и задачи поиска (многоязыковый поиск, проблема переноса техники поиска на другие языки и т.п. см. п. 1), но принципиальных
Содержание
изменений в методологии так и не последовало.
Предлагаемое исследование — маленький шажок в сторону понимания эффектов искажения результатов тестирования при переносе на новые данные. В работе сделана попытка анализа поведения результатов оценки при изменении данных. Так же предложен оригинальный способ автоматического построения оценки системы поиска относительно результатов работы системы с известными характеристиками. Рассмотренный метод имеет значительный потенциал для применения в построении предварительной оценки, так как несравнимо менее требователен к ресурсам (прежде всего человеческим), чем все существующие подходы. Построение описанного метода было невозможно без теоретической поддержки. В работе приведена своя интерпретация понятия релевантности, основанная на вероятностной модели. Еще одной иллюстрацией адекватности предложенной модели релевантности стала эффективность предлагаемого метода построения мета-поисковой системы, основанного на этой модели.
Далее работа разделена на пять частей. Первая часть представляет собой анализ существующего состояния дел в области оценки текстового поиска[73]. Основной целью этой части является введение в проблематику и обзор принятой на сегодня методологии оценки. Отличительной чертой приведенного анализа является представление большой части известных аспектов оценки в едином каркасе.
Во второй части работы приведены основные теоретические выкладки. В этой части многие утверждения приводятся без доказательств (которые приведены отдельно в разделе экспериментов) с целью как можно более краткого и обозримого изложения. Несмотря на свой небольшой объем эта часть содержит большинство результатов работы.
Третья часть посвящена экспериментальным данным, использованным для подтверждения теоретических выкладок. В качестве тестовой базы приводимых экспериментов были использованы данные РОМИП'ОЗ (Российский семинар по Оценке Методов Информационного Поиска). Качество данных и способ их сбора — ключевая часть любого эксперимента, по-
Содержание
этому было решено подробно описать процедуру их построения. К тому же, в рамках работы над диссертацией автор имел возможность принять участие в работе семинара РОМИП (Российский по Оценке Методов Информационного Поиска) в качестве одного из его организаторов. И наряду с другими участниками организационного комитета создавал методологическую базу семинара. Этим фактом так же объясняется использование в работе данных, закрытых для широкого пользователя.
Четвертая часть работы представляет собой серию экспериментов, показывающих обоснованность утверждений второй части.
Последняя пятая часть посвящена выводам и возможным направлениям дальнейших исследований.
Оценка систем информационного поиска
Обобщенной целью оценки систем информационного поиска, к которым относятся и системы текстового поиска, является выявление полезности системы на практике [63]. Оцениваемую систему можно рассматривать как инновацию (т.е. нововведение), вероятность общественного признания которой характеризуется рядом атрибутов [70]:
Относительное преимущество: степень, в которой инновация воспринимается лучше предшествующей идеи с точки зрения экономической прибыльности, социального престижа, физического удобства и психологического удовлетворения.
Совместимость: степень, в которой инновация воспринимается "вписывающейся" в существующие социально-культурные ценности, убеждения и нормы, прошлый опыт, зарекомендовавшие себя идеи, приемы и оборудование, а также в осознанные потребности потенциальных пользователей. Сложность: степень, в которой инновация воспринимается как относительно трудная для понимания и применения с точки зрения существующих знаний и навыков.
Возможность тестирования: степень, в которой инновацию можно предварительно протестировать в ограниченном масштабе, таким образом снижая риск и неопределенность, связанные с внедрением. Возможность наблюдения: степень, в которой инновация и эффект от ее применения наглядно видны для других. Таблица 1.1 иллюстрирует взаимосвязь между этими атрибутами и критериями оценки систем информационного поиска, обсуждаемыми в последующих разделах [63]. Оценка всегда происходит в некотором контексте, характеризующем потребителя инновации [70]. Для информационных систем выделяют три контекста [48]: контекст общества, т.е. оценивается насколько хорошо система удовлетворяет социальные запросы и роли; контекст организации, т.е. оценивается насколько хорошо система подходит для целей организации; контекст индивидуального пользователя, т.е. насколько система помогает удовлетворять информационные потребности пользователей. Оценка систем поиска в контексте общества или организации — сложная задача. Поэтому большинство практических исследований проходит в контексте индивидуальных пользователей. Далее мы будем подразумевать именно этот контекст. Известно много подходов к оценке информационных систем. Например, можно оценивать влияние системы на общество или экономические параметры, такие как стоимость достижения заданного уровня эффективности. Однако, при оценке систем информационного поиска доминирует системный подход, согласно которому оценивается, насколько хорошо система выполняет то, для чего она была создана [48]. Можно выделить несколько уровней, на которых производится оценка системы текстового поиска: Инженерный уровень: исследуются характеристики эффективности программного обеспечения, такие как вычислительная сложность поисковых алгоритмов. Уровень входа: исследуются вопросы, связанные со взаимоотношением входной информации и содержимым системы, например, насколько полно в системе представлена информация о целевой области. Уровень обработки: изучается качество работы используемых алгоритмов и методов поиска. Уровень выхода: исследуется взаимодействие пользователя с системой и получаемыми результатами. Например, определяются оценки механизмов обратной связи, удобства представления результатов и т.п. Уровень применения: рассматривается полезность результатов поиска для решения заданной проблемы или задачи. Социальный уровень: изучается влияние на окружение, т.е. на эффективность решения практических задач, принятие решений и т.п. В применяемых на практике системах текстового поиска эти уровни тесно взаимосвязаны, но исследования по оценке поисковых систем редко затрагивают сразу несколько из них. Этот факт считается одним из серьезнейших недостатков текущей практики оценки методов поиска [48]. Важной характеристикой задачи оценки систем текстового поиска является ее неразложимость на подзадачи тестирования отдельных методов поиска. Поскольку вклад каждого отдельного метода в общую оценку не определен, то невозможно определить критерий, характеризующий его полезность для системы. Поэтому, полезность индивидуального метода в системе текстового поиска обычно оценивается косвенно как изменение оценки системы в целом при замене его на альтернативный метод.
Вероятностное представление релевантности
В работах исследователей области информационного поиска не раз отмечалось, что релевантность является субъективным понятием, и что разные эксперты дают различные оценки релевантности для одной и той же пары документ - запрос. Такой разброс оценок порождает гипотезу об адекватности вероятностного представления релевантности. В частности, в случае бинарной релевантности можно рассмотреть для каждой пары документ запрос вероятностное пространство, состоящее из двух элементарных событий (релевантности и нерелевантности), множества их подмножеств и функцию вероятности где d и дхдокумент и запрос соответственно. В отличии от бинарной релевантности, в которой определяются два уровня (релевантен и нерелевантен), предлагаемое определение оперирует со случайным событием релевантности. Такой подход позволяет перейти к непрерывной вероятности релевантности минуя введение шкалы степени релевантности. В вводимой терминологии изменяются формулировки задач поиска и его оценки, однако целью работы является не исследование этих новых задач, а использование возможностей нового представления релевантности для решения старых проблем.
Для сохранения методологической базы необходимо привести механизм вычисления значений бинарной релевантности в терминах классической схемы. В связи с тем, что предложенная формулировка гораздо шире классической, эти значения не будут обладать свойством детерминированности, что, однако, не мешает их применению в механизмах оценки и других областях поиска.
В качестве механизма перевода предлагается использование генератора случайных чисел. В частности для определения d Є R берется случайное , равномерно распределенное на отрезке [0,1]. Если полученное p(d\q) то документ d считается релевантным q. Как можно заметить новое представление релевантности напоминает смешанные стратегии в теории игр. Как и в случае смешанных стратегий новое представление релевантности включает в себя и классическую детерминированную схему2. Несмотря на случайный выбор значений, при вычислении большого количества подобных оценок, необходимого для всех рассматриваемых далее методов, по закону больших чисел зависимые характеристики (являющиеся случайными в случае применения вероятностного представления) оказываются стабильными.
Основой оценки в любой области служит повторяемость результатов. В частности, результаты системы имеющей известные характеристики на заданном множестве документов, несут в себе долю информации о истиной релевантности этих документов. Оценки, построенные по этой информации, мы и будем далее называть относительной релевантностью. Простейшим примером относительной релевантности являются оценки, построенные применением хорошо известных вероятностных методов3. Заметим, что построение понятия относительной релевантности невозможно в ее классическом бинарном представлении.
Использование относительной релевантности, построенной на основе вероятностных методов ограничено классом этих методов и не использует всей доступной информации, в частности известных результатов оценки эффективности работы системы. На сегодняшний день эти результаты используются в основном для анализа поведения системы. Однако, как будет показано далее возможно применение этих данных также и для вычисления относительной релевантности.
При вычислении относительной релевантности, как можно видеть из определения, производится оценка вероятности релевантности, что присуще вероятностным методам поиска. Таким образом можно рассмотреть полученные результаты не только как характеристику данных (релевантность), но и как новый алгоритм поиска, зачастую использующий дополнительную информацию, которая может обеспечить лучший результат от Одной из наиболее дорогостоящих частей исследования любого метода поиска является его тестирование, а точнее подготовка тестового корпуса. В первую очередь это связано с большим объемом ручного труда необходимого для сравнительного тестирования. С введением относительной релевантности можно попытаться оценить один или более методов на фоне известного (используя значения релевантности, вычисленные относительно этого метода). Необходимо отметить, что точность такой оценки заметно ниже точности оценок, полученных с помощью прямого сбора экспертных данных.
Как следует из нашего определения, относительная релевантность строится на информации предоставляемой методом. Эта информация, в свою очередь, напрямую определяется эффективностью метода. Как известно, эффективность современных методов поиска заметно уступает ручной оценке (особенно на сложных данных), что и приводит к более низкой точности оценки относительной релевантности и, следовательно, относительной эффективности. Однако, для грубой оценки этот метод может значительно облегчить труд исследователя. Таким образом, приведенная далее методика некоим образом не конкурирует с известными методами оценки, а, наоборот, дополняет их арсенал.
Метрики для вычисления оценок результатов прогонов
Вопрос устойчивости характеристик ИПС к изменению входных данных является одним из ключевых моментов как предлагаемого -исследования, так и всей области оценки систем текстового поиска. Эта задача является одной из значительных частей проблемы влияния тестовых данных на результаты работы методов поиска. Несмотря на важность этой проблематики, каких-либо серьезных исследований в этой области еще не проводилось. В первую очередь это связано с тем, внимание исследователей было сосредоточено на значимости результатов, полученных применением различных систем в одинаковом окружении. Как уже отмечалось в п.1, вопрос показательности этих результатов до конца 90-х оставался открытым, и лишь эксперименты группы исследователей из NIST 1999-2001 г.г. несколько ослабили остроту проблемы субъективности и несовпадения оценок релевантности. Теперь же, как нам кажется, пришло время и проблемы зависимости результатов от данных.
На сегодняшний момент принятая практика такова, что для авторитетности того или иного исследования в области создания методов поиска достаточно провести тестирование на объеме порядка 100,000 — 200, 000 документов при 25 — 100 запросах. Но численные характеристики не дают полного представления о сложности использованных данных и результаты тестирования, несмотря на их повторяемость, не представляют реального интереса для практического применения в той или иной области. В итоге в области поиска складывается ситуация, когда в год исследуются тысячи новых подходов в методологии поиска, а на практике используются только старые, проверенные годами TF/TFIDF. Одним из путей преодоления этого кризиса является создание все новых дорожек поиска (Веб-поиск, поиск на очень больших коллекциях и т.п.). Эти коллекции обычно создаются на основе реальных данных. Однако и здесь мы сталкиваемся с той же проблемой — проблемой недостаточности тех характеристик, которыми описывается коллекция.
Предлагаемое исследование — малый шаг к общей теории и некоим образом не претендует на полноту. В нашем эксперименте мы попытались рассмотреть две известные характеристики поисковых систем и понять насколько им можно доверять при изменении тестовой базы. С одной стороны, много раз отмечалось и достаточно ожидаемо, что численные характеристики метода поиска могут сильно отличаться при изменении одной из компонент тестового корпуса (например запроса). На рис.4.2 представлены 11-точечные графики TREC результатов одной из систем, построенные на различных запросах, которые ярко демонстрируют выдвинутый тезис. С другой стороны, для значимости результатов тестирования, в том числе и сравнительного, необходима стабильность результатов в среднем. То есть при усреднении результатов по ряду запросов их разброс скорее всего будет уменьшаться. Основная цель приводимого эксперимента проверить эту гипотезу.
Предлагаемый эксперимент преследует две основные цели: оценить возможную величину погрешности при изменении данных и прояснить вопрос сходимости последовательности характеристик методов при увеличении объема тестовых данных. В эксперименте были рассмотрены две характеристики ИПС: зависимость точности от полноты по версии TREC, как самая распространенная характеристика в современном поиске, и часто используемая в нашем исследовании зависимость средней величины точности от полноты. Такой выбор обусловлен в первую очередь тем, что практически все остальные характеристики можно вывести из этих графиков, представляющих собой наиболее полное отражение поведения системы на всех уровнях глубины ответа.
Для исследования влияния данных на характеристики случайным образом выбирались подмножества тестового корпуса и на выбранных подмножествах вычислялись характеристики систем. Далее полученные результаты сравнивались между собой. Случайность выбора подмножеств обеспечила необходимую вариационность данных. На выбранных подмножествах были построены исследуемые характеристики и вычислены графики их средних значений и среднеквадратичного отклонения от этих значений.
Полученные значения позволяют оценить величину абсолютной и относительной погрешности характеристик ИПС при их переносе на другие данные. Таким образом была решена первая из поставленных задач.
Для решения второй задачи необходимо рассмотреть последовательность указанных характеристик при увеличении объема данных. В работе Е. Вурхез (Н. Voorhees) показывается, что важнейшую роль в стабильности характеристик ИПС играет количество заданий, использованных для их вычисления. Поэтому в качестве последовательности наборов были рассмотрены наборы, содержащие различное количество запросов. При этом строился график зависимости среднего отклонения от количества использованных запросов. Однако, убывания абсолютных величин этого графика оказывается недостаточно для однозначного ответа на вопрос о сходимости рассмотренных характеристик. Этот факт связан с тем, что для исследования разброса результатов были использованы случайные наборы заданий из одного и того же множества (54 запросов дорожки поиска РОМИП ОЗ). Таким образом при увеличении количества запросов так же увеличивается и ожидание пересечения этих выборок, что приводит к методическому уменьшению разброса конечных характеристик. В связи с этим фактом, для исследования вопроса сходимости графиков необходимо так же построить и график теоретического уменьшения величины разброса характеристик. С целью построения этого графика была рассмотрена следующая модель:
Устойчивость характеристик ИПС к изменению входных данных
В приведенной работе были исследованы некоторые свойства результатов оценки систем текстового поиска. Данное исследование представляет собой первый шаг в области более широкого использования результатов тестирования. На основе предложенного подхода были получены следующие результаты: нашла свое подтверждение гипотеза о сходимости результатов тестирования при увеличении тестовой базы; исследована зависимость вероятности релевантности документа запросу от индекса ранжирования реальной поисковой системы; построена новая математическая модель представления релевантности; разработан метод автоматического построения характеристик поисковой системы относительно известной; разработан алгоритм построения мета-поисковой системы на основе предложенной теории. Эти результаты показывают перспективность выбранного направления и примененного подхода к определению основных понятий поиска.
В работе результаты оценки рассматриваются как самостоятельные данные, что позволяет в значительной степени расширить область их применения. Подобное было бы невозможно без знания того, что в среднем эти результаты сходятся при увеличении тестового набора. Этот фундаментальный факт получил частичное подтверждение в изложенной выше работе, однако характер сходимости и ее зависимость от данных — тема дальнейших исследований.
Впервые результаты оценки были рассмотрены не только как характеристика оцениваемых систем, но и как характеристика тестовой коллекции. Такой подход дал возможность разработать новую модель релевантности, которая позволила с одной стороны оценивать системы друг относительно друга, с другой же, ранжировать результаты работы различных систем поиска.
В частности, одним из приложений выдвинутой модели стал метод автоматической оценки систем текстового поиска. Кроме своей практической ценности (а это по сути первый метод такого рода) результатом построения предложенного метода является и доказательство независимости отношения характеристик методов от тестовой базы. В нашем исследовании была использована лишь информация о распределении вероятности релевантности, полученная на небольшом наборе из 54 заданий. Далее эта информация была применена ко много большему множеству заданий (10000). Полученная в результате схожесть графиков (экспертного и полученного в результате работы предложенного алгоритма) не может быть случайной и говорит об общем для любых данных отношении поведения систем. Это, на первый взгляд, слишком сильное утверждение во многом следует из самой постановки задачи поиска. Как видно из п.4.1 в среднем вероятность релевантности документа запросу убывает с увеличением индекса ответа. Задача любой системы поиска — сделать это убывание как можно более сильным, таким образом, с точки зрения вероятности релевантности, системы тем ближе друг другу, чем лучше они эту задачу решают. Эта близость и приводит к зависимости их характеристик.
Вторым приложением нового представления релевантности является разработанная мета-поисковая система. Используя знания о соотношении оценок систем, можно построить единое ранжирование их ответов. Высокая эффективность предложенной системы еще раз подтверждает верность наших предположений. Кроме теоретического значения построенная система может быть использована на практике, так как не требует почти никаких ресурсов как для реализации, так и для работы.
