지금까지는 일반화된 랭킹 학습 체계 및 2가지 학습 알고리즘(1, 2)을 다루었다. 첫 번째 글에서, 결국 문제는 다음과 같이 단순화되었다.


즉, 임의의 아이템 xi와 xi'에 대해 어느 것이 더 좋은지를 가리키는 선호도 데이터들이 주어졌을 때, 이러한 데이터와 가장 잘 매치하는 랭킹 함수 f를 구하는 것이 목적이 된다. 예를 들면,

1. 누군가가 "나는 빵보다 밥이 좋고(빵,밥,<), 돼지고기보다 소고기가 좋고(돼지고기,소고기,<), 고기보다 회가 좋고(고기,회,<), 우유를 커피보다 좋아해(우유,커피,>)" 라고 얘기했을 때,
2. 그에 대한 일반화 규칙(즉, 랭킹 함수 f)을 찾아냄으로써,
3. 작게는 위의 예제 속에 등장하는 빵, 밥, 돼지고기, 소고기, 회, 커피, 우유라는 음식들 간의 순위를 예측하고,
4. 더 나아가, 이 사람이 된장찌개는 얼마나 좋아하는지(즉, f(된장찌개)의 값), 인절미는 얼마나 좋아하는지(즉, f(인절미)의 값) 등등, 애초에 언급하지 않았던 음식들에 대해서도 선호도를 예측하는 것이 목적이 된다.

이때, 하나의 데이터는 한 쌍의 아이템에 대한 선호도만 나타내면 충분하며(즉, 3개 이상의 아이템에 대해 줄을 세울 필요는 없음), 그 이유는 transitivity 때문이라고 첫 번째 글에서 언급하였다.
그리고 두 번째 글과 세 번째 글에서는, 선호도 데이터가 주어졌을 때 실제로 랭킹 함수를 구할 수 있는 알고리즘을 소개하였다.


하지만 아직 한 가지 문제가 남아있는데... 선호도 데이터를 어떻게 수집할 것인가? 하는 문제이다.
사실 이건 쉽게 구현하려면 무지 쉽다. 다음과 같이 하면 된다.


하지만, 종종 뜬금없이 이런 식으로 질문을 던지고 답을 요구하는 귀찮은 검색 엔진. 당신이라면 쓰겠는가?
윈도우에서 프로그램이 갑자기 뻗었을 때 오류 보고를 클릭하는 것도 귀찮아하는 것이 일반 사용자들이다. 특별히 눈길을 끄는 앙케이트가 아닌 한(예: 이회창 출마 찬성vs반대, 군가산점 폐지vs부활, 원더걸스vs소녀시대, ...), 사용자 참여를 기대하는 건 지나친 욕심인 것이다. 또한, 저렇게 대놓고 물어보면 거짓말 하기도 쉽다.

요는, 데이터 수집도 사용자 친화적으로 해야 한다는 것이다. 사용자는 그저 자연스럽게 서비스를 이용하게 놔둬야 하고, 우리는 사용자의 서비스 이용 패턴을 열심히 분석하여 그 속에서 선호도를 발견할 수 있어야 한다.


논의의 범위를 웹 검색으로 한정시켜보자.
웹 검색에서 선호도라고 하면, 어떤 문서가 원하는 정보를 더 많이 갖고 있는가가 되겠다. 다시 말하면,


즉, (qi, xi, xi', yi)가 선호도 데이터가 된다.
주어진 검색어라는 부분을 유독 강조한 이유는, 웹 검색에서 각 문서에 대한 선호도는 검색어에 따라 달라지기 때문이다(주1). 따라서 "어떤 검색어에 대한 선호도인지"(즉, qi)가 데이터에 포함이 되어야 하며, 랭킹 함수 f 또한 검색어 qi를 인자로 포함해야 한다. 즉, 웹 검색에서 랭킹을 구하는 문제는 다음과 같이 정의된다.

주석 보기

웹 검색 절차는 대개 다음과 같다.

1. 사용자는 검색어를 입력하고, 엔진은 그에 해당하는 검색 결과를 내놓는다(구글의 경우 한 페이지에 10개씩).
2. 각각의 검색 결과는 미리보기가 포함돼 있으며, 사용자는 각 링크의 미리보기 내용을 보고 이걸 클릭할지 말지 결정한다.
3. 딱히 이거다 싶은 정보를 찾지 못하면, 사용자는 검색어를 좀 더 적절하게 바꾸어 다시 입력한다.
4. 원하는 정보를 찾을 때까지 이를 반복한다.

즉, 이러한 절차를 방해하지 않으면서 선호도 데이터를 수집할 수 있어야 하는데, 이때 중요한 단서가 되는 것들이 바로 미리보기와 클릭, 그리고 재검색이다.

1. 미리보기를 통해, 사용자는 각각의 검색 결과가 원하는 것인지 아닌지 꽤 정확하게 파악할 수 있다.
2. 그렇게 파악을 하고 나면, 사용자는 그 중 가장 적절한 문서를 클릭한다. 즉, 클릭한 문서는 클릭하지 않은 문서보다 주어진 검색어에 더 적합한 것이라고 볼 수 있다.
3. 클릭한 문서가 여럿인 경우, 클릭한 문서들 끼리는 우열을 논할 수 없다.
4. 재검색을 하는 경우, 검색어는 다소 달라지지만 찾고자 하는 정보는 여전히 같다. 따라서, 재검색에서 클릭한 문서는 수정된 검색어 뿐 아니라 이전의 검색어에 대해서도 더 적합한 것으로 볼 수 있다.
5. 재검색에서 클릭한 문서는 이전 검색에서 클릭하지 않은 문서보다 더 적합한 것으로 볼 수 있다.

요약하면, 사용자가 클릭한 아이템을 클릭하지 않은 아이템보다 선호하는 것으로 여길 수 있다는 거다.
단, 이때 중요한 전제 조건이 있는데, 사용자가 미리보기로 본 아이템에 대해서만 생각해야 한다는 것이다. 미리보기를 보고도 선택하지 않았다면, 이건 확실히 덜 선호한다고 생각할 수 있다. 하지만, 아예 보지도 않은 아이템은 애초에 사용자로부터 어떤 판단을 받을 기회조차 없었던 셈이므로, 선호도에 대해 말할 수 없는 것이다.
즉, 정리하자면 다음과 같다.



하지만 한 가지 심각한 문제가 생겼는데, 어떤 것을 보았고, 어떤 것을 보지 않았는지 어떻게 알 수 있겠는가?
클릭은 기록이 남지만, 미리보기를 보았는지 안보았는지는...;; 모든 가정의 모니터에 눈동자 위치 추적기를 달 수도 없는 노릇인데 말이다.

그렇다. 어떤 사용자가 각 문서의 미리보기를 봤는지 안봤는지 일일히 확인하는 것은 불가능하다. 단지, "대부분의 사용자들은 대체로 이러이러하다~" 라는 경향성은, 적절한 규모의 실험자들에 대해 실험을 하여 통계량을 구하는 방법으로 알아낼 수 있다.

호아킴 그룹의 그랜카(L. Granka)라는 사람은 실제로 그러한 실험을 수행했는데, 실험 참여자들에게 구글로 이것저것 검색을 하게 하고, 그들의 클릭 기록 및 눈동자 위치 추적 기록(ASL 504라는 eye tracker를 이용)을 분석하여, 다음과 같은 결론을 발표한 바가 있다.

• 검색 결과에서 1위와 2위인 문서는 미리보기를 보는 경우가 많았다(60% 이상). 3위부터는 미리보기를 보는 비율이 많이 떨어졌다.
• 사용자는 대부분 최상단 결과부터 순서대로 훑어보았다. (즉, 순위가 높은 것을 더 먼저 봄)
• 클릭한 문서의 바로 아래 문서까지 미리보기를 보는 경우가 많았다. 예를 들어 5위인 문서를 클릭했다면, 클릭하기 전에 6위까지는 미리보기를 본다는 것이다.

이러한 경향성을 이용하여, 우리는 다음과 같은 규칙으로 선호도 데이터를 수집할 수 있다.

주석 보기

주석 보기

이제 마지막으로 한 문제만 남았다. 현재 검색어 qj가 이전 검색어 qi에 대한 재검색인지 아니면 새로운 다른 것을 검색하려는 것인지 어떻게 알 수 있을까?

호아킴 그룹이 Cornell University Library(CUL) 검색 엔진에 대해 쿼리 로그(검색 기록)를 분석한 결과, 같은 IP주소에서 30분 이내의 시간 간격으로 입력된 검색어는 91% 가량이 재검색이었다고 한다.

따라서, "같은 IP에서 30분 이내에 입력한 검색어는 모두 재검색이다" 라고 판단하여 규칙 3.과 4.를 적용해도 되겠다. 하지만 이것이 찜찜하다면, 연속된 검색어 qi와 qj가 서로 얼마나 유사한지, 그리고 각각의 검색 결과 리스트는 또 얼마나 서로 유사한지 등을 feature로 하여, 재검색 여부를 판단하는 binary classifier를 학습시켜도 무방하다. 물론 학습에 필요한 데이터, 즉 재검색에 해당하는 검색어 쌍들과 해당하지 않는 검색어 쌍들은 사람이 직접 골라줘야 하지만...
호아킴 그룹이 제안하는 feature들은 다음과 같다.

• CosineDistance(qi, qj):
    코사인 거리란, qi와 qj의 유클리디안 거리를 qi의 norm과 qj의 norm의 곱으로 나눈 값을 말한다.
   
• CosineDistance(qi의 검색 결과, qj의 검색 결과):
    [qi와 qj 모두에 대해 10위 이내인 문서의 개수]/100
   
• qi의 검색 결과 개수와 qj의 검색 결과 개수 중 작은 값:
    (1) 오타 등으로 검색 결과가 너무 적게 나온 경우 재검색을 할 확률이 높다.
    (2) 검색 결과가 너무 많이 나온 경우, 좀 더 자세한 검색어로 재검색하여 검색 결과 개수를 줄이려는 경우가 많다.
   
• 기타
    검색 결과의 미리보기가 서로 얼마나 유사한지? (미리보기에 등장하는 단어들로 판단)
    두 검색어가 입력된 시간 간격은? (5초 이내 / 10초 이내 / 30초 이내 / 100초 이내 / 100초 이상 등등)

이번 글은 수식이 없어서 쉽게 설명이 될 줄 알았는데 오히려 이전 글들보다도 훨씬 읽기가 힘드네요...ㅠ_ㅠ;
헷갈리는 문장도 많고 온갖 기호와 i, j 인덱스로 도배가 돼서...
애매한 부분은 질문 및 지적을 부탁드립니다...