Okapi BM25

tf–idf와 유사하지만 좀 더 개선된 함수. BM은 “Best Matching”의 줄임말. tf–idf와 유사한 형태이지만 두 가지 요소(문서 내 단어 빈도 증가에 따른 점수의 포화 정도를 제어, 문서 길이가 점수에 주는 영향을 제어)를 더 고려한다.

$$Score(D,Q) = \sum_{i=1}^{n} IDF(q_i) \cdot \frac{f(q_i, D) \cdot (k_1 + 1)}{f(q_i, D) + k_1 \cdot (1 - b + b \cdot \frac{|D|}{avgdl})}$$

• $Q$는 질의에 담긴 단어들(Multiset)
• $D$는 점수를 구하고자 하는 문서
• $avgdl$은 전체 문서들의 평균 길이
• $f(q_i, D)$는 문서 $D$에 단어 $q_i$가 나오는 빈도
• $k_1$은 상수. 보통은 1.2 또는 2.0 (term freq. saturation 상수)
• $b$는 상수. 보통은 0.75 (document length normalization 상수)

$IDF$는 다음과 같다:

$$IDF(q_i) = ln(\frac{N - n(q_i) + 0.5}{n(q_i) + 0.5} + 1)$$

• $N$은 전체 문서의 수
• $n(q_i)$는 단어 $q_i$를 담고 있는 문서의 수

IDF component

• $ln$ 안의 $+1$ 항은 $ln$이 음수가 되지 않도록 하기 위함.
• 분자, 분모의 $+0.5$는 Lidstone smoothing.

Term frequency component

• $k_1$은 단어 빈도 증가에 따른 점수의 포화 정도(term frequency saturation)를 제어한다. 1.2이면 빠르게 포화되고 2.0이면 천천히 포화된다.
• $b$는 문서 길이가 점수에 주는 영향도를 조절(document length normalization)한다. 문서가 전체 문서의 평균보다 길면 점수가 감소하고 문서가 평균보다 짧으면 점수가 증가하는데, $b$를 통해 그 영향도를 조절할 수 있다.

See also

• Contextual retrieval