Алгоритм Okapi BM25 – модификация формулы TF-IDF ранжирования документов

BM25 – функция расчета текстовой релевантности документов, разработанная британцами Стивеном Робертсоном и Карен Спарк Джоунс, опубликованная в 1994 году. Основана на эмпирических данных при попытке улучшить результаты работы критерия TF-IDF. Наилучшее соответствие между ожидаемым результатом и рассчитанным показал 25 алгоритм в списке, за что и получил свое название «Best matching», или BM25. Впервые был реализован в поисковой системе Okapi (Окапи), а в дальнейшем –  положен в основу текстовых анализаторов современных поисковых машин.

Что такое TF-IDF

TF-IDF – формула оценки значимости определенного слова в документе относительно всей выборки. Разработана Джорджом Солтоном в середине 70-х годов. Согласно TF-IDF, вес слова пропорционален количеству употреблений в текущем документе и обратно пропорционален частоте употребления слова в других документах выборки. Если слово используется в этом документе чаще, чем в других, то оно имеет большую значимость для него – именно такой критерий релевантности документа по запросу был у первых анализаторов поисковых систем.

Расшифровка TF-IDF

TF (term frequency) – это частотность слова, показывающая, насколько часто оно употребляется в документе. В длинном тексте вхождений термина может быть значительно больше, чем в коротком, хотя это вовсе не означает, что он точнее отвечает требованиям посетителей. Чтобы уравнять шансы длинных и коротких документов, используется отношение количества употребления слова к общему количеству слов в документе.

Где:

IDF (inverse document frequency) – обратная частота употребления слова в документе. Вводится в формулу для снижения веса часто употребляемых слов в выборке. После расчета TF мы получили только частотность, но слова сами по себе еще равнозначны. Часто употребляемые предлоги и союзы не могут быть сопоставимы по важности с другими словам, так как не несут смысловой нагрузки, поэтому, чтобы перераспределить вес значимости, вводится множитель IDF. Редкие слова получают более высокую значимость, а часто употребляемые – низкую.

Где:

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

Расчет TF-IDF

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

Вычислим IDF, предположив, что у нас всего 210420 документов в выборке и 10241 из них содержат термин «компьютер»:

Умножив TF на  IDF, получаем оценку важности термина «компьютер» для документа X: TF­IDF=0,004386·1,312745=0,005758. Рассмотрим другой пример. У нас есть 4 условных документа, имеющих следующее содержание:

Рассчитаем TF-IDF для данных документов по ключевым словам:

• Релевантность;
• Текстовая релевантность;
• Текстовая релевантность документа;
• Текстовая релевантность документа в поиске.

Посчитаем общее количество слов в документах, а также количество вхождений каждого слова из запроса в документ.

Рассчитаем множители TF и IDF для каждого слова:

В итоге получаем TF-IDF равным:

Вес запросов относительно документов рассчитаем как сумму TF-IDF каждого слова из запроса:

Запрос «Релевантность» наиболее значимый в 3 документе, что не удивительно, ведь в нем, больше всего вхождений. По аналогичной причине запрос «Текстовая релевантность» более значим в 1 документе. Дальше интереснее – первый текст вовсе не содержит слов «Документа», «Поиске», но при этом все равно выигрывает у других по оценке TF-IDF. Стоит отметить, что абсолютно все слова, по которым идет поиск, не содержит ни один документ. Больше всего, а именно 3 слова из 4, содержит третий документ. Добавим недостающее слово «Текстовая» в третий текст и посмотрим на результаты:

Ситуация ожидаемо изменилась в пользу документа 3, за ним идет документ 4, а первый – только на третьем месте. При этом в документы 4 и 1 никаких изменений не вносилось. Уберем предыдущее изменение и добавим слово «Релевантность» в  документ 4. IDF по этому запросу равен 0, т.к. запрос встречается во всех документах. За счет этого документ 4 выигрывает оценку TF-IDF по запросу «Текстовая релевантность документа в поиске».

Скачать Пример расчета TF-IDF При увеличении вхождений ключевого слова в документ пропорционально увеличивается значение TF. Таким образом, добавление вхождений ключевых слов на страницу значительно повышает ее релевантность. Функция BM25 должна была устранить этот недостаток.

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

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

D

по запросу

Q

, содержащего слова q_i=q₁,q₂…q_n по формуле BM25:

Где:

Для

IDF

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

Где:

Формула для

TF

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

Релевантность по запросу Q равна сумме релевантностей по всем словам q_i=q₁,q₂…q_n из запроса. На первый взгляд, принцип работы такой же, как и TF-IDF:

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

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

• TF при увлечении вхождений асимптотически стремится к определенному коэффициентами b,k₁ значению. В то время как в классической формуле 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 по запросу «Текстовая релевантность документа в поиске»:

Скачать Пример расчета BM25 Наглядный пример, того как 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 решили, что в Яндексе при расчете релевантности использовались похожие формулы:

Где:

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

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

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

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

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

Текстовые факторы ранжирования Яндекса (РОМИП-2006)

На РОМИП-2006 представители Яндекса несколько приоткрыли завесу тайны по используемым текстовым факторам ранжирования:

Где:

Вот несколько цитат:

При подсчете количества вхождений слова в документ мы проводим предварительную лемматизацию слов запроса и слов документа. Использование в качестве меры длины документа максимальной TF среди всех лемм документа ухудшает результат.

Помимо учета количества слов в документе можно учитывать html-форматирование и позицию слова в документе. Мы учитываем это в виде отдельного слагаемого. Учитывается наличие слова в первом предложении, во втором предложении, внутри выделяющих html тегов.

Пара учитывается, когда слова запроса встречаются в тексте подряд (+1), через слово (+0.5) или в обратном порядке (+0.5). Плюс еще специальный случай, когда слова, идущие в запросе через одно, в тексте встречаются подряд (+0.1).

На 2010 год, по словам Дена Расковалова, в Яндексе учитывалось  более 420 факторов ранжирования, а приведенные выше – это только малая часть из них.

Модифицированная формула BM25F

Все указанные достоинства и недостатки TF-IDF подобных формул были учтены при создании действующих алгоритмов ранжирования. В 2009 году Яндекс внедрил машинное обучение Матрикснет. Научился понимать морфологию запроса, учитывать наличие синонимов (тезаурусов) в документе, регулярно внедряет новые технологии для улучшения качества поиска. Сегодня релевантность определяется отдельно для зон документа, а за неестественное или чрезмерное количество ключей благополучно накладываются текстовые пост-фильтры. Границы текстовой переоптимизации могут довольно часто сдвигаться, причем независимо для каждой зоны документа. Сегодня документ попал в «зеленую зону» и вы в ТОПе, завтра границы сдвинулись и вы вылетели. BM25 field (BM25F) – функция расчета релевантности по зонам документа:

1. Title;
2. Текст:
   • Вес слов угасает от начала документа;
   • Учитываются точные вхождения, словоформы, части слова из запроса и их всевозможные комбинации;
   • Наличие слов из запроса в одном пассаже.
3. Html-форматирование текста (заголовки H, strong, ul и т.п.)
4. Текст анкоров исходящих ссылок с документа;
5. Текст анкоров входящих ссылок на документ;
6. Вхождения слов из запроса в URL.

Для оценки влияния ссылочных факторов существуют отдельные функции: LF-IDF, LinkBM25. Современная SEO-оптимизация – это непрерывные эксперименты с количеством вхождений, словоформой, положением ключевых слов в документе и т.п. Знание и понимание таких основ текстового ранжирования, как TF-IDF, BM25 существенно облегчают жизнь оптимизатора, внося долю ясности в непознанный мир Платонов Щукиных.