LiFiDeA의 검색 이야기 

웹의 발전은 정보검색(IR)이라는 분야를 도서관학의 일개 전공분야에서 최신 기술과 막대한 인력, 자원이 투입되는 거대 산업으로 바꾸어 놓았습니다. 지금도 대부분의 사람에게 웹 검색은 일상사가 되었지만, 앞으로도 위키/블로그와 같은 데이터 생산 및 공유 기술의 개발, 그리고 그에 따른 데이터의 증가에 따라 웹 검색의 수요는 계속 늘어날 것입니다.

규모도 규모지만, 웹은 IR 연구자들에게 항상 새로운 과제를 제시합니다. 홈페이지 검색, 뉴스 검색, Q&A 검색, 블로그 검색 등은 웹이 없었다면 생기지도 않았을 IR의 세부 연구주제입니다. 새로운 형태의 웹 서비스는 고유의 검색 문제를 안고 태어난다고 해도 과언이 아닙니다. 문제만 준다면 조금 얄미울텐데, 다행히 대부분은 해결의 실마리도 따라옵니다. 웹 문서의 링크 구조를 활용하는 PageRank 알고리즘, 검색에 활용되기 시작한 태그 데이터 등이 그 사례입니다.

하지만 웹의 발전이 IR연구자에게 주는 가장 귀한 선물은 역시 검색 로그(query log)가 아닐까 합니다. 사용자가 서비스에 접속하여 어떤 질의어를 입력하는지, 그리고 어떤 문서를 클릭하는지를 그대로 기록한 검색 로그에는 연구자들이 궁금해하는 검색의 비밀이 고스란히 담겨있기 때문입니다. 더 좋은 것은 이런 데이터를 거의 무제한으로 비용 없이 얻을 수 있다는 점입니다.

문제는 검색 업체가 아닌 이상은 이 데이터에 접근할 수 없다는 점인데, 최근에 MSR에서 검색 로그 데이터를 선별된 연구자에게 제공하는 워크샵을 제안했습니다. MSN의 검색 로그 1500만건이 클릭 데이터와 같이 제공된다고 하니 흔치않은 기회인 것 같습니다.

그렇다면 검색 로그로 무엇을 할 수 있을까요? 가장 단순하게는 질의어 통계를 낼 수 있을 것입니다. 네이버나 다음에서 보여주는 ‘인기 검색어’등이 그 예입니다. 또한, 사용자 활동이 세션(접속→종료)별로 기록된다는 점을 감안하면 사용자가 먼저 입력한 질의어를 가지고 다음 질의어를 예측하는 모델을 만들 수 있을 것입니다. 질의어 맞춤법 교정(query correction)이나 관련 검색어 제안 등이 이러한 사례입니다. 이를 좀더 확장하면 사용자의 검색 실력을 감지하여 그에 따라 적절한 처리를 해줄 수도 있습니다.

올해 SIGIR에서 화제가 되었듯이, 질의어를 분류하고 군집화하여 적절한 처리를 하는 데에도 검색 로그는 필수적입니다. 트렉 등에서 제공하는 수십 수백건의 질의어를 갖고 의미있는 질의어 모델을 만드는 것은 상식적으로 불가능하겠죠. 또한 연구용 컬렉션(문서-질의어 모음)은 실제 검색 서비스에서 나온 데이터가 아니라는 한계도 있습니다.

각 검색에에 대해 클릭된 문서가 질의어에 관련하여 옳은(relevant) 문서라고 간주하면, 대용량 검색 로그를 가지고 검색 모델(retrieval model) 자체를 학습하는 것도 가능합니다. 실제 검색 로그는 검색 서비스를 개발하고 개선하는 데 기반이 되며, 검색 모델 학습(Learning to rank)이 웹 검색의 폭발적 확산과 함께 본격적으로 연구되기 시작한 것도 우연은 아닐 겁니다. 하지만 사용자가 목록에 있는 모든 문서를 검토하고 클릭을 하는 것은 아니며, 원래 검색 의도와 다른 클릭도 있을 수 있기 때문에, 이런 방식으로 검색 로그를 활용하기 위해서는 다양한 노이즈 제거 기법이 적용되어야 합니다.

이러한 검색 로그 분석에는 대용량 데이터가 사용되기 떄문에 MapReduce 등의 대용량 병렬 처리 환경이 필요합니다. 저는 최근에 연구실에 있는 검색 로그를 학교의 Hadoop Cluster에서 분석하고 있는데, Pig라는 환경이 MapReduce를 데이터베이스(RDBMS)처럼 편리하게 사용하도록 도와줍니다. 좀더 익숙해지면 이곳을 통해 소개하도록 하겠습니다.

정보 검색, 컴퓨터 비전, 기계 번역 등 알고리즘으로 인간을 흉내내려는 인공지능 분야에서는 결국 사람이 무엇이 옳은지에 대한 판단을 내려줘야 하는 경우가 많습니다. 예를 들어 특정 질의어에 주어진 문서가 적합한지, 번역된 문서의 뜻이 원문에 충실한지 등의 판단이 이에 속합니다.

이처럼 단순하지만 사람이 해야 하는 일을 게임화하여 자발적으로 하게끔 하게 만드는 것을 핵심 아이디어로 하는 연구의 동영상이 Human Computation이라는 이름으로 화제가 된 적이 있었습니다. 그 연구의 핵심인물인 Luis von Ahn은 그 해 미국 CS Professor Job Market의 Hottest Candidate이었다고 하죠.

그때 많은 사람들이 재미있다고 생각하고 넘겼을 이 아이디어를 아마존이 사업화했습니다. 이러한 단순 작업의 노동력을 사고 파는 시장이 생긴 것입니다. 예를 들어 검색엔진 개발자가 질의어 100개와 각 질의어에 해당하는 Top100문서를 올리면 이들의 relevance를 누군가가 온라인으로 판별해주고 돈을 받는 것입니다. 실제로 얼마전에 MS에 인수된 자언어 검색 앤진 업체인 PowerSet의 검색 결과 판별이 올라와 있군요. 물론 온라인 옥션에서처럼 일이 제대로 되었는지를 제안자가 확인하여 지불하는 시스템입니다.

단순히 검색 연구자에게만 관련된 일은 아닌 것 같습니다. 지금은 이렇게 단순한 형태의 서비스지만, 앞으로 더 복잡하고 창조적인 일에 대해서도 충분히 적용될 수 있기 때문입니다. 더 나아가서는 피터 드러커나 폴 그라함, 구본형씨 등이 누누히 외쳐온 대로 전통적인 고용 형태가 점차 일회적이고 프로젝트 단위로 결합하여 일하는 ‘1인 기업(free agent)’의 집합으로 변화하는 신호탄이라고 해석할 수도 있지 않을까요.

한 블로그에는 이곳에서 일을 수행한 사람들의 처리 속도를 분석한 자료가 올라와 있습니다. 단순 작업이라도 일정한 속도로 처리하는 사람과 들쭉날쭉한 속도를 보이는 사람이 뚜렷이 구분되며 일 간에도 난이도의 편차가 있기 때문에, 더 ‘효율적인’ 사람에게 더 어려운 일을 배정하는 알고리즘이 필요하다고 결론짓고 있군요. 효율도 효율이지만, 제가 일의 성과가 낱낱이 데이터화하고 이에 따라 다음에 할 일이 기계적으로 결정된다면 조금 우울할 것 같군요 ;)

자연어 처리(NLP)를 중심으로 관련 분야를 폭넓고 싶게 다루었던 ‘Foundation of Statistical Natual Lanugage Processing(일명 주사위책)’을 기억하시는 분이 많으실 겁니다. 그 필진에 야후 리서치 책임자이신 분이 가세하여 집필한 IR책이 나와서 오늘 받아서 몇 챕터를 읽어보았습니다. 이미 국내 블로그에 소개된 바 대로, 웹에 초판이 꾸준히 공개되면서 널리 알려진 책입니다.

사실 처음 시작하는 입장이 아니라, IR이라는 분야를 1년간 주로 논문 및 실제 연구를 통해 공부한 후에 ’교과서’로 다시 읽는 기분은 조금 남다른 데가 있습니다. 학부때처럼 ‘요걸 언제 다 읽어’가 아니라, ‘이걸 이렇게 쓰셨구나.. 그런데 이 부분은 좀 이상한데?’가 되기 때문입니다. 산 아래에서 올려다보는 아득함과, 조금 올라와서 한숨 돌리며 내려다보는 여유의 차이라고 할까요? 아직은 아득함이 압도적이지만 말입니다.

이 책의 존재를 접하고 처음 들었던 의문이 있었습니다.

‘왜 IR책을 NLP연구자가 쓰는거지?’

사실 1저자인 Christopher D. Manning의 출판물 목록을 보면 IR쪽 연구는 거의 하지 않는다는 것을 알 수 있습니다. 연구 관심사를 살펴 보아도 IR은 빠져있군요. NLP와 IR이 그만큼 깊은 관련을 맺고있다는 측면에서 이해할 수도 있고, 그만큼 IR이라는 분야가 널리 각광을 받고 있다고 생각할 수도 있지만, 관련 분야의 연구자가 교과서를 쓰겠다고 나설 수 있을 정도로 아직 IR이라는 분야의 역사나 저변이 충분치 못해서라는 생각이 듭니다. 사실 DB 교과서를 OS 연구자가 쓴다는 건 말이 안 되지 않습니까.

어쨌든 책을 받아들고 읽으면서 이런 우려를 상당 부분 떨쳐버릴 수 있었습니다. 정통 IR에 해당하는 인덱싱이나 검색 모델 부분, 웹 검색에 대부분의 지면이 할애되어 있고, 예전에 주사위책에 있던 Latent Semantic Indexing도 거의 새로 씌인 것 같습니다. 오히려 NLP의 색채를 지우기 위한 노력의 일환인지, 제가 관심을 가졌던 NLP와 IR의 연계 연구에 대해서는 내용이 빈약하다는 느낌을 받을 정도였습니다.

하지만, 역시 본격 IR 교과서로는 미흡하다고 할만한 부분도 눈에 띕니다. 우선 지난번 책에 이어 Clustering과 Classification을 지나치게 많이 (그것도 비슷한 내용으로) 다루면서 IR의 주요 분야인 Question Answering이나 Cross Language IR, Multimedia IR을 누락시킨 것은 이해하기 힘듭니다. 또한 정통 IR 연구의 핵심인 검색 성능 평가(evaluation)부분에서는 평가 결과의 유의성 테스트(significance test)가 전혀 다루어지지 않으며, 평가의 효율성을 높이기 위한 최근 연구성과가 많이 누락되어 있음을 확인했습니다. (사실 이 부분은 실제 IR 연구를 하지 않고서는 깊이있게 쓰기 힘든 점이 있습니다.)

검색 모델 측면에서도 거의 모든 부분에 걸쳐 Vector Space Model(VSM) 을 기준으로 설명이 이루어집니다. 단, 별도로 독립된 Language Model(LM)관련 챕터에서는 LM의 상대적 장점을 분명히 인정하고 있습니다. 작년 말 Draft에서는 좀더 LM쪽에 인색한 평가를 내렸던 점으로 미루어볼때, 그사이에 IR 연구자들의 의견을 반영한 듯 합니다. 어쨌든 이론적으로나 성능으로나 이미 학계의 대세가 된 LM 관련 내용이 부족한 것은 사실입니다. (LM과 관련된 대부분의 연구가 최근에 이루어졌다는 것은 인정합니다만)

이처럼 구성 측면의 아쉬움에도 불구하고 복잡한 개념을 명쾌한 예와 간결한 문장으로 풀해내는 저자들의 능력은 이 책에서도 유감없이 발휘되고 있습니다. 조만간 정통 IR에 더 가까운 책이 나오겠지만, 이 책은 앞으로도 많이 쓰일 것 같습니다. 단, IR로 밥멀이를 하시는 분이 아닌 분이라면 (특히 주사위 책을 갖고계시다면) 웹사이트에서 부분적으로 출력해 보시는 것도 좋지 않을까 하는 판단입니다.

P.S. 이 책의 별명(~책)은 뭐가 될까요? 파란 색이라 물결?, 아니면 표지의 태그?

IR 연구를 하다 보면 매일 데이터를 접하고, 이를 통계적으로 해석하여 결론을 내리게 됩니다. 검색이 다루는 대상(문서, 질의어 등)이 불확정적인 대상이며, 검색의 목표 역시 결국에는 통계적으로 최대 다수의 사용자를 만족시키는 결과를 제공하는 것을 목표로 하기 때문입니다.

하지만 저는 불행히도 통계를 정식으로 배운 적이 없기에 이런 상황에서 항상 마음 한구석에 불편함을 느꼈습니다. 하지만, 이론적 틀이 없다는 약점은 스스로 자유롭게 사고할 수 있다는 기회를 제공하나 봅니다. 배우고 연구하면서 생긴 의문을 해결하기 위해 고민하고, 주변의 자문을 구하는 동안 통계라는 것이 단순히 학문이라기보다는 세상을 바라보는 방식이라는 느낌이 들었습니다.

통계적으로 세상을 바라본다는 것은 어떤 뜻일까요? 대부분의 통계 기법은 불확정적인 현상을 주어진 모델(주로 확률 분포) 중 하나에 대입하는 데에서 출발합니다. 모든 현상이 몇 안되는 분포에 들어맞으리라는 보장은 없지만, 중심극한정리로 설명되는 자연의 규칙성으로 말미암아 실제로 대부분의 현상은 정규분포로 대표되는 통계학적 모델에 부합합니다. (모델 선정이 적절한지는 그 자체로 통계학의 주요 관심사로 이를 모델비평(model criticism)이라고 합니다.)

일단 현상이 모델화되면 그 다음부터는 다양한 방법으로 데이터에 대한 결론을 유도할 수 있습니다. 모델과 관찰값을 비교하여 관찰값이 모델에서 나왔을 확률을 구할수도 있고, 서로 다른 관찰값으로부터 생성된 두 모델을 비교하여 서로 유의미한 차이가 있는지를 알아볼 수도 있습니다. 물론 모델에 의존하지 않는 통계 기법도 존재합니다만, 이들은 좀더 폭넓은 응용법위를 갖는 반면에 데이터에 대한 가정이 적은 만큼 정확성에 있어 제약을 받습니다.

이제 관심을 IR로 돌려봅시다. IR에서 내려야 하는 중요한 문제는 ‘새로운 알고리즘의 성능이 기존 알고리즘에 비해 훌륭한가?’입니다. 이는 위에서 언급한 두 모델을 비교하는 문제의 일종인데, 우선 기존 알고리즘과 새 알고리즘의 쿼리별 성능을 두 벡터의 형태로 얻고, 이 두 벡터가 하나의 분포에서 나왔다는 가설을 세우는 겁니다. 이때 세우는 가설은 우리가 증명하고자 하는 사실(새로운 알고리즘이 기존 알고리즘과 다른 분포에서 나왔다는 것)의 반대를 가정하기에 귀무가설(null hypothesis)라고 합니다.

이 과정은 두 사건(기존 알고리즘과 새 알고리즘의 성능)의 차이가 통계적으로 유의미한가(statistically significant)를 가리는 과정이기에 유의성 테스트(significance test)라고 하며, IR시스템의 평가를 다룬 최근 논문에서는 알려진 방법 중에 t-test를 사용하는 것을 권장하고 있으며, 적어도 50개의 토픽(질의어)를 대상으로 유의성 테스트와 상대적인 평가 지표(MAP)에서 10% 이상의 향상이 있는 경우에만 의미있는 성능 향상이라는 결론을 내고 있습니다.

통계 분석을 위해서는 주로 R이라는 패키지를 사용하는데, 이는 S라는 상용 통계 패키지의 공개 구현(implementation)으로 벡터와 행렬을 기본 데이터형으로 사용하는 등 Matlab과 유사한 형태를 띠나 좀더 통계 분석에 특화된 것으로 보입니다. R 참고문서로는 다음 자료를 추천합니다. 약간 생소한 언어학(linguistics) 데이터를 사용하고는 있지만, 기본 문법부터 고급 데이터 분석까지 충실히 설명하고 있습니다.

Reference

• 구체적인 예로 이 포스팅을 추천합니다.
• 좀더 자세한 설명은 다음 책의 샘플 챕터를 참조하시기 바랍니다.

IR분야의 최고 컨퍼런스인 SIGIR 2008이 얼마전에 싱가포르에서 열렸습니다. 그 권위만큼이나 대표적인 연구자들의 최신 성과들이 집대성되기에, 발표된 논문을 훑어보면 지금 IR 연구의 state-of-the-art, 그리고 앞으로의 방향까지 짐작케합니다.

그중 저의 눈길을 끌었던 것은 사용자의 질의를 분류하여 적절한 검색 방식을 선택하는 주제였습니다. 어떤 쿼리가 들어오든지 정해진 검색 모델을 사용하여 랭킹을 계산하던 모델은 사용자 및 검색 의도(query intent)가 제한적이었던 시절에는 유효했을 겁니다. 하지만 거의 모든 사람이, 온갖 목적으로 검색엔진을 이용하는 요즘에는 질의어에서 속성(feature)을 추출하여 분류(classification) 혹은 군집화(clustering)하고, 이에 따른 적절한 처리를 하는것이 중요한 이슈가 되고 있습니다.

이중 MSR에서 질의어를 분석하여 가장 적합한 검색엔진으로 검색한 결과를 보여주는 주제로 논문이 나왔습니다. 여기서는 더 나은 검색엔진을 만들어도 이미 구글에 락인(lock-in)된 사용자들을 유인하기 쉽지 않은 MS의 고민이 엿보입니다. 브라우저 플러그인 형태로 만들어져 가장 좋은 검색결과가 예측되는 검색엔진을 자동 선택해주기 때문에, 검색엔진간의 자유경쟁 시대를 예고하는 잠재력을 가진 연구라고 할까요. 물론 MS에서 개발된 플러그인은 웬만하면 Live Search를 추천하겠지만요;)

또한 질의어 분석을 통해 검색 개인화(personalization) 여부를 결정하는 논문도 흥미있었습니다. 개인화가 중요한 화두임에는 분명하지만, 이를 무차별적으로 적용했을 때는 오히려 검색결과의 품질이 전반적으로 떨어진다는 점이 문제인데, 여기서는 질의어와 상위 랭크된 문서를 분석하여 개인화가 성능을 높일 것으로 예측되는 질의에만 선택적으로 적용한다는 해결책을 내놓고 있습니다. 그리고 검색 의도가 분명치 않아 다양한 종류의 결과가 나오는 질의어일수록 개인화에 의해 성능을 높일 수 있다는 분석 결과를 밝히고 있습니다. 이와 유사한 연구로 질의어를 통해 지역화(localization)여부를 결정하는 논문도 있군요.

마지막으로 쿼리 분류를 랭킹 학습(Learning to Rank)에 접목시킨 연구도 눈여겨볼만 합니다. 기존 랭킹학습이 쿼리의 종류에 관계없이 단일한 랭킹 함수를 학습했다면, 여기서는 일단 기존의 질의어 집합을 K-Nearest Neighbor알고리즘으로 클러스터링하여 각 클러스터별로 랭킹을 학습한 뒤 새로 들어온 질의어에는 이와 유사한 질의어 클러스터의 랭킹 함수를 조합한 랭킹 함수를 적용한다는 아이디어입니다. 예를들어 어떤 질의에는 검색 결과의 최신성(recency)이, 다른 질의에는 권위(authority)가 중요할텐데요, 질의어를 보고 이를 예측하여 적절한 처리를 하겠다는 겁니다.

해마다 SIGIR에서는 발표 논문의 소주제(예 : 웹검색, 개인화, 랭킹 학습 등등)가 10가지 정도 결정되곤 하는데, 그 주제 자체가 매년 상당수 바뀝니다. 이렇게 역동적인 분야에서 연구를 한다는 것은 분명 도전이지만 그만큼 흥미진진합니다. 무럭무럭 자라는 아이를 지켜보는 느낌이랄까요. 내년에는 그 아이의 성장에 저도 한 숟가락(?) 기여해 보렵니다.