BM25 알고리즘 요약

BM25란 무엇인가?

BM25는 "Best Matching 25"의 약자로, 문서와 검색 쿼리 간의 관련성을 점수로 나타내는 방법입다. 검색 엔진이 사용자에게 가장 적합한 정보를 제공하기 위해 이 알고리즘을 사용하죠. BM25는 여러 요소를 조합하여 문서의 점수를 계산합니다.

BM25의 주요 요소

1. 단어 빈도 (TF)

단어 빈도는 특정 문서에서 쿼리와 관련된 단어가 얼마나 자주 등장하는지를 나타냅니다. 예를 들어, "강아지"라는 단어가 문서에 많이 포함되어 있다면, 이 문서는 "강아지"에 대한 쿼리와 관련성이 높다고 판단합니다. 간단히 말해, 같은 단어가 많이 나오면 그만큼 중요하다고 보는 것이죠!

2. 역문서 빈도 (IDF)

역문서 빈도는 특정 단어가 전체 문서 집합에서 얼마나 드물게 등장하는지를 평가합니다. 예를 들어, "강아지"라는 단어가 많은 문서에 등장한다면, 그 단어는 상대적으로 덜 중요한 단어로 간주됩니다. 반대로, "멸종 위기" 같은 드문 단어는 더 높은 점수를 받습니다. 드물수록 더 귀한 정보라는 원리죠.

3. 문서 길이 조정

BM25는 문서의 길이에 따라 점수를 조정합니다. 긴 문서는 자연스럽게 더 많은 단어를 포함하기 때문에, 단순히 TF가 높다고 해서 높은 점수를 받지는 않습니다. 문서의 평균 길이에 따라 점수를 조정해 균형을 맞추는 것이죠. 이렇게 해서 짧은 문서와 긴 문서 간의 공정한 비교를 가능하게 합니다.

BM25 점수 계산

BM25는 다음과 같은 수식을 사용합니다:

\[ \text{BM25}(q, D) = \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|}{\text{avgdl}})} \]

여기서 각 변수는 다음을 의미합니다.

• \( q \): 사용자의 검색 쿼리
• \( D \): 문서
• \( q_i \): 검색 쿼리 내의 \(i\)번째 용어
• \( f(q_i, D) \): 문서 \(D\) 내의 용어 \(q_i\)의 빈도(TF)
• \( |D| \): 문서 \(D\)의 길이(단어 수)
• \( \text{avgdl} \): 컬렉션 내 문서들의 평균 길이
• \( k_1 \): 용어 빈도에 대한 가중치(일반적으로 1.2 ~ 2 사이의 값)
• \( b \): 문서 길이 정규화 매개변수(일반적으로 0.75로 설정)

IDF 값은 다음과 같이 계산됩니다:

\[ IDF(q_i) = \log \frac{N - n(q_i) + 0.5}{n(q_i) + 0.5} \]

여기서

• \( N \): 전체 문서의 수
• \( n(q_i) \): 용어 \( q_i \)를 포함하는 문서의 수

 

하이퍼파라미터란?

• k1​: 단어 빈도가 점수에 미치는 영향을 조절합니다. 높은 값일수록 단어 빈도의 중요성이 커집니다.
• b: 문서 길이에 대한 조정 비율로, 0과 1 사이의 값을 가집니다. 1에 가까울수록 문서 길이의 영향을 더 많이 반영합니다.

BM25의 장점

BM25는 다음과 같은 장점이 있습니다:

1. 효율적: 간단한 수식으로 빠르게 점수를 계산할 수 있습니다.
2. 효과적: 실제 검색 엔진에서 좋은 성능을 보입니다.
3. 유연성: 하이퍼파라미터를 조정하여 다양한 상황에 맞게 최적화할 수 있습니다.

마무리

Okapi BM25는 검색 엔진의 핵심 알고리즘 중 하나로, 문서의 관련성을 평가하는 데 매우 유용합니다. 단어 빈도, 역문서 빈도, 문서 길이 조정 등을 통해 사용자가 원하는 정보를 효과적으로 찾는 데 도움을 줍니다.

이제 BM25에 대한 이해가 조금 더 깊어졌기를 바랍니다! 앞으로 검색 엔진의 작동 원리를 이해하는 데 이 정보가 도움이 되길 바랄게요. 감사합니다!

 

참조

https://en.wikipedia.org/wiki/Okapi_BM25#Modifications

Okapi BM25 - Wikipedia