4.1. 확률 검색 모델
“확률 검색 모델”(Probabilistic Retrieval Model)은 사용자 질의에 대한
“적합확률”(Probability of Relevance)의 역 순으로 문서를 나열하여 검색 결과를 도출하는 모델입니다.
질의 \(Q\)가 주어졌을 때, 문서 \(D\)가 검색되었다면,
문서 \(D\)가 검색된 상황에서 \(D\)가 적합문서일 확률을 \(P( R | D )\) 라고 표현합니다.
또한, \(D\)가 적합문서가 아닌 경우일 확률을 \(P( N\!R | D )\) 라고 표현합니다.
어떤 문서가 \(P( R | D ) > P( N\!R | D )\) 이면,
문서 \(D\)는 적합문서일 확률이 아닐 확률 보다 높아서 이 때, 문서 \(D\)를 적합문서로 판단합니다.
만약, \(P( R | D )\) 를 직접 구할 수 있는 경우에는 값을 구하면 되지만,
만약, \(P( R | D )\) 를 직접 구할 수 없는 경우에는 “베이즈” 공식을 적용하여 값을 구할 수도 있습니다.
( 베이즈 공식은 수학 파트에 확률 통계 부분에 자세하게 정의되어 있습니다. )
즉, \(P( R | D ) = \frac{ P( R )P( D | R ) }{ P( D ) }\) 가 됩니다.
\(P( P | D ) > P( N\!R | D )\) 이면, \(\frac{ P( R )P( D | R )}{P( D )} > \frac{P( N\!R )P( D | N\!R )}{P( D )}\) 이고,
=> \(P( R )P( D | R ) > P( N\!R )P( D | N\!R )\) => \(\frac{P( D | R )}{P(D | N\!R)} > \frac{P( N\!R )}{P( R )}\)
이는, 우항 : \(\frac{P( N\!R )}{P( R )}\) 이 문서\(D\)에 독립적으로 질의 \(Q\)에 따라 값의 영향을 받기 때문에,
결국, 문서 \(D\)의 적합문서 여부는 이 좌항 : \(\frac{P( D | R )}{P( D | N\!R )}\) 값이 결정하게 됩니다.
해당 값은 가능도 비율 (Likelihood Ratio)값으로 해당 문서\(D\)의 적합성으로 자주 사용됩니다.
이산 확률 분포에서와 연속 확률 분포에서의 확률 정의는 다릅니다.
이산 확률 분포는 정의역 케이스에 대한 치역이 확률 값이 되는 반면에,
연속 확률 분포는 정의역 범위에서의 치역의 면적, 즉 정적분 값을 확률로 정의하기 때문에,
이산 확률 분포는 모든 치역의 합이 1(확률의 특징)이 되고, 연속 확률 분포는 전체 면적(정적분)값이 1이 되기 때문에,
연속 확률 분포의 모든 치역의 합은 일반적으로 확률보다 작게 됩니다. 이 치역을 파라미터 \(P\) 로 표현하고,
가능도는 결국 연속 확률 분포에서 정의역 값들을 가지고 치역 \(P(파라미터)\)를 구하는 개념일 것입니다.
이를 구체적으로 “파라미터 추정”(Parameter Estimation)이라고 표현합니다.
다음은 대표적인 3 가지 파라미터 추정법을 나열 한 것입니다.
1). Maximum Likelihood Estimation (MLE) : 일어난 사건에 대한 조건부확률 \(p\)를 구하는 방법을 사용합니다.
\(p\)는 파라미터이고, \(c_i\)를 각 사건이라고 정의 할 때, \(P(p | c_1, c_2, \ldots, c_k)\)\( = \frac{P(p)P(c_1, c_2, \ldots, c_k | p)}{P(c_1, c_2, \ldots, c_k)}\) 이고,
이때, \(P(c_1, c_2, \ldots, c_k | p)\) 가 가능도라고 볼 수 있고,
이 값만을 적용하여 \(P(p | c_1, c_2, \ldots, c_k) \approx P(c_1, c_2, \ldots, c_k | p)\) 로 값을 사용하는 방법입니다.
최대 가능도는 연속 확률 분포에서 극대(최대) 값이므로 미분을 진행하여 0인 점을 찾아내는 방법을 사용합니다.
즉, \(\hat{p} = \arg \max_{p} L\) ( 최대 지점 )이므로,
미분이 0인 값 \(\frac{dlog(L)}{dp} = 0\) \(: ( L(c_1, c_2, \ldots, c_k | p) = P(c_1, c_2, \ldots, c_k | p) = \Pi_{i=1}^{k} P( c_i | p ) )\) 가 됩니다.
2). Bayesian Estimation : 베이즈 식을 적용한 방법으로,
MLE 에서 \(P(c_1, c_2, \ldots, c_k | p)\)만을 사용한 1)과 다르게 \(P(p)\)을 같이 사용한 \(P(p)P(c_1, c_2, \ldots, c_k | p)\)를 사용합니다.
여기서 세 확률 식에 대해 자세하게 설명을 할 필요가 있어 추가 했습니다.
i). “사후 분포”( Posterior )는 식에서 \(P(p | c_1, c_2, \ldots, c_k)\) 로 일련의 사건으로 확률을 구하는 식입니다.
ii). “가능도”( Likelihood ) 는 식에서 \(P(c_1, c_2, \ldots, c_k | p)\) 로 확률로 일련의 사건의 가능도를 구하는 식입니다.
iii). “사전 분포”( Prior ) 는 식에서 \(P(p)\) 로 일련의 사건과 독립적으로, 기존에 알고 있는 확률을 구하는 식입니다.
MLE방식은 ii) 만을 사용하여 i)를 구하는 방식이지만, Bayesian Estimation 방식은 ii) + iii) 을 사용하여 값을 구합니다.
즉, Bayesian Estimation 은 \(Posterior = \frac{ Prior \times Likelihood }{ Normalizing }\) 라고 볼 수 있습니다.
이는, 가능도의 경우 이미 알고 있는 식을 적용하면 문제 없겠지만, 사전 분포를 구하는 것이 문제 일 것 입니다.
( 보통의 사전 분포는 “균일분포”(Uniform), “표준 정규 분포”(Normal) 등이 될 수 있습니다. )
3). Maximum A Posteriori estimation (MAP estimation) : Bayesian Estimation의 특별한 케이스로,
Prior는 “베타 분포”( Beta Distribution )를 사용합니다. 이유는 크게 두 가지로 꼽습니다.
i). “켤레 사전 분포”(Conjugate Prior) : 사전 분포와 사후 분포가 같은 분포 계열( 같은 식의 형태 )을
가지는 것을 의미하는데,
베타 분포는 켤레 사전 분포를 가능케 해주기 때문에, 결과적으로 계산의 용이하게 해주어 이를 사용됩니다.
ii). 적합성과 자유도 : 0과 1사이에 존재하는 연속 확률 분포로 파라미터 추정에 적합한 함수로 평가 받으며,
두 개의 모수\((\alpha, \beta)\) 로 결과 값이 자유자재로 변하기 때문에 다양한 상황에 대해 가정 할 수 있습니다.
그렇다면, \(\hat{p} \)\(= \arg \max_{p}log( P(p)P(c_1, c_2, \ldots, c_k | p) )\)\( = \arg \max_{p}( log( P(p) ) + log( P(c_1, c_2, \ldots, c_k | p) ) )\) 이므로,
미분이 0인 값 \(\frac{d( log( P(p) ) + log( P(c_1, c_2, \ldots, c_k | p) ) )}{dp} = 0\)\( :
( P(p) = \frac{1}{B(\alpha, \beta)}p^{\alpha-1}(1-p)^{\beta-1} , \)\(B(\alpha, \beta)\)는 상수 \()\) 가 됩니다.
4.2. 이진 독립 모델
그렇다면, \(\frac{P( D | R )}{P(D | N\!R)}\) 을 계산해 봅시다.
먼저, 용어 집합의 각 원소를 독립으로 보고 존재 여부를 기준으로 이진 값을 사용합니다.
이 모델을 “이진 독립 모델”(Binary Independence Model)이라고 표현합니다.
그래서, \(\frac{P( D | R )}{P( D | N\!R )}\)\( = \frac{P( b_1, \ldots, b_n | R )}{P( b_1, \ldots, b_n | N\!R )}\)\( : (b_i = 0 | 1)\)\(= \frac{P( b_1 | R )}{P( b_1 | NR )}\frac{P( b_2 | R )}{P( b_2 | NR )}\cdots\frac{P( b_n | R )}{P( b_n | N\!R )}\) 이고,
줄여서, \((\prod_{t \in E} \frac{P( t | R )}{P( t | NR)}) \times (\prod_{t \in N\!E} \frac{1 – P( t | R )}{1 – P( t | N\!R )})\)
\( : (\)집합 \(E\)는 \(b_i\) 가 \(1\)인 즉, 값이 존재하는 원소들의 집합이고,\(N\!E\)는 \(b_i\) 가 \(0\)인 즉, 존재하지 않는 원소들의 집합입니다.\()\)
더 줄여서, \(P(t_i | R)\)를 \(p_i\)로 두고, \(P(t_i | N\!R)\)를 \(s_i\)로 둔다면,\((\prod_{t_i \in E} \frac{p_i}{s_i} \times \prod_{t_i \in N\!E} \frac{1 – p_i}{1 – s_i})\) 로도 표현 가능합니다.
추가로, \(\frac{P(D | R)}{R(D | N\!R)}\)\( = \prod_{t_i \in E} \frac{p_i(1-s_i)}{s_i(1-p_i)} \times \prod_{t_i \in E \cup N\!E} \frac{1-p_i}{1-s_i}\) 로도 나타낼 수 있습니다.
(\(E\)집합 쪽의 연산을 전개하면 다음가 같은 결과를 도출할 수 있습니다.)
이 때, 위의 식에서 \(\prod_{t_i \in E \cup N\!E} \frac{1-p_i}{1-s_i}\) 는 문서에 대해 값은 상수 값을 가지게 되므로
\(\prod_{t_i \in E} \frac{p_i(1-s_i)}{s_i(1-p_i)}\) 가 실질적으로 값을 결정짓게 됩니다.
위의 값을 \(log\)를 씌워서 \(\log {\prod_{t_i \in E} \frac{p_i(1-s_i)}{s_i(1-p_i)}}\) 를 사용하기도 하는데,
왜냐하면, \(\prod_{t_i \in E} \frac{p_i(1-s_i)}{s_i(1-p_i)}\) 는 확률 값이기에 \(log\)를 씌워도 상대적 확률은 바뀌거나
판정이 역전되지 않기 때문에, 단순 치환으로 허용한다는 의미로 사용 가능 하고,
또한, \(\log {\prod_{t_i \in E} \frac{p_i(1-s_i)}{s_i(1-p_i)}}\)\( = \sum_{t_i \in E} \log {\frac{p_1(1-s_i)}{s_i(1-p_i)}}\) 로 표현 가능 하기 때문에 사용됩니다.
( 위 식의 \(\sum_{t_i \in E} \log {\frac{p_1(1-s_i)}{s_i(1-p_i)}}\) 를 “RSV”(Retrieval Status Value))로 표현합니다. )
RSV를 계산하는 방법 중에서 \(p_i = \frac{1}{2} , s_i = \frac{n_i}{N}\)\( :
(\)\(N\)은 문서 전체 용어 개수, \(df_i\)는 \(i\)번 째 용어 출현 빈도수 \()\)
로 두고 값을 수정하면, \(\sum_{t_i \in E} \log{\frac{p_1(1-s_i)}{s_i(1-p_i)}}\) 은 \(\sum_{t_i \in E} \log{\frac{N}{df_i}}\) 값과 근사 하게 됩니다.
( 이는 \(idf\)와 비례함을 알 수 있는 부분입니다. )
만약,
\(n_i\) 를 \(i\)번째 용어가 출현한 문서의 수( 즉, \(df_i\) ) ,
\(r_i\) 를 \(i\)번째 용어가 출현한 적합 문서의 수 ,
\(N\) 을 전체 문서의 수 ,
\(R\) 을 현재 질의에 대한 적합 문서의 수 ,
\(d_i\) 를 \(i\)번째 용어가 검색되었는지 여부( 1이면 검색 됨, 0이면 검색 안 됨 )라고 한다면,
| Relevant | Non-Relevant | Total | |
| \(d_i = 1\) | \(r_i + 0.5\) | \(n_i – r_i + 0.5\) | \(n_i + 1\) |
| \(d_i = 0\) | \(R – r_i + 0.5\) | \(N – n_i – R + r_i + 0.5\) | \(N – n_i + 1\) |
| Total | \(R + 1\) | \(N – R + 1\) | \(N + 2\) |
위의 테이블에서 \(\frac{P( D | R )}{P( D | N\!R )}\) 은 \(\Sigma_{i \in E} \log{\frac{\frac{r_i + 0.5}{R – r_i + 0.5}}{\frac{n_i – r + 0.5}{N – R – n_i + r_i + 0.5}}}\) 와 근사 할 것입니다.
( \(E := d_i = 1\) 이고 \(q_i = 1\) 인 집합 즉, 질의한 용어가 출현 까지 한 용어들의 집합 )
여기서 만약, \(r_i = R = 0\) 인 경우 (적합/부적합 문서집합에서의 출현 정보가 없는 경우) 에는
\(\frac{P( D | R )}{P( D | N\!R )}\) 은 \(\Sigma_{i \in E}\log{\frac{N – n_i}{n_i}}\) 와 근사 할 것입니다. ( \(E := d_i = 1\) 이고 \(q_i = 1\) 인 집합 )
4.3. BM25
이진 독립 모델의 경우 같은 값은 아니지만, \(log-idf\) 값과 비례한 수치를 사용한다는 결론이 나왔었습니다.
그러나 \(idf\)만을 사용한다는 것은 성능 기대를 하기가 힘들다 봐야 되고, 실제로 좋은 편이 아니였습니다.
여기서 \(tf\)요소를 추가한 새로운 모델이 나왔고 그 모델이 “BM25″(Best Match 25) 입니다.
BM25의 정의는 다음과 같습니다.
먼저,
\(tf_i\) 는 용어 \(i\)의 문서 내 \(tf\) 를 의미합니다.
\(qf_i\) 는 용어 \(i\)의 질의 내 \(tf\) 를 의미합니다.
\(k_1\) 은 상수 값으로 \(tf_i\)의 상대적 중요도를 나타냅니다. 클수록 \(tf_i\)가 선형(linear)의 가중치를 가집니다.
\(k_2\) 는 상수 값으로 \(qf_i\)의 상대적 중요도를 나타냅니다. 클수록 \(qf_i\)가 선형(linear)의 가중치를 가집니다.
\(dl\) 은 문서 길이( Document Length ) 이고, \(avdl\) 은 평균 문서 길이( AVerage Document Length ) 입니다.
\(BM25 = \Sigma_{i \in Q}log \frac{\frac{r_i + 0.5}{R – r_i + 0.5}}{\frac{n_i – r + 0.5}{N – R – n_i + r_i + 0.5}}\)\( \times \frac{(k_1 + 1)tf_i}{k_1((1-b) + b \times \frac{dl}{avdl}) + tf_1}\)\( \times \frac{(k_2 + 1)qf_i}{k_2 + qf_i}\)
위의 식을 그냥 보면 굉장히 난해한 공식 같지만,
처음부터 따라온 분들은 익숙한 식들의 곱으로 이루어졌다는 것을 눈치 채셨을 것입니다.
BM25 는 TF-normalization 과 Length-normalization 되어 있다는 것을 알 수 있습니다.
식 중에서 \(\frac{(k_1 + 1)tf_i}{k_1((1-b) + b \times \frac{dl}{avdl}) + tf_1}\) 은 예전에 피봇 기반 길이 정규화에서 본 식과 유사합니다.
( 이는 길이 정규화를 피봇기반으로 했다고 볼 수 있습니다. )
또한, 두 식 \(\frac{(k_1 + 1)tf_i}{k_1((1-b) + b \times \frac{dl}{avdl}) + tf_1}\) 과 \(\frac{(k_2 + 1)qf_i}{k_2 + qf_i}\) 의 공통점인 조화 평균 형태의 식에 초점을 본다면,
값이 클수록 \(tf\)값(선형)에 근사해지는 특징은 \(tf\)를 비례로 적용한다는 점과
가중치에 따라 \(rawTF\) (즉, linear) 이거나 \(logTF\) (즉, sub-linear) 를 선택하여
normalization 한다는 것을 알 수 있습니다.
( 일반적으로 \(k_1\)은 \(1.2 :\) sub-linear 값을, \(k_2\)는 \(100 :\) nearly-linear 값을 사용합니다. )