tgoop.com/reverse13/718
Last Update:
В information retrieval => search engines есть такое понятие как релевантность документа aka document rank (score).
Допустим у вас есть набор текстовых документов, вы ищите документы удовлетворяющие булевому запросу слов (одно слово будем называть term, ещё иногда используют token).
Например, foo or bar => вернет все документы, которые содержат слова foo или bar.
Результат запроса может быть большим. Поэтому мы хотим определить некий порядок на найденных документах, причем вероятно так, чтобы порядок зависел от запроса, найденного документа, и всего множества документов.
Такой порядок устанавливается на практике с помощью функции, которая возвращает вещественное число, а принимает большое число параметров, называют ranking (score) function.
Есть довольно много разных ranking model, но переменные везде примерно одинаковые:
1) document term frequency, tf – обычно имеется в виду сколько раз конкретный терм запроса встречается в конкретном документе.
2) document length, dl, |D|, norm – сколько всего термов в конкретном документе
3) average document length, думаю итак ясно.
4) inverse document frequency, IDF, это составной компонент, который вычисляется для вашего запроса и всего множества документов, а не конкретного документа, он может иметь разную форму (*), например, log(N / n_t).
4.1) N – количество документов всего
4.2) n_t – в скольких документах содержится такой терм
Важное замечание, дальнейшие рассуждения исходят из того, что запрос это ровно 1 терм, в случае же если термов несколько, то обычно скор документа, это сумма скоров для каждого найденного терма запроса. Впрочем это необязательно, например, умножение или максимум тоже могут подходить, просто полученные свойства будут в большинстве случаев хуже.
Одна из самых простых и при этом популярных функций это tf-IDF – tf * IDF, тут важно упомянуть что как и с IDF, под tf здесь может подразумевается некоторая модификация и log(1 + tf), и sqrt(tf) / sqrt(dl) (это в lucene) и тд.BM25 (https://en.wikipedia.org/wiki/Okapi_BM25) другая известная и пожалуй самая популярная функция на сегодняшний день. Как правило ее параметризуют двумя константами k1 и b.
Собственно к чему я это все, в какой-то момент мне стало любопытно “А почему k1? Есть другие k2, k3, …?”
Собственно погуглив, я обнаружил странное, для k2 и k3 находится один и тот же дополнительный коэффициент вида BM25(k1, b) * (tf_q + k3 * tf_q) / (tf_q + k3)tf_q – как много раз терм встречается в запросе.
По сути мы пытаемся увеличить значение скора, если мы нашли документ по терму который запросили несколько раз.
Оказалось, что такая добавка мало что дает в плане качества, поэтому не используется на практике. К тому же в lucene-like системах обычно есть альтернативный вариант сказать, что какая-то часть подзапроса более/менее важна чем другие (boosting).
Но как же быть с тем, что и k2 и k3 называют в разных пейперах одно и тоже?
В итоге благодаря этому https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/okapi_trec3.pdf я похоже нашел разгадку.
Изначально в ходе экспериментов k3 действительно был таким (он кстати встречается чаще чем k2), а вот k2 другим. При этом k2 оказался еще более бесполезным чем k3. В итоге k3 стал более известен, но k1, k3 выглядит весьма странно, поэтому кто-то поменял k3 на k2, ну а дальше кто-то это скопировал :)
Не знаю зачем я это написал, но по-моему прикольная история.
(*) Версия IDF в BM25 лучше исключает влияние на score часто встречающихся термов, а в lucene модифицировали эту версию, чтобы избежать отрицательных значений результата функции (это полезно для алгоритма, который используется для оптимизации top k запросов, wand)
BY Loser story
Share with your friend now:
tgoop.com/reverse13/718