Public Note

Prologue: 지난번에 소개한 Random Walks on the Click Graph의 저자들이 쓴 다른 논문입니다. International World Wide Web Conference, 줄여서 WWW라고 하는 컨퍼런스에 포스터로 나온 건데요(2008년), 구체적인 기술 내용까지 모두 이해하려면 이것 외에 이 논문도 읽어봐야 할 것 같습니다.

텍스트를 주제에 따라 분류하는 기술도 아직 완벽하지 않습니다. 그러니 사진 같은 멀티미디어 데이터를 분류하는 일은 오죽하겠습니까. 성인 이미지 필터링 같은 문제를 생각해보면 됩니다.

문서에 들어있는 키워드만 고려하여 주제를 분류하면 이를 내용에 기반(content-based)했다고 합니다. 문서의 외부적인 조건 -웹페이지를 예로 들면, 누가 링크/추천했는지 같은 게 있겠네요- 은 무시하고 내용 그 자체에만 충실한 방식이죠.

반대로, 사람들이 그 문서를 어떻게 사용하는지에 따라서, 즉 그 문서를 둘러싼 외부 행위에 기반(bahavior-based)해서 분류를 하는 방법도 생각할 수 있습니다. 이 논문 Behavioral Classification on the Click Graph에서는 클릭 그래프(Click Graph, “검색 쿼리” – “클릭한 문서”의 관계를 그래프로 표현한 것)를 활용해서 성인 이미지 필터링을 했다고 합니다.

구체적인 알고리즘에 대한 설명은 아무도 원하지 않으므로 패스(-_-)하는데, 한 가지 눈길을 끄는 점은 웹페이지를 무작위로 뽑아서 성인용인지를 판단한 게 아니라, 텍스트 내용만 보고 분류했을 때 애매한 페이지만 따로 뽑아서 행위 기반으로 분류했다는 겁니다.(웹페이지 안에는 이미지만 있는 게 아니라 텍스트도 있잖아요.)

이제부터는 추측입니다. 눈을 감고 조용히 상상해봅시다.

마이크로소프트 연구소(Microsft Research)에서 열심히 일하던 저자들에게 어느 날 새로운 업무가 떨어집니다.

“웹페이지 중에서 성인 이미지가 들어 있는 것들만 골라내라.”

그들은 어떻게 할까 고민하다가 일단 텍스트 기반으로 필터링 필터링하기로 합니다. 이런.. 정확도가 별로 만족스럽지 않군요.

‘이제 어쩐다…? 옳지! 잘 분류되지 않은 놈들만 따로 모아서 클릭 그래프 방식으로 분류해 보자.’

346,000개의 쿼리와 2,500,000개의 URL로 이루어진 클릭 그래프를 처리하는 초조한 시간이 지나가고 드디어 결과가 나왔습니다.

‘오! 이 정도면 만족할 만한걸. 어서 논문 쓰자 +_+’

상상 끝났습니다. 이제 눈 떠도 됩니다. 실제 이야기를 알 도리는 없지만, 혹시 이런 과정을 거쳐 이 논문이 세상에 나온 건 아닐까요? :) 결과로 나온 논문을 보면서 그들이 어떻게 이런 걸 하게 됐는지 상상의 나래를 펼쳐보는 것도 꽤 재미있더라고요.

아무튼 클릭 그래프에서 랜덤 워크 모델을 쓰니까 -텍스트 기반 필터에서는 잘 분류되지 않던 페이지에 대해서- 정확도가 80%까지 나왔다는 소식을 전하며 장황했던 글을 마칩니다. 관심 있는 분들은 이 논문과 프롤로그에서 링크한 논문을 같이 한 번 읽어보세요.

이글과 관련이 있을지도 모르는 글 Random Walks on the Click Graph – SIGIR 2007 SIGIR 2010에서 관심이 가는 논문들

Tags: WWW, 그래프, 논문, 랜덤워크, 마이크로소프트, 정보검색, 클릭, 클릭그래프

This entry was posted on Tuesday, December 8th, 2009 at 10:53 pm and is filed under 공부. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.