Алгоритм BM25

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

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

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

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

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

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

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

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

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

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