2.1. 검색 모델
검색 모델을 설명하기 전에 먼저 알아야 할 용어들을 정리 하였습니다.
1). “용어 빈도수”(Term Frequency 또는 \(TF\) ) : “특정한 하나의 문서 내” 에서 출현한 “특정한 용어의 출현 횟수” 입니다.
2). “컬렉션 빈도수”(Collection Frequency 또는 \(CF\) ) : “문서 집합 전체” 에서 출현한 “특정한 용어의 출현 횟수” 입니다.
3). “문헌 빈도수”(Document Frequency 또는 \(DF\) ) : “특정한 용어” 가 출현 한 “문서의 개수” 입니다.
4). “역문헌 빈도수”(Inverse Document Frequency 또는 \(IDF\) ) : 문서집합의 총 문서 개수 / 문헌 빈도수 한 값입니다.
5). “문서 길이”(Document Length) : “특정한 하나의 문서”의 총 길이 입니다.
6). 문서 \(D\)에서 용어 \(t\) 의 가중치는 \(w( t , D ) = \frac{tf( t , D )idf( t , D )} {length( D )}\) 라고 표현합니다.
7). “질의-문서 유사도”(Query-Document Similarity) : 질의와 해당 문서가 얼마나 유사한지 수식화 한 값입니다.
8). 질의 \(Q\)와 문서 \(D\)의 유사도는 \(sim( Q , D ) = \sum_{i=1}^{n}{ w( q_i , D ) }\) 라고 표현합니다.
( \(Q = \{ q_1, \ldots, q_n \}\) 이라 가정합니다. )
“검색 모델”(Retrieval Models)은 역파일 색인에서 검색 모듈이 사용자의 질의를 받아 검색을 하고
결과(관련 문서 리스트)를 도출하는 과정을 구체화 한 것입니다.
검색 모델에는 주로 4가지 개념의 모델을 사용합니다.
1). “불리언 모델”(Boolean Model) : 질의를 용어와 불리언 연산자(AND , OR , NOT)를 사용하여 표현 한 것입니다.
각 용어에 대응되는 문서집합을 동일하게 불리언 연산하여 결과집합에 포함된 문서들을 보여줍니다.
( 구글도 불리언 검색 모델입니다. )
2). “벡터 공간 모델”(Vector Space Model) :
질의 속 각각의 용어를 축에 대응시켜 얻어지는 벡터공간을 사용한 모델입니다.
각 용어는 “독립”적 이기 때문에, 수학적으로 각각의 용어를 축으로 대응하여 사용할 수 있을 것입니다.
질의와 문서 둘 다 벡터공간을 생성하여 둘의 유사도를 계산하여 유사도 내림차순으로 문서들을 보여줍니다.
3). “확률 모델”(Probabilistic Model) : 확률이론(Probability Theory)에 기반하여 적합도를 계산한 모델입니다.
4). “언어 모델”(Language Model) : 용어 별로 불순도와 정보량 가중치를 부여하여 계산한 모델입니다.
2.2. 벡터 공간 모델
벡터 공간 모델에서 질의-문서 유사도로 “코사인 유사도”(Cosine Similarity)를 사용합니다.
질의 벡터와 문서 벡터의 사이각 코사인을 유사도로 보고, 1일수록 유사도가 높고 0일수록 유사도가 낮은 방식입니다.
\(sim( Q , D ) = \frac{Q · D} {||Q||||D||} =\frac{ \sum_{i=1}^{n} { w( q_i , d_i ) } } { \sqrt{ \sum_{i=1}^{n}{ q_i^2 } } \sqrt{ \sum_{i=1}^{n}{ d_i^2 } } } \)
코사인 유사도는 길이에 대해서 정규화(Length Normalization) 된 데이터를 다루기 때문에
단순 크기 비교보다 용어 비율을 비교 하는 방식 입니다.
벡터의 성분을 표현하는 방법도 다양할 수 있는데, 다음은 대표적인 4가지를 나열한 것입니다.
1). 이진(Binary) 벡터 표현 : 용어의 출현 여부만을 고려하여 출현 용어가 있으면 1, 없으면 0으로 이루어진
벡터 표현법 입니다.
2). \(TF\) 벡터 표현 : \(TF\) (raw \(TF\)) 만을 1배수 그대로 사용하여 문서 내 출현 용어의 빈도수로 이루어진
벡터 표현법입니다.
3). \(IDF\) 벡터 표현 : \(IDF\)를 사용하여 모든 문서에서 용어가 출현한 문서 수를 나눈 값으로 이루어진
벡터 표현법입니다.
4). \(TF-IDF\) 벡터 표현 : \(TF\)와 \(IDF\)를 섞어서 각자 다른 가중치로 사용하여 이루어진 벡터 표현법입니다.
\(TF-IDF\)에서는 \(TF\) , \(IDF\) , 정규화 세 가지 방법을 각자 다른 가중치로 적용가능하고,
\(TF\)는 그대로 사용하는 raw \(TF\) , \(log\)를 씌워서 \(log(TF)\)를 쓰거나 미적용하는 방법을,
\(IDF\)역시 raw\(IDF\)를 그대로 쓰거나 \(log(IDF)\)를 쓰거나, 미적용하는 방법을,
정규화도 미적용 또는, 코사인 정규화, 피봇 기반 정규화들이 사용됩니다.
질의/문서 벡터 성분 표현 중에 “SMART 표기법”(SMART Notation)을 사용하여
어떤 가중치를 사용했는지 한 번에 알 수 있습니다.
“SMART 표기법” 은 다음과 같습니다.
\(TF\) 는 “n”(natural) : \(tf( t , d )\) ,
“l”(logarithm) : \(1 + log( tf( t , d ) )\) ,
“d”(double) : \(1 + log( 1 + log( tf( t , d ) ) )\) ,
“a”(augmented) : \(0.5 + \frac{ 0.5 * tf( t , d ) } {max_t'( tf( t’ , d ) ) }\) ,
“b”(Boolean) : \(tf( t , d ) > 0 => 1 , tf( t , d ) ≤ 0 => 0 \)
\(DF\) 는 “n”(no) : \(1\) ,
“t”(idf) : \(log( \frac{N} {df( t )} )\)
\(Normalization\) 는 “n”(none) : \(1\) ,
“c”(cosine) : \(\frac{1} { \sqrt{ \sum_{i=1}^{n} { w_i^2 } } }\) ,
“p”(pivoted) : \(\frac{1} { ( 1 – s ) + \frac{ s * length} { avg( length ) } }\)
일 때, 문서벡터의 \(TF\) 가중치 , \(DF\) 가중치 , 정규화 가중치 + “.” +
질의벡터의 \(TF\) 가중치 , \(DF\) 가중치 , 정규화 가중치로 나타냅니다.
(위에서 다룬 \(TF\) 벡터 표현은 SMART 표기법으로 nnc.nnc , 이진 벡터 표현은 bnc.bnc 입니다.)
코사인 유사도 이외에도 질의-문서 유사도로 용어 가중치(\(\frac{tf * idf} {length}\))를 사용하여 나타내는 방법도 있습니다.
질의 \(Q\)와 문서 \(D\)의 유사도를 측정하기 위해 두 용어집합의 교집합의 원소(용어)를 \(t\) 라고 할 때, \(( t ∈ Q ∩ D )\)이고,
\(w_{t, D} = \frac{tf( t , D )idf( t )} {length( D )} , w_{t, Q} = \frac{tf( t , Q )idf( t )} {length( Q )}\) 일 때,
\(sim( Q , D ) = \sum_{i=1}^{t}{ w_{i, D} * w_{i, Q} }\) 로도 표현될 수 있습니다.
코사인 유사도의 문제점으로 꼽히는 점은 질의가 문서보다 보통 짧기 때문에,
짧은 일부 적합 문서가 실제 적합 문서보다 더 높은 유사도를 얻을 때가 있습니다.
(문서의 규모가 클 수록 방향이 극단으로 몰리지 않기 때문에
짧은 질의가 조금 더 극단에 있는 짧은 문서들을 더 선호(유사도가 더 높게)하게 됩니다.)
그래서 특정 피봇을 정하여 피봇보다 짧은 문서와 긴 문서의 간극을 맞추는
피봇 기반 문서 길이 정규화를 사용합니다.
피봇기반 문서 길이 정규화는 다음과 같습니다.
\(p := \frac{1} { ( 1 – s ) + \frac{s * length} { avg( length ) } }\)( \(s\)는 특정 가중치 상수이고, \(length\)는 문서길이( = 벡터의 길이 ), \(avg(length)\)는 평균 문서길이 입니다.)
정의역 \(length\) 와 치역 \(p\)로 함수를 그린다면, 계수가 \(\frac{s} {avg( length )}\) 이므로,
기울기가 감소한 모습을 볼 수 있습니다.
이외에도,
1). Pivoted cosine normalization (피봇 코사인 정규화)
2). Pivoted unique normalization (피봇 용어수 정규화)
3). Pivoted byte size normalization (피봇 바이트 크기 정규화)
들이 존재합니다.