26. Graphical model structure learning

26.1. Introduction

이 장에서는 그래프 모델의 구조를 학습하는 법을 다룬다. 이는 지식 발견과 밀도함수 추정 등의 적용 분야가 있다. 주된 난점은 가능한 그래프의 수가 정점의 수에 대해 지수함수적이라는 것이다. 간단한 상한으로 O(2^{\frac{V(V-1)}{2}})이 있다. 그러므로 전체 사후분포 p(G|\mathcal{D})는 계산하기도 힘들고 저장할 수도 없다. 그래서 그에 대한 적절한 간추림을 사용한다.

지식 발견이 목적이면, 사후 간선 주변분포 p(G_{st} = 1 | \mathcal{D})를 계산한 뒤 대응되는 그래프를 플로팅할 수 있다. 밀도함수 추정이 목적이면 최대사후확률추정 그래프 \hat{G} \in \mathrm{argmax}_{G} p(G | \mathcal{D})을 계산할 수 있다. 이는 대개 지수함수적으로 계산 시간이 걸리므로 휴리스틱 탐색과 같은 최적화 방법을 사용한다. 하지만 트리의 경우에는 전역적으로 최적인 그래프 구조에 대해 효율적으로 정확한 추론이 가능하다. 밀도함수 추정만이 목적이라면 잠재변수 모델을 학습해서 관측가능한 변수간의 상관 관계를 모델링하는 것이 나을지를 고려해 볼 수도 있다. 이는 학습된 그래프에서의 추론을 필요로 하지 않기 때문에 상대적으로 더 학습하기 쉽고 학습 시의 적용 범위도 넓기 때문이다. 단점은 이런 잠재 인자들을 특정하고 표현하기 어렵다는 점이다. 어떤 경우에는 관측가능한 변수들 간의 상관 관계를 모델링하는 것뿐만 아니라 데이터 뒤의 인과 관계를 모델링해야 할 때도 있다.

26.2. Structure learning for knowledge discovery

최대사후확률추정 그래프나 정확한 간선주변분포의 사후분포를 계산하는 것은 일반적으로 계산 가능하지 않기 때문에 여기서는 간단한 휴리스틱을 다룬다. 이들은 예측에도 쓸 수 없고 정식으로 계산 가능하지도 않지만 간단한 시각화는 가능케 해준다.

26.2.1. Relevance networks

연관성 망은 복수의 확률변수간의 상호 정보를 시각화하는 방법이다. 기준점을 고른 뒤에 \mathbb{I}(X_{i}; X_{j})가 그 기준점을 넘어서면 정점 i로부터 j의 간선을 그리는 것이다. 가우시안의 경우에는 \mathbb{I}(X_{i}; X_{j}) = -\frac{1}{2} \log (1-\rho_{ij}^{2})이 될 것이다. 하지만 연관성 망에는 문제가 있는데 그래프가 일반적으로 매우 조밀하다는 것이다. 더 좋은 방법으로는 그래프 모델을 이용해 조건부독립을 표현하는 것이 있다.

26.2.2. Dependency networks

그래프 모델을 학습하는 간단하고 효과적인 방법은 D개의 전체 조건부 확률분포 p(x_{t} | \mathbf{x}_{-t})을 독립적으로 학습하는 것이다. 이를 의존성 망이라 한다. 선택된 변수들은 정점의 입력을 구성하고, 결과로 나오는 희소한 그래프를 시각화하면 된다. 이것이 연관성 망에 대해 갖는 이점은 필요 없는 변수들이 입력으로 선택되지 않는다는 것이다. 이 때 각각의 조건부밀도함수를 피팅하는 데에는 희소 회귀나 분류 방법 중 어떤 것도 쓸 수 있다.

의존성 망은 데이터를 시각화하는 것뿐만 아니라 추론에도 쓸 수 있다. 하지만 이 때 쓸 수 있는 알고리즘은 깁스 샘플링 뿐이다. 전체 조건부함수의 곱은 결합분포의 올바른 표현이 된다는 보장이 없기 때문에 깁스 샘플링의 결과가 의미있다는 보장도 없다. 그럼에도 불구하고, 유실된 데이터가 많지 않다면 유의미한 결과를 줄 수도 있다. 또는, 더 복잡한 알고리즘에 있어 초기화 방법으로 작동할 수도 있다.

26.3. Learning tree structures

전체 결합확률분포는 어떻게 학습할까? 일반적인 그래프에 대해서는 NP-난해이기 때문에, 트리에 대해서만 다뤄보자. 트리는 학습을 효율적으로 할 수 있으며 이후에 정확한 추론까지 가능하다.

26.3.1. Directed or undirected tree?

방향 트리를 써야 하나 비방향 트리를 써야 하나? 방향 트리의 경우 결합분포는 다음과 같다.

p(\mathbf{x} | T) = \prod_{t \in V}p(x_{t} | x_{\mathrm{pa}(t)})

이는 대칭적이지 못하다. 대칭적인 트리를 쓰려면 비방향 트리를 쓴다. 이 경우 결합분포는 다음과 같다.

p(\mathbf{x} | T) = \prod_{t \in V}p(x_{t}) \prod_{(s, t) \in E} \frac{p(x_{s}, x_{t})}{p(x_{s})p(x_{t})}

이 때 트리는 비방향 그래프로도 방향 그래프로도 나타내어질 수 있다. 매개변수의 수도 같고, 복잡도도 같다. 또한, 두 표현에서의 추론도 같다. 비방향 표현은 대칭적이므로 구조 학습에 좋고, 방향 표현은 매개변수 학습에 좋다.

26.3.2. Chow-Liu algorithm for finding the ML tree structure

트리에 대한 가능도는 다음과 같이 쓸 수 있다.

\log p(\mathcal{D} | \mathbf{\theta}, T) = \sum_{t} \sum_{k} N_{tk} \log p(x_{t} = k | \mathbf{\theta}) + \sum_{s, t}\sum_{j,k} N_{stjk} \log \frac{p(x_{s} = j, x_{t} = k | \mathbf{\theta})}{p(x_{s} = j | \mathbf{\theta}) p(x_{t} = k | \mathbf{\theta})}

이를 실측 분포에 대해 다시 쓰면 다음과 같다.

\frac{\log p(\mathcal{D} | \mathbf{\theta}, T)}{N} = \sum_{t \in \mathcal{V}}\sum_{k} p_{\mathrm{emp}}(x_{t} = k) \log p_{\mathrm{emp}}(x_{t} = k) + \sum_{(s, t) \in \mathcal{E}(T)} \mathbb{I}(x_{s}, x_{t} | \hat{\mathbf{\theta}}_{st})

이 때 뒤의 \mathbb{I}(x_{s}, x_{t} | \hat{\mathbf{\theta}}_{st}) = \sum_{j} \sum_{k} p_{\mathrm{emp}}(x_{s} = j, x_{t} = k) \log \frac{p_{\mathrm{emp}}(x_{s} = j, x_{t} = k)}{p_{\mathrm{emp}}(x_{s} = j)p_{\mathrm{emp}}(x_{t} = k)}은 실측 분포가 주어진 조건하의 x_{s}, x_{t}간 상호 정보량이다.

즉 이 가능도를 최대화시키는 트리 구조는 간선 가중치가 쌍별 상호 정보량일 때 최대 가중치 신장 트리를 구함으로써 계산할 수 있다. 이를 초우-리우 알고리즘이라 한다. 수행 시간은 O(NV^{2} + V^{2} \log V)가 된다.

26.3.3. Finding the MAP forest

모든 트리가 같은 개수의 매개변수를 갖고 있기 때문에, 과적합의 우려 없이 최대가능도 점수를 모델 선택 기준으로 쓸 수 있다. 하지만, 단일 트리 대신에 포레스트를 피팅하는 것이 좋을 때가 있는데, 포레스트에서의 추론은 트리에서의 추론보다 더 빠르기 때문이다. 최대가능도추정 기준치가 간선을 빠트리는 선택을 하지 않는다. 다만 주변가능도나 징벌가능도를 사용한다면 최적해는 포레스트가 될 수 있다. 여기서는 주변가능도에 대한 경우를 다룬다.

방향비순환그래프의 주변가능도는 디리클레 사전분포를 이용해 계산할 수 있다. 이를 계산하면 다음과 같다.

\log p(\mathcal{D} | T) = \sum_{t \in \mathcal{V}} \log \int \prod_{i=1}^{N} p(x_{it} | \mathbf{x}_{i, \mathrm{pa}(t)} | \mathbf{\theta}_{t}) p(\mathbf{\theta}_{t}) d \mathbf{\theta}_{t} = \sum_{t} \mathrm{score}(\mathbf{N}_{t, \mathrm{pa}(t)})

이 때 부모 노드가 하나인 경우에는 다음과 같이 간략화된다.

\log p(\mathcal{D} | T) = \sum_{t} w_{\mathrm{pa}(t), t} + \sum_{t} \mathrm{score}(t | 0)

마지막 항은 트리 구조에 대해 불변이므로 무시할 수 있다. 그러므로 가장 가능성 높은 트리를 찾는 것은 대응하는 방향가중치그래프 내의 최대 브랜칭을 찾는 것이 된다.

점수 함수가 사전분포-가능도와 동치라면 \mathrm{score}(s | t) +\mathrm{score}(t | 0) = \mathrm{score}(t | s) + \mathrm{score}(s | 0)이 성립하므로 가중치 행렬이 대칭이 된다. 이 경우 최대 브랜칭은 최대 가중치 포레스트가 된다. 최대 신장 트리를 찾는 알고리즘을 적절히 수정해 적용할 수 있다.

26.3.4. Mixtures of trees

단일 트리는 표현력에 있어서 제약이 있다. 다른 대안은 트리의 혼합 모델을 쓰는 것이다. 이는 기대값 최대화 알고리즘으로 피팅할 수 있다. E 단계에서는 각 데이터의 각 클러스터에서의 책임도를 계산하고, M 단계에서는 초우-리우 알고리즘의 가중치 부여된 버전을 쓴다. 트리의 무한 혼합을 생성하는 것도 가능한데, 시간 복잡도는 O(V^{3})이다. 이는 사후 간선 주변분포에 대한 정확한 베이지안 추론을 가능케 하지만, 은닉 노드에 대한 추론이 계산 가능하지 않다.

26.4. Learning DAG structures

G가 방향비순환그래프일 때 p(G | \mathcal{D})를 계산하는 것을 베이지안 네트워크 구조 학습이라 한다. 여기서는 유실된 데이터와 은닉 변수가 없다고 가정한다. (완전 데이터 가정) 모든 변수가 범주 변수이고 조건부 확률밀도가 테이블임을 가정하지만, 이는 실변수 데이터와 선형-가우시안 조건부 확률밀도에 대해서도 일반화 가능하다.

26.4.1. Markov equivalence

방향그래프 모델이 같은 조건부독립 항을 나타낸다면 마르코프 동치라고 하며, 마르코프 동치인 방향그래프 모델들을 마르코프 동치류라 한다. 이 때 다음이 성립한다.

Theorem. 두 구조가 마르코프 동치일 필요충분조건은 같은 비방향 뼈대 구조를 갖고 같은 v-구조의 집합을 갖는 것이다.

이 때 마르코프 동치류를 단일한 부분방향비순환그래프 / 필수 요소 그래프 / 패턴 으로 표현할 수 있다. 비방향 간선은 가역임을 나타낸다. 방향 간선은 강요 간선이라 불리는데, 이들을 변경하는 것은 v-구조를 변경하기 때문이다. 위 정리의 의미는 데이터로부터 비방향그래프 구조를 학습하더라도 간선의 방향을 유일하게 특정할 수 없다는 것이다.

26.4.2. Exact structural inference

그래프에 대한 정확한 사후분포 p(G | \mathcal{D})을 계산해 보자.

26.4.2.1. Deriving the likelihood

유실된 데이터가 없고 모든 조건부 확률분포가 테이블형이라면 가능도는 다음과 같이 쓸 수 있다.

p(\mathcal{D} | G, \mathbf{\theta}) = \prod_{t=1}^{V} \prod_{c=1}^{C_{t}} \prod_{k=1}^{K_{t}} \theta_{tck}^{N_{tck}}

26.4.2.2. Deriving the marginal likelihood

가능도를 최대화시키는 그래프를 선택하는 것은 완전연결그래프를 선택하므로 과적합의 위험이 있다. 이를 방지하기 위해 최대 주변가능도 p(\mathcal{D} | G)을 최대화시키는 그래프를 선택할 수 있다. 주변가능도를 계산하기 위해서는 매개변수에 대한 사전분포를 특정해야 한다. 이를 위해서는 2가지 가정이 필요한데, 첫째는 전역 사전분포 매개변수 독립성으로 p(\mathbf{\theta}) = \prod_{t=1}^{V} p(\mathbf{\theta}_{t})을 의미한다. 둘째는 지역 사전분포 매개변수 독립성으로 p(\mathbf{\theta}_{t}) = \prod_{c=1}^{C_{t}}p(\mathbf{\theta}_{tc})을 의미한다. 이 가정하에서는 각 조건부 확률밀도함수의 각 행의 사전분포가 디리클레여야 하며, 즉 p(\mathbf{\theta}_{tc}) = \mathrm{Dir}(\mathbf{\theta}_{tc} | \mathbf{\alpha}_{tc})이어야 한다. 이 가정들 하에서, 주변가능도는 다음과 같아진다.

p(\mathcal{D} | G) = \prod_{t=1}^{V} \mathrm{score}(\mathbf{N}_{t, \mathrm{pa}(t)})

\mathrm{score}(\mathbf{N}_{t, \mathrm{pa}(t)}) = \prod_{c=1}^{C_{t}} \frac{B(\mathrm{N}_{tc} + \mathbf{\alpha}_{tc})}{B(\mathbf{\alpha}_{tc})}

즉, 주변가능도가 그래프 구조를 따라 분해된다고 볼 수 있다.

26.4.2.3. Setting the prior

\alpha_{tck}를 어떻게 쓸 것인가? 제프리 사전분포를 쓸 수도 있지만 이는 가능도 등가성(마르코프 동치인 그래프가 같은 주변가능도를 가져야 한다는 성질)을 깬다. 이를 보존하는 사전분포는 디리클레 사전분포로 \alpha_{tck} = \alpha p_{0}(x_{t} = k, \mathbf{x}_{\mathrm{pa}(t)} = c)의 형태를 가진다. 이 때 \alpha > 0동치 표본수이고, p_{0}은 어떠한 사전 결합확률분포이다. 이는 BDe 사전분포(베이지안 디리클레 가능도 동치)라고 불린다.

다른 그래프 구조에 대한 초매개변수를 유도하기 위해서는 매개변수 모듈성, 즉 두 그래프 내에서 어떤 노드가 같은 부모를 갖는다면 매개변수의 두 그래프에 대한 조건부 확률분포는 동일해야 한다는 가정이 필요하다. 이를 가정한다면, 유사 카운트를 합함으로써 임의의 노드 t에 대해 \mathbf{\alpha}_{t}를 계산할 수 있다.

대개 사전분포 p_{0}은 모든 결합 구조에 대해서 균일하다고 가정한다. 이 경우 \alpha_{tck} = \frac{\alpha}{K_{t}C_{t}}이 된다. 이를 BDeu 사전분포(베이지안 디리클레 가능도 동치 균일)이라 한다. 이것이 베이즈 망 구조를 학습하는 데 가장 많이 쓰이는 사전분포이다.

26.4.2.4. Simple worked example

간단한 예에 적용해 볼 수 있다.

26.4.2.5. Example: analysis of the college plans dataset

대학 진학 계획 관련된 데이터셋에 이를 적용해볼 수 있다.

26.4.2.6. The K2 algorithm

노드의 전체 순서를 안다면 각 노드에 대한 부모의 분포를 방향그래프 생성 없이 독립적으로 계산할 수 있다. 이 때 각 노드에 대해서 최적 부모의 집합을 반환하는 알고리즘으로 K2 알고리즘이 있다.

26.4.2.7. Handling non-tabular CPDs

조건부 확률분포가 선형 가우시안이라면 디리클레-다항 모델을 정규-감마 모델로 치환할 수 있다. 이를 조건부 가우시안 방향비순환그래프라 한다.

이외에는 주변가능도를 다음과 같이 BIC 근사를 해야 한다:

\sum_{t} \log p(\mathcal{D}_{t} | \hat{\mathbf{\theta}}_{t}) - \frac{K_{t} C_{t}}{2} \log N

26.4.3. Scaling up to larger graphs

정점 D개에 대한 방향그래프의 수는 f(D) = \sum_{i=1}^{D} (-1)^{i+1} \binom{D}{i} 2^{i (D-i)} f(D-i)로 주어지는데, 이는 정점 수가 조금만 많아져도 엄청나게 크게 증가하므로 근사법을 써야 한다.

26.4.3.1. Approximating the mode of the posterior

전역적으로 최적인 최대사후확률추정 방향비순환그래프는 동적 계획법으로 찾을 수 있지만 이는 O(V2^{V}) 의 시간, 공간복잡도가 든다. 또한, 일반적인 해결책은 NP-완전이다. 그래서 국소적으로 최적인 최대사후확률추정 방향비순환그래프를 찾아야 한다. 가장 흔한 방법은 탐욕적 언덕 오르기 방법으로, 각 단계마다 하나의 간선을 삭제하거나 추가하거나 방향을 반전시킨다. 이것을 사후확률을 가장 증가시키는 방향으로 수행하며, 국소적 최적해에 도달할 때 정지한다.

탐색의 초기값은 최적의 트리로부터 시작할 수도 있다. 속도를 위해, 탐색을 오로지 간선을 추가하는 방향으로만 제한할 수도 있다. 복수의 무작위 재시작을 할 수도 있다.

26.4.3.2. Approximating other functions of the posterior

지식 발견이 목적이라면 최대사후확률추정 방향비순환그래프는 부적절할 수 있다. 더 나은 방법은 각 간선이 존재할 확률 p(G_{st} = 1 | \mathcal{D})을 계산하는 것이다. 이는 동적 계획법으로 풀 수 있지만 역시 O(V2^{V})의 시간 복잡도가 들기 때문에 계산 가능하지 않다. 근사법은 사후분포에서 방향비순환그래프를 메트로폴리스 헤이스팅스로 샘플링하고 각 정점의 쌍에 대해 방향 간선이 존재하는 비율만큼으로 근사하는 것이다. 붕괴 메트로폴리스 헤이스팅스 샘플링을 쓰면 더 빠른데, 노드의 전체 순서를 안다면 노드의 부모를 독립적으로 계산할 수 있으므로 전체 순서만 샘플링하면 되기 때문이다.

26.5. Learning DAG structure with latent variables

유실된 데이터나 은닉 변수가 있는 경우에는 주변가능도는 다음과 같다.

p(\mathcal{D} | G) = \int \sum_{\mathbf{h}} p(\mathcal{D}, \mathbf{h} | \mathbf{\theta}, G) p(\mathbf{\theta} | G)d \mathbf{\theta} = \sum_{\mathbf{h}} \int p(\mathcal{D}, \mathbf{h} | \mathbf{\theta}, G) p(\mathbf{\theta} | G) d \mathbf{\theta}

이는 일반적으로는 계산 가능하지 않다.

26.5.1. Approximating the marginal likelihood when we have missing data

몬테 카를로 법을 쓸 수도 있으나 이는 느리다. 더 좋은 방법들이 있다.

26.5.1.1. BIC approximation

간단한 근사는 다음의 BIC 점수를 이용하는 것이다.

\mathrm{BIC}(G) = \log p(\mathcal{D} | \hat{\mathbf{\theta}}, G) - \frac{\log N}{2} \mathrm{dof}(G)

그러나 이는 주변가능도를 과소추정할 때가 많아 간단한 모델을 선호하게 된다는 단점이 있다.

26.5.1.2. Cheeseman-Stutz approximation

더 나은 방법으로 치즈맨-스투츠 근사가 있다. 은닉 변수를 그 변수들의 기대값으로 채워넣은 뒤 정확한 주변가능도 식을 쓰는 것이다.

p(\mathcal{D} | G) \simeq p(\bar{\mathcal{D}} | G) = \int p(\bar{\mathcal{D}} | \mathbf{\theta}, G)p(\mathbf{\theta} | G) d \mathbf{\theta}

이는 \mathbf{h}의 가능한 값들에 대한 합을 수행하지 않는데 이를 보정하기 위해 우선 다음과 같이 쓴다.

\log p(\mathcal{D} | G) = \log p(\bar{\mathcal{D}} | G) + \log p(\mathcal{D} | G) - \log p(\bar{\mathcal{D}} | G)

그 후 뒤의 2항에 BIC 근사를 하면 다음을 얻는다.

\log p(\mathcal{D} | G) \simeq \log p(\bar{\mathcal{D}} | G) + \log p(\mathcal{D} | \hat{\mathbf{\theta}}, G) - \log p(\bar{\mathcal{D}} | \hat{\mathbf{\theta}}, G)

첫 번째 항은 기대값으로 채워넣어진 데이터를 주변가능도 식에 대입하면 된다. 두 번째 항은 추론 알고리즘으로 계산할 수 있다. 세 번째 항은 기대값으로 채워넣어진 데이터를 가능도 식에 대입하면 된다.

26.5.1.3. Variational Bayes EM

더 정확한 접근법은 변분 베이즈 기대값 최대화 알고리즘이다. 핵심 발상은 다음의 인수분해 조건을 가정하는 것이었음을 떠올려보자:

p(\mathbf{\theta}, \mathbf{z}_{1 : N} | \mathcal{D}) \simeq q(\mathbf{\theta})q(\mathbf{z}) = q(\mathbf{\theta}) \prod_{i} q(\mathbf{z}_{i})

E 단계에서는 q(\mathbf{z}_{i})를 업데이트하고, M 단계에서는 q(\mathbf{\theta})를 업데이트한다. 대응되는 변분 자유 에너지는 로그 주변가능도에 대한 하한을 제공하며, 이 하한이 로그 주변가능도에 대해 BIC 근사나 CS 근사보다 항상 더 좋은 근사를 제공한다.

26.5.1.4. Example: college plans revisited

26.4.2.5에서의 대학 진학 계획 관련 데이터셋에 대해 제한조건-기반 접근으로 더 정확한 분석을 할 수 있다.

26.5.2. Structural EM

데이터가 일부 유실된 경우 구조적 추론을 하는 법은 일반적인 탐색을 한 뒤 주변가능도를 추정하는 것이다. 하지만 이는 대단히 비효율적인데 데이터가 유실된 경우에는 주변가능도도 그 근사치도 인수분해되지 않기 때문이다. 그래서 구조적 기대값 최대화라는 훨씬 효율적인 방법이 있다. 기본 발상은 각 후보의 근방 그래프를 피팅한 뒤 데이터를 채워넣는 대신, 데이터를 한 번만 채워넣고 이 채워넣어진 데이터를 이용해 다른 근방의 점수를 계산하는 것이다. 이는 주변가능도 자체에 대한 근사로는 안 좋을지 몰라도 서로 다른 모델간 주변가능도의 차를 근사하는 데에는 쓸만하고, 최적의 근방을 선택하는 데에는 이것으로 충분하다.

정확히는, \bar{\mathcal{D}}(G_{0}, \hat{\mathbf{\theta}}_{0})를 모델 G_{0}에 최대사후확률추정 매개변수 \hat{\mathbf{\theta}}_{0}로 채워넣어진 데이터라고 하자. 이후 수정된 BIC 점수를 다음과 같이 정의한다.

\mathrm{score}_{\mathrm{BIC}}(G, \mathcal{D}) = \log p(\mathcal{D} | \hat{\mathbf{\theta}}, G) - \frac{\log N}{2} \mathrm{dof}(G) + \log p(G) + \log p(\bar{\mathbf{\theta}}| G)

여기서는 그래프와 매개변수의 로그 사전분포가 포함되었다. 이 때 그래프 G를 G_{0}에 대한 BIC 점수를 기대 데이터에서 계산한 값을 증가시키는 방향으로 선택하면 실제 데이터에서도 BIC 점수가 증가함이 알려져 있다. 즉,

\mathrm{score}_{\mathrm{BIC}}(G, \bar{\mathcal{D}}(G_{0}, \hat{\mathbf{\theta}}_{0})) - \mathrm{score}_{\mathrm{BIC}}(G_{0}, \bar{\mathcal{D}}(G_{0}, \hat{\mathbf{\theta}}_{0})) \leq \mathrm{score}_{\mathrm{BIC}}(G, \mathcal{D}) - \mathrm{score}_{\mathrm{BIC}}(G_{0}, \mathcal{D})이 성립한다.

이를 알고리즘화 하면 다음과 같다. 우선, 어떠한 그래프 G_{0}과 어떤 매개변수 집합 \mathbf{\theta}_{0}으로 초기화를 시킨다. 이후 현재 매개변수를 이용해 데이터를 채워넣는다. 이후 모든 근방의 BIC 점수를 채워넣은 데이터를 이용해 계산한 뒤 최고의 근방을 선택한다. 이후 모델 매개변수를 다시 피팅하고, 데이터를 다시 채워 넣고, 이를 반복한다. 속도를 빠르게 하기 위해, 모델 피팅은 매 단계마다가 아니라 몇 단계마다 수행할 수도 있다.

흥미로운 적용례는 계통발생 트리 구조를 학습하는 것이다. 또는 희소한 혼합 모델을 학습할 수도 있다.

26.5.3. Discovering hidden variables

은닉 변수를 찾아내는 방법을 자동화할 수는 없을까? 은닉 변수가 있다면 그 자식 노드들은 조밀하게 연결되어 있을 가능성이 높다. 이에 착안해서, 가측영역에 대해 구조적 학습을 수행한 뒤 구조적 신호 (조밀하게 연결된 정점의 집합과 같은)를 찾은 뒤 은닉 변수를 도입해 이 집합 내 정점들과 전부 연결시키고 구조적 기대값 최대화로 세부 부분을 피팅하는 것이다. 이 방법은 그리 잘 작동하지는 못하는데, 실제 모델들 내의 클리크가 조밀하게 연결되었다는 보장이 없기 떄문이다.

다른 유용한 직관은 클러스터링에서 착안한다. 평탄한 혼합 모델 (잠재 클래스 모델)에서, 이산 잠재 변수는 그 자식 노드에 대한 압축적 표현을 제공한다. 그래서 자식들과 상호 정보량이 많은 은닉 변수를 만들 수 있다. 이를 위해 잠재 변수에 대한 트리 구조 계층을 만들고는 하는데, 이를 계층적 잠재 클래스 모델이라 한다. 이는 탐욕적 국소적 탐색 알고리즘을 써서 정점이나 간선들을 추가하거나 삭제하여 이러한 구조를 학습한다. 응집적 계층 클러스터링에 기반한 더 빠른 방법도 존재한다.

다른 방법도 있다. 이 때는 관측 데이터를 리프로 제한시키지 않는데, 관측된 데이터의 초우-리우 트리로부터 시작해서 은닉 변수를 추가하면서 내부 노드들 간 고차 의존성을 포착한다. 이는 훨씬 더 조밀한 모델을 형성하고, 혼합 모델 등의 방법들에 비해 예측 정확도도 더 높고, 데이터가 트리에서 생성되었다면 정확한 잠재 트리 구조를 복원할 수도 있다. 하지만 은닉 변수와 관측 변수의 개수가 같아야 한다는 조건이 있다. 또한, 가측 변수가 가우시안이면 은닉 변수도 가우시안이어야 한다.

26.5.4. Case study: Google’s Rephil

구글의 레필이라는 대형 방향그래프모델이 이 용례이다. 이는 함께 가동되는 정점들은 함께 묶여 있을 것이다라는 직관에 기반한다.

26.5.5. Structural equation models

구조적 방정식 모델은 방향 혼합 그래프의 특수한 예로, 모든 조건부확률분포가 선형 가우시안이고 양방향 간선은 전부 상호 연관된 가우시안 노이즈를 나타낸다. 이러한 모델들은 경로 다이어그램이라고도 한다. 순환이 있을 수도 있으며 이는 피드백 순환으로 나타내어진다. 이 자체로는 인과관계적인 요소가 없으며 그저 결합 가우시안을 특정하는 방법 중 하나일 뿐이다. 구조적 방정식 모델은 다음과 같은 연속된 전체 조건부함수로 정의할 수 있다:

x_{i} = \mu_{i} + \sum_{j \neq i} w_{ij}x_{j} + \epsilon_{i} (\mathbf{\epsilon} \sim \mathcal{N}(\mathbf{0}, \mathbf{\Phi}))

이를 행렬 형식으로 쓰면 다음과 같다: \mathbf{x} = (\mathbf{I} - \mathbf{W})^{-1}(\mathbf{\epsilon} + \mathbf{\mu})

그러므로 결합분포는 p(\mathbf{x}) = \mathcal{N}(\mathbf{\mu}, \mathbf{\Sigma})로 나타내어진다. (\mathbf{\Sigma} = (\mathbf{I} - \mathbf{W})^{-1}\mathbf{\Phi}(\mathbf{I} - \mathbf{W})^{-T})

이 때 |w_{ij}|>0인 경우 X_{j} \to X_{i} 간선을 그린다. \mathbf{W}가 하삼각행렬이라면 그래프는 비순환이 된다. 대각행렬이라면 이는 가우시안 방향그래프모델과 같은 재귀 모델이다. 대각 행렬이 아니라면 주대각선에 있지 않은 원소간 양방향 간선을 그린다. 이는 상호 연관을 나타낸다.

구조적 방정식 모델을 사용할 때에는 보통 변수들을 잠재 변수 Z_{t}노출 변수 Y_{t}로 나눈다. 소프트웨어 구현에는 LISREL이라는 패키지가 주로 쓰인다.

구조적 방정식 모델은 인자 분석 모델과 밀접한 연관이 있다. 기본적 차이점은 인자 분석 모델에서 잠재 가우시안은 저랭크 공분산 행렬이고, 관측 노이즈는 대각 공분산을 가진다. 구조적 방정식 모델에서는 잠재 가우시안의 공분산은 희소한 촐스키 분해를 가지고, 관측 노이즈의 공분산 행렬이 대각이 아닐 수 있다. 구조적 방정식 모델은 여러 방법으로 확장될 수 있다.

26.6. Learning causal DAGs

인과 모델은 계에 대한 조정의 효과를 예측할 수 있는 모델로, 연관적 모델보다 훨씬 강력하다. 보통 방향비순환그래프로 모델링되고는 한다.

26.6.1. Causal interpretation of DAGs

인과 모델을 방향비순환그래프로 모델링할 때는 방향간선 A \to B는 “A가 직접적으로 B를 야기한다”를 의미한다. 이를 인과 마르코프 가정이라 한다. 이 때 모든 연관 변수는 모델에 포함되어 있고 미지 혼동자는 없다고 가정한다. 이를 인과 충분성 가정이라 한다. 이 가정들 하에서, 방향비순환그래프를 이용해 인과 관계에 대한 질문에 답할 수 있다. 핵심은 완전 간섭으로, 특정한 변수를 특정한 값으로 세팅해 버리는 것이다. 표현은 do 식 표현을 쓰며, 이는 그래프 수술로 모델링된다. 엄밀하게는 다음과 같다.

Theorem. 인과 마르코프 가정하에, p(X_{i} | \mathrm{do}(X_{j}))을 계산하려면 X_{j}로 들어오는 간선을 없애버린 뒤 표준적 확률적 추론을 하면 된다.

이를 그래프에 동작 정점을 추가하는 식으로 확장할 수도 있는데 이를 증강 방향비순환그래프라 한다. 동작이 복수의 정점에 영향을 주도록 한다면 살찐 손 간섭이라 한다.

26.6.2. Using causal DAGs to resolve Simpson’s paradox

심슨의 모순이라는 문제가 있는데 이는 두 변수 간 임의의 통계적 관계는 분석에 있어 인자를 추가함으로써 역전시킬 수 있다는 패러독스이다. 인과 방향비순환그래프모델을 이용해 이를 해결할 수 있다. 정점간 백도어 경로를 없애기 위해 혼동 변수조건을 거는 것이다.

26.6.3. Learning causal DAG structures

인과적 방향비순환그래프 구조를 어떻게 학습해야 할까?

26.6.3.1. Learning from observational data

데이터가 있어도 원본 방향비순환그래프에 대해 마르코프 동치인 그래프까지밖에 복원을 못한다. 그렇다면 마르코프 동치류라도 추정하려면 어떻게 해야 하나? 탐욕적 동치류 탐색이 쓰인다. 이 때 생성 분포 p가 생성 방향비순환그래프 G에 대해 신뢰성 있다는 조건 (안정된 분포라고도 한다), 즉, I(p) = I(G)임이 보장되어야 한다.

확률적 방향비순환그래프를 학습하면 그걸로는 뭘 하나? 전체 그래프를 복원하는 대신 간선 주변분포의 인과적 버전에만 집중할 수 있다. 즉, 한 정점의 다른 정점에 대한 인과관계의 크기를 계산할 수 있다. 방향비순환그래프를 모른다면? 데이터에서 동치류를 학습하고, 동치류 내의 모든 방향비순환그래프를 나열하고, do 식을 통해 각 방향비순환그래프 내에서 어떠한 정점의 다른 정점에 대한 인과 크기를 계산한 뒤 이것의 최소값을 하한으로 쓴다. 모든 방향비순환그래프를 계산하는 것은 대개 불가능하지만 방향비순환그래프가 없을 시의 간섭식 (IDA)를 이용해 국소적 근방은 계산할 수가 있다.

26.6.3.2. Learning from interventional data

방향비순환그래프를 동치류와 구분하려면 특정 변수가 세팅되고 그 결과값이 측정된 간섭 데이터가 필요하다. 이 때 일반적인 베이지안 점수 기준을 수정해서 관측 데이터와 실험 데이터의 혼합으로부터 학습할 수 있도록 하는 것은 간단하다. 조건부확률분포의 매개변수의 충족 통계량을 계산할 때 간섭이 일어난 정점만 건너뛰면 된다. 예를 들어, 테이블 조건부확률분포를 쓸 때는 실측 개수를 다음과 같이 수정한다: N_{tck} = \sum_{i : x_{it} not set} \mathbf{1}_{x_{it} = k, \mathbf{x}_{i, pa(t)} = c}

위의 방법은 간섭이 완전하다고 가정하는데, 실제로는 그렇지 않을 때가 많으므로 방향비순환그래프에 간섭 정점을 더한 뒤 증강된 방향비순환그래프를 학습하는 식으로 이를 보정한다.

26.7. Learning undirected Gaussian graphical models

비방향그래프모델을 학습하는 것은 방향비순환그래프모델을 학습하는 것보다 어떤 면에서는 더 쉽다. 순환을 걱정할 필요가 없기 때문이다. 그러나 가능도가 인수분해되지 않는다는 점에서는 더 어렵다. 이는 탐욕적 탐색이나 마르코프 연쇄 몬테 카를로 샘플링과 같은 방법을 적용하기 불가능하게 한다. 이 절에서는 가우시안 무작위 장법으로 이를 해결한다.

26.7.1. MLE for a GGM

먼저 매개변수 추정을 다뤄야 할 필요가 있다. 가우시안 그래프 모델에 대한 최대가능도추정을 계산하는 것은 공분산 선택이라 한다. 먼저 정밀도 행렬 \mathbf{\Omega} = \mathbf{\Sigma}^{-1}에 대한 가능도는 l(\mathbf{\Omega}) = \log \mathrm{det}(\mathbf{\Omega}) - \mathrm{tr}(\mathbf{S}\mathbf{\Omega})로 주어진다. 이 때 이의 경사는 \nabla l(\mathbf{\Omega}) = \mathbf{\Omega}^{-1} - \mathbf{S}이 된다. 추가로 G_{st} = 0 \to \Omega_{st} = 0\mathbf{\Omega}이 양의 정부호라는 조건이 필요하다.

이 때 최대가능도추정은 다음의 성질을 만족한다. G_{st}=1이거나 s = t이면 \Sigma_{st} = S_{st}이고, G_{st} = 0이면 \Omega_{st} = 0. 그러므로 \mathbf{\Sigma}\mathbf{S}의 양의 정부호 행렬 완비화라 한다.

26.7.2. Graphical lasso

희소한 가우시안 무작위 장 구조를 학습하는 하나의 방법은 정밀도 행렬의 0과 그래프 내 간선의 부재에 일대일대응이 성립한다는 것을 이용한다. 즉, 정밀도 행렬에 0을 유도하는 목적 함수 J(\mathbf{\Omega}) = -\log \mathrm{det} \mathbf{\Omega} + \mathrm{tr}(\mathbf{S} \mathbf{\Omega}) + \lambda \lVert \mathbf{\Omega} \rVert_{1}를 써서 희소한 그래프 구조를 학습할 수 있다. 이를 그래프 라쏘 또는 글라쏘라 한다.

목적 함수는 볼록이지만, 이는 매끄럽지 않다. 이를 최적화하는 방법 중 하나는 라쏘 최적화된 경사 하강법을 쓰는 것이 있다.

방향비순환그래프모델과 비교해 보면, 방향비순환그래프는 데이터의 간섭성은 잘 모델링할 수 있지만, 피드백 순환은 모델링할 수 없다. 베이지안 정보량 기준을 사용해 최적의 비방향그래프모델을 선택할 수도 있고, 역으로 사후분포에서 여러 방향비순환그래프를 샘플링할 수도 있다.

26.7.3. Bayesian inference for GGM structure

그래프 라쏘는 충분히 빠르긴 하지만 구조에 대한 점 추정만을 제공한다. 또한, 이 추정자는 모델의 참값에 일관적이지 않기 때문에 데이터가 무한히 확보되어도 그래프의 참값을 복원할 수 없다. 그래서 매개변수를 적분해 빼내고 그래프의 공간에 대해 사후확률추론을 수행해 p(G | \mathcal{D})을 계산하고는 한다. 이후 사후분포에 대한 정보들 (사후간선주변분포 p(G_{ij} = 1 | \mathcal{D}) 같은 정보들)을 추출한다.

그래프가 분해 가능하고 켤레사전분포를 쓸 수 있다면 주변가능도를 닫힌 형태로 계산할 수 있다. 또한, 그래프의 분해 가능한 근방들을 효과적으로 특정할 수 있다. 이는 추계적 국소적 탐색을 효율적으로 수행해서 사후분포를 잘 근사할 수 있다는 것을 의미한다. 하지만 분해 가능한 그래프의 수가 비방향그래프 중 많지는 않기 때문에 한계점이 있다. 그래프가 분해 가능하지 않은 경우에는 많은 방법들이 주변가능도에 대한 몬테 카를로 근사를 수행하기 때문에 큰 그래프로 확장 가능하지 않다. 그래서 경사 기반 방법을 수정해서 최대사후확률추정을 찾고는 한다. 속도를 더 빠르게 하기 위해 대각 라플라스 근사도 사용한다. 이는 그래프 라쏘보다 좋은 성능을 보인다.

26.7.4. Handling non-Gaussian data using copulas

그래프 라쏘와 그 변형들은 데이터가 결합 가우시안인 경우로 적용이 한정되지만, 비 가우시안인 경우로도 확장할 수 있다. (연속성은 필요하다) 기본 아이디어는 변수마다 일변수 단조변환을 하나씩 구성해 변환된 데이터가 결합 가우시안이 되도록 하는 것이다. 이것이 가능한 경우를 비초자연적 분포라 하며, 가우시안 코풀라와 동치이다. 변환을 한 뒤에는 상관 행렬을 계산할 수 있고 글라쏘를 적용하면 된다. 이는 일관적 추정자임이 알려져 있다.

26.8. Learning undirected discrete graphical models

비방향그래프 모델이 이산적일 경우는 분할 함수가 계산가능하지 않기 때문에 학습이 더 힘들다. 가우시안인 경우에는 O(V^{3})이면 가능하다. 아래에는 시도된 방법들을 논한다.

26.8.1. Graphical lasso for MRFs/CRFs

그래프 라쏘법을 이산적 마르코프 무작위 장이나 조건적 무작위 장으로 확장할 수 있다. 이 때에는 그래프의 간선마다 매개변수의 집합이 연관되어 있기 때문에 그룹 라쏘의 그래프 버전을 사용해야 한다. 희소 구조를 학습하기 위해서는 다음의 목적 함수를 최소화할 수 있다.

J = -\sum_{i=1}^{N} [\sum_{t} \log \phi_{t}(y_{it}, \mathbf{x}_{i}, \mathbf{v}_{t}) + \sum_{s=1}^{V} \sum_{t = s+1}^{V} \log \phi_{st} (y_{is}, y_{it}, \mathbf{x}_{i}, \mathbf{w}_{st})] + \lambda_{1} \sum_{s=1}^{V} \sum_{t = s+1}^{V} \lVert \mathbf{w}_{st} \rVert_{p} + \lambda_{2} \sum_{t=1}^{V} \lVert \mathbf{v}_{t} \rVert_{2}^{2}

이 목적 함수는 볼록이지만 계산하는 데 많은 시간이 든다. 경사를 구하는 데 추론이 필요하기 때문이다. 그래서 이 함수를 너무 많이 호출하는 것은 좋지 않다. 아니면 볼록 믿음 전파와 같은 근사 추론 방법도 쓸 수 있다. 또는 그룹 라쏘 징벌항을 쓸 수도 있다.

26.8.2. Thin junction trees

희소 그래프라고 트리 두께가 작은 것은 아니다. 이는 추론조차 계산 불가능할 수 있다는 것을 의미한다. 얇은 접합 트리 은 접근법이 있으나 정확한 추론은 역시 어렵다. 또 다른 방법으로는 회로 복잡도가 낮은 모델을 학습하는 방법이 있다. 이는 트리 두께는 높을 수 있지만 맥락 의존적 독립성을 이용해 빠른 추론을 가능케 한다.

요점 정리

  • 그래프 모델의 구조를 학습할 수 있다.
  • 최대사후확률추정 그래프나 정확한 간선주변분포의 사후분포를 계산하는 것은 일반적으로 계산 가능하지 않기 때문에 여러 휴리스틱을 쓴다.
  • 트리는 전체 결합확률분포에 대한 학습을 효율적으로 할 수 있으며 이후에 정확한 추론까지 가능하다.
  • 방향비순환그래프일 때 여러 방법으로 그래프 구조를 학습할 수 있다.
  • 유실된 데이터나 은닉 변수가 있으면 근사법을 사용한다.
  • 인과 모델은 계에 대한 조정의 효과를 예측할 수 있는 모델로, 연관적 모델보다 훨씬 강력하다.
  • 비방향그래프모델은 가우시안 무작위 장법 등으로 학습한다.
  • 비방향그래프 모델이 이산적일 경우엔 더 어렵다. 여러 근사법이 있다.

답글 남기기

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

WordPress.com 로고

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

Google photo

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

Twitter 사진

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

Facebook 사진

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

%s에 연결하는 중