Поисковые системы в исторической перспективе

ОЦЕНКА КАЧЕСТВА Consistency checking has shown that the overlap of relevant documents

between any two assesors is on the order of 40% on average…crossassesor recall and precision of about 65% …This implies a practical upper bound on retrieval system performance of 65% …5

Donna Harman What we have learned, and not learned, from TREC [harman] 3 для больших коллекций число «смыслов» увеличивают до 300 4 После наших экспериментов с LSI получилось, что «смысл номер 1» в Рунете - все англоязычные документы, «смысл номер 3» – все форумы и т.п. 5 «...проверка устойчивости показала, что перекрытие релевантных документов между любыми двумя асессорами примерно 40% в среднем ... точность и полнота измеренная между асессорами около 65% ... Это накладывает практическую верхнюю границу на качество поиска в районе 65%...» Какова бы ни была модель, поисковая система нуждается в «тюнинге» - оценке качества поиска и настройке параметров. Оценка качества – идея, фундаментальная для теории поиска. Ибо именно благодаря оценке качества можно говорить о применимости или не применимости той или иной модели и даже обсуждать их теоретичеcкие аспекты.  В частности, одним из естественных ограничений качества поиска служит наблюдение, вынесенное в эпиграф: мнения двух «асессоров» (специалистов,  выносящих вердикт о релевантности) в среднем не совпадают друг с другом в очень большой степени! Отсюда вытекает и естественная верхняя граница качества поиска, ведь качество измеряется по итогам сопоставления с мнением асессора.  Обычно6 для оценки качества поиска меряют два параметра:  • точность (precision) – доля релевантного материала в ответе поисковой системы • полнота (recall) – доля найденных релевантных документов в общем числе релевантных документов коллекции Именно эти параметры использовались и используются на регулярной основе для выбора моделей и их параметров в рамках созданной Американским Интститутом Стандартов (NIST) конференции по оценке систем текстового поиска (TREC – text retrival evaluation conference)7. Начавшаяся в 1992 году консорциумом из 25 групп,  к 12-му году своего существования конференция накопила значительный материал,  на котором до сих пор оттачиваются поисковые системы. К каждой очередной конференции готовится новый материал (т.н. «дорожка») по каждому из интересующих направлений. «Дорожка» включает коллекцию документов и запросов. Приведу примеры:

 • Дорожка произвольных запросов (ad hoc) – присутствует на всех конференциях • Многоязычный поиск

• Маршрутизация и фильтрации

• Высокоточный поиск (с единственным ответом, выполняемый на время)  • Взаимодействие с пользователем

• Естестственно-языковая «дорожка»

• Ответы на «вопросы»

• Поиск в «грязных» (только что  отсканированных) текстах

• Голосовой поиск

• Поиск в очень большом корпусе (20GB, 100GB и т.д.)

• WEB корпус (на последних конференциях он представлен выборкой по домену

.gov)

• Распределенный поиск и слияние результатов поиска из разных систем

6 но не обязательно – есть и «альтернативные» метрики!

7 материалы конференции публично доступны по адресу trec.nist.gov/pubs.html

НЕ ТОЛЬКО ПОИСК

Как видно из «дорожек» TREC, к самому поиску тесно примыкает ряд задач, либо разделяющих с ним общую идеологию (классификация, маршрутизация,  фильтрация, аннотирование), либо являющихся неотъемлемой частью поискового процесса (кластеризация результатов, расширение и сужение запросов, обратная '84Ќ{связь, «запросо-зависимое» аннотирование, поисковый интерфейс и языки запросов). Нет ни одной поисковой системы, которой бы не приходилось решать на практике хотя бы одну из этих задач.  Зачастую наличие того или иного дополнительного свойства является решающим доводом в конкурентной борьбе поисковых систем. Например, краткие аннотации состоящие из информативных цитат документа, которыми некоторые поисковые системы сопровождают результаты соей работы, помогают им оставаться на полступеньки впереди конкурентов.  Обо всех задачах и способах их решения рассказать невозможно. Для примера рассмотрим «расширение запроса», которое обычно производится через привлечение к поиску ассоциированных терминов. Решение этой задачи возможно в двух видах – локальном (динамическом) и глобальном (статическом). Локальные техники опираются на текст запроса и анализируют только документы, найденные по нему. Глобальные же «расширения» могут оперировать тезаурусами, как априорными (лингвистическими), так и построенными автоматически по всей коллекции документов. По общепринятому мнению, глобальные модификации запросов через тезаурусы работают неэффективно, понижая точность поиска. Более успешный глобальный подход основан на построенных вручную статических классификациях, например, ВЕБ-директориях. Этот подход широко использутся в интернет-поисковиках в операциях сужения или расширения запроса.  Нередко реализация дополнительных возможностей основана на тех же самых или очень похожих принципах и моделях, что и сам поиск. Сравните, например,  нейросетевую поисковую модель, в которой используется идея передачи затухающих колебаний от слов к документам и обратно к словам (амплитуда первого колебания – все тот же TF*IDF), с техникой локального расширения запроса. Последняя основанна на обратной связи (relevance feedback), в которой берутся наиболее смыслоразличительные (контрастные) слова из документов,  принадлежащих верхушке списка найденного.  К сожалению, локальные методы расширения запроса, несмотря на эффектные технические идеи типа «Term Vector Database» [stata] и очевидную пользу, все еще остаются крайне «дорогим»8 удовольствием. 8 в смысле вычислительных ресурсов

ЛИНГВИСТИКА

Немного в стороне от статистических моделей и структур данных стоит  класс алгоритмов, традиционно относимых к лингвистическим. Точно границы между статистическим и лингвистическими методами провести трудно. Условно можно считать лингвистическими методы, опирающиеся на словари (морфологические,  синтаксические, семантические), созданные человеком. Хотя считается доказанным, что для некоторых языков лингвистические алгоритмы не вносят существенного прироста точности и полноты (например, английский) [strzalkowski], все же основная масса языков требует хотя бы минимального уровня лингвистической обработки. Не вдаваясь в подробности, приведу только список задач, решаемый лингвистическими или окололингвистическими приемами:  • автоматическое определение языка документа

• токенизация (графематический анализ): выделение слов, границ предложений

• исключение неинформативных слов (стоп-слов)

• лемматизация (нормализация, стемминг): приведение словоизменительных

форм к «словарной». В том  числе и для слов, не входящих в словарь системы

• разделение сложных слов (компаундов) для некоторых языков (например,

немецкого)

• дизамбигуация: полное или частичное снятие омонимии

• выделение именных групп

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

ПОИСК В ВЕБЕ

“Things that work well on TREC often do not produce good results on the web ... Some argue that on the web, users should specify more accurately what they want and add more words to their query. We disagree vehemently with this position. If a user issues a query like "Bill Clinton" they should get reasonable results since there is a enormous amount of high quality information available on this topic”9

Sergei Brin, Larry Page

The Anatomy of a Large-Scale Hypertextual Web Search Engine [*]

http://www7.scu.edu.au/programme/fullpapers/1921/com1921.htm

"I was struck when a Google person told me at SIGIR that the most recent Google ranking algorithm completely ignores anything discovered at 9 ... то, что хорошо работает в TREC часто не срабатывает в вебе ... некоторые утверждают, что в вебе пользователи обязаны более точно специфицировать то, что им нужно, писать побольше слов в запросах. Мы категорически не согласны с такой точкой зрения. Если люди спрашивают «Билл Клинтон» они должны получать осмысленные результаты, так как в вебе полным полно качественной информации на эту тему.... Сергей Брин, Ларри Пейдж TREC, because all the good Ad Hoc ranking algorithms developed over the 10 years of TREC get trashed by spam"10

Mark Sanderson [*]

http://groups.yahoo.com/group/webir/message/710

Пора вернуться к теме, с которой  началась эта статья: что же изменилось поисковых системах за последнее время?  Прежде всего, стало очевидно, что поиск в вебе, не может быть сколько-нибудь корректно выполнен, будучи основан на анализе (пусть даже сколь угодно глубоком, семантическом и т.п.) одного лишь текста документа. Ведь внетекстовые (off-page) факторы играют не меньшую, а порой и бо́льшую роль,  чем текст самой страницы. Положение на сайте, посещаемость, авторитетность источника, частота обновления, цитируемость страницы и ее авторов – все эти факторы невозможно сбрасывать со счета.  Cтав основным источником получения справочной информации для человеческого вида, поисковые системы стали основным источником трафика для интернет- сайтов. Как следствие, они немедленно подверглись «атакам» недобросовестных авторов, желающих любой ценой оказаться в первых страницах результатов поиска. Искусственная генерация входных страниц, насыщенных популярными словами, техника клоакинга, «слепого текста» и многие другие приемы,  предназначенные для обмана поисковых систем, мгновенно заполонили Интернет.  Кроме проблемы корректного ранжирования, создателям поисковых систем в Интернете пришлось решать задачу обновления и синхронизации колоссальной по размеру коллекции с гетерогенными форматами, способами доставки, языками,  кодировками, массой бессодержательных и дублирующихся текстов. Необходимо поддерживать базу в состоянии максимальной свежести (на самом деле достаточно создавать иллюзию свежести - но это тема отдельного разговора), может быть учитывать индивидуальные и коллективные предпочтения пользователей. Многие из этих задач никогда прежде не рассматривались в традицонной науке информационного поиска.  Для примера рассмотрим пару таких задач и практических способов их решения в поисковых системах для интернета.

Качество ранжирования

Не все внетекстовые критерии полезны  в равной мере. Именно ссылочная популярность и производные от нее оказались решающим фактором, поменявшим в 1999-2000 мир поисковых систем и вернувший им преданность пользователей.  Так как именно с ее помощью поисковые системы научились прилично и самостоятельно (без подпорок из вручную отредактированных результатов) 10 ... я был потрясен, когда кто-то из Гугля сказал мне, что они вообще не используют ничего наработанного в TREC, потому что все алгоритмы заточеные на дорожке «произвольных запросов»  спам рашибает вдребезги... Марк Сандерсон ранжировать ответы на короткие частотные запросы, составляющие значительную часть поискового потока.  Простейшая идея глобального (т.е. статического) учета ссылочной популярности состоит в подсчете числа ссылок, указывающих на страницы. Примерно то, что в традиционном библиотековедении назвают индексом цитирования. Этот критерий использовался в поисковых системах еще до 1998 года. Однако он легко подвергается накрутке, кроме того, он не учитывает вес самих источников.  Естественным развитием этой идеи можно считать предложенный Брином и Пейджем в 1998 году алгоритм PageRank [brin] – итеративный алгоритм, подобный тому, что используется в задаче определения победителя в шахматной турнире по швейцарской системе. В сочетании с поиском по лексике ссылок, указывающих на страницу (старая, весьма продуктивная идея, которая использовалась в гипертекстовых поисковых системах еще в 80-е годы), эта мера позволила резко повысить качество поиска.  Немного раньше, чем PageRank, был предложен локальный (т.е. динамический,  основанный на запросе) алгоритм учета популярности – HITS [kleinberg],  который11 не используется на практике в основном из-за вычислительной дороговизны. Примерно по той же причине, что и локальные (т.е. динамические)  методы, оперирующие словами.  Оба алгоритма, их формулы, условия сходимости подробно описаны, в том числе и в русскоязычной литературе. Отмечу только, что расчет статической популярности не является самоценной задачей, он используется в многочисленных вспомогательных целях: определение порядка обхода документов, ранжирование поиска по тексту ссылок и т.д. Формулы расчета популярности постоянно улучшают, в них вносят учет дополнительных факторов: тематической близости документов (например, популярная поисковая система www.teoma.com), их структуры, и т.п., позволяющие понизить влияние непотизма. Интересной отдельной темой является эффективная реализация соответствующих структур данных [bharat]

Качество индекса

Хотя размер базы в интернете  на поверхностный взгляд не кажется  критическим фактором, это не так. Недаром рост посещаемости таких машин, как Google и Fast хорошо коррелируют именно с ростом их баз. Основная причины: «редкие»  запросы, то есть те, по которым находится менее 100 документов, составляют в сумме около 30% от всей массы поисков – весьма значительную часть. Этот факт делает размер базы одним из самых критичных параметров системы.  Однако рост базы, кроме технических проблем с дисками и серверами,  ограничивается логическими: необходимостью адекватно реагировать на мусор,  повторы и т.п. Не могу удержаться, чтобы не описать остроумный алгоритм, 11 точнее производные от него, так как сам алгоритм оказался не очень устойчив

применяемый в современных поисковых системах для того, чтобы исключить  «очень похожие документы».  Происхождение копий документов в Интернете может быть различным. Один и тот же документ на одном и том же сервере может отличаться по техническим причинам: быть представлен в разных кодировках и форматах; может содержать переменные вставки – рекламу или текущую дату.  Широкий класс документов в вебе активно копируется и редактируется – ленты новостных агентств, документация и юридические документы, прейскуранты магазинов, ответы на часто задаваемые вопросы и т.д. Популярные типы изменений: корректура, реорганизация, ревизия, реферирование, раскрытие темы и т.д. Наконец, публикации могут быть скопированы с нарушением авторских прав и изменены злонамеренно с целью затруднить их обнаружение.  Кроме того, индексация поисковыми машинами страниц, генерируемых из баз данных, порождает еще один распространенных класс внешне мало отличающихся документов: анкеты, форумы, страницы товаров в электронных магазинах Очевидно, что с полными повторами проблем особых нет, достаточно сохранять в индексе контрольную сумму текста и игнорировать все остальные тексты с такой же контрольной суммой. Однако этот метод не работает для выявления хотя бы чуть-чуть измененных документов.  Для решения этой задачи Udi Manber (Уди Манбер) (автор известной программы приближенного прямого поиска agrep) в 1994 году предложил идею [manber1994],  а Andrei Broder (Андрей Бродер) в 1997 [broder] придумал название и довел до ума алгоритм «шинглов» (от слова shingles, «черепички, чешуйки»). Вот его примерное описание.  Рис. 2

Для каждого десятисловия текста рассчитывается контрольная сумма (шингл).  Десятисловия идут внахлест, с перекрытием, так, чтобы ни одно не пропало. А затем из всего множества контрольных сумм (очевидно, что их столько же, сколько слов в документе минус 9) отбираются только те, которые делятся на, скажем, 25.  Поскольку значения контрольных сумм распределены равномерно, критерий выборки никак не привязан к особенностям текста. Ясно, что повтор даже одного десятисловия – весомый признак дублирования, если же их много, скажем, больше половины, то с определенной (несложно оценить вероятность) уверенностью можно утверждать: копия найдена! Ведь один совпавший шингл в выборке соответствует примерно 25 совпавшим десятисловиям в полном тексте!  Очевидно, что так можно определять процент перекрытия текстов, выявлять все его источники и т.п. Этот изящный алгоритм воплотил давнюю мечту доцентов:  отныне мучительный вопрос «у кого студент списывал этот курсовик» можно