갈아먹는 검색엔진 [2] Binary Independence Model

지난 포스팅

갈아먹는 검색엔진 [1] 검색의 확률론(probabilistics information retrieval)

 

들어가며

이전 포스팅에서 검색 엔진의 랭킹이란 무엇인지, 그리고 이를 확률의 관점에서는 어떻게 접근할 수 있는지 알아보았습니다. 살짝 복습해보면 문서와 질의어가 주어졌을 때, 해당 문서가 질의어와 관련이 있을 확률은 다음과 같이 표기할 수 있었습니다.

그리고 위 확률이 높은 순서대로 정렬해서 결과를 리턴하는 것이 최선이다! 라는걸 PRP(Probability Ranking Principle)라고 불렀습니다. 이번 포스팅에서는 좀 더 구체적으로 이 PRP로부터 파생한 Binary Independence Model에 대해서 알아보겠습니다. 수학적인 유도 과정이 꽤 많은데, 그 과정이 꽤나 흥미로우니까 쉽게 포기하지 말고 따라와보세요! ㅎㅎ (수식 유도 과정은 [1]을 참고했습니다.)

Binary Independence Model의 두 가지 가정

BIM은 가장 기본적인 모델답게 문제를 최대한 단순화 시키기 위해서 여러 가정들을 집어 넣게 됩니다. 이름에서도 알 수 있듯이 Binary 가정과 Independence 가정을 추가합니다. 먼저 Information Retrieval 분야에서 문서를 어떻게 벡터로 표현하는 지 살펴보겠습니다.

x1과 x2라는 문서가 주어졌을 때, 이를 문서를 이루는 term들의 등장 빈도 수를 가지고 벡터로 표현할 수 있습니다. BIM에서는 여기에 binary 가정을 추가하여, 빈도 수가 아닌, 텀의 등장 여부를 나타내는 binary 값으로 문서를 벡터로 표현합니다.

그 다음으로 BIM은 텀들이 등장하는 것은 서로 간에 독립 사건임을 가정합니다. 예를들어 "아이즈원" 이라는 텀은 "아이돌"이라는 텀과 함께 등장할 확률이 높습니다. 그러나 BIM은 문제를 단순하게 만들기 위해서 이러한 상관관계는 무시하고 독립을 가정합니다. 

랭킹 수식 유도

자, 그러면 이 두 가정을 갖고 처음의 수식인 P(rel=1 | d, q)로 되돌아가보겠습니다. 우리가 궁금한 것은 저 수식의 정확한 값이 아니라, 문서들 간에 저 확률 값의 대소관계입니다. 따라서 위 수식에 odds를 취해주겠습니다. odds는 아래 그래프와 같이 우상향 형태를 띄므로 문서들 간의 대소관계에 영향을 주지 않습니다.

odds를 취해주면 아래와 같은 수식이 유도됩니다.

여기에 베이즈 정리를 적용해서 조건부 확률을 뒤집을 겁니다. 여기서 조건으로 걸려있는 확률 변수가 두 개이므로 수식이 조금 복잡합니다. 자세한 유도 과정이 궁금하신 분들은 다음 링크를 참고해주세요.[2]

가장 왼쪽 항에 삼항 베이즈 정리를 적용해 준 뒤, 분모가 동일하므로 제거해주어 수식을 정리하면 가장 오른쪽 항이 유도됩니다. 

빨간 박스 친 수식의 분자는 쿼리가 주어졌을 때, 임의의 문서를 뽑아서 그 문서와 쿼리가 관련있을 확률을 의미합니다. 분모의 경우는 관련이 없을 확률을 말합니다. 즉, 이 두 확률값은 어느 문서를 뽑던지 간에 동일한 값을 가지게 됩니다. 이는 문서들 간에 대소관계에 영향을 주지 못하므로 생략합니다. 빨간 박스를 생략한 오른쪽 수식은 아래와 같이 표기할 수 있습니다.

앞서서 BIM에서의 문서는 텀들의 등장 여부를 나타내는 binary 값들의 벡터로 표현되었습니다. 그리고 텀들 간의 independence를 가정했기 때문에, 쿼리가 주어졌고, 관련성이 있을 때, 뽑은 문서가 x일 확률 P(x|R=1, q)은 문서를 이루는 개별 텀들의 조건부 확률 값들의 곱과 동일합니다. 이 수식을 다시 문서에 등장한 텀과 등장하지 않는 텀으로 나누면 아래와 같습니다.

이제 표기를 간단하게 하기 위해서 아래와 같은 기호를 추가해보겠습니다.

해석해보면 pt는 쿼리가 주어졌고, 임의로 뽑은 문서가 쿼리와 관련이 있을 때, 특정 텀 xt가 등장할 확률입니다. 반대로 ut는 쿼리가 주어졌고, 임의로 뽑은 문서가 쿼리와 관련이 없을 때, 특정 텀 xt가 등장할 확률입니다.

Qt 개념 추가

문서와 마찬가지로 사용자의 질의어에 해당하는 쿼리 역시 벡터로 표현 가능합니다. 쿼리에 속하는 특정 텀들 qt라고 놓겠습니다. 이 qt를 활용하여 한 가지 가정을 추가합니다.

 

바로 쿼리에 등장하지 않은 텀들에 대해서는 pt와 ut가 동일하다는 것입니다. 즉, qt=0인 텀들은 관련이 있는 문서건, 관련이 없는 문서건 등장할 확률이 동일하다는 것입니다. (이는 텀들 간의 independence를 가정했기 때문에 가능합니다.) 그러면 쿼리에 속하지 않는 텀들은 대소관계에 영향을 주지 않으므로, 위 수식을 아래와 같이 표할 수 있습니다.

바로 qt=0인 경우는 생략하고, 문서와 쿼리에 모두 등장한 텀과 쿼리에는 등장하지 않았지만 문서에는 등장한 텀들로 나눠볼 수 있습니다. 여기에 약간의 트릭을 더해주면 아래 수식을 유도할 수 있습니다.

빨간 박스 친 수식을 보시겠습니다. 쿼리에 속하는 텀들에 대해서 (1-pt) / (1-ut) 값을 계산해 준 뒤, 모두 곱해줍니다. 1 - pt는 쿼리가 주어졌고, 임의의 문서를 뽑았을 때 특정 텀이 등장하지 않을 확률이었습니다. 때문에 어떤 문서를 뽑던 간에 빨간 박스 속 수식은 동일한 값을 갖습니다.

 

반면에 빨간 박스 왼쪽 수식의 경우, 쿼리와 문서에 모두 속하는 텀들에 대해서 pt와 ut를 계산하여 곱해줍니다. 쿼리와 문서에 모두! 속하는 텀들을 대상으로 계산하므로 이 값은 문서마다 달라지게 됩니다. BIM을 공부하면서 가장 이해하기 어려웠던 부분이었는데 쉽게 잘 전달이 되었을까 모르겠습니다ㅎㅎ

 

이제 생략해도 되는 부분을 모두 날려버리고, 문서 간의 랭킹을 결정하는 수식을 뽑아내면 아래와 같습니다.

문서의 랭킹을 결정하는 수식을 RSVd로 표기하였습니다. 이는 쿼리에도 속하고 문서에도 속하는 텀들의 ct 값들의 곱으로 계산할 수 있습니다. 이제 문서의 랭킹을 결정하기 위해서 알아야 할 값들이 추려졌습니다. 이제 쿼리와 문서가 주어지면, 공통으로 갖는 텀들에 대해 ct를 계산하면 해당 문서의 랭킹 점수를 얻을 수 있습니다.

 

헌데 ct의 값을 정확하게 얻어내는 것은 사실상 불가능합니다. pt와 ut의 정의에서 그 이유를 알 수 있습니다.

pt와 ut는 각각 쿼리가 주어졌고, 임의의 문서를 뽑았는데 관련이 있는 경우와 없는 경우를 조건으로 갖습니다. 그런데 우리는 문서가 쿼리와관련이 있는지 없는지 정확하게 알 수 없고, 다만 근사할 뿐입니다. 따라서 pt와 ut로 구성된 ct를 "근사" 할 수 밖에 없습니다.

 

Ct 근사하기

 

Reference

[1] Introduction to Information Retrieval

[2] 3 variables bayes rule, math.stackexchange.com/questions/1281454/bayes-rule-with-3-variables/1281558