원제: Some simple effective approximations to the 2-Poisson model for probabilistic weighted retrieval

잡소리
간단하게만 보고 SPLADE까지 같이 정리하려고 했다. 어쩌다보니 생각보다 길어져서 그냥 분리시켰다.

BM25

무려 1994년 논문이시다. 하지만 DPR이 나온 아직까지도 병행해서 같이 쓰이곤 한다. 참고로 tf는 term-frequency, 한 문서 내에 특정 용어가 몇 번 등장했는가이다.

Introduction

1. Formal Model: 모델이 정확한 수식을 명시하는 방식.

• 검색 성능에 영향을 끼치는 매우 많은 변수들을 고려하기가 종종 어려움

2. Ad-hoc: 그럴듯해보이는 수식을 시도해본다.

• 특정 변수를 어떻게 다루는지에 대한 지침이 없음
• 수식을 추측해서 만들어보고 실험해야함

3. Regression: 독립 변수와 함수는 ad-hoc, 검색에서 가치를 평가하고 일부를 선택하여 가중치를 부여하는 Formal한 방식도 채용

Basic Probabilistic Weighting Model

(1)
$w(\underline x) = log{{P(\underline x|R)P(\underline 0|\overline R)}\over{P(\underline x|\overline R)P(\underline 0|R)}}$

이때 $\underline x$는 문서에 대한 정보를 담은 벡터, \underline 0는 가중치가 0이되는 기준벡터, $R$과 $\overline R$은 관련/비관련
즉, $\underline 0$는 질문 용어가 문서 내에 전혀 등장하지 않은 문서 벡터로, 해당 값보다 $\underline x$가 큰지/작은지로 성능을 평가한다.
$R$과 $\overline R$은 현재 질의를 기준으로 정답인가/아닌가를 구분한다.

간단하게 식을 요약해보자면 문서 x가 관련 문서(R)에 나타날 가능성이 비관련($\overline R$)에 나타날 가능성보다 얼마나 큰가를 설명한다. 이때 비교대상은 $\underline 0$이다.
(2)
$W = log{{p(1-q)}\over{q(1-p)}}$ = $log{{(r+0.5)/(R-r+0.5}\over{(n-r+0.5)/(N-n-R+r+0.5)}}$
여기서
p = P(term present | R)
q = P(term present | $\overline R$)
N은 index된 전체 문서 수, n은 해당 용어를 포함하는 문서 수, R은 알려진 관련 문서 수, r은 R에서 해당 용어를 포함하는 문서 수
(3)
만약 R과 $\overline R$과 같은 관련성 정보가 없다면 ICF에 근사한다.(이를 W(1)로 정의한다)
문서 내 용어 빈도만 다룬다면 $W = log({{p_{tf}}\over{q_{tf}}}\cdot{{q_0}\over{p_0}})$
$p_{tf}$ = P(term present with frequency tf | R)
$q_{tf}$ = P(term present with frequency tf | $\overline R)$
$p_0$, $q_0$는 용어가 전혀 나타나지 않을 확률

Eliteness

문서에서 특정 용어가 등장하는 현상이 무작위적이거나 확률적인 요소를 포함한다고 가정한다. 그리고 해당 확률은 그 문서가 실제로 그 개념에 관한 것인가/아닌가라는 구분을 반영한다. 이 중 이 문서가 그 개념에 관한 경우를 elite하다고 부른다.

용어 빈도는 eliteness에만 의존하지만, eliteness는 반드시 용어 빈도에 의존하지는 않는다. 기존의 term-independence assumption은 서로 다른 용어들에 대한 eliteness가 서로 독립적이라는 가정으로 대체한다.

2-푸아송 모델(2-Poisson Model)

자 일단 푸아송모델이 기억이 안날 수도 있다. 푸아송 모델은
$P(tf = k) = {{\lambda ^k e^{-k}}\over{k!}}$로 어떤 사건이 특정 구간(여기선 문서 전체)에 걸쳐 $\lambda$번 무작위로 발생한다는 확률 분포 모델이다.
일반 푸아송이 아닌 2-푸아송이 나온 이유는 elite문서와 non-elite문서를 구분하기 위함이다. 논문에 나오는 복잡한 식을 간략하게 줄여보면
$P(tf = k) = p(elite)Pois(\lambda)+P(non\_elite)Pois(\mu)$이다.
즉, tf가 크다는 것을 문서의 eliteness로 엮어낸 것이다.

변형

2-푸아송 모델 자체는 식이 너무 복잡하기에 그대로 사용하기엔 문제가 많다. 따라서 2-푸아송 모델의 성질은 유지하되 더 간단한 식으로 변형한다.

2-푸아송 모델의 성질은
1) tf = 0일때 값이 0이다
2) tf가 증가하면 모델 값도 단조증가한다.
3) 그러나 어떤 점근적 최대값에 수렴한다.
4) 3)의 점근적 최대값은 eliteness를 직접적으로 나타내는 지표에 부여되는 Robertson/Sparck Jones 가중치에 근사한다.

이를 만족시키면서 훨씬 단순화시킨 식은
${tf}\over{constant + tf}$로,

(constant == 1인 경우다) 이때 tf>=0 이기 때문에, 시작은 0이면서 1에 점근한다. 또한 constant가 큰 상수값이 되면 거의 선형에 가깝게 증가한다. (constant == 50인 경우)

여기에 점근적 최대값을 변경하기 위해 적절한 가중치를 곱해줄 필요가 있다. 이를 Robertson/Sparck Jones 가중치(위의 Basic Probabilistic Weighting Model의 (2)번 식)에서 통상적인 추정치 W(1)을 사용하면
$w = {{tf}\over{k_1+tf}}\cdot W(1)$ ($k_1$은 1~2범위의 값이 적절해 보인다고 한다.)
다만 이 식은 Fuhr나 Cooper의 방법에 사용하기 적합하지 않다.
또한 핵심적으로 원래의 2-푸아송 그래프와 달리 좌상단 볼록(convex)하다는 차이점도 존재한다.

문서 길이

문서 길이가 다른 이유에 대해서도 두가지 가설이나 존재한다. 첫번째 Scope hypothesis는 긴 문서는 짧은 문서들보다 더 다루는 내용이 많다는 가설이고, Verbosity hypothesis는 긴 문서와 짧은 문서 모두 다루는 범위는 유사하지만 단지 더 많은 단어를 사용한다는 가설이다. 해당 논문에서는 Verbosity hypothesis를 가정한다.
Verbosity hypothesis로 가정하면서 eliteness는 문서 길이와 독립적이지만, 특정 항에 대해 eliteness가 주어졌을 때 해당 항의 tf는 문서 길이에 의존한다.

이에 따라 문서가 길어질수록 tf는 커지지만, 단순히 "길어서 많이 나온 것"과 "내용상 중요해서 많이 나온 것"을 구분하려는 시도를 한다.

이제 식이 쭉 나오는데 핵심만 잡아보면
1) 가장 직관적인 모델(문서길이 d, $k_1$의 평균 길이 A) - term 기준
$w = {{tf}\over{k_1 \cdot {{d}\over{A}}+tf}} \cdot W(1)$
즉, tf는 문서 길이로 나눠야한다.
2) 문서 자체가 긴지 짧은지를 고려해야 한다 - 문서 전체 기준
$k_2 \cdot n_q \cdot {{A-d}\over{A+d}}$
즉 문서 길이는 평균 길이를 기준으로 평균보다 길면 패널티를 주고, 평균보다 짧으면 패널티가 덜해진다.

Query Term Frequency

이번엔 문서에서 tf가 아닌 유저가 한 질문에서 tf를 고려하는 방법이다.
문서는 위에서 말한 것 처럼 문서 길이에 따라서 나누고 패널티를 주고 복잡한 과정을 한다. 하지만 유저의 Query에 있는 tf는 어떤 노이즈도 아닌 '의도적'인 값에 가깝다. 그렇기에 그냥
$w = qtf \cdot W(1)$라는 아주 간단한 식이 완성된다.

결론

기존의 TF-IDF에서 TF가 클수록 중요한 단어라는 베이스를 바탕으로 진행한다. 여기에 BM25는 TF가 단순한 선형이 아닌 어느 순간부터 의미가 멈추도록(점근적 한계치) 설정하고, eliteness를 이용해 단순히 TF가 크다고 핵심이라고 끝낸 것에서 벗어나고, 문서의 길이를 노이즈로 구분해서 줄이는 방법을 채택했다.