Разреженный поиск

Разреженный поиск (англ. sparse retrieval, sparse search) — это метод информационного поиска, основанный на представлении документов и запросов в виде разреженных векторов в многомерном пространстве, где большинство координат равны нулю, а ненулевые значения соответствуют весам отдельных термов (слов, токенов). В отличие от плотного (dense) поиска, использующего нейросетевые эмбеддинги, разреженный поиск опирается на точное совпадение термов и их статистическую значимость, что обеспечивает высокую интерпретируемость и эффективность при работе с большими текстовыми коллекциями.

Принцип работы

Основой разреженного поиска является векторная модель (vector space model), где каждый документ и поисковый запрос представляются как векторы в пространстве, размерность которого равна числу уникальных термов в коллекции (словарю). Вектор является разреженным, так как каждый документ содержит лишь малую долю термов из всего словаря. Ненулевые значения вектора — это веса термов, чаще всего вычисляемые по схеме TF-IDF (Term Frequency — Inverse Document Frequency):

• TF (частота терма) — количество вхождений терма в документе, часто нормированное (например, логарифмическое сглаживание).
• IDF (обратная документная частота) — мера редкости терма в коллекции, вычисляемая как логарифм отношения общего числа документов к числу документов, содержащих данный терм.

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

История и развитие

Концепция разреженного поиска восходит к 1960-м годам, когда были разработаны первые информационно-поисковые системы, такие как SMART (System for the Mechanical Analysis and Retrieval of Text) под руководством Джерарда Салтона. В 1970-х годах была формализована модель TF-IDF, ставшая стандартом де-факто для текстового поиска.

В 1990-х годах с ростом веба разреженный поиск лёг в основу первых поисковых систем, включая ранние версии AltaVista и Google. Инвертированный индекс — структура данных, сопоставляющая каждому терму список документов, где он встречается, — позволил выполнять поиск за сублинейное время.

В 2010-х годах с развитием нейросетей появились плотные методы (dense retrieval), использующие эмбеддинги BERT и других трансформеров. Однако разреженный поиск сохранил актуальность благодаря своей эффективности, интерпретируемости и низким требованиям к вычислительным ресурсам. В 2020-х годах возникли гибридные подходы, сочетающие разреженный и плотный поиск (например, SPLADE, ColBERT), а также методы обучения разреженных представлений (Learned Sparse Retrieval), где веса термов не вычисляются по TF-IDF, а предсказываются нейросетью.

Классификация методов разреженного поиска

Классические (статистические) методы

• TF-IDF — базовая схема взвешивания, используемая в большинстве традиционных систем.
• BM25 (Okapi BM25) — вероятностная модель, улучшающая TF-IDF за счёт учёта длины документа и насыщения частоты терма. Является стандартом в современных поисковых движках (Elasticsearch, Lucene, Solr).
• Language Model (LM) with Dirichlet smoothing — метод, основанный на оценке вероятности генерации запроса из модели документа.

Обученные разреженные методы (Learned Sparse Retrieval)

• SPLADE (Sparse Lexical and Dense) — нейросетевая модель, которая предсказывает веса термов из словаря для каждого документа, используя архитектуру трансформера. Векторы остаются разреженными, но веса оптимизируются под задачу ранжирования.
• DeepImpact — метод, обучающий модель присваивать вес каждому терму документа на основе его семантической важности.
• uniCOIL — подход, в котором веса термов вычисляются как активации выходного слоя BERT, что позволяет комбинировать лексическое и семантическое соответствие.

Гибридные системы

• ColBERT (Contextualized Late Interaction) — модель, которая генерирует плотные эмбеддинги для каждого терма запроса и документа, но затем выполняет разреженное потермное сравнение (MaxSim) для ранжирования.
• Dense-Sparse Fusion — комбинация результатов разреженного (BM25) и плотного (Dense Passage Retriever) поиска с последующим переранжированием.

Преимущества и недостатки

Преимущества

• Интерпретируемость — результат поиска объясняется точным совпадением термов: пользователь видит, какие слова запроса встретились в документе.
• Эффективность — инвертированный индекс позволяет обрабатывать миллиарды документов за миллисекунды без использования GPU.
• Низкие требования к ресурсам — не требуется обучение нейросетей или хранение плотных эмбеддингов (сотни гигабайт против единиц гигабайт для индекса BM25).
• Работа с редкими и специфическими термами — точное совпадение хорошо находит точные названия, коды, идентификаторы, которые плотные модели могут «размывать».
• Простота реализации — алгоритмы (TF-IDF, BM25) реализованы в стандартных библиотеках (Scikit-learn, Elasticsearch, Lucene).

Недостатки

• Проблема синонимии — разреженный поиск не находит документы, где смысл запроса выражен другими словами (например, запрос «автомобиль» не найдёт документ со словом «машина»).
• Проблема полисемии — одно и то же слово в разных контекстах (например, «ключ» как инструмент и как устройство доступа) обрабатывается одинаково.
• Зависимость от точного совпадения — опечатки, морфологические формы (падежи, склонения) требуют предварительной нормализации (стемминг, лемматизация).
• Разреженность запроса — короткие запросы (1-2 слова) дают мало совпадений, что снижает качество ранжирования.

Применение

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

• Поисковые системы — Elasticsearch, Apache Solr, Sphinx — основаны на BM25 для полнотекстового поиска по веб-страницам, документам, базам знаний.
• Библиотечные и архивные системы — поиск по каталогам, метаданным, полным текстам книг и статей.
• Юридические и медицинские информационные системы — поиск по кодексам, нормативным актам, клиническим рекомендациям, где важна точность терминологии.
• Электронная коммерция — поиск товаров по названиям, артикулам, характеристикам.
• Системы управления контентом (CMS) — внутренний поиск по документам, блогам, базам знаний.
• Научные поисковые системы — Google Scholar, Semantic Scholar, PubMed используют разреженные методы для индексации и поиска по миллионам публикаций.

Сравнение с плотным поиском

Интересные факты

• Алгоритм BM25 был разработан в 1994 году Стивеном Робертсоном и Карен Спарк Джонс в рамках проекта Okapi в Лондонском университете. Он остаётся стандартом де-факто в промышленных поисковых системах спустя 30 лет.
• В 2023 году на соревновании TREC (Text Retrieval Conference) гибридные системы, сочетающие BM25 и плотные методы, показали наилучшие результаты на задачах веб-поиска.
• Разреженный поиск используется в ядре поисковой системы «Яндекс» (в комбинации с нейросетевыми методами) для обработки более 90 % запросов, где требуется точное совпадение (например, поиск по адресам, номерам телефонов, артикулам).
• Инвертированный индекс, лежащий в основе разреженного поиска, был впервые описан в 1960-х годах Хансом-Петером Люном и независимо — в 1970-х годах сотрудниками компании IBM.

Критика

Основная критика разреженного поиска связана с его неспособностью улавливать семантические связи между словами. В условиях современного веба, где запросы часто формулируются естественным языком (например, «как починить кран на кухне»), разреженный поиск может не найти релевантные документы, если в них используется другая лексика («ремонт смесителя»). Кроме того, разреженные методы плохо работают с мультимодальными данными (изображения, видео, аудио), где лексическое представление невозможно.

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

Источники

• Robertson, S. E., & Zaragoza, H. (2009). The Probabilistic Relevance Framework: BM25 and Beyond. Foundations and Trends in Information Retrieval, 3(4), 333–389.
• Salton, G., & McGill, M. J. (1983). Introduction to Modern Information Retrieval. McGraw-Hill.
• Formal, T., Piwowarski, B., & Clinchant, S. (2021). SPLADE: Sparse Lexical and Dense Retrieval. Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval.
• Lin, J., Nogueira, R., & Yates, A. (2021). Pretrained Transformers for Text Ranking: BERT and Beyond. Morgan & Claypool.
• Manning, C. D., Raghavan, P., & Schütze, H. (2008). Introduction to Information Retrieval. Cambridge University Press.