최근에 산업체 연구소에 지원을 시작했습니다. 지원하는 회사 중 대형 전자상거래 업체가 있는 관계로 '추천 시스템(Recommendation System -- 이하 RecSys)'에 관심을 가지게 되었습니다. 추천 시스템이라는 분야 및 RecSys라는 컨퍼런스는 알고 있었지만, 좀더 자세히 들여다보면서 검색 분야와 재미있는 차이 및 연관성을 발견할 수 있었습니다. 오늘은 검색의 사촌(?)이라고 할 수 있는 RecSys라는 분야에 대해 소개해볼까 합니다.

추천 시스템 개관

우선 추천 시스템 및 연구의 흐름을 살펴봅시다. 넷플릭스 시스템이 사용자에게 다음에 볼 영화를 추천하는 것, 혹은 아마존이 초기화면 및 상품 페이지에 'You might be interested…'라는 식으로 구매를 유도하는  것이 추천 시스템의 대표적인 사례입니다. 더 자세한 소개는 위키피디아 아티클을 참고합시다.

최근에 읽은 Recommender Systems: An Introduction이라는 책에는 추천 시스템 연구에 대한 최근 동향이 잘 소개되어 있습니다. 이책에 따르면, 사용자 집단의 품목 선호도를 바탕으로 사용자가 아직 경험하지 못한 품목을 추천하는 문제에서 추천 분야의 연구가 시작되었다고 합니다. 사용자 집단에 대한 정보를 개별 사용자의 품목 추천을 위해 사용한다는 의미에서 이를 Collaborative Filtering이라고 통칭합니다. 

Collaborative Filtering은 결국 User-Item Matrix에서 아직 관찰되지 않은 값은 예측하는 문제로 귀결되는데, 사용자 혹은 항목간의 Similarity를 기반으로 예측하는 Memory-based Approach와 Matrix 전체를 대상으로 예측을 위한 알고리즘을 적용하는 Model-based Approach가 있습니다. Memory-based Approach가 복잡성이나 효율면에서 우위를 갖지만, Model-based Approach가 적은 데이터에서 더 잘 동작하며, 전반적으로 더 나은 성능을 내는 것으로 알려져 있습니다.

전통적인 검색 모델에서는 Query와 문서의 유사도를 바탕으로 문서를 랭킹하기에, 여기까지는 검색과 추천이 상당히 다른 이야기입니다. 하지만 추천을 하기에 충분한 양의 선호도 및 기타 정보가 존재하지 않는 경우, 사용자의 프로파일과의 매칭을 바탕으로 추천 결과를 생성하는데, 이를 Content-based Approach라고 부릅니다. 이 경우 매칭을 위해 TF-IDF, 혹은 이와 유사항 Metric을 사용하기 떄문에 결국은 사용자의 프로파일이 질의어가 되는 검색이라고 볼 수도 있습니다. 

이외에도 다양한 추천 기법이 존재하는데, 예컨데 디지털 카메라 선택과 같이 특정 도메인의 지식이 필요한 경우, 이를 직접 모델링하는 (예를들어 가격에 민감한 사용자에게 Low-pixel 카메라를 추천) Knowledge-based Approach도 눈여겨볼만 합니다. 최근에는 위에서 설명한 여러 기법을 결합하여 성능을 향상시키는 Hybrid Approach가 주로 사용되는데, 이는 검색 Feature를 기계학습을 통해 결합하는 Learning-to-Rank기법과 유사합니다. 
 

검색 vs. 추천?

이처럼 추천과 검색은 비슷하면서도 다른 문제입니다. 검색에서는 질의어와 품목(주로 문서)를, 추천에서는 사용자와 품목(주로 상품)을 매칭합니다. 검색이 사용자가 입력한 질의에 대한 응답으로 이에 적합한 문서를 찾는 반면, 추천은 사용자의 선호도 정보를 바탕으로 (굳이 사용자의 요청이 없이도) 품목을 추천하여 사용자의 의사결정을 돕는 것을 목표로 합니다. 검색과 추천 리서치 커뮤니티의 주요 컨퍼런스 역시 전혀 다릅니다. 

하지만, 검색과 추천이라는 전통적인 사고의 틀을 조금만 벗어나면 이 둘의 유사성이 눈에 들어옵니다. 우선 검색과 추천 둘다 대상은 다르지만 (Query-Item / User-Item) 유사도 분석을 필요로 하는 매칭의 문제입니다. 또한 개인화 검색에서는 사용자의 선호도를 직접 모델링하니, 추천과 검색의 Hybrid라고 볼 수 있습니다. 반면에, 많은 추천 시스템에서 키워드 검색을 함께 제공하고 있습니다. 아래 표는 검색과 추천의 유사점과 차이점을 요약합니다. 


검색 + 추천

여기까지 읽으신 분이라면 어느정도 감을 잡으셨겠지만, 검색과 추천은 목표에 있어서나 기법상으로나 연관성이 많은 분야입니다. 위에서 언급한 Content-based Recommendation이나 Personalized Search같은 경우에는 이미 검색과 추천의 구분이 별 의미가 없습니다.

굳이 나누자면, 사용자에 대해 별 정보가 없고 사용자의 정보욕구가 질의어를 통해 잘 표현되는 경우 검색 기법이, 사용자에 대한 정보가 많이 존재하여 사용자의 정보욕구에 대한 좀더 정확한 예측이 가능할수록 추천 기법이 유용하다고 볼 수 있습니다. 아래 다이어그램은 어떤 상황에서 검색과 추천 기법이 적용가능한지를 나타냅니다.


시스템 관점에서는 이렇게 검색과 추천을 구분할 수 있습니다만, 사용자의 입장에서는 시스템이 자신이 찾는 정보를 보여주는 것과 알아서 자신에게 정보를 보내주는 것이 둘 다 중요할 것입니다. 따라서, 제대로 된 서비스를 위해서는 검색과 추천 기능이 모두 필요할 텐데, 여기서 중요한 것이 검색과 추천 기능의 통합입니다. 

여기서 통합은 단순히 두 기능을 동시에 제공하는 것이 아니라, 두 기능의 동작을 유기적으로 결합하는 것을 뜻합니다. 예컨데, 사용자가 추천 알고리즘의 결과에서 어떤 항목을 선택했다면, 이를 검색 결과에도 반영하고, 반면에 검색 질의어 및 선택결과가 추천 결과에도 반영되는 것입니다. 검색을 검색으로, 추천을 추천으로 바라보는 기존 시각으로는 이렇게 검색과 추천을 아우르는 사용자 경험을 제공할 수 없을 것입니다.



마치며 & 관련자료

오늘은 검색과 사촌간이라고 할 수 있는 추천 시스템 연구를 검색과의 비교를 통해 알아보았습니다. 궁극적으로는 사용자와 시스템의 모든 인터렉션을 바탕으로 프로파일을 구성하고, Siri와 같은 사용자에게 친화적인 인터페이스를 통해 개인화된 서비스를 제공하는 것이 검색 및 추천 연구의 비전일 것입니다. 위에서 언급한대로, 이런 비전을 현실화하기 위해서는 여러 분야로 파펀화된 연구성과를 융합해야 할 것입니다.

RecSys 역시 검색처럼 상업 애플리케이션이 활발한 분야라 관련 Tutorial이나 Survey가 많습니다.  더 자세한 소개는 위에 언급한 책 및 다음에 소개하는 주요 논문을 참고하시기 바랍니다. 

  • Evaluating collaborative filtering recommender systems
    Beyond Algorithms: An HCI Perspective on Recommender Systems
    Collaborative Prediction and Ranking with Non-Random Missing Data

p.s. 강민석( @minsuk1015 )님께서 CACM에 나온 관련기사를 추천해 주셨습니다. 

오랜만의 책소개입니다. 오늘은 "How to Measure Anything"이라는 제목의 (실용서를 가장한) 통계학 책입니다. 물론 '측정'에 관심있는 분들에게는 실용서가 되겠지만, 저는 통계학 교과서보다 통계 이론의 요점을 더 명쾌하게 전달하는데 가장 높은 점수를 주고 싶습니다. 

이 책은 제목 그대로 '모든 것은 측정할 수 있다'는 명제에서 출발합니다. 저자의 핵심 주장은 결국 측정이란 어떤 종류의 의사결정을 뒷받침하기 위한 수단이며, 어떤 종류의 측정이건 의사결정의 불확실성을 낮춰줄 수 있다면 유효하다는 것입니다. 예컨데 인간의 지능을 정확히 측정하기란 불가능에 가깝겠지만, 두 사람중 누구를 채용할 것인가를 결정하는 데에 필요한 정보를 얻는 것을 훨씬 쉽다는 것입니다. 이 책에서 제시하는 정의를 몇가지 살펴봅시다.

Measurement : 
  A quantitatively expressed reduction of uncertainty based on one or more observations.

Uncertainty :
  The lack of complete certainty; the existence of more than one possibility

Risk :
  A state of uncertainty where some of the possibilities involve undesirable outcome.

이를 바탕으로, 이 책은 모든 종류의 측정 문제에 적용할 수 있는 5단계 지침을 제공합니다. 우선 의사결정 및 측정 대상을 명확히 하고, 현재 지식 수준을 파악한 후, 의사결정을 위해 추가적인 정보가 얼마나 필요한지 추정합니다. 마지막으로 적절한 측정 수단을 사용하여 정보를 얻고 결정을 내리는 것입니다. 

  • Define a decision problem and relevant uncertainties
    • Ask first : 'What is your dilemma?' instead of 'How do we measure X?'
  • Determine what you know now
    • Describe your uncertainty in terms of ranges and probs.
    • Assess the risk involved in the decision
  • Compute the value of additional information
    • How much of risk can it reduce?
  • Apply the relevant measurement instrument(s) to high-value measurements
    • Until the economically justifiable amount of uncertain is removed
  • Make a decision and act on it
    • Track results and return to step 1

이렇게 나열해보면 '코끼리 냉장고 넣기'처럼 자명해 보이지만, 대부분의 경우 어떤 문제를 풀기 위해 어떤 측정값이 얼마나 많이 필요한지 생각하지 않고 무작정 측정에 들어가는 경우가 많기에, 이 책의 조언은 유의미합니다.

이 책에서는 이밖에도 통계에 관한 여러 팁을 제공합니다. 예컨데, Rule of Five는 모집단의 크기에 관계없이 5개의 측정값만 있다면 집단의 중간값(median)의 범위를 (측정값의 최소 및 최대값 사이) 93%의 정확도로 예측할 수 있다는 것입니다. 또한 모집단 전체 크기를 측정할 수 있는 Catch-recatch, 모집단내 측정 부분집합의 비율을 측정하는 Population proportion sampling등의 방법도 소개됩니다. 

측정되지 않는 것은 개선할 수 없다는 데밍의 말을 인용하지 않더라도, 데이터에 근거한 의사결정은 비즈니스 혹은 검색, 추천 등 인공지능 시스템 설계에 핵심적인 역할을 합니다. 제가 최근에 시작한 Self-tracking역시 삶의 만족도를 일종의 Measurement Problem으로 접근하는 시도입니다. 

7주차 반성 및 계획
앞으로 주간 반성은 독립된 포스팅으로보다는 다른 포스팅에 뭍어 올리려 합니다 ;-) 이번주는 WSDM에서 돌아온 직후 월요일에 SIGIR 논문 마감으로 (전례없이) 밤을 새야했고, 그 이후는 시차 적응 및 인터뷰 준비로 시간을 보냈습니다. 주 막바지에 약간의 오점(?)을 남기기는 했지만, 전체적으로 무난히 보낸 한주였습니다. 



이번주 배우고 느낀점은 위 서평으로 대신할까 합니다.^^ 

검색의 미래 - 개인화 검색

검색공부하기 : 2011. 9. 22. 06:09   By LiFiDeA
오랜만에 검색 관련 포스팅으로, 인턴 프로젝트 및 기타 이유로 관심을 많이 갖게 된 검색 개인화에 대해 써볼까 합니다. 개인화는 2000넌대 초반부터 주로 연구되어 최근까지 굉장히 Hot한 주제였습니다. 제가 논문 검색에 자주 사용하는 DBLP 검색엔진의 결과를 보면 2000년대 후반에 굉장히 많은 연구가 이루어졌음을 알 수 있습니다. 


 
검색, 검색 개인화, 문서 추천

지난 연재에서 소개했듯이, 전통적인 검색 연구의 두 축은 질의어와 문서입니다. 즉, 주어진 질의어에 관련성이 높은 순서로 문서를 랭킹하는 것이 핵심 문제입니다. 그러다 보니 관련성은 질의어와 문서에 대해서만 정의되며, 실제로 질의어를 입력하고 결과를 사용하는 개별 사용자는 고려되지 않았습니다. 개별 사용자의 취향을 고려하기 보다는, 주어진 질의에 대해 최대한의 사용자를 만족시키는 '정답'이 존재한다고 가정하고, 이를 여러 방시으로 찾으려는 것입니다.

이에 반해 개인화된 검색은 질의어와 문서에 '사용자'를 직접 고려합니다. 기존 웹검색의 성능을 높이는 일이 어느정도 한계에 부딛히고, 검색엔진이 사용자에 대한 다양한 정보를 수집하게 되면서 '다수'를 만족시키는 랭킹보다는 사용자 각각을 만족시키는 랭킹을 찾으려고 노력하게 된 것입니다. 아래 그림에서처럼 이제 문서(D)의 관련성(R)이 질의어(Q) 뿐만 아니라 개별 사용자(U)의 관점에서도 정의되는 것입니다. 여기서 질의어라는 개념을 뺀다면 각 사용자에 대한 문서를 추천하는 Collaborative Filtering과도 많이 닮아있는 것을 보실 수 있습니다. 



개인화 검색의 이슈들

이처럼 '사용자'라는 하나의 축이 더 생기다보니, 개인화된 검색에는 많은 고려사항이 있습니다. 우선, 질의와 문서간의 매칭 뿐만 아니라 사용자와 문서의 매칭까지 고려해야 합니다. 즉, 사용자의 위치, 평소 관심 분야와 취향을 고려해 선호되지 않을 것으로 예측되는 문서는 질의어와의 관련성이 높더라도 랭킹을 낮추는 것입니다.

하지만, 잘 최적화된 기본 랭킹 대신에, 개인화된 랭킹을 적용하는 일에는 여러가지 위험성이 따르기에, 이를 고려하여 개인화의 여부 및 정도를 적절히 결정하는 것이 필요합니다. 최근에 발표된 연구중 문서의 난이도를 고려하여 검색 결과를 개인화하는 연구를 [1] 예를 들어봅시다. 평소에 어려운 문서를 읽는 사용자라도 가끔 쉬운 문서를 읽고싶을 때가 있을 텐데, 만약 검색엔진이 계속 어려운 문서만 추천한다면 오히려 사용자 만족도를 떨어뜨리는 결과를 낳을 것입니다. 

마지막으로, 검색 결과의 '정답'이 각 사용자에 따라 달라지기에, 예전처럼 검색 품질 평가에 별도의 평가자(Judge)를 고용하는 일은 더이상 의미가 없습니다. 대신 개별 사용자의 클릭 데이터가 주된 평가의 척도가 됩니다. 검색 알고리즘 평가에 관한 학회중 대표적인 TREC에서 최근에 검색 세션에서의 사용자 만족도 향상을 목표로 하는 Session Track을 시작했는데, 여기서도 평가를 위해 개별 사용자의 만족도를 반영하는 클릭 데이터가 새용됩니다. 

위에서 설명했듯 개인화된 랭킹을 만들고 평가하는 데에는 개별 사용자의 로그 데이터가 필수적입니다. 각 사용자의 관심도나 취향을 추측하고, 개인화된 결과가 더 좋은 결과를 낳는지는 사용자의 검색 기록을 통해서만 알 수 있기 때문입니다. 그래서 많은 검색엔진은 검색 기록 이외에도 브라우저 툴바 등을 통해 개인 사용자에 대한 기록을 모으고 있습니다. 또한, 모든 사용자 각각에 대해 충분한 데이터를 얻을 수 있는 것이 아니기 때문에, 사용자를 여러 속성으로 군집화하여 개인화 대신 집단에 대해 최적화된 결과를 제공하기도 합니다.  
 
마치며

검색 연구는 주어진 질의에 대해 고정된 '정답'을 내놓는 방식에서 개별 사용자를 고려한 결과를 제시하는 방향으로 바뀌고 있습니다. 여기서는 주로 문서의 랭킹을 논하였지만, 사실 문서 요약(snippet), 질의어 추천 등 검색엔진의 모든 측면이 잠재적인 개인화의 대상입니다. 앞으로는 사용자에 대해 충분히 많은 정보를 수집한 검색엔진이 사용자의 질의 없이도 관련 정보를 추천하는 일도 가능할 것입니다. (이미 구글에서 5년전에 나온 관련 논문이 있습니다.) 

p.s. 좀더 구체적인 정보를 원하시는 분들은 제가 인턴 기간중 작성한 개인화 관련 연구의 survey slide를 참고하세요. 

p.s. 사포러스 님께서 개인화된 검색에 대해 다른 견해를 다룬 책을 소개해 주셨네요.  

  • [1] K. Collins-Thompson, P. N. Bennett, R. W. White, S. de la Chica, D. Sontag. (To appear.) Personalizing Web Search Results by Reading Level. Proceedings of the Twentieth ACM International Conference on Information and Knowledge Management (CIKM 2011). Glasgow, Scotland. Oct. 2011.
 

정보검색을 위한 정보이론

검색공부하기 : 2011. 4. 3. 11:09   By LiFiDeA
최근 본 블로그 방문자들의 검색 키워드 통계를 보다가 '정보이론(Information Theory)'이 가장 높은 빈도를 차지한다는 것을 발견하였습니다. 정보이론은 많은 검색 및 기계학습 이론의 근간을 이루기는 하지만, 국내에 정보이론에 관심을 갖는 분들이 많다는 점은 뜻밖이었습니다. 혹은 정보이론에 대한 자료가 별로 없기 때문일수도 있겠다고 생각했습니다. 예전에 정보이론에 대한 글을 썼지만, 이번 기회에 다시 정보이론에 대해 정리해보기로 마음먹었습니다. 정보이론의 기본 개념 및 검색(IR) 및 기계학습 분야의 응용 몇가지를 알아봅시다.

정보이론에서 말하는 '정보'

하루에서 수십번씩 사용하는 말이 '정보'입니다. 정보이론에서 말하는 정보 역시 일종의 '앎'입니다. 하지만 정보이론의 정보는 '무지'의 반대말로 이해하는 것이 더 쉽습니다. 이런 '앎'의 개념은 '불확실성'과도 상통하는데, 어떤 대상에 대해 전혀 모를 경우 어떤 예측도 불가능하므로 가장 불확실성이 높고, 지식 수준의 높아질수록 불확실성도 낮아진다는 측면에서 그렇습니다.

정보이론의 핵심 개념인 '엔트로피(Entropy)'는 무질서도라고도 번역되는데, 어떤 앎의 불확실성을 측정하는 개념입니다. 정확한 정의는 지난번 글과  위키피디아를 참조하시고, 여기서는 '내일의 날씨'라는 정보를 예로 들어봅시다. 내일 날씨가 어떤지 전혀 감을 잡을 수 없을 경우 (맑음 50% / 흐림 50%) 엔트로피가 높고, 내일 흐릴 것이라고 거의 확실히 예측되는 경우  (맑음 10% / 흐림 90%) 엔트로피가 낮아집니다. 

정보이론이 유용한 이유

정보이론이 하나의 정보(확률분포)의 특성을 기술하는데만 쓰인다면 지금처럼 넓은 응용을 갖지는 못했을 것입니다. 정보이론의 진짜 가치는 임의의 확률분포 사이의 정량적인 비교를 가능하게 한다는 데 있습니다. 본질적으로 불확실한 대상에 대한 의사결정을 다루는 검색 및 기계학습의 여러 이론은 확률적으로 표현되는 대상간의 비교에 의존하기 때문에, 정보이론의 여러 지표(Information-theoretic Measure)가 유용한 것입니다.


그런 의미에서 저는 정보이론의 엔트로피를 '확률분포에 대한 절대값'이라고 규정하고 싶습니다. 마치 실수와 허수에 대해 각각 가감승제 연산을 통해 값을 비교할 수 있는 것처럼, 확률변수에도 다양한 연산법칙이 있습니다. 하지만, 양적인 비교를 가능케하는 절대값의 개념이 확률이론에는 없는데, 정보이론은 확률변수의 불확실성에 대한 평가 지표를 제공하는 것입니다. 이제 이들 지표에 대해 자세히 알아봅시다. 

하나의 대상에 대한 두가지 정보의 비교 : Cross Entropy & Relative Entropy

먼저, 특정 대상에 대한 여러 정보를 비교하는 경우를 알아봅시다. 확률 이론 관점에서는 Event Space가 동일한 여러 분포를 비교하는 것으로 생각할 수 있습니다. 이 경우 사용하는 지표가 Cross Entropy와 Relative Entropy(Kullback-Leibler Divergence)인데, 둘다 기준이 되는 확률분포 (P)와 다른 확률분포(Q) 사이의 차이를 측정를 측정합니다. 

지난번 글에서는 질의어와 문서를 모두 확률분포로 놓고, 질의어(P)와 가장 가까운 순서로 문서(Q)를 랭킹하는 검색 모델의 예를 들었는데, 이번에는 검색엔진의 성능을 예측(query performance prediction)하는데 사용되는 Query Clarity라는 기법의 예를 들어봅시다. 검색엔진의 성능을 '측정'하는데에는 검색 결과에 대한 사용자의 평가자료가 필요하기 때문에, 그런 데이터 없이 성능을 '예측'하는 기법이 의미를 갖습니다. 

Query Clarity는 문자 그대로 주어진 질의의 명확성을 측정하는데, 이는 명확한 질의가 (애매한 질의보다)더 좋은 성능을 낸다는 직관을 바탕으로 합니다. 그리고 질의의 명확성을 측정하는 방법으로 사용하는 것이 질의의 확률분포와 컬렉션 전체의 확률분포를 Relative Entropy를 사용해 비교하는 것입니다. 이를 수식으로 표현하면 다음과 같습니다. 



실제로 사용자의 질의는 굉장히 짧기 때문에, 질의어를 그대로 사용해 확률분포 P(w|Q)를 계산하기 보다는 질의어를 사용해 검색한 결과로 반환되는 Top-K 문서를 사용해 질의의 확률분포를 계산하게 됩니다. 좀더 자세한 사항은 논문을 참고하시기 바랍니다. 검색 성능의 예측은 그 결과에 따라 다양한 조치를 취하는 것을 가능하게 하기 때문에, 활발히 연구되는 분야입니다. 관련 분야의 Survey는 다음 논문을 참고하시기 바랍니다. 

 
각기 다른 대상에 대한 정보의 비교 : Mutual Information
 
위에서는 같은 대상에 대한 두 확률분포를 비교하는 기법을 알아보았는데, 서로 다른 대상에 대한 확률분포를 비교하는 기법이 Mutual Information입니다. Relative Entropy와는 달리 서로 다른 대상을 대상으로 하기에, Mutual Information은 두가지 확률분포의 '유사성'보다는 '독립성'을 측정하는 지표입니다.

 Mutual Information은 자연어처리에서 단어 의미 분간(disambiguation)등에 사용되기도 하지만, 여기서는 분류(classification)알고리즘의 속성 선택(feature selection)에 사용되는 경우를 알아봅시다. 속성 선택은 수많은 속성 중 가장 성능에 공헌도가 높은 속성만을 선별하는 기법으로, 기계학습 알고리즘의 성능을 높이는데 중요한 단계입니다. 

속성 선택에서 어떻게 Mutual Information을 활용할 수 있는지 알아봅시다. 분류 알고리즘을 만드는 데 가장 도움이 되는 속성은 분류 결과와 가장 유사한, 즉 dependency가 높은 속성일 겁니다. 예컨데 스팸 필터를 만드는 데 제목에 'XXX'라는 단어가 들어가는 문서가 100% 스팸이라면 굉장히 분류 작업에 유용하겠죠? 따라서, 문서 레이블의 분포 X와 속성값의 분포 Y간의 Mutual Information이 높을수록 해당 속성은 더 유용하다고 볼 수 있습니다. 


마치며

위에서 소개한 몇가지 지표는 사실 정보이론이라는 분야의 극히 일부분입니다. 검색 및 자연어처리에 자주 등장하는 기타 개념으로 Noisy Channel이 있는데, 흔히 음성언어 인식 및 기계번역이 Noisy Channel 문제로 간주되곤 합니다. 좀더 자세한 소개는 아래 적은 책들을 참고하시면 됩니다. 마지막으로 YouTube에도 엔트로피의 개념을 소개하는 비디오가 있어 소개합니다. 더 궁금하신 내용이 있으시면 답글로 남겨주세요.

참고자료
 
Foundations of Statistical NLP (book)
Information Theory, Inference, and Learning Algorithms : (book - free pdf available)
작년에 Gmail에 도입된 유용한 서비스가 Priority Inbox입니다. 작년에 구글이 Buzz 및 Wave등으로 한창 삽질(?)을 하고난 이후라서 처음에는 그 유용성에 대해 반신반의했었지만, 처음에 몇개의 Email을 Important / Not Important로 레이블링 해주고 난 후에는 거의 100% 올바른 분류를 하는 것을 확인하고 놀랐습니다.

오늘 연구실 동료의 트윗에서 Gmail Priority Inbox의 알고리즘을 소개한 Technical Paper를 발견하고 읽어 보았습니다. 그동안 저처럼 궁금하셨을 분들께 간단히 소개합니다. 평소 기계학습이 '주어진 알고리즘을 갖다 쓰는 것'이라고 여겼던 분들이라면, 단순한 Regression Model을 주어진 Learning Problem에 적용하는 과정에도 굉장히 많은 고려가 필요함을 알 수 있습니다. 

The Learning Problem

잘 아시겠지만, Regression은 주어진 Feature를 가지고 실수값을 갖는 Label을 예측하는 기법입니다. 우선 메일의 중요도를 나타내는 Label을 살펴보면, 메일 도착 후 일정시간 이내에 사용자가 특정한 액션(open, reply 등)을 취하는 경우를 중요한 메일로, 사용자가 보고도 아무 조치도 취하지 않은 경우 중요하지 않은 것으로 간주하는 것을 알 수 있습니다. 즉, 사용자의 Explicit Label과 함께 Implicit Action을 모두 학습에 활요하는 것입니다. 

또한 아래와 같은 다양한 Feature가 학습에 활용됩니다. 이메일의 기본 Feature에 Label까지 활용하는군요. 
Social features are based on the degree of interaction between sender and recipient, e.g. the percentage of a sender’s mail that is read by the recipient. 
Content features attempt to identify headers and recent terms that are highly correlated with the recipient acting (or not) on the mail, e.g. the presence of a recent term in the subject. 
Thread features note the user’s interaction with the thread so far, e.g. if a user began a thread. 
Label features examine the labels that the user applies to mail using filters

다음은 실제 학습 알고리즘입니다. 기본적으로는 Logistic Regression을 사용하지만, 모든 유저의 데이터에서 학습한 내용과 개별 유저로부터의 학습 내용을 모두 학습에 사용하기 위하여 Transfer Learning을 사용합니다. Transfer Learning은 모델을 학습한 도메인과 적용할 도메인이 다를 경우 사용하는 기법입니다. 다음 다이어그램은 이러한 학습 과정을 시각화합니다.


알고리즘에서 또 하나 이채로운 점은, 각 메일에 대한 Important / Not Important의 결정을 내리는 기준(threshold)을 사용자의 Explicit Label을 사용해 개인화한다는 점입니다. 각 사용자 별로 중요한 메일의 비율이 다르기 때문에, 이는 자동화하기 힘든 부분입니다.

Production

개발된 알고리즘을 수백만의 사용자가 매일 사용하는 시스템에 적용하는 것은 또다른 문제입니다. 논문에서는 구글 컴퓨팅 클러스터의 기본 데이터 구조인 BigTable이 어떻게 활용되는지 자세히 밝히고 있습니다. 사용자별 학습 알고리즘 수행의 부하를 각 Core에 나누는 과정도 흥미롭습니다.

Result

논문에서는 위에서 설명한 Global Model과 Per-user Model의 조합, 그리고 사용자별 중요도 기준의 개인화를 통해서 에러율을 상당부분 낮출 수 있었다는 결론을 내고 있습니다. 또한 Industry Paper답게 Priority Inbox의 도입이 Gmail사용자들의 메일 사용을 어떻게 효율적으로 만들었는지를 다음과 같이 밝히고 있습니다. 

The ultimate goal is to help Gmail users. We analyzed the time Google employees spent on email with and without Priority Inbox. Averaging over Googlers that receive similar volumes of mail, Priority Inbox users (approx. 2000 users) spent 6% less time reading mail overall, and 13% less time reading unimportant mail. They are also more confident to bulk archive or delete email.

마치며

겨우 4장짜리 논문이지만, 기계학습 알고리즘을 실제 문제에 적용하는 과정에서 발생하는 수많은 문제를 간결하면서도 명쾌하게 기록하고 있습니다. 한때 기계학습이 알고리즘의 인풋과 아웃풋만 알면 블랙박스처럼 활요할 수 있을 것이라고 생각한 때도 있었지만, 위 논문만 읽어 보아도 학습 기법의 실전 활용에는 상당한 지식이 필요함을 알 수 있습니다. 기타 재미있는 디테일이 많으니 관심있으신 분들꼐 일독을 권합니다.

목차 : 
정보 검색 (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)이 각광받고 있습니다. 이런 연구에 널리 사용되는 데이터셋을 소개한 논문에는 검색을 위해 얼마나 다양한 속성이 사용될 수 있는지가 잘 드러나 있습니다. 

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

오늘은 , 최근의 연구 동향을 문서 모델(document model), 질의어 모델(query model), 검색 모델(retrieval model), 그리고 평가(evaluation)의 순으로 정리해보려 합니다. 전체를 아우르는 큰 그림은 지난 포스트에 소개한 바가 있습니다. 

(1) Document Modeling
문서 모델링은 문서에서 검색에 도움이 되는 속성(feature)을 뽑아 인덱스를 생성하는 단계입니다. 잘 알려진 것으로는 단어의 빈도에 근거하여 관련성(topicality)을 평가하는 전통적인 속성(TF-IDF, BM25), 그리고 웹 문서의 연결 관계(link structure)를 분석하여 가장 권위있는 문서를 뽑아주는 속성(PageRankHITS) 등이 있습니다. 

전통적으로 가장 많은 연구가 집중되어온 영역이지만 최근들어 새로운 속성(feature)을 찾는 일은 조금씩 한계에 부딛히고 있는 듯 합니다. 하지만 Anchor Text나 태그 등 부가적인 메타데이터를 활용하거나, 클러스터링 등을 통해 발견한 인접 문서와의 유사성을 이용하여 문서를 좀더 정확하게 평가하려는 노력은 계속되고 있습니다. 

(2) Query Analysis
다음은 사용자가 입력한 질의를 분석하는 단계입니다. 여기에는 질의어 확장(expansion), 교체(substitution), 어근 분석(stemming), 철자 교정(spell correction), 분리(segmentation), 가중치 부여(weighting) 등 질의어 자체를 개선 하거나 좀더 세분화된 처리를 위해 질의어의 유형을 분류(classification)하는 작업이 포함됩니다. 사용자의 질의는 (특히 웹 검색) 보통 짧은데다가 애매하거나 오류를 포함한 경우가 많아, 잘의어 분석만 잘 해도 검색 성능을 획기적으로 올릴 수 있습니다.

특히 기존 연구 (e.g. 문서 모델링)가 한계에 부딛히고, 대량으로 주어지는 Query Log의 활용이 새로운 연구 토픽으로 각광받으면서 최근 검색 연구에서 가장 'hot'한 분야라고 할 수 있습니다. 최근 구글과 야후 등이 경쟁하듯 내놓고 있는 개인화 검색 역시, 사용자 프로필에서 추출한 단어를 검색어로 사용한다는 측면에서 주로 이쪽에 분류됩니다. 검색 개인화에 대해서는 좀더 자세히 다루겠습니다.

(3) Retrieval Model
검색 모델은 문서 모델링(1)에서 추출한 속성과 질의어 모델링(2)에서 분석된 질의어를 기반으로 각 문서의 실제 점수를 계산하는 공식(ranking formula)을 가리킵니다. 전통적인 의미의 검색 모델은 대부분 질의어와 문서의 유의성(textual similarity)에 기반한 것이 많았는데, Vector Space Model, Probabilistic Model (BM25), Language Model등이 모두 여기에 포함됩니다. 

하지만 2003년 이후, 검색의 기준이 되는 속성에 문서의 최신성, 품질 등 많은 요소가 추가되고, 검색 품질에 대한 평가를 자동화할 수 있는 클릭 로그(click-through log)의 사용이 보편화되면서 머신러닝 기법을 검색에 도입하는 연구가 대세를 이루고 있으며 이를 통칭하여 랭킹 학습(Rank-learning / Learning to Rank) 기법이라고 합니다. RankNet, RankSVM, RankBoost등이 이에 포함됩니다.

이와 함께 최근 눈에 띄는 경향은 검색 결과의 다양성(diversity)을 높이려는 시도입니다. 과거에는 문서 각각을 평가하여 좋은 문서가 Top에 있으면 무조건 좋은 것으로 간주하였지만, 비슷한 혹은 중복된 문서를 여러 개 보여주는 것은 검색 품질에 악영향을 끼치기 때문에, 이를 검색 모델 및 평가에 반영하려는 것입니다. 

(4) Evaluation
검색은 '평가의 과학'이라는 말이 있을 정도로 검색 결과를 정확하고 효율적으로 평가하는 일은 검색 연구의 주된 축이었습니다. 전통적인 Precision / Recall / Mean Average Precision 이외에도 검색 결과를 정확히 반영하는 평가 지표(metric)을 만드려는 노력이 계속되어 문서의 품질을 평가 결과에 좀더 정확히 반영할 수 있는 NDCG등 새로운 방법이 각광받게 되었습니다. 

또한 검색 결과의 평가를 위해서는 문서 각각의 적합성을 사람이 직접 평가해야 되기 때문에, 이 과정에서 필요한 문서의 숫자를 줄이려는 연구도 있었습니다. 또한 단순히 Top 10에 몇개의 relevant한 문서가 있다는 식이 아니라, 실제 사용자의 작업 효율을 높여주는 정도를 평가 척도에 반영하려는 노력도 있어 왔습니다.

기계적인 검색에서 인간적인
 검색으로
몇 단어를 던져주면 딱 맞는 문서를 찾아 주는 마술같은 검색 엔진의 이면에는 이렇게 복잡다단한 노력이 숨어 있습니다. 위에서 여러가지 흐름을 소개했지만, 요약하자면 점차 '사용자' 중심의 연구를 하게 되었다고 볼 수 있을 것 같습니다. 단순히 고정한 함수를 계산하여 가장 높은 점수순으로 문서를 출력하는 것이 아니라, 사용자에게 실제로 유의미한 결과를 제공할 수 있는 검색 모델을 만들고, 사용자 질의를 분석 및 분류하고, 클릭 데이터를 수집하여 평가하고, 이를 바탕으로 검색 결과를 개선하는 겁니다. 물론 검색 개인화 역시 같은 맥락으로 볼 수 있습니다.

 다음회부터는 각 부문별 동향 소개가 이어집니다.  좀더 설명이 필요한 부분이 있다면 지적 바랍니다. ^^
작년 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

웹의 발전은 정보검색(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)처럼 편리하게 사용하도록 도와줍니다. 좀더 익숙해지면 이곳을 통해 소개하도록 하겠습니다.

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

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

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

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

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

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

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

Reference