Эффективность ранжирования пассажей как одного из способов поиска информации в текстовых коллекциях

От редакции: Сегодня мы публикуем первую часть материала, посвященного методам ранжирования пассажей. Статья будет интересна как разработчикам поисковых систем, так и оптимизаторам. Так как авторы статьи австралийские ученые, некоторые употребляемые в материале термины являются дословным переводом с английского. Мы намеренно не стали заменять их близкими по смыслу терминами, употребляемыми в российском мире SEO, дабы сохранить изначальный смысл исследования.

Аннотация

Запросы в текстовые коллекции выполняются путем ранжирования документов в коллекции, пользователю предоставляются документы с наивысшей оценкой. Альтернативным поисковым методом является ранжирования пассажей (небольших фрагментов документа). Данный метод рассчитан улучшать эффективность выдачи и определять релевантность материала документов больших размеров. Однако метод ранжирования пассажей может значительно увеличить затраты на поиск. В данной работе будут рассмотрены альтернативные и разработаны новые способы оценки запросов. Экспериментально будет показано, что правильно выбранный способ поиска пассажей представляет собой конструктивное решение для ПК с ограниченным объемом памяти. Сравнив поиск пассажей с известными алгоритмами ранжирования документов, было определено, что новому алгоритму ранжирования пассажей \DO-TOS" необходима лишь часть источников.

Введение

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

С появлением Интернета и онлайн-систем обработки документов, наблюдается стремительное увеличение количества пользователей, имеющих доступ к базе текстовых данных. Это привело к разработке новых, эффективных алгоритмов индексации и оценки релевантности запросов, которые позволяют выполнить запрос намного быстрее, используя меньшее количество источников, по сравнению технологиями прошлых лет. Новые методы предполагают уменьшение размера индекса и размера текста, использование методов сжатия, эвристических правил, что значительно уменьшает количество документов, которые могут стать возможными ответами на каждый запрос.

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

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

В данной работе, сначала рассматриваются базовые способы оценки запросов, включая document-ordered или DO processing, где инвертированные списки обрабатываются одновременно, term-ordered или TO processing, где каждый инвертированный список обрабатывается последовательно. А также skipping или TOS стратегии, предполагающие ограничение числа потенциальных документов, рассмотренных во время оценки запроса. Для ранжирования всего документа предыдущий анализ предполагает, что для ограниченного объема памяти DO оценка представляется более эффективной, чем TO. Используя MG прототип системы текстовой базы, экспериментально сравнили TO, TOS и DO. Результаты исследования показали, что для коротких запросов эффективнее DO, а не TO. Однако для других запросов предпочтительнее использовать способ DO, оценка запроса TO является более оперативной. Однако для ранжирования документов оба способа уступают способу оценки TOS.

В дальнейшем будет рассмотрено соответствие каждого способа оценки для поиска пассажей и предложены рекомендации по практическому поиску пассажей. На основе экспериментов, все способы будут оценены по степени результативности и степени экономичности. Результаты экспериментов докажут практическую полезность ранжирования пассажей для коротких запросов в больших коллекциях, оцененных в ограниченном объеме памяти за первые секунды. Для достаточной памяти, результативными представляются и TOS, и DO, для того, чтобы выполнить обычное поисковое задание – предоставить список из 10-20 документов, – объем памяти не должен быть большим. Также будет доказано, что для ранжирования всего документа и для длинных запросов затраты на оценку запроса способом DO увеличиваются быстрее, чем способом TOS. Для коротких запросов способ DO считается более эффективным. Мы рекомендуем использовать комбинированный метод DO-TOS, где DO processing используется для определения набора похожих документов, основанных на редких терминах запросов, а TOS processing упорядочивает заново данный набор документов.

Текстовый поиск

В поисковых системах документы ранжируются по функции эвристического подобия, определяющей степень релевантности документа запросу. Оценка осуществляется при помощи вычисления релевантности каждого документа запросу, после чего выдается k документов с наивысшей оценкой подобия. Было предложено много функций подобия, наиболее распространенной и эффективной является косинусная оценка:

C(q; d) = Pt2q^d(wq;t _ wd;t)
Wd
где q - запрос, d - документ,
Wd = pX
t2d
w2
d;t ;
wd;t = loge(fd;t + 1) ;
wq;t = loge(fq;t + 1) _ loge(N=ft + 1)

Показатель fx;t – это число вхождений термина t в x (запрос или документ в запросе); присутствует N документов; ft- число уникальных документов, содержащих t; уравнение (N=ft + 1) – «обратная частота документов», редкость нахождения t в коллекции. Сравнив с косинусными формулировками, где были сделаны такие улучшения как стандартизация длины сходных документов, было обнаружено, что в тестовых данных, представленных в данной работе, вышеуказанная формулировка достигает той же результативности.

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

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

Следующим способом улучшения является использование релевантной обратной связи, где пользователям представлены небольшое количество ответов, из которого можно выбрать нужный. Система может эвристически выбрать из данных документов дополнительные термины запроса. Данный способ представляется удачным, т.к. одно и то же понятие может быть выражено по-разному, а релевантные запросу документы могут представить пользователю новые формулировки интересующего его понятия. Эксперименты показали, что расширение запроса приводит к улучшению выдачи. Однако на практике расширение запроса имеет недостатки: увеличивается число терминов запроса, что приводит к увеличению затрат на оценку запроса.

Поиск пассажей

Альтернативой текстовому поиску является поиск пассажей или небольших частей документа. Ранжирование может осуществляться либо по выборке документов, имеющих наиболее релевантные пассажи, либо по выборке самих пассажей. Несмотря на то, что поиск пассажей предполагает поиск только части документа, он имеет некоторые преимущества: в пассажах термины запроса могут быть приблизительными; нет проблемы нормализации, если пассажи одной длинны; пассажи являются указателями релевантности больших документов; пассажи удобны для презентации пользователю.

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

В литературе предложено много определений понятия «пассаж», включая пассажи, основанные: на разметке документа на разделы, параграфы и группы предложений; на последовательности параграфов одной длины; на словах в фиксированной по длине последовательности, которые могут рассматриваться по отдельности или комплексно. Некоторые из этих определений основаны на семантических свойствах, например, границы предложений. Можно предположить, что пассажи, основанные на блоках текста, обеспечат основу поиска. По результатам исследования, наибольшая поисковая результативность достигается с помощью пассажей, состоящих из фиксированной по длине последовательности слов. Также результаты демонстрируют, что, принимая во внимание даже простейшие структуры, например, абзацы и границы предложения, эффективность значительно снижается; использование подобной структуры предполагает ее точное определение и повторное представление проблем, таких как нормализация длины.

Для FR подраздела TREC (Text REtrieval Conference), которая состоит из документов различной длины (объема), было продемонстрировано, что использование совпадающих пассажей из 150-300 слов значительно улучшают эффективность. Для TREC были отмечены менее значительные, но последовательные улучшения. Как поисковый механизм первого уровня, данные результаты показывают, что пассажи являются лучшим способом оценки подобия целого документа. Доказано, что наивысшая эффективность достигается, если пассажи могут быть выбраны из любой части документа, если нет, то с интервалами в 25 слов, тогда ухудшения незначительные.

Подобный результат получается и для небольших запросов, если использовать способ разметки. Кларк (Clarke) использует булевые запросы для определения сегментов документов, которые удовлетворяют булевым условиям. Подобие документов основывается на самых коротких сегментах, подходящих булевому запросу, оценивающих сегменты текста по их абсолютной длине. Никаких статистических данных коллекции не требуется, однако на начальном этапе данного исследования был необходим ручной труд для введения булевых запросов. Все термины запроса обрабатывались эквивалентно. Способ, не предполагающий использование ручного труда, был представлен в 1998 на конференции TREC. Запросы на естественном языке использовались для генерации набора булевых запросов, выстроенных по уменьшению числа терминов: первый запрос – все слова, второй – все кроме слова с наивысшим IDF и т.д. Пока данный способ представляется эффективным для коротких запросов, и находится в стадии разработки.

Пассажи имеют лишь один недостаток: велики затраты на их оценку. Число подходящих пассажей в несколько раз больше, числа подходящих документов, поэтому использование данного способа может оказаться практически нецелесообразным. Однако, как упоминалось выше, иногда нет логического деления текста на документы, и для коллекций больших пассажей документов обеспечивается большая эффективность, чем при использовании альтернативных способов.

Марчин Казкиел (Marcin Kaszkiel), Джастин Зобель (Justin Zobel), Рон Сакс-Дэвис (Ron Sacks-Davis)
Университет RMIT, Мельбурн, Австралия.

Перевод под редакцией Анны Макаровой.