정보검색 5

5.1. 언어 모델

“언어 모델”(Language Model)은 특정 언어에 속하는 임의의 표현(문장, 구, 단어)에 대한 확률 분포를
사용하는 모델입니다.

정보검색에서의 언어모델은 구체적으로 검색대상이 되는 각 문서 들의 “주제”(Topic)를 표현하기 위해,

문서 작성자가 사용하는 언어를 사용한 모델을 의미합니다.

그래서 이를 “문서모델”(Document Model)로도 표현합니다.

이 때, 질의 \(Q = {q_1, q_2, \ldots, q_k}\) 는 순서가 있는 나열이라 판단하면, 찾는 문서를 \(M\)이라 할 때,

\(P( Q | M ) = P(q_1 | M) P(q_2 | M) \cdots P(q_k | M)\) 로 정의하여 사용하고,

질의 \(Q\)를 순서가 없는 나열이라 판단하면, 찾는 문서를 \(M\)이라 할 때,

\(P( Q | M ) = \frac{|Q|!}{|q’_1|! |q’_2|! \cdots |q’_i|!} P(q’_1 | M) P(q’_2 | M) \cdots P(q’_i | M)\) \(:
(\)\(q’_i\) 는 중복된 단어를 합한 상태, \(|q’_i|\)는 단어 개수 \()\) 로 정의해서 사용합니다.

---

만약, 질의 \(Q\)가 주어 졌을 때, 문서 \(D\)에서 \(P( D | Q )\) 를 구하는 과정이라 가정한다면,

\(P( D | Q ) = \frac{P( D )P(Q | D)}{P(Q)} \approx P( Q | D )\) \(( ∵ P(Q)\)는 \(D\)에 독립된 값, \(P(D)\)는 uniform하다고 가정 \()\)

\(= \prod^{n}_{i=1}P(q_i | D)\) \(: (\) \(Q = {q_1, q_2, \ldots, q_n}\) 이고 \(q\)끼리 서로 독립 \()\)

\(\approx \prod^{n}_{i=1}P(q_i | D_{MLE})\) \(( ∵\) 모평균을 사용할 수 없어 표본평균의 \(MLE\)를 사용 \()\)

하지만, \(\prod^{n}_{i=1}P(q_i | D_{MLE})\) 식의 경우 문제점이 하나 존재 하는데,

\(P(q_i | D_{MLE}) = 0\) 인 \(q_i\)가 하나라도 있으면, 이 모델은 의미가 없기 때문입니다.

그래서 \(q_i\)을 필터링 하기에는 \(D\)를 전부 봐야 하고 이는 비효율적이기 때문에,

결국 이를 해결하기 위해 값을 보간하는 “스무딩”(Smoothing) 기법을 사용합니다.

---

스무딩 기법 중 먼저, “Jelinek – Mercer Smoothing”을 사용한 방법입니다.

\(\prod^{n}_{i=1}P(q_i | D_{MLE})\) 에서 이 값과 유사하지만,

0값을 피할 수 있는 방법으로 떠오른 것이 \(CF\)(컬렉션 빈도수)를 사용하여 해결하는 것입니다.

\(\prod^{n}_{i=1}P(q_i | D_{MLE}) \)\(\approx \prod^{n}_{i=1}((1-\lambda)P(q_i | D_{MLE}) + \lambda P(q_i | C_{MLE}) )\) \(: ( C_{MLE}\) 는 \(cf_{MLE}\) 을 의미합니다. \()\)

\(\approx \prod^{n}_{i=1}( (1-\lambda) \frac{ f_{q_i, D} }{ |D| } + \lambda \frac{ f_{q_i, C} }{ |C| } )\)\(= e^{ \log ( \prod^{n}_{i=1}( (1-\lambda) \frac{ f_{q_i, D} }{ |D| } + \lambda \frac{ f_{q_i, C} }{ |C| } ) ) }\)\(\approx \Sigma^{n}_{i=1}\log( (1-\lambda) \frac{ f_{q_i, D} }{ |D| } + \lambda \frac{ f_{q_i, C} }{ |C| } )\) 가 됩니다.

\(\lambda\)가 작을수록, 스무딩을 약하게 한다는 의미이고, \(\frac{ f_{q_i, D} }{ |D| }\) 의 비중을 둔다는 의미가 됩니다.

\(\lambda\)가 클수록, 스무딩을 강하게 한다는 의미이고, \(\frac{ f_{q_i, C} }{ |C| }\) 의 비중을 둔다는 의미가 됩니다.

---

다음은 “Dirichlet Smoothing”을 사용한 방법입니다.

Dirichlet Smoothing은 사실 \(\lambda\)를 사용하는 Jelinek – Mercer Smoothing와 유사하지만, 가중치가 조금 다릅니다.

\(\Sigma^{n}_{i=1}\log( (1-\lambda) \frac{ f_{q_i, D} }{ |D| } + \lambda \frac{ f_{q_i, C} }{ |C| } )\) 에서

\((1-\lambda)\) 를 \(\frac{ N }{ N + \mu }\) \(: (\)\(N\)은 문서 길이, \(\mu\)는 상수\()\) 로, \(\lambda\) 를 \(\frac{ \mu }{ N + \mu }\) \(: (\)\(N\)은 문서 길이 \(|D|\) 이고, \(\mu\)는 상수) 로 변환하면,
Dirichlet Smoothing이 됩니다.

즉, \(\prod^{n}_{i=1}P(q_i | D_{MLE}) \approx \prod^{n}_{i=1}( \frac{|D|}{|D| + \mu} \frac{tf(q_i, D)}{|D|} + \frac{\mu}{|D| + \mu} \frac{cf(q_i)}{|C|} ) \)\(= \prod^{n}_{i=1}\frac{f_{q_i, D} + \mu \frac{f_{q_i, C}}{|C|}}{|D| + \mu} \approx \Sigma^{n}_{i=1} \log{ \frac{f_{q_i, D} + \mu \frac{f_{q_i, C}}{|C|}}{|D| + \mu} }\) 가 됩니다.

여기서, \(\lambda = \frac{ \mu }{ |D| + \mu}\) 를 이 식의 핵심으로 보는데, 이 것을 \(\alpha_D\)로 표현하기도 합니다.

---

5.2. N-gram

언어모델 중에서 대표적으로 \(n\)-gram이 존재합니다. \(n\)-gram은 단어를 \(n\)단위로 잘라서 사용한다는 개념입니다.

먼저, \(n=1\)인 \(1\)-gram을 “Unigram Model”이라고 표현하고, 모든 글자를 한 단어 단위로 잘라서

단어의 가중치를 사용하는 방식입니다.

Unigram Model은 단어 단위의 확률을 사용하기 때문에 단어의 빈도수에 따른

문서의 맥락과 문서 전체의 느낌을 빠르게 보는 것에 특화된 모델입니다.

단어 단위는 문장의 구조 또는 단어간의 상호작용에 대해 독립적으로 판단하는 모델이고,

보다 더 큰 \(n\)-gram 에 비해 얻는 데이터도 많이 손실 되기 때문에,

빠르면서도 문서를 전체적으로 파악하는 것에 좋은 모델이 될 수 있습니다.

또한, 단어에 특화 된 모델이기에 특별한 단어들을 다룰수록 성능이 좋아지는 특징도 있습니다.

다만, Unigram은 “Bag of Word” 방식이기에 해당 특성의 단점으로 꼽히는 단어 순서에 대해서

구별하는 능력이 없어 정확도가 떨어질 수 있습니다.

---

\(n=2\)인 \(2\)-gram을 “Bigram Model”이라고 표현하고, 모든 글자를 두 단어 단위로 모아서

글자의 가중치를 사용하는 방식입니다.

정확히는 어떤 단어가 이전 단어에 대한 조건부 확률을 같이 고려하여 두 단어를 고려하는 방식이고,

두 글자 \(( Prev, Next )\) 의 가중치는 \(P( Next | Prev )\)로 구하여 사용됩니다.

Unigram 방식과 다르게 단어간의 상호작용도 신경을 쓰기 때문에, 성능도 보다 좋아졌고,

특히, 단어 순서 구별 능력을 가져서 보다 정확도를 올린 모델이라 볼 수 있습니다.

구체적으로 Bigram Model 부터는 데이터를 겹쳐서 쓰는 셈이기에 자료 효율성이 높아졌습니다.

---

\(n=3\)인 \(3\)-gram을 “Trigram Model”이라고 표현하고, 모든 글자를 세 단어 단위로 모아서

글자의 가중치를 사용하는 방식입니다.

위와 동일하게 적용되고, 세 글자 \(( Prev1, Prev2, Next )\) 의 가중치는 \(P( Next | Prev1, Prev2 )\)로 구하여 사용됩니다.

---

5.3. 모델의 비교를 통한 검색

우리가 배운 강종 모델들은 크게 “Query Language Model” 과 “Document Language Model” 로 나뉘어

두 모델을 가지고 정보검색(IR)을 구현 했었습니다.

결과로 도출된 두 모델을 “비교”(Compare) 함으로써, 두 모델의 유사도나 적합성을 평가하고,

이를 이용하는 것이 검색엔진의 성능또한 끌어올릴 수 있는 중요한 방법이라고 볼 수 있습니다.

---

실제에서 Query Language Model 과 Document Language Model을 비교하는 대표적인 방법으로

“쿨백-라이블러 발산”(Kullback-Leibler Divergence)방식을 사용합니다.

쿨백-라이블러 발산은 \(KL( P || Q ) = \Sigma_{t}P(t)\log\frac{P(t)}{Q(t)}\) \(:(\) \(P\)는 실제 확률, \(Q\)는 추정 확률 \()\) 가 됩니다.

쉽게, 해당 식은 실제 확률 \(P\)와 (\(P\)를) 추정한 확률 \(Q\)를 가지고 둘의 차이,

구체적으로 정보량을 파악하는 식이라 볼 수 있습니다.

이번에는 Query Language Model 과 Document Language Model을 비교하는 것이기 때문에,

각각의 모델을 \(Q\)와 \(D\)로 놓고 \(w_i(1 \leq i \leq n)\)를 질의 또는 문서에 언급 된 모든 단어들로 놓는다면, \(KL\)식은 다음과 같을 것입니다.

따라서, \(KL( P(Q) || P(D) ) = \Sigma^{n}_{i = 1} P( w_i | Q )\log{\frac{ P( w_i | Q ) }{ P( w_i | D ) }}\)\(= \Sigma^{n}_{i=1} ( P( w_i | Q ) \log{P( w_i | Q )} – P( w_i | Q ) \log{P( w_i | D )} )\) 가 됩니다.

---

\(KL\)식은 둘의 “차이”를 구하는 것이기 때문에, 두 모델을 비교하는 현 상황에는 차이가 적을수록 높은 점수를 부여해야 합니다.

이는 다시 말해서 반비례 또는 Negative(음수) 식으로 변환해서 사용해야 된다는 것을 의미합니다.

따라서 \(Negative\)_\(KL( P(Q) || P(D) ) = -KL ( P(Q) || P(D) ) = \)\(\Sigma^{n}_{i=1} ( P( w_i | Q ) \log{P( w_i | D )} – P( w_i | Q ) \log{P( w_i | Q )} ) \) 가 됩니다.

여기서 \(Q\)는 가능한 모든 질의 모델 (모집단)인데,

이는 현실적으로 불가능 하므로 표본집단 \(Q_{MLE}\)를 사용하여 값을 근사 하고,

\(P( w_i | Q ) \log{P( w_i | Q )}\) 는 두 모델 \((Q, D)\)의 차이를 아는데 영향을 끼치지 않기 때문에

( \(D\)에 독립적인 값이기 때문에 ) 이를 제거하고, 다음의 식을 얻을 수 있습니다.

\(\approx \Sigma^{n}_{i = 1} P(w_i | Q_{MLE})\log{ P( w_i | D ) }\) \(= \Sigma^{n}_{i = 1} \frac{tf( w_i | Q )}{ |Q| }\log{ P( w_i | D ) }\)

---