검색 엔진의 질의어 분석 - 하나를 보고 열을 찾아라!

검색연구동향 : 2010. 3. 22. 10:16   By LiFiDeA
목차 : 
질의어 분석 - 하나를 보고 열을 찾아라
랭킹 함수 (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 : 질의어 분석에 대한 저희 지도교수님의 발표자료입니다.

'검색연구동향' 카테고리의 다른 글

다시 화두가 된 실시간(real-time) 검색  (3) 2010.06.22
소셜 검색엔진 Aardvark(아드박)을 해부한다.  (2) 2010.02.21
검색(IR) 연구자의 경쟁력은?  (0) 2010.02.10
Trackback() : Comment ()

최선을 다하지 않는 것이 최선이다?

Essay : 2010. 3. 6. 12:15   By LiFiDeA
그야말로 all-out effort를 쏟아넣은 한주를 보낸 금요일 밤, 갑자기 든 생각입니다. 성실한 민족성으로 유명한 우리나라에서 '최선을 다한다'는 자세는 굉장한 미덕처럼 되어 있지만, 과연 최선을 다하는 것이 항상 바람직한 일일까요?

1. 냉정함을 유지하기가 어렵다.

최선을 다한다는 것은 그만큼 자신을 그 일과 동화(identify)시킨다는 일입니다. 그러다 보면 냉정함을 유지하기가 어렵습니다. 그런데 세상의 많은 일은 열정 만큼이나 냉정함을 필요로 합니다. 따라서, 최선을 다하려다가 오히려 일을 그르치는 수가 있습니다. 

2. 큰 그림을 놓치게 된다.

몰입도가 높을수록 한발짝 떨어져서 전체를 조망하기는 어렵습니다. 그러다보면 일이 잘못된 방향으로 나아가는 경우가 많고, 그 사실을 깨닫기도 어려워집니다. 몇시간 열심히 코딩한 것을 설계상의 실수로 다 날리게 되었을 때의 느낌, 아시나요?

3. 초반에 지쳐 쓰러지게 된다.

가치있는 일일수록 시간이 걸리고 불확실성이 큽니다. 살다보면 100만큼의 노력으로 된다고 생각했던 일에 두세배의 노력이 드는 경우도많습니다. 처음부터 최선을 다하다보면 계속 그만큼의 에너지를 쏟을수도 없을 것이고, 중반쯤 되서 포기하고 싶어집니다. 그러다보면 아무것도 이룰 수 없겠죠.

4. 삶의 균형을 잃기 쉽다.

갈수록 개인이 담당해야 할 Role이 많아지는 세상입니다. 그런데 한가지 일에 몰입하다보면 다른 일에 정신을 쏟기는 그만큼 어려워집니다. 최선을 다한 일이 잘못된 경우, 그만큼 상처도 큽니다. 한가지만 잘못되어도 모두 망가지는 것이 삶이니, 이 역시 최선을 다하는 데에 따른 부작용이 아닐까 합니다. 

5. 스스로에게 뭔가를 강요하게 된다.

별로 끌리지 않는 일인데도 '최선을 다한다'는 생각에 열심히 할 때가 있습니다. 영어에서는 그런 종류의 성실함을 drive라고 칭하고 마음에서 우러난 열정을 passion이라고 하는데 그렇게 강요된 성실함은 오래 가지도 않을 뿐더러 열정의 싹을 잘라버리는 경우가 많은 것 같습니다. 

----

이렇게 적어놓고 나니 말끝마다 'cool'을 입에 달고사는 미국 사람들이 갑자기 이해가 가기도 합니다. 열정이 배제된 삶은 마치 흑백 영상처럼 무미건조하겠지만, 열정이라는 불꽃을 통제하지 못한다면 큰 상처를 입게 될 테니까요. 매사에 최선을 다하기도 쉬운 일이 아닌데, 그렇게 해도 이렇게 함정이 많으니 노래 가사처럼 삶은 참 만만치 않군요. 하지만, 적어도 로봇이 이런 복잡미묘한 판단을 내린다는 것은 당분간 불가능할테니, 아직 인간의 존재 자체를 위협받을 일은 없다는 사실에 안도해도 될까요?

'Essay' 카테고리의 다른 글

스포츠와 스포츠맨십 - 야구에서 퍼팩트 게임보다 소중한 것은  (0) 2010.06.14
전문가의 시대는 끝났나  (0) 2008.10.03
개인 프로젝트를 왜 해야 하나  (0) 2007.03.01
Trackback() : Comment ()

구글의 진짜 경쟁력은 유연성

검색산업동향 : 2010. 3. 1. 12:40   By LiFiDeA
이번 달 Wired에 실린 구글의 검색 품질에 관한 기사입니다. 수많은 도전에도 불구하고 구글의 검색 품질은 따라잡기 힘들 것이라고 전망하고 있군요. 그리고 이를 뒷받침하는 핵심 역량은 유연성이라고 지적합니다. 경쟁사에서 새로운 기술을 선보여도 구글은 곧 이를 자사의 검색 알고리즘에 통합시킬 수 있을 테니까요. 저자는 이렇게 결론짓고 있습니다.
Still, even if there is such a shift, Google’s algorithms will probably be able to incorporate that, too. That’s why Google is such a fearsome competitor; it has built a machine nimble enough to absorb almost any approach that threatens it — all while returning high-quality results that its competitors can’t match.
물론 이는 말처럼 쉬운 일이 아닙니다. 수백개의 속성(feature)의 조합으로 이루어지는 검색 알고리즘을 잘못 고쳤다가는 그동안 쌓아올린 향상이 모두 무너질 수도 있기 때문이죠. 말하자면 검색은 균형의 예술(balancing act)인 것입니다. 구글의 검색 책임자인 Amit Sighal의 말을 들어봅시다.
Throughout its history, Google has devised ways of adding more signals, all without disrupting its users’ core experience. Every couple of years there’s a major change in the system — sort of equivalent to a new version of Windows — that’s a big deal in Mountain View but not discussed publicly. “Our job is to basically change the engines on a plane that is flying at 1,000 kilometers an hour, 30,000 feet above Earth,” Singhal says.
운항중인 항공기의 엔진을 고치는 일이라 -- 실감나는 비유입니다. 그리고 이정도 규모와 복잡성을 지닌 시스템을 튜닝하는 것은 과학에 가깝습니다. 더이상 '감'에 의존하는 것이 불가능하기 때문입니다. 이를 잘 아는 구글은 입력되는 모든 쿼리를 하나 이상의 실험을 위해 활용한다고 합니다.
 Every time engineers want to test a tweak, they run the new algorithm on a tiny percentage of random users, letting the rest of the site’s searchers serve as a massive control group. There are so many changes to measure that Google has discarded the traditional scientific nostrum that only one experiment should be conducted at a time. “On most Google queries, you’re actually in multiple control or experimental groups simultaneously,” says search quality engineer Patrick Riley.
인터넷 검색과 같은 Winner-takes-all Market에서 독보적인 1위를 추격하는 것은 어려운 일입니다. 특히, 이처럼 선두가 방심하고 있지 않다면 더욱 그렇습니다. 흔히 구글 검색의 품질은 PageRank에 기인한 것으로 알려져 있지만, 그들의 진짜 경쟁력은 끊임없이 바뀌는 환경에 적응할 수 있는 능력, 이를 뒷받침하는 실험 인프라와 노하우일 것입니다.

또한, 이 기사는 지난 10년간 구글이 선보인 검색 기술상의 혁신과 구글 검색이 경쟁사에 비해 나은 점을 구체적인 질의(query)를 들어 설명하고 있습니다. 예컨데, 구글은 'new york', 'new york times', 'new york times square'가 모두 다른 대상을 가리키는 질의라는 사실을 알아냅니다. 기사를 좀더 읽어보시면, 구글 역시 문서보다는 사용자의 질의를 좀더 잘 이해하는 쪽에 연구 초점을 맞추고 있다는 것을 알 수 있습니다. 예전에 이곳에 올린 검색 연구의 흐름에 관한 글과 비교해 보시면 흥미로울 것 같습니다. 

원본

'검색산업동향' 카테고리의 다른 글

네이버가 구글과 싸우는 법 - 검색엔진 연구자의 관점  (26) 2010.03.25
한국 인터넷은 술자리다  (4) 2010.02.23
iPod, iPhone, iPad, 소프트웨어를 무시해서는 삼성전자도 안된다  (16) 2010.01.31
Trackback() : Comment ()

한국 인터넷은 술자리다

검색산업동향 : 2010. 2. 23. 13:07   By LiFiDeA
주로 연구 목적으로 인터넷을 사용하다가 최근 블로깅을 재개하면서 우리나라 인터넷을 많이 사용하게 되었습니다. 처음에는 단지 제가 익숙하던 인터넷과 많이 다르다는 느낌이었지만, 점차 그 차이가 명확하게 다가왔습니다. 지나친 일반화의 오류를 감수하더라도 이렇게 요약해 보렵니다. 
(미국의) Internet이 광장이라면 우리나라의 인터넷은 술자리입니다. 
광장은 열린 공간에서 모든 사람이 자유롭게 서로를 바라보며 의사를 교환하는 상황을 가리킵니다. 술자리는 특정 호스트에 의해 제공되는 닫힌 공간에서 이루어지는 제한된 참가자들간의 소통을 상징합니다. 물론 광장에서 나누는 대화의 내용은 술자리의 그것과는 사뭇 다르리라 짐작할 수 있습니다. 

똑같은 TCP/IP망에 HTTP프로토콜을 사용하는 인터넷의 특성이 이렇게 다른 데에는 여러 원인이 있을 것입니다. 물론 근본적으로 문화가 다릅니다. 미국은 개인 중심의 사회이며, 모임의 장소도 주로 집인 경우가 많습니다. 하지만 한국은 아직도 개인에 대한 집단의 영향략이 강한 곳입니다. 게다가 (저를 포함하여) 우리나라 사람들은 '모임'을 참 좋아합니다. '자기'가 중심이 되는 블로그보다는 싸이월드, 포탈 게시판이 좀더 성향에 맞을지도 모르겠습니다. 

하지만, 우리나라 인터넷의 특성을 규정하는 데에는 포탈의 역할을 빼놓을 수 없습니다. 아래 표에 간단히 정리한대로 포탈은 인터넷의 주도권을 쥐고 (우리나라에서 인터넷을 한다는 것은 네이버나 다음을 한다는 것과 같습니다) 개인이 생산한 컨텐츠를 편집하고 출판합니다. 그 과정에서 운영방침에 맞지 않는 컨텐츠가 걸러지기도 하고 랭킹도 결정됩니다. 개인이 블로그나 포럼 등에 올린 컨텐츠가 랭킹 알고리즘에 의해 서열화되는 미국과는 매우 다른 모델입니다.

  인터넷 Internet 
주도권 네이버 / 다음 / 기타 분야별 포탈 (e.g. 해커스) 구글 /  블로그
컨텐츠 생산 개인이 생산 개인이 생산
컨텐츠 유통 포탈이 편집 & 출판  개인이 편집 & 출판 
컨텐츠 성격 수다 / 인신공격이 주 정보 교환 / 토론이 주
요약 닫힌 플렛폼 (Splinternet)  / 편집자 중심 열린 플렛폼 / 알고리즘 중심 

재미있는 것은 이런 컨텐츠 유통 과정의 차이가 컨텐츠의 성격에 미치는 영향입니다. 여러번 사회문제가 되었을 정도로 우리나라 인터넷(주로 포탈)에서 생산/소비되는 컨텐츠의 질에는 많은 문제가 있습니다. 건설적인 토론보다는 수다와 인신공격이 주를 이룹니다. 반면, Internet의 컨텐츠는 정보 및 의견 교환이 주를 이룹니다. 술자리와 광장이라는 비유가 여기서도 유효합니다. 반면, 우리나라 인터넷에서도 (주로 포탈 밖) 블로그의 컨텐츠는 품질면에서 외국에 견줄만 합니다. 
마셜 멕루한의 말을 빌지 않더라도 미디어가 메시지에 미치는 영향은 지대합니다. 다음 아고라등의 포탈에서는 제한된 카테고리(교육 / 정치 / 문화 / 등등)에 나이 / 계층 구별도 없이 전 국민이 여과되지 않은 의견을 쏟아내고, 이는 다시 답글이라는 형태로 확대재생산됩니다. 많은 서비스에 '인기글' 시스템이 있지만, 이 역시 다양한 글을 골고루 노출시키는 알고리즘의 부재로 일단 인기글에 올라간 글은 품질에 관계없이 계속 남아있는 폐해가 있습니다. 결과적으로 대부분의 포탈 게시판은 대부분 잡답 수준의 컨텐츠로 채워지고 있으며, 좋은 글이 있어도 발견되기 어려운 탓에 정보원으로서의 가치가 낮습니다.

포탈 측에서는 '적어도 사용자들이 모여 소통할 공간'을 제공하지 않았느냐고 항변할지도 모릅니다. 하지만, 이미 사회의 주도적인 커뮤니케이션 채널이 된 인터넷을 장악하고 있는 주체로서, 건전한 논의를 유도해야할 사회적 책임을 면하기 어렵습니다. 외부 검색엔진에 대한 컨텐츠 비공개 / 임의적인 서비스 중단 및 변경 / 공익보다는 자사의 이익을 위한 편집권 남용 등으로 포탈은 많은 비난에 직면하고 있습니다.

구글이 'Don't be evil'이라는 모토를 사용하는 것은 자사의 서비스가 가진 사회적 영향력을 남용하지 않겠다는 의지의 표현입니다. 포탈이 단기적인 트레픽 유지에 급급하는 대신, 더 넓은 안목에서 사용자가 좋은 컨텐츠를 만들고 폭넓게 공유할 수 있는 플렛폼을 제공한다면 장기적으로는 영리 추구과 사회적인 책임이라는 두마리 토끼를 잡을 수 있을 것입니다. 너무 순진한 생각일까요?

'검색산업동향' 카테고리의 다른 글

구글의 진짜 경쟁력은 유연성  (3) 2010.03.01
iPod, iPhone, iPad, 소프트웨어를 무시해서는 삼성전자도 안된다  (16) 2010.01.31
Human Computation의 사업화 - 아마존 Mechanical Turk  (0) 2009.02.03
Trackback() : Comment ()

소셜 검색엔진 Aardvark(아드박)을 해부한다.

검색연구동향 : 2010. 2. 21. 23:15   By LiFiDeA
윤석찬님 블로그에 소개된 소셜 검색엔진 Aardvark(아드박이라고 읽는군요;)에 관한 논문을 읽어 보았습니다. 아드박은 사용자의 질문에 대한 대답을 주는 문서를 찾는 대신에 가장 적절한 답변자를 찾아준다는 아이디어를 기반으로 합니다. 수십년간 지속되었으나 아직도 상용화되지 못한 자동 QA시스템 연구에 멋진 카운터를 먹인 셈이라고나 할까요. 

'Anatomy of a Large-Scale Social Search Engine'이라는 제목의 논문 역시 이론과 응용이 조화를 이룬 수작입니다. '문서'를 찾는 검색 모델을 '사람'을 찾는 용도로 변형시켰다는 측면에서 학문적으로 새로운 내용은 아니지만, 검색 모델의 구성요소를 요목조목 잘 설명하고 있습니다. 산업체 출신의 저자가 쓴 이유에선지 기술적인 내용을 쉽게 소개하고 있어, 검색 공부를 하시는 분들께 일독을 권합니다.

개괄적인 내용은 앞서 소개한 포스팅에 잘 소개되어 있으니, 여기서는 아드박의 검색 모델을 분석해볼까 합니다. 

검색 모델 분석
아드박의 검색 모델은 질문자(u_j)와 질문(q)에 대하여 잠재적인 답변자(u_i)를 랭킹하는 다음 수식으로 요약됩니다.


언뜻 복잡해보이는 이 수식은 사실 간단한 메시지를 담고 있습니다. 1) 질문자와 가장 가깝고 p(u_i | u_j) 2) 해당 질문을 가장 잘 아는 p(u_i | q) 답변자를 선택하라는 것입니다. 또한 질문에 대한 잠재 답변자의 지식을 평가하기 위해서 사용자가 어떤 주제(t)에 정통한지 p(u_i | t)와 질문이 어떤 주제에 해당하는지 p(t | q)를 고려하고 있습니다. 

이번에는 문서를 찾는 전통적인 검색 모델의 관점에서 위 검색 모델을 생각해 봅시다. 전통적 검색 모델에서는 문서의 품질 및 질의와의 관련성을 평가합니다. 또한 문서와 질의의 관련성을 평가하기 위해 질의를 다양한 토픽에 매핑시키는 기법이 사용됩니다. [1] 요약하면, 아드박의 검색 모델은 기존 검색 모델의 뼈대를 유지한 채 사용자 검색이라는 컨텍스트에 맞게 변형시킨 결과입니다. 

1) 사용자간의 친화성
사용자간의 친화성은 프로필 / 소셜 그래프 / 행동 패턴 등 다양한 기준(feature)에서 평가될 수 있으며, 실제 평가는 이 모든 요소를 적절한 Weight로 결합하여 이루어집니다. 재미있는 것은 행동 패턴 부분인데, 사용자가 얼마나 수다스러운지, 공손한지, 신속하게 응답하는지까지 고려합니다. 이는 단순히 유사한 관심사를 갖는 사용자를 매칭시키는 기존의 소셜 네트워크 검색 기법을 뛰어넘는 것이라고 볼 수 있습니다.

2) 답변자와 질문의 관련성
질문과 답변자의 관련성을 평가하기 위해서는 답변자의 프로필과 질문이 각각 어느 주제에 매칭되는지를 알아야 합니다. 우선 답변자의 프로필은 사용자의 정보 및 홈페이지 등을 통해 만들어지는데, 이 과정에서 해당 사용자의 소셜 네트워크가 해당 사용자의 프로필에 반영되는 점이 이채롭습니다. 즉, 내 친구들이 컴퓨터 전문가라면 나 역시 컴퓨터에 정통할 확률이 높아진다는 점을 고려하는 것입니다. 질문을 주제에 매칭하는 과정은 1)에서와 유사하게 Linear Combination을 활용하고 있습니다.

마치며
Aardbark은 인간과 기계를 한 시스템에서 조화시킨(Humans-in-the-loop) 좋은 사례입니다. 이처럼 사용자의 적극적인 참여를 유도하고, 이를 알고리즘과 결합하여 다시 사용자에게 고품질의 결과를 제공하는 어프로치는 최근 '핫'한 토픽인 것 같습니다. 아울러 전통적인 검색 모델이 이처럼 새로운 문제에 활용될 수 있다는 점이 주목할만합니다.  문서 대신에 '사람'을 검색한다는 아이디어 역시 이미 Expert Search라는 연구 분야에서 다루어진 바가 있지만, QA 서비스라는 문제에 적용시킨 점이 참신합니다. 구인/구직, Matchmaking(e.g. 듀오) 등에 폭넓게 활용될 수 있지 않을까 합니다. 

[1] 관련성 부분은 Relevance-based Language Model 이라는 논문에서 소개된 것과 거의 같습니다. 

'검색연구동향' 카테고리의 다른 글

검색 엔진의 질의어 분석 - 하나를 보고 열을 찾아라!  (3) 2010.03.22
검색(IR) 연구자의 경쟁력은?  (0) 2010.02.10
CIKM의 한국인 저자 논문들  (0) 2009.09.12
Trackback() : Comment ()

티스토리툴바