Теоретический фундамент (Information Retrieval)

kirill_ir · Сообщение **kirill_ir** » 16 май 2026, 07:31

Часть I · ~8 ч · Сложность: (базовый)→(средний) · Пререквизиты: Модуль 0

Обзор модуля

Этот модуль закладывает теоретическую базу всего курса. Прежде чем разбирать, как поисковая система обходит веб, строит индекс и ранжирует миллиарды документов, нужно понять элементарную задачу information retrieval (IR): дан запрос и коллекция документов — как численно оценить, насколько документ отвечает на запрос, и как упорядочить документы по этой оценке. Всё остальное в курсе — это масштабирование, ускорение и усложнение этой одной идеи.

Мы пройдём путь от самого грубого представления текста («мешок слов») до моделей, которые до сих пор работают в ядре любой промышленной ПС. Сначала научимся превращать сырой текст в нормализованные термины (токенизация, нормализация, стемминг, стоп-слова). Затем построим три классические модели поиска — булеву, векторную (TF-IDF + косинус) и вероятностные/языковые — и поймём, чем они отличаются и почему вероятностный взгляд оказался самым плодотворным (из него вырастет BM25 в Модуле 6). Наконец, разберём, как вообще понять, что поиск хороший: метрики precision/recall, F1, MAP, MRR, nDCG и PR-кривые.

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

После модуля студент сможет вручную посчитать TF-IDF и косинусную близость на мини-корпусе, объяснить разницу между булевым и ранжирующим поиском, вывести формулу query likelihood со сглаживанием и оценить качество ранжированной выдачи метриками MAP/MRR/nDCG.

Как читать по трекам

Студент CS — все четыре главы обязательны, с выводами формул и ручными расчётами. Это базис экзамена и всех последующих модулей.
Инженер поиска/ML — все главы обязательны. Особое внимание: инженерные заметки про обратный индекс, нормировку длины, реализацию метрик в офлайн-оценке.
SEO-специалист — главы 1.1 и 1.2 обязательны (как ПС «видит» текст и почему важна редкость слова), 1.3 — обзорно (интуиция вместо вывода), 1.4 — обязательно (понимать, чем меряют качество выдачи). Читайте все SEO-врезки.
Смешанный/руководитель — читайте «Интуицию», «Примеры» и «Итоги»; выводы формул можно пролистать.

Карта модуля

1.1 — как сырой текст превращается в термины: мешок слов, токенизация, нормализация, стемминг/лемматизация, стоп-слова. (базовый)
1.2 — три способа сопоставить запрос и документ: булев поиск, векторная модель, TF-IDF, косинусная близость. (средний)
1.3 — вероятностный взгляд на релевантность и языковые модели: query likelihood и сглаживание. (средний)
1.4 — как измерить качество: precision/recall, F1, MAP, MRR, nDCG, PR-кривые. (средний)

Глава 1.1. Модель «мешка слов», токенизация, нормализация, стемминг/лемматизация, стоп-слова (базовый)

Цели обучения

После этой главы студент сможет:

объяснить модель «мешка слов» (bag of words) и явно назвать, какую информацию она отбрасывает;
разбить текст на токены и перечислить типичные ловушки токенизации;
применить нормализацию (регистр, диакритика, словоформы) и объяснить связь нормализации с обратным индексом;
сравнить стемминг и лемматизацию по точности и стоимости;
обосновать, когда стоп-слова полезно убирать, а когда удаление вредит.

Конспект

Поисковая система не понимает текст как человек. Её первая задача — превратить документ и запрос в сопоставимые единицы, чтобы их можно было сравнивать механически. Эти единицы называют термины (terms). Конвейер «текст → термины» называют анализом текста (text analysis), и одинаковый анализ обязан применяться и к документам при индексации, и к запросу при поиске — иначе они не «встретятся».

Модель «мешка слов» (bag of words)

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

Формально документ d представляется как мультимножество (мешок) терминов: для каждого термина t известна его частота в документе tf(t, d) — сколько раз t встретился в d. Информация о порядке слов, синтаксисе и расстоянии между словами отбрасывается.

Что теряется и почему это важно:

Порядок и фразы. «собака укусила человека» и «человек укусил собаку» дают одинаковый мешок. Чтобы различать их, позже введут позиционный индекс и фразовый поиск (Модули 4, 6).
Близость слов. «дешёвый авиабилет Москва» как набор слов не отличает документ, где эти слова стоят рядом, от документа, где они разбросаны по разным абзацам.
Семантика и синонимы. Мешок не знает, что «авто» и «машина» — почти одно и то же. Это починят нейромодели (Модуль 10).

Несмотря на потери, мешок слов — основа всех классических моделей этого модуля, потому что он даёт обратный индекс (inverted index): отображение «термин → список документов, где он встречается». Именно обратный индекс позволяет за миллисекунды найти документы по запросу, не перебирая всю коллекцию.

Инженерная заметка. Обратный индекс — это словарь терминов (term dictionary), где каждому термину сопоставлен список вхождений (postings list): идентификаторы документов и метаданные (частота, позиции). Анализ текста определяет, что станет ключом словаря. Если документ проанализирован как Бег, а запрос — как бег, ключи разные и совпадения не будет. Поэтому правило №1: анализ документа и анализ запроса должны быть согласованы.

Токенизация (tokenization)

Токенизация — разбиение строки символов на токены: предварительные кандидаты в термины (обычно «слова»). Кажется тривиальной («режем по пробелам»), но содержит много ловушек.

Типичные проблемы:

Пунктуация и дефисы. IP-адрес, что-то, e-mail — один токен или два? Решение влияет на находимость.
Апострофы и сокращения. D'Artagnan, don't.
Числа, даты, версии. 2026, 12.04.2026, v1.2.3, телефон +7 900 000-00-00.
Языки без пробелов. В ряде языков слова не разделяются пробелами — нужна словарная или статистическая сегментация.
URL, e-mail, хэштеги, эмодзи. Часто требуют специальных правил.
Составные слова (немецкий Donaudampfschiff…) — может требоваться декомпозиция.

Пример. Строка Купил смартфон X2-15 за 79 990 руб. при наивной токенизации по пробелам даст токены Купил, смартфон, X2-15, за, 79, 990, руб.. Хорошая токенизация уберёт точку из руб., склеит 79 990 в число 79990 и решит, дробить ли X2-15 на X2 + 15. От этих решений напрямую зависит, найдётся ли документ по запросу x2 15.

Нормализация (normalization)

После токенизации токены приводят к каноническому виду, чтобы варианты написания совпадали как термины:

Регистр (case folding): Поиск → поиск. Осторожно с аббревиатурами: US (страна) vs us (англ. «нас»).
Диакритика и буква ё/е: café ↔ cafe, ёлка ↔ елка.
Юникод-нормализация (NFC/NFKC): один и тот же символ может быть закодирован по-разному.
Удаление/унификация пунктуации, обработка апострофов и дефисов.

Внимание. Нормализация повышает полноту (recall), но может снизить точность (precision): склеив US и us, мы найдём больше документов, но среди них будет мусор. Это фундаментальный компромисс, к которому мы вернёмся в главе 1.4.

Стемминг и лемматизация

Одно слово в естественном языке имеет много словоформ: бежать, бегу, бежал, бегущий. Чтобы запрос бежать находил документ со словом бегущий, словоформы приводят к общей основе.

Стемминг (stemming) — грубое отсечение окончаний/суффиксов по правилам, без словаря. Быстро, но иногда даёт несуществующую «основу» и ошибки:

бегущий → бег (хорошо), но университет → университ.
Англ.: running → run, но university/universe → univers (склеивает разные слова — overstemming); news → new (искажает смысл).

Лемматизация (lemmatization) — приведение к словарной форме (лемме) с учётом части речи и словаря: бежал → бежать, мыши → мышь. Точнее, но дороже (нужны словарь и морфоанализ) и зависит от языка.

Код: Выделить всё

Свойство              |  Стемминг                   |  Лемматизация
----------------------+-----------------------------+-------------------------
Метод                 |  правила отсечения          |  словарь + морфология
Скорость              |  высокая                    |  ниже
Результат             |  может быть не словом       |  всегда настоящее слово
Точность              |  ниже (over/understemming)  |  выше
Зависимость от языка  |  средняя                    |  высокая
Типичное применение   |  большие веб-индексы        |  там, где важна точность

Заблуждение. «Стемминг и лемматизация — одно и то же, просто разные названия.» Нет: стемминг механически режет строку (лошади → лошад), лемматизация возвращает корректную лемму (лошади → лошадь). Разница видна на нерегулярных формах: стеммер не превратит шёл в идти, а лемматизатор — превратит.

Стоп-слова (stop words)

Стоп-слова — очень частотные служебные слова (и, в, на, the, of), которые почти не несут различающей информации. Их исторически удаляли, чтобы:

сократить размер индекса (короткие частотные термины дают огромные postings list);
ускорить поиск.

Но удаление стоп-слов не всегда безопасно:

Фраза to be or not to be целиком состоит из стоп-слов — удалив их, мы потеряем запрос.
группа The Who — the и who здесь значимы.
Предлоги меняют смысл: работа в Москве vs работа из Москвы.

Инженерная заметка. Современные системы чаще не удаляют стоп-слова жёстко, а понижают их вес: модели вроде TF-IDF/BM25 (главы 1.2–1.3, Модуль 6) автоматически дают частотным словам почти нулевой вклад через IDF. Это элегантнее, чем чёрный список, и не ломает фразовые запросы.

SEO-врезка. Понимание анализа текста объясняет, почему «точное вхождение ключа» переоценено. ПС индексирует нормализованные термины, а не вашу буквальную фразу: после стемминга купить велосипеды и куплю велосипед дают почти одинаковые термины. Писать неестественно («велосипед купить велосипед дёшево велосипед») бессмысленно — частотные повторы гасятся насыщением и IDF (главы 1.2–1.3), а читаемость падает. Пишите естественно и покрывайте словоформы и синонимы темы, а не одну фразу.

Частые заблуждения

Заблуждение. «Раз порядок слов теряется в мешке слов, фразовый поиск невозможен.» Мешок слов — это базовая модель скоринга; для фраз ПС хранит позиции терминов в позиционном индексе и проверяет соседство отдельно. Одно не отменяет другого.

Заблуждение. «Удаление стоп-слов всегда ускоряет и улучшает поиск.» Ускоряет — да, улучшает — не всегда: страдают фразы и запросы, состоящие из частотных слов. Поэтому решают взвешиванием, а не удалением.

Лаба / практика

Цель: реализовать конвейер анализа текста и собрать обратный индекс.

Вход: мини-корпус из 4 коротких документов (на русском или английском, по 1–2 предложения).

Шаги:

Токенизируйте каждый документ (разбейте по пробелам и пунктуации).
Нормализуйте: lower-case, уберите пунктуацию, унифицируйте ё→е.
Примените простой стеммер (можно готовую библиотеку или правило отсечения 2–3 распространённых окончаний).
Удалите стоп-слова по списку из ~20 слов.
Постройте словарь терминов и postings lists (термин → {docId: tf}).
Сравните результат с шагом без удаления стоп-слов: насколько изменился индекс?

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

Время: ~45 мин. Критерий «сделано»: индекс согласован (один и тот же анализатор), приведён хотя бы один пример ошибки стеммера и один пример вреда от удаления стоп-слов.

Контрольные вопросы

Какую информацию о тексте отбрасывает модель «мешок слов»? Приведите два запроса, которые она не различит.
Почему анализ документа и анализ запроса обязаны быть одинаковыми? Что сломается, если индексировать Бег, а искать бег?
Назовите три ловушки токенизации и предложите для каждой решение.
В чём разница между стеммингом и лемматизацией? Приведите словоформу, на которой они дадут разный результат.
Что такое overstemming и understemming? Дайте пример каждого.
Почему удаление стоп-слов может навредить? Приведите запрос, который оно ломает.
Как современные модели «обезвреживают» частотные слова без чёрного списка?

Глава 1.2. Булев поиск, векторная модель, TF-IDF, косинусная близость (средний)

Цели обучения

После этой главы студент сможет:

сформулировать булеву модель поиска и назвать её главное ограничение;
объяснить идею векторного пространства и представить документ/запрос как вектор;
вывести компоненты TF-IDF и объяснить, зачем нужна каждая;
посчитать косинусную близость вручную на мини-корпусе;
объяснить, почему косинус, а не евклидово расстояние, и роль нормировки длины.

Конспект

У нас есть термины (глава 1.1). Теперь нужно по запросу q упорядочить документы. Рассмотрим три исторических подхода в порядке роста выразительности.

Булева модель (Boolean retrieval)

Самая ранняя модель. Документ либо содержит термин, либо нет (множества по 0/1). Запрос — логическое выражение из AND, OR, NOT.

Пример. Запрос (велосипед AND горный) AND NOT детский. Система берёт postings list термина велосипед, пересекает (AND) со списком горный и вычитает (NOT) список детский. Результат — множество документов, удовлетворяющих условию.

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

Главное ограничение — нет ранжирования: все подходящие документы равноправны. По запросу из 3 слов либо тысячи документов «подходят» (и непонятно, какой первый), либо ноль (AND слишком строг). Нет понятия «насколько» документ релевантен.

Заблуждение. «Булев AND гарантирует лучшие результаты, потому что слова точно есть.» Он гарантирует наличие слов, но не релевантность и не порядок. Документ, упомянувший велосипед и горный по разу в футере, формально подходит наравне с профильным каталогом горных велосипедов.

Векторная модель (Vector Space Model, VSM)

Идея: представить и документ, и запрос как векторы в пространстве, где каждое измерение — отдельный термин словаря. Координата — вес термина в документе. Чем «ближе» векторы, тем релевантнее документ.

Интуиция. Если словарь — это {велосипед, горный, детский, цена} (4 измерения), то документ про горные велосипеды — это стрелка, сильно вытянутая вдоль осей велосипед и горный. Запрос горный велосипед — стрелка в ту же сторону. «Похожесть» = насколько стрелки сонаправлены.

Осталось определить две вещи: как считать вес термина (TF-IDF) и как мерить близость векторов (косинус).

TF-IDF: вес термина

Вес термина складывается из двух множителей: насколько термин важен внутри документа (TF) и насколько он редок по коллекции (IDF).

Term Frequency (TF) — частота термина в документе. Базовый вариант — просто tf(t,d). Но 100 вхождений не в 100 раз важнее одного.

Интуиция (насыщение). Первое вхождение слова — сильный сигнал «документ про это». Сотое почти ничего не добавляет. Поэтому TF часто логарифмируют:
wtf(t,d) = 1 + log10(tf(t,d)), если tf > 0, иначе 0.

Document Frequency и IDF. df(t) — в скольких документах коллекции встречается термин t. Inverse Document Frequency:

idf(t) = log10( N / df(t) ),

где N — число документов в коллекции.

Интуиция (редкость). Слово и есть почти везде (df ≈ N) → idf ≈ log(1) = 0 → нулевой вклад. Слово сольвалоу встречается в 2 документах из миллиона → огромный IDF → если оно совпало, это сильнейший сигнал. IDF автоматически обесценивает стоп-слова — то самое «обезвреживание» из главы 1.1.

Итоговый вес:

w(t,d) = wtf(t,d) · idf(t) = (1 + log10 tf(t,d)) · log10(N/df(t)).

Пример (расчёт IDF). Пусть N = 1000. Термин и: df = 1000 → idf = log10(1000/1000) = log10(1) = 0. Термин велосипед: df = 100 → idf = log10(10) = 1. Термин сольвалоу: df = 1 → idf = log10(1000) = 3. Видно: чем реже слово, тем больше его вес.

Косинусная близость (cosine similarity)

Близость двух векторов меряют косинусом угла между ними:

cos(q, d) = (q · d) / (‖q‖ · ‖d‖) = Σ_t (w(t,q)·w(t,d)) / ( sqrt(Σ_t w(t,q)²) · sqrt(Σ_t w(t,d)²) ).

Числитель — скалярное произведение (сумма произведений весов по общим терминам). Знаменатель — произведение длин (норм) векторов: он нормирует длину документа.

Интуиция (почему косинус, а не евклидово расстояние). Длинный документ повторяет слова много раз → его вектор «длинный». По евклидову расстоянию короткий релевантный документ казался бы дальше просто из-за масштаба. Косинус смотрит только на направление (про что документ), игнорируя длину. Значение косинуса — от 0 (нет общих терминов, ортогональны) до 1 (сонаправлены).

Внимание. Нормировка длины — палка о двух концах. Она честно уравнивает длинный и короткий документы по «тематике», но слишком агрессивная нормировка наказывает длинные документы, которые объективно полнее. В BM25 (Модуль 6) появится настраиваемый параметр b, регулирующий силу нормировки длины.

Полный пример расчёта на мини-корпусе

Корпус из N = 3 документов (термины уже нормализованы):

d1: «горный велосипед горный велосипед» → tf: горный=2, велосипед=2
d2: «детский велосипед цена» → tf: детский=1, велосипед=1, цена=1
d3: «горный поход палатка» → tf: горный=1, поход=1, палатка=1

Запрос q: «горный велосипед».

Шаг 1. df и idf (N=3, idf = log10(N/df)):

Код: Выделить всё

Термин     |  df         |  idf = log10(3/df)
-----------+-------------+--------------------
горный     |  2 (d1,d3)  |  log10(1.5) ≈ 0.176
велосипед  |  2 (d1,d2)  |  log10(1.5) ≈ 0.176
детский    |  1          |  log10(3) ≈ 0.477
цена       |  1          |  log10(3) ≈ 0.477
поход      |  1          |  log10(3) ≈ 0.477
палатка    |  1          |  log10(3) ≈ 0.477

Шаг 2. Веса w = (1 + log10 tf) · idf (считаем только нужные термины).

Для tf=1: 1+log10(1) = 1. Для tf=2: 1+log10(2) ≈ 1.301.

d1: горный 1.301·0.176 ≈ 0.229; велосипед 1.301·0.176 ≈ 0.229.
d2: велосипед 1·0.176 = 0.176; детский 1·0.477 = 0.477; цена 1·0.477 = 0.477.
d3: горный 1·0.176 = 0.176; поход 0.477; палатка 0.477.
q: горный 1·0.176 = 0.176; велосипед 1·0.176 = 0.176.

Шаг 3. Скалярные произведения q·d (по общим терминам):

q·d1 = 0.176·0.229 + 0.176·0.229 ≈ 0.0403 + 0.0403 = 0.0806.
q·d2 = велосипед: 0.176·0.176 ≈ 0.0310 (термина горный в d2 нет).
q·d3 = горный: 0.176·0.176 ≈ 0.0310 (термина велосипед в d3 нет).

Шаг 4. Нормы векторов:

‖q‖ = sqrt(0.176² + 0.176²) = sqrt(0.0620) ≈ 0.249.
‖d1‖ = sqrt(0.229² + 0.229²) = sqrt(0.1049) ≈ 0.324.
‖d2‖ = sqrt(0.176² + 0.477² + 0.477²) = sqrt(0.0310+0.2275+0.2275) = sqrt(0.486) ≈ 0.697.
‖d3‖ = sqrt(0.176² + 0.477² + 0.477²) ≈ 0.697.

Шаг 5. Косинусы:

cos(q,d1) = 0.0806 / (0.249·0.324) = 0.0806 / 0.0807 ≈ 0.999.
cos(q,d2) = 0.0310 / (0.249·0.697) = 0.0310 / 0.1735 ≈ 0.179.
cos(q,d3) = 0.0310 / (0.249·0.697) ≈ 0.179.

Итоговое ранжирование: d1 (0.999) > d2 ≈ d3 (0.179).

Пример (разбор результата). d1 — почти идеальный ответ: он только про горные велосипеды, оба слова запроса присутствуют. d2 и d3 совпали лишь по одному термину каждый, плюс их векторы «разбавлены» дополнительными словами (детский/цена, поход/палатка) — нормировка длины их понизила. Так VSM даёт порядок, которого не было в булевой модели.

SEO-врезка. Из расчёта видно, что попадание редкого релевантного термина (высокий IDF) ценнее, чем десятое повторение частотного слова. Для оптимизации это значит: покрывайте специфичную, тематически-точную лексику страницы (термины, которых нет у конкурентов), а не накручивайте частоту общих слов. И помните про нормировку длины — «размывание» страницы посторонними блоками уменьшает её косинус к целевому запросу.

Частые заблуждения

Заблуждение. «TF-IDF учитывает порядок слов.» Нет, это по-прежнему мешок слов. Веса считаются по частотам, позиции игнорируются.

Заблуждение. «Чем длиннее документ, тем выше он ранжируется, ведь больше вхождений.» Косинус нормирует длину: длинный документ имеет длинный вектор в знаменателе, и преимущество от повторов сокращается.

Лаба / практика

Цель: реализовать ранжирование TF-IDF + косинус и сверить с булевым поиском.

Вход: мини-корпус из 5 документов и запрос из 2–3 слов.

Шаги:

Постройте словарь, tf, df, посчитайте idf = log10(N/df).
Посчитайте веса w = (1 + log10 tf)·idf для документов и запроса.
Посчитайте cos(q, d) для каждого документа, отсортируйте.
Отдельно выполните булев AND-поиск по тем же словам.
Сравните: какие документы булев поиск вернул без порядка, как их упорядочил косинус.

Ожидаемый результат: таблица tf/idf/w, список косинусов, отсортированная выдача и текстовый разбор отличий от булевой модели.

Время: ~50 мин. Критерий «сделано»: порядок совпал с эталоном (±перестановки при равных скорах), объяснено влияние IDF и нормировки длины хотя бы на одном документе.

Контрольные вопросы

Почему булева модель не годится для веб-поиска из миллиардов страниц?
Что представляет собой измерение векторного пространства и что — координата?
Зачем логарифмировать TF? Что моделирует этот логарифм?
Чему равен IDF стоп-слова, встречающегося во всех документах, и почему это удобно?
Почему для близости берут косинус, а не евклидово расстояние?
Что делает знаменатель в формуле косинуса и какой компромисс он создаёт?
Два документа отличаются только тем, что один в 3 раза длиннее (то же содержание трижды). Как соотносятся их косинусы к запросу и почему?

Глава 1.3. Вероятностные модели релевантности и языковые модели (query likelihood, сглаживание) (средний)

Цели обучения

После этой главы студент сможет:

сформулировать «принцип вероятностного ранжирования» (Probability Ranking Principle);
объяснить идею модели query likelihood и интерпретировать документ как языковую модель;
вывести скор query likelihood как сумму логарифмов вероятностей терминов;
объяснить проблему нулевой вероятности и роль сглаживания;
сравнить сглаживание Йелинека–Мерсера и Дирихле и связать их с TF-IDF/BM25.

Конспект

Векторная модель работает, но её веса (TF-IDF, косинус) выбраны во многом эвристически: почему именно логарифм, почему косинус? Вероятностный подход даёт принципиальный фундамент: будем рассуждать в терминах вероятностей релевантности.

Принцип вероятностного ранжирования

Принцип (Probability Ranking Principle). Если ранжировать документы по убыванию вероятности их релевантности запросу — при разумных предположениях это оптимальное упорядочивание (минимизирует ожидаемые потери пользователя).

То есть «правильный» скор документа d для запроса q — это P(R=1 | d, q), вероятность, что d релевантен. Эта идея порождает целое семейство моделей. Из неё, в частности, выводится BM25 (Модуль 6) — поэтому здесь мы закладываем интуицию, а строгий вывод BM25 отложим.

Языковые модели и query likelihood

Альтернативный, очень элегантный взгляд — языковые модели (language models). Представим, что каждый документ d «умеет порождать текст»: у него есть своя вероятностная модель языка M_d, которая для любого слова t выдаёт вероятность P(t | M_d).

Интуиция. Вообразите: автор документа d написал его, случайно вытягивая слова из своего «мешка вероятностей». Документ про горные велосипеды чаще вытягивает велосипед, горный, рама. Теперь спросим: насколько вероятно, что именно этот документ сгенерировал бы наш запрос? Чем вероятнее — тем документ релевантнее. Это и есть модель query likelihood.

Формально ранжируем документы по P(q | M_d) — вероятности породить запрос q из языковой модели документа d. В простейшей (unigram) модели слова независимы, поэтому вероятность запроса — произведение по его терминам:

P(q | M_d) = Π_{t∈q} P(t | M_d).

Максимально-правдоподобная оценка вероятности термина — его доля в документе:

P_ml(t | M_d) = tf(t,d) / |d|,

где |d| — длина документа (число токенов).

Произведение многих вероятностей <1 быстро уходит в очень малые числа (underflow), поэтому на практике ранжируют по логарифму (логарифм монотонен, порядок сохраняется):

log P(q | M_d) = Σ_{t∈q} log P(t | M_d).

Проблема нулевой вероятности

Внимание. Если хотя бы один термин запроса не встречается в документе, то P_ml(t|M_d) = 0, всё произведение обнуляется (а логарифм уходит в −∞). Тогда документ, идеально совпавший по 4 словам из 5, получит нулевой скор из-за единственного отсутствующего слова. Это недопустимо.

Лечение — сглаживание (smoothing): ни одному слову не присваиваем нулевую вероятность. Резервируем часть вероятностной массы для «невиданных» слов, оценивая их через языковую модель всей коллекции M_C (как часто слово встречается в корпусе вообще).

Интуиция. Если документ не упомянул слово, это ещё не значит «вероятность ноль» — может, тема просто не дошла. Опираемся на фон: насколько слово вообще частотно в коллекции.

Два классических метода сглаживания

1. Йелинек–Мерсер (Jelinek–Mercer) — линейное смешивание модели документа и модели коллекции с фиксированным коэффициентом λ ∈ (0,1):

P(t | d) = λ · (tf(t,d)/|d|) + (1−λ) · P(t | M_C).

λ ближе к 1 — больше доверия документу (хорошо для коротких запросов); ближе к 0 — больше сглаживания.

2. Сглаживание Дирихле (Dirichlet) — добавляет μ «псевдонаблюдений» из модели коллекции; сила сглаживания зависит от длины документа:

P(t | d) = ( tf(t,d) + μ·P(t | M_C) ) / ( |d| + μ ).

Интуиция (почему Дирихле обычно лучше). У короткого документа мало данных — ему нужно сильнее доверять фону; у длинного оценки надёжнее. В формуле Дирихле эффективный вес сглаживания μ/(|d|+μ) сам убывает с ростом |d|. Это автоматическая, зависящая от длины регуляризация — на практике Дирихле часто превосходит Йелинека–Мерсера, особенно на коротких запросах.

Пример расчёта query likelihood со сглаживанием

Коллекция: те же d1, d2, d3 из главы 1.2. Сначала модель коллекции (доли слов во всём корпусе). Всего токенов: d1=4, d2=3, d3=3, итого |C| = 10.

Подсчёт вхождений по корпусу: горный=3 (d1×2, d3×1), велосипед=3 (d1×2, d2×1), детский=1, цена=1, поход=1, палатка=1.

P(горный|M_C) = 3/10 = 0.3; P(велосипед|M_C) = 3/10 = 0.3.

Запрос q = «горный велосипед». Возьмём Йелинека–Мерсера с λ = 0.5.

Документ d1 («горный велосипед горный велосипед», |d1|=4):

горный: 0.5·(2/4) + 0.5·0.3 = 0.5·0.5 + 0.15 = 0.25 + 0.15 = 0.40.
велосипед: 0.5·(2/4) + 0.5·0.3 = 0.40.
P(q|d1) = 0.40·0.40 = 0.160; log10 ≈ −0.796.

Документ d2 («детский велосипед цена», |d2|=3):

горный (нет в d2, tf=0): 0.5·(0/3) + 0.5·0.3 = 0.15.
велосипед: 0.5·(1/3) + 0.5·0.3 = 0.1667 + 0.15 = 0.3167.
P(q|d2) = 0.15·0.3167 = 0.0475; log10 ≈ −1.323.

Документ d3 («горный поход палатка», |d3|=3):

горный: 0.5·(1/3) + 0.5·0.3 = 0.1667 + 0.15 = 0.3167.
велосипед (нет, tf=0): 0.5·0 + 0.15 = 0.15.
P(q|d3) = 0.3167·0.15 = 0.0475; log10 ≈ −1.323.

Ранжирование: d1 (0.160) > d2 ≈ d3 (0.0475).

Пример (что сделало сглаживание). Без сглаживания d2 и d3 получили бы P=0 (в каждом нет одного из слов запроса) и провалились бы вниз наравне с нерелевантными. Сглаживание дало им ненулевой, но малый скор за фоновую вероятность отсутствующего слова — справедливо ниже d1, но не «в минус бесконечность». Порядок совпал с косинусным (глава 1.2), но получен из вероятностного принципа.

Связь с TF-IDF и BM25

Если расписать логарифм сглаженного query likelihood, в нём естественно появляются две знакомые компоненты: множитель, растущий с tf (как TF), и множитель, штрафующий частотные по коллекции слова (как IDF). То есть вероятностный взгляд не противоречит TF-IDF, а объясняет, откуда берётся его форма. BM25 (Модуль 6) — это другая ветвь того же дерева (из Probability Ranking Principle), добавляющая явное насыщение TF и настраиваемую нормировку длины.

Частые заблуждения

Заблуждение. «Языковая модель документа понимает смысл текста.» Нет: unigram-модель — это просто распределение вероятностей отдельных слов (мешок слов с вероятностями). Никакой семантики, синтаксиса или порядка. Смысл появится только в нейромоделях (Модуль 10).

Заблуждение. «Сглаживание — мелкая техническая правка против деления на ноль.» Сглаживание — содержательная часть модели: оно одновременно лечит нули и выполняет роль, аналогичную IDF (за счёт фоновой вероятности частотные слова автоматически дают меньший дифференцирующий вклад). Выбор метода и параметра заметно влияет на качество.

Лаба / практика

Цель: реализовать ранжирование query likelihood со сглаживанием и сравнить методы.

Вход: мини-корпус из 5 документов, запрос из 2–3 слов (минимум одно слово должно отсутствовать в части документов).

Шаги:

Постройте модель коллекции P(t|M_C) (доли слов по всему корпусу).
Реализуйте Йелинека–Мерсера (λ=0.5) и Дирихле (μ=2000, либо подберите под малый корпус, например μ=2).
Посчитайте log P(q|d) для каждого документа обоими методами, отсортируйте.
Сравните ранжирования между собой и с TF-IDF из лабы 1.2.
Поэкспериментируйте с λ (0.1 и 0.9) и μ — как меняется порядок?

Ожидаемый результат: две отсортированные выдачи (JM и Дирихле), таблица скоров, разбор: где методы разошлись и почему (роль длины документа в Дирихле).

Время: ~50 мин. Критерий «сделано»: ни один документ не получил −∞; объяснено, как сглаживание заменяет нулевую вероятность, и показано влияние параметра.

Контрольные вопросы

Сформулируйте принцип вероятностного ранжирования. Что именно он предлагает упорядочивать?
Что означает «документ как языковая модель» в модели query likelihood?
Почему ранжируют по логарифму вероятности, а не по самой вероятности?
Что произойдёт без сглаживания, если одно слово запроса отсутствует в документе?
Чем сглаживание Дирихле отличается от Йелинека–Мерсера и почему оно зависит от длины документа?
Как сглаживание выполняет роль, похожую на IDF?
Почему unigram-языковая модель не «понимает» смысл текста, хотя называется «языковой»?

Глава 1.4. Базовые метрики качества: precision/recall, F1, MAP, MRR, nDCG, кривые PR (средний)

Цели обучения

После этой главы студент сможет:

определить precision и recall и объяснить их компромисс;
посчитать F1 и обосновать, когда нужна F-мера с другим весом;
отличить метрики множества (precision/recall/F1) от метрик ранжированного списка (MAP, MRR, nDCG);
вручную посчитать AP, MAP, MRR и nDCG@k на примере;
построить и прочитать PR-кривую; выбрать метрику под тип задачи.

Конспект

Мы построили модели ранжирования. Теперь главный инженерный вопрос: какая лучше? Без числа «качество» нельзя ни сравнить модели, ни заметить регресс, ни провести эксперимент (Модуль 19). Метрики опираются на оценки релевантности (relevance judgments): для запроса заранее известно, какие документы релевантны (бинарно: да/нет, или градуированно: 0–4).

Метрики на множестве: precision и recall

Для запроса система вернула множество результатов. Каждый документ — релевантный (R) или нет. Получаем матрицу ошибок:

Код: Выделить всё

               |  Вернули              |  Не вернули
---------------+-----------------------+---------------------
Релевантен     |  TP (true positive)   |  FN (false negative)
Не релевантен  |  FP (false positive)  |  TN (true negative)

Точность (precision) P = TP / (TP + FP) — какая доля выданного действительно релевантна. «Не сорим ли мы мусором?»
Полнота (recall) R = TP / (TP + FN) — какую долю всех релевантных мы нашли. «Не упустили ли нужное?»

Интуиция. Precision — про чистоту выдачи, recall — про охват. Выдать вообще все документы → recall=100%, но precision мизерная. Выдать один сверхнадёжный документ → precision=100%, но recall крошечный. Это и есть компромисс precision/recall.

Пример. В коллекции 10 релевантных документов по запросу. Система вернула 8 документов, из них релевантны 6. Тогда TP=6, FP=2, FN=4. P = 6/8 = 0.75; R = 6/10 = 0.60.

SEO-врезка. «Вернуть всё подряд» (высокий recall, низкая precision) пользователь воспринимает как мусорную выдачу и быстро уходит. ПС оптимизируют качество верхушки списка (см. nDCG@k ниже), поэтому в вебе важнее точность первых позиций, чем полнота. Это объясняет, почему «попасть в индекс» (recall) — необходимо, но недостаточно: решает позиция в топе.

F1 и F-мера

Часто нужно одно число. F1 — гармоническое среднее precision и recall:

F1 = 2·P·R / (P + R).

Интуиция (почему гармоническое, а не арифметическое). Гармоническое среднее тянется к меньшему из двух значений и сильно штрафует перекос. Если P=1.0, а R=0.0: арифметическое = 0.5 (вводит в заблуждение), гармоническое = 0. F1 высок только если обе метрики высоки.

Пример. Для случая выше P=0.75, R=0.60: F1 = 2·0.75·0.60/(0.75+0.60) = 0.9/1.35 ≈ 0.667.

Обобщение — Fβ, где β>1 весит recall сильнее (важно в поиске пропущенного, напр. медицина), β<1 — precision.

Внимание. Precision/recall/F1 — метрики множества: им безразличен порядок. Но поиск возвращает ранжированный список, где порядок — это всё. Для него нужны другие метрики.

Метрики ранжированного списка

Precision@k и Recall@k — precision/recall, посчитанные на первых k результатах. P@10 — сколько из первой десятки релевантны. Просто, но не различает порядок внутри топ-k.

Average Precision (AP) и MAP. Average Precision для одного запроса — среднее значений precision, взятых в позициях, где стоит релевантный документ:

AP = (1/R_total) · Σ_{k: doc_k релевантен} Precision@k,

где R_total — общее число релевантных. AP вознаграждает за то, что релевантные стоят выше. MAP (Mean Average Precision) — среднее AP по всем запросам.

Пример (расчёт AP). Выдача из 5 документов, релевантность: [Р, –, Р, –, Р] (релевантны позиции 1, 3, 5; всего релевантных R_total=3).
- Позиция 1 (Р): P@1 = 1/1 = 1.000.
- Позиция 3 (Р): P@3 = 2/3 ≈ 0.667.
- Позиция 5 (Р): P@5 = 3/5 = 0.600.
- AP = (1.000 + 0.667 + 0.600)/3 ≈ 0.756.
Если бы релевантные стояли выше ([Р, Р, Р, –, –]): AP = (1 + 1 + 1)/3 = 1.0. Видно, как AP награждает ранний показ релевантного.

Mean Reciprocal Rank (MRR). Для запросов, где важен один правильный ответ (навигация, вопрос-ответ). Reciprocal Rank = 1/rank_первого_релевантного. MRR — среднее по запросам.

Пример. Первый релевантный документ на позиции 1 → RR=1; на позиции 2 → RR=0.5; на позиции 4 → RR=0.25. Для трёх запросов с позициями (1, 3, 2): MRR = (1 + 0.333 + 0.5)/3 ≈ 0.611.

nDCG (normalized Discounted Cumulative Gain) — главная метрика для градуированной релевантности (не «да/нет», а оценка rel ∈ {0,1,2,3,4}) и порядка.

Gain — ценность документа, обычно 2^rel − 1 (для rel=0..4: 0,1,3,7,15 — экспоненциальный рост ценности высоких оценок).
Discount — скидка за позицию: документ на позиции i весит 1/log2(i+1) (чем ниже, тем меньше ценится).
DCG@k = Σ_{i=1..k} (2^{rel_i} − 1) / log2(i+1).
IDCG@k — DCG идеального порядка (документы отсортированы по убыванию rel).
nDCG@k = DCG@k / IDCG@k ∈ [0,1].

Пример (расчёт nDCG@4). Выдача с оценками по позициям: rel = [3, 2, 0, 1]. Логарифмы (log2): позиция 1 → log2(2)=1; 2 → log2(3)≈1.585; 3 → log2(4)=2; 4 → log2(5)≈2.322.
Gains 2^rel−1: [7, 3, 0, 1].
- DCG = 7/1 + 3/1.585 + 0/2 + 1/2.322 = 7 + 1.893 + 0 + 0.431 = 9.324.
Идеальный порядок по убыванию rel: [3, 2, 1, 0] → gains [7, 3, 1, 0]:
- IDCG = 7/1 + 3/1.585 + 1/2 + 0/2.322 = 7 + 1.893 + 0.5 + 0 = 9.393.
nDCG@4 = 9.324 / 9.393 ≈ 0.993. Выдача почти идеальна — единственная «ошибка» в том, что документ с rel=1 стоит ниже rel=0, что чуть снизило DCG.

Интуиция (зачем нормировка на IDCG). Сырой DCG несравним между запросами: у запроса с пятью высокорелевантными документами «потолок» DCG выше, чем у запроса с одним. Деление на идеальный DCG приводит всё к шкале [0,1], где 1 = идеальный порядок для данного запроса.

PR-кривая (precision–recall curve)

Если двигаться вниз по ранжированному списку и на каждом шаге пересчитывать (recall, precision), получится кривая. По мере роста recall (находим больше релевантных) precision обычно падает (захватываем мусор). PR-кривая показывает этот компромисс целиком; площадь под ней связана с Average Precision.

Код: Выделить всё

P │■■■
1 │    ■■
  │       ■■■
  │          ■■■■
  │              ■■■■■■■
  └───────────────────────→ R
  0                        1

Инженерная заметка. На практике метрики считают офлайн на «золотом наборе» (запросы + judgments) при каждом изменении ранжирующей модели — это офлайн-оценка (Модуль 19). nDCG@k (часто k=10) — рабочая лошадка веб-поиска, потому что учитывает и градации релевантности, и позиции, и нормирована между запросами. MAP популярна там, где релевантность бинарна, MRR — где нужен один ответ.

Какую метрику выбирать

Код: Выделить всё

Задача                                  |  Релевантность   |  Метрика
----------------------------------------+------------------+-------------
Один правильный ответ (навигация, QA)   |  бинарная        |  MRR
Найти все релевантные (право, патенты)  |  бинарная        |  Recall, MAP
Веб-выдача, важен топ                   |  градуированная  |  nDCG@k
Баланс точность/полнота, одно число     |  бинарная        |  F1 / Fβ
Анализ компромисса                      |  бинарная        |  PR-кривая

Частые заблуждения

Заблуждение. «Точность 95% — отличный поиск.» Без recall это пусто: можно вернуть один документ, угадать и отрапортовать precision=100%, упустив 99% релевантного. Метрики читают парами или берут агрегаты (F1, MAP, nDCG).

Заблуждение. «Precision@10 полностью описывает качество топа.» Она не различает порядок внутри десятки: [Р,–,–,…] и [–,…,Р] дают одинаковый P@10, хотя для пользователя это небо и земля. Поэтому нужны MAP/nDCG, чувствительные к позиции.

Заблуждение. «nDCG и MAP взаимозаменяемы.» MAP — для бинарной релевантности и не различает «релевантный» и «очень релевантный»; nDCG учитывает градации. На задачах с оценками 0–4 они могут расходиться.

Лаба / практика

Цель: реализовать и сверить метрики на размеченной выдаче.

Вход: для 3 запросов даны ранжированные списки по 10 документов и оценки релевантности (для одного запроса — градуированные 0–3, для остальных — бинарные).

Шаги:

Посчитайте P@5, R@5, F1 для каждого запроса.
Посчитайте AP для каждого и MAP по трём запросам.
Посчитайте MRR (позиция первого релевантного).
Для запроса с градуированными оценками посчитайте DCG@10, IDCG@10, nDCG@10.
Постройте PR-кривую для одного запроса (точки на каждом найденном релевантном).
Поменяйте местами документ с позиции 1 и 5 — как изменятся P@5, AP, nDCG? Какая метрика отреагировала, какая нет, почему?

Ожидаемый результат: таблица всех метрик, PR-кривая (можно ASCII/график), разбор шага 6.

Время: ~60 мин. Критерий «сделано»: все метрики посчитаны верно (сверка с эталоном), объяснено, почему P@5 нечувствительна к перестановке внутри топ-5, а AP/nDCG — чувствительны.

Контрольные вопросы

Дайте определения precision и recall через TP/FP/FN. В чём их компромисс?
Почему F1 — гармоническое, а не арифметическое среднее? Что будет с F1 при R=0?
Чем метрики множества (P/R/F1) принципиально отличаются от метрик ранжированного списка?
Как считается Average Precision и почему она награждает ранний показ релевантного?
Когда уместна MRR, а не MAP? Приведите тип запроса.
Зачем в nDCG нормировка на IDCG? Что станет с метрикой без неё при сравнении двух запросов?
Почему в DCG используют дисконт 1/log2(i+1), а gain часто берут как 2^rel−1?
Нарисуйте словами, как ведёт себя PR-кривая при движении вниз по выдаче и почему.

Итоги модуля

Текст → термины. Любая ПС сначала анализирует текст (токенизация → нормализация → стемминг/лемматизация → обработка стоп-слов); анализ документа и запроса обязан быть согласован, иначе совпадений не будет.
Мешок слов отбрасывает порядок и семантику, но даёт обратный индекс — основу быстрого поиска и всех классических моделей скоринга.
Булева модель даёт точную логику, но не ранжирует; для веба нужен числовой скор релевантности.
Векторная модель + TF-IDF + косинус дают ранжирование: TF (с насыщением через логарифм) × IDF (редкость слова), близость как косинус угла с нормировкой длины.
Вероятностный взгляд (Probability Ranking Principle, query likelihood) обосновывает скоринг принципиально; сглаживание (Йелинека–Мерсера, Дирихле) лечит нулевые вероятности и играет роль, схожую с IDF.
TF-IDF и языковые модели — две ветви одного дерева; обе ведут к BM25 (Модуль 6).
Качество измеряют метриками: precision/recall/F1 — на множестве; MAP, MRR, nDCG — на ранжированном списке; nDCG@k — стандарт веб-поиска (учитывает градации и позиции).
Любое улучшение ранжирования имеет смысл только относительно метрики на размеченном наборе — это мост к офлайн-оценке и экспериментам (Модуль 19).

Глоссарий модуля

Мешок слов (bag of words) — представление документа как мультимножества терминов без учёта порядка.
Термин (term) — нормализованная единица индекса, ключ обратного индекса.
Токенизация (tokenization) — разбиение текста на токены (кандидаты в термины).
Нормализация (normalization) — приведение токенов к каноническому виду (регистр, диакритика, юникод).
Стемминг (stemming) — грубое отсечение окончаний по правилам, без словаря.
Лемматизация (lemmatization) — приведение слова к словарной форме (лемме) с морфоанализом.
Стоп-слова (stop words) — высокочастотные малоинформативные слова.
Обратный индекс (inverted index) — отображение «термин → список документов (postings list)».
Булева модель (Boolean retrieval) — поиск по логическим выражениям AND/OR/NOT без ранжирования.
Векторная модель (Vector Space Model) — представление документов и запросов как векторов в пространстве терминов.
TF (term frequency) — частота термина в документе (часто логарифмически сглаженная).
IDF (inverse document frequency) — мера редкости термина по коллекции, log(N/df).
Косинусная близость (cosine similarity) — косинус угла между векторами; близость с нормировкой длины.
Probability Ranking Principle — принцип: ранжировать по убыванию вероятности релевантности оптимально.
Query likelihood — модель: ранжировать по вероятности породить запрос из языковой модели документа.
Сглаживание (smoothing) — присвоение ненулевой вероятности невиданным словам через модель коллекции (Йелинека–Мерсера, Дирихле).
Precision / Recall — точность (доля релевантного среди выданного) и полнота (доля найденного среди всего релевантного).
F1 / Fβ — гармоническое среднее precision и recall (с весом β).
MAP (Mean Average Precision) — среднее Average Precision по запросам.
MRR (Mean Reciprocal Rank) — среднее обратного ранга первого релевантного документа.
nDCG — нормированный дисконтированный накопленный выигрыш; метрика для градуированной релевантности и порядка.
PR-кривая — кривая компромисса precision–recall по ходу выдачи.
Relevance judgments — экспертные оценки релевантности (золотой набор) для расчёта метрик.

Связи с другими модулями

Опирается на: Модуль 0 (введение, картина конвейера, треки).
Питает дальше:
Модуль 4 (Индексирование) — обратный индекс, postings lists, анализ текста реализуются в ядре хранения.
Модуль 5 (Понимание запроса) — нормализация и анализ применяются к запросу симметрично документам.
Модуль 6 (Текстовая релевантность) — TF-IDF и query likelihood прямо ведут к BM25 и его параметрам k1, b.
Модуль 9–10 (Learning-to-Rank, Neural IR) — TF-IDF/BM25 становятся признаками; нейромодели снимают ограничения мешка слов (семантика, порядок).
Модуль 19 (Измерение качества и эксперименты) — метрики этого модуля используются в офлайн-оценке и A/B-тестах.

Материалы для углубления

Классические учебники по information retrieval (разделы про векторную модель, обратный индекс, оценку качества).
Обзорные работы по вероятностным моделям IR и языковым моделям в поиске (query likelihood, сравнение методов сглаживания).
Методические материалы по метрикам ранжирования (вывод nDCG, свойства MAP/MRR, связь PR-кривой и AP).
Практические руководства по морфологическому анализу для конкретного языка (стемминг vs лемматизация, обработка словоформ).
Открытые тестовые коллекции и наборы relevance judgments — для самостоятельной офлайн-оценки моделей.

skull18 · Сообщение **skull18** » 16 май 2026, 19:34

по boolean retrieval вопрос: пересечение постинг-листов же делают по отсортированным docid с галопирующим поиском, а не тупо линейно? в модуле это упомянуто или дойдем позже в разделе про сжатие индекса

sacpress · Сообщение **sacpress** » 19 май 2026, 08:05

у нас на внутреннем поиске долго жили на голом tf-idf и оно норм работало пока документы были примерно одной длины. как полезли длинные мануалы рядом с короткими faq - выдачу перекосило в пользу простыни. перешли на bm25 с подкрученным b под нормализацию длины и сразу полегчало, так что про насыщение tf это не теория а прям боль из жизни

regex3 · Сообщение **regex3** » 20 май 2026, 15:45

немного душню: precision и recall в вакууме мало о чем говорят, всегда смотрите на каком k мерите. precision@10 и precision по всей выдаче это совсем разные истории, и для веб-поиска первый намного честнее

Теоретический фундамент (Information Retrieval)

Теоретический фундамент (Information Retrieval)

Re: Теоретический фундамент (Information Retrieval)

Re: Теоретический фундамент (Information Retrieval)

Re: Теоретический фундамент (Information Retrieval)

Кто сейчас на конференции