Everyday carnival!

출처: http://ideas.tistory.com/1228153

Problem Definition

기존의 검색 엔진은 유저의 query에 대한 결과로 popular한 페이지를 검색 결과의 상위에 보여준다. 그 결과 popular한 페이지는 더 popular해지기 쉬운 반면, unpopular한 페이지는 일반적인 유저들에게 무시당하게 된다. 실제로 이러한 "Rich-get-richer" 현상은 새롭게 만들어진 high-quality의 페이지들이 그 높은 quality에도 불구하고 유저의 주의를 끌 기회 조차 가질 수 없기 때문에 문제가 된다. 이 페이퍼에서는 기존의 popular-based ranking(예를 들면 PageRank)의 문제를 완화할 수 있는 새로운 ranking function, "Page Quality"을 제안하려고 한다.

Their Solution & Results

PageRank의 핵심적인 feature는 그것이 웹 페이지의 popularity에 기초하고 있다는 것이다. 지금까지 popular한 페이지는, 새로운 유저가 보더라도 좋아할 확률이 높다는 것을 가정하고, 검색 엔진은 그들의 결과로 높은 PageRank를 갖는 페이지들을 상위에 보여준다. 그러나 동시에 unpopular한 페이지, 특히 최근에 새롭게 만들어진 페이지에 대해서는 매우 unbiased한데, 예를 들어 매우 훌륭하게 만들어져서 누구라도 좋아할만한 웹 페이지가 새롭게 만들어졌다면, 아직 많은 사람이 알지 못하기 때문에 적은 (또는 전혀 없는) 링크 수를 갖게 되고, 낮은 PageRank로 이어진다. 결국 검색 결과의 아랫 부분에 등장하게 되며, 이것은 다시 적은 수의 유저들에게만 이 페이지가 노출됨을 의미한다.

이러한 논의를 중심으로 생각해본다면, 우리가 정말로 원하는 것은 현재의 popularity에 기초한 ranking metric이 아니라, 처음 페이지를 보는 유저가 그 페이지를 얼마나 좋아(like)하는지에 대한 probability에 기초한 시스템이라 할 수 있겠다. 즉, Page Quality는 유저가 어떤 페이지를 처음 보았을 때 그 페이지를 좋아할 조건부 확률(conditional probability)이라 할 수 있다. 이제 문제는, 그것을 어떻게 구해낼 것인지에 관한 것이다.

그들의 아이디어는 크게 두 가지에 기초한다.

1. 그 페이지에 대한 링크가 만들어진다는 것은, 곧 유저가 그 페이지를 좋아한다는 것을 의미한다.
2. high-quaility의 페이지는 방문자의 대부분이 좋아할 것이기 때문에, popularity가 증가하는 속도가 다른 페이지에 비해 매우 빠르다.

첫 번째는 PageRank 알고리즘의 성공이 증명하고 있다. 유저는 자신이 어떤 페이지에 대한 흥미를 느낄 때 그 페이지에 대한 링크를 만든다. 그러므로 페이지에 대한 link가 만들어지는 것에 주목하면, 어느 정도의 유저가 그 페이지를 현재 좋아하고 있는지 대강이나마 추측할 수 있다. 두 번째는 직관적으로 이해할 수 있다.

이제 문제는 어떻게 popularity의 증가를 정확히 어떻게 quaility의 측정에 이용할 것인지에 관한 것이다. 저 둘이 비례할 것인가? 우리는 현재의 popularity와 popularity의 증가를 동시에 고려해야 하는가? 저 둘을 어떻게 합칠 것인가? 어떻게 합친 것이 가장 좋은 방법인지를 알아낼 수는 있는가? 등등.

이런 질문에 답하기 위해 간단한 웹-유저 모델로부터 출발한다. 이 모델은 어떤 식으로 유저가 웹을 surfing하는지를 반영하고 있다. 그래서 popularity evolution function을 얻어낼 수 있다면, 그것의 연구를 통해 어떤 식으로 quality를 추정할 수 있는지를 연구할 수 있을 것이다.

(논리의 전개 & 각종 수식의 유도는 논문을 직접 참고하시고)

페이지가 만들어진 당시에 많은 유저들은 그 페이지에 대해서 알지 못한다. 그렇기 때문에 그 페이지의 popularity는 quality를 정확히 반영하지 못한다. 하지만 페이지를 방문하는 유저의 대부분이 first-time visitor 이므로, 페이지의 퀄리티가 높기만 한다면 페이지의 popularity는 빠르게 증가할 것이다. 그러므로 상대적인 popularity의 증가는 좋은 quality estimator가 될 수 있다. 시간이 지나고 많은 유저가 그 페이지에 대해 알게 되면 페이지의 popularity는 더 이상 증가하지 않는다. 하지만 이 시점에서는 popularity 자체가 quality의 좋은 estimator가 될 수 있다.

이런 논의로부터 Relative popularity increase와 popularity 의 관계에 주목하면, 그 두 값은 상호 보완적이므로 두 값의 합을 구해보면 두 값의 합은 계속 일정하며, 그 값은 quality에 대한 좋은 estimator가 됨을 알 수 있다.

Strong Points

• 수학적 모델에 기초를 둔 논리 전개가 설득력 있음
• 처음에는 간단한 모델에서 시작해서 개념적인 이해를 도왔으며, 다양한 factor를 반영하여 새로운 모델을 만들어가는 과정에서도 여전히 첫 모델에서 얻어낸 concept이 옳다는 것을 이끌어내는 과정이 좋았음.
• PageRank의 단점을 보완했음을 이론적으로/실험적으로 증명했음.
• 기존에 존재하는 방법들(예를 들면 PageRank)보다 새롭게 만들어진 high-quality의 페이지가 유저에게 노출될 때까지 걸리는 시간이 줄어들었음.
• PageRank의 목표도 common-case를 유저에게 더 잘 제공할 수 있는 것이지만 이 시스템은 좀 더 현실의 유행에 민감한 common-case를 보여준다. 어떤 사건이 일어나면 같은 검색어에 대해서도 어제 유저들이 찾던 토픽과 오늘 유저들이 관심 있는 토픽이 다르다는 것을 고려할 때 Page Quality에 기반한 시스템은 유저들이 찾는 것을 보다 정확히 제공할 가능성이 높다.
• link structure가 만들어진 이후 contents의 변화에 대해 quality를 다시 계산하는 효과가 있다. 실제로 링크는, 만들어진 이후에는 잘 관리되지 않는다. (아무 블로그에나 가서 예전 글들을 보면 끊어진 링크나 내용이 변한 링크를 쉽게 발견할 수 있다) 그렇기 때문에 링크된 컨텐츠가 변경되었다 할지라도 link structure는 유지되기 때문에 PageRank의 방법에서는 - 끊어진 링크는 탐지해낼 수 있다 하더라도 - 변경된 컨텐츠에 덜 민감하다. 하지만 이 Page Quality의 방법은 popularity의 변화량을 같이 고려하기 때문에 PageRank보다 더 탄력적으로 반응할 수 있다.

Weak Points

• (페이퍼에서도 언급하고 있지만) 적은 scale로 실험이 이루어졌음
• (이것도 어느 정도는 언급하고 있지만) 실제로는 popularity의 시간에 대한 미분 값을 구할 수 없으므로 어느 정도의 시간차를 두고 PageRank의 값을 구해 그 차이를 이용해야 하며 오차가 필연적으로 발생한다.
• 실제로 구현/적용하기 위해서는 기존의 popularity-based ranking 시스템을 구현해야 하며, 그것을 기초로 다시 pageRank 값의 차이를 계산하는 시스템을 이중으로 구현해야 한다. (구현의 비용!)
• 새로 생겨난 페이지에 대해서 만들어지는 링크에 대해 매우 sensitive하므로, overestimating할 위험이 있다.
• n/r 파라미터를 정확히 결정하지 않으면 큰 효용을 얻기 어려움에도 불구하고 n/r의 최적 값을 구할 수 있는 것은 quality가 popularity와 어느 정도 비슷해 졌을 (충분한 시간이 흘렀을) 때이다. 또한 저 값은 검색어마다도 다를 것이고, 시간이 변하면 함께 변하는 값일텐데 ... 음. 로또인가.

New Idea

• 1세대 검색이 페이지의 content에 기반한 ranking metric, 2세대 검색이 현재의 link structure에 기반한 PageRank ranking metirc, 그리고 3세대 검색이 현재의 link structure 뿐만 아니라, 앞으로의 변화와 확장도 고려하는 Page Quality ranking metric 이라는데 음. 어느 정도 동의한다. 특히 네이버에 비해 구글이 '지금 당장'의 토픽에 덜 민감한 것을 고려하면 - 물론, 네이버는 Page Quality ranking metric을 도입하고 있는 것이 아니지만 - PageRank는 어떤 식으로든 이런 방향으로의 개선이 필요하다고 생각한다.
• 실시간 인기 검색어를 응용하면 유저의 최근 behavior를 보다 더 잘 반영할 수 있을 것 같다. 순위가 급등한 검색어에 대해서는 그만큼 'popularity의 증가율'에 가중치를 두어 계산한다고 하면 더 빠르게 그러한 경향을 검색 결과에서 보여줄 수 있다.