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

---

* 베이지안 네트워크(BN; Bayesian Network) 란?

---

• 확률 변수(RV; Random variables)들 사이의 조건부 독립 등의 관계를 보임으로써, RV의 full joint distribution등을 간결하게 표현할 수 있는 그래프 표기법 (Graphical Notation) 이다.

• 여기서 그래프(Graph) 란, 수학에서 차트(Chart)와 대조되어 정의된 node와 edge의 집합

  • edge가 방향이 지정되어 있으면 directed, 그렇지 않으면 undirected

  • 그래프의 모든 edge가 directed일 때 directed graph

  • directed 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된다는 명제는 이하와 필요충분조건이다.

  1. 경로p는 조건부집합 $\{W\}$에 속하는 중간노드 $Z$ 의 사슬 $X \rightarrow Z \rightarrow Y$ 또는 분기 $X \leftarrow Z \rightarrow Y$ 를 포함한다.

  2. 경로p는 조건부집합 $\{W\}$에 속하지 않는 중간노드 $Z'$ 의 충돌부 $X \rightarrow Z' \leftarrow Y$ 를 포함한다.

---

* Reference

해당 포스트는 Edwith에 개설된 문일철 교수님의 인공지능 및 기계학습 개론 II 강의를 정리 & 추가한 내용임을 밝힙니다.

추가 내용 참조

의학 및 사회과학 연구를 위한 통계적 인과추론 （Judea Pearl, Madelyn Glymour, Nicholas P. Jewell）