마르코프 랜덤 필드

물리학과 확률의 영역에서, 마르코프 무작위 필드(MRF), 마르코프 네트워크 또는 비간접 그래픽 모델은 비방향 그래프에 의해 설명되는 마르코프 속성을 가진 랜덤 변수들의 집합이다. 즉 임의 필드는 마르코프 속성을 만족하면 마르코프 랜덤 필드라고 한다.

마르코프 네트워크 또는 MRF는 의존성의 표현에서 베이지안 네트워크와 유사하다. 반면에 마코프 네트워크는 방향을 정하고 반복된다는 차이점이다. 그러므로, 마코프 네트워크는 베이시안 네트워크가 할 수 없는 특정한 의존성(순환^{[further explanation needed]} 종속성 등)을 나타낼 수 있고, 다른 한편으로는 베이시안 네트워크가 할 수 있는 특정한 의존성(유도 의존성^{[further explanation needed]} 등)을 나타낼 수 없다. 마르코프 랜덤 필드의 기본 그래프는 유한하거나 무한할 수 있다.

무작위 변수의 관절 확률 밀도가 엄격히 양수인 경우, 해머슬리-클리포드 정리에 따라 적절한 (로컬하게 정의된) 에너지 함수에 대한 깁스 측도로 나타낼 수 있기 때문에 깁스 무작위 장이라고도 한다. 원형 마르코프 랜덤 필드는 이싱 모델이다. 실제로, 마코프 랜덤 필드는 이싱 모델의 일반적인 설정으로 도입되었다.^[1] 인공지능 영역에서는 마코프 랜덤 필드가 사용돼 이미지 처리와 컴퓨터 비전 등에서 다양한 중저준위 작업을 모델링한다.^[2]

정의

Given an undirected graph ${\displaystyle G=(V,E)}$, a set of random variables ${\displaystyle X=(X_{v})_{v\in V}}$ indexed by ${\displaystyle V}$ form a Markov random field with respect to ${\displaystyle G}$ if they satisfy the local Markov properties:

Pairwise Markov 속성: 다른 모든 변수를 고려할 때 두 개의 비인접 변수는 조건부로 독립적이다.

$\displaystyle X_{u}\perp \!\!\!\perp X_{v}\mid X_{V\setminus \{u,v\}}}$

로컬 마르코프 속성: 변수는 인접 변수가 주어진 다른 모든 변수와 조건부로 독립적이다.

$\displaystyle X_{v}\perp \!\!\!\perp X_{V\setminus \operatorname {N} [v]}\mid X_{\operatorname {N}(v)}}}}}$

where ${\textstyle \operatorname {N} (v)}$ is the set of neighbors of ${\displaystyle v}$, and ${\displaystyle \operatorname {N} [v]=v\cup \operatorname {N} (v)}$ is the closed neighbourhood of ${\displaystyle v}$.

글로벌 마르코프 속성: 두 변수의 하위 집합은 구분된 하위 집합에 따라 조건부로 독립적이다.

$\displaystyle X_{A}\perp \!\!\!\perp X_{B}\mid X_{S}}$

여기서 A{\$displaystyle A}$의 노드에서 B ${\displaystyle B}$의 노드로 가는 모든 경로는 S ${\displaystyle$ S$}$을(를) 통과한다.

Global Markov 속성은 Local Markov 속성보다 강하며, 다시 Pairwise 속성보다 강하다.^[3] 그러나 위의 세 가지 마르코프 특성은 양의 분포^[4](관련 변수에 0이 아닌 확률만 할당하는 분포)에 대해 동등하다.

클라이크 인자화

임의 확률 분포의 마르코프 속성은 설정하기 어려울 수 있으므로, 일반적으로 사용되는 마르코프 랜덤 필드의 종류는 그래프의 분류에 따라 인수될 수 있는 종류들이다.

Given a set of random variables ${\displaystyle X=(X_{v})_{v\in V}}$, let ${\displaystyle P(X=x)}$ be the probability of a particular field configuration ${\displaystyle x}$ in ${\displaystyle X}$. That is, ${\displaystyle P(X=x)}$ is the probability of finding that 임의 변수 X ${\displaystyle X}$이(가) 특정 값 x ${\displaystyle x}$을(를) 취함. X ${\displaystyle$ X$}$이(가) 집합이므로 X v ${\$의 공동 분포와 관련하여 x ${\displaystystytype$ X$}$의 확률을 이해해야 한다.

이 조인트 밀도를 G ${\displaystyle G}$의 부류에 대해 고려할 수 있는 경우:

${\displaystyle P(X=x)=\prod _{C\in \operatorname {cl}(G)}\phi _{C}$

그러면 X ${\displaystyle X}$이(가) G ${\displaystyle G$}과(와) 관련하여 마르코프랜덤 필드를 형성한다. 여기서 cl $⁡$(G $)$ {\$displaystyle$ \$operatorname {cl}($$)$은 G {\$displaystystyle$ G$}$의 click 집합이며, 최대 click만 사용되는 경우 정의는 동일하다. ϕ C ${\$ 함수를 요인 전위 또는 집단 전위라고 부르기도 한다. 그러나 상충되는 용어들이 사용되고 있다: potential C ${\$의 로그에 전위라는 단어가 종종 적용된다. 이는 통계역학에서 로그 ⁡ (ϕ C) ${\displaystyle \log(\phi _{C})$가 구성 X ${\\$의 잠재적 에너지로 직접 해석되기 때문이다.$e x_{C}}$.

일부 MRF는 고려되지 않는다. 예를 들어, 0 확률을 구성하여 V ${\displaystyle V$^[6]의 전체 그래프에 무한 에너지를 작용하도록 허용하더라도 일부 무한 에너지와 같은 4개 노드의 사이클로 구성될 수 있다.^[5]

다음 조건 중 하나 이상이 충족되면 MRF를 인수한다.

• 밀도는 양수(Hammersley-Clifford 정리)
• 그래프는 화음(베이지안 네트워크와 동등하게)

그러한 요소화가 존재하는 경우, 네트워크에 대한 요소 그래프를 구성할 수 있다.

지수군

임의의 양의 마르코프 무작위 필드는 형상함수 f k ${\$를 갖는 표준형식으로 지수형 패밀리로 쓸 수 있으므로 전체 접합분포를 다음과 같이 쓸 수 있다.

${\displaystyle P(X=x)={\frac {1}{Z}\exp \left(\sum _{k}w_{k}^{\f_{k\}}}{{k\}}}\right)}}}$

표기가 있는 곳에.

${\displaystyle w_{k}^{\top }f_{k}(x_{\{k\}}})=\sum _{i=1}^{{n_{k_{k}\cdot f_{k,i}(x_{k\}}}})}}}$

단순히 필드 구성 위에 도트 제품이며, Z는 파티션 함수:

${\displaystyle Z=\sum _{x\in {\mathcal {X}}\exp \left(\sum _{k}^{k}^{\f_{k\}}}}\right).}$

여기서 X ${\$은(는) 네트워크의 모든 임의 변수에 대해 가능한 모든 값의 할당 집합을 나타낸다. Usually, the feature functions ${\displaystyle f_{k,i}}$ are defined such that they are indicators of the clique's configuration, i.e. ${\displaystyle f_{k,i}(x_{\{k\}})=1}$ if ${\displaystyle x_{\{k\}}}$ corresponds to the i-th possible configuration of the k-th clique and 그렇지 않으면 0이다. This model is equivalent to the clique factorization model given above, if ${\displaystyle N_{k}= \operatorname {dom} (C_{k}) }$ is the cardinality of the clique, and the weight of a feature ${\displaystyle f_{k,i}}$ corresponds to the logarithm of the corresponding clique factor, i.e. ${\displaystyle w_{k,i}=\log \phi (c_{k,i})}$, where ${\displaystyle c_{k,i}}$ is the i-th possible configuration of the k-th clique, i.e. the i-th value in the domain of the clique ${\displaystyle C_{k}}$.

확률 P는 흔히 깁스 측정이라고 불린다. 마르코프 필드를 로지스틱 모델로 사용하는 이 표현은 모든 클라이크 요인이 0이 아닌 경우에만 가능하다. 즉, X ${\$의 요소 중 0의 확률을 할당하지 않은 경우에만 가능하다. 이를 통해 매트릭스 대수에서 기법을 적용할 수 있다. 예를 들어, 매트릭스의 추적이 결정 인자의 로그이며, 그래프의 발생 행렬에서 발생하는 그래프의 행렬을 나타낼 수 있다.

파티션 함수 Z의 중요성은 엔트로피와 같은 통계 역학으로부터 마르코프 네트워크의 사례에 이르기까지 많은 개념들이 직접 일반화되며, 이에 따라 직관적인 이해를 얻을 수 있다는 것이다. 또한, 파티션 함수는 하나 이상의 무작위 변수에 추진력을 부착할 수 있고, 이러한 동요에 대응한 네트워크의 반응을 탐색할 수 있는 등, 문제의 해결책에 가변적인 방법을 적용할 수 있도록 한다. 따라서 예를 들어, 그래프의 각 꼭지점 v에 대해 다음을 얻기 위해 파티션 함수에 운전 용어 J를_v 추가할 수 있다.

${\displaystyle Z[J]=\sum _{x\in {\mathcal {X}}\exp \ex(\sum _{k}^{\f_{k\}}}^{\f_{k\}}}+\sum _{v}J_{v}x_{v}\rig}\rig}\rig)}}}$

J에_v 대해 공식적으로 차별화하면 정점 v와 연관된 랜덤 변수 X의_v 기대값을 얻을 수 있다.

${\displaystyle E[X_{v}]={\frac {1}{Z}\왼쪽.{\frac {\partial Z[J]}{\partial J_{v}}}\오른쪽 _{J_{v}=0}}$

상관 함수도 마찬가지로 계산된다. 두 점 상관 관계는 다음과 같다.

${\displaystyle C[X_{u},X_{v}]={\frac {1}{Z}\왼쪽.{\frac {\partial ^{2}Z[J]}{\partial J_{u}\partial J_{v}}}\right _{J_{u}=0,J_{v}=0}}}}$

불행히도, 로지스틱 마르코프 네트워크의 가능성은 볼록하지만, 모델의 우도 또는 구배를 평가하려면 일반적으로 계산상 실현 불가능한 모델의 추론이 필요하다(아래 '추론' 참조).

예

가우스어

다변량 정규 분포는 결측 에지가 정밀 행렬(역분산 행렬)의 0에 해당하는 경우 그래프 G=(V, E )${\displaystyle$ G$=(V,E)}$에 대해 마르코프 랜덤 필드를 형성한다.

${\displaystyle X=(X_{v})_{v\in V}\sim {\mathcal{N}({\boldsymbol {\mu }},\Sigma )}$

그런

${\displaystyle(\Sigma ^{-1}_{uv}=0\quad {\text{iff}}\quad \{u,v\}\notin E.}$^[7]

추론

As in a Bayesian network, one may calculate the conditional distribution of a set of nodes ${\displaystyle V'=\{v_{1},\ldots ,v_{i}\}}$ given values to another set of nodes ${\displaystyle W'=\{w_{1},\ldots ,w_{j}\}}$ in the Markov random field by summing over all possiu ∉ V ′, W ′ ${\$ ,$W'}$에 대한 할당 ; 이것을 정확한 추론이라고 한다. 그러나 정확한 추론은 #P-완전한 문제여서 일반적인 경우에는 계산적으로 난해한 것이다. 마르코프 체인 몬테 카를로나 루피 신앙 전파와 같은 근사치 기법은 종종 실무에서 더 실현 가능하다. 나무(Chow-Liu 트리 참조)와 같은 MRF의 일부 하위 분류에는 다항 시간 추론 알고리즘이 있다. 이러한 하위 분류의 발견은 활발한 연구 주제다. 또한 효율적인 MAP 또는 가장 가능성이 높은 할당 추론을 허용하는 MRF의 하위 클래스도 있다. 이러한 예에는 연관 네트워크가 포함된다.^[8][9] 또 다른 흥미로운 하위 등급은 분해 가능한 모델 중 하나이다(그래프가 화음일 때): MLE를 위한 폐쇄형 형태를 가지면, 수백 개의 변수에 대한 일관된 구조를 발견할 수 있다.^[10]

조건부 랜덤 필드

마르코프 랜덤 필드의 주목할 만한 변종 중 하나는 조건부 랜덤 필드인데, 이 필드에서는 각 랜덤 변수가 글로벌 관찰 집합 o ${\$$displaystyle o}$에 따라 조건화될 수 $있다$. 이 모델에서 각 함수 . k {\$displaystyle \phi _$${$k$}$는 클라이크 k와 관측치 모두에 대한 모든 할당에서 매핑된 것이다.음수가 아닌 실제 숫자에 대해 표시 $스타일 o}.$ 마르코프 네트워크의 이러한 형태는 관측치에 대한 분포를 모형화하지 않는 차별적 분류자를 생성하는 데 더 적합할 수 있다. CRF는 존 D에 의해 제안되었다. 2001년 라퍼티, 앤드류 맥칼럼, 페르난도 C.N. 페레이라.^[11]

다양한 애플리케이션

마르코프 무작위 분야는 컴퓨터 그래픽에서부터 컴퓨터 비전, 머신러닝 또는 컴퓨터 생물학에 이르는 다양한 분야에서 응용 프로그램을 찾는다.^[12][13] MRF는 유연하고 확률적인 이미지 모델을 생성하는 데 사용될 수 있기 때문에 질감을 생성하기 위해 이미지 처리에 사용된다. 이미지 모델링에서 과제는 주어진 이미지의 적절한 강도 분포를 찾는 것이다. 여기서 적합성은 작업 종류에 따라 달라지며 MRF는 영상과 질감 합성, 영상 압축 및 복원, 영상 세분화, 2D 영상의 3D 영상 추론, 영상 등록, 질감 합성, 슈퍼리즈 등에 사용될 수 있을 정도로 유연하다.Olution, 스테레오 매칭 및 정보 검색. 그것들은 에너지 최소화 문제로 제기될 수 있는 다양한 컴퓨터 비전 문제나 마르코프 무작위 필드 프레임워크 내에서 지역의 범주를 예측하기 위해 구별되는 특징들을 사용하여 서로 다른 지역을 구별해야 하는 문제를 해결하는 데 사용될 수 있다.^[14] 마르코프 무작위 필드는 Ising 모델에 대한 일반화였으며, 그 이후로 조합 최적화 및 네트워크에 널리 사용되었다.

참고 항목

참조