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

들어가며

우리가 하루도 거르지 않고 사용하는 IT 기술 중에는 어떤 것들이 있을까요? 메신저, SNS, 동영상 등도 떠오르지만 뭐니뭐니해도 검색을 빼놓을 수 없습니다. 조그마한 검색창을 통해서 우리는 웹 상의 방대한 문서들 중에 우리가 원하는 정보만 쏙쏙 골라서 얻을 수 있습니다. 그런데 이러한 검색이 어떻게 동작하는 걸까요?

 

큰 틀에서 검색 시스템을 구축하기 위해서는 다음과 같은 요소들과 대표적인 기술들은 아래와 같습니다.

 

(1) 문서를 오지게 모아서 저장한다.

(2) 원본 문서를 색인을 만들기 적합한 형태로 가공한다.

(3) 색인을 만든다.

(4) 사용자가 검색어를 입력하면, 검색어에 가장 알맞은 문서를 찾아서 보여준다.

 

문서의 수집이나 가공, 색인도 물론 흥미로운 주제들이지만, 이 포스팅에서 다뤄볼 주제는 (4), 랭킹입니다. 어떻게 검색 엔진들은 사용자가 검색어를 입력하면 신통방통하게 어떤 문서가 가장 적합한지를 판단할까요? 그리고 어떤 문서가 다른 문서보다 "더" 적합한지 판단하는 기준이 될까요?

 

대표적인 검색 엔진 오픈 소스(lucene)를 살펴보면 BM25라는 확률 기반의 점수 계산식을 기본으로 사용합니다. [1] 확률을 통해서 사용자의 검색어와 가장 유사한 문서를 찾아내는 과정을 따라가보면 굉장히 흥미롭습니다.

 

이 포스팅을 시작으로 확률이 검색에 적용되는 방식, binary independence model, 2-poisson-model, BM25까지 다뤄볼 예정입니다. 주된 자료는 검색 분야의 바이블 교과서로 유명한 [2]와 Stanford 276 강의 자료에서 가져왔습니다. 최대한 직관적으로 설명하면서도 수식을 하나하나 꼼꼼하게 살펴보겠습니다. 수식에 관심이 없으신 분들은 빠르게 스킵하셔도 됩니다. :)

사전 지식

검색 확률론을 이해하기 위해서 먼저 간단한 사전 지식이 필요합니다. 이들에 대해서 따로 상세하게 설명하지는 않겠습니다. 특히 베이즈 정리는 정말 중요하니, 잘 이해해야 합니다.

 

 

이 정도 수학 개념만 알아도 검색 엔진이 동작하는 핵심 원리를 이해하는데 무리가 없습니다. 그럼 본격적으로 시작해보겠습니다! 

 

Probability Ranking Principle

확률을 사용해서 검색이라는 문제를 풀기 위해서는 먼저 문제를 확률스럽게 정의해야겠죠? 먼저 세 가지 확률 변수를 정의합니다.

 

그리고 문서에 질의가 적합할 경우 R=1, 적합하지 않을 경우 R=0이 됩니다. 우리가 궁금한 것은 특정 검색어와 문서가 주어졌을 때, relevant 할 확률입니다. 이를 조건부 확률로 표기해보면 아래와 같습니다.

검색어 q가 주어졌을 때, 이 조건부 확률값이 높은 문서일 수록 관련성이 높습니다. 그러므로 이 값을 기준으로 정렬을 하여 검색 결과를 보여주는 것이 최선이라는 것을 멋있는 말로 Probability Ranking Principle이라 부릅니다. (좀 더 엄밀한 정의와 증명이 궁금하신 분들은 [1] ch 11.2를 참고하시기 바랍니다.)

마치며

이렇게 문제 정의까지하고 검색 랭킹 알고리즘 첫 포스팅을 마칩니다. 좀 짧은 감이 없지 않은데, 다음으로 다룰 BIM이 내용이 많아서 여기서 끊도록 하겠습니다.

 

감사합니다.

Reference

[1] BM25, the next generation of lucene relevance, opensourceconnections.com 

[1] Introduction to Information Retrieval, Manning et al

[2] Information Retreival and Web Search, Stanford CS 276