itmo_conspects

Лекция 2. Классический поиск и вероятностное ранжирование

Основы поиска информации

Поисковые системы начали свое развитие с каталогов. При появлении новой страницы она заносится в каталог, где перечислены страницы по алфавиту или сгруппированы по категориям

Когда число страниц в 1990 году стало настолько огромным, что вручную их нельзя было перечислить, появилась первая поисковая система - Archie. Ее создал студент Алан Эмтедж из университета Макгилла для поиска среди файлов, размещенных на FTP-серверах. Тогда появился подход предварительного построения поискового индекса для оптимизации времени поиска

Далее с развитием всемирной сети Интернет студент Массачусетского института технологий Мэттью Грей в 1993 году разработал программу World Wide Web Wanderer - веб-робота, который бродил по страницам и собирал информацию о них. Полученная база данных получила название Wandex

В 1994 году была представлена аналогичная поисковая система - ALIWEB (Archie Like Indexing for the WEB), но для работы которой владельцы сайтов должны были сами зарегистрировать свои страницы

Далее в середине 1990-ых появляются массовые поисковые системы: Yahoo! в 1994, Lycos в 1994, AltaVista в 1995. В России появились системы Рамблер и Апорт в 1996 году

Затем, несмотря на быстрый поиск, появилась другая проблема: какие страницы показывать пользователю первыми?

Чтобы решить эту проблему Ларри Пейдж и Сергей Брин предложили учитывать структуру гиперссылок, которые ведут на другие документы, в алгоритме PageRank, описанном в 1998 году, для поисковой системы BackRub. Позднее BackRub будет переименован в Google

К середине 2000-ых годов основные задачи полнотекстового поиска были решены, поэтому развитие поисковых систем происходило в других направлениях:


Поиск делится на два этапа:

Ключевую роль в оптимизации поиска играет индексация, в ходе которой данные подготавливаются в такую структуру, в которой запрос на поиск занимает наименьшее время

В более усовершенствованных системах поиск среди множества документов делится на несколько этапов:

  1. Стадия отбора кандидатов (Candidate Retrieval), цель которой - это отобрать за 5-15 миллисекунд с помощью быстрых алгоритмов из миллионов документов тысячу потенциально подходящих. Для этого используют лексический поиск (например, поиск по инвертированному индексу или вероятностные формулы совпадения слов) и поиск приближенных соседей (ANN)
  2. Стадия тяжелого переранжирования (Reranking), в которой нужно отсортировать по релевантности эту тысячу документов. Здесь применяются деревья решений с градиентным бустингом
  3. Стадия постобработки и финального показа, где отбираются 10 или 20 лучших для пользователя результатов

Поиск данных (Data Retrieval) - это поиск объектов в структурированных данных по формально заданным условиям, например, SELECT-запрос в базах данных SQL

С математической точки зрения поиск данных сводится к вычислению предиката \(f(d) = \begin{cases} 1, & \text{если } d \in R, \\ 0, & \text{если } d \notin R, \end{cases}\), где $d$ - это объект базы данных, а $R$ - множество объектов, удовлетворяющих запросу

Здесь все найденные записи равноправны, то есть предикат не определяет их порядок

Задача информационного поиска состоит иначе - вместо формализованного запроса, для которого легко построить алгоритм, есть текстовый запрос, который должен по смыслу соответствовать интересующим пользователя документами

Информационный поиск (Information Retrieval, IR) - это область информатики, которая изучает методы поиска документов, удовлетворяющих информационной потребности пользователя, из большой коллекции, при этом документы чаще всего не имеют единой четкой структуры

Запрос - это формализованный способ выражения информационной потребности с использованием средств естественного языка (то есть слов), при этом одна и та же потребность может быть сформулирована разными запросами

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

Критерием поиска выступает степень соответствия запросу, по которому можно сделать ранжирование объектов поиска


Булева модель исторически является первой и математически строгой моделью информационного поиска:

Такая модель детерминирована (то есть результат воспроизводим), но в ней нет встроенного ранжирования, то есть документ, где термин встретился 50 раз, не отличается от документа с одним упоминанием. Кроме того, возникает “проблема ловушки выдачи”: строгий AND часто возвращает ноль документов из-за переограничения, а широкий OR - миллионы из-за недоограничения

Наивный подход к булеву поиску - это полнотекстовое сканирование (наподобие утилиты grep). Сложность такого подхода составляет $O(N \cdot L)$, где $N$ - число документов, а $L$ - средняя длина документа, что очень много: на корпусе из $10^7$ документов запрос может выполняться десятки секунд или минуты, операция NOT требует чтения всего объёма данных без ранней остановки, а обработка регулярных выражений и связок операторов масштабируется линейно с ростом базы

Первая концептуальная структура для ускорения поиска - это терм-документная матрица инцидентности. Строки соответствуют уникальным словам словаря корпуса $V$, а столбцы - идентификаторам документов $D$. Если в ячейке $A_{t,d}$ матрицы значение 1, то термин $t$ присутствует в документе $d$. Логические операции транслируются в побитовые операции процессора, которые могут выполняться параллельно на уровне регистров

Проблема масштаба связана с разреженностью матрицы: если $N=1000000$ документов, $|V|=500 000$ уникальных слов, то объём матрицы составляет $|V| \cdot N = 5 \cdot 10^{11}$ ячеек, что занимает примерно 58.2 Гб при хранении одного бита на ячейку. При этом средний документ содержит от 200 до 1000 уникальных слов, поэтому доля единиц в столбце составляет 0.04-0.2%, а доля нулей - 99.8%

Инвертированный индекс получается путем удаления нулей и сохранения только номеров документов для слов. Инвертированный индекс состоит из списков документов и словаря, который хранит уникальные термины, документную частоту $df$ и указатель на список отсортированных документов, где содержится это слово

Словарь организуется как B-дерево, префиксное дерево или хеш-таблица (у которых асимптотическая сложность поиска $O(\text{длина слова})$ или $O(1)$). Сортировка документов критична для эффективного объединения и пересечения списков

Обработка булевых запросов над списками документов не требует сканирования всей базы, например:

Для оптимизации булева поиска можно применять принцип наименьшей частотности (Shortest First) - пересечение лучше начинать со списков с наименьшей документной частотой, что сразу уменьшает выборку

Булев поиск возвращает несортированный список идентификаторов документов. Чтобы его отранжировать, используют частоту слова в документе или же подходы TF-IDF и BM25


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

Например, с помощью расстояния Левенштейна (Levenshtein Distance), предложенного Владимиром Левенштейном в 1965 году, которое определяется как число удаления, вставки или замены символов, чтобы одно слово преобразить в другое. Расстояние Левенштейна можно вычислить с помощью динамического программирования за $O(n m)$, где $n$ - длина 1-ого слова, $m$ - длина 2-ого слова


Сравнивать запрос со всеми словами словаря слишком дорого: при $|V|=1000000$ сложность $O(|V| \cdot n \cdot m)$ оказывается слишком высокой. Поэтому используются специальные структуры:

Современные системы всё чаще используют большие языковые модели, которые учитывают семантику запроса и исправляют не только орфографические, но и смысловые ошибки

Модели TF-IDF и BM25

Булев поиск делит документы бинарно, но при совпадении тысяч страниц невозможно выдать неструктурированный список - отсюда возникает принцип вероятностного ранжирования (сформулирован Робертсоном в 1977 году): поисковая система достигает максимальной полезности, если ранжирует документы $d$ по убыванию вероятности их релевантности запросу $q$, то есть $P(R=1 \mid d,q)$

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

Исторически первым решением стала векторная модель (Vector Space Model), в которой документ и запрос отображаются в $|V|$-мерное пространство, где координата каждого слова - это произведение $\mathrm{TF} \times \mathrm{IDF}$, а мера близости - это косинус угла $\cos \theta$

Так появилась модель TF-IDF, основанная на мере TF-IDF - статистической мере важности слова в документе с учетом коллекции. Мера TF-IDF состоит из двух других мер:

Получается формула $\mathrm{Score}(q,d) = \sum_{t \in q} \mathrm{TF}(t,d) \cdot \mathrm{IDF}(t)$

У классического TF-IDF есть два недостатка:

Другая модель, BM25 (Best Matching 25), учитывает это. Формула ранжирования документа $D$ по запросу $Q=(q_1,q_2,\ldots,q_n)$ становится следующей:

\[\mathrm{Score} (D,Q) = \sum_{i=1}^{n} \mathrm{IDF}(q_i) \cdot \frac{\mathrm{TF}(q_i,D) \cdot (k_1+1)} {\mathrm{TF}(q_i,D)+k_1\cdot \left(1-b+b\cdot \frac{\|D\|}{\mathrm{avgdl}}\right)},\]

где $|D|$ - длина документа в словах, $\mathrm{avgdl}$ - средняя длина документа по корпусу, $k_1$ и $b$ - гиперпараметры

Параметр $k_1 \in [1.2,2.0]$ регулирует насыщение частоты термина TF:

Параметр $b \in [0,1]$ управляет нормализацией длины документа:


На многословных запросах списки содержат миллионы документов. Полный подсчет BM25 для каждого документа перегружает процессор, хотя пользователю нужно только несколько лучших кандидатов

Алгоритм безопасного отсечения WAND (от Weak AND) решает эту проблему. Алгоритм гарантирует математически точную выборку $k$ лучших кандидатов, но пропускает вычисление точного оценка релевантности для большинства документов

Основные идеи алгоритма:


Индекс можно строить в базе данных, например в SQLite. Схема простого индекса состоит из четырех таблиц:

Дополнительно можно завести таблицу linkwords для текста ссылки

В каждой таблице SQLite по умолчанию есть поле rowid, поэтому явно задавать ключевые поля необязательно

Таблица wordlocation связывает слова с документами, поэтому можно легко найти страницы, содержащие данное слово. Но поисковая машина должна поддерживать запросы из нескольких слов, поэтому нужна функция, которая принимает строку запроса, разбивает ее на слова и строит SQL-запрос для поиска URL документов, в которые входят все указанные слова

В ответе сначала идет идентификатор документа, затем позиция первого слова из запроса, позиция второго слова и так далее для каждого вхождения. Отдельно возвращается список идентификаторов слов из запроса

Функция поиска сужает круг документов, но также нужно присвоить страницам ранг относительно запроса и возвращать их по убыванию ранга. Это можно делать следующим образом:

Ранжирование по содержимому в веб-поиске не всегда дает хороший результат. Его можно улучшить, учитывая количество и качество ссылок на страницу

Оценка качества

После проектирования индекса или изменения весов BM25 возникает задача: как объективно понять, стала ли поисковая выдача лучше? В информационном поиске используется двухуровневая методология:

Офлайн-тестирование опирается на парадигму Крэнфилда, предложенную в экспериментах Cranfield II в 1960-ые годы. Тестовая коллекция, или Gold Standard, формализуется тройкой $C = \langle D, Q, R \rangle$, где $D$ - коллекция документов, статичный массив текстов, по которому строится индекс ($|D|=N$), $Q$ - набор поисковых запросов, репрезентативная выборка реальных пользовательских запросов, а $R$ - матрица суждений о релевантности (или Qrels, она отображает пару “запрос-документ” в оценку полезности $rel(q,d)$)

Оценки в Qrels бывают:

Если в корпусе $10^7$ документов, а в наборе $10^3$ запросов, то зачастую нет возможности физически разметить $10^{10}$ пар. Поэтому в проверках (вроде TREC) используется пулинг:

  1. Берутся $M$ разных поисковых систем: BM25, плотный векторный поиск, бустинг и другие
  2. Каждая система возвращает свою выборку $\mathrm{TopK}$ из $K$ элементов, например $K=100$
  3. Результаты объединяются: $P_q = \bigcup_{i=1}^{M} \mathrm{TopK}_i$
  4. Эксперты размечают только документы из объединения $P_q$. Остальные документы корпуса считаются нерелевантными (для них $rel=0$)

Экспертные оценки релевантности не являются абсолютной истиной: они субъективны и зависят от содержания, кругозора эксперта и контекста. Для аудита качества разметки используется коэффициент Каппа Коэна - $\kappa = \frac{P_o - P_e}{1 - P_e}$, где $P_o$ - наблюдаемая доля совпадений, $P_e$ - гипотетическая вероятность случайного совпадения при маргинальных распределениях оценок

Чем выше $\kappa$, тем выше согласие. В масштабных бенчмарках TREC и MS MARCO значение $\kappa$ обычно колеблется в диапазоне $0.45-0.65$

Важно учитывать, что часто релевантность (соответствие текста документа смысловому полю запроса) расходится с полезностью документа для решения проблемы пользователя


Онлайн-оценка базируется на журналировании взаимодействий реального пользователя с интерфейсом. Ключевые продуктовые метрики включают:

Также применяют:

Здесь важно учитывать, что первая позиция собирает максимум кликов просто по привычке читать сверху вниз (даже если релевантный документ находится на 3-4 месте) - такое называется позиционным смещением (Position Bias), а также влияет привлекательность сегмента текста, который презентует сайт в выдаче (Presentation Bias)


Для офлайн-оценки используют такие метрики:

При изменении поиска изменение метрик может говорить о разном:

Рост или падение метрики может быть шумом, поэтому используют статистические проверки гипотез