BM25 – функция расчета текстовой релевантности документов, разработанная британцами Стивеном Робертсоном и Карен Спарк Джоунс, опубликованная в 1994 году. Основана на эмпирических данных при попытке улучшить результаты работы критерия TF-IDF. Наилучшее соответствие между ожидаемым результатом и рассчитанным показал 25 алгоритм в списке, за что и получил свое название «Best matching», или BM25. Впервые был реализован в поисковой системе Okapi (Окапи), а в дальнейшем – положен в основу текстовых анализаторов современных поисковых машин.
- Что такое TF-IDF
- Расшифровка TF-IDF
- Расчет TF-IDF
- Расшифровка BM25
- Процентный рост BM25 от числа вхождений
- Зависимость Score от объема текста (TF уменьшается).
- Расчет BM-25
- Тошнота документа по Минычу
- Недостатки TF-IDF и BM-25
- Текстовые факторы ранжирования Яндекса (РОМИП-2006)
- Вот несколько цитат:
- Модифицированная формула BM25F
Что такое 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 | ||
Количество слов в документе | 456 | 0,004386 |
Количество вхождений термина в документ | 2 | |
IDF | ||
Всего документов в выборке | 210420 | 1,312745 |
Количество документов c вхождением термина | 10241 | |
TF-IDF | 0,005758 |
Умножив TF на IDF, получаем оценку важности термина «компьютер» для документа X: TFIDF=0,004386·1,312745=0,005758. Рассмотрим другой пример. У нас есть 4 условных документа, имеющих следующее содержание:
1 | Текстовая релевантность – это соответствие текста страницы или целого сайта конкретному поисковому запросу. Чем выше текстовая релевантность, тем больше у вашей странички шансов попасть на первую строку выдачи поисковиков при равенстве прочих факторов. |
2 | Текстовая релевантность в поиске – это мера соответствия совокупности внутритекстовых факторов страницы запросу, поставленному пользователем. К внутритекстовым факторам относятся: заголовки, текстовое содержание, форматирование текста, атрибуты тегов. |
3 | Релевантность в общем смысле – это соответствие документа ожиданиям пользователя. Таким образом, релевантность в поиске – это степень удовлетворения пользователя показанными в ответ на его запрос поисковыми результатами. Высчитывается с помощью алгоритмов поисковых систем. |
4 | Соответствие документа запросам пользователей, а также соблюдение правил поисковых систем позволяют данному сайту занимать более высокие позиции в поиске. |
Рассчитаем TF-IDF для данных документов по ключевым словам:
- Релевантность;
- Текстовая релевантность;
- Текстовая релевантность документа;
- Текстовая релевантность документа в поиске.
Посчитаем общее количество слов в документах, а также количество вхождений каждого слова из запроса в документ.
№ документа | Всего слов | Текстовая | Релевантность | Документа | Поиске |
---|---|---|---|---|---|
1 | 25 | 2 | 2 | 0 | 0 |
2 | 22 | 1 | 1 | 0 | 1 |
3 | 26 | 0 | 3 | 1 | 1 |
4 | 17 | 0 | 0 | 1 | 1 |
Итого: | 2 | 3 | 2 | 3 |
Рассчитаем множители TF и IDF для каждого слова:
Cлова | TF | IDF | |||
---|---|---|---|---|---|
1 док | 2 док | 3 док | 4 док | ||
Текстовая | 0,080 | 0,045 | 0,000 | 0,000 | 0,301 |
Релевантность | 0,080 | 0,045 | 0,115 | 0,000 | 0,125 |
Документа | 0,000 | 0,000 | 0,038 | 0,059 | 0,301 |
Поиске | 0,000 | 0,045 | 0,308 | 0,059 | 0,125 |
В итоге получаем TF-IDF равным:
Cлова | TF-IDF | |||
---|---|---|---|---|
1 док | 2 док | 3 док | 4 док | |
Текстовая | 0,024 | 0,014 | 0,000 | 0,000 |
Релевантность | 0,010 | 0,006 | 0,014 | 0,000 |
Документа | 0,000 | 0,000 | 0,012 | 0,018 |
Поиске | 0,000 | 0,006 | 0,005 | 0,007 |
Вес запросов относительно документов рассчитаем как сумму TF-IDF каждого слова из запроса:
Запросы | Σ(TF·IDF) | |||
---|---|---|---|---|
1 док | 2 док | 3 док | 4 док | |
Релевантность | 0,010 | 0,006 | 0,014 | 0,000 |
Текстовая релевантность | 0,034 | 0,020 | 0,014 | 0,000 |
Текстовая релевантность документа | 0,034 | 0,020 | 0,026 | 0,018 |
Текстовая релевантность документа в поиске | 0,034 | 0,026 | 0,031 | 0,025 |
Запрос «Релевантность» наиболее значимый в 3 документе, что не удивительно, ведь в нем, больше всего вхождений. По аналогичной причине запрос «Текстовая релевантность» более значим в 1 документе. Дальше интереснее – первый текст вовсе не содержит слов «Документа», «Поиске», но при этом все равно выигрывает у других по оценке TF-IDF. Стоит отметить, что абсолютно все слова, по которым идет поиск, не содержит ни один документ. Больше всего, а именно 3 слова из 4, содержит третий документ. Добавим недостающее слово «Текстовая» в третий текст и посмотрим на результаты:
Запросы | Σ(TF·IDF) | |||
---|---|---|---|---|
1 док | 2 док | 3 док | 4 док | |
Релевантность | 0,010 | 0,006 | 0,014 | 0,000 |
Текстовая релевантность | 0,020 | 0,011 | 0,010 | 0,000 |
Текстовая релевантность документа | 0,020 | 0,011 | 0,031 | 0,018 |
Текстовая релевантность документа в поиске | 0,020 | 0,017 | 0,036 | 0,025 |
Ситуация ожидаемо изменилась в пользу документа 3, за ним идет документ 4, а первый – только на третьем месте. При этом в документы 4 и 1 никаких изменений не вносилось. Уберем предыдущее изменение и добавим слово «Релевантность» в документ 4. IDF по этому запросу равен 0, т.к. запрос встречается во всех документах. За счет этого документ 4 выигрывает оценку TF-IDF по запросу «Текстовая релевантность документа в поиске».
Запросы | Σ(TF·IDF) | |||
---|---|---|---|---|
1 док | 2 док | 3 док | 4 док | |
Релевантность | 0,000 | 0,000 | 0,000 | 0,000 |
Текстовая релевантность | 0,024 | 0,014 | 0,000 | 0,000 |
Текстовая релевантность документа | 0,024 | 0,014 | 0,012 | 0,018 |
Текстовая релевантность документа в поиске | 0,024 | 0,019 | 0,016 | 0,025 |
Скачать Пример расчета TF-IDF При увеличении вхождений ключевого слова в документ пропорционально увеличивается значение TF. Таким образом, добавление вхождений ключевых слов на страницу значительно повышает ее релевантность. Функция 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 от числа вхождений
Число вхождений | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
Рост Score в процентах | — | 50% | 20% | 11,1% | 7,1% | 5,0% | 3,7% | 2,9% | 2,3% | 1,9% |
- IDF принимает отрицательные значения для слов, входящих более чем в половину документов. Часто встречающиеся слова сильно портят итоговую оценку документа. При наличии двух почти одинаковых документов, отличающихся только одним часто употребляемым словом, приоритет получит документ, не содержащий его. Данный факт далек от того, чтобы дать адекватную оценку качества документа, поэтому используется один из двух из вариантов: а) отрицательные значения в сумме вообще игнорируются; б) накладывается нижняя граница, при достижении которой значение IDF считается фиксированным числом;
- Короткие документы гораздо быстрее достигают насыщения по оценке TF. После достижения определенного порога дальнейшее увеличение частоты термина в документе не приводит к росту TF Score. Длинные же документы, наоборот, достигают насыщения гораздо позже.
- Значение Score зависит от длины документа D. Чем больше слов в документе, тем меньше будет итоговая оценка для документа.
Зависимость Score от объема текста (TF уменьшается).
Объем текста (слов) | 50 | 150 | 250 | 350 | 450 | 550 | 650 | 750 | 850 |
---|---|---|---|---|---|---|---|---|---|
Падение Score в процентах | — | -4,60% | -4,40% | -4,20% | -4,10% | -3,90% | -3,80% | -3,60% | -3,50% |
- Если взять в расчет только относительную релевантность, т.е. релевантность нескольких документов по одному запросу, то множитель IDF сократится. При расчете Score двух текстов с одинаковым 2% вхождением однословного ключа (TF фиксированный) текст на 2300 символов получит Score = 7,45 (≈-6%), а текст на 20 000 символов – Score = 7,86% (≈+6%). Если взять двухсловный запрос, Score для длинного текста уже составит +12%. Именно поэтому создание текстовых «портянок» долгое время было нормой для SEO-специалистов.
Немногие помнят «золотую эру SEO», когда вебмастера спамили ключевыми словами, достигали более высокой релевантности за счет их количества и, добавив ко всему этому тысячу сапо-ссылок, за пару недель выходили в ТОП.
Расчет BM-25
Возьмем те же тексты и рассчитаем количество документов, содержащих слова из запроса, и среднюю длину документа.
Текстовая | Релевантность | Документа | Поиске | ||
---|---|---|---|---|---|
Количество документов содержащих слово | 2 | 3 | 2 | 3 | |
Док.1 | Док.2 | Док.3 | Док.4 | Средняя | |
Длина документа | 25 | 22 | 26 | 17 | 22,5 |
Далее найдем IDF для каждого слова из запроса
Слова из запроса | |||||
Текстовая | Релевантность | Документа | Поиске | ||
Док.1 | Частота слова | 0,080 | 0,080 | 0,000 | 0,000 |
Док.2 | 0,045 | 0,045 | 0,000 | 0,045 | |
Док.3 | 0,000 | 0,115 | 0,038 | 0,038 | |
Док.4 | 0,000 | 0,000 | 0,059 | 0,059 | |
IDF | 0 | -0,368 | 0 | -0,368 |
В итоге получаем следующее значение TF и оценку Score по запросу «Текстовая релевантность документа в поиске»:
Текстовая | Релевантность | Документа | Поиске | ||||
---|---|---|---|---|---|---|---|
Док.1 | TF | 0,107 | 0,107 | 0,000 | 0,000 | Score | 0,00107 |
Док.2 | TF | 0,068 | 0,068 | 0,000 | 0,068 | Score | 0,00136 |
Док.3 | TF | 0,000 | 0,147 | 0,051 | 0,051 | Score | 0,00198 |
Док.4 | TF | 0,000 | 0,000 | 0,104 | 0,104 | Score | 0,00104 |
Скачать
BM25 | Запросы | |||
---|---|---|---|---|
№ документа | Релевантность | Текстовая релевантность | Текстовая релевантность документа | Текстовая релевантность документа в поиске |
Док.1 | ||||
Док.2 | ||||
Док.3 | ||||
Док.4 |
BM25 | Запросы | |||
---|---|---|---|---|
№ документа | Релевантность | Текстовая релевантность | Текстовая релевантность документа | Текстовая релевантность документа в поиске |
Док.1 | ||||
Док.2 | ||||
Док.3 | ||||
Док.4 |
До этого мы рассматривали ограниченную выборку, в которой заранее известно, что документы околотематические. Для лучшего понимания формулы рассмотрим пример с нетематической коллекцией документов. Найдем 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, накладывалась пессимизация документа.
Недостатки 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) – функция расчета релевантности по зонам документа:
- Title;
- Текст:
- Вес слов угасает от начала документа;
- Учитываются точные вхождения, словоформы, части слова из запроса и их всевозможные комбинации;
- Наличие слов из запроса в одном пассаже.
- Html-форматирование текста (заголовки H, strong, ul и т.п.)
- Текст анкоров исходящих ссылок с документа;
- Текст анкоров входящих ссылок на документ;
- Вхождения слов из запроса в URL.
Для оценки влияния ссылочных факторов существуют отдельные функции: LF-IDF, LinkBM25. Современная SEO-оптимизация – это непрерывные эксперименты с количеством вхождений, словоформой, положением ключевых слов в документе и т.п. Знание и понимание таких основ текстового ранжирования, как TF-IDF, BM25 существенно облегчают жизнь оптимизатора, внося долю ясности в непознанный мир Платонов Щукиных.