【 도대체 베이지안 네트워크가 뭐야? ①】
* 베이지안 네트워크(BN; Bayesian Network) 란?
- 확률 변수(RV; Random variables)들 사이의 조건부 독립 등의 관계를 보임으로써, RV의 full joint distribution등을 간결하게 표현할 수 있는 그래프 표기법 (Graphical Notation) 이다.
여기서 그래프(Graph) 란, 수학에서 차트(Chart)와 대조되어 정의된
node와edge의 집합edge가 방향이 지정되어 있으면directed, 그렇지 않으면undirected그래프의 모든
edge가directed일 때directed graphdirected edge에서, 시작되는 쪽의 노드를parent node라고 하고 반대쪽은child node라고 한다복수의 연결된
directed edge의 방향이 같은 경우 이를directed path라고 하고,directed path의 첫 번째 노드는 경로상의 모든 노드들의ancestor node이고, 반대로 나머지 노드들은 첫번째 노드의descendant node이다.directed path의 시작점과 끝점이 일치할 경우 이를cyclic이라 하고, 그렇지 않은 경우acyclic라고 한다.
베이지안 네트워크(BN) 의 Syntax
Network는Node와 이들을 연결시키는Edge로 구성된다방향성 비순환 그래프(DAG; Directed Acyclic Graph)가 되어야 한다개별
Node들은 RV인 \(X\)에 대해 \(\bf P(X | Paranets(X))\)를 의미한다.개별
Edge들은 부모가 자식에게 주는 직접적인 영향(Direct Influence) 을 의미한다.
* 먼저 확률에 대한 간단한 복습부터
- 베이지안 네트워크 라는 것은 결국 확률변수(RV) 간의 관계 를 표현한 것이다.
- 확률 이라는 것은 상대적인 빈도 이다.
독립성 (Independence)
\(P(A|B) = P(A)\)
\(\Leftrightarrow P(A,B) = P(A)P(B)\)
\(\Leftrightarrow P(B|A) = P(B)\); A와 B가 독립이면, B는 A와 독립이다.
사건B가 발생했다는 정보는 사건A가 발생할 확률에 추가적인 정보를 제공하지 못한다.
이는, 밑에 서술하는 Conditional Independence 와 대립되는 의미로 Marginal Independence 라고 할 수 있다.
조건부 독립 (Conditional Independence)
\(P(A|B,C) = P(A|C)\)
- 사건C가 주어졌을 때 두 사건 A와 B가 독립인 경우, 이것은 C라는 조건하에서 조건부 독립 이다.
조건부 확률 (Conditional Probability)
\(P(A= true|B=true)\)
"Probablity of A given B"
B가 주어졌을 때, A의 확률
결합 확률 (joint Probability)
\(P(A= true, B=true)\)
"the probability of A=true and B=true"
A=true와 B=true가 동시에 만족할 확률
조건부 확률과 결합 확률의 관계 는 일반적으로, \(P(X|Y) =\cfrac{P(X,Y)}{P(Y)}\)
총 확률 법칙 (Law of Total Probability)
"Summing out" or "Marginalization"
\(P(A) = \sum_kP(A,B_k) = \sum_kP(A|B_k)P(B_k)\)
\(P(A) = \sum_kP(A,B_k)\) 는 \(B_1,B_2,...,B_n\)이 각각 상호배반적인 집합이고 이들의 합집합이 전체집합이 되므로 성립 (marginalize)
\(\sum_kP(A,B_k) = \sum_kP(A|B_k)P(B_k)\)는 조건부확률과 결합확률의 관계를 이용하면 유도가능
이로 인한 이점은, \(P(A)\)를 직접 구하는 것보다, \(P(A|B_k)\)와 같은 조건부확률을 구해서 합치는 것이 일반적으로 더 수월하다는 것이다.
혹은 결합확률을 알고 있을 때, 여러가지 확률을 계산 할 수 있다.
예를들어, 결합확률인 \(P(a,b,c,d)\)를 알고 있을 때, \(P(c|b)\)는 이렇게 표현할 수 있다
\(P(c|b) = \sum_a \sum_d P(a,c,d|b) = \cfrac{1}{P(b)}\sum_a \sum_d {\bf P(a,b,c,d)}\)
그러나 joint의 경우에는 parameter의 수가 exponential하게 늘어나게 된다! (Chain Rule의 필요성)
확률의 연쇄법칙 (Chain Rule for probability)
모든 joint distribution에 대해, 결합확률과 조건부확률의 관계에 의해 언제나 이하와 같이 표현할 수 있다.
\(P(a,b,c,...,z) = P(a|b,c,...,z)P(b,c,....,z)\)
이것을 반복적으로 하면, \(P(a,b,c,...,z) = P(a|b,c,...,z)P(b|c,...,z)P(c|d,...,z)...P(z)\)로 표현 가능하다. (Factorization)
곱 분해 법칙 (Rule of product decomposition)
Bayesian Network에서는 그래프에 속한 RV의 결합분포(joint distribution)는
family의 모든 조건부 분포 \(P(Child|Parent)\)의 곱\(^{[*1]}\)으로 표현 할 수 있다. (시리즈의 다음 포스트의 Factorization of Bayes Network 내용 참조)\(P(x_1,x_2,...,x_n) = \prod _iP(x_i|Parents(x_i))\)
Parents는 직접적으로 연결되어 영향을 받는 변수만을 의미!
예를 들어, \(X\rightarrow Y \rightarrow Z\) 인 그래프에서 \(P(X=x, Y=y, Z=z)\)를 구하는 것을 생각해보자
원래는 가능한 모든 조합의 \((x, y, z)\)에 해당하는 확률 테이블을 만들어야 한다
그러나, 이 법칙을 이용하면 \(P(X=x, Y=y, Z=z) = P(X=x)P(Y=y|X=x)P(Z=z|Y=y)\)로 간결하게 표현 가능
이처럼 고차원을 저차원으로 만들어 차원의 저주(curse of dimensionality) 에서도 비교적 자유로워 질 수 있다.
<span style="font-size: 85%;> \(^{[*1]}:\) 이렇게 정의되는 원래는 뒤에서 기술하는 베이지안 네트워크의 Typical Local Structures Rules와 관련 되어있다.
* 베이지안 네트워크의 Rules of Typical Local Structures
Rule 1. 사슬 혹은 폭포형 (Chain or Cascading)
변수\(X\)와 변수\(Y\)의 사이에 하나의 방향성 경로 만 있고 변수\(Z\)가 해당 경로를 가로막고 있는 경우, \(Z\)가 조건부로 주어졌을때 두 변수 \(X\)와 \(Y\)는 조건부 독립 이다.
\(X \perp Y|Z\)
\(\Leftrightarrow P(Y|X,Z) = P(Y|Z)\)
Rule 2. 분기 혹은 공통부모형 (Fork or Common parent)
변수 \(Z\)가 \(X\)와 \(Y\)의 공통 원인이고 \(X\)와 \(Y\)사이에 단 하나의 경로가 있는 경우, \(Z\)의 조건이 주어졌을 때 \(X\)와 \(Y\)는 조건부 독립 이다.
\(X \perp Y | Z\)
\(\Leftrightarrow P(X,Y|Z) = P(X|Z)P(Y|Z)\)
Rule 3. 충돌부 혹은 V-구조 (Collider or V-structure)
변수 \(Z\)가 두 변수 \(X\)와 \(Y\) 사이의 충돌 노드이고 \(X\)와 \(Y\) 사이에 단 하나의 경로 만 있을 경우, \(X\)와 \(Y\)는 비조건부 독립(underconditionally independent) 이다. 그러나 \(Z\) 또는 \(Z\)의
descendant을 조건부로 하였을 때 \(X\)와 \(Y\)는 종속적일 가능성 이 있다.\(\sim (X \perp Y|Z)\)
\(\Leftrightarrow P(X,Y,Z)=P(X)P(Y)P(Z|X,Y)\)즉 \(Z\)가 not given 일 때는 독립이지만, 반대로 \(Z\)가 given으로 주어지면 \(X\), \(Y\)가 종속적이 될 가능성이 생겨버린다.
* Bayes Ball Algorithm
목적 ; \(X \perp Y | Z\) (\(Z\)가 given일 때 \(X\)와 \(Y\)가 독립) 이 성립하는지 여부를 판정하기 위한 알고리즘
\(X\)에서 공이 출발한다고 가정했을 때 \(Y\)까지 공이 도달하는지 확인하는 방법
여기서 공은
Information을 의미하고 화살표는 공의 움직임을 의미한다. 노드 간이 직접적인 edge로 연결되어 있지 않더라도 공이 굴러가서 도달할 수 있다면Indirect influence가 존재하기때문에 두 변수는depedent하다는 것을 의미한다.
Rule 1의 경우
(1). \(Z\)가 given이 아닐 때, 공은 지나갈 수 있다. (\(X, Y\)는 종속)
(2). \(Z\)가 given 일 때, 공은 지나갈 수 없다. (\(X \perp Y|Z\))
Rule 2의 경우
(1). \(Z\)가 given이 아닐 때, 공은 지나갈 수 있다. (\(X, Y\)는 종속)
(2). \(Z\)가 given 일 때, 공은 지나갈 수 없다. (\(X \perp Y|Z\))
Rule 3의 경우
(1). \(Z\)가 given이 아닐 때, 공은 지나갈 수 없다. (\(\bf X \perp Y\))
(2). \(X_C\)가 given 일 때, 반대로 path가 생겨서 공이 지나갈 수 있게 된다. (\(X, Y\)는 종속 \(|Z\))
Bayes Ball Algorithm 연습
문제 1. \(X_1\perp X_4|X_2\)
두가지 경로로 공을 굴릴 수 있다.
(1). \(X_1 \rightarrow {\bf X_2}(given) \rightarrow X_4\) 의 경로는 \(X_2\)가 사슬의 given으로 막혀있으므로 지나갈 수 없다.
(2). \(X_1 \rightarrow X_3 \rightarrow X_5 \rightarrow X_6 \leftarrow {\bf X_2}(given) \rightarrow X_4\) 의 경로는 \(X_6\)가 충돌부의 not given으로 막혀있으므로 지나갈 수 없다.
따라서 어떠한 경로로도 볼은 지나갈수 없으므로 \(X_2\)가 given일 때 \(X_1\)와 \(X_4\)는 독립 이다.
문제 2. \(X_2\perp X_5|X_1\)
두가지 경로로 공을 굴릴 수 있다.
(1). \(X_2 \rightarrow X_6 \leftarrow X_5\) 의 경로는 \(X_6\)가 충돌부의 not given으로 막혀있으므로 지나갈 수 없다.
(2). \(X_2 \leftarrow {\bf X_1}(given) \rightarrow X_3 \rightarrow X_5\) 의 경로는 \(X_1\)가 분기의 given으로 막혀있으므로 지나갈 수 없다.
따라서 어떠한 경로로도 볼은 지나갈수 없으므로 \(X_1\)가 given일 때 \(X_2\)와 \(X_5\)는 독립 이다.
문제 3. \(X_1\perp X_6|\{X_2, X_3\}\)
두가지 경로로 공을 굴릴 수 있다.
(1). \(X_1 \rightarrow {\bf X_2}(given) \rightarrow X_6\) 의 경로는 \(X_2\)가 사슬의 given으로 막혀있으므로 지나갈 수 없다.
(2). \(X_1 \rightarrow {\bf X_3}(given) \rightarrow X_5 \rightarrow X_6\) 의 경로는 \(X_3\)가 사슬의 given으로 막혀있으므로 지나갈 수 없다.
따라서 어떠한 경로로도 볼은 지나갈수 없으므로 \(\{X_2, X_3\}\)가 given일 때 \(X_1\)와 \(X_6\)는 독립 이다.
문제 4. \(X_2\perp X_3|\{X_1, X_6\}\)
두가지 경로로 공을 굴릴 수 있다.
(1). \(X_2 \leftarrow {\bf X_1}(given) \rightarrow X_3\) 의 경로는 \(X_1\)가 분기의 given으로 막혀있으므로 지나갈 수 없다.
(2). \(X_2 \rightarrow {\bf X_6}(given) \leftarrow X_5 \leftarrow X_3\) 의 경로는 \(X_6\)가 충돌부의 given으로 뚫려있으므로 지나갈 수 있다.
따라서 두번째 경로로 볼은 지나갈 수 있으므로 \(\{X_1, X_6\}\)가 given일 때 \(X_2\)와 \(X_3\)는 독립이 성립하지 않는다.
* \(d\)-Seperation의 정의
\(d\)는 방향성(directly)을 의미한다.
Bayesian Ball Algorithm으로 \(d\)-Seperation을 확인할 수 있다.
정리하자면, 경로p가 조건부집합 \(\{W\}\)에 의해 \(d\)-Seperate된다는 명제는 이하와 필요충분조건이다.
경로p는 조건부집합 \(\{W\}\)에 속하는 중간노드 \(Z\) 의 사슬 \(X \rightarrow Z \rightarrow Y\) 또는 분기 \(X \leftarrow Z \rightarrow Y\) 를 포함한다.
경로p는 조건부집합 \(\{W\}\)에 속하지 않는 중간노드 \(Z'\) 의 충돌부 \(X \rightarrow Z' \leftarrow Y\) 를 포함한다.
* Reference
해당 포스트는 Edwith에 개설된 문일철 교수님의 인공지능 및 기계학습 개론 II 강의를 정리 & 추가한 내용임을 밝힙니다.
추가 내용 참조
의학 및 사회과학 연구를 위한 통계적 인과추론 （Judea Pearl, Madelyn Glymour, Nicholas P. Jewell）
