Поисковые системы начали свое развитие с каталогов. При появлении новой страницы она заносится в каталог, где перечислены страницы по алфавиту или сгруппированы по категориям
Когда число страниц в 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-ых годов основные задачи полнотекстового поиска были решены, поэтому развитие поисковых систем происходило в других направлениях:
Поиск делится на два этапа:
Предварительная подготовка данных
Далее пользователь вводит свой поисковой запрос
Ключевую роль в оптимизации поиска играет индексация, в ходе которой данные подготавливаются в такую структуру, в которой запрос на поиск занимает наименьшее время
В более усовершенствованных системах поиск среди множества документов делится на несколько этапов:
Поиск данных (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) - это область информатики, которая изучает методы поиска документов, удовлетворяющих информационной потребности пользователя, из большой коллекции, при этом документы чаще всего не имеют единой четкой структуры
Запрос - это формализованный способ выражения информационной потребности с использованием средств естественного языка (то есть слов), при этом одна и та же потребность может быть сформулирована разными запросами
Объект поиска - это информационная сущность, которая хранится в базе автоматизированной поисковой системы. Чаще всего это текстовый документ, но может быть медиа. Процесс занесения объектов поиска в поисковую систему называется индексацией
Критерием поиска выступает степень соответствия запросу, по которому можно сделать ранжирование объектов поиска
Булева модель исторически является первой и математически строгой моделью информационного поиска:
AND, OR, NOT, либо отбрасываетсяТакая модель детерминирована (то есть результат воспроизводим), но в ней нет встроенного ранжирования, то есть документ, где термин встретился 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)$). Сортировка документов критична для эффективного объединения и пересечения списков
Обработка булевых запросов над списками документов не требует сканирования всей базы, например:
AND реализуется методом двух указателей (со сложностью $O(L_1 + L_2)$, где $L_1$ и $L_2$ - длины списков документов)OR аналогична слиянию без дубликатов (сложность - $O(L_1 + L_2)$)NOT в запросе A AND NOT B выполняется проходом по списку A с проверкой, что элементов списка A нет в списке B (асимптотика - $O(L_A + L_B)$)Для оптимизации булева поиска можно применять принцип наименьшей частотности (Shortest First) - пересечение лучше начинать со списков с наименьшей документной частотой, что сразу уменьшает выборку
Булев поиск возвращает несортированный список идентификаторов документов. Чтобы его отранжировать, используют частоту слова в документе или же подходы TF-IDF и BM25
Также поиск должен исправлять нечеткость. Различают нечеткость на уровне документа, когда документ не полностью соответствует запросу (такое решается ранжированием), и на уровне слова (например, опечатка в запросе, разное написание). Для решения этой проблемы поверх словаря инвертированного индекса строятся вспомогательные структуры
Например, с помощью расстояния Левенштейна (Levenshtein Distance), предложенного Владимиром Левенштейном в 1965 году, которое определяется как число удаления, вставки или замены символов, чтобы одно слово преобразить в другое. Расстояние Левенштейна можно вычислить с помощью динамического программирования за $O(n m)$, где $n$ - длина 1-ого слова, $m$ - длина 2-ого слова
Сравнивать запрос со всеми словами словаря слишком дорого: при $|V|=1000000$ сложность $O(|V| \cdot n \cdot m)$ оказывается слишком высокой. Поэтому используются специальные структуры:
BK-деревья (Burkhard–Keller Trees), предложенные Буркхардом и Келлером в 1973 году, организуют вершины по расстоянию Левенштейна и позволяют рассматривать лишь небольшую часть словаря
BK-дерево существенно сокращает число вычислений по сравнению с полным перебором, при этом современные поисковые системы почти никогда не используют только расстояние Левенштейна - исправление запросов является задачей машинного обучения, где учитываются расстояние между словами, частота слов в языке, частота поисковых запросов, контекст, история поиска пользователя и языковые модели
Современные системы всё чаще используют большие языковые модели, которые учитывают семантику запроса и исправляют не только орфографические, но и смысловые ошибки
Булев поиск делит документы бинарно, но при совпадении тысяч страниц невозможно выдать неструктурированный список - отсюда возникает принцип вероятностного ранжирования (сформулирован Робертсоном в 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. Схема простого индекса состоит из четырех таблиц:
urllist - список проиндексированных URLwordlist - список словwordlocation - список мест вхождения слов в документы, где место вхождения - это номер слова в документеlink - идентификаторы двух URL, связанных ссылкойДополнительно можно завести таблицу 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) используется пулинг:
Экспертные оценки релевантности не являются абсолютной истиной: они субъективны и зависят от содержания, кругозора эксперта и контекста. Для аудита качества разметки используется коэффициент Каппа Коэна - $\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)
Для офлайн-оценки используют такие метрики:
Precision@K показывает, какая доля документов среди первых $K$ результатов действительно релевантна: $\mathrm{Precision@K} = \frac{\text{число релевантных документов в Top-}K}{K}$
Если среди первых 10 документов 7 релевантных, то $\mathrm{Precision@10} = \frac{7}{10} = 0.7$
Precision оценивает только ту часть выдачи, которую пользователь реально просматривает, поэтому часто используют Precision@5 и Precision@10. Однако эта метрика не учитывает порядок внутри выборки
Recall@K показывает, какую долю всех релевантных документов система смогла найти: $\mathrm{Recall@K} = \frac{\text{число найденных релевантных документов}}{\text{общее число релевантных документов}}$
Если в коллекции 25 релевантных документов, а система нашла только 20 релевантных, то $\mathrm{Recall} = \frac{20}{25} = 0.8$
Mean Reciprocal Rank (MRR) моделирует поиск “известного факта”, когда пользователю нужен строго первый полезный документ
Пусть для запроса $q$ первый релевантный документ найден на позиции $rank_q$ - тогда $\mathrm{RR}(q) = \frac{1}{rank_q}$, а $\mathrm{MRR} = \frac{1}{|Q|} \sum_{q \in Q} \frac{1}{rank_q}$
MRR резко штрафует за смещение первого ответа вниз, применяется в навигационных запросах. Недостаток состоит в том, что MRR не учитывает документы после первого найденного
Mean Average Precision (MAP) вычисляет точность в каждой точке выдачи, где появляется очередной релевантный документ, и усредняет эти значения
Пусть $R_q$ - общее число релевантных документов для запроса $q$, $P@k(q)$ - точность на срезе первых $k$ документов, $rel_k \in {0,1}$ - индикатор релевантности документа на позиции $k$, тогда $\mathrm{AP}(q) = \frac{1}{R_q} \sum_{k=1}^{N} P@k(q) \cdot rel_k$
Нормировка идет на общее число релевантных документов $R_q$, а не на число фактически найденных документов - $\mathrm{MAP} = \frac{1}{|Q|} \sum_{q \in Q} \mathrm{AP}(q)$
MAP оценивает, насколько плотно релевантные документы сгруппированы у вершины списка. Недостаток состоит в том, что MAP требует бинарной релевантности и не различает глубокий обзор и поверхностную заметку
Normalized Discounted Cumulative Gain (nDCG) учитывает градации качества и вычисляется так:
Вычисляется дисконтированный совокупный выигрыш - $\mathrm{DCG@K} = \sum_{i=1}^{K} \frac{2^{rel_i} - 1}{\log_2(i+1)}$
Числитель $2^{rel_i}-1$ экспоненциально поощряет документы высшего качества, а знаменатель $\log_2(i+1)$ отражает логарифмическое затухание внимания
Далее нормализация - $\mathrm{nDCG@K} = \frac{\mathrm{DCG@K}}{\mathrm{IDCG@K}} \in [0,1]$, где $\mathrm{IDCG@K} = \sum_{i=1}^{K} \frac{2^{rel^_i} - 1}{\log_2(i+1)}$, а $rel^$ - истинные релевантности, отсортированные по убыванию
При изменении поиска изменение метрик может говорить о разном:
Рост или падение метрики может быть шумом, поэтому используют статистические проверки гипотез