정보검색을 위한 정보이론

검색공부하기 : 2011.04.03 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)
신고

티스토리 툴바