Перейти до основного вмісту
Алгоритм BM25

BM25 - один з алгоритмів, який використовується пошуковими системами для ранжування відповідності документів щодо їх релевантності даному пошуковому запиту користувачів. Алгоритм заснований на імовірнісно-пошуковому механізмі, розроблений ще в 1970-х і 1980-х роках Стівен Е. Робертсономі Карен Спарк Джонсом.

Формула алгоритму BM25 - це пошукова функція в комплексі документів на підставі запиту слів, що входять до кожного з цих документів, незалежно від взаємовідносин між термінами запиту в межах документа (наприклад, їх відносна близькість). Це не одна функція, а сімейство функцій, з різними компонентами та параметрами. Алгоритм BM25F враховує не лише сам текст, але його окремі ділянки чи зони. До таких ділянок відносять тег Title, метатеги, заголовки та підзаголовки, текстовий текст.

Одна з найпоширеніших формул цієї функції виглядає так:

Нехай даний запит Q містить слова  q1...qn, тоді функція BM25 дає наступну оцінку релевантності документа D запиту Q:

формула BM25

Де f(qi, D) є частота слова qiу документі D, |D | є довжина документа (кількість слів у ньому), а avgdl — середня довжина документа в колекції. k1 та b — вільні коефіцієнти, зазвичай їх вибирають як k1 = 2.0 та b = 0.75.

IDF(qi) є зворотною документною частотою слова qi. Є кілька тлумачень IDF і невеликі варіації його формули. Класично вона визначається як:

классическая формула IDF

де N є загальна кількість документів у колекції, а n(qi ) — кількість документів, що містять qi. Але найчастіше застосовуються «згладжені» варіанти цієї формули, наприклад:

сглаженная формула IDF

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

Іншими словами, слова, що часто зустрічаються, зіпсують остаточну оцінку документа. Це небажано, тому в багатьох додатках вищенаведена формула може бути скоригована такими способами:

  • Ігнорувати взагалі всі негативні складові в сумі (що еквівалентно занесенню до стоп-листу та ігнорування всіх відповідних високочастотних слів);
  • Накладати на IDF деяку нижню межу \varepsilon: якщо IDF менше \varepsilon, то вважати її рівною \varepsilon.
  • Використовувати іншу формулу IDF, яка не має негативних значень.