검색 엔진에서 가장 중요한 것은 “얼마나 많은 문서를 수집하느냐”가 아니라 “가지고 있는 문서를 얼마나 잘 랭킹하느냐”라는 것을 구글이 증명했다. 즉, 질의를 입력한 사용자가 가장 원할 것 같은 문서를 상위에 배치하는 것이 중요하다. 그렇다면 검색 엔진은 보통 어떤 방법으로 랭킹을 하고 있을까?

컴퓨터로 랭킹 알고리즘을 구현할 때 먼저 생각해야 할 것은, 검색어와 문서를 컴퓨터 상에서 어떻게 표현할 것이냐는 문제다. 그 다음으로는 질의어와 문서의 연관도를 어떻게 계산할지 결정해야 한다. 쉬운 방법은 단순히 질의어에 속한 단어를 포함한 모든 문서를 찾는 것이지만 이것만으로는 정확도가 떨어진다. 그래서 보통 벡터 공간 모델(Vector Space Model, VSM)을 사용한다. 질의어와 문서를 키워드의 벡터로 표현하고, 내적값을 계산해서 유사함을 평가한다. (Cosine Similarity)

간결하게 아래처럼 표기할 것이다. 괜히 복잡해 보일 수도 있지만, 따지고 보면 누구나 생각할 수 있는 아이디어를 수학적으로 표현한 것에 불과하다. 찬찬히 읽어보면 쉽게 이해될 것이다.

• N: The number of documents
• f(d, t): Within document frequency
• r(d, t): Relative term frequency
• w(d, t): Document-term weight
• f(t): The number of documents that contains t
• w(t): Term weight

(Term에 대한 마땅한 번역어가 떠오르지 않아서 “단어”, “키워드” 등의 단어를 혼용했다.)

시작해보자. 어떤 문서가 특정 키워드를 많이 가지고 있다면, 그 문서와 해당 키워드 사이에는 밀접한 관계가 있다고 봐도 무방하다. 블로그 광고에 대한 글은 아무래도 “블로그”와 “광고”라는 단어를 많이 사용할 것 아닌가? 그것을 표현한 것이 f(d, t)로서, 문서 d에 단어 t가 몇 번 나오는지를 나타낸다. 간단하지만 그럴듯한 생각이다.

하지만… 가만 생각해보면 문제가 있다. 이 계산에 따르면, 키워드 등장 횟수가 늘어날수록 관련성도 비례해서 증가할 것이 아닌가? 예를 들어, 문서 A에는 “광고”가 8번, 문서 B에는 11번 등장한다고 해보자. A, B와 “광고” 사이의 관계는 거의 비슷하다고 봐도 될 것 같은데, 연관성을 평가하면 둘 사이에는 꽤나 큰 차이가 생기고 만다. 이럴 때 수학에서 흔히 사용하는 도구가 바로 로그 함수다.

r(d, t) = 1 + log(f(d, t))

이제는 f(d, t) 값이 증가하면 처음에는 차이가 좀 생기겠지만 어느 정도 지나고 나면 더 이상 차이가 벌어지지 않게 된다. (단, f(d, t)가 0이면, r(d, t)도 0이 된다.) 이렇게 약간 보완한 단어-문서 가중치를 Relative Term Frequency라고 한다.

한 가지 언급해둘 것은 r(d, t)를 계산하는 방법은 정하기 나름이라는 것이다. f(d, t)를 그대로 가져다 쓴다고 틀린 것도 아니고, 제3의 방식을 고안해낼 수도 있다. 중요한 것은, r(d, t)는 키워드 빈도를 기본으로 문서와 키워드 사이의 연관성을 수치화 한다는 것이다. 아무튼 이제 f(d, t)보다 세련된 방식을 갖게 되었다.

아직 개선의 여지가 보인다. 지금 이 글을 형태소 별로 분리했을 때 가장 많이 등장하는 것은 무엇일까?

• 키워드?
• 문서?
• 랭킹?

아니다. 직접 세어보지는 않았지만, 아마도 “이/가”, “을/를”, “이다” 같은 조사가 가장 많이 나올 것이다. 무슨 말인가? 단순한 등장 빈도만으로는 키워드와 문서의 관련성을 표현하기에 한계가 있다. 저런 조사는 어느 문서에나 빈번하게 등장할 것이고, 사실 상 문서와의 관련성은 제로에 가깝다. 그러면 어떻게 해야 할까?

키워드 자체에도 가중치를 부여하면 된다. 이를테면, “이다”와 “랭킹”이 각각 20번과 5번 나온다고 했을 때, “이다”에는 0.01, “랭킹”에는 0.3의 가중치를 부여하는 식이다. 이것을 키워드 가중치 w(t)라고 하며, r(d, t)와 w(t)를 함께 고려해야 제대로 된 문서-키워드 가중치 w(d, t)를 구할 수 있을 것이다.

그러면 w(t)는 어떻게 수치화 할 수 있을까? 일단 힌트는 많이 등장하는 단어일수록 w(t)가 작아야 한다는 것이다. 어떻게?

『Managing Gigabytes』 책 183쪽을 보면, George Zipf라는 사람이 1949년에 쓴 책 『Human Behavior and the Principle of Least Effort』라는 책을 인용하고 있다.

frequency of an item tends to be inversely proportional to its rank.

여기서 랭크(Rank)를 번역하면 지위나 신분이 될 텐데, 랭크는 등장 빈도에 반비례 한다는 뜻이다. 즉, w(t) = 1 / f(t)가 된다. 여기서 f(t)는 키워드 t의 등장 횟수가 아니고, t가 등장하는 문서의 개수이다. 문서 빈도의 역이기 때문에 이를 Inverse Document Frequency, IDF라고 부른다.

이제 w(t)도 구했다. 그런데.. 앞에서 f(d, t)를 그대로 쓰지 않고 r(d, t)를 만들어 쓴 것처럼, w(t)도 약간 변형할 필요가 있다. f(t1)은 1이고, f(t2)는 2라고 생각해보자. t1과 t2 사이에 얼마나 큰 차이가 있겠는가? 별로 없을 것이다. 하지만 단순히 1 / f(t)로 계산하면 w(t1)은 w(t2)의 두 배가 된다. 이런 문제를 해결하기 위해서 또 로그 함수를 동원한다.

w(t) = log(1 + N / f(t))

여기서 N은 전체 문서의 개수이다. 물론 이와 다른 w(t)를 고안하는 것도 얼마든지 가능하다.

자, 이제 정리해보자. 우리가 원하는 것은 1) 질의어와 문서를 수학적으로 표현하고, 2) 그들 사이의 유사함을 계산하는 방법이다. 일반적으로 쓰이는 벡터 공간 모델을 이용하기로 했으므로 질의어와 문서는 키워드의 벡터로 표현된다. 키워드-문서 가중치는, 키워드의 등장 빈도를 기본으로 하되, 일반적으로 많이 쓰이는 단어의 비중을 낮추기 위해서 Relative Term Frequency와 Term Weight의 곱으로 표현한다. 즉, w(d, t) = r(d, t) * w(t) 이것이 흔히 말하는 TF-IDF(Term Frequency - Inverse Document Frequency) 알고리즘이다. 위의 식에서 로그 함수를 사용했기 때문에 순수하게 TF와 IDF에 비례하지는 않지만, 기본적인 취지는 그대로 남아있음을 알 수 있다. 키워드-질의어 가중치 w(q, t)도 위와 비슷한 방식으로 구할 수 있을 것이다. 마지막으로 남은 것은 w(d, t)와 w(q, t) 사이의 유사도를 계산하는 방법인데, 서두에서 말한 것처럼 내적을 통한 Cosine Similarity가 일반적으로 쓰인다.

참고 자료

• Managing Gigabytes, 2nd edition, Witten, Moffat, Bell, Morgan Kaufmann, 1999