[정보검색] 제7장 정보검색 모형 - 제8절 확률 검색

이 글은 정영미 교수님의 정보검색연구를 바탕으로 연세대학교 문성빈 교수님의 수업을 공부한 기록입니다.

확률 검색 (Probabilistic Retrieval)

• 확률 이론을 사용하여 질의에 대한 문헌의 적합성을 산출하는 검색 기법
• 확률 검색에서는 문헌과 질의 간 유사도를 문헌이 질의에 적합할 확률로써 계산
• 특정한 질문에 대해 각 문헌이 적합할 확률과 부적합할 확률을 산출하여 적합할 확률이 부적합할 확률보다 큰 문헌을 검색하는 것

확률 검색 모형 가정

• 각 문헌은 주어진 질의에 적합하거나 부적합하다.
• 한 문헌에 대한 적합성 판정은 다른 문헌의 적합성에 대해 아무런 영향을 미치지 않는다. (독립)

확률 검색 모형 종류

• Binary Independence Model
  • 용어의 출현 여부(1 or 0)만 활용
  • $RSV = \sum_{i=1}^n x_i \times \log \frac{p_i (1 - p_i) }{q_i (1 - q_i)}$
• Two-Poisson Independence Model
  • 용어의 출현 빈도(TF)까지 고려
  • $RSV = \sum_{i=1}^n x_i \times \log_2 \frac{u_i}{v_i}$

확률 검색 공식 유도

• 대부분의 확률 검색 모형은 적합문헌과 부적합문헌 내 색인어의 출현정보에 기초
• 문헌 $X$를 용어들의 이원벡터로 표현
  • $X = (x1, x2, \cdots, xn)$
  • $x_i$ : 용어 ti의 출현 여부를 표현 (1 or 0)
• 문헌 X는 특정한 질문에 대해 적합하거나 부적합할 두가지 경우 중 하나에 해당
• 결과적으로 검색 결정규칙 $P(rel \mid X) > P(nonrel \mid X)$을 만족시키는 문헌이 검색
• 실제로 두 확률을 직접 산출하기 어려우므로 베이즈 정리를 이용하여 검색 결정규칙을 변형
  • $\frac{P(X \mid rel)}{P(X \mid nonrel)} > \frac{P(nonrel)}{P(rel)}$
    • $P(rel \mid X)$ : 문헌 $X$가 적합할 확률
    • $P(nonrel \mid X)$ : 문헌 $X$가 부적합할 확률
    • $P(rel)$ : 적합할 사전확률
    • $P(nonrel)$ : 부적합할 사전확률
• 문헌의 적합성 값을 산출하기 위해 적합성 함수 표현
  • 결과적으로 검색되는 각 문헌에는 이에 따라 적합성 순위 부여
• $g(X) = \log \frac{P(X \mid rel)}{P(X \mid nonrel)}$
  • 문헌 $X$가 적합문헌일 때 색인어 ti가 부여될 확률 : $p_i = P(x_i = 1 \mid rel)$
  • 문헌 $X$가 적합문헌일 때 색인어 ti가 부여되지 않을 확률 : $1 - p_i$
  • 문헌 $X$가 부적합문헌일 때 색인어 ti가 부여될 확률 : $q_i = P(x_i = 1 \mid nonrel)$
  • 문헌 $X$가 부적합문헌일 때 색인어 ti가 부여되지 않을 확률 : $1 - q_i$
• $g(X) = \sum_{i=1}^n x_i \times \log \frac{ p_i (1 - p_i) }{ q_i (1 - q_i) }$

적합성 정보가 준비되어 있지 않은 경우의 초기검색 전략

• 초기검색에서 모든 질의어는 적합문헌에서 발생할 확률 $p_i$가 동일하다고 가정하고 적합성 함수를 수정하여 사용
• $g(X) = \sum_{i=1}^n x_i \times \log \frac{N - n_i}{n_i}$
  • $n_i$ : 색인어 $t_i$가 부여된 문헌의 수
  • $n_i$ 값이 작을 경우 각 검색어의 초기 가중치 $\log \frac{N-n_i}{n_i}$는 역문헌빈도 값과 유사
• 초기 가중치를 이용하여 검색한 다음 적합성 판정을 통해 각 문헌의 적합성 가중치를 다시 산출하여 검색문헌을 재순위화

예제) 문헌 A ,B, C, D에 두개의 용어 t1, t2가 아래와 같이 출현하고 p1=1/3, q1=0.2, p2=q2=0.1일 때, 문헌 C의 가중치(RSV: Retrieval Status Value)를 구하시오.

	t1	t2
A	0	0
B	0	1
C	1	0
D	1	1

$RSVc = x_1 \times \log_2 \frac{p_1/(1-p_1)}{q_1/(1-q_1)} + x_2 \times \log_2 \frac{p_2/(1-p_2)}{q_2/(1-q_2)} = 1 * \log_2 \frac{0.33/0.67}{0.2/0.8} + 0 \times \log_2 ⁡\frac{0.1/0.9}{0.1/0.9} = 1$

예제) 문헌 A ,B, C, D에 두개의 용어 t1, t2가 아래와 같이 출현하고 u1=2, v1=1, u2=2, v2=1일 때, 문헌 D의 가중치(RSV: Retrieval Status Value)를 구하시오.

	t1	t2
A	1	0
B	0	3
C	1	2
D	2	1

$RSVd = \sum_{i=1}^n x_i \times \log_2 \frac{u_i}{v_i}⁡ = x_1 \times \log_2⁡ \frac{u_1}{v_1} + x_2 \times \log_2 \frac{⁡u_2}{v_2} = 2 \times \log_2 \frac{2}{1}⁡ + 1 \times \log_2⁡ \frac{2}{1} = 3$

예제) 다음과 같이 t1, t2의 문헌출현빈도가 주어졌을 때 이진독립모형과 2-포아송독립모형을 활용하여 문헌 H의 가중치(RSV)를 구하시오.

이진독립모형

	클래스	t1	t2
A	적합문헌	1	0
B	부적합문헌	0	0
C	부적합문헌	0	0
D	적합문헌	1	0
E	적합문헌	0	1
F	부적합문헌	1	0
G	부적합문헌	0	1
H	적합문헌	1	1

$p_i$ = 용어 i의 적합문헌 클래스의 출현 문헌 수 / 적합문헌 클래스의 문헌 수
$q_i$ = 용어 i의 부적합문헌 클래스의 출현 문헌 수 / 부적합문헌 클래스의 문헌 수

$p_1 = 3 / 4$
$q_1 = 1 / 4$
$p_2 = 2 / 4$
$q_2 = 1 / 4$

$RSVh = \sum_{i=1}^n xi \times \log_2 \frac{p_i/(1-p_i)}{q_i/(1-q_i)} = x_1 \times \log_2 \frac{p_i/(1-p_1)}{q_1/(1-q_1)} + x_2 \times \frac{p_2/(1-p_2)}{q_2/(1-q_2)}$
$= 1 \times \log_2 \frac{0.75/0.25}{0.25/0.75} + 1 \times \log_2 \frac{0.5/0.5}{0.25/0.75} = 3 \log_2 ⁡3$

2-포아송독립모형

	클래스	t1	t2
A	적합문헌	3	0
B	부적합문헌	0	0
C	부적합문헌	0	0
D	적합문헌	3	0
E	적합문헌	0	2
F	부적합문헌	2	0
G	부적합문헌	0	1
H	적합문헌	2	2

$u_i$ = 용어 i의 적합문헌 클래스에서의 출현 횟수 / 적합문헌 클래스의 문헌 수
$v_i$ = 용어 i의 부적합문헌 클래스에서의 출현 횟수 / 부적합문헌 클래스의 문헌 수

$u_1 = 8 / 4 = 2$
$u_2 = 4 / 4 = 1$
$v_1 = 2 / 4 = 1 / 2$
$v_2 = 1 / 4$

$RSVh = \sum_{i=1}^n x_i \times \log_2 \frac{u_i}{v_i} = x_1 \times \log_2 \frac{u_1}{v_1} + x_2 \times \log_2⁡ \frac{u_2}{v_2} = 2 \times \log_2 \frac{2}{1/2} + 2 \times \log_2 \frac{⁡1}{1/4} = 8$

언어모형(Language Model) 기반 확률 검색

• 문헌들로부터 질의를 생성하는 과정에 초점
• 색인어로 표현된 문헌 모형으로부터 특정 질의를 생성할 확률을 산출하여 문헌들을 순위화시키는 것
• 용어 가중치에 기반한 문헌 검색을 다양한 수학적 공식에 의해 표현하는 새로운 접근방법

• 질의는 $Q$, 문헌 $d$의 모형은 $M_d$일 때 질의 생성 확률 $P(Q

  M_d)$을 산출하는 것

단일 질의어로 구성된 질의의 생성 확률

• 최우추정법에 의하여 단일 질의어 $t$로 구성된 질의에 대한 $P(Q \mid M_d)$ 산출
• $P_{MLE}(t,d) = \frac{tf(t,d)}{\left\vert d \right\vert}$
  • $tf(t,d)$ : 질의어 $t$가 문헌 $d$에서 출현한 빈도
  • $\left\vert d \right\vert$ : 문헌 $d$의 길이 = 문헌 $d$에 출현한 모든 단어의 수

복수 질의어로 구성된 질의의 생성 확률

• 질의를 구성하는 각 질의어에 대해 문헌이 적합할 확률을 모두 곱한 값
• $P(Q \mid M_d) = \prod P_{MLE}(t,d)$
  • 문헌에 출현하지 않은 질의어가 있을 경우 미출현 질의어에 대한 확률은 0이 되어 결국 질의 생성 확률이 0이 되는 문제 발생
  • 따라서 각 질의어에 대한 $P(t \mid d)$ 산출 시 단어의 문헌 내 출현빈도(TF)에 장서빈도(CF)를 추가하여 질의 생성 확률이 0이 되는 것을 방지하는 값 조정(smoothing) 방법을 사용

Jelinek-Mercer 방법

• $P(t \mid d) = \frac{ (1 - \lambda) tf(t,d) }{ \left\vert d \right\vert} + \lambda P(t \mid C)$
  • $P(t \mid C)$ : 질의어 t의 장서빈도(Cf)를 장서 내 모든 용어의 수로 나눈 값
  • $\lambda$ : 두 항의 비중을 나타내는 가중치

전통적인 확률 검색 vs. 언어모형 기반 확률 검색의 차이점

• 기준 : 검색 과정을 보는 관점
  • 전통적인 확률 검색 : 질의에 대해 문헌이 적합할 확률을 산출하여 문헌들을 순위화하는 과정
  • 언어모형 기반 확률 검색 : 문헌으로부터 질의를 생성할 확률을 산출하여 문헌들을 순위화하는 과정