마르코프 확률장

통계 컴퓨터 그래픽스 마지막 수정: 2026-08-02 05:52:09

1. 개요[편집]

픽셀 하나의 값은 온 세상이 아니라 이웃 넷만 알면 된다. 이 한 문장이 영상 처리 20년을 먹여 살렸다.

마르코프 확률장(Markov random field, MRF. 마르코프 랜덤 필드)은 무향 그래프 위에 정의된 확률변수 집합으로, 각 변수가 자신의 이웃이 주어지면 나머지 전부와 조건부 독립이 되는 성질을 갖는 모형이다. 시간 축을 따라 한 방향으로 흐르는 마르코프 연쇄를 임의의 그래프(특히 2차원 격자)로 일반화한 것이며, 영상 분할·잡음제거·스테레오 정합처럼 “이웃한 것끼리는 비슷할 것”이라는 사전지식이 문제의 핵심인 영역에서 표준 언어로 쓰인다.

방향성 그래프(베이즈망)와의 차이가 본질적이다. 격자 위 픽셀 사이에는 인과 방향이라는 게 없고, 순환이 어디에나 있어서 비순환 방향그래프로 표현할 수 없다. 무향이라는 것이 MRF의 선택이 아니라 문제의 성질이다.

2. 국소 성질과 해머슬리-클리퍼드 정리[편집]

무향 그래프 $G=(V,E)$ 위 변수 $X = \{X_v\}$ 에 대해 세 층위의 마르코프 성질이 있다.

쌍별: 간선으로 이어지지 않은 두 정점은 나머지 전부가 주어지면 독립.
국소: $X_v \perp X_{V\setminus \mathrm{cl}(v)} \mid X_{N(v)}$ . 이웃 $N(v)$ 가 곧 마르코프 담요다.
전역: 집합 $S$ 가 $A$ 와 $B$ 를 그래프에서 분리하면 $X_A \perp X_B \mid X_S$ .

일반적으로 전역 ⟹ 국소 ⟹ 쌍별이고, 역방향은 조건이 붙는다. 그리고 이 모형이 실제로 쓸모 있게 되는 지점이 해머슬리-클리퍼드 정리다.

확률밀도가 모든 배치에서 양수( $P(x)>0$ )라면, $X$ 가 $G$ 에 대한 MRF인 것과 $P$ 가 $G$ 의 클리크에 대한 깁스 분포인 것이 동치다.

P(x) \;=\; \frac{1}{Z}\exp\!\Big(-\sum_{c\in\mathcal{C}} V_c(x_c)\Big), \qquad Z = \sum_{x}\exp\!\Big(-\sum_c V_c(x_c)\Big)

여기서 $\mathcal{C}$ 는 그래프의 클리크 집합, $V_c$ 는 그 위의 퍼텐셜, $Z$ 는 분배함수다. 이 정리가 하는 일은 “국소 조건부 독립”이라는 정성적 서술을 “에너지의 합”이라는 계산 가능한 형태로 바꿔치기하는 것이다. 조건부 독립 구조만 설계하면 에너지를 클리크별로 조립하면 된다는 보장을 얻는다.

양성 조건은 장식이 아니다. $P(x)=0$ 인 배치가 있으면 정리가 실제로 깨지고, 무스리스(Moussouris, 1974)가 4-사이클 위에서 쌍별 마르코프 성질을 만족하지만 어떤 쌍별 인수분해로도 표현되지 않는 반례를 만들었다. 하드 제약(금지된 조합)을 에너지 $+\infty$ 로 넣는 순간 이 정리의 보호를 벗어난다는 뜻이라, 실무에서는 아주 큰 유한 벌점으로 대체하는 것이 국룰이다.¹

3. 에너지 설계 — 데이터항과 평활항[편집]

응용에서 압도적으로 많이 쓰이는 형태는 클리크를 정점과 간선까지만 쓰는 쌍별 MRF다.

E(x) = \underbrace{\sum_{i\in V} D_i(x_i)}_{\text{데이터항}} \;+\; \underbrace{\sum_{(i,j)\in E} V_{ij}(x_i,x_j)}_{\text{평활항}}

데이터항은 관측과의 불일치(예: $-\log P(y_i\mid x_i)$ ), 평활항은 이웃끼리 다른 라벨을 가질 때의 벌점이다. 평활항을 $V(x_i,x_j) = \beta\,[x_i\ne x_j]$ 로 두면 포츠 모형, 상태를 $\pm1$ 두 개로 제한하면 정확히 **이징 모형**이 된다. 즉 이징 모형은 데이터항 없는 가장 단순한 MRF이고, MRF는 이징에 관측을 붙인 것이다. 물리 쪽 표기( $\beta$ , 해밀토니안, 분배함수)와 비전 쪽 표기(에너지, 사전분포, 정규화 상수)가 한 글자씩만 다른 이유가 이것이다. 결합이 무작위 부호를 가지면 스핀글라스가 되고, 그때부터는 에너지 지형이 거칠어져 최적화가 지옥이 된다.

평활항의 형태가 결과를 지배한다. 절댓값형 $\lvert x_i - x_j \rvert$ 는 전변동에 해당해 계단 경계를 보존하고, 제곱형 $(x_i-x_j)^2$ 은 경계를 뭉갠다. 그래서 영상 복원에서 “경계가 흐려진다”는 불만의 원인은 대부분 모형이 아니라 평활항 선택이다.

4. 추론 — $Z$ 가 문제다[편집]

MRF를 쓰기 어렵게 만드는 단 하나의 이유는 분배함수다. $Z$ 의 정확한 계산은 일반 그래프에서 #P-난해이고(2차원 격자 이징의 계수 세기부터 이미 어렵다), 따라서 주변확률도 정확히 못 구한다. 근사는 크게 세 갈래다.

(a) 표본추출. 마르코프 연쇄 몬테카를로로 $P(x)$ 에서 뽑는다. 각 변수를 이웃 조건부에서 차례로 갱신하는 깁스 표본추출이 기본형이며, 조건부가 이웃만 보므로 계산이 국소적이라는 것이 MRF의 큰 장점이다. 문제는 강한 결합( $\beta$ 가 클 때) 영역에서 국소 갱신이 임계 감속에 걸려 사실상 안 움직인다는 것. 처방이 스완센-왕 클러스터 이동이다 — 같은 라벨의 이웃을 확률 $1-e^{-\beta}$ 로 묶어 덩어리째 뒤집는다. 국소 갱신이 수만 스텝 걸릴 전이를 한 번에 해낸다.

(b) 변분 근사. 다루기 쉬운 분포족에서 KL 발산을 최소화한다(변분 추론). 가장 단순한 평균장 근사는 $Q(x)=\prod_i Q_i(x_i)$ 로 전부 독립이라 가정하는 것이라, 상관을 통째로 버리고 상전이 온도를 틀리게 예측하는 대신 매우 빠르다. 한 단계 나은 것이 루피 믿음 전파(loopy BP)인데, 트리에서는 정확하지만 순환이 있으면 같은 정보가 돌아와 스스로를 강화한다. 그럼에도 잘 도는 이유가 예디디아 등이 밝혀낸 바 BP의 고정점이 정확히 베테 자유에너지의 정류점이기 때문이다. 즉 루피 BP는 발산하는 휴리스틱이 아니라 특정 변분 목적함수를 (비볼록하게) 푸는 알고리즘이다.

(c) 조합 최적화. 사후확률의 최댓값(MAP)만 필요하다면 확률을 포기하고 에너지 최소화 문제로 직행할 수 있다. 그리고 여기서 이 분야 최고의 결과가 나온다 — 이진 라벨 MRF의 에너지가 부분모듈(submodular)이면 그래프 컷으로 전역 최적해를 다항 시간에 정확히 구할 수 있다. 쌍별 항에 대한 부분모듈 조건은

V(0,0) + V(1,1) \;\le\; V(0,1) + V(1,0)

이고, “이웃끼리 같은 라벨을 선호한다”는 상식적 사전분포는 이 조건을 자동으로 만족한다. 최소절단/최대유량으로 환원하는 구성은 그래프 컷 문서로 위임한다. 라벨이 셋 이상이면 일반적으로 NP-난해가 되지만, $\alpha$ -확장(평활항이 거리 함수일 때 최적해의 2배 이내라는 보장)과 $\alpha\beta$ -스왑이 이진 그래프 컷을 반복 호출해 실무에서 거의 최적에 도달한다.²

5. CRF와의 구분[편집]

조건부 확률장(conditional random field, CRF)은 결합분포 $P(x,y)$ 대신 $P(x\mid y)$ 를 직접 모형화한다. 차이는 생성 대 판별이다. MRF는 관측 $y$ 의 생성 과정까지 모형에 넣어야 하고, 그래서 데이터항이 각 픽셀에 대해 독립적인 우도여야 한다는 제약을 받는다. CRF는 $y$ 를 항상 조건으로만 쓰므로 관측 전체에 의존하는 임의의 특징을 퍼텐셜에 넣을 수 있다. 영상 분할에서 “이 두 픽셀의 색이 비슷하면 평활 벌점을 낮춘다”는 대비 민감 평활항은 CRF에서만 정당하다. 대가는 판별 모형의 일반적 대가와 같다 — 결측 데이터 처리와 비지도 학습이 어려워진다. 딥러닝 시대에도 분할 네트워크 출력에 dense CRF를 후처리로 붙이는 조합이 오래 표준이었다.

6. 응용[편집]

저수준 비전: 영상 분할, 잡음제거, 인페인팅, 스테레오 정합(시차가 곧 라벨), 초해상도의 사전분포. 스테레오는 MRF-그래프 컷 조합의 대표 성공 사례다.
텍스처: 텍스처 합성의 고전 기법들이 픽셀의 조건부를 이웃 패치로 모형화하는데, 이게 정확히 MRF 가정이다.
렌더링 후처리: 디퍼드 셰이딩 G-버퍼나 전역 조명의 저표본 결과를 정리하는 디노이저가 공간적으로 매끄러움을 가정하는 것도 같은 구조다. 실시간 구현은 대개 MRF를 정직하게 풀지 않고 한두 번의 가장자리 보존 필터로 근사한다.
역문제와 정규화: MRF 사전분포에 $-\log$ 를 씌우면 곧바로 정규화항이 된다. 절댓값 평활항이 전변동 정규화, 제곱 평활항이 티호노프 정규화에 대응한다. 정규화 계수를 고르는 일이 곧 사전분포의 세기를 고르는 일이라는 관점이 여기서 나온다.
공간 통계: 자료동화와 불확실성 정량화에서 가우스 MRF(GMRF)는 정밀도 행렬이 희소하다는 성질 덕에 가우시안 프로세스의 조밀 공분산 $O(n^3)$ 을 우회하는 표준 도구다. 격자 위 공간 사전분포로 쓰면 희소행렬 촐레스키 하나로 끝난다.
모수 추정과 결합: 라벨을 은닉변수로 두고 기댓값 최대화 알고리즘을 돌리되 E-단계를 MRF 사전분포로 정칙화하는 은닉 MRF-EM은 가우시안 혼합 모형 단독 분할이 만드는 소금-후추 잡음을 깔끔하게 없앤다. 의료영상 조직 분할에서 사실상 표준이었다.³⁴

7. 관련 문서[편집]

“확률 0인 사건은 어차피 안 일어나니 상관없잖아”라고 생각하는 순간 반례에 밟힌다. 정리가 요구하는 건 결과가 아니라 지지집합의 위상이다. 코드에서는 $\infty$ 대신 $10^{9}$ 를 쓰는 게 이론적으로도 정직하고 수치적으로도 안전하다. ↩
부분모듈성 조건을 못 맞추는 에너지를 억지로 그래프 컷에 넣으면 최소절단 구성 자체가 음수 용량 간선을 요구해 알고리즘이 성립하지 않는다. 라이브러리가 던지는 “non-submodular term” 에러를 보고 데이터를 의심하기 전에 평활항 부호부터 확인하자. 대개 벌점 부호를 뒤집어 놨다. ↩
딥러닝이 이 분야를 상당 부분 대체한 뒤에도 MRF가 안 사라진 이유는, 신경망이 학습한 것을 왜 그렇게 매끄럽게 만들었는지 설명해 주는 언어가 여전히 이것밖에 없기 때문이다. 손실함수에 붙는 평활 정규화항은 전부 MRF 사전분포의 로그다. ↩
이름이 헷갈리기로도 유명하다. 마르코프 확률장 / 마르코프 랜덤 필드 / 마르코프 망 / 무향 그래프 모형이 전부 같은 것이고, 깁스 확률장(Gibbs random field)도 해머슬리-클리퍼드 덕에 (양성 조건 아래) 같은 것이다. 논문 네 편을 읽으면 이름이 네 개 나온다. ↩