Поисковые системы изнутри
Формальные компоненты поисковой системы
Логический метод определения множества претендентов
Ранжирование на основе вектора документа
Реалистичные модели ранжирования
Оценка качества документа на основе цитирования: алгоритм PageRank
Введение
В повседневной речи под термином «поисковая система» понимается программное обеспечение, состоящее из базы данных документов, снабженной пользовательским интерфейсом, позволяющим пользователю получить упорядоченное подмножество этих документов как ответ на его поисковый запрос. Основная задача поисковой системы заключается в выборе наилучшего возможного подмножества в ответ на конкретный запрос, то есть множества документов, которые оптимально соответствуют тому, что ищет пользователь (обычно в порядке убывания релевантности).
Самыми распространенными примерами поисковых систем, используемых повсюду, являются поисковые системы для Веба (такие как Google и Yahoo), которые применяются для обнаружения текстовой информации (например, документы в формате HTML и PDF), хранящейся на веб-серверах, расположенных по всему миру. Схожие технологии применяются и при поиске информации в корпоративных внутренних сетях.
Формальные компоненты поисковой системы
Большинство поисковых систем состоит из двух основных независимых компонентов: компонента индексирования и компонента поиска. Пользователю доступен только поисковый компонент. Компонент индексирования используется для создания внутреннего эффективного представления данных, в которых будет производиться поиск необходимой информации, а поисковый компонент отвечает за получение результатов из внутренней базы данных в ответ на поисковый запрос пользователя.
Компонент индексации выполняет функцию преобразования документов среды, в которой ведется поиск, в адекватное внутреннее представление поисковой системы. Множество документов, среди которых будет вестись поиск, называется универсумом. Для поисковой системы Интернета это страницы, которые мы загружаем из сети, для графической поисковой системы им будет являться набор изображений, а для академической поисковой системы универсум будет представлен, например, собранием работ, статей и книг. Множество документов, являющееся внутренним представлением универсума, называется репозиторием. Репозиторий, как правило, содержит документы с привязанными к ним соответствующими уникальными идентификаторами (их принято обозначать DOCID). Каждое представление документа из универсума в репозитории зависит в первую очередь от поисковой системы.
Рассмотрим компонент поиска, который обращается к документам, расположенным в репозитории для того, чтобы осуществить выборку, соответствующую поисковому запросу. Формально поисковый компонент может быть представлен как программа, реализующая преобразование поискового запроса, то есть конечной строки, введенной пользователем, во множество документов, релевантных этому запросу. Поисковый запрос принято считать состоящим из терминов, являющихся атомарными словами, поиск которых ведется, и операторов, описывающих способы интерпретации терминов. Например, в поисковом запросе «цепи Маркова» запрос состоит из терминов «Маркова» и «цепи». Оператором в данном случае будет являться логическое «И», что описывает ситуацию, когда нам необходимы документы, содержащие оба этих термина. Количество возвращаемых документов называется эффективностью поиска для данного поискового запроса.
Результат работы компонента поиска — это информация, предоставляемая пользователю. Элементы возвращаемого множества — это все документы, которые поисковая система сочла подходящими для включения в результирующий набор. Более того, элементы в результирующем множестве расположены в таком порядке, что первый считается более значимым для пользователя, чем второй, и т.д. Точность определяется долей возвращенных документов, которые фактически релевантны.
Здесь понятие релевантности является абсолютно произвольным и полностью зависит от поисковой системы (или, возможно, от ее пользователей).
Рассмотрим проблему получения результирующего множества документов на основании поискового запроса и репозитория. Поисковая система обычно осуществляет выборку в два этапа:
Выбор множества претендентов из репозитория — такого, что все элементы в нем в той или иной степени релевантны поисковому запросу. Определение релевантности на данном этапе очень приближенное. Например, может быть использован логический метод, рассматриваемый далее.
Для каждого документа множества претендентов определяется его релевантность, а затем множество сортируется в порядке уменьшения релевантности. В процессе сортировки некоторые элементы, имеющие релевантность ниже порогового значения, могут быть исключены из выборки.
Логический метод определения множества претендентов
Рассмотрим процесс определения множества претендентов, который обычно происходит с использованием логического метода. Основная идея данного метода заключается в том, что результирующее множество поискового запроса (такого, например, как «цепи Маркова») должно содержать только страницы, относящиеся ко всем уникальным терминам запроса (в данном случае ими будут являться «Маркова» и «цепи»). Затем ответ на поисковый запрос может быть дан после просмотра всех документов, содержащих термины «Маркова» и «цепи», используя документы, содержащие пересечение этих терминов как результирующее множество претендентов.
Так происходит по той причине, что основной задачей компонента индексации является построение инвертированного индекса, являющегося структурой данных, в которой терминам в соответствие ставятся документы (или DOCID), содержащие эти слова (как расширение, например, в поисковой системе изображений, термин «лицо» может быть привязан ко всем документам, которые классифицируются как содержащие лица).
В табл. 1 представлен пример инвертированного индекса. Инвертированный индекс является одной из важных частей вышеупомянутого внутреннего представления документов. Запрос, таким образом, подвергается декомпозиции в древовидную структуру с терминами (то есть атомарными словами или фразами) в качестве листьев и логическими операторами в качестве узлов.
Логическое сравнение является простым путем получения множества потенциально релевантных документов, но, конечно, не представляет их в порядке соответствия запросу.
Проблема ранжирования
В дальнейшем, после определения множества претендентов, происходит поиск зависимой от поискового запроса функции ранжирования или релевантности. Логический метод в той или иной мере применим к любому набору данных, однако проблема ранжирования в высшей степени зависит от окружения универсума, из которого данные были извлечены. Например, поисковые системы для веба постоянно сталкиваются с проблемой спама: веб-страницами, которые пытаются «перехитрить» поисковые системы, предоставляя необычайно высокое значение релевантности для конкурентоспособного термина поискового запроса и тем самым рассчитывая на увеличение количества появлений страницы в результатах поиска. Данная проблема приводит к тому, что функция определения релевантности должна определяться как можно тщательнее и скептически. Тем временем также не стоит отсеивать «честные» документы. Это приводит к тому, что решение проблемы ранжирования результатов в неконтролируемой среде становится очень востребованным и перспективным. Обычно спам не является проблемой в более контролируемых средах, таких как поисковые системы для академических работ или внутренних сетей.
Обратим внимание на особенности ранжирования в неконтролируемых средах, таких как Веб. Здесь функция ранжирования принимает в расчет как внешние факторы (on-page factors): информационное содержимое и его размещение на странице, так и внутренние факторы (inter-page factors): обычно информация о том, как страницы соотносятся с другими посредством гиперссылок, и т.п. Основное внимание следует уделить внутреннему фактору гиперссылок между страницами: предварительно проведем небольшой обзор процесса ранжирования в целом. Мотивацией к изучению внутренних факторов является то, что все внешние факторы находятся под полным контролем автора страницы. Изучение различных отношений внутри документа с гораздо большим числом страниц позволяет более гибко оценить качество исследуемой страницы.
Рассмотрим далее три возможных метода определения релевантности документов.
Логический метод ранжирования
Данный метод является самым тривиальным. Представим простейшую поисковую систему, принимающую значения внешних факторов всех страниц одинаковыми. Результирующее множество будет состоять исключительно из множества претендентов, отсортированных по убыванию значимости внутренних факторов страниц. Так функционирует чисто логическая поисковая система: все страницы, имеющие любое отношение к терминам, которые ищет пользователь, одинаково релевантны поисковому запросу.
Ранжирование на основе вектора документа
Подход к ранжированию с использованием вектора документа является достаточно популярной технологией.
Первым предположением в данной модели является то, что документ должен иметь высокий рейтинг по термину поискового запроса, если данный термин часто встречается на этой странице. Зададим частоту терминов (TF) как отношение количества появлений термина в документе к размеру документа в некоторых удобных единицах измерения (например, количество слов или байтов).
Далее предположим, что некоторые термины более значимы при поиске, чем другие. Стандартный метод определения значимости терминов заключается в нахождении инверсивной частоты документа (IDF). Инверсивная частота документа представляет собой оценку количества информации, свойственной термину. Если термин часто встречается в документах, находящихся в репозитории, то вероятность того, что он весьма общий, высока, и поиск определенного ресурса при помощи поисковой системы не даст значительных результатов, поэтому ему присваивается низкое значение IDF. В табл. 2 представлены примеры вычисленных значений IDF для некоторых терминов (в примере используются словосочетания), относящихся к хорошо известной теории множеств, но с возрастающей степенью обобщения и поэтому с убывающим количеством содержащейся в документах полезной информации.
TF и IDF будут применяться для определения оценки документа. Для каждого документа из множества претендентов определяется вектор документа, равный произведению TF и IDF.
Реалистичные модели ранжирования
Большинство поисковых систем в действительности используют улучшенную модель вектора документа. Тем не менее существует множество противников данной модели, поскольку самый существенный ее недостаток в том, что подход, использующий подсчет частоты вхождений терминов, может дать ошибочные результаты, поскольку количество слов на странице подсчитывается «вслепую». Поэтому вносятся корректирующие коэффициенты, основанные на таких факторах, как расположение терминов относительно друг друга, статистические измерения корреляции между термами и аспектами форматирования страницы (такими как шрифт и размер шрифта, которым представлены термины).
Одним из популярных методов ранжирования является OKAPI BM25 [2]. Данная функция пытается нормализовать рейтинги документов, исходя из их длины: большой документ может содержать гораздо больше повторений отдельных терминов, чем маленький, и, тем не менее, быть менее релевантным запросу.
Следующим улучшенным вариантом является функция OKAPI BM25F, в которой ранжирующая функция разбивается на части относительно полей документа, таких как заголовки, ссылки, основной текст и т.д.
Однако у всех представленных методов существует еще одна проблема. Пользователь, совершающий поиск, ожидает найти авторитетную информацию в результатах поиска раньше, чем всё остальное. Но в большинстве случаев стандартные слова в поисковом запросе не выделены особым образом на анализируемых при поиске страницах. Например, не все производители автомобилей используют слово «машина» на своих веб-сайтах! Более того, неавторитетные или даже вредоносные ресурсы могут легко обогнать авторитетные по рейтингу, просто используя термины по нескольку раз на своих страницах: к примеру, при поиске Volvo, главная страница компании Volvo будет находиться гораздо ниже в рейтинге, чем локальные дистрибьюторы автомобилей, использующие слово Volvo десятки раз у себя на страницах. Это не тот эффект, который необходим. Требуется решение, которое позволило бы оценивать качество страницы независимо от запроса.
Оценка качества документа на основе цитирования: алгоритм PageRank
Рассмотрим один из наиболее популярных и широко используемых методов оценки качества документов, основанный на ссылках между документами, — так называемый метод рейтинга цитируемости. Примерами цитат могут служить список цитированной литературы в научных работах или гиперссылки между веб-страницами. Идея рейтинга цитируемости заключается в определении качественной оценки документа на основании количества и качества ссылающихся на него документов.
Алгоритм PageRank можно рассматривать как модель поведения пользователя. Предполагается, что веб-серфер (пользователь, «путешествующий» по веб-страницам, то есть переходящий по ссылкам с одной страницы на другую) с заданной случайным образом стартовой страницы переходит по ссылкам (снова выбирая их случайным образом) на другие страницы и никогда не возвращается на предыдущую страницу, иногда прерывая переход по ссылкам и начиная снова с другой случайной страницы. Вероятность того, что веб-серфер посетит определенную страницу, и является ее рейтингом PageRank. А коэффициент затухания определяет, как скоро веб-серфер начнет процесс заново, перейдя на случайную страницу. Единственное важное различие в задании фактора затухания заключается в том, что он может быть присвоен как группе страниц, так и отдельным страницам. Данный подход позволяет персонализировать выборку и сводит к минимуму вероятность того, что система ошибется, присваивая странице рейтинг. Существует несколько расширений алгоритма Page Rank, описанных в [5].
Другое наглядное обоснование того, что страница может иметь высокий рейтинг PageRank, заключается в определении количества страниц, ссылающихся на нее и также имеющих высокий рейтинг PagRank. Таким образом, страницы, на которые ссылается множество документов в Вебе, являются более предпочтительными. Кроме того, страницы, имеющие хотя бы одну ссылку, например, с домашней страницы Yahoo! являются более предпочтительными. Если ссылка на страницу не работает или страница низкого качества, то маловероятно, что домашняя страница Yahoo! будет ссылаться на нее. PageRank анализирует подобные ситуации, а также рекурсивные ссылки нескольких страниц, посредством которых их владельцы пытаются повысить их рейтинг.
Анкерный текст
Рассмотрим некоторые особенности поисковой системы Google, основой которой является алгоритм PageRank. В поисковой системе Google анкерный текст обрабатывается особым образом. Анкером называется слово или группа слов (фраза), к которым привязана гипертекстовая ссылка. Большинство поисковых систем связывают текст ссылки со страницей, на которой эта ссылка находится. В Google анкерный текст также ассоциируется со страницей, на которую эта ссылка указывает. Данный подход имеет несколько преимуществ в силу того, что анкеры обрабатываются особым образом. Во-первых, анкеры содержат более точное описание страниц, чем сами страницы. Во-вторых, анкеры могут описывать документы, которые не могут быть проиндексированы системой без графического интерфейса, такие как изображения, приложения и базы данных. Таким образом, становится возможным отбирать веб-страницы, которые фактически не были проиндексированы.
Идея привязки анкерного текста к странице, на которую он ссылается, впервые была реализована в World Wide Web Worm [6] именно из-за того, что данный подход позволяет находить информацию, представленную не в виде текста, а также расширяет возможности стандартной поисковой системы. В Google используют анкерную привязку в основном для того, чтобы получить наиболее качественную выборку. Эффективное применение анкерного текста очень проблематично с технической точки зрения: необходимо обрабатывать огромное количество информации. К примеру, для репозитория, содержащего 24 млн страниц, было проиндексировано более 259 млн анкеров [3].
Заключение
Поиск информации в гетерогенной среде, такой как World Wide Web, является актуальной задачей, для которой существует множество методов решения. При поиске данных в репозитории поисковой системы производится выборка проиндексированных документов и определяется их релевантность поисковому запросу, введенному пользователем. Если для определения множества претендентов для выборки подходит логический метод, то для определения релевантности документов используются гораздо более сложные методы, самым эффективным из которых является алгоритм PageRank. Этот алгоритм основан на анализе как ссылок, исходящих из документа, так и документов, ссылающихся на него. При этом также производится оценка качества ссылающихся документов.
Тем не менее перед поисковыми системами стоит множество проблем, таких как спам и ситуации, когда создатель страницы добавляет искусственную избыточную информацию с целью повысить рейтинг своей страницы. Кроме того, существуют проблемы анализа документов, не имеющих текстовой информации (таких как изображения или мультимедиа). Для их решения используются различные подходы, которые применяются в крупных поисковых системах и являются коммерческой тайной разрабатывающих компаний. В настоящее время ведется активная работа над существующими методами поиска, направленная на их оптимизацию.
Литература
- Shannon, C.E. A mathematical theory of communication. Bell Syst. Tech. J. 27 (1948).
- Sparck-Jones, K., Walker, S., Robertson, S.E. A probabilistic model of information retrieval: Development and comparative experiments. Inf. Process. Manag. 36(6), 779-808. 2000.
- Brin, S., Page, L. The anatomy of a large-scale hypertextual Web search engine // Proceedings of the 7th International World Wide Web Conference, 1998.
- Page, L., Brin, S., Motwani, R., Winograd, T. The PageRank Citation Ranking: Bringing Order to the Web // Stanford Digital Libraries Working Paper. Stanford University, 1998.
- Page, L., Brin, S., Motwani, R., Winograd, T. The PageRank Citation Ranking: Bringing Order to the Web. Manuscript in progress // http://google.stanford.edu/~backrub/pageranksub.ps.
- Oliver A., McBryan. GENVL and WWWW: Tools for Taming the Web. First International Conference on the World Wide Web. CERN, Geneva (Switzerland), May 25-27, 1994 // http://www.cs.colorado.edu/home/mcbryan/mypapers/www94.ps.
 |
|
