В прошлой дорожке мы разбирали, как быстро найти ближайшие векторы. Но векторы плохо помнят редкие имена, коды ошибок и номера договоров, а по ним люди ищут постоянно. Поэтому в рабочем поиске рядом с векторами почти всегда стоит старый добрый поиск по словам, и результаты двух поисков склеивают. Узкий вопрос дня: как устроен поиск по словам BM25 и как правильно склеить его выдачу с векторной (гибридный поиск, hybrid search). В старой короткой дорожке про поиск по заметкам гибридный поиск был одной ступенью «на пальцах»; здесь — формулы, настройки и замеры. Все примеры ниже запускались на коробке: BM25 написан вручную в несколько строк, «модель смысла» — игрушечная, на numpy, чтобы было видно каждый шаг. Цифры качества относятся к этому игрушечному миру и показывают направление, а не обещание для ваших данных; цифры из документации и статей помечены источником.
Все дорожки — /put. Прошлая — приближённый поиск соседей.
Зачем это в работе. Поиск по словам (лексический поиск, lexical search) — это то, что стоит внутри Elasticsearch, OpenSearch, полнотекстового поиска PostgreSQL и «поиска по ключевым словам» почти в любой векторной базе. Он находит документ, если в нём есть слова из вопроса, и особенно хорош там, где важна точная строка: код ошибки, артикул, фамилия, имя функции. Чтобы понимать, почему он нашёл одно и не нашёл другое, и чтобы правильно склеивать его с векторами, нужно знать две вещи: как он быстро находит документы со словом и как решает, какое слово в вопросе важнее.
Как это устроено. Шаг первый — разбить текст на слова (токенизация, tokenization). Это не те токены, на которые текст режет языковая модель: здесь обычно берут целые слова, приводят их к нижнему регистру и выбрасывают знаки препинания. Уже на этом шаге решается многое: «Поиск» и «поиск» станут одним словом, а «поиск» и «поиске» — двумя разными, если отдельно не позаботиться об окончаниях (к этому вернёмся на пятой ступени).
Шаг второй — построить обратный индекс (inverted index). Для каждого слова хранят список документов, где оно встречается, и сколько раз; такой список называют списком вхождений (postings list). Он «обратный», потому что идёт не от документа к словам, а от слова к документам — как предметный указатель в конце книги. При поиске не нужно читать все документы: берут списки вхождений только тех слов, что есть в вопросе, и складывают оценки. Документ, где нет ни одного слова вопроса, вообще не рассматривается. В этом главное отличие от векторного перебора из прошлой дорожки, где вопрос сравнивают с каждым вектором.
Шаг третий — понять, какое слово важнее. Слово, которое есть почти в каждом документе («по», «и», «это»), почти ничего не говорит о том, какой документ нужен. Слово, которое есть в одном документе из тысячи, говорит много. Это свойство меряют обратной документной частотой (IDF, inverse document frequency): чем в меньшем числе документов встречается слово, тем больше его вес. В Lucene, а значит в Elasticsearch и OpenSearch, для BM25 её считают так: idf = ln(1 + (N − n + 0,5) / (n + 0,5)), где N — число документов, n — в скольких из них есть слово. У слова, которое есть везде, idf близок к нулю; у слова из одного документа он максимален.
Ограничение у этого подхода одно и очень важное: поиск по словам видит только совпадение строк. Синоним, пересказ своими словами, другая форма слова или опечатка для него — просто другое слово. Отличие от соседнего понятия: IDF — это вес слова во всей коллекции, он одинаков для всех документов; а то, сколько раз слово встретилось в конкретном документе, — частота слова (TF, term frequency), и с ней работают на следующей ступени.
Подробный пример. Восемь коротких документов на темы прошлых дорожек. Строим обратный индекс, смотрим списки вхождений и idf нескольких слов, а потом задаём три вопроса и считаем оценки BM25 (саму формулу разберём на второй ступени; параметры — как по умолчанию в Elasticsearch, k1 = 1,2 и b = 0,75). Общий модуль с токенизатором и BM25 используется во всех примерах дорожки.
import numpy as np, re, math
from collections import Counter, defaultdict
def tokens(text):
"""Самая простая разбивка: нижний регистр, слова из букв, цифр и дефиса."""
return re.findall(r"[\w-]+", text.lower())
class BM25:
"""BM25 как в Lucene/Elasticsearch: idf = ln(1 + (N - n + 0.5) / (n + 0.5))."""
def __init__(self, docs, k1=1.2, b=0.75):
self.k1, self.b = k1, b
self.N = len(docs)
self.len = np.array([len(d) for d in docs], dtype=float)
self.avg = self.len.mean()
self.post = defaultdict(list) # слово -> [(номер документа, сколько раз)]
for i, d in enumerate(docs):
for w, c in Counter(d).items():
self.post[w].append((i, c))
def idf(self, w):
n = len(self.post.get(w, []))
return math.log(1 + (self.N - n + 0.5) / (n + 0.5))
def scores(self, query):
s = np.zeros(self.N); touched = 0
for w in set(query):
idf = self.idf(w)
for i, tf in self.post.get(w, []):
norm = self.k1 * (1 - self.b + self.b * self.len[i] / self.avg)
s[i] += idf * tf * (self.k1 + 1) / (tf + norm)
touched += 1
return s, touched
def topk(s, k):
k = min(k, len(s))
idx = np.argpartition(-s, k - 1)[:k]
return idx[np.argsort(-s[idx], kind="stable")]
def rank_of(order, target):
hit = np.where(order == target)[0]
return int(hit[0]) + 1 if len(hit) else None
def report(name, ranks, k=10):
"""hit@k — нашёлся ли нужный документ в первых k; MRR@k — среднее 1/место."""
hit = np.mean([r is not None and r <= k for r in ranks])
mrr = np.mean([1 / r if r is not None and r <= k else 0 for r in ranks])
print(f" {name:<34s} hit@{k} = {hit:.3f} MRR@{k} = {mrr:.3f}")
from common import *
docs_text = [
"Индекс HNSW строит граф соседей и ищет по нему жадно",
"Параметр nprobe задаёт, сколько ячеек IVF просматривать при поиске",
"Ошибка ERR-4512 появляется, когда индекс не обучен",
"Поиск по смыслу находит пересказ, но путает редкие имена",
"Поиск по словам находит редкие имена и коды ошибок",
"Граф соседей в HNSW хранит обратные рёбра",
"При поиске модель сравнивает вопрос с каждым куском текста",
"Куски текста режут по абзацам, чтобы поиск находил нужное место",
]
docs = [tokens(t) for t in docs_text]
bm = BM25(docs)
print("документов:", bm.N, " средняя длина:", round(bm.avg, 2), "слова")
for w in ["поиск", "поиске", "соседей", "hnsw", "err-4512", "по"]:
print(f"{w:>9s}: списки {[i for i, _ in bm.post.get(w, [])]!s:<14s} idf = {bm.idf(w):.3f}")
for q in ["ошибка ERR-4512", "граф соседей HNSW", "поиск по словам"]:
s, touched = bm.scores(tokens(q))
best = topk(s, 3)
print(f"\nвопрос «{q}»: просмотрено записей {touched}, оценки ненулевые у {int((s > 0).sum())} из {bm.N}")
for i in best[s[best] > 0]:
print(f" {s[i]:.3f} #{i} {docs_text[i]}")
У нас этот код напечатал:
документов: 8 средняя длина: 8.75 слова
поиск: списки [3, 4, 7] idf = 0.944
поиске: списки [1, 6] idf = 1.281
соседей: списки [0, 5] idf = 1.281
hnsw: списки [0, 5] idf = 1.281
err-4512: списки [2] idf = 1.792
по: списки [0, 3, 4, 7] idf = 0.693
вопрос «ошибка ERR-4512»: просмотрено записей 2, оценки ненулевые у 1 из 8
3.903 #2 Ошибка ERR-4512 появляется, когда индекс не обучен
вопрос «граф соседей HNSW»: просмотрено записей 6, оценки ненулевые у 2 из 8
4.185 #5 Граф соседей в HNSW хранит обратные рёбра
3.631 #0 Индекс HNSW строит граф соседей и ищет по нему жадно
вопрос «поиск по словам»: просмотрено записей 8, оценки ненулевые у 4 из 8
3.390 #4 Поиск по словам находит редкие имена и коды ошибок
1.619 #3 Поиск по смыслу находит пересказ, но путает редкие имена
1.547 #7 Куски текста режут по абзацам, чтобы поиск находил нужное место
Что видно. Код ERR-4512 встречается в одном документе из восьми, и его idf самый большой — 1,792; предлог «по» встречается в половине документов, и его idf меньше в два с половиной раза — 0,693. На вопрос «ошибка ERR-4512» индексу пришлось прочитать всего две записи вхождений, и нашёлся ровно один документ — остальные семь даже не рассматривались. На вопрос «граф соседей HNSW» все три слова есть в двух документах, но выше оказался более короткий (документ 5, семь слов против десяти у документа 0): BM25 считает, что в коротком тексте совпадение весит больше. А на вопрос «поиск по словам» документ 6 «При поиске модель сравнивает…» не нашёлся вовсе: «поиске» для индекса — другое слово, чем «поиск».
Где обычно ошибаются.
Словарь ступени.
Поиск по словам (lexical search). Поиск, который находит документы по совпадению слов вопроса со словами текста.
Токенизация (tokenization). Разбиение текста на слова или части слов перед построением индекса.
Обратный индекс (inverted index). Таблица «слово → список документов, где оно есть», как предметный указатель в книге.
Список вхождений (postings list). Перечень документов с данным словом и числом его повторов в каждом.
Обратная документная частота (IDF). Вес слова, который тем больше, чем в меньшем числе документов оно встречается.
Частота слова (TF, term frequency). Сколько раз слово встретилось в конкретном документе.
Стоп-слова (stop words). Очень частые служебные слова, которые иногда выбрасывают из индекса.
Lucene. Открытая библиотека полнотекстового поиска на Java, на которой построены Elasticsearch и OpenSearch.
Зачем это в работе. BM25 — оценка по умолчанию в Elasticsearch, OpenSearch и Lucene и стандартная «ключевая» половина гибридного поиска в Weaviate, Qdrant, Milvus и других базах. У неё всего два параметра, k1 и b, и от них зависит, победит ли в выдаче короткая точная заметка или длинная статья, где нужное слово повторено двадцать раз. Понимая, что делает каждый параметр, можно объяснить странную выдачу и не крутить настройки наугад.
Как это устроено. Оценка документа — сумма вкладов по словам вопроса. Вклад одного слова = idf × tf × (k1 + 1) / (tf + k1 × (1 − b + b × длина / средняя длина)). Формула пришла из вероятностной модели поиска Робертсона и Спарк Джонс; сама BM25 появилась в поисковой системе Okapi лондонского City University в середине 1990-х, а подробный разбор есть в обзоре Robertson и Zaragoza «The Probabilistic Relevance Framework: BM25 and Beyond» (2009). По умолчанию в Elasticsearch k1 = 1,2 и b = 0,75 — так написано в его документации о настройках сходства (similarity).
Первый параметр, k1, отвечает за насыщение (saturation). Если бы вклад рос прямо пропорционально числу повторов, как в простом TF-IDF, то документ, где слово повторено 20 раз, получал бы в 20 раз больше, чем документ с одним упоминанием, — и выигрывали бы тексты, набитые ключевыми словами. В BM25 каждый следующий повтор добавляет всё меньше, и вклад не может превысить idf × (k1 + 1). Чем меньше k1, тем быстрее наступает насыщение: при k1 = 0 считается только «есть слово или нет».
Второй параметр, b, — поправка на длину документа (length normalization). Длинный текст случайно содержит больше слов, поэтому одно совпадение в нём весит меньше, чем в короткой заметке. При b = 0 длина не учитывается, при b = 1 вклад делится на длину полностью, 0,75 — промежуточное значение, которое хорошо показало себя в экспериментах и стало стандартом по умолчанию. Ограничение: «средняя длина» берётся по всей коллекции (в Lucene — по полю в индексе), поэтому, если смешать в одном поле заголовки из пяти слов и статьи из пяти тысяч, поправка будет плохо подходить и тем, и другим.
Чем BM25 отличается от соседних понятий. От TF-IDF — насыщением и поправкой на длину. От векторного сходства — тем, что оценка BM25 не ограничена сверху и зависит от вопроса: у вопроса из пяти редких слов оценки будут порядка десятков, у вопроса из одного частого слова — меньше единицы. Сравнивать оценки BM25 между разными вопросами или с косинусом напрямую нельзя; это станет главной проблемой на четвёртой ступени.
Подробный пример. Берём вес кода ERR-4512 из первого примера (idf = 1,792) и считаем его вклад при разном числе повторов и разной длине документа. Затем сравниваем «честную» страницу, где код упомянут дважды, с «набитой», где он повторён 20 раз и которая из-за этого в полтора раза длиннее.
import math
idf = 1.792 # вес слова err-4512 из первого примера
def part(tf, k1=1.2, b=0.75, ratio=1.0): # ratio = длина документа / средняя длина
if k1 == "inf": return idf * tf # без насыщения: просто «сколько раз»
return idf * tf * (k1 + 1) / (tf + k1 * (1 - b + b * ratio))
print("вклад одного слова при разной частоте в документе (длина = средняя):")
print(" tf:" + " " * 9 + "".join(f"{t:>7d}" for t in (1, 2, 3, 5, 10, 20)))
for k1 in (0.5, 1.2, 2.0, "inf"):
label = f"k1 = {k1}" if k1 != "inf" else "tf·idf"
print(f" {label:<10s} " + "".join(f"{part(t, k1):7.2f}" for t in (1, 2, 3, 5, 10, 20)))
print("\nтот же вклад при tf = 1 и разной длине документа (k1 = 1.2):")
print(" длина/средняя:" + "".join(f"{r:>7.2f}" for r in (0.25, 0.5, 1, 2, 4, 8)))
for b in (0.0, 0.75, 1.0):
print(f" b = {b:<4} " + "".join(f"{part(1, 1.2, b, r):7.2f}" for r in (0.25, 0.5, 1, 2, 4, 8)))
print("\nпредел при tf -> бесконечность:", round(idf * 2.2, 3), "= idf * (k1 + 1)")
# «набивка»: страница повторяет слово 20 раз ради поиска, честная страница — 2 раза
honest = part(2, ratio=1.0); stuffed = part(20, ratio=1.5)
print(f"честная страница (tf=2, длина 1.0): {honest:.2f}; набитая (tf=20, длина 1.5): {stuffed:.2f}; "
f"во сколько раз больше: {stuffed / honest:.2f}")
print(f"без насыщения было бы: {part(2, 'inf'):.2f} против {part(20, 'inf'):.2f}, в {20 / 2:.0f} раз")
У нас этот код напечатал:
вклад одного слова при разной частоте в документе (длина = средняя):
tf: 1 2 3 5 10 20
k1 = 0.5 1.79 2.15 2.30 2.44 2.56 2.62
k1 = 1.2 1.79 2.46 2.82 3.18 3.52 3.72
k1 = 2.0 1.79 2.69 3.23 3.84 4.48 4.89
tf·idf 1.79 3.58 5.38 8.96 17.92 35.84
тот же вклад при tf = 1 и разной длине документа (k1 = 1.2):
длина/средняя: 0.25 0.50 1.00 2.00 4.00 8.00
b = 0.0 1.79 1.79 1.79 1.79 1.79 1.79
b = 0.75 2.59 2.25 1.79 1.27 0.80 0.46
b = 1.0 3.03 2.46 1.79 1.16 0.68 0.37
предел при tf -> бесконечность: 3.942 = idf * (k1 + 1)
честная страница (tf=2, длина 1.0): 2.46; набитая (tf=20, длина 1.5): 3.64; во сколько раз больше: 1.48
без насыщения было бы: 3.58 против 35.84, в 10 раз
Что видно. При k1 = 1,2 второй повтор добавляет к первому 0,67, третий — уже 0,36, а с 10 до 20 повторов вклад растёт только с 3,52 до 3,72; потолок — 3,942. Без насыщения (строка tf·idf) двадцать повторов дают 35,84, то есть в двадцать раз больше одного. Поэтому набитая страница при BM25 выигрывает у честной только в 1,48 раза, а при простом TF-IDF выиграла бы в 10 раз. Поправка на длину заметна не меньше: при b = 0,75 одно совпадение в документе вчетверо короче среднего весит 2,59, а в документе вчетверо длиннее — 0,80, разница больше чем в три раза. При b = 0 длина не влияет совсем.
Где обычно ошибаются.
Словарь ступени.
BM25 (Best Matching 25). Формула оценки документа по словам вопроса с учётом редкости слова, числа повторов и длины документа.
TF-IDF. Простейшая оценка «частота слова в документе × вес редкости слова» без насыщения и поправки на длину.
Насыщение (saturation). Свойство, при котором каждый следующий повтор слова добавляет к оценке всё меньше.
k1. Параметр BM25, задающий, как быстро наступает насыщение; в Elasticsearch по умолчанию 1,2.
b. Параметр BM25 от 0 до 1, задающий силу поправки на длину документа; по умолчанию 0,75.
Поправка на длину (length normalization). Уменьшение веса совпадения в длинных документах и увеличение в коротких.
Набивка ключевыми словами (keyword stuffing). Искусственный повтор нужного слова в тексте ради высокого места в поиске.
TREC. Ежегодные открытые соревнования по информационному поиску, на которых в 1990-х проверяли и BM25.
Зачем это в работе. Прежде чем склеивать два поиска, полезно увидеть своими глазами, что каждый из них умеет и чего не умеет. Тогда понятно, зачем вообще гибрид, на каких вопросах он должен помочь и как составить проверочный набор: если в нём только «пересказы», поиск по словам будет выглядеть бесполезным, а если только коды — бесполезными покажутся векторы.
Как это устроено. Векторный поиск (dense retrieval) переводит вопрос и документ в векторы моделью эмбеддингов и ищет близкие. Модель обучена на парах текстов (это была дорожка про контрастное обучение) и потому знает, что «упал сервер» и «сервис недоступен» — про одно. Но строку, которую она никогда не видела, — номер заказа, свежий код ошибки, фамилию нового сотрудника — она превращает в вектор, который почти ничего не говорит о смысле, и такой вопрос тонет среди документов «на ту же тему».
Поиск по словам устроен наоборот. Он ничего не знает о синонимах, зато уникальная строка для него — самое ценное: у неё максимальный idf, и документ с ней почти наверняка окажется наверху. Он также очень дёшев: работает только со списками вхождений слов вопроса.
Чтобы это измерить, нужен мир, где известен правильный ответ. Мы построили игрушечный: 20 000 документов на 200 тем, в каждой теме 30 «понятий», и у каждого понятия три слова-синонима (c17a, c17b, c17c — метки вместо настоящих слов). Документ называет 4 понятия своей темы, каждое одним из синонимов, плюс 20–60 служебных слов, частых и редких по закону Ципфа (частота слова обратно пропорциональна его номеру в списке по частоте), и у 30% документов есть уникальный код вида kod-123456. «Модель эмбеддингов» в этом мире знает, что синонимы значат одно и то же, но код для неё — шум. Это упрощение, но оно повторяет главное свойство настоящих моделей.
Вопросы трёх видов, у каждого ровно один правильный документ: «пересказ» — два понятия документа, названные другими синонимами, так что общих слов с документом нет; «код» — код документа плюс одно понятие его темы любым из синонимов; «те же слова» — два понятия теми же словами, что в документе. Качество меряем долей вопросов, где правильный документ попал в первые 10 (hit@10), и средним значением 1/место (MRR@10, mean reciprocal rank): если ответ первый, вопрос даёт 1, если третий — 1/3, если за пределами десятки — 0. Отличие от recall@10 прошлой дорожки: там «правильными» были настоящие ближайшие векторы, здесь — документ, который на самом деле отвечает на вопрос.
Подробный пример. Строим мир (функция make_world во второй части общего модуля), считаем BM25 и векторный перебор для 300 вопросов каждого вида.
# ---------- игрушечный мир для третьей–пятой ступеней ----------
def make_world(n_docs=20_000, n_topics=200, per_topic=30, syn=3, d=64, seed=0):
"""Каждое «понятие» можно назвать тремя словами-синонимами (c17a, c17b, c17c).
Документ: тема -> 4 понятия темы, каждое названо одним из синонимов 1–3 раза,
плюс 20–60 служебных слов (f0..f399, частые встречаются чаще) и у 30% — уникальный код вида kod-123456.
«Модель эмбеддингов» знает, что синонимы значат одно и то же (у них общий вектор понятия),
а код для неё — незнакомая строка: вектор кода случайный и не связан с документом."""
rng = np.random.default_rng(seed)
n_conc = n_topics * per_topic
concept_vec = rng.normal(size=(n_conc, d))
topic_vec = rng.normal(size=(n_topics, d))
filler_p = 1 / np.arange(1, 401); filler_p /= filler_p.sum() # закон Ципфа
filler_vec = 0.15 * rng.normal(size=(400, d))
docs, vecs, codes, conc_of_doc, syn_of = [], [], [], [], []
for i in range(n_docs):
t = rng.integers(n_topics)
cs = t * per_topic + rng.choice(per_topic, 4, replace=False)
words, v = [], 0.8 * topic_vec[t]
chosen = {}
for c in cs:
s = rng.integers(syn); chosen[c] = s
rep = rng.integers(1, 4)
words += [f"c{c}{'abc'[s]}"] * rep
v = v + rep * (concept_vec[c] + 0.3 * rng.normal(size=d))
fl = rng.choice(400, rng.integers(20, 61), p=filler_p)
words += [f"f{j}" for j in fl]; v = v + filler_vec[fl].sum(0)
code = None
if rng.random() < 0.3:
code = f"kod-{rng.integers(10**5, 10**6)}"
words.append(code); v = v + 2.0 * rng.normal(size=d) # модель не знает код: шум
rng.shuffle(words)
docs.append(words); vecs.append(v / np.linalg.norm(v)); codes.append(code)
conc_of_doc.append(cs); syn_of.append(chosen)
W = dict(rng=rng, concept_vec=concept_vec, topic_vec=topic_vec, filler_vec=filler_vec,
filler_p=filler_p, conc=conc_of_doc, syn=syn_of, codes=codes, n_topics=n_topics, per_topic=per_topic)
return docs, np.array(vecs, dtype=np.float32), W
def embed_query(words_concepts, W, code=False):
"""Вектор вопроса той же «моделью»: понятия + немного шума, код — случайный шум."""
rng = W["rng"]; d = W["concept_vec"].shape[1]
v = sum(W["concept_vec"][c] + 0.3 * rng.normal(size=d) for c in words_concepts)
if code: v = v + 2.0 * rng.normal(size=d)
return (v / np.linalg.norm(v)).astype(np.float32)
def make_queries(docs, W, n=300, seed=1):
"""Три вида вопросов, у каждого ровно один правильный документ:
«пересказ» — два понятия документа, названные ДРУГИМИ синонимами (общих слов нет);
«код» — код документа плюс одно понятие его темы своими словами;
«те же слова» — два понятия документа теми же словами, что в нём."""
rng = np.random.default_rng(seed)
Q = {"пересказ": [], "код": [], "те же слова": []}
with_code = [i for i, c in enumerate(W["codes"]) if c]
for _ in range(n):
i = rng.integers(len(docs)); cs = rng.choice(W["conc"][i], 2, replace=False)
words = [f"c{c}{'abc'[(W['syn'][i][c] + rng.integers(1, 3)) % 3]}" for c in cs]
Q["пересказ"].append((words, embed_query(cs, W), i))
i = with_code[rng.integers(len(with_code))]; c = rng.choice(W["conc"][i])
words = [W["codes"][i], f"c{c}{'abc'[rng.integers(3)]}"]
Q["код"].append((words, embed_query([c], W, code=True), i))
i = rng.integers(len(docs)); cs = rng.choice(W["conc"][i], 2, replace=False)
words = [f"c{c}{'abc'[W['syn'][i][c]]}" for c in cs]
Q["те же слова"].append((words, embed_query(cs, W), i))
return Q
import time
from common import *
docs, vecs, W = make_world()
Q = make_queries(docs, W)
t = time.perf_counter(); bm = BM25(docs); t_build = time.perf_counter() - t
print(f"документов {len(docs)}, средняя длина {bm.avg:.1f} слова, разных слов {len(bm.post)}, "
f"индекс построен за {t_build:.2f} с")
for w in ["f0", "f10", "f300", "c17a", W["codes"][W["codes"].index(next(c for c in W["codes"] if c))]]:
print(f" слово {w:<11s} встречается в {len(bm.post[w]):5d} документах, idf = {bm.idf(w):.2f}")
touched_all = []
for kind, qs in Q.items():
print(f"\nвопросы «{kind}» ({len(qs)} шт.), пример слов вопроса: {qs[0][0]}")
rb, rd = [], []
for words, qv, target in qs:
s, touched = bm.scores(words); touched_all.append(touched)
rb.append(rank_of(topk(s, 10), target))
rd.append(rank_of(topk(vecs @ qv, 10), target))
report("слова (BM25)", rb); report("смысл (векторы)", rd)
both = np.mean([(a is not None) or (b is not None) for a, b in zip(rb, rd)])
print(f" хотя бы один из двух нашёл в первых 10: {both:.3f}")
print(f"\nBM25 просмотрел в среднем {np.mean(touched_all):.0f} записей на вопрос "
f"({np.mean(touched_all) / len(docs):.2%} от числа документов), векторный перебор — все {len(docs)}")
У нас этот код напечатал:
документов 20000, средняя длина 48.2 слова, разных слов 24176, индекс построен за 0.18 с
слово f0 встречается в 19900 документах, idf = 0.01
слово f10 встречается в 8385 документах, idf = 0.87
слово f300 встречается в 380 документах, idf = 3.96
слово c17a встречается в 3 документах, idf = 8.65
слово kod-998745 встречается в 1 документах, idf = 9.50
вопросы «пересказ» (300 шт.), пример слов вопроса: ['c5246a', 'c5223b']
слова (BM25) hit@10 = 0.000 MRR@10 = 0.000
смысл (векторы) hit@10 = 0.803 MRR@10 = 0.516
хотя бы один из двух нашёл в первых 10: 0.803
вопросы «код» (300 шт.), пример слов вопроса: ['kod-207920', 'c2729a']
слова (BM25) hit@10 = 1.000 MRR@10 = 0.538
смысл (векторы) hit@10 = 0.030 MRR@10 = 0.015
хотя бы один из двух нашёл в первых 10: 1.000
вопросы «те же слова» (300 шт.), пример слов вопроса: ['c4814a', 'c4803b']
слова (BM25) hit@10 = 1.000 MRR@10 = 0.973
смысл (векторы) hit@10 = 0.807 MRR@10 = 0.534
хотя бы один из двух нашёл в первых 10: 1.000
BM25 просмотрел в среднем 9 записей на вопрос (0.04% от числа документов), векторный перебор — все 20000
Что видно. На пересказах поиск по словам не нашёл ни одного правильного документа — общих слов просто нет, — а векторы нашли 80,3% в первой десятке. На вопросах с кодом картина зеркальная: BM25 находит 100%, векторы — 3%. Обратите внимание на MRR@10 = 0,538 у BM25 на кодах: правильный документ попадает в десятку всегда, но часто вторым или третьим. Причина в формуле второй ступени: вопрос содержит ещё и слово понятия, и короткий документ, где это слово повторено трижды, набирает больше, чем документ с кодом, где этого синонима нет. На вопросах «теми же словами» оба справляются, но BM25 точнее (MRR 0,973 против 0,534). Последняя строка — о цене: BM25 прочитал в среднем 9 записей вхождений на вопрос, векторный перебор сравнил вопрос со всеми 20 000 документами. Строка «хотя бы один из двух нашёл» — это потолок, к которому стремится хорошая склейка.
Где обычно ошибаются.
Словарь ступени.
Векторный поиск (dense retrieval). Поиск по близости векторов, которые модель эмбеддингов строит для вопроса и документов.
Разреженный поиск (sparse retrieval). Другое название поиска по словам: вектор документа в нём — счётчики слов, почти все равны нулю.
Незнакомое слово (out-of-vocabulary). Строка, которую модель не видела при обучении и потому плохо кодирует смыслом.
Закон Ципфа. Наблюдение, что частота слова примерно обратно пропорциональна его месту в списке слов по частоте.
hit@10. Доля вопросов, у которых правильный документ попал в первые 10 результатов.
MRR (mean reciprocal rank). Среднее значение 1/место правильного ответа; 1 — всегда первый, 0 — никогда не в списке.
Проверочный набор вопросов. Вопросы с заранее известными правильными документами, на которых сравнивают настройки поиска.
Зачем это в работе. Гибридный поиск (hybrid search) — это два поиска по одному вопросу и одна общая выдача. Сами поиски уже готовы; всё качество гибрида решает способ склейки (fusion). В Weaviate за это отвечают параметры alpha и fusion_type, в Elasticsearch — retriever rrf с rank_constant и rank_window_size, в Qdrant — запрос с fusion. Если склеить неудачно, гибрид окажется хуже, чем любой из двух поисков по отдельности, и это очень частая ситуация.
Как это устроено. Шаг первый: каждый поиск возвращает своих кандидатов — например, по 100 лучших. Шаг второй: их надо свести к одной шкале. Самый очевидный путь — сложить оценки как есть, но он не работает: оценки BM25 бывают от нуля до десятков, косинусы — от −1 до 1, и сумма почти целиком повторяет BM25. Поэтому оценки сначала нормируют (score normalization). Нормировка min-max переводит оценки каждого списка в отрезок от 0 до 1: лучший получает 1, худший 0. Нормировка z-оценками вычитает среднее и делит на разброс. Затем берут взвешенную сумму: (1 − alpha) × слова + alpha × смысл. В Weaviate так и устроено: alpha = 1 — чистый вектор, alpha = 0 — чистый BM25, а склейка по относительным оценкам (relative score fusion) там по умолчанию с версии 1.24.
Второй путь — вообще не смотреть на оценки, а только на места. Это обратный ранг (reciprocal rank fusion, RRF): документ получает сумму 1/(k + место) по всем спискам, где он есть. Метод предложили Cormack, Clarke и Büttcher в статье на конференции SIGIR 2009, там же — k = 60; в Elasticsearch rank_constant по умолчанию тоже 60. Чем меньше k, тем сильнее первые места отрываются от остальных; чем больше, тем важнее попасть в оба списка, пусть и не на первые места.
У каждого пути своё ограничение. Нормировка min-max зависит от худшего кандидата в списке: если в списке BM25 всего два документа, второй получит 0, даже если он почти так же хорош. RRF не боится разных шкал, но выбрасывает информацию о том, насколько первый лучше второго: документ, который BM25 нашёл с огромным отрывом по редкому коду, получает за первое место столько же, сколько получил бы при ничьей.
Чем склейка отличается от соседнего понятия — пересортировки (reranking). Пересортировка — это следующий, более дорогой шаг: отдельная модель-перекрёстный кодировщик читает вопрос вместе с каждым кандидатом и ставит новые оценки. Склейка работает только с уже посчитанными оценками или местами и почти ничего не стоит; пересортировку обычно ставят после неё, на несколько десятков лучших кандидатов.
Подробный пример. Тот же игрушечный мир и те же 900 вопросов. Из каждого поиска берём по 100 кандидатов (у BM25 — только документы, где есть хоть одно слово вопроса) и сравниваем девять способов: каждый поиск отдельно, сумму оценок как есть, min-max с тремя значениями alpha, z-оценки и RRF с k = 60 и k = 5.
from common import *
docs, vecs, W = make_world()
Q = make_queries(docs, W)
bm = BM25(docs)
DEPTH = 100 # сколько кандидатов берём из каждого списка
def lists(words, qv, depth=DEPTH):
sb, _ = bm.scores(words); sd = vecs @ qv
ib = topk(sb, depth); ib = ib[sb[ib] > 0] # у BM25 в списке только документы с общими словами
idn = topk(sd, depth)
return (ib, sb[ib]), (idn, sd[idn])
def fuse_scores(L1, L2, how, alpha=0.5):
(i1, s1), (i2, s2) = L1, L2
if how == "сумма как есть": f1, f2, a = s1, s2, 0.5
elif how == "min-max":
mm = lambda s: (s - s.min()) / (s.max() - s.min()) if len(s) > 1 and s.max() > s.min() else np.ones_like(s)
f1, f2, a = mm(s1), mm(s2), alpha
elif how == "z-оценки":
z = lambda s: (s - s.mean()) / (s.std() + 1e-9) if len(s) > 1 else np.zeros_like(s)
f1, f2, a = z(s1), z(s2), 0.5
out = defaultdict(float)
for i, v in zip(i1, f1): out[i] += (1 - a) * v
for i, v in zip(i2, f2): out[i] += a * v
return out
def rrf(L1, L2, k=60):
out = defaultdict(float)
for ids, _ in (L1, L2):
for r, i in enumerate(ids, 1): out[i] += 1 / (k + r)
return out
def order(d):
return np.array(sorted(d, key=lambda i: -d[i])[:10])
methods = {
"только слова (BM25)": lambda L1, L2: {i: s for i, s in zip(*L1)},
"только смысл (векторы)": lambda L1, L2: {i: s for i, s in zip(*L2)},
"сумма оценок как есть": lambda L1, L2: fuse_scores(L1, L2, "сумма как есть"),
"min-max, alpha = 0.3": lambda L1, L2: fuse_scores(L1, L2, "min-max", 0.3),
"min-max, alpha = 0.5": lambda L1, L2: fuse_scores(L1, L2, "min-max", 0.5),
"min-max, alpha = 0.7": lambda L1, L2: fuse_scores(L1, L2, "min-max", 0.7),
"z-оценки, поровну": lambda L1, L2: fuse_scores(L1, L2, "z-оценки"),
"RRF, k = 60": lambda L1, L2: rrf(L1, L2, 60),
"RRF, k = 5": lambda L1, L2: rrf(L1, L2, 5),
}
cache = {kind: [(lists(w, qv), t) for w, qv, t in qs] for kind, qs in Q.items()}
allr = defaultdict(list)
for kind in Q:
print(f"\nвопросы «{kind}»:")
for name, f in methods.items():
r = [rank_of(order(f(L1, L2)), t) for (L1, L2), t in cache[kind]]
allr[name] += r; report(name, r)
print("\nвсе 900 вопросов вместе:")
for name in methods: report(name, allr[name])
# типичные шкалы оценок, из-за которых «сумма как есть» ведёт себя как один BM25
b1 = [L1[1][0] for (L1, L2), t in cache["код"] if len(L1[1])]
d1 = [L2[1][0] for (L1, L2), t in cache["код"]]
print(f"\nшкалы: лучшая оценка BM25 в среднем {np.mean(b1):.2f}, лучший косинус в среднем {np.mean(d1):.3f}")
У нас этот код напечатал:
вопросы «пересказ»:
только слова (BM25) hit@10 = 0.000 MRR@10 = 0.000
только смысл (векторы) hit@10 = 0.803 MRR@10 = 0.516
сумма оценок как есть hit@10 = 0.347 MRR@10 = 0.046
min-max, alpha = 0.3 hit@10 = 0.627 MRR@10 = 0.115
min-max, alpha = 0.5 hit@10 = 0.733 MRR@10 = 0.202
min-max, alpha = 0.7 hit@10 = 0.790 MRR@10 = 0.433
z-оценки, поровну hit@10 = 0.800 MRR@10 = 0.484
RRF, k = 60 hit@10 = 0.687 MRR@10 = 0.133
RRF, k = 5 hit@10 = 0.710 MRR@10 = 0.179
вопросы «код»:
только слова (BM25) hit@10 = 1.000 MRR@10 = 0.538
только смысл (векторы) hit@10 = 0.030 MRR@10 = 0.015
сумма оценок как есть hit@10 = 1.000 MRR@10 = 0.538
min-max, alpha = 0.3 hit@10 = 0.610 MRR@10 = 0.425
min-max, alpha = 0.5 hit@10 = 0.447 MRR@10 = 0.367
min-max, alpha = 0.7 hit@10 = 0.100 MRR@10 = 0.035
z-оценки, поровну hit@10 = 0.300 MRR@10 = 0.064
RRF, k = 60 hit@10 = 0.873 MRR@10 = 0.388
RRF, k = 5 hit@10 = 0.873 MRR@10 = 0.431
вопросы «те же слова»:
только слова (BM25) hit@10 = 1.000 MRR@10 = 0.973
только смысл (векторы) hit@10 = 0.807 MRR@10 = 0.534
сумма оценок как есть hit@10 = 1.000 MRR@10 = 0.971
min-max, alpha = 0.3 hit@10 = 1.000 MRR@10 = 0.965
min-max, alpha = 0.5 hit@10 = 0.997 MRR@10 = 0.905
min-max, alpha = 0.7 hit@10 = 0.963 MRR@10 = 0.753
z-оценки, поровну hit@10 = 0.973 MRR@10 = 0.772
RRF, k = 60 hit@10 = 1.000 MRR@10 = 0.825
RRF, k = 5 hit@10 = 1.000 MRR@10 = 0.852
все 900 вопросов вместе:
только слова (BM25) hit@10 = 0.667 MRR@10 = 0.504
только смысл (векторы) hit@10 = 0.547 MRR@10 = 0.355
сумма оценок как есть hit@10 = 0.782 MRR@10 = 0.518
min-max, alpha = 0.3 hit@10 = 0.746 MRR@10 = 0.502
min-max, alpha = 0.5 hit@10 = 0.726 MRR@10 = 0.491
min-max, alpha = 0.7 hit@10 = 0.618 MRR@10 = 0.407
z-оценки, поровну hit@10 = 0.691 MRR@10 = 0.440
RRF, k = 60 hit@10 = 0.853 MRR@10 = 0.449
RRF, k = 5 hit@10 = 0.861 MRR@10 = 0.488
шкалы: лучшая оценка BM25 в среднем 15.57, лучший косинус в среднем 0.469
Что видно. Во-первых, гибрид действительно помогает: по всем 900 вопросам BM25 сам по себе находит 66,7%, векторы — 54,7%, а RRF с k = 60 — 85,3%, близко к потолку из третьей ступени. Во-вторых, «сумма как есть» ведёт себя как BM25: лучшая оценка BM25 в среднем 15,57, лучший косинус — 0,469, и на пересказах эта сумма даже хуже чистых векторов (34,7% против 80,3%): документы с теми же синонимами, но без второго понятия, получают от BM25 гигантские баллы и выталкивают правильный. В-третьих, у взвешенной суммы нет одного хорошего alpha: alpha = 0,7 почти догоняет векторы на пересказах (79,0%), но проваливает коды (10,0%); alpha = 0,3 лучше на кодах (61,0%), но хуже на пересказах (62,7%), и ни одно значение не держит оба вида вопросов сразу. В-четвёртых, у RRF самый высокий hit@10, но не самый высокий MRR@10: 0,449 против 0,518 у суммы как есть и 0,504 у чистого BM25, потому что он не видит отрыва по оценке и ставит правильный документ в десятку, но не всегда первым. Меньшее k = 5 подняло MRR@10 до 0,488 и чуть-чуть hit@10 — до 0,861. Какой способ лучше — зависит от доли разных видов вопросов в вашем потоке, и это надо мерить, а не брать из чужой статьи.
Где обычно ошибаются.
Словарь ступени.
Гибридный поиск (hybrid search). Поиск, который запускает и поиск по словам, и векторный поиск и сводит их выдачи в одну.
Склейка (fusion). Способ превратить два списка кандидатов с оценками в один упорядоченный список.
Нормировка оценок (score normalization). Приведение оценок разных поисков к общей шкале перед сложением.
Min-max. Нормировка, при которой лучший кандидат списка получает 1, худший — 0, остальные — пропорционально между ними.
Z-оценка (z-score). Оценка минус среднее по списку, делённая на разброс; показывает, насколько кандидат выделяется.
alpha. Вес векторной половины во взвешенной сумме; 1 — только векторы, 0 — только слова.
Обратный ранг (RRF, reciprocal rank fusion). Склейка по местам: документ получает сумму 1/(k + место) по всем спискам.
Пересортировка (reranking). Отдельный более дорогой шаг после склейки, когда модель заново оценивает каждую пару «вопрос — кандидат».
Зачем это в работе. Гибридный поиск обычно включают одной галочкой, и он сразу работает «неплохо». Проблемы проявляются позже и выглядят как необъяснимые промахи: на русском языке не находится очевидный документ, RAG уверенно отвечает на вопрос, ответа на который в базе нет, а увеличение числа кандидатов почему-то не помогает. У всех трёх случаев понятные причины, и их можно проверить за пару минут.
Как это устроено. Первая ловушка — окончания. В русском у слова десятки форм, а поиск по словам сравнивает строки, поэтому «поиск соседа» не совпадает с «поиске» и «соседей». Решения два. Стемминг (stemming) отрезает окончания по правилам: быстро, но грубо — иногда склеивает разные слова или не трогает чередования. Лемматизация (lemmatization) приводит слово к словарной форме по словарю (для русского так делают, например, pymorphy и mystem): точнее, но медленнее и требует словаря. В Elasticsearch для этого есть готовые анализаторы, в том числе стеммер для русского. Векторы этой проблемой страдают меньше: модель видела разные формы слова при обучении.
Вторая ловушка — «ответа нет». Векторный поиск всегда возвращает k ближайших, даже если ни один не подходит: ближайший сосед есть всегда. Поиск по словам в такой ситуации честно возвращает пустой список. RRF смотрит только на места, а первое место в векторном списке стоит 1/61 — столько же, сколько первое место в списке BM25 с идеальным совпадением. Поэтому по итоговой оценке RRF нельзя понять, нашлось ли хоть что-то. Если системе нужно уметь говорить «в базе этого нет», порог ставят не на итоговую оценку RRF, а на исходные: есть ли совпадения у BM25, насколько велик косинус, что сказала модель пересортировки.
Третья ловушка — глубина списков (в Elasticsearch — rank_window_size). Кажется, что чем больше кандидатов из каждого поиска, тем лучше. Но в хвосте каждого списка в основном шум, и при RRF каждый шумный кандидат, попавший в оба хвоста, получает две небольшие добавки и может обогнать документ, который был высоко только в одном списке. Глубина — тоже настройка, которую надо мерить, а не ставить «побольше». Отличие от nprobe и ef из прошлой дорожки: там больше просмотренных кандидатов почти всегда давало лучший recall, а здесь больше кандидатов может ухудшить итоговый порядок.
Подробный пример. Три небольших замера. (а) Пять документов и вопрос «поиск соседа» — без обработки окончаний и с самой грубой обрезкой окончаний на десяток строк. (б) 200 вопросов, состоящих из одного кода: сначала из кода, который есть в базе, потом из кода, которого нет; вектор незнакомого кода в обоих случаях — шум, как в третьей ступени. Сравниваем, что видит BM25, векторы и RRF. (в) RRF с k = 60 на всех 900 вопросах при глубине 10, 30, 100 и 1000 кандидатов из каждого списка. Функции lists, rrf и order — те же, что в четвёртом примере, они вынесены в файл ex4_lib.py.
from common import *
import ex4_lib as F # те же функции склейки, что в четвёртой ступени
# (а) русские окончания: «поиск», «поиска», «поиске» — для BM25 три разных слова
docs_text = [
"Индекс HNSW строит граф соседей и ищет по нему жадно",
"Параметр nprobe задаёт, сколько ячеек IVF просматривать при поиске",
"Поиск по смыслу находит пересказ, но путает редкие имена",
"Граф соседей в HNSW хранит обратные рёбра",
"Скорость поиска ближайшего соседа зависит от индекса",
]
END = sorted("а я о е ы и у ю ь ей ой ом ем ам ям ах ях ов ев ами ями ого его ому ему ая яя ое ее ые ие ую юю".split(), key=len, reverse=True)
def stem(w):
for e in END:
if w.endswith(e) and len(w) - len(e) >= 4: return w[:-len(e)]
return w
q = "поиск соседа"
for name, f in (("как есть", lambda t: tokens(t)), ("обрезка окончаний", lambda t: [stem(w) for w in tokens(t)])):
bm = BM25([f(t) for t in docs_text]); s, _ = bm.scores(f(q))
print(f"{name:<18s} вопрос {f(q)} -> нашлись документы {[int(i) for i in np.where(s > 0)[0]]}")
print("обрезка склеивает разное:", [stem(w) for w in ("граната", "гранат")], [stem(w) for w in ("сталь", "стали", "стал")])
# (б) «ответа нет»: код, которого нет в базе
docs, vecs, W = make_world(); bm = BM25(docs); F.setup(bm, vecs)
rng = np.random.default_rng(7)
with_code = [i for i, c in enumerate(W["codes"]) if c]
real, fake = [], []
for j in range(200):
i = with_code[rng.integers(len(with_code))]
v = rng.normal(size=vecs.shape[1]).astype(np.float32); v /= np.linalg.norm(v) # вектор незнакомого кода — шум
for code, bucket in ((W["codes"][i], real), (f"kod-{rng.integers(10**5, 10**6)}x", fake)):
L1, L2 = F.lists([code], v)
r = F.rrf(L1, L2, 60); top = max(r.values())
bucket.append((len(L1[0]), L1[1][0] if len(L1[0]) else 0.0, float(L2[1][0]), top))
for name, b in (("код есть в базе", real), ("кода нет в базе", fake)):
a = np.array(b)
print(f"{name}: BM25 нашёл документов в среднем {a[:,0].mean():.2f}, лучшая оценка BM25 {a[:,1].mean():.2f}, "
f"лучший косинус {a[:,2].mean():.3f}, лучшая оценка RRF {a[:,3].mean():.5f}, выдача RRF непустая в {np.mean(a[:,3] > 0):.0%}")
# (в) глубина списков перед склейкой
Q = make_queries(docs, W)
for depth in (10, 30, 100, 1000):
r = [rank_of(F.order(F.rrf(*F.lists(w, qv, depth), 60)), t) for qs in Q.values() for w, qv, t in qs]
report(f"RRF k=60, по {depth} кандидатов из списка", r)
У нас этот код напечатал:
как есть вопрос ['поиск', 'соседа'] -> нашлись документы [2, 4]
обрезка окончаний вопрос ['поиск', 'сосед'] -> нашлись документы [0, 1, 2, 3, 4]
обрезка склеивает разное: ['гранат', 'гранат'] ['стал', 'стал', 'стал']
код есть в базе: BM25 нашёл документов в среднем 1.00, лучшая оценка BM25 9.57, лучший косинус 0.462, лучшая оценка RRF 0.01643, выдача RRF непустая в 100%
кода нет в базе: BM25 нашёл документов в среднем 0.00, лучшая оценка BM25 0.00, лучший косинус 0.462, лучшая оценка RRF 0.01639, выдача RRF непустая в 100%
RRF k=60, по 10 кандидатов из списка hit@10 = 0.864 MRR@10 = 0.495
RRF k=60, по 30 кандидатов из списка hit@10 = 0.861 MRR@10 = 0.472
RRF k=60, по 100 кандидатов из списка hit@10 = 0.853 MRR@10 = 0.449
RRF k=60, по 1000 кандидатов из списка hit@10 = 0.841 MRR@10 = 0.441
Что видно. (а) Без обработки окончаний вопрос «поиск соседа» нашёл 2 документа из 5; после обрезки окончаний — все 5, включая «при поиске» и «граф соседей». Но та же обрезка превратила «граната» и «гранат», а также «сталь», «стали» и «стал» в одну строку: в поиске по металлургии появятся тексты, где кто-то «стал» начальником. (б) Если код есть в базе, BM25 находит ровно один документ с оценкой 9,57, если нет — ноль документов. Векторный поиск в обоих случаях выдаёт соседа с косинусом 0,462, а лучшая оценка RRF — 0,01643 и 0,01639, разница в четвёртом знаке. Выдача RRF непустая в 100% случаев, то есть по ней пользователь получит «ответ» и на несуществующий код. (в) Глубина 10 дала hit@10 = 0,864, глубина 1000 — 0,841: в нашем мире лишние кандидаты из хвостов немного мешают. На ваших данных может быть иначе, поэтому глубину подбирают замером на проверочном наборе.
Где обычно ошибаются.
Словарь ступени.
Стемминг (stemming). Отрезание окончаний по правилам, чтобы разные формы слова стали одной строкой.
Лемматизация (lemmatization). Приведение слова к словарной форме по словарю языка: «поиске» → «поиск».
Анализатор (analyzer). Цепочка обработки текста в Elasticsearch и OpenSearch: токенизация, нижний регистр, стемминг и т. п.
Пересклейка (overstemming). Ошибка стемминга, когда разные по смыслу слова сводятся к одной основе.
Глубина списка (rank_window_size). Сколько кандидатов из каждого поиска передаётся в склейку.
Пустая выдача. Честный ответ поиска по словам «совпадений нет», которого векторный поиск дать не может.
Порог отсечения. Значение оценки, ниже которого результат считается неподходящим и не показывается.
Словарь целиком — /slovar, новости — /novosti. Все дорожки — /put.