#8. 확률 모델(Probabilistic Model)

# 여담

앞에서는 벡터 모델을 주로 설명했었다. 사실 단순히 생각해보면 TF-IDF 모델을 사용하는 벡터 모델이 훨씬 좋을 것 같지만 확률 모델도 굉장히 성능이 좋은 BM25 (Best Match 25, Okapi)라는 모델이 있다. 실제 IR 서비스를 제공하는 ElasticSearch에도 5.0부터 BM25 알고리즘을 기본으로 채택해서 사용중. 재밌는 건 벡터 모델과 달리 수학적으로 전부 증명하고 모델을 사용하기 시작한게 아니라 다른 딥러닝 모델 성능 실험하는 것처럼

'어 이유는 모르겠지만 성능 엄청 좋은데? (=블랙박스)' 하고 쓰면서 조금씩 성능을 증명하고 있는 모델.

자, 여담은 여기까지 하고 이제 BM25이 어떻게 만들어졌는지 알기 위해서 확률 모델을 공부해보자.

* 아래 수식에서 BM25 (앞부분) * (뒷부분) 에서 앞부분에 확률 검색모델의 개념(IDF) 요소가 들어가있고, 뒤에 TF요소는 성능이 좋아서 넣은 거긴 한데, 왜 이 수식이 성립하는지 수학적으로 증명되지는 않았다. 아무튼 성능은 좋다.

수식이 복잡하지만, 신기하게도 동작하는 과정을 보면 tf, log(tf)와 비슷하게 동작한다.

# 설명하기전에

확률검색모델의 가중치 수식에는 '확률' 정보가 보이지 않습니다.

아래의 설명은 확률검색모델이 어떻게 확률정보가 보이지 않는 수식을 사용할 수 있는가? 어떻게 그 수식이 유도되었는가? 를 설명합니다. 수식을 외울려고하지말고, 이게 무슨 과정인지 이해하도록 합시다. (문제는 완성된 간단한 수식을 외워서 풀면 됩니다.)

# 확률 검색 모델

사용자의 질의에 대한 적합확률의 역순으로 문서를 순위화하는 아이디어를 사용한 검색모델.

[질의문(Q)에 대해서 나온 문서 D가 적합문서일 확률]

질의문(Q)에 대해 1. 해당 문서(D)가 나온다음 2. 그 문서가 적합문서(R, rel) 인 확률이라는 의미로

$P (확 률 | 조 건)$ $=>$ $P (R | D)$ 또는 $P (R | Q, D)$ 라고 적는다.

이 2개의 값을 사용하면 확률 모델을 만들 수 있지 않을까? 에서 출발한 아이디어.

확률 모델의 기본 아이디어는 어떠한 문서 D를 뽑았을 때 적합문서일 확률(rel), 부적합 문서일 확률(non-rel)을 각각 구해서 $P (r e l ∣ X) > P (n o n r e l ∣ X)$ $P (r e l ∣ X) > P (n o n r e l ∣ X)$

$P (r e l ∣ X) > P (n o n r e l ∣ X)$ $P (r e l ∣ X) > P (n o n r e l ∣ X)$

$P (r e l ∣ X) > P (n o n r e l ∣ X)$

1. 조건부확률 공식 유도하기

사건 A, B와 그 사건이 일어날 확률 $P (A) P (B)$ 가 있다고 가정하자. (단, $P (B) > 0$ )

사건 B가 일어 난 후 사건 A가 일어날 확률을 $P (A | B)$ 라고 쓰자 그러면

$P (A | B) = \frac{A, B 가 동 시 에 일 어 날 확 률}{B 가 일 어 날 확 률}$ 이렇게 나타낼 수 있고 이를 수식으로

$P (A | B) = \frac{P (A \cap B)}{P (B)}$ 라고 적을 수 있다.

마찬가지로 거꾸로 뒤집어 A가 일어난 후 B가 일어날 확률은

$P (B | A) = \frac{P (A \cap B)}{P (A)}$ 이다.

이 두 식을 이용하면

$P (A \cap B)$ = $P (A | B) * P (B)$ = $P (B | A) * P (A)$ 라는 식을 만들 수 있다.

두 사건 A,B이 일어날 확률이 서로에게 전혀 영향끼치지않는, 독립사건이라고 한다면

$P (A \cap B)$ = $P (A) * P (B)$ 이다.

이는 두 사건이 아니라 A,B,C,D... 여러개가 있어도 마찬가지이다.

$P (A \cap B \cap C \cap D)$ = $P (A) * P (B) * P (C) * P (D)$

3. 분할

사건 A를 여러개로 분할 할 수 있습니다.

사건 A를 $A_{1}, A_{2} . . . A_{n}$ 개로 분할한다면 이런느낌. (당연히 서로 겹치지않게, 각각의 사건이 서로소를 유지하면서)

4. 베이즈 정리 (Bayes' Law)

베이즈 정리는 $P (B | A) = \frac{P (A \cap B)}{P (A)}$ 에서 분모 $P (A)$ 값을 유도하는 과정에서 출발한다.

$P (A \cap B)$ = $P (A) * P (B)$

이 식에서 사건 B를 $B_{1}, B_{2} . . . B_{n}$ 개로 분할 한다면 다음과 같이 적을 수 있다.

$A =$ $(A \cap B_{1})$ $\cup$ $(A \cap B_{2})$ $\dots \cup$ $(A \cap B_{n})$

마찬가지로 여기에 각각의 확률을 구하면 아래와 같은 식이 만들어지고

$P (A) =$ $P (A \cap B_{1})$ $\cup$ $P (A \cap B_{2})$ $\dots \cup$ $P (A \cap B_{n})$

사건 A가 일어 났을 때, B의 분할 중 하나인 B_j라는 사건이 같이 일어날 확률은 다음과 같다.

이 식의 핵심은, 사건 $A$ 가 일어났을 때 $B_{j}$ 가 일어날 확률 ( $P (B_{j} | A)$ )을 거꾸로 뒤집은

$B$ 가 일어났을 때의 확률들 ($P(A|B_1), P(A|B_2) \dots P(A|B_k) 들$)로 나타낼 수 있다는 것에 있다.

5. 베이즈 정리의 응용

베이즈 정리는 사전정보, 즉 '데이터 분석을 통해 어떠한 사건이 일어날 확률 값을 이미 알고 있을 때' 사용되며 이를 이용하여 [어떠한 사건 A 발생 이후 일어날 확률] $P (θ | A)$ 를 구할 때 사용된다.

예를 들어 [내일 하루 주식이 오를 확률]을 $θ$ 라고 가정하자 ( $θ$ 는 0.0~1.0 사이값)

빅데이터 분석을 통해 [주식이 오를 확률] $θ$ 가 0.4일 확률이 50%, 0.5일 확률이 50%임을 찾아냈다면

$P (θ = 0.4)$ = 0.5 $P (θ = 0.6)$ = 0.5 으로 적을 수 있다.

여기에서 주가가 3일 연속으로 오를 확률을 A라고 가정해보자.

3일 연속으로 올랐으니 A는 [내일 하루 주식이 오를 확률]을 3번 곱하면 된다. $P (A)$ = $θ^{3}$

위에서 빅데이터 분석을 통해 [주가가 오를 확률 $θ$ ]가 0.6이 될 확률이 50%임을 알고있으니

사건 A가 발생 한 후, [주가가 오를 확률 $θ$ ]가 0.6이 될 확률은 다음과 같이 구할 수 있다.

위에서 유도한 식을 그대로 적은 것 뿐이다. A= 0^3 (세타 세제곱)

즉 베이즈 정리는 가지고 있는 확률 정보를 응용해서 새로운 정보를 도출해내는 공식이라고 이해하면 된다.

아래 적합문서 확률에 베이즈 공식을 적용한 예

다만, 베이즈 정리를 이용하여 확률을 구하려면

질의에 대한 모든 적합 문서(R)에 대한 확률 데이터가 있어야 하고

적합문서일 확률(R), 문서가 검색될 확률(D) 이 서로 독립적인 확률이라고 가정해야한다.

<궁금한 친구를 위한 추가 설명 링크>

독립적인 확률은 가정한다 쳐도 모든 적합문서에 대한 정보는 어떻게 구하죠?

사람이 수작업으로 만든다.

현재의 검색시스템들은 자동 적합성 피드백을 사용하기도 하는데 과정은 생각보다 복잡하니 대충 알아보고 넘어가자. #10 글에 적합성피드백에 대한 내용을 추가로 설명하겠다.

자동 적합성 피드백은 효과가 없을 것 같지만, 적용 했을 때 결과가 더 좋아진다는 논문이 많아서 사용된다.

P (RD)는 특정 질의(Q)에 대해 나온 문서가 나올 확률을 의미한다.

다만 정보검색에서는 '몇번째 순위까지 위 식을 만족하는 문서인가?'를 찾을 필요가 없다.

그냥 점수를 매길 수 있는 가중치 공식만 있다면, 그 공식을 이용해서 상위문서 순위만 정하면 된다.

다시 말해서 위 공식에서 나온 $\frac{P (N R)}{P (R)}$ 은 굳이 사용하지 않아도 상관없다. (이 문서의 적합문서 확률, 부적합 문서 확률을 비교해서 적합확률이 높은 경계값을 찾을 필요가 없다는 말이다.)

결국 $\frac{P (D | R)}{P (D | N R)}$ 이 큰 값이 정확률 순위가 높다는 말이니까.

그래서 확률 검색모델의 가중치(정확도)는 $\frac{P (D | R)}{P (D | N R)}$ 만 사용한다.

# 확률 검색모델의 모형

벡터공간 모델처럼, 확률 검색모델에서 용어의 적합여부는 여러가지 방법으로 계산 할 수 있다.

하지만 이 글에서는 간단하게 이진검색모델 (BIM)만 사용해보겠다.

이는 이름 그대로 용어의 출현 여부를 이진으로 구분, 즉 있다(1) 없다(0) 사용하고 문서 내 용어들의 확률은 서로 관련없는 독립적(Independence)인 확률이라고 가정한다. (베이즈 공식을 사용하기 위함)

단어들이 독립적이지 않는데 어떻게 이 모델이 동작하는지는 아직 정확하게 밝혀내지 않았답니다.. 그냥 써보니 성능이 좋길래 그렇다 치고 쓰는중

# 직접 구해보자

이를 수식으로 예쁘게 만들면 아래와 같다.

그냥 위에 식을 반으로 나눠 product로 계산하기 편하게 적은 것 뿐이다.

제일 아래 수식은 {car, Lincoln ..} 이런 용어를 {1,2,3..} 으로 일반항으로 바꾸었을 때 나오는 수식.

참고로 마지막에 $P_{i}$ 는 [i번째 용어가 적합문서에서 나올 확률], $S_{i}$ 는 [i번째 용어가 부적합 문서에서 나올 확률]을 의미한다.

계산하기 편한 공식을 만드는 유도과정 (지져스..)

이 그림에서는 마지막 우측항이 '상수' 라서 버려도 상관없다는 것을 증명하는 내용.

수식을 유사한 값으로 바꿔 더 계산하기 편하게 변경. log를 사용하면 곱셈이 덧셈연산으로 바뀝니다. 이렇게 구한값을 RSV(검색 상태 값, 가중치)라고 부름

질의 Q에 대한 계산은 필요없다는 설명. 위에서 구한 RSV를 계산하는 방법

# 책 던지기 전에 예제부터 봅시다.

각 용어의 적합문서집합, 부적합문서집합에서 출현 정보가 있다면 계산이 엄청 간단해진다.

* 적합문서인데 (Relevant) 질의 내용(부산) 이 없는 문서도 있다는걸 유의하자.

적합문서 집합 내에서 '부산'의 DF = 2, 부적합이면 전체(1000) - 2%

1. 출현 정보가 주어진다면 (↑그림)

부산이 적합문서에 있을 확률 $= \frac{부 산 이 출 현 한 적 합 문 서}{전 체 적 합 문 서}$ , $P_{부} = \frac{r_{부}}{R}$

부산이 부적합문서에 있을 확률은 [전체 - 적합문서 개수]로 구할 수 있으므로

$= \frac{(부 산 이 출 현 한 모 든 문 서) - (부 산 이 출 현 한 적 합 문 서)}{(전 체 문 서 수) - (적 합 문 서 수)}$ , 즉 아래 그림과 같다.

2. 만약 출현정보가 없다면

$P_{i} = \frac{1}{2}$ , $S_{i} = \frac{n_{i}}{N}$ 로 가정하고 구하면 된다.

$P_{부} = \frac{1}{2}$ , $S_{부} = \frac{n_{부}}{N}$ 으로 계산하면 된다.

3. 요약해서, 특정단어 i에 대해서

${r_{i}, n_{i}, R, N}$ 이 주어지면 적합확률( $P_{i}$ ), 부적합확률( $S_{i}$ )을 구할 수 있다

$r_{i}$ = 적합문서에서 i가 출현한 문서의 수 (* i가 출현한 문서의 개수이다. 단어의 개수가 아니다.)

$n_{i}$ = 전체문서에서 i가 출현한 문서의 수

$R$ = 적합 문서의 개수

$N$ = 전체 문서의 개수

4. 실제 모델에서 사용하는 수식으로 적용한다면

유도과정이 복잡하지, 계산은 어렵지 않다. 아래 문제에도 나오니 한번 보고 가자.

- log를 이용해서 계산하기 편한 식으로 (유사값으로) 변경합니다. 로그는 곱셈연산을 덧셈으로 바꿔줍니다.

- log 0은 계산이 불가능하므로 분자, 분모에 0.5씩 더해줍니다.

이 공식을 그대로 적용해서 표를 그려보면 아래와 같습니다.

#BM25(Best Match 25)

위의 BIM(이진모델)의 최종 식의 유도과정을 보면 알겠지만, 문서의 출현횟수와 길이만을 이용해서 구했습니다.

즉 질의(Q), 즉 TF요소가 바뀌더라도 가중치에 영향을 주지 못합니다.

그래서 TF와 문서의 길이를 추가로 반영한게 BM25 모델이다.

그런데 문서(D)의 TF와 질의문(Q)의 TF는 어떻게 구했을까!?

어떻게 구했을까? 과연 어떤 수학천재가 유도과정을 통해 증명했을까!?

정답은 모른다. 그냥 가설을 세우고 느낌 좋은 값들 찍어넣었더니 성능이 좋아서 쓰고있다. 진짜로.

TF와 Length 값을 어떻게 찍어서 넣었을까요?

상수 b의 값이 0이라고 생각했을 때

상수 k1, k2값을 적절히 조정하면 TF값에 따라 그래프가 linear (선형, 1:1), sub-linear(로그 그래프) 처럼 값이 매겨진다. 즉 벡터공간모델에서 사용했던 1+log tf 와 유사한 기능을 할 것이라고 추측해서 사용하니, 실제로 성능이 좋다고 한다. 물론 수학적으로 완벽하게 증명되지는 않았다.