BM25 —семейство функций ранжирования документов, Тошнота документа по Минычу

Сразу хочу сказать, что здесь никакой воды про bm15 , и только нужная информация. Для того чтобы лучше понимать что такое bm15 , bm11 , bm25 , bm25f, алгоритм ранжирования, функция ранжирования, тошнота документа по минычу , настоятельно рекомендую прочитать все из категории Обработка естественного языка.

Okapi bm25 — функция ранжирования , используемая поисковыми системами для упорядочивания документов по их релевантности данному поисковому запросу. Она основывается на вероятностной модели, разработанной в 1970-х и 1980-х годах Стивеном Робертсоном, Карен Спарк Джонс и другими.

Сама функция носит название BM25 (BM от англ. best match), но ее часто называют «Okapi BM25» по названию поисковой системы Okapi, созданной в Лондонском городском университете в 1980-х и 1990-х годах, в которой эта функция была впервые применена.

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

Функция (алгоритм) ранжирования

BM25 — поисковая функция на неупорядоченном множестве термов («мешке слов») и множестве документов, которые она оценивает на основе встречаемости слов запроса в каждом документе, без учета взаимоотношений между ними (например, близости). Это не одна функция, а семейство функций с различными компонентами и параметрами. Одна из распространенных форм этой функции описана ниже.

Пусть дан запрос , содержащий слова , тогда функция BM25 дает следующую оценку релевантности документа запросу :

где есть частота слова (англ. term frequency, TF) в документе , есть длина документа (количество слов в нем), а — средняя длина документа в коллекции. и — свободные коэффициенты, обычно их выбирают как и .

есть обратная документная частота (англ. inverse document frequency, IDF) слова . Есть несколько толкований IDF и небольших вариации его формулы. Классически, она определяется как:

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

Заметим, что вышеуказанная формула IDF имеет следующий недостаток. Для слов, входящих в более чем половину документов из коллекции, значение IDF отрицательно. Таким образом, при наличии любых двух почти идентичных документов, в одном из которых есть слово, а в другом — нет, второй может получить бо́льшую оценку.

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

• Игнорировать вообще все отрицательные слагаемые в сумме (что эквивалентно занесению в стоп-лист и игнорированию всех соответствующих высокочастотных слов);
• Налагать на IDF некоторую нижнюю границу : если IDF меньше , то считать ее равной .
• Использовать другую формулу IDF, не принимающую отрицательных значений.

Интерпретация IDF в теории информации

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

Теперь положим, что имеется два поисковых слова и . Об этом говорит сайт https://intellect.icu . Если они входят в документ независимо друг от друга, то вероятность обнаружить их в случайно выбранном документе такова:

и содержание этого события

Это примерно то, что выражается компонентой IDF в BM25.

Модификации

• При экстремальных значениях коэффициента в функции BM25 получаются функции ранжирования, известные под названиями bm11 (при ) и bm15 (при ).
• BM25F — модификация BM25, в которой документ рассматривается как совокупность нескольких полей (таких как, например, заголовки, основной текст, ссылочный текст), длины которых независимо нормализуются, и каждому из которых может быть назначена своя степень значимости в итоговой функции ранжирования.

Недостатки TF-IDF и BM-25

Используемая модель «bag-of-words» (мешок слов) не учитывает:

• • взаимное расположение слов (ключи в одном предложении или разбросаны по тексту);
  • позицию слова относительно начала документа (ключ в первом предложении);
  • словоформу (совпадение формы слова).
  • положение ключа в документе (зона документа).

Поэтому одна лишь формула BM25 в чистом виде для оценки релевантности документа не использовалась.

Расшифровка BM25

Робертсон хоть и утверждает, что для получения формулы использовалась вероятностная модель, но некоторые специалисты считают ее «подгонкой» под нужный результат. В функцию БМ25 внедрены свободные коэффициенты, которые могут принимать различные значения. Они подбираются так, чтобы «подогнать» результат работы поиска под заранее имеющиеся данные. Документы сначала оценивают асессоры, которые и говорят что плохо, а что хорошо. Затем на основании этих данных выбирают упомянутые коэффициенты, чтобы расположить документы так же, как это сделали асессоры – так называемый «принцип обезьянки». Оценка релевантности документа D по запросу Q , содержащего слова qi=q1,q2…qn по формуле BM25:

Где:

Для IDF используется сглаженная формула:

Где:

Формула для

TF

также изменилась:

Релевантность по запросу Q равна сумме релевантностей по всем словам qi=q1,q2…qn из запроса. На первый взгляд, принцип работы такой же, как и TF-IDF:

• при отсутствии слова из запроса в документе f(qi,D)=0 слагаемое в формуле score(D,Qi) также будет равно 0;
• чем больше слов и запроса встречается в документе, а также чем больше их частота употребления, тем больше будет итоговая оценка score.

Но есть и отличия:

• TF при увлечении вхождений асимптотически стремится к определенному коэффициентами b,k1 значению. В то время как в классической формуле TF стремится к бесконечности.

Процентный рост BM25 от числа вхождений

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

а) отрицательные значения в сумме вообще игнорируются;

б) накладывается нижняя граница, при достижении которой значение IDF считается фиксированным числом;

• Короткие документы гораздо быстрее достигают насыщения по оценке TF. После достижения определенного порога дальнейшее увеличение частоты термина в документе не приводит к росту TF Score. Длинные же документы, наоборот, достигают насыщения гораздо позже.

• Значение Score зависит от длины документа D. Чем больше слов в документе, тем меньше будет итоговая оценка для документа.

Зависимость Score от объема текста (TF уменьшается).

• Если взять в расчет только относительную релевантность, т.е. релевантность нескольких документов по одному запросу, то множитель IDF сократится. При расчете Score двух текстов с одинаковым 2% вхождением однословного ключа (TF фиксированный) текст на 2300 символов получит Score = 7,45 (≈-6%), а текст на 20 000 символов – Score = 7,86% (≈+6%). Если взять двухсловный запрос, Score для длинного текста уже составит +12%. Именно поэтому создание текстовых «портянок» долгое время было нормой для SEO-специалистов.

Немногие помнят «золотую эру SEO», когда вебмастера спамили ключевыми словами, достигали более высокой релевантности за счет их количества и, добавив ко всему этому тысячу сапо-ссылок, за пару недель выходили в ТОП.

Расчет BM-25

Возьмем те же тексты и рассчитаем количество документов, содержащих слова из запроса, и среднюю длину документа.

Далее найдем IDF для каждого слова из запроса

В итоге получаем следующее значение TF и оценку Score по запросу «Текстовая релевантность документа в поиске»:

Наглядный пример, того как IDF может принимать отрицательные значения для слов, которые встречаются больше чем в половине документов. Вместо отрицательного значения IDF брали фиксированное IDF=0,01. Наибольшую оценку получил «документ 3», хотя в классической TF-IDF формуле – документ 1, который теперь имеет самую низкую оценку Score по BM25. Распределение оценок по различным запросам:

До этого мы рассматривали ограниченную выборку, в которой заранее известно, что документы околотематические. Для лучшего понимания формулы рассмотрим пример с нетематической коллекцией документов. Найдем Score в выборке из 20 000 документов.

IDF для слова «документа» значительно больше, чем для слов «релевантность» и «текстовая». Теперь увеличим частоту слова «документа» в док2 с 2% до 5%.

Видим значительный рост TF и Score при неизменном IDF. Увеличим частоту «текстовая» до 6% в док 1.

Сумма частот каждого слова из запроса в документе 1 и документе 2 одинаковая и составляет 13%, но термин «документа» меньше употребляется в коллекции. Из итоговой оценки и можно говорить, что значимость узкоспециализированных слов значительно выше, чем других терминов из запроса.

тошнота документа по минычу

В 2006-2007 годах по методике пользователя под ником Миныч на форуме Searchengines решили, что в Яндексе при расчете релевантности использовались похожие формулы:

Где:

Видим, что по данной формуле максимальная релевантность достигается, когда продвигаемый запрос ti является самым частотным в документе n(ti,d)=nmax, а плотность ключевого слова вообще не влияет на оценку. Миныч – первый, кто ввел понятие «Тошнота». В его методике тошнота W=max(√7,√nmax) – квадратный корень от частоты самого употребляемого слова nmax в документе. Если nmax меньше 7, то W=√7. При превышении некоторого порога спамности для конкретного слова, например W>25, накладывалась пессимизация документа.

Вау!! 😲 Ты еще не читал? Это зря!

• Ссылочное ранжирование‎
• Алгоритм HITS алгоритм hits , алгоритм ранжирования ,
• Обучение ранжированию
• TF-IDF
• Ранжирование (поиск информации)
• Модель дивергенции от случайности
• Okapi BM25
• Алгоритм поиска
• PageRank
• Ранжирование Яндекса ( РОМИП -2006 )
• ранжирования документов ,
• Поиск изображений на основе содержимого
• Поиск мультимедийной информации
• Поиск изображений
• Потеря триплета

Статью про bm15 я написал специально для тебя. Если ты хотел бы внести свой вклад в развитие теории и практики, ты можешь написать коммент или статью отправив на мою почту в разделе контакты. Этим ты поможешь другим читателям, ведь ты хочешь это сделать? Надеюсь, что теперь ты понял что такое bm15 , bm11 , bm25 , bm25f, алгоритм ранжирования, функция ранжирования, тошнота документа по минычу и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Обработка естественного языка