요약
마르코브 랜덤필드(Markov random field, MRF)은 이산확률변수사이에 상호의존성을 표현하는 그래프모델입니다. 주요한 특징은 무방향성(Undirected)이며 인접한 경우에만 상호작용하는(pairwise interaction)하는 그래프의 성질을 지니고 있습니다. 관찰된 데이터로부터 알려지지 않은 변수를 추론하기위해서 주로 사용되며, 특히 이미지에서는 이미지 복원, 이미지 세그멘테이션, 객체인식 등에 주로 쓰입니다.
마르코브 랜덤 필드 정의(MRF, Markov random fields)
마르코브 랜덤필드는 마르코브 속성을 가진 그래프를 의미합니다. 이산확률변수(노드)사이의 상호의존성(edge)을 표현하는 그래프 모댈입니다. 이 노드 사이에서는 무방향성(undirect, 무향)입니다.
- 일반적인 Markov network (=마르코브 속성(Markov property)가 있어야함)
- 그래프모형이기에 노드(node)와 엣지(edge)가 존재하며, node은 확률변수, edge은 확률변수사이에 종속성을 의미함.
그림 표현
- 검정색원(filled circle)은 관찰된 상태의 노드를 의미
- 흰 원(empty circle)은 관찰되지 않은 상태의 노드를 의미
위의 그림1은 마르코브 랜덤필드의 흔한 예시입니다. 격자형으로 마르코브 속성을 가집니다. 쉽게 말해서 각 노드들이 확률변수 일때, 변수들 변수들간의 상호 의존성이 존재한다는 것입니다. 마르코브 속성은 현재상태가 과거상태에만 의존한다는 것인데, 이전 과거의 T상태전까지(T memory markcov라고도 함)영향을 받을 수 있음을 의미합니다. 위의 격자모형의 그래프에서는 상호의존성을 인접한 노드에서 받을 수 있습니다. 좀 더 나아가서 인접한 노드라고하지만, 이 인접한 노드들은 주변의 인접한 노드가 또 있기에(2칸 떨어진) 이전 T상태전까지 영향을 받는것처럼 생각할 수도 있습니다(하지만 2칸떨어진 노드가 직접영향을 주는 것은 절대아닙니다. 그럴거면 2칸 떨어진 노드에 직접 연결되어있어야합니다.).
만일 노드 3개(A, B, C)가 주어져있고, 노드A가 C을 통하지 않으면 B로갈 경로가 없다고하면 다음과 같이 표기합니다. 만일 이러한 경로가 있으면 이 노드들의 구성은 dependent한것입니다.
$X_A \perp X_B \,|\, X_C$
수식표현
- $x_{i}$: 확률변수. 노드를 의미. 변수라고도하고 node라도 합니
- $\psi(x_{i}, x_{j})$: 관찰되지않은 노드($x_{i}$)와 관찰되지 않은노드($x_{j}$)의 종속성을 의미. 발음은 프사이라고 합니다. 이 종속성은 메트릭스로도 표현할 수 있습니다. 통상 대칭인 정방행렬(symmetric, square matrix)여서 노드 i에서 j로 가거나 노드 j에서 노드i로 가는 것이 동일한 종속성입니다. 하지만, 이 두 노드 사이가 비대칭이어도 상관없습니다. 영문표기로는 compatible function라고합니다.
- $\phi(x_{i}, y_{j})$: 관찰되지않은 노드($x_{i}$)와 관찰된 노드($y_{j}$)의 종속성을 의미합니다. 위의 표기와 다르게 한쪽이 관찰되지 않을 때 쓰는 notation입니다. 영문표기로는 evidence for x라고 합니다. 이미 y은 결정되어있으니 x을 구하기위한 근거라는 것이죠.
- $N_{n}=\{m \in \mathbb{N} \,|\, (n,m) \in \varepsilon\}$: 노드 n의 엣지로 연결된 노드의 집합 (=노드N의 이웃집합)
- $P(X_{n} \| X_{N_{n}})$: 노드n의 인접한노드(=로컬 조건부확률)로만 알고있으면$ X_{n}$의 확률을 알 수 있음을 의미합니다. 마르코브 속성을 의미합니다. [1]
마르코브 랜덤 필드의 예시
아래의 그림은 MRF의 예시입니다. 4개의 노드가 존재합니다. 3개의 노드($x_{1}, x_{2}, x_{3}$)은 관찰되지 않은 노드이고, 유일하게 node 4($y_{2}$)만 관찰된 노드입니다.
위 MRF을 수식으로 표현해보겠습니다.
- 노드: 관찰되지 않은 노드1은 $x_{1}$, ..., 노드3은 $x_{3}$입니다. 반면 관찰된 노드4은 $y_{4}$입니다.
- MRF은 각 노드사이의 종속성을 표현한다고 했습니다. 각 노드의 종속성을 아래와 같이 표현할 수 있습니다.
에너지함수(energy function)와 포탠셜(Potential)
마르코브 랜덤필드의 확률분포는 에너지함수를 사용하여 계산할 수 있습니다. 즉, 이런 마르코브랜덤 필드가 나오려면 어떤 확률분포였겠드냐를 의미합니다. 여기서 에너지함수라는 것을사용하는데,에너지함수는 다음과 같은 아이디에 기반합니다.
- 높은 에너지를 가지고 있는 상태는 불안정하니 낮은 확률을 갖는다는 것
- 에너지함수는 확률변수의 집합의 각 상태에 대한 에너지값을 부여하며, 에너지가 낮을수록 높은확률
깁스 분포(Gibbs distribution)을 이용해서 마르코브 랜덤필드를 정의해보겠습니다. (깁스 분포는 결합확률분포가 각 확률변수의 조건부 독립적이어서 곱한것을 의미)
$P(X)= \frac {1}{Z} \prod _{c\in C} \phi_{c} (x_{c})$
여기서 C은 maximal clique을 의미합니다. 즉 이 그래프에서 클리크에 속하는 모든 노드들의 확률을 다 하나하나 곱하면 전체 그래프가 될 수 있다는 것을 의미합니다. 그리고 여기서 Z은 보통 정규화 상수인데, 이 그래프에서는 다음과 같이 표현합니다.
$Z=\sum_{x}\prod _{c \in C}\phi_{c}(x_{c})$
이 그래프에서 $phi_{c}(x_{c})$을 다음과 같이 쓸 수 있습니다. 보통 여기서 T은 온도(temperature)라고해서 1을 쓰씁니다.
$\phi_{c}(x_{c})=e^{-1 \frac{1}{T}V_{c}(x_{c})}$
각각 Z랑 $phi_{c}(x_{c})$을 알고있으니, 깁스분포에 대입해보면, 아래와 같고, 지수의 승을 덧셈으로 표현할 수 있으니까 결국 두번째식까지 얻어낼 수 있습니다.
$P(x)=\frac{1}{Z}\prod _{c \in C} e^{-\frac{1}{T}V_{c}(x_{c})}$
$P(X)=\frac{1}{Z}e^{-\frac{1}{T}\sum_{c \in C}V_{c}(x_{c})}$
이때, $\sum_{c \in C}V_{c}(x_{c})$을 보통 $U(x)$라고하고, 에너지라고합니다. 그리고 V은 클리크 포탠셜(clique potential)이라고합니다.
마르코브 랜덤 필드와 베이지안 네트워크의 차이
마르코브랜덤필드는 베이지안 네트워크와 유사합니다. 표로 정리하면 아래와 같은 차이점이 있습니다.
| 마르코브 랜덤 필드 | 베이지안 네트워크 | |
| 정의 | 확률 변수 간의 조건부 독립 관계를 나타내는 무방향 그래프 | 확률 변수의 조건부 독립 관계를 나타내는 방향성 있는 그래프(Acyclic) |
| 방향 | Undirected | Directed |
| 두 노드의 확률 | compatible function ψ_ij (x_i,x_j) | Conditional probability p(x_i |x_j) |
| 변수타입 | 이산 | 이산, 연속 |
| 순환가능 | 가능 | 불가능 |
Python example
MRF의 예시
import networkx as nx
import matplotlib.pyplot as plt
# 그래프 생성
G = nx.Graph()
# 노드 추가
nodes = ["x1", "x2", "x3", "y2"]
G.add_nodes_from(nodes)
# 간선 추가 및 가중치 설정
edges = [("x1", "x2", 0.9), ("x2", "x3", 0.1), ("y2", "x2", 0.1)]
G.add_weighted_edges_from(edges)
# 각 노드에 확률 변수 값을 할당 (예: 이진 랜덤 변수)
for node in G.nodes:
G.nodes[node]['value'] = 0 # 초기값을 0 또는 1로 설정
# 노드 위치 지정
pos = {
"x1": (-1, 0), # 왼쪽에 위치
"x2": (0, 0), # 6시 방향에 위치
"x3": (1, 0), # 오른쪽에 위치
"y2": (0, 1) # 12시 방향에 위치
}
# 그래프 시각화
nx.draw(G, pos, with_labels=True, font_weight='bold', node_size=800, node_color='lightblue', font_color='black')
plt.show()
MRF을 이용한 iterated conditional modes(ICM)을 적용
import cv2
import numpy as np
from PIL import Image
# 이미지 불러오기
image = cv2.imread('/home/heon/repositories/detection_models/sample.png', cv2.IMREAD_GRAYSCALE)
image = cv2.resize(image, (128, 128))
noisy_image = image + np.random.normal(0, 15, image.shape).astype(np.uint8)
binary_image = cv2.threshold(noisy_image, 100, 255, cv2.THRESH_BINARY)[1]
Image.fromarray(image)
Image.fromarray(noisy_image)
Image.fromarray(binary_image)
def calculate_cost(y_p, x_p, alpha, beta, neighbors, y_k):
cost = alpha * (1 - (y_p == x_p))
for q in neighbors:
cost += beta * (1 - (y_p == y_k[q]))
return cost
def icm_reconstruction(observed_image, alpha, beta, max_iterations):
height, width = observed_image.shape
y_k = np.copy(observed_image) # Initialize the restored image as the observed image.
neighbors = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
for _ in range(max_iterations):
updated_y = np.copy(y_k)
for i in range(1, height - 1):
for j in range(1, width - 1):
current_pixel = observed_image[i, j]
best_cost = float('inf')
best_pixel_value = None
for y_p in [0, 1]:
cost = calculate_cost(y_p, current_pixel, alpha, beta, neighbors, y_k)
# print(i,j,cost, best_cost)
if cost < best_cost:
best_cost = cost
best_pixel_value = y_p
updated_y[i, j] = best_pixel_value
if np.array_equal(updated_y, y_k):
break
y_k = updated_y
return y_k
Reference
'Data science > Graph theory' 카테고리의 다른 글
| 온톨로지의 의미론적 유사도: Information content 란? (0) | 2023.01.09 |
|---|---|
| Clique (파벌, 패거리)란? 5분 컷이해 (0) | 2021.10.11 |
