[참고] 베이지안 네트워크 원리 (참고자료)

출처(번역) : http://blog.naver.com/omega71/50007604090
출처(원문) : http://people.cs.ubc.ca/~murphyk/Bayes/bayes.html

아래 내용은 A Brief Introduction to Graphical Models and Bayesian Networks 에서 번역하고, Gurugail.com의 GGOP(Virtual Dog) 프로젝트에 맞추어 수정, 요약한 것입니다.

Bayesian Network는

"확률 이론과 그래픽 이론의 결합으로 이루어진 그래픽 모델(Graphical Models)"

이라고 짧게 표현될 수 있다. 그래픽 모델의 기본적 아이디어는 복잡한 시스템을 간단한 모듈로서의 구성을 그래프적으로 표현이 가능하다는 특징이 있다. 그럼으로써 그 모듈이 어떻게 서로 연관성을 가지는지를 확률적 이론에 기반하여 표현이 가능하며, 하나의 모듈은 노드(Node)로써 표현이 가능하며, 모듈간의 관계는 호(Arc)로 표현된다. 그래픽 모델은 방향성(Directed or Undirected)이나 노드의 순환성(Cyclic or nonCyclic)에 따라서 HMM(Hidden Markow Models), FA(Factor Analysis), Kalman Filters 등 여러 가지가 있으며, 그 중 하나가 Baysian Network이다.

I. BN의 그래픽 표기법(Representation)

그래픽 모델에서, 노드는 랜덤 변수(Random Variables)를 나타내며, 호는 노드들간의 관계성을 가리킨다. 중요한 사실은 그래픽적 표현만으로 Fully Joint Probabilty Distribution의 표현이 가능하다라는 것이다. 이는 다시 말해, BN으로 표현이 되면, 랜덤 변수의 모든 조합으로 구성된 확률 분포도를 알 수 있다라는 말이다.

BN는 그래픽 모델 중에서 방향성이 있으며, 비순환의 그래픽 모델을 말한다. 줄여서 DAG, (Directed ACyclic Graph)라고 한다. 아래 간단한 예제 BN을 살펴보자. BN의 설명에서 종종 등장하는 예제이다. 잔디(WetGrass)가 젖을 경우는 스프린클러(Sprinkler)가 동작하거나 비가 오거나의 경우를 BN으로 표현한 것이다. 아래 예에서 "날씨가 흐릴 때 비가 올 확률", 즉 P(R=T| C=T) = 0.8이다.

 

어떤 상황을 BN으로 구성하기 위해서는 위와 같은 경우처럼,

1. 시스템을 표현할 수 있는 노드 구성
2. 노드와의 연결성 (Arc 구성)
3. 확률 테이블(CPT) 구성

하면 모든 것이 끝난다. 단, 중요한 사실은 노드간의 조건부 독립(Conditional Indendence)의 특성을 부여하면서 구성해야 된다는 사실이다. 조건부 독립을 확인하기 위한 D-seperation 알고리즘?도 있고, 복잡도 하지만 간단히, 제 생각으로는 적어도 Virtual Dog에서 느낌상으로 조건부 독립적으로 노드를 구성하면 OK이다. 위의 예에서는 스프린쿨러(S)가 동작할 경우와 비가 올 경우는 흐린날(C)이라는 조건에서 서로 조건부 독립이다.

위와 같은 BN이구성되면, "잔디가 젖었을 때(W), 스프린쿨러(S)가 동작하였을 확률"을 아래 식처럼 직접 계산할 수 있다. CPT에 직접적으로 표현이 되지 않았지만, 추론이라는 Method에 의해 표현(계산, 추측, 추론)될 수 있는 것이다.

다른 모든 경우도 수식으로 계산이 가능한 것이다. 다만 직접 계산을 할 경우 기하급수적으로 계산량이 증가하기 때문에, Approximation 방법을 이용하기도 한다고 한다. 계산 방법은 이 문서에서는 생략하고, 다만 그냥 개념만 이해하고 갔으면 한다. 하나 더 추가할 개념은 여기서 W가 Evidence가 되고 S가 Query가 되는 셈이며( 잔디가 젖었다는 사실을 알고, 그에 상응하는 S의 확률을 쿼리), 이런 식의 계산을 Bottom-up reasoning 이라고 한다.

II. 추론(Inference)

BN에서 추론이란 무엇일까, 어떤 의미를 추론이라고 할까? 위에서 잠깐 언급한 Evidence와 Query를 먼저 이해해야 한다. BN에서 추론이란 "알고 있는 확률변수를 이용해서 원하는(알고자 하는) 확률값을 구하는 과정"이라 할 수 있다. 위의 과정이 바로 추론과정이다. 위 그림의 BN에서는 Casuality(원인 -> 결과)에 따른 확률값은 표현이 되어 있고(CPT), 위 수식과 같이 "잔디가 젖었을 때(W), 스프린쿨러(S)가 동작하였을 확률"은 CPT를 이용해 바로 구할 수는 없다. 그럼으로 계산이나 Approximation 방법 등을 이용한 추론을 해야 한다. 물론 어떻게 보면 확률 계산에 불과하지만, 그러한 계산이 노드에 따라서 기하 급수적으로 증가하기 때문에 여러 가지 추론 알고리즘이 있다. (Variable Elimination, Dynamic Programming, Approximation Algorithms, etc)

1. Variable Elimination

추론을 하는 방법 중의 하나이다. 기본 생각은 추론을 원하고자 하는 식을 CPT의 Factored Representation으로 표현하는 것이다. 그것은 관계 없는 변수에 대한 경우의 합계 표현으로 가능하다. 설명이 잘 이해가 되지 않을 것이다. ^^; 고등학교 때 배운 확률을 잘 생각해보자. Joint Probability에서 랜던 변수 X, Y가 있고, Y는 Boolean Variable이라고 가정하면

P(X=i) = P(X=i, Y=false) + P(X=i, Y=true) 인 것이 생각이 나는지... 아무튼 이와 같은 원리와 그리고 Bayes 이론을 사용해서 확률값을 구하는 방법론이 Variable Elimination이다.

WetGrass(P(W=true))인 확률을 구하기 위해서 위와 같은 단계를 거치면, 결국 CPT에 있는 확률값들을 이용해서 구할 수 있는 것이다. 왜 이 방법이 "변수 제거(Variable Elimination)"인지는 확률값을 구하기 위해서는 Innermost가 우선적으로 구해지고, 그에 따라 Summation 되는 변수(c,s,r) 등이 차례로 구해지는 과정에서 생긴 이름으로 생각된다.

III. 학습(Learning)

BN에서 학습이란, 주어진 학습 데이타를 이용하여, 그래프의 Topology를 구성하는 것과 CPT(Conditional Probability Table)을 구성하는 것을 말하며, 그래프의 Topology를 구성하는 것이 CPT를 구성하는 것보다 어려운 작업이다. 데이터 혹은 그래프에 따라 조건별 학습 방법은 아래와 같다.

Structure	Observability	Method
Known	Full	Maximum Likelihood Estimation
Known	Partial	EM (or gradient ascent)
Unknown	Full	Search through model space
Unknown	Partial	EM + search through model space

1. Structure가 Known이며, 학습 데이터도 Full Observability할 경우의 예
(Maximum Likelihood Estimation)

이와 같은 경우도 그래픽의 구조나 CPT를 구하기 위한 모든 학습 데이터가 주어지기 때문에 단순 Counting으로 추측할 수 있다. 가령 위 그림에서 W 노드의 CPT를 구한다고 가정하면, 다음과 같이 Maximum Likelihood Estimation 방법을 이용한다.

식을 보면 단순히 Counting만으로 W 노드의 CPT를 구하는 것을 볼 수 있다.(N는 경우의 수)