10. Directed graphical models (Bayes nets)

10.1. Introduction

복수의 상호 연관된 변수들에 대해서 결합 분포 p(\mathbf{x} | \mathbf{\theta})을 어떻게 표현할 것인가? 이 분포로 변수를 어떻게 추론할 것인가? 이 분포의 매개변수를 어떻게 학습할 것인가?

10.1.1. Chain rule

확률의 연쇄법칙에 의해, 결합 분포는 다음과 같이 나타낼 수 있다.

p(x_{1 : V}) = p(x_{1}) p(x_{2} | x_{1}) \cdots p(x_{V} | x_{1 : V-1})

이 조건부 분포들은 추계적 행렬로 나타내어지는 조건부 확률표(CPT)가 되는데 수가 O(K^{V})이 되므로 매개변수가 많아질수록 계산이 거의 불가능해진다. 하나의 대안은 조건부 확률표를 조건부 확률분포로 바꾸는 것인데, 이러면 매개변수의 수는 O(K^{2}V^{2})이 되지만 각 변수가 그 전 변수들 전부에 의존하는 관계가 필요 없다면 다른 접근법이 필요하다.

10.1.2. Conditional independence

큰 결합분포를 나타내는 데 있어 핵심은 일부 변수들간 조건부 독립(CI)을 가정하는 것이다. 현재 조건 하의 과거에 미래 변수가 의존하지 않는다는 마르코프 가정 x_{t+1} \perp \mathbf{x}_{1 : t-1} | x_{t} 을 가정할 경우 결합 분포는 p(\mathbf{x}_{1 : V}) = p(x_{1} \prod_{t=1}^{V} p(x_{t} | x_{t - 1})이 된다. 이를 마르코프 연쇄라 한다. 이는 최초 분포와 상태 전이 행렬 p(x_{t} = j | x_{t-1} = i) 들로 나타낼 수 있다.

10.1.3. Graphical models

그래프 모델은 결합분포를 조건부 독립 가정하에 나타내기 위한 방법이다. 우선은 방향그래프만 다룬다.

10.1.4. Graph terminology

그래프노드정점들과 그를 잇는 간선들로 구성되어 있고 그를 나타내는 인접행렬로 표현할 수 있다. 간선에 방향이 존재하면 방향그래프이고 그렇지 않으면 비방향그래프라 한다. 자가 루프는 없다고 가정한다.

  • 방향 그래프에서 노드의 부모는 노드로 향하는 간선이 있는 노드이다.
  • 방향 그래프에서 노드의 자식은 노드로부터 향하는 간선들이 도착하는 노드이다.
  • 방향 그래프에서 노드의 가족은 그 노드와 부모의 합이다.
  • 방향 그래프의 뿌리는 부모가 없는 노드이다.
  • 방향 그래프의 은 자식이 없는 노드이다.
  • 방향 그래프에서 노드의 조상은 부모, 부모의 부모, … 들의 집합이다.
  • 방향 그래프에서 노드의 후손은 자식, 자식의 자식, … 들의 집합이다.
  • 그래프에서 노드의 근방은 간선 1개로 연결되어 있는 노드들이다.
  • 노드의 차수는 근방의 수이다. 내차수는 부모의 수이고 외차수는 자식의 수이다.
  • 순환이나 루프는 노드에서 같은 노드로 돌아오는 간선들의 모임을 말한다.
  • 방향 비순환 그래프(DAG)는 순환이 없는 방향 그래프이다.
  • 방향 비순환 그래프의 위상 정렬 또는 전체 정렬은 부모가 자식보다 선행하게 정렬하는 것이다.
  • 경로자취는 노드에서 노드로 가는 간선의 모임이다.
  • 나무는 순환이 없는 그래프이다.
  • 은 나무의 집합이다.
  • 부분그래프는 그래프의 부분집합으로서의 그래프이다.
  • 비방향그래프에서 클리크는 각자가 다른 모든 노드들의 근방인 노드들의 집합이다. 최대 클리크는 그래프 내 최대 크기의 클리크이다.

10.1.5. Directed graphical models

방향 그래프 모델(DGM)은 그래프가 방향 비순환 그래프인 모델로, 베이지안 망, 믿음 망, 인과 망이라고도 한다. 방향 비순환 그래프의 특성은 노드들을 위상 정렬시킬 수 있으므로 순서 마르코프 특성, 즉 노드가 직접 부모에만 의존한다는 특성을 도입할 수 있다는 것이다. 이는 pa(s)가 부모, pred(s)가 조상일 때 x_{s} \perp \mathbf{x}_{\mathrm{pred}(s) - \mathrm{pa}(s)} | \mathbf{x}_{\mathrm{pa}(s)}로 나타낼 수 있다. 이러한 가정을 도입할 경우 필요한 매개변수의 수가 훨씬 적어진다.

10.2. Examples

10.2.1. Naive Bayes classifiers

나이브 베이즈 분류기는 모든 특성이 조건부독립이라 가정하는 예이다. 이를 나무로 모델링해 나무-증강 나이브 베이스 분류기(TAN) 모델을 가정할 수 있다.

10.2.2. Markov and hidden Markov models

1차 마르코프 연쇄 가정을 완화해 2차 마르코프 연쇄로 만들 수 있다. 이 가정은 x_{t}x_{t-2}로부터의 의존성도 가정하는 것이다. 그렇게 하면 p(\mathbf{x}_{1 : T}) = p(x_{1}, x_{2}) \prod_{t=3}^{T} p(x_{t} | x_{t-1}, x_{t-2})이 된다.

관측간에 장기 상호 연관이 많다면 2차 마르코프 가정도 부적절해진다. 이 경우에는 1차 마르코프 연쇄를 따르는 은닉 변수 z_{t}들의 프로세스가 있다 가정하되 데이터는 그 프로세스의 노이즈 낀 관찰이라고 가정하는 것이 낫다. 이를 은닉 마르코프 모델(HMM)이라 한다. p(z_{t} | z_{t-1})전이 모델, p(\mathbf{x}_{t} | z_{t})관측 모델이라 한다. p(z_{t} | \mathbf{x}_{1 : t}, \mathbf{\theta})을 계산하는 것을 상태 추정이라 한다.

10.2.3. Medical diagnosis

알람 망은 집중 치료실에서 관측되는 변인을 모델링하는 수단 중 하나이다. 이는 지식 공학 또는 확률적 전문가 시스템이라는 프로세스에 의해 만들어진다. 다른 종류로는 신속 의료 참조(QMR) 망이 있는데 이는 이분 그래프 구조이며 분포는 가측 노드(증상) v_{t}, 은닉 노드(질병) h_{t}에 대해 p(\mathbf{v}, \mathbf{h}) = \prod_{s} p(h_{s}) \prod_{t} p(v_{t} | \mathbf{h}_{\mathrm{pa}(t)})가 된다.

이 때 잎 노드들은 팬-인(부모의 수)가 많아지므로 조건부 확률분포를 계산하기 힘든데, 이 경우엔 로지스틱 회귀로 대신할 수 있다. 이 방법을 시그모이드 믿음 망이라 한다. 다른 방법으로 모델의 매개변수를 직접 만드는 노이즈-OR 모델을 쓸 수도 있다. 이는 부모 특성이 켜질 경우 자식 특성도 일반적으로 켜지게 됨을 확률적으로 가정한다. 이 경우 각 증상의 발현에 대한 확률은 p(v_{t} = 0 | \mathbf{h}) = \prod_{s \in \mathrm{pa}(t)} \theta_{st}^{\mathbf{1}_{h_{s} = 1}} 이 된다. p(v_{t} = 1 | \mathbf{h}) = 1 -  p(v_{t} = 0 | \mathbf{h}) 이다. 모든 부모가 꺼진 경우에도 자식 특성이 켜진 경우 (알려진 질병들은 걸리지 않았는데도 증상이 발견되는 경우)를 대처하기 위해 항상 켜진 더미 누수 노드 h_{0}을 두는데 이 경우엔 p(v_{t} = 0 | \mathbf{h}) =\theta_{0t} \prod_{s \in \mathrm{pa}(t)} \theta_{st}^{\mathbf{1}_{h_{s} = 1}} 이 된다. 노이즈-OR 조건부 확률분포를 가정하는 이분 모델은 BN2O 모델이라 한다.

10.2.4. Genetic linkage analysis

방향그래프모델의 중요한 적용은 유전 연결관계 분석으로, 족보 그래프로부터 시작한다. 이를 구성하기 위해서는 사람 i와 게놈의 자취 j에 대해 3개의 노드를 만든다. 마커 노드 X_{ij}, 유전자형 \mathbf{G}를 형성하는 2개의 대립 형질 노드 G_{ij}^{m}, G_{ij}^{p}. 이 때 조건부 확률분포 p(X_{ij} | \mathbf{G})침투 모델으로 불린다. 사람 i의 부모로부터 유전자형으로의 호를 더해 유전 물질의 멘델리안 상속을 모델링할 수도 있다. 이는 유전자형의 을 모델링하는 상속 모델로 모델링되며 변수의 값은 단상형이다. 이후에 뿌리 노드의 사전분포를 창립자 모델로 모델링하고, 상속 과정을 조절하는 변수들의 통제에 대한 사전분포를 재조합 모델로 모델링한다. 이 과정을 거쳐서 전체 방향그래프가 얻어진다. 이는 계통발생 은닉 마르코프 모델과 관련이 있다.

이 모델의 간단한 활용예는, 혈액형 A형과 유전자형 (A, A), (A, O), (O, A) 사이에는 일대일대응이 성립하지 않는데 여기서 유전자형을 추론하는 역함수 문제가 있다. 여기서 국소적 증거 p(x_{i} | \mathbf{G}_{i})을 통해 국소적 사후분포 p(\mathbf{G}_{i} | \mathbf{x})을 얻는다.

실제로 이 모델은 어떤 질병을 일으키는 유전자가 어느 게놈에 위치하는지를 알아낼 때 쓰인다. 우선 마커 자취간의 거리를 포함한 모든 매개변수를 안다고 가정하면 미지수는 질병을 일으키는 유전자의 위치 뿐인데, 마커 자취로부터 마르코프 스위치 매개변수를 추정해 질병 유전자와 가장 가까운 알려진 자취간의 거리를 각각 구한 뒤 가능도가 가장 높은 모델을 선택하는 것이다. 문제는 사람의 수나 자취의 수가 커지면 계산 방법에 있어 정확하게 구할 수 없다는 것인데 변량 추론법으로 근사할 수 있다.

10.2.5. Directed Gaussian graphical models

실변수 방향그래프모델의 조건부 확률분포가 p(x_{t} | \mathbf{x}_{\mathrm{pa}(t)} = \mathcal{N}(x_{t} | \mu_{t} + \mathbf{w}_{t}^{T} \mathbf{x}_{\mathrm{pa}(t)}, \sigma_{t}^{2}) 꼴이면 선형 가우시안 조건부 확률분포라 한다. 이를 전부 곱한 큰 결합확률분포 p(\mathbf{x}) = \mathcal{N}(\mathbf{x} | \mathbf{\mu}, \mathbf{\Sigma})은 가우시안이 되는데 이를 방향 가우시안 그래프 모델 또는 가우시안 베이즈 이라 한다. 계산의 편의를 위해 z_{t} \sim \mathcal{N}(0, 1)에 대해 x_{t} = \mu_{t} + \sum_{s \in \mathrm{pa}(t)} w_{ts}(x_{s} - \mu_{s}) + \sigma_{t} z_{t}으로 놓으면 \mathbf{\mu} = (\mu_{1}, \cdots, \mu_{D})이다.

\mathbf{S} = \mathrm{diag}(\mathbf{\sigma}), \mathbf{U} = (\mathbf{I} - \mathbf{W})^{-1}이라 하면 \mathbf{\Sigma} = \mathrm{cov}[\mathbf{x}] =  \mathrm{cov}[\mathbf{x} - \mathbf{\mu}] =  \mathrm{cov}[\mathbf{U}\mathbf{S}\mathbf{z}] = \mathbf{U}\mathbf{S}^{2} \mathbf{U}^{T}가 된다.

10.3. Inference

상호 연관된 확률변수의 결합분포 p(\mathbf{x}_{1 : V} | \mathbf{\theta})의 주 용도는 확률적 추론이다. 관측된 변수 \mathbf{x}_{v}, 숨겨진 변수 \mathbf{x}_{h}가 있을 때 이를 추론하는 법은 p(\mathbf{x}_{h} | \mathbf{x}_{v}, \mathbf{\theta}) = \frac{p(\mathbf{x}_{h}, \mathbf{x}_{v} | \mathbf{\theta})}{ p(\mathbf{x}_{v} | \mathbf{\theta}) } =  \frac{p(\mathbf{x}_{h}, \mathbf{x}_{v} | \mathbf{\theta})}{ \sum_{\mathbf{x}_{h'}} p(\mathbf{x}_{h'}, \mathbf{x}_{v} | \mathbf{\theta})  }  가 된다. 이는 관측 변수를 관측된 값에 고정시켜 조건을 거는 것이 된다. 표준화 상수는 데이터의 가능도이며 증거 확률이라고도 한다.

숨겨진 변수 중 일부에만 흥미가 있을 수 있는데 이것을 쿼리 변수 \mathbf{x}_{q}로 두고 나머지 숨겨진 변수는 방해 변수 \mathbf{x}_{u}로 주고 적분해 빼낼 수 있다. 그러면 p(\mathbf{x}_{q} | \mathbf{x}_{v}, \mathbf{\theta}) = \sum_{\mathbf{x}_{u}} p(\mathbf{x}_{q}, \mathbf{x}_{u} | \mathbf{x}_{v}, \mathbf{\theta}) 이 된다.

다변수 가우시안에 대해서 이 연산은 O(V^{3})이다. 하지만 이산확률변수에 대해서는 훨씬 오래 걸린다. 변수간 의존 관계가 트리에 가까우면 적은 시간복잡도로 가능하지만 그렇지 않다면 근사할 수밖에 없다.

10.4. Learning

추론은 v가 가측 노드, h가 은닉 노드일 때 p(\mathbf{x}_{h} | \mathbf{x}_{v} | \mathbf{\theta})을 계산하는 것을 뜻한다. 학습은 데이터가 주어졌을 때의 최대사후확률추정 \hat{\mathbf{\theta}} = \mathrm{argmax}_{\mathbf{\theta}} \sum_{i=1}^{N} \log p(\mathbf{x}_{i, v} | \mathbf{\theta}) + \log p(\mathbf{\theta}) 을 계산하는 것을 뜻한다. 균등사전분포를 택할 경우 이는 최대가능도추정이 된다.

베이지안 관점에서는 매개변수 또한 미확인 변수이므로 추론되어야 하는 존재이다. 그렇기 때문에 추론과 학습의 차이가 없어진다. 이 관점에서 은닉 변수와 매개변수의 차이점은 은닉 변수의 수는 학습 데이터에 따라 증가하지만 매개변수의 수는 대개 고정된다는 점이다. 그러므로 과적합을 피하기 위해 은닉 변수를 적분해서 빼내는 것이 필요하다.

10.4.1. Plate notation

데이터가 (상호 조건부) 독립적이고 균등하게 분포되었을 경우에는 데이터의 배치 순서에 상관이 없어지는데 이 경우를 교환 가능하다 한다. 문법적 향료로서 플레이트로 반복된 변수를 묶어 모델이 펼쳐질 때 플레이트 내 변수들이 반복됨을 표현할 수 있다. 이는 p(\mathbf{\theta}, \mathcal{D}) = p(\mathbf{\theta}) \prod_{i=1}^{N} p(\mathbf{x}_{i} | \mathbf{\theta})을 도식화한 것이다. 나이브 베이스처럼 변수 범위가 2중일 때는 중첩 플레이트도 쓸 수 있다. 이 때 나이브 베이스는 맥락 특정적 독립의 예라 볼 수 있다.

10.4.2. Learning from complete data

모든 변수가 완전히 관찰되고 유실된 데이터나 은닉 변수가 없으면 데이터가 완전하다고 한다. 이 때 가능도는 p(\mathcal{D} | \mathbf{\theta}) = \prod_{t=1}^{V} p(\mathcal{D}_{t} | \mathbf{\theta}_{t})이 되며 가능도가 그래프 구조를 통해 분해된다고 한다. 사전분포나 사후분포도 분해된다.

베이지안 나이브 베이스의 예를 들면 각각의 조건 케이스는 플레이트 내에서 하나의 행이 된다고 할 수 있다. 행 내의 가중치를 전부 합하면 1이다.

10.4.3. Learning with missing and/or latent variables

유실된 데이터나 은닉 변수가 있다면 가능도는 더 이상 인수분해되지 않으며 볼록함수도 아니다. 즉 국소적으로 최적인 최대가능도추정이나 최대사후확률추정만 구할 수 있다. 베이지안 추론은 더 어려워진다.

10.5. Conditional independence properties of DGMs

그래프 모델의 핵심은 조건부 독립 가정인 \mathbf{x}_{A} \perp_{G} \mathbf{x}_{B} | \mathbf{x}_{C}이다. 그래프 G에 대해 I(G)를 그래프에 표현된 모든 조건부 독립 관계의 집합이라고 할 때 이것이 분포 p의 조건부 독립 관계 안에 포함되면 G를 p의 독립 맵(I-맵), 또는 p를 G에 대해 마르코프라고 한다. 완전연결그래프는 모든 분포의 I-맵이다. G가 p의 I-맵이면서 G' \subseteq G인 다른 I-맵 G’가 없다면 G를 최소 I-맵이라 한다. 그렇다면 그래프 내에서의 조건부 독립 가정은 어떻게 판단해야 할까?

10.5.1. d-separation and the Bayes Ball algorithm (global Markov properties)

비방향경로 P가 노드의 집합 E에 대해 다음의 조건 중 하나 이상을 만족시킬 때 d-분할이라 한다.

  • m이 E에 속할 때 P에 경로 s \leftarrow m \leftarrow t 또는 s \rightarrow m \rightarrow t가 존재한다.
  • m이 E에 속할 때 P에 텐트 s \leftarrow m \rightarrow t가 존재한다.
  • m과 m의 자식 중 아무것도 E에 속하지 않을 때 P에 충돌자(또는 v-구조) s \rightarrow m \leftarrow t가 존재한다.

이 때 노드의 집합 A와 B는 A 내의 모든 노드로부터 B 내의 모든 노드로의 경로가 E에 의해 d-분할이 되면 \mathbf{x}_{A} \perp_{G} \mathbf{x}_{B} | \mathbf{x}_{E}이라 한다.

베이즈 공 알고리즘은 A와 B가 E에 의해 d-분할이 되었는지 아닌지를 판단하는 간단한 알고리즘인데, E의 노드들을 색칠한 뒤에 A 내의 노드들을 통해 공을 굴려서 모든 공들이 B의 노드에 도달할 수 있는지를 보면 된다. 엄밀하게 표현하면 다음과 같다.

  • X \rightarrow Y \rightarrow Z : p(x, y, z) = p(x) p(y | x) p(z | y)p(x, z | y) = p(x|y) p(z|y)이므로 x \perp z | y이다.
  • X \leftarrow Y \rightarrow Z : p(x, y, z) = p(y) p(x | y) p(z | y)p(x, z | y) = p(x | y) p(z | y)이므로 x \perp z | y이다.
  • X \rightarrow Y \leftarrow Z : p(x, y, z) = p(x)p(z)p(y | x, z)p(x, z)=p(x)p(z)이 되어 주변독립이 된다. 그러므로 공통자식에 대해 조건을 거는 것은 그 부모변수들끼리 독립적이지 않게 만든다. 이를 설명, 인과관계 추론, 베크슨의 패러독스라 한다.

베이즈 공 알고리즘에는 경계조건 2개도 필요하다. 흰색 노드 x \leftarrow y 사이에서는 역방향 진행이 불가능하다는 것, y가 검은색 노드(관측된 변수)일 때는 역방향 진행이 가능하다는 것.

10.5.2. Other Markov properties of DGMs

d-분할 조건으로 인해, \mathrm{nd}(t)를 후손을 제외한 비후손 노드라고 할 때 t \perp (\mathrm{nd}(t) - \mathrm{pa}(t)) | \mathrm{pa}(t)가 성립함을 알 수 있다. 이를 방향 국소 마르코프 특성이라 한다. 특수한 케이스로, 위상정렬을 했을 때에는 t \perp (\mathrm{pred}(t) - \mathrm{pa}(t)) | \mathrm{pa}(t)이 되는데 이를 순서 마르코프 특성이라 한다. 방향 전역 마르코프 특성, 방향 국소 마르코프 특성, 순서 마르코프 특성 3가지는 동치이다. 또한, 그래프 G에 대해 분포 p가 마르코프인 것과 p(\mathbf{x}_{1 : V} | G) = \prod_{t=1}^{V} p(x_{t} | \mathbf{x}_{\mathrm{pa}(t)}인 것도 동치이다.

10.5.3. Markov blanket and full conditionals

노드 t와 그래프 내 다른 노드들과는 조건부독립으로 관계가 있는 노드들의 최소 집합을 마르코프 담요 \mathrm{mb}(t)라 하며, 이는 부모, 자식, 그리고 공부모(노드의 자식들의 또 다른 부모)들의 합집합이 된다.

공부모가 왜 마르코프 담요에 속하는가? p(x_{t} | \mathbf{x}_{-t}) = p(\mathbf{x}) / p(\mathbf{x}_{-t}) \propto p(x_{t} | \mathbf{x}_{\mathrm{pa}(t)} \prod_{s \in \mathrm{ch}(t)}p(x_{s} | \mathbf{x}_{\mathrm{pa}(s)})이 되기 때문이다.

10.6. Influence (decision) diagrams

다단계 베이지안 문제는 결정 도표 또는 영향 도표라는 그래프 표현으로 도식화할 수 있다. 이는 그래프 모델에 결정 노드(행위 노드)와 효용 노드(값 노드), 그리고 가능성 노드의 개념을 추가한 것이다. 유명한 예로는 원유 시추 문제가 있다. 원유 우물을 시추하는 것이 나은가? 하지 않는 것이 나은가? 자연 상태가 원유가 많은지/적은지이고 이에 대한 간접적 관측은 음향 신호의 반응으로부터 정보 원호를 그어 이루어진다. 이 때 기대수익\sum_{s} p(s) \mathrm{EU}(d^{\ast}(s)|s)로 계산된다.

테스트에도 비용이 들 경우에는 테스트를 할 경우에 기대효용이 얼마나 증가하는가를 계산할 수 있다. 이를 완전정보의 가치라 한다.

이의 일반화된 모델은 부분 관측 마르코프 결정과정(POMDP)이라 하는데, 이는 관측-동작 사이클을 주로 모델링한다. 상태가 완전히 관측되는 부분 관측 마르코프 결정과정은 마르코프 결정 과정(MDP)라 한다.

요점 정리

  • 방향 그래프 모델(베이즈 넷) : 변수간의 조건부독립을 모델링. 나이브 베이스, 마르코프 모델, 은닉 마르코프 모델 등의 예시가 있음
  • 그래프 모델의 추론은 관측 변수에 대해 베이즈 정리로 은닉 변수의 분포를 계산
  • 그래프 모델의 학습은 데이터가 완전한 경우 사후분포가 인수분해됨을 이용
  • 방향 그래프 모델의 조건부독립 특성을 밝혀내는 데에는 베이즈 공 알고리즘을 사용
  • 방향 그래프 모델의 결정론적 응용으로 영향 도표가 있음

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중