Graphical model

정의를 확실히 아는 것이 중요하다. (물론 위키는 많이 트린다.틀릴 수 있다.)

A graphical model or probabilistic graphical model (PGM) is a probabilistic model for which a graph expresses the conditional dependence structure between random variables. They are commonly used in probability theory, statistics—particularly Bayesian statistics—and machine learning.

여기 정의에 따르면 GM과 PGM은 같은 것으로 본다. 중요한 점은 conditional dependency를 그래프 구조로 나타낸 것이다. 

가장 대표적인 GM으로는 Bayesian network와 Markov random fields가 있다. 

*Bayesian network

네트워크 구조가 directed acyclic graph로 표현된다면 이 모델은 모든 random variable의 joint probability의 factor로 해석될 수 있다. 

$$ P[X_1, ..., X_n] = \prod_{i=1}^n P[X_i | pa_i] $$

*Markov random fields

A Markov random field, also known as a Markov network, is a model over an undirected graph. 

A graphical model with many repeated subunits can be represented with plate notation.

*Factor Graph

A factor graph is a bipartite graph representing the factorization of a function.

In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets '$U$' and '$V$' such that every edge connects a vertex in '$U$' to one in '$V$'.

위 그림이 complete bipartite graph이다. 

- 모든 tree는 bipartite이다. 

아래 예제가 bipartite graph로 풀리는 재밌는 문제이다. 

결국 bipartite graph은 좀 제너럴한 구조이다. 예를 들어 임의의 hypernetwork도 이걸로 표현 하능하다고 한다. 그래프의 집합과 엣지의 집합을 '$U$'와 '$V$'로 잡으면 된다. 내가 좋아하는 RBM도 이 구조와 동일하다. 이 구조에 어떤 연결 구조를 주는지는 다른 문제이기 때문에 뉴럴넷도 이걸로 표현 가능하다. 

잡설이 길어졌는데, factor graph는 아래와 같은 구조를 갖는다. 

위의 그래프를 수식(?)으로 표현해보면 다음과 같다. 

$$ g(X_1,X_2,X_3) = f_1(X_1) f_2(X_1,X_2) f_3(X_1,X_2) f_4$(X_2,X_3) $$

위 그림에서도 알 수 있든이 '$f_2(X_1,X_2)f_3(X_1,X_2)$'를 합치면 tree가 된다. 위에서 언급한 bipartite graph가 tree가 되는 것과 같은 얘기. 뒤에서 살펴볼 message passing 알고리즘은 tree에서는 exact하지만 이런 cycle이 있는 그래프에서는 근사만 할 수 있다. 

일반적으로 쓰이는 message passing 알고리즘은 sum-product 알고리즘이다. 목적은 각 변수의 marginal을 구하는 것이다. 

$$ g_k(X_k) = \sum_{X_{\bar{k}}} g(X_1,X_2, ..., X_n) $$

여기서 '$X_{\bar{k}}$'는 '$k$'번째를 제외한 나머지 변수들을 뜻한다. 

In practice, the sum-product algorithm is used for statistical inference, whereby '${ g(X_{1},X_{2},\dots ,X_{n})}$' is a joint distribution or a joint likelihood function, and the factorization depends on the conditional independencies among the variables. 

The Hammersley–Clifford theorem shows that other probabilistic models such as Bayesian networks and Markov networks can be represented as factor graphs; (오호 이거 재밌는 사실이다.)

the latter representation is frequently used when performing inference over such networks using belief propagation. On the other hand, Bayesian networks are more naturally suited for generative models, as they can directly represent the causalities of the model.