베이지안 네트워크

Bayesian network, Bayes network, belief network; 베이지안 네트워크, 베이즈 네트워크, 신뢰 네트워크
확률 변수들을 노드로, 직접적인 조건부 의존 관계를 방향 있는 간선으로 나타낸 방향성 비순환 그래프와, 각 노드의 조건부 확률표로 이루어진 확률 모델

베이지안 네트워크는 여러 확률 변수의 결합 확률 분포를 그래프로 간결하게 표현하는 확률 그래프 모델(probabilistic graphical model)이다. "비가 오면 잔디가 젖는다", "질병이 있으면 증상이 나타난다"처럼 변수 사이의 직접 영향 관계를 화살표로 그리고, 각 변수에 부모 변수가 주어졌을 때의 조건부 확률만 적어 두면, 전체 변수의 결합 분포가 정해진다. 그 위에서 관측된 증거(잔디가 젖었다)로부터 관측되지 않은 원인(비가 왔을까)의 확률을 계산할 수 있다. 복잡한 문제에 베이즈 정리를 체계적으로 적용하는 장치라 할 수 있다.

이름은 주데아 펄(Judea Pearl)이 1985년 붙였다.^[1] 1980년대 후반 펄의 《Probabilistic Reasoning in Intelligent Systems》(1988)와 리처드 니어폴리탄의 《Probabilistic Reasoning in Expert Systems》(1989)가 이론을 정리하면서 독립된 연구 분야가 되었다. 규칙 기반 전문가 시스템이 불확실성을 다루기 어려웠던 문제를 확률론 위에서 풀었고, 불확실성 아래 추론하는 인공지능의 표준 도구가 되었다. 펄은 확률적·인과적 추론의 계산 체계를 세운 공로로 2011년 튜링 상을 받았다.^[2]

정의

베이지안 네트워크는 두 부분으로 이루어진다.

구조: 방향성 비순환 그래프(DAG) $G = (V, E)$ . 노드는 확률 변수, 간선 $X \to Y$ 는 X가 Y에 직접 영향을 준다는 뜻이다. X를 Y의 부모라 한다.
매개변수: 각 노드 $X_{i}$ 의 조건부 확률 분포 $P (X_{i} ∣ Pa (X_{i}))$ . 이산 변수라면 부모 값의 조합마다 확률을 적은 조건부 확률표(CPT)가 된다.

이 둘이 정하는 결합 분포는 각 노드의 조건부 확률을 곱한 것이다(인수분해 정의).

$P (X_{1}, \dots, X_{n}) = \prod_{i = 1}^{n} P (X_{i} ∣ Pa (X_{i}))$

일반적인 확률의 연쇄 법칙은 $P (X_{1}, \dots, X_{n}) = \prod_{i} P (X_{i} ∣ X_{1}, \dots, X_{i - 1})$ 이므로, 베이지안 네트워크는 "각 변수는 부모가 주어지면 나머지 앞선 변수들과 독립"이라는 가정을 그래프로 나타낸 것이다. 이를 국소 마르코프 성질(local Markov property)이라 한다. 각 변수는 부모가 주어지면 자신의 자손이 아닌 모든 변수와 조건부 독립이다.

표현의 경제성

이진 변수 10개의 결합 분포를 표로 적으면 $2^{10} = 1024$ 칸이 필요하다. 각 변수의 부모가 많아야 3개라면 베이지안 네트워크로는 많아야 $10 \times 2^{3} = 80$ 개 값이면 된다. 변수 사이 의존 관계가 드물수록 이득이 커지고, 사람이 그래프를 보고 모델을 이해하거나 전문가에게 확률을 물어 채우기도 쉽다.

예: 스프링클러 네트워크

비(R), 스프링클러(S), 젖은 잔디(G) 세 이진 변수를 생각하자. 비가 오면 스프링클러를 덜 켜고, 비와 스프링클러 둘 다 잔디를 적신다. 그래프는 R→S, R→G, S→G다.

조건부 확률	값
P(R=참)	0.2
P(S=참 ∣ R=참) / P(S=참 ∣ R=거짓)	0.01 / 0.4
P(G=참 ∣ S=참, R=참)	0.99
P(G=참 ∣ S=참, R=거짓)	0.9
P(G=참 ∣ S=거짓, R=참)	0.8
P(G=참 ∣ S=거짓, R=거짓)	0.0

결합 분포는 $P (G, S, R) = P (G ∣ S, R) P (S ∣ R) P (R)$ 이다. "잔디가 젖었을 때 비가 왔을 확률"은 스프링클러 변수를 합해 없앤 뒤 계산한다.

$P (R = T ∣ G = T) = \frac{\sum_{s} P (G = T, S = s, R = T)}{\sum_{s, r} P (G = T, S = s, R = r)} = \frac{0.00198 + 0.1584}{0.00198 + 0.1584 + 0.288 + 0} \approx 0.358$

잔디가 젖었다는 증거로 비 올 확률이 사전 확률 0.2에서 약 0.36으로 올랐다. 이처럼 결과에서 원인을 거꾸로 추정하는 것이 베이지안 네트워크의 대표적인 쓰임이다.

조건부 독립과 d-분리

그래프만 보고 어떤 변수들이 조건부 독립인지 판정하는 규칙이 d-분리(d-separation, 방향 분리)다. 세 노드가 이어지는 방식은 세 가지뿐이다.

연결	모양	예	가운데 노드 B를 관측하면
사슬(chain)	A → B → C	흡연 → 폐암 → 기침	A와 C가 독립이 된다(경로가 막힘)
분기(fork, 공통 원인)	A ← B → C	비 → 우산, 비 → 젖은 도로	A와 C가 독립이 된다(경로가 막힘)
충돌(collider, 공통 결과)	A → B ← C	비 → 젖은 잔디 ← 스프링클러	원래 독립이던 A와 C가 의존하게 된다(경로가 열림)

충돌 노드의 성질이 직관과 어긋나는 부분이다. 비와 스프링클러는 서로 독립이지만, 잔디가 젖은 것을 안 상태에서 스프링클러가 켜져 있었다는 사실을 알면 비 올 확률은 내려간다. 원인 하나가 결과를 설명해 버려 다른 원인의 가능성이 줄어드는 이 현상을 해명 효과(explaining away)라 한다. 충돌 노드의 자손을 관측해도 경로가 열린다.

두 노드 사이의 모든 경로가 관측 집합 Z에 의해 막혀 있으면 두 노드는 Z가 주어졌을 때 d-분리되며, 이 경우 조건부 독립이 보장된다. 어떤 노드를 나머지 네트워크 전체와 독립으로 만드는 최소 집합은 부모, 자식, 자식의 다른 부모로 이루어지며, 이를 마르코프 블랭킷(Markov blanket)이라 한다.

추론

추론은 증거 변수 $e$ 가 주어졌을 때 질의 변수 $X$ 의 사후 분포 $P (X ∣ e)$ 를 구하는 일이다. 가장 그럴듯한 전체 설명(MPE, MAP)을 찾는 것도 추론에 속한다.

정확 추론

열거(enumeration): 결합 분포를 인수분해 식으로 모두 펼쳐 숨은 변수를 합한다. 변수 수에 지수적인 시간이 든다.
변수 소거(variable elimination): 합을 곱 안쪽으로 밀어 넣고 중간 결과(인자)를 재사용해 숨은 변수를 하나씩 없앤다. 동적 계획법과 같은 발상이다.
신뢰 전파(belief propagation): 펄이 제안한 메시지 전달 알고리즘. 간선을 따라 이웃 노드에 확률 메시지를 보내며, 무방향 순환이 없는 폴리트리(polytree)에서는 정확하고 노드 수에 선형 시간이다.
접합 트리(junction tree, 클리크 트리) 알고리즘: 그래프를 클리크들의 트리로 바꾼 뒤 메시지를 전달한다. 한 번 계산해 두면 여러 질의에 답하고 새 증거를 빠르게 반영할 수 있다.

정확 추론의 복잡도는 그래프의 트리폭(treewidth)에 지수적이다. 그레고리 쿠퍼는 1990년 일반 베이지안 네트워크의 정확 추론이 NP-난해임을 증명했고,^[3] 폴 대검과 마이클 루비는 1993년 일정 오차 안의 근사 추론조차 일반적으로 NP-난해임을 보였다.^[4] 그래서 실제로는 구조에 제약을 두거나 근사 추론을 쓴다.

근사 추론

표본 추출: 네트워크를 위상 순서대로 표본을 뽑는 사전 표본 추출, 증거와 맞지 않는 표본을 버리는 기각 표본 추출, 증거의 가능도로 가중치를 주는 가능도 가중(likelihood weighting)
마르코프 연쇄 몬테카를로(MCMC): 깁스 표집으로 마르코프 블랭킷만 보고 변수를 하나씩 다시 뽑는다(몬테카를로 시뮬레이션 참고)
루프 있는 신뢰 전파(loopy belief propagation): 순환이 있는 그래프에서 신뢰 전파를 반복 적용. 수렴이 보장되지 않지만 실전에서 잘 통하는 경우가 많다
변분 추론: 다루기 쉬운 분포족으로 사후 분포를 근사하는 최적화 문제로 바꾼다

학습

매개변수 학습

구조가 정해져 있으면 데이터로 조건부 확률표를 추정한다. 완전한 데이터라면 최대 가능도 추정은 단순히 빈도를 세는 것이다. 예를 들어 $\hat{P} (S = T ∣ R = T)$ 는 비 온 날 중 스프링클러가 켜진 날의 비율이다. 데이터가 적을 때는 디리클레 사전 분포를 둔 베이즈 추정으로 0 확률을 피한다. 관측되지 않은 변수나 결측값이 있으면 기댓값 최대화(EM) 알고리즘으로 숨은 변수의 기댓값 계산과 매개변수 최대화를 번갈아 한다.

구조 학습

그래프 구조 자체를 데이터에서 찾는 것은 훨씬 어렵다. 가능한 DAG의 수가 변수 수에 대해 초지수적으로 늘어나고, 최적 구조 찾기는 일반적으로 NP-난해다.

제약 기반 방법: 데이터에서 조건부 독립 검정을 해 간선을 지우고, 충돌 구조(A → B ← C)를 찾아 방향을 정한다. 사슬과 분기는 같은 독립 관계를 만들어 데이터만으로는 구별되지 않지만, 충돌은 구별되기 때문이다. 펄과 레바네의 복원 알고리즘에서 출발했고 PC 알고리즘이 대표적이다.
점수 기반 방법: BIC, BDeu 같은 점수를 정의하고 탐욕적 국소 탐색, MCMC, 정수 계획법으로 점수가 가장 높은 구조를 찾는다.
전문가 지식과 데이터를 결합하는 방식도 흔하다.

인과 추론과의 관계

베이지안 네트워크의 간선이 꼭 인과를 뜻하지는 않는다. A → B → C와 A ← B ← C는 같은 조건부 독립 관계를 표현하므로 통계적으로 같은 모델이다. 간선이 실제 인과 관계를 나타낸다고 약속한 것이 인과 베이지안 네트워크(인과 그래프)다.

인과 네트워크에서는 "관찰"과 "개입"을 구분한다. 변수 X를 외부에서 강제로 x로 정하는 개입은 do 연산자 $d o (X = x)$ 로 쓰며, 그래프에서 X로 들어오는 간선을 모두 끊고 X를 x로 고정한 것과 같다. 스프링클러 예에서 "잔디가 젖은 것을 보았다"는 비의 확률을 높이지만, "호스로 잔디를 적셨다"( $d o (G = T)$ )는 비의 확률을 바꾸지 않는다.

$P (R ∣ d o (G = T)) = P (R)$

관찰 데이터만으로 개입 효과를 계산할 수 있는지는 그래프 구조에 달려 있다. X에서 Y로 가는 뒷문 경로(X로 들어오는 화살표로 시작하는 경로)를 모두 막는 변수 집합 Z를 관측할 수 있으면 뒷문 기준(back-door criterion)에 따라 다음과 같이 보정할 수 있다.

$P (Y ∣ d o (X = x)) = \sum_{z} P (Y ∣ X = x, Z = z) P (Z = z)$

더 일반적인 경우는 펄의 do-계산법(do-calculus) 세 규칙으로 판정한다. 펄은 이 체계를 《Causality》(2000)에서 정리했고, 인과 추론은 이후 역학, 경제학, 설명 가능한 인공지능, 공정성 연구로 퍼졌다. 상관관계와 인과관계를 혼동해 생기는 심슨의 역설도 이 틀로 설명된다.

응용

의료 진단: 질병과 증상, 검사 결과의 관계를 모델링해 증상으로부터 질병 확률을 계산
고장 진단: 장비 부품 상태와 경보 신호의 관계로 고장 원인 추정
위험 평가와 의사결정 지원: 영향 다이어그램으로 불확실성 아래 선택지 비교
스팸 필터와 문서 분류: 나이브 베이즈 분류기
생물정보학: 유전자 조절 네트워크 추정
음성 인식, 추적: 동적 베이지안 네트워크(은닉 마르코프 모델, 칼만 필터)

파이썬 예: 열거로 추론하기

from itertools import product

P_R = {True: 0.2, False: 0.8}
P_S = {True: {True: 0.01, False: 0.99},      # P(S | R=True)
       False: {True: 0.4, False: 0.6}}       # P(S | R=False)
P_G = {(True, True): 0.99, (True, False): 0.9,   # P(G=True | S, R)
       (False, True): 0.8, (False, False): 0.0}

def joint(r, s, g):
    pg = P_G[(s, r)] if g else 1 - P_G[(s, r)]
    return P_R[r] * P_S[r][s] * pg               # 인수분해 정의

num = sum(joint(True, s, True) for s in (True, False))
den = sum(joint(r, s, True) for r, s in product((True, False), repeat=2))
print(round(num / den, 4))                       # P(R=True | G=True) = 0.3577

실무에서는 pgmpy(파이썬), bnlearn(R), 상용 도구인 Netica, Hugin 등을 쓴다.

같이 보기

각주

↑ Judea Pearl, 〈Bayesian Networks: A Model of Self-Activated Memory for Evidential Reasoning〉, Proceedings of the 7th Conference of the Cognitive Science Society, 1985. UCLA CSD-850017
↑ Judea Pearl, A.M. Turing Award, ACM.
↑ Gregory F. Cooper, 〈The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks〉, 《Artificial Intelligence》 42(2-3), 1990. doi:10.1016/0004-3702(90)90060-D
↑ Paul Dagum, Michael Luby, 〈Approximating probabilistic inference in Bayesian belief networks is NP-hard〉, 《Artificial Intelligence》 60(1), 1993. doi:10.1016/0004-3702(93)90036-B

참고 문헌

Judea Pearl, 《Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference》, Morgan Kaufmann, 1988.
Judea Pearl, 《Causality: Models, Reasoning, and Inference》, Cambridge University Press, 2000.
Daphne Koller, Nir Friedman, 《Probabilistic Graphical Models: Principles and Techniques》, MIT Press, 2009.
Stuart Russell, Peter Norvig, 《Artificial Intelligence: A Modern Approach》 4판, 13장, Pearson, 2021.

[pearl85-1] Judea Pearl, 〈Bayesian Networks: A Model of Self-Activated Memory for Evidential Reasoning〉, Proceedings of the 7th Conference of the Cognitive Science Society, 1985. UCLA CSD-850017

[2] Judea Pearl, A.M. Turing Award, ACM.

[3] Gregory F. Cooper, 〈The Computational Complexity of Probabilistic Inference Using Bayesian Belief Networks〉, 《Artificial Intelligence》 42(2-3), 1990. doi:10.1016/0004-3702(90)90060-D

[4] Paul Dagum, Michael Luby, 〈Approximating probabilistic inference in Bayesian belief networks is NP-hard〉, 《Artificial Intelligence》 60(1), 1993. doi:10.1016/0004-3702(93)90036-B

[1]

[2]

[3]

[4]

모델	베이지안 네트워크와의 관계
나이브 베이즈	클래스 노드 하나가 모든 특징 노드의 부모인 가장 단순한 베이지안 네트워크
은닉 마르코프 모델	시간에 따라 반복되는 구조를 가진 동적 베이지안 네트워크(DBN)의 특수한 경우. 칼만 필터도 연속 변수 DBN이다
마르코프 네트워크(마르코프 랜덤 필드)	방향 없는 그래프로 나타내는 확률 그래프 모델. 대칭적인 상호작용(이미지 픽셀 등)에 적합하다. 깁스 분포 형태로 표현된다
영향 다이어그램(influence diagram)	결정 노드와 효용 노드를 추가해 불확실성 아래 의사결정을 다룬다
변분 오토인코더 등 심층 생성 모델	신경망으로 조건부 분포를 매개변수화한 방향 그래프 모델로 볼 수 있다

정의