Posted 2020-11-14Updated 2020-12-17Prerequisite / Causal Inference / b.Bayesian Network

【 도대체 베이지안 네트워크가 뭐야? ②】

* Factorization of Bayes Network

그래프에 속한 RV의 결합분포(joint distribution)는 family의 모든 조건부 분포 \(P(Child|Parent)\)의 곱으로 표현 할 수 있다.
\(P(X_1,X_2,...,X_n) = \prod _iP(X_i|Parents(X_i))\)
곱 분해 법칙 (Rule of product decomposition)
확률의 연쇄법칙 \(P(a,b,c,...,z) = P(a|b,c,...,z)P(b,c,....,z)\)에서 사슬과 분기의 Rule에 따르면 부모노드가 given이면 이상은 조상노드는 전부 독립이게 되므로 성립. (충돌부는 부모노드가 아니다.)
즉, Bayes Network의 정보를 통해 joint distribution를 계산할 때 parameter의 갯수를 줄일 수 있다.

\([ 예시 ]\)

\(P(X_1,X_2,X_3,X_4,X_5,X_6,X_7,X_8)\)를 구한다고 하자.

확률의 연쇄법칙 (Chain Rule for probability) 에 의해 아무런 Bayesian Network의 정보가 없다고 하더라도 \(P(X_1,X_2,X_3,...,X_8) = P(X_1|X_2,X_3,...,X_8)P(X_2|X_3,...,X_8)P(X_3|X_4,...,X_8)...P(X_8)\) 로 Factorize 할 수 있다.
곱 분해 법칙 (Rule of product decomposition) 에 의해 Bayesian Network의 정보를 활용하면 \(P(X_1,X_2,X_3,...,X_8) = P(X_1)P(X_2)P(X_3|X_1)P(X_4|X_2)P(X_5|X_2)P(X_6|X_3,X_4)P(X_7|X_6)P(X_8|X_5,X_6)\) 로 훨씬 작은 parameter만으로 Factorize 가능하다.

* Plate Notation

\(\begin{align} P(D|\theta) &= P(X_1,...,X_N|\mu,\sigma) \\ &= \prod_i^N P(X_i|\mu,\sigma) \end{align}\)

이처럼 여러 개의 독립적인 RV들에 대해 위와 같이 Plate Notation 로 표현하는 것이 가능하다.

* 베이지안 네트워크에서의 확률추론

BN에 있는 모든 random variables ;
\(X = \{X1 ... X_N\}\)
주어진 증거 변수 (given evidence variables) ;
\(X_V =\{X_{k+1}...X_N\}\)
\(x_V\)는 evidence values
명시적으로 다루지는 않지만 관계가 있어서 감안할 필요가 있는 변수 (hidden variables) ;
\(X_H = X-X_V = \{X_1...X_k\}\)
hidden variables ; \(X_H = \{Y,Z\}\)
- \(Y\) : query variable (interested hidden variables)
- \(Z\) : uninterested hidden variables

1-1 주변확률 (Marginal Probability)

증거 변수 \(X_V\) 의 주변확률 (Marginal Probability) \(P(x_V)\) 는?

\(\begin{align} P(x_V) &=\sum_{X_H}P(X)=\sum_{X_H}P(X_H,X_V) \space\space\space\space\space\space\dots(1)\\ &= \sum_{x_1}...\sum_{x_k}P(x_1...x_k,x_V)\space\space\space\space\space\space\space\space\space\dots(2) \end{align}\)

(1). 모든 변수에 대해 full joint 된 것을 \(X_H\)로 marginalize out한 것이라고 생각한다.
(2). 각각의 Hidden variable에 대해 marginalize out한 것이라고 생각한다.

1-2. 조건부 확률 (Conditional Probability)

주어진 증거(evidence)의 집합\(x_V\)이 있을때, query variable(주어지지 않았지만 관심있는 변수) 의 조건부 확률 \(P(Y|x_V)\)은?

\(\begin{align} P(Y|X_V) &= \sum_ZP(Y,Z = z|x_V) \space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\dots(1)\\ &= \sum_Z\cfrac{P(Y,Z,x_V)}{P(x_V)} = \sum_Z\alpha P(X) \space\space\space\space\space\space\space\space\space\space\dots(2)\\ &= \sum_Z \cfrac{P(Y,Z,x_V)}{\sum_{y,z}P(Y=y, Z=z, x_V)}\space\space\space\space\space\space\space\space\space\dots(3) \end{align}\)

(1). \(Z\)를 joint로 넣어주면서 \(Z\)에 대해 marginalize out 한다.
(2). 조건부 확률의 정의를 이용해, \(x_V\)를 포함한 full joint 를 \(P(x_V)\) (Marginal Probability)로 나눈다.
(\(\cfrac{1}{P(x_V)} = \alpha\)라는 정규화 상수(normalization constant)의 곱으로 생각할수도 있다.)
(3). 분모의 주변확률은 Inference Question1처럼 full joint 를 모든 Hidden variable에 대해 marginalize 해서 구할 수 있다.

* 변수제거 알고리즘 (Variable Eliminatation Algorithm)

위와 같이 주어진 상황에서 변수제거 알고리즘으로 \(P(J=j)\)를 구해보자

* Step1

위의 준비를 통해 베이지안 네트워크 상에서 관심있는 확률의 추론을 위해서, full joint 를 구하고 uninterested hidden variable에 대해 Marginalize 한다.

\(\sum_{A,E,B,M} P(J= j,A,E,B,M)\)

* Step2

full joint 를 Bayesina Network의 정보를 이용해 곱분해 법칙으로 바꿔 쓴다.
분해한 곱의 나열순서는 topological order \(^{[*1]}\) 를 따른다.
topological order ; B, E, A, J, M

\(\sum_{B,E,A,M} P(B)P(E)P(A|B,E)P(J=j|A)P(M|A)\)

<span style="font-size: 85%;> \(^{[*1]}:\) 들어오는 화살표가 없는 노드 부터 하나씩 선택하며 지우는 것을 반복할때 결정되는 순서

* Step3

순서를 유지한 채 각 \(\sum\)가 관련없는 것을 밖으로 빼낸다.
제거할 변수의 순서는 뒤에서부터 정해진다.

\(\space\space\space\sum_B P(B)\sum_EP(E)\sum_AP(A|B,E)P(J=j|A)\sum_MP(M|A)\)

* Step4

뒤에서 부터 function notation으로 바꿔주면서 변수를 지워나간다.

\(\space\space\space\sum_B P(B)\sum_EP(E)\sum_AP(A|B,E)P(J=j|A) \underline {\sum_MP(M|A)}\)

\(=\sum_B P(B)\sum_EP(E)\sum_AP(A|B,E)P(J=j|A) \underline {\bf f_1(A)}\)
- 밑줄친 부분은 J와 \(d\)-seperate이기 때문에 고려할 필요가 없다. 즉, A의 값과 상관없이 \(f_1(A)\)는 1을 갖는다.