[인공지능] 14. Bayesian Networks

1. Definition of Bayesian Networks

 

1) Bayesian networks (= belief networks, Bayesian belief networks, graphical models)

  - Directed graph임

  - Nodes (= Random variable)와 Links 로 구성됨 

  - node X로부터 node Y로의 links로 이루어진 directed acyclic graph(DAG)

  - X는 causes, Y는 effects

  - Conditional probability distribution P(Xi | Parents(Xi) ) : Xi 의 부모 노드들이 발생할 때 Xi가 발생할 확률

 

즉 ~가 발생할 때의 확률을 트리처럼..? 그래프로 나타냄

 

2) Conditional Probability Table ( = CPT ) : 조건부 확률표

  - k개의 Boolean parents가 있을 경우 ; 2^k 개의 선행된 확률이 있음 -> 2^k개의 행을 가짐

  - parents가 없을 경우 : prior probabilities

 

  3) Bayesian network의 probabilistic inference

    - Joint distribution in the Bayesian network

      P(x1, x2, ... , xn) = ∏ P(xi | x1, ... , xi-1) = ∏ P(xi | Parent(xi))

     왜냐면 parent의 parent랑 현재 노드랑은 서로 independent하다. (=conditional independent)

 

   - Query (C는 query, E는 관측된 evidence)

     P(C | E1, E2 ,..., En) = P(C, E1, E2, ..., En) / P(E1, E2, ..., En)

 

 

2. Constructing Bayesian Networks

 1) Nodes

   - Variables {X1, ..., Xn}

   - cause는 effect보다 먼저 오게 numbering해야 더 간단한 bayesian networks를 생성할 수 있음

 2) Links

   - Acyclic 해야 함 

   - 1부터 n까지 다음 작업을 반복한다.

     Xi에 대해 P(xi | x1 ,.., xi-1 ) = P(xi | Parent(xi) ) 를 만족하는 가장 작은 set of parents를 골라서 parent와 Xi 를 연결한다. 그리고 CPTs (조건부 확률표) P(Xi | Parent(Xi))를 적는다. 

Cause가 Effects보다 선행되어야 하는 이유 -> 복잡해짐 ㅎ.ㅎ..

  - Diagnostic model : effect를 보고 cause를 진단. 바로 위 그래프가 이거임

  - Causal model : 위위 그래프처럼 cause가 effect보다 먼저 와서 제일 simple한 꼴의 그래프. 확률 학습에 용이함.

 

 

 

3. Inference in Bayesian Networks

  1) Inference by Enumeration

 

 - Query variables and evidence variables.

 

 

P(X|e) = P(X, e) / P(e) = αP(X,e) = α ∑y P(X, e, y)  <- 모든 y에 대한 값을 더함. marginalize

P(v1, v2, ... , vn) = ∏P(vi | v1 ,.., vi-1) = ∏ P(vi | Parent(vi))

 

 

 

...

수도코드를 이해해보자....

 

 - Analysis of Enumeration-Ask Algorithm

    : Space complexity : linear (=DFS)

      Time complexity : n개의 boolean variables이 있을 때 O(2^n)

 

 

  2) Variable Elimination Algorithm 

   * Dynamic Programming : 저장해서 활용하기

     : enumeration algorithm은 계산의 반복을 없애서 개선할 수 있다. 

  -> Variable Elimination Algorithm이 바로 그 알고리즘! dynamic program을 활용해서 기존의 inference 알고리즘을 개선한다. (bottom up) 

 

  * Pointwise product

f1 이라는 함수는 A와 B의 값에 따른 확률을 갖는 함수, f2는 B와 C의 값에 따라 확률을 갖는 함수, f3는 A, B, C에 대한 건데 f1과 f2의 곱으로 나타낼 수 있음. 이 때 곱은, 두 함수의 공통인 인자인 B의 진리값이 같아야 합쳐짐(곱해질 수 있음)

 

예시 )