Random Walks on the Click Graph – SIGIR 2007

by seunglee

검색 사용자들의 클릭 정보를 활용해서 검색 품질을 높일 수 있다는 건 이미 널리 알려진 사실입니다. 쉽게 생각해도 사람들이 많이 클릭한 문서일수록 좋은 문서일 것 같잖아요. 하지만, 막상 적용하려고 하면 그리 간단하지만은 않습니다. 일단 악의적으로 특정 문서를 많이 클릭해서 많이 노출시키려는 사람들이 있지요. 이런 걸 스팸 또는 어뷰징(abusing)이라고 합니다. 또 악의는 없더라도 제목에 낚여서 사람들이 많이 클릭한 문서가 있다면 역시 적절히 걸러줘야 할 겁니다.

두 번째는 사람들의 관심과 클릭이 검색 결과 상단에 집중되기 때문에 나타나는 문제인데, 대부분의 문서에는 클릭이 아예 발생하지 않습니다. 아무리 좋은 문서라도요. 상위에 노출되기 때문에 많이 클릭되고, 또 많이 클릭되기 때문에 계속 상위에 노출되는 악순환이 생기는 거지요.

클릭 데이터를 쓰면 좋아지는 건 확실한데, 이런 부작용이 있다? 사람들이 이를 가만히 놓아둘 리 없죠. 수많은 연구자가 이를 해결할 수 있는, 아니 개선할 수 있는 저마다의 아이디어를 제안했습니다. 이번에 소개하는 Random Walks on the Click Graph도 그 중 하나입니다. 웹페이지의 하이퍼링크를 이용해서 좋은 문서를 골라내는 구글의 페이지랭크처럼, 검색 클릭 패턴으로부터 좋은 문서를 찾아내자는 것입니다.

클릭 그래프(Click Graph)라고 해서, 사용자가 입력한 쿼리(query)와 문서를 그래프의 점(vertex, node)으로, 클릭수를 edge로 나타냅니다. 쿼리-문서 쌍이 많이 클릭될수록 edge는 강해집니다. 아래 그림을 보면 사용자가 어떤 쿼리를 입력하고, 결과 중에 어떤 문서를 클릭했는지 나와 있습니다.(논문에서는 이 검색모델을 이미지 검색에 적용했기 때문에 이 글에서는 문서와 이미지라는 말을 같은 의미로 봐도 무방합니다.)

Click Graph

이 그래프 상에서 특정 노드(즉, 쿼리)에서 출발해서 edge를 따라 임의로 돌아다닙니다. 임의(random)라고 했습니다만, 정확히 말하면 edge가 강할수록 그 길(edge)을 따라갈 확률이 높습니다. 이렇게 돌아다니는 것을 랜덤 워크(Random Walk)라고 하는데, 정해진 횟수만큼 이동한 뒤 특정 문서에 도착할 확률이 얼마인지를 계산하는 거지요.

간단하게 수식으로 써볼게요. J 노드에서 출발해서 얼마 후에 K 노드에 도착할 확률을 P(K|J)라고 합시다. J가 쿼리이고 K가 문서라면, P(K|J)가 높을수록 문서가 쿼리에 잘 부합한다는 뜻이니까 K의 랭크를 높여서 검색결과 상위에 보여주면 되겠죠?

클릭 그래프에 적용해서 설명하자면, 쿼리 노드에서 시작해서 많이 클릭된 문서 노드로 이동하고, 그 문서를 많이 클릭한 다른 쿼리(B)를 찾아서 또 이동하고, B에 대해서 많이 클릭한 문서로 이동하기를 반복. 그러다 보면 정말 좋은 문서에 도착하는 거지요.(그 문서와 애초의 쿼리 사이에 클릭 관계가 없더라도요.) 괜찮은 아이디어 같죠?

그런데… 이 순서를 뒤집어도 말이 됩니다. 무슨 말이냐고요? 이렇게 생각해 봅시다. 사용자는 찾으려고 하는 영상을 먼저 마음속에 그립니다. 그리고 나서 그런 이미지를 찾을 수 있는 쿼리를 입력하는 거지요. 즉, 앞에서 얘기한 P(K|J)에서 앞뒤가 바뀐 겁니다. 이를 P'(K|J)라고 할까요? 사용자가 쿼리 J를 입력하게 됐을 때, 애초에 염두에 뒀던 이미지가 K였을 확률을 구하자는 얘깁니다

클릭 그래프로 설명하자면, 이번에는 이미지 노드에서 출발해서 쿼리 노드로, 다시 이미지를 거쳐 쿼리 노드에 도착합니다. 도착하고 나서, 어디서 출발했을 확률이 가장 높은지를 따져보는 거지요. 이 방식은 뒤(쿼리)에서부터 거꾸로 원인(즉, 처음에 생각한 영상)을 찾아 들어가기 때문에 Backward Walk라고 부릅니다. 쿼리에서부터 시작하는 첫 번째 방식은 Forward Walk구요.

이런 아이디어를 수식으로 표현하고 계산하려고 Transition Matrix, Bayes Rule 등을 쓰는데, 자세한 설명은 논문을 참조하시면 되겠습니다.

다른 건 그냥 접어놓고, Forward Walk 방식과 Backward Walk 방식 중에 어떤 게 더 좋은 결과를 낼 것 같나요?

이것도 역시 논문에 다 나와 있으니까 궁금하신 분은 한 번 읽어보세요 :)