최근 구글 검색에 대한 뉴스가 많습니다. 빙(Bing)에서 구글 검색결과를 모방한다는 이야기가 들어가기가 무섭게 JC Penny의 검색엔진최적화(SEO) 결과가 문제가 되었습니다. SEO는 다양한 수단으로 검색엔진 랭킹을 높이려는 행위 및 주체를 가리키는데, 여기에는 검색엔진이 용인하는 방법 (White Hat SEO)과 허용하지 않는 (Black Hat SEO) 방법이 있습니다. 사실 미국에서는 SEO가 산업으로 성장할 만큼 활발한데, JC Penny같은 큰 회사에서 Black Hat SEO를 했기 떄문에 문제가 된 것입니다. 뉴욕타임즈는 이번 SEO를 통해 JC Penny가 얻은 이득을 다음과 같이 추산합니다.
The Keyword Estimator at Google puts the number of searches for “dresses” in the United States at 11.1 million a month, an average based on 12 months of data. So for “dresses” alone, Penney may have been attracting roughly 3.8 million visits every month it showed up as No. 1. Exactly how many of those visits translate into sales, and the size of each sale, only Penney would know.

구글의 반격

제가 주목했던 것은, 여기에 대한 구글의 대응입니다. 우선 JC Penny의 Black Hat SEO 대해 즉각적인 조치를 취한 후, 전체 질의의 12%가 영향을 받을 정도로 대규모 업데이트를 단행하고, 이례적으로 그 내용을 공개했습니다. 그 주된 내용은 (사용자에게) 좋은 웹사이트와 나쁜 웹사이트를 구분할 수 있는 자동 분류기를 만들고, 이 분류 결과를 검색 랭킹에 적극 반영하는 것입니다. 구글이 '좋은 컨텐츠'를 구분하기 위해 사용했다는 기준은 다음과 같습니다.
  • Would you be comfortable giving this site your credit card?
  • Would you be comfortable giving medicine prescribed by this site to your kids?
  • Do you consider this site to be authoritative?
  • Would it be okay if this was in a magazine?
  • Does this site have excessive ads?
위 목록을 보면, 이번 업데이트가 단지 '스팸'을 가려내기 위함이 아니라, 웹사이트의 품질을 전반적으로 랭킹에 반영하기 위한 시도라는 것이 분명합니다. 그 결과로 주요 컨텐츠 팜 (퍼담기 등을 통해 불량 컨텐츠를 대량으로 생산하는 사이트) 의 랭킹은 심각한 타격을 입고, Times, CNN, Wikipedia 등 양질의 컨텐츠를 보유한 사이트의 랭킹이 올라갔다고 합니다. 워낙 광법위한 변화라 대부분의 웹사이트에서 이에 대한 대응책을 마련하고 있다고 합니다. 

검색엔진과 정보 생태계

이번 사건은 구글이라는 단일 검색엔진이 인터넷 정보 생태계 전반에 갖는 막대한 영향력을 다시금 환기시킵니다. 그리고 그들이 자신의 힘을 남용하지 않고 있다는 것을 보여줍니다. 이와 같은 대규모 업데이트의 내용을 이례적으로 공개한 것은 웹사이트 운영자들에게 구글 랭킹을 높이기 위해 해야할 일을 주지시키기 위함일 것입니다. 즉, 구글은 공권력을 동원하지 않고도 웹 퍼블리셔들이 더 유용한 컨텐츠를 만들도록 유도하는 것입니다. 구글에서 Web Spam 퇴치를 담당하는 Matt Cutts에 대한 묘사는 이러한 구글의 태도를 대변합니다.
Mr. Cutts sounded remarkably upbeat and unperturbed during this conversation, which was a surprise given that we were discussing a large, sustained effort to snooker his employer. Asked about his zenlike calm, he said the company strives not to act out of anger. You get the sense that Mr. Cutts and his colleagues are acutely aware of the singular power they wield as judge, jury and appeals panel, and they’re eager to project an air of maturity and judiciousness.
이처럼 정보나 상거래가 인터넷으로 집중되는 오늘날 검색엔진의 결과는 한 회사의 비즈니스 도구 이상의 의미를 띕니다. 모든 정보에 대한 접근성과 우선순위를 결정한다는 측면에서, 검색엔진의 역할은 정보 세상의 도로망을 까는 일에 비유할 수도 있을 것 같습니다.  예전 글에도 썼지만, 우리 나라 검색 회사들도 더 나은 인터넷 환경을 만들 수 있도록 힘써 주었으면 하는 바램입니다. 

추신 : 

구글이 사용한 것과 같이 문서 품질을 웹 검색결과에 반영하는 방법에 관한 논문이 이번에 저희 연구실에서 출판되어 소개합니다. 올해 2월 WSDM (Web Search and Data Mining) 컨퍼런스에서 발표된 따끈따끈한 논문입니다 ;)
작년부터 검색 서비스 업계의 화두는 '실시간 검색'이었다고 해도 과언이 아닙니다. 검색엔진 빅3(구글, 야후, 빙)에 이어 국내 포탈에서도 실시간 검색 서비스를 제공하고 있습니다. 최근 구글의 카페인 인덱싱 발표를 계기로, 더 신속한(fresh) 결과를 제공하기 위한 경쟁이 더욱 치열해질 것으로 보입니다. 구글의 발표 및 그리고 실제 사용자들의 테스트 결과에 따르면 블로그 및 뉴스 페이지가 업데이트된 후 검색에 표시되기까지 1분도 걸리지 않는다고 합니다.

실시간 검색이야 이미 다 되는 기술인데 뭐가 대수냐고 하실지 모르겠습니다. 하지만, 지난번 네이버의 개편 관련 포스팅에서도 언급했한대로 실시간 검색에 대한 빅3와 국내 포탈의 접근방법은 완전히 다릅니다. 오늘은 실시간 검색과 관련된 연구 결과를 요약해 보겠습니다.

야후! 리서치에서 발표한 최근 연구 논문에 따르면 실시간 검색의 주된 이슈는 1) 질의의 실시간성을 가리는 것 2) 실시간성 질의에 대한 더 나은 결과를 제공하는 것으로 나눌 수 있습니다. 예컨데, 마이클 잭슨의 사망소식이 전해졌을 때 질의어 'michael jackson'에 대해 최신의 권위있는 뉴스 결과를 제공한다면 성공입니다. 

이들은 실시간성 질의의 경우, 갑자기 질의량이 폭증한다던가 최신 뉴스 기사에 등장하는 단어가 사용된다는 등의 특성(feature)을 이용하여 최대 90%의 확률로 실시간 질의를 가려냅니다. 이런 식으로 분류된 실시간성 질의에 대해서는 문서의 시간, 종류, 속보성(hotness)등을 랭킹에 적극 반영합니다. 하지만 실시간 질의의 경우에도 기존에 사용하던 기법이 유효하기에, 기존 검색 모델의 성능을 살리는 동시에 실시간성을 고려하기 위해 이들은 세가지 기계학습 기반의 검색 모델을 제시합니다. 마지막으로, 일반 질의와 실시간 질의 처리에 모두 사용가능한 학습 데이터를 만들기 위해서 이들은 문서의 품질 평가에 일반적인 기준을 번저 적용하고, 나중에 실시간성을 반영하는 방식을 사용합니다.

이처럼 실시간성 질의와 일반 질의를 분리하여 처리하기에, 각각의 유형에 따른 적절한 결과를 보여줄 수 있습니다. 이들의 최신 논문에서는 트위터 등의 SNS를 활용하여 실시간성 질의의 검색 결과를 더욱 향상시키는 결과를 볼 수 있습니다. 이외에, 실시간성 질의가 아닌 경우에도 문서의 업데이트 주기 등을 랭킹에 반영하는 방법이 제안되기도 했습니다. 이번 구글의 발표내용을 살펴보아도, 모든 웹페이지의 변화 내용을 감시할 수는 없기에 페이지의 중요도 및 업데이트 주기를 고려하여 인덱싱의 우선순위를 결정하는 등 실시간 검색 구현을 위한 고려사항이 복잡다단하다는 것을 알 수 있습니다.

이처럼 실시간 질의를 제대로 구현하는 데에는 인덱싱에서 검색 모델과 특성(feature), 그리고 평가에 이르기까지 많은 고려가 필요합니다. 하지만, 국내 포탈에서는 아직 제한된 검색어에 대해 편집된 결과를 제공하는 것으로 보입니다. 하지만 이런 방식으로는 뉴스 속보 등에 관련된 질의에는 대응할 수 있을지 몰라도, 검색어의 대부분을 차지하는 테일(tail - 적은 빈도의) 질의에는 제대로 대응할 수가 없습니다. 검색 엔진의 경쟁력이 사실상 테일에서 결정된다는 점, 그리고 앞으로 검색엔진에 대한 의존도가 증가하면서 질의의 범주도 다양화될 것이라는 점을 감안하면, 이는 올바른 방향이 아니라는 생각입니다. 
목차 : 
질의어 분석 - 하나를 보고 열을 찾아라
랭킹 함수 (retrieval model) - 검색 엔진의 심장부
검색 결과 평가하기 - 평가 없이는 향상도 없다
검색 기술의 미래 - 
  
검색 연구자들은 어떤 생각을 하고 있을까 

이번 글의 주제는 질의어 분석입니다.
검색을 '문제 해결'에 비유한다면 질의어 분석은 문제를 정확히 파악하는 것인데, 문제 파악이 제대로 되어야 올바른 답안(문서)를 고를 수 있다는 것은 자명합니다. 특히 
사용자의 질의어는 대부분 불충분하며 (평균 2~3단어) 오류를 포함하는 경우도 많기에 효과적인 질의어 분석은 검색 품질에 결정적인 영향을 끼칩니다. 

구글이나 야후, 빙과 같은 검색 엔진들도 이를 잘 알기에 사용자의 질의어를 고쳐주거나(spell correction), 더 나은 대안을 제시하거나(query suggestion) 합니다. 이를 구현하기 위해 과거에 대부분 규칙 기반(rule-based)의 처리에 의존했던 것이, 막대한 양의 사용자 데이터(query log)를 활용한 통계적인 기법으로 대체되고 있습니다. 예컨데 과거에 고정된 규칙이나 단어 목록을 사용하던 어근 분석(stemming)이나 불용어 제거(stopword removal)에도 데이터에 기반하여 검색 성능을 최적화하는 연구가 진행되고 있습니다. 

질의어 분석이라는 주제는 
저희 연구실에서 한학기동안 세미나를 했을 정도로 방대하기에, 이번 글에서는 검색엔진이 사용자의 질의를 받아 처리하는 과정을 단계별로 소개하고, 그 과정에서 질의어 분석의 주요 이슈를 소개하고자 합니다. 아래의 네 단계는 세미나 내용을 바탕으로 제가 구성한 것입을 밝힙니다. 

(1) 분석을 위한 추가적인 단서 찾기 (augmentation)

질의어 분석을 위해 가장 먼저 해야하는 일은 분
석을 위한 추가적인 단서를 찾는 것입니다. 사용자가 입력하는 질의는 보통 짧지만 사용자의 프로필이나 현재 위치, 혹은 과거의 질의 목록을 안다면 분석에 도움을 받을 수 있는 경우가 많습니다. 흔히 말하는 검색 결과의 개인화는 이 단계에서 이루어지는 경우가 많습니다. 

(2) 유형별로 분류하기 (classification)

단계 (1)을 거쳐 확장된 질의는 추가적인 처리를 거치기 전에 유형별로 분류되는 것이 보통입니다. 분류의 기준은 매우 다양하겠지만, 보통 정보를 찾는지 (informational) 웹사이트를 찾는지(navigational), 뉴스 / 지역 / 쇼핑 등 특정 분야의 컨텐츠를 원하는지(vertical intent) 등을 판별해 내는 것이 목적입니다. 질의어에 대한 세세한 처리를 거치기 전에 질의어의 유형을 파악함으로써 유형에 따른 적절한 처리가 가능해집니다.

(3) 질의 해석하기 (interpretation)

그 다음 순서는 질의를 세부적으로 해석하는 일입니다. 질의에서 고유명사를 찾아내거나 
(named entity recognition)
, 잘게 나누거나(segmentation), 오류를 수정하는 일(spell correction)이 모두 이 단계에서 이루어집니다. 앞서 언급한 
어근 분석(stemming)이나 불용어 제거(stopword removal) 역시 이에 해당합니다. 
단계 (1)과 (2)에서 파악된 추가적인 단서와 유형은 이 단계에서 정확한 해석을 하는데 큰 도움이 됩니다. 예컨데 쇼핑에 대한 질의로 판명된 경우, 알려진 제품명과 대조하는 방법으로 고유명사를 찾아낼 수 있을 것입니다. 

(4) 질의 다듬기 (refinement)

앞선 단계에서 질의 자체의 의도에 대한 분석에 초점을 맞추었다면, 마지막 단계에서는 분석 결과를 바탕으로 질의를 다듬고 개선합니다. 추가적인 질의어를 더하거나 (expansion) 쓸데없는 질의어를 빼기도 하고 (reduction),  질의어에 중요도에 따라 가중치를 두기도 합니다 (weighting). 당연한 말이지만 적절한 변형을 위해서는 질의 자체에 대한 정확한 분석이 선행되어야 합니다. 이처럼 변형된 질의는 사용자의 원래 질의를 대체하는 것이 보통이지만, 경우에 따라서는 사용자에게 제안되기도(suggestion) 합니다. 

마치며
이번 글에서는 검색 엔진의 질의어 분석 과정을 처리 순서에 따라 알아 보았습니다. 사용자가 입력하는 몇 안되는 단어를 가지고 사용자의 의도를 파악하고 이를 더욱 효과적인 질의로 변형하는 과정은 이처럼 복잡 다단합니다. 또한 위에서 설명한 단계들간에 밀접한 연관성이 있기 때문에, 이 모두를 아우르는 통합적인 모델의 개발이 최근의 연구 초점이라는 점도 주목할만 합니다. 좀더 궁금하신 내용을 답글로 알려주시면 감사하겠습니다.

참고자료
Query Evolution by W. Bruce Croft : 질의어 분석에 대한 저희 지도교수님의 발표자료입니다.

목차 : 
정보 검색 (IR) 연구의 최신 동향
4가지 측면에서 바라본 정보 검색 (IR) 연구의 흐름
검색을 위한 문서 모델링 - 문서에서 유용한 속성 추출하기
질의어 분석 - 사용자 질의를 남김없이 해부한다
랭킹 함수 (retrieval model) - 검색 엔진의 심장부
검색 결과 평가하기 - 평가 없이는 향상도 없다
검색 기술의 미래 - 
 
검색 연구자들은 어떤 생각을 하고 있을까 

검색을 한마디로 정의하자면 '질의어에 대하여 문서를 평가하는 일'입니다. 그리고 제대로 된 평가를 위해서는 평가의 항목이 잘 정의되어야 할 것입니다. 중요한 요소
(feature)
를 모두 포함시키고 각 항목의 값을 정확히 매겨야 할 것입니다. 문서 모델링은 이처럼 검색을 위해 유용한 속성을 찾고 그 값을 추정(estimate)하는 작업입니다. 다음으로 몇 가지 대표적인 속성을 알아보겠습니다.

Topicality (textual similarity)
검색엔진을 만든다면 가장 먼저 생각할 수 있는 것이 질의어를 많이 포함한 문서(TF)를 먼저 보여주는 것입니다. 실제 검색엔진이 질의어에 대한 관련성을 평가하는 방법 역시 유사합니다. 몇가지 더 추가되는 고려사항은, 같은 빈도라면 좀더 드문 단어를 포함한 문서를 높게 평가하고 (IDF), 문서간 길이가 다르다는 사실을 고려하여 점수를 보정한다는 정도입니다. 많이 사용되는 TF-IDF, BM25, Query-likelihood등이 모두 이러한 아이디어를 각기 다른 수학적 모델로 표현한 결과이며, 잘 튜닝된 경우 비슷한 성능을 내는 것으로 알려져 있습니다. 

문서가 구조화된 경우에는 여러 항목(field)가 존재하기 때문에, 위와 같은 관련성 평가를 각 항목별로 할 수 있습니다. 그 후에 항목별 점수를 가중치를 두어 (예: 제목은 본문보다 2배 중요하다) 결합하면 최종 점수를 계산할 수 있을 겁니다. 저의 첫번째 논문은 이에 한걸음 나아가 각 질의어 별로 각 항목에 다른 가중치를 두는 아이디어를 기반으로 합니다. 

또한 검색 성능(주로 recall)을 높이기 위해 문서에 추가적인 텍스트 요소를 포함시키는 기법 역시 활발한 연구가 되고 있습니다. 많이 알려진 Anchor Text (문서를 대상으로 한 링크에 포함된 텍스트) 이외에 문서에 대한 태그나 질의어를 아는 경우 이를 문서 자체에 포함시키면 검색 성능을 높일 수 있겠죠. 또한 클러스터링을 통해 이웃 문서를 찾고, 이렇게 찾은 이웃 문서의 단어를 각 문서에 포함시키면 성능이 높아진다는 연구 결과도 있습니다.

Authority (popularity)
내용상의 관련성이 비슷하다고 해도 품질이 높고 믿을만한 문서를 먼저 보여주어야 할 것입니다. 이제는 일반명사가 되버린 구글의 PageRank를 포함하여 이러한 문서의 품질을 평가하는 방법에는 여러 가지가 있습니다만, 대부분 (웹) 문서간의 연결관계를 분석하여 종합한 결과로 품질이 게산된다는 점입니다.  이에 대한 확장으로 특정 주제에 대해 권위있는 페이지를 계산해내는 Topical PageRank라는 기법도 개발되어 널리 쓰이고 있습니다. 

Recency
최근 많은 검색업계의 화두가 된 것이 실시간 검색(real-time search)입니다. 이는 속보성이 중요한 질의를 가려내어 실시간으로 업데이트되는 뉴스나 트윗을 보여주는 기법입니다. 실시간이 아니더라도 최근 만들어진 문서일수록 더 정확한 내용을 담고 있을 확률이 높습니다. 또한 자주 업데이트되는 페이지 역시 좋은 점수를 받습니다. 

마치며
지금까지 검색을 위해 문서를 평가하는데 유용한 속성을 알아보았습니다. 물론 이외에도 도메인에 따라 다양한 속성이 존재하며, 상업용 웹
 검색엔진에서는 수백 수천개의 속성을 사용한다고 합니다. 사람이라면 순간적 직관으로 판단할 수 있는 일이겠지만, 그 정도로 복잡한 시스템의 
검색 결과에도 오류가 많은 것을 보면 인공지능을 만드는 것이 어렵다는 것을 알 수 있습니다. 

또한 속성이 개수가 많아질수록 속성간의 상대적 중요성을 사람의 힘으로 판단하기 어렵습니다. 따라서 최근에는 주로 사용자 클릭 데이터를 바탕으로 속성의 가중치를 계산해주는 기계학습 기법(Learning to Rank)이 각광받고 있습니다. 이런 연구에 널리 사용되는 데이터셋을 소개한 논문에는 검색을 위해 얼마나 다양한 속성이 사용될 수 있는지가 잘 드러나 있습니다. 

작년 2학기에 저는 지도교수이신 Bruce Croft교수님이 주제하는 논문 발표 세미나에 참가하였습니다. 규모는 크지 않았지만 Yahoo! Research의 Rosie Jones와 같은 사람들이 연사로 초청될 정도였습니다. 한학기 내내 최근 검색 연구동향을 대표하는 약 스무편의 논문을 읽고, 저는 검색 개인화(personalization) 관련 내용을 발표(자료 첨부)했습니다. 

한참 전에 검색 연구의 개론이라는 글을 썼었는데, 그간 배운 내용을 정리할 겸 앞으로 몇차례에 걸쳐, 최신 논문에 근거한 IR 연구의 동향을 소개할까 합니다. 각 논문의 기술적인 내용을 다 설명할 수는 없겠지만, 기본 아이디어와 큰 흐름 정도는 전달하려 합니다.  큰 그림은 다음과 같습니다. 시스템 측면에서 문서의 속성(feature)을 추출하여 인덱싱(1)하고 사용자의 질의를 분석(2)하여 최종적으로 각 문서에 대한 점수를 계산(3)하고, 마지막으로 검색 결과의 품질을 평가(4)하여 성능 개선에 활용하는 것입니다. 


위 그림이 검색 연구의 전부라고 할 수는 없지만, 대부분의 연구가
 문서 모델(document model), 질의어 모델(query model), 검색 모델(retrieval model), 그리고 평가(evaluation) 중 하나의 카테고리에 속하며, 실제 많은 연구가 위에 소개한 기본적인 모델을 특정 분야 (e.g. 웹 검색, 블로그 검색, 데스크탑 검색)에 적용하는 것을 주제로 합니다. 

마치며
다음번에는 각 부문별로 최근의 연구 동향을 요약해보겠습니다. 내용에 대한 문의나 제안은 언제든지 환영합니다. ^^

참고 자료
IR 교과서 Stanford / UMass CIIR