[PGM] part1 - Bayesian Network

확률 그래피컬 모델(Probability Graphical Model) - part1

1. 확률과 그래프의 만남

1.1 그래프 표현

• 방향 그래프(directed graph) : 베이지안 네트워크(Bayesian network) = 방향 그래피컬 모델(Dirtected graphical model)

  그래프는 인과관계를 표현하는 뼈대를 형성하고, 뼈대에 확률을 부여합니다.

• 무방향 그래프(undirected graph) : 마르코프 랜덤필드 MRF(Markov Random Field) = 무방향 그래피컬 모델(undirected graphical model)

  영상의 각 화소는 이웃화소와 밀접한 연관이 있지만, 한 화소가 다른 화소에게 일방적으로 영향을 미치는 인과관계는 형성되지 않습니다. 따라서 영상은 무방향 그래프로 표현되는 MRF를 사용하는 것이 적절합니다.

• 깊은 신경망(DMLP) : DBN(Deep Belief Network) - 은닉층이 하나인 RMB(Restricted Boltzman Machine)을 순차적으로 쌓음

MRF와 RBM은 에너지 모델(energy model)입니다. 확률 벡터 x가 발생활 확률을
$$
P(x) = exp(-energy(x))
$$
와 같이 표현합니다.

1.2 그래프 분해와 확률 표현

• G = (X, E)
• X = {$x_1, x_2, \cdots, x_n$}, E = {$e_1, e_2, \cdots, e_n$}

그래피컬 모델에서는 노드 $x_i$를 확률변수(Random variable)라고 합니다.

그래프에 확률을 부여하는 가장 단순한 방법은 결합확률(joint probability)입니다.

P(x) = P($x_1, x_2, x_3$) = P($x_3$)P($x_2 | x_3$)P($x_1 | x_2, x_3$) 등과 같이 표현할 수 있습니다.

하지만 의료진단이나 주식 예측 등에서는 매우 많은 확률변수를 가질 것이므로 n개의 확률변수가 있고, 각각 q개의 값을 가진다면 총 $q^n - 1$개의 확률값을 지정해야 하므로 차원의 저주 문제가 발생합니다. 이렇게 방대한 경우의 수를 일일이 확률을 지정하는 일은 불가능합니다.

따라서, 그래피컬 모델의 핵심 아이디어는 직접 상호작용하는 노드(확률변수)만 에지로 연결하는 것입니다. 이렇게 그래프가 부분 연결 구조를 가지게 하는 방법을 그래프 분해(graph decomposition)라고 합니다.

마르코프 성질(Marcov Property)에 의해 분해한 그래프의 부분집합의 확률분포만 추정하면 됩니다.

2. Bayesian Network

확률변수 간 인과관계가 뚜렷한 응용 분야에 널리 쓰입니다.(Pearl, 1988)

특성

1) 에너지함수가 아닌, 데이터로부터 추정한 확률을 이용하므로 좀 더 엄격한 확률 모델입니다.

2) 확률변수 사이의 인과관계를 조건부 확률로 표현하므로 불완전 데이터를 처리할 수 있습니다.

​ 즉, 확률변수의 일부만 관찰해서 나머지 변수 중 관심 있는 것의 확률을 추론할 수 있습니다.

3) 데이터와 도메인 지식을 혼용할 수 있습니다.

주요문제

1) 구조학습(structure learning): 그래프 구조를 만드는 작업입니다. 확률변수는 사람이 정하고, 인과관계는 사람이 정하거나 데이터로부터 자동으로 알아냅니다.

2) 확률학습(probability learning): 노드 또는 엣지의 확률을 부여하는 작업입니다. root node는 사전확률, 부모가 있는 노드는 조건부 확률을 알아냅니다. 보통 조건부 확률의 | 오른쪽에 있는 변수는 관찰 가능한 변수이고, | 왼쪽에는 확률을 알고자 하는 변수가 옵니다.

3) 확률추론(probability inference): 테스트 단계입니다. 각종 질문에 대한 확률을 추정합니다.

1) 예제

2) 그래프 분해

(Neapolitan, 2004)

확률변수 간 인과관계를 나타낸 그래프를 인과관계 그래프(causality graph)라고 합니다.

방향 그래프이면서 사이클을 허용하지 않으므로 DAG(directed acyclic graph)라고 합니다.

위 그림은 위상정렬(topological sort)가 된 그래프입니다.

결합확률(Joint probability)을 조건부확률(conditional probability)로 분해
$$
\begin{align}
P(\mathbb{x}) & = P(x_1, x_2, \cdots, x_n) \
& = P(x_1)P(x_2|x_1)P(x_3|x_2, x_1)\cdots P(x_n|x_{n-1}, x_{n-2}, \cdots, x_1)
\end{align}
$$

베이지안 네트워크는 마르코프 조건(Marcov condition)을 적용해서 그래프를 추가로 분해합니다.

마르코프 조건은 노드 x의 부모 노드를 y라 할 때, y의 값이 주어지면 x는 자신의 후손을 제외한 모든 노드(비후손)와 조건부 독립이라는 조건입니다.

독립이라는 조건이 붙으면, 위 수식은 간단해질 수 있습니다.

즉, 인과관계 네트워크에 확률을 부여하는 '확률 학습'문제를 부모 자식 사이로 지역화 된 것입니다.

부모가 없는 루트 노드는 사전확률을 부여하고, 부모가 있는 노드들은 부모와 자식 사이로 한정하여 조건부 확률을 부여합니다.

이렇게 되면 식은 아래와 같이 표현할 수 있습니다.
$$
P(\mathbb{x}) = \prod_{i=1}^n P(x_i |parent(x_i))
$$
여기서 $parent(x)$는 노드 $x$의 부모 노드 집합입니다.

확률 학습

확률을 부여하는 방법은 두 가지가 있습니다.

1) 전문가의 경험, 보유한 데이터를 가지고 부여합니다.

2) 훈련집합을 가지고 자동으로 학습합니다. (Neapolitan, 2004)

3) d-분리

조건부 독립

확률변수의 값이 주어졌을 때, 독립인 확률변수와 독립이 아닌 확률변수를 확인합니다.

베이지안 네트워크는 세 가지 연결패턴 선형, 분기, 합류로 구성됩니다.

(a) 선형구조

폐암 확률변수의 값이 알려지면, 마르코프 조건에 따라 엑스레이는 흡연과 조건부 독립이 됩니다.

확률 표기를 사용하면 $P(c | b, a) = P(c | b)$이 됩니다.

독립 표기를 사용하면 $I(c, a| b)$ 입니다. 여기서 $I(x_i, x_j | x_k)$는 $x_k$가 주어지면 $x_i$와 $x_j$는 독립이라는 뜻입니다.

(b) 분기구조

b(폐암 여부)을 모른다고 가정해봅시다. 이 때 피로를 느낀다는 사실을 알면, 폐암일 확률이 높아지고 이에 따라 엑스레이 양성 반응 가능성이 커집니다. 즉, b를 모르면 a와 c가 독립이 아닙니다.

하지만 b를 알면, 피로를 느낀다는 사실이 더 이상 엑스레이에 영향을 주지 못합니다. 확률로 표기하면 $P(c|a, b) = P(c|b)$ 이고, 조건부 독립 표기를 하면 $I(a, c| b)$입니다.

이 현상을 'b를 알면 a←b→c라는 체인 폐쇄된다.' 라고 합니다.

(c) 합류구조

합류와 분기는 반대로 작용합니다. b를 모르면 a와 c는 독립입니다. 피로 여부를 모르는 상태에서는 폐렴 여부가 폐암 확률에 영향을 미치지 않습니다. 하지만 b를 알면, a와 c는 더 이상 조건부 독립이 아닙니다. 피로를 느낀다는 사실을 알면 폐암과 폐렴은 서로 영향을 주게 됩니다.

여기서 환자가 폐렴이라는 사실을 알게되면 폐암일 가능성을 낮게 봅니다. 폐렴 때문에 피로가 설명되기 때문에 확률이 낮아지는데 이를 설명됨(explaining way)이라고 합니다. 심리학에서는 이를 확률이 삭감된다는 의미로 할인(discounting)현상이라고 합니다.

반대로 폐렴이 아니라는 사실을 알게되면, 폐암일 확률이 올라갑니다. 이러한 현상을 'b를 알면 체인 a→b←c는 폐쇄되지 않는다.(또는 열린다.)'라고 합니다.

---

[정의 1] 체인의 폐쇄

a와 c를 잇는 체인과 노드 집합 W가 주어졌을 때, 다음 조건 중 하나라도 성립하면, 체인은 W에 의해 폐쇄되었다고 말합니다.

(1)선형: W에 속한 노드가 체인에 머리-꼬리 형태로 나타난다.

(2)분기: W에 속한 노드가 체인에 꼬리-꼬리 형태로 나타난다.

(3)합류: 체인에 머리-머리 형태의 노드가 있을 때, 이 노드와 노드의 자손이 모두 W에 속하지 않는다.

예제

d-분리(d-seperated)

[정의 1]은 두 노드를 잇는 체인 하나의 폐쇄 여부를 따집니다. 하지만, 두 노드 사이에는 여러 개의 체인이 있으므로 두 노드가 완전히 폐쇄되어 조건부 독립을 이루는지 알아보려면, 모든 체인을 다 확인해야 합니다. [정의 2]는 확인 작업에 사용합니다.

[정의 2] d-분리

두 노드 a와 c사이에 있는 모든 체인이 노드 집합 W에 의해 폐쇄되면 두 노드는 d-분리되었다고 하고, $d - sep(a, c|W)$라고 표기합니다.

노드 집합으로 확장하면, 두 노드 집합 $A$와 $C$ 사이에 있는 모든 체인이 노드 집합 W에 의해 폐쇄되면 두 노드 집합은 d-분리 되었다고 하고, $d - sep(A, C|W)$라고 표기합니다.

4) 확률 추론

d-분리와 확률 추론

지정된 확률 이외의 확률을 알아내려면 추가적인 계산이 필요합니다. 이 계산을 확률추론(probabilistic inference)라고 합니다.

현실 세계에서는 엑스레이 결과가 positive인데 폐암일 확률 = P(lung_cancer | positive)와 같은 값에 관심이 있습니다.

베이지안 네트워크에서는 아래 노드일수록 관찰 결과에, 위쪽 노드일수록 원인에 해당하게 됩니다.

관찰 결과에 가까운 노드를 정보 확률변수(information random variable), 원인에 가까운 노드를 가설 확률변수(hypothesis random variable)라고 합니다. 보통 관찰을 통해 정보 확률변수를 알았을 때, 가설 확률변수의 값을 구하는데에 관심이 있습니다. (예. P(lung_cancer | positive, not_fatigue))

현실에서 베이지안 네트워크는 확률변수가 매우 많으므로, 계산량을 줄이는 것이 핵심 주제입니다. 이 때 d-분리는 매우 효과적입니다
$$
\begin{gather}
d - sep(a,c|W) \rightarrow I(a,c |W) \
d - sep(A,C|W) \rightarrow I(A,C |W)
\end{gather}
$$
라는 정리가 증명되있으므로, d-분리를 통해 확률변수 간 독립성을 알 수 있습니다.

정확한 해 구하기

확률 추론 알고리즘은 메시지 전달(message passing)방식 입니다. 즉, 알려진 확률 변수에서 출발하여 이웃 확률변수로 정보를 파급하는 방식으로 동작합니다.

펄은 단일연결그래프(Singly-connected graph)에서 동작하는 확률 추론 알고리즘을 제시하였습니다.(Pearl, 1988)

단일연결그래프란 아래 그림과 같이 노드와 노드 사이의 체인이 하나만 있는 그래프를 말합니다. 다중 연결 그래프(multi-connected graph)에서는 다른 알고리즘이 필요합니다.

근사 추론

일반적인 베이지안 네트워크에서 정확한 확률을 추론하는 문제는 NP-hard임이 증명되었습니다.(Cooper, 1990) 확률변수에 따라 지수적으로 계산 시간이 증가하여 현실적인 시간안에 알고리즘을 풀지 못하는 것입니다. 따라서 근사해를 구합니다.

근사해를 구하기 위해 샘플링을 사용합니다.

논리샘플링 (Henrion, 1988)

샘플이 많을수록 정확한 해에 근접하며, 무한대이면 정확한 해와 같아진다는 정리가 증명되어있습니다.

논리 샘플링은 이해가 쉽지만, 현재는 마르코프 체인 몬테카를로(MCMC, Marcov Chain Monte Carlo)기법에 밀려 잘 사용하지 않습니다.

근사해를 구하는 알고리즘도 작은 오류를 보장하는 문제는 NP-hard라고 증명이 되어있습니다. 따라서 베이지안 네트워크에서 확률 추론을 선형시간내에 하는 일은 중요한 연구 주제입니다.

---

Reference

기계학습, 오일석, 2017, 10. 확률 그래피컬 모델