Belief Propagation

Belief Propagation 이란?

그래프 상에서 관측된 일부 확률 변수에 대한 확률 분포 또는 값이 주어졌을 때, 그 외 관측되지 않은 확률 변수의 Marginal Distribution (BELIEF) 를 추정하는 문제임.

즉, 우리의 목표는 $P(B_i|D) = BEL(B_i)$ 를 추정(INFERENCE)하는 것이다.

$$BEL(B_i) = P(B_i|D_B^+, D_B^-) = alpha * P()$$

Factor Graph를 활용하면 우리가 구하고자 하는 Inference 를 CRF 와 같은 무방향 그래프에서 구할 수 있다. Factor Graph 에서 두가지 형태의 메세지가 있다.

• From a variable node to its neighbor factor nodes:

• From a factor node to its neighbor variable nodes:

. Markov Random Fields

Undirected Graphical Models 의 일종인가 ? 베이지안 네트워크에서는 변수를 나타내는 노드와 조건부 확률을 나타내는 간선이 있는데 이러한 베이지안 네트워크에서는 방향이 있어서 부모와 자식 역할이 있다. $P(A,B,C) = P(B|A)P(C|B)P(A|C) = P(B,C|A)P(A|C) = P(A,B,C|C)$ 따라서 베이지안 네트워크에서는 몇가지 제한이 있는데 P(A) = P(B) = P(C) =1 이어야 한다. 즉, 모든 베이지안 네트워크는 방향성이 있고, acyclic graph(DAGs) 이어야 한다. 만약에 방향이 없는 그래프를 모델링 하기 위해서 마코프 랜덤 필드를 사용한다.

방향 그래프에서 간선의 의미가 조건부 확률이었다면, 무방향 그래프에서 간선의 의미는 모든 클릭의 확률을 곱한 것과 같다. 즉 결합확률분포가 팩토라이제이션 되어 있다.

cliques 란 완전 그래프의 부분 그래프이지만, 여기서는 간선이라고 생각해보자.

Potential Functions

A,B,C,D 가 선형으로 연결되 있는 그래프 P(A|B)P(B|C)P(C|D)P(D)

pdf 가 가지는 성질들을 만족하지 못하기 때문에 potential function 이라고 한다. 클릭은 무엇인가? Data Structure 또는 Dijeckstra 서브 그래프 인데 완전 연결된 그래프이다. 클릭(A-B, B-C, C-D)들을 연결해주는 것은 Separator 이다. 이제 정의해보자 풋사이 함수를 클릭마다 정의함. 풋사이 함수의 파라미터는 각 노드. 구분함수에는 파이를 정의함.

정의 할 수 있음. 풋싸이 곱한 것 나누기 파이 곱한것.

https://www.sciencedirect.com/topics/computer-science/markov-random-fields