Распределения релевантности и ее оценок - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
Похожие работы
Название работы Кол-во страниц Размер
Исследование проблем релевантности бухгалтерской 1 87.89kb.
Учебно-методический комплекс для студентов очной формы обучения направление... 5 552.37kb.
Научный подход к анализу урока 1 220.46kb.
Обработка экспертных оценок и интерпретация результатов 1 122.5kb.
Контрольная работа Оценка параметров функции распределения и построение... 1 166.84kb.
Ежегодный перечень Первоначальных оценок окружающей среды (поос) 1 298.44kb.
Проблема кросскультурной релевантности методик самооценки способностей 1 13.91kb.
Представлено: сда 1 280.8kb.
Методические рекомендации Мариуполь, 2012 Успех состоит из деталей 1 154.26kb.
Задача Непрерывная случайная величина задана ее плотностью распределения 1 18.25kb.
Решение. Построим многоугольник распределения данной случайной величины. 1 26.39kb.
Исследование проблем релевантности бухгалтерской 1 87.89kb.
Направления изучения представлений о справедливости 1 202.17kb.

Распределения релевантности и ее оценок - страница №1/3

Распределения релевантности и ее оценок

Н.Е. Бузикашвили, Д.С. Гуревич, С.М. Карпенко, Д.В. Самойлов

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

1 Введение

Стандартная ситуация поиска состоит в том, что пользователь–человек обращается к поисковой системе с запросом, а поисковая система находит в своей базе документы, этому запросу, на ее взгляд, удовлетворяющие (релевантные), и возвращает пользователю их список. Представления пользователя о релевантности того или иного документа отличаются от представлений поисковой системы даже и в том случае, когда запрос сформулирован предельно ясно. Пока размер списка мал, важно только, чтобы истинно (т.е. на взгляд пользователя) релевантные документы попали в этот список. То, что они окажутся не в самом начале списка, не критично.

Однако с появлением больших баз данных и особенно интернета списки становятся необозримыми, а несовпадение упорядочений документов по истинной релевантности и упорядочений по ее оценкам, начисляемым поисковыми методами (машинами, например, Google, Yahoo и т.п.), критичным. Принципиально важно, чтобы, с одной стороны, высокорелевантные документы оказались в числе получивших высшие оценки, а с другой, чтобы изменение релевантности в упорядоченном поисковой машиной списке было достаточно монотонным, а нарушения монотонности либо непродолжительными (один–два документа), либо укладывающимися в ту — обычно неявную — модель поведения поисковой машины, которой так или иначе руководствуется пользователь, взаимодействуя с поисковой машиной.

Массово используемые в поисковых методах способы начисления оценок релевантности основаны на частотах входящих в запрос терминов (например, оценки Okapi или Inquery). При всей привлекательности концепции “семантической” обработки запроса, как и вообще введения семантических метрик, реального доступным полем в ближайшее время останется поверхностная синонимия. Но и в этом случае шкала, в которой выставляют оценки поисковые методы, является порядковой и потенциально бесконечнозначной, а среди документов, получивших оценку выше произвольного порога, подавляющее большинство будет иметь уникальные оценки.

Напротив, число градаций истинной релевантности до недавних пор считалось равным двум — “релевантен” и “нерелевантен”. В целом, и сегодня среди теоретиков информационного поиска большинство придерживается той точки зрения, что “бинарной релевантности вполне достаточно”. Вследствие веры в бинарность релевантности, вне поля изучения оказался такой объект как распределения релевантности, т.е. числа документов по градациям истинной релевантности. Напротив, распределения оценок релевантности (т.е. релевантности с точки зрения поисковых машин) изучаются если и не продуктивно, то давно и активно (см. например, [10],[12]).

Понятно, в случае бинарной релевантности нельзя ожидать никакого разнообразия распределений: число документов, релевантных осмысленному запросу, гораздо меньше числа нерелевантных. Однако необходимость в изучении распределений релевантности немедленно возникает, как только мы соглашаемся с тем, что число градаций релевантности может быть больше двух. Это исследование имеет далеко не только академическую мотивацию. Действительно, распределения релевантности, а как следствие, и распределения оценок релевантности самым существенным образом определяют как качество поиска с помощью отдельного метода (поисковой машины) [1], так и качество (используемого при метапоиске) основанного на рангах слияния списков документов, сформированных разными поисковыми машинами [2],[4].

Любой пользователь интернета попадал в ситуацию, когда первому запросу соответствуют десятки тысяч документов, его доуточнению — сотни документов, а следующему доуточнению — буквально 2–3 документа. Однако в другом случае последнее доуточнение лишь незначительно сокращает полученные на втором шаге сотни документов. Значит ли это, что любые ситуации возможны? А если нет, то какие возможны? Приведенный пример непосредственно имеет дело с распределением не (истинной) релевантности, а ее оценок, выставляемых поисковой машиной, тем не менее, вопрос о возможных типах распределений касается как самой релевантности, так и (ее отражающих) оценок.

Не существует никакой определенности относительно распределения “многозначной” релевантности даже применительно к тестовым базам [7]. Распределения релевантности до сих пор не подвергались регулярному исследованию, и в настоящий момент публикаций на эту тему нет (работа [3], развитием которой является настоящая статья, еще только должна появиться). Мы постараемся показать, что число типов распределений релевантности (и соответствующих распределений оценок) очень невелико. Бинарная релевантность порождает только один, очевидный тип распределения. Но оказывается, что и для более многозначных релевантностей число типов также ограничивается всего лишь несколькими. Мы перечислим эти типы и покажем, что с ростом числа градаций распределения сходятся к вариантам “экспоненциального”. В завершение, мы обсудим возможные виды распределений оценок релевантности (а этих видов в некотором смысле всего два) и покажем их отличие от традиционно используемого описания.



2 Комбинированная релевантность

Недостаточность бинарной релевантности стала очевидной с момента появления больших баз данных и интренета. В то же время в теории поиска информации по-прежнему господствует парадигма бинарной релеватности. Одна из причин состоит в довольно забавной интерпретации бинарной релевантности. Именно, как в случае оценок, выставленных поисковой машиной, так и в случае оценок, гипотетически выставляемых пользователем, речь идет не о релевантности, а о некоей вероятности быть релевантным, т.е. величине, измеряемой отнюдь не в порядковой и не двузначной шкале. Однако если оценки поисковой машины еще можно трактовать как субъективную (т.е. “с точки зрения поисковой машины”) меру релевантности, при этом не ставя под сомнение бинарность самой релевантности, то использование субъективной релевантности, измеряемой в непрерывной шкале, применительно к оценкам пользователя, выглядит по меньшей мере странно, поскольку эта субъективная мера и есть релевантность. Таким образом, бинарная релевантность оказывается не более (и не менее) чем псевдонимом непрерывно-значной релевантности.

В работах [7]–[9], [11] представлена доказательная база в пользу отказа от бинарной релевантности. В частности, в [7] убедительно показано, что результаты поиска для документов, относящихся к разным градациям 3-4 значной релевантности, различаются весьма существенно (при этом, в случае 4-значной релевантности, наименее выражены различия между первыми двумя наиболее релевантными градациями). Кроме того, сейчас документы в двух главных тестовых коллекциях размечены (или переразмечены заново) для каждого из запросов в 3-4-значной шкале (см. [10] для TREC и [4], [8] для NTCIR). Тем самым снимается последний, зыбкий, а в устах теоретиков еще и загадочный, довод в пользу бинарной релевантности, согласно которому, 99% документов в тестовых коллекциях размечены на бинарной шкале и потому модели поиска информации, использующие большее число градаций релевантности, ограничены рамками теоретических изысков. (Как будто для верификации модели необходимо, чтобы все ее параметры были явно наблюдаемы.) Обратим внимание на другое — что число градаций “многозначной” релевантности ни в одной из коллекций не превышает 4.

Априори существуют два способа изучения распределений релевантности — посредством наблюдения и посредством моделирования.

Первый путь возможен только применительно к тестовым коллекциям. В этом случае группа экспертов должна для каждого запроса оценить (assess) каждый документ тестовой базы по сколько-то значной шкале. При этом кто-то должен для каждого запроса решить, сколькозначная релевантность ему соответствует. Иначе пришлось бы прибегнуть к попарному сравнению всех документов, и таким путем одновременно разметить документы и выявить число градаций. Однако уже чисто технически это невозможно. Если же в результате прикидочного просмотра небольшого числа документов эксперты принимают решение о числе градаций, соответствующих данному запросу, и для каждой градации выбирают один или несколько документов-представителей, то теперь достаточно сравнить все документы базы только с документами-представителями. Тот факт, что способность человека различить релевантность пары документов ограничена, в действительности означает лишь, что число градаций релевантности как правило очень невелико.

Однако нет никакой уверенности что разметка документов по тому, насколько они релевантны сотням (десяткам) включенных в коллекцию запросов, даст представительную картину распределений релевантности. Еще более существенно, что в силу того, что запросы в тестовых коллекциях неявно отражают документную базу, полученные распределения можно рассматривать только как заведомо смещенные оценки распределений на реальных базах. И хотя среди входящих в коллекцию запросов очень мало коротких, которые характерны для обычных обращений пользователей [6], типичная доля высокорелевантных документов в коллекции составляет порядка одного процента. Что невероятно много и для простых запросов. Действительно, если база поисковой машины содержит несколько триллионов документов, то при тех же, что в тестовых коллекциях, пропорциях градаций релевантности число высокорелевантных документов равнялось бы в среднем десяткам миллионов, что противоречит нашему опыту.

Поэтому мы вынуждены отказаться от использования тестовых коллекций как (основного) источника знаний о распределениях релевантностей. Главным или единственным путем для изучения распределений релевантности оказывается их моделирование. Идея состоит в том, что, подобно тому как более сложный запрос представим как комбинация более простых, так и имеющая большее число градаций релевантность представима в виде комбинации релевантностей с меньшим числом градаций. Простейший запрос порождает релевантность, имеющую несколько (2–3) градаций. Число возможных распределений такой релевантности также невелико, а эти распределения, как и сама малозначная релевантность имеют абсолютно прозрачную интерпретацию. Комбинируя такие простейшие конфигурации, включающие шкалу релевантности и распределение на ней, мы получим более многозначные релевантности и соответствующие распределения документов. Свойства получаемых таким путем производных распределений автоматически выводятся из свойств комбинируемых простейших. (В скобках заметим, что значность релевантности, порождаемой запросом, определяется не только его длиной, но и типом. Так при поиске “на совпадение” запрос может содержать достаточно длинное название, но значений релевантности оказывается 2–3, т.е. мы имеем дело с релевантностями из базового набора.)

2.1 Базовый набор простейших конфигураций

Релевантность измеряется в линейной порядковой шкале. Все градации этой шкалы поименованы (например, “релевантный”, “частично релевантный” и “нерелевантный”) и перенумерованы по убыванию релевантности. Будем называть R-конфигурацией пару R-значная шкала релевантности и измеренное в грубых мерах (“примерно то же” и “существенно больше”) распределение документов на этой шкале. Таким образом, R-конфигурация задается тривиальным вектором предпочтений p (таким, что p1 > … > pR) и вектором распределения , где nr — число документов, относящихся к r-й градации релевантности.



Базовый набор конфигураций включает только два типа конфигураций: основанные на бинарной (“релевантен”и “нерелевантен”) и тернарной (“релевантен”, “частично релевантен” и “нерелевантен”) релевантности.

Бинарная релевантность порождает только один тип распределений:

B1. n1<<n2 (число релевантных документов n1 гораздо меньше числа нерелевантных n2)

На тернарной шкале имеются 4 существенно различных типа распределений:



T1. 0 < n1 << n2 << n3 (“экспоненциальное” распределение)

T2. 0 < n1n2 << n3 (‘’ обозначает однопорядковые величины, например, n1 = 2n2 или n1 = 0,7n1)

T3.1. n1 = 0, 0 < n2 << n3

T3.2. n2 = 0, 0 < n1 << n3

B1
















T1










T2










T3.1










T3.2





























































































































































































































































































1

2













1

2

3







1

2

3







1

2

3







1

2

3

Рис. 1. Распределения для базисных 2- и 3-конфигураций (‘’ обозначает однопорядковость, ‘’ — существенный рост)

3-конфигурации легко (и по–разному) интерпретируемы. Например, к первой градации можно отнести сами искомые документы и прямые указатели (links) на них, ко второй — документы, содержащие упоминания (references) этих документов, к третьей — документы без ссылок и упоминаний искомых. При поиске в интернете какой-нибудь классической работы мы сталкиваемся с конфигурацией T3.1. Эта конфигурация соответствует “старым объектам”. Напротив, только что созданным персональным страницам интернета соответсвует конфигурация T3.2. Она относится к поиску новых объектов (документов, областей и т.п.) и достаточно нетипична. В терминах 3-конфигураций, жизненный цикл печатных материалов в доинтернетевскую эру описывается как T3.2, затем T2, после чего, возможно, T1 и T3.1.

Ниже мы покажем, почему базис, по которому мы собираемся разлагать многозначные релевантности, должен включать 3-конфигурации, как и то любая R-конфигурация разлагается либо на (R-1)/2 3-конфигураций для нечетного R, либо одну 2-конфигурацию и R/2–1 3-конфигураций для четного R.

2.2 Многомерная комбинированная релевантность и ее линеаризация

Конфигурации для R>3 строятся как комбинации 2– и 3-конфигураций. Если запрос представляет собой комбинацию K (более простых) запросов, то релевантность, порождаемая этим запросом, измеряется в K-мерной порядковой шкале. Эта шкала описывается двумя K-мерными матрицами: предпочтений P и распределения A. Элемент есть число документов, которые одновременно r1-релевантны по 1-й шкале, r2-релевантны по 2-й шкале и т.д. для всех образующих комбинацию шкал. На K-мерной шкале любая градация доминирует над всеми градациями, расположенными “не выше и не левее” ее, доминируется всеми градациями “не ниже и не правее”, и несравнима с градациями “выше и правее” и “ниже и левее” (Рис. 2). Психологическая сложность сравнения релевантности вызвана не столько многозначностью (линейной) релевантности, сколько существованием для многомерной релевантности несравнимых градаций.

Однако релевантность должна (с точки зрения организации списка документов) быть измерена в линейной порядковой шкале. И человек часто с успехом справляется с линеаризацией многомерной релевантности. Естественное требование к линеаризации состоит в том, чтобы она не нарушала строгих отношений предпочтения, то есть если один документ релевантнее другого на многомерной шкале, то и на линеаризованной шкале он должен остаться более релевантным. Только одно, интуитивно ясное отображение удовлетворяет этому условию. Именно линеаризация состоит в объединении всех несравнимых градаций , лежащих на одной дискретной гиперплоскости . На рис. 3 градации 2-мерных релевантностей, лежащие на одних гиперплоскостях несравнимости, представлены одним цветом.























(i-1,j)










(i,j-1)

(i, j)

(i,j+1)










(i+1,j)






















следующая страница >>



Грустно быть козлом отпущения среди ослов. «Пшекруй»
ещё >>