마르코프 네트워크
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
마르코프 네트워크는 무방향 그래프를 기반으로 하는 확률적 모델로, 변수 간의 조건부 독립성을 묘사한다. 쌍별, 국소, 전역 마르코프 속성을 통해 정의되며, 클리크 분해와 지수족 표현을 사용하여 모델을 분석하고 표현할 수 있다. 추론은 #P-완전 문제로 정확한 계산이 어렵지만, 근사 기법이 사용된다. 마르코프 네트워크는 조건부 무작위장과 같은 변형을 가지며, 컴퓨터 그래픽스, 컴퓨터 비전, 기계 학습 등 다양한 분야에 응용된다.
마르코프 네트워크, 또는 마르코프 확률장(Markov random field)은 무향 그래프 와 이 그래프의 정점 에 대응하는 확률 변수 집합 으로 구성된다. 이 확률 변수 집합 는 그래프 에 대해 다음의 세 가지 마르코프 성질 중 하나(또는 동등하게 모두)를 만족할 때 마르코프 확률장이라고 불린다.[18][4]
임의의 확률 분포에서 마르코프 성질을 확립하기 어려울 수 있으므로, 일반적으로 사용되는 마르코프 랜덤 필드의 클래스는 그래프의 클리크에 따라 인수분해될 수 있는 것들이다.
2. 정의
:
:
:여기서 는 의 이웃 집합이고, 는 와 그 이웃을 포함하는 닫힌 이웃 집합이다.
:
이 세 가지 마르코프 속성은 서로 동등하지 않다. 일반적으로 전역 마르코프 속성이 가장 강한 조건이며, 국소 마르코프 속성, 쌍별 마르코프 속성 순으로 약해진다.[4] 하지만 확률 변수들의 결합 분포가 양의 값을 가지는 경우(즉, 어떤 변수 조합에도 0이 아닌 확률이 할당되는 경우), 이 세 가지 속성은 서로 동등하다.[5][18]
다변량 정규 분포를 따르는 확률 변수 집합 는 특정 조건 하에서 그래프 에 대한 마르코프 확률장을 형성한다. 그 조건은 정밀 행렬(공분산 행렬의 역행렬 )의 특정 원소 가 0인 것이 그래프에서 해당 두 노드 사이에 간선이 없는 것()과 동치인 경우이다.[8]
:
2. 1. 쌍별 마르코프 속성
무향 그래프 와 변수 집합 가 주어졌을 때, 이들이 마르코프 확률장을 형성하기 위한 조건 중 하나로 쌍별 마르코프 속성(Pairwise Markov property)이 있다. 이는 인접하지 않은 임의의 두 변수가 다른 모든 변수가 주어졌을 때 조건부 독립임을 의미한다.[18]
마르코프 확률장과 관련된 다른 마르코프 속성들은 다음과 같다.
여기서 는 의 이웃 노드 집합이고, 는 의 닫힌 이웃이다.
이 세 가지 마르코프 속성 간에는 강도 차이가 존재한다. 전역 마르코프 속성은 국소 마르코프 속성보다 강한 조건이며, 국소 마르코프 속성은 쌍별 마르코프 속성보다 강한 조건이다.[4] 하지만 확률 분포가 양의 값을 가지는 경우(즉, 모든 변수 조합의 확률이 0보다 큰 경우), 이 세 가지 속성은 서로 동등하다.[5][18]
2. 2. 국소 마르코프 속성
무향 그래프 와 이 그래프의 정점 에 의해 인덱싱된 확률 변수 집합 가 주어졌을 때, 가 에 대한 마르코프 확률장(Markov random field)을 형성하기 위해서는 특정 마르코프 성질을 만족해야 한다. 국소 마르코프 속성은 이러한 성질 중 하나이다.
국소 마르코프 속성은 어떤 변수가 그 변수의 이웃(neighbors)이 주어졌을 때, 다른 모든 변수들과 조건부 독립임을 의미한다. 수학적으로는 다음과 같이 표현된다.
:
여기서 는 정점 의 이웃 노드들의 집합을 의미하며, 는 와 그 이웃 노드들을 포함하는 닫힌 이웃 집합을 나타낸다.
마르코프 확률장과 관련된 다른 마르코프 속성들은 다음과 같다.
: (단, 와 는 인접하지 않음)
:
이 세 가지 마르코프 속성 사이에는 강도 차이가 존재한다. 일반적으로 전역 마르코프 속성이 가장 강하며, 국소 마르코프 속성이 그 다음이고, 쌍별 마르코프 속성이 가장 약하다.[4] 하지만 확률 분포가 양의 분포(positive distribution), 즉 모든 변수 구성에 대해 0보다 큰 확률 값을 가지는 경우에는 이 세 가지 속성이 모두 동등하게 성립한다.[5][18]
2. 3. 전역 마르코프 속성
전역 마르코프 속성은 확률 변수 집합의 임의의 두 부분 집합 와 가, 이 둘을 분리하는(separate) 부분 집합 가 주어졌을 때 조건부 독립임을 의미한다. 수식으로는 다음과 같이 표현된다.[18]
:
여기서 는 의 노드에서 의 노드로 가는 모든 경로가 통과하는 노드들의 집합이다.
전역 마르코프 속성은 국소 마르코프 속성보다 강하고, 국소 마르코프 속성은 쌍별 마르코프 속성보다 강하다.[4][18] 그러나 분포가 양수(positive distribution)일 경우, 즉 관련된 변수에 0이 아닌 확률만 할당하는 분포에서는 이 세 가지 마르코프 성질이 동등하다.[5][18]
3. 클리크 분해
랜덤 변수 집합 가 주어졌을 때, 를 에서 특정 필드 구성 의 확률로 정의하자. 즉, 는 랜덤 변수 가 특정 값 를 가질 확률을 의미한다. 는 집합이므로, 의 확률은 들의 결합 분포로 이해해야 한다.
이 결합 밀도가 그래프 의 클리크에 대해 다음과 같이 인수분해될 수 있다면, 는 에 대한 마르코프 랜덤 필드를 형성한다.
:
여기서 는 의 클리크 집합이며, 는 클리크 에 속하는 변수들의 상태를 나타낸다. 이 정의는 최대 클리크만을 사용해도 동일하게 적용된다. 함수 는 인수 잠재력(factor potential) 또는 클리크 잠재력(clique potential)이라고 불린다. 때로는 의 로그 값, 즉 를 '잠재력'이라고 부르기도 하는데, 이는 통계 역학에서 이 값이 구성 의 포텐셜 에너지로 직접 해석되기 때문이다.
모든 마르코프 랜덤 필드가 인수분해되는 것은 아니다. 예를 들어, 4개의 노드가 순환 구조를 이루는 그래프에서 특정 구성의 확률을 0으로 만드는(즉, 무한 에너지를 갖는) 방식으로 인수분해가 불가능한 마르코프 랜덤 필드를 구성할 수 있다.[6][7]
마르코프 랜덤 필드는 다음 조건 중 적어도 하나가 충족되면 인수분해된다.
이러한 인수분해가 존재할 때, 네트워크에 대한 인수 그래프를 구성하는 것이 가능하다.
어떤 양의 마르코프 네트워크는 다음과 같이 전체 결합 분포를 쓸 수 있는 특징 함수 를 사용하여 정규 형식으로 지수족으로 표현할 수 있다.
:
여기서 표기법은 다음과 같다.
:
이는 단순히 필드 구성에 대한 점 곱이며, 는 분배 함수이다.
:
여기서 는 네트워크의 모든 확률 변수에 대한 모든 가능한 값 할당의 집합을 나타낸다. 일반적으로 특징 함수 는 특정 클리크 구성의 지표 함수로 정의된다. 즉, 가 번째 클리크의 번째 가능한 구성에 해당하면 이고, 그렇지 않으면 0이다. 이 모델은 클리크의 기수(cardinality) 와 특징 의 가중치가 해당 클리크 인자의 로그 값, 즉 (여기서 는 번째 클리크의 번째 가능한 구성)일 때, 위에서 설명한 클리크 인수분해 모델과 동일하다.
확률 는 종종 깁스 척도(Gibbs measure)라고 불린다. 마르코프 필드를 로지스틱 모델로 표현하는 것은 모든 클리크 인자가 0이 아닌 경우, 즉 의 어떤 요소도 0의 확률로 할당되지 않은 경우에만 가능하다. 이는 행렬 대수의 기술을 적용할 수 있게 하며, 예를 들어 행렬의 대각합은 그래프의 인접 행렬에서 발생하는 그래프의 행렬 표현을 사용하여 행렬식의 로그와 관련된다.
분배 함수 는 통계 역학의 많은 개념(예: 엔트로피)이 마르코프 네트워크의 경우로 직접 일반화될 수 있게 하여 직관적인 이해를 돕는다. 또한 분배 함수를 사용하면 변분법을 문제 해결에 적용할 수 있다. 예를 들어, 하나 이상의 확률 변수에 외부 힘(driving force)을 가하고 이 섭동에 대한 네트워크의 반응을 탐색할 수 있다. 그래프의 각 정점 에 대한 구동 항 를 분배 함수에 추가하면 다음과 같다.
:
에 대해 공식적으로 미분하면 정점 와 관련된 확률 변수 의 기댓값을 얻을 수 있다.
:
상관 함수도 유사하게 계산된다. 두 점 간의 상관 관계는 다음과 같다.
:
하지만 로지스틱 마르코프 네트워크의 가능도(likelihood)는 볼록 함수이지만, 모델의 가능도나 가능도의 기울기를 평가하려면 모델에서 추론 과정이 필요한데, 이는 일반적으로 계산적으로 매우 복잡하여 실행 불가능한 경우가 많다.
4. 지수족 표현
어떤 양의 마르코프 네트워크는 전체 결합 분포를 지수족 형태로 작성할 수 있다. 이는 다음과 같이 특징 함수 를 사용하여 표현된다.
:
여기서 는 필드 구성에 대한 점 곱을 나타낸다. ''Z''는 분배 함수이다.
:
는 네트워크의 모든 확률 변수에 대한 가능한 모든 값 할당의 집합을 의미한다. 일반적으로 특징 함수 는 클리크 구성의 지표 함수로 정의된다. 즉, 가 ''k''번째 클리크의 ''i''번째 가능한 구성에 해당하면 이고, 그렇지 않으면 0이다. 이 모델은 가 클리크의 기수이고, 특징 의 가중치가 해당 클리크 인자의 로그 값()과 같을 때, 위에서 설명한 클리크 인수분해 모델과 동일하다. 여기서 는 ''k''번째 클리크의 ''i''번째 가능한 구성, 즉 클리크 의 도메인에서 ''i''번째 값이다.
확률 ''P''는 종종 깁스 척도(Gibbs measure)라고 불린다. 마르코프 필드를 로지스틱 모델로 표현하는 것은 모든 클리크 인자가 0이 아닐 때, 즉 의 어떤 요소도 0의 확률로 할당되지 않은 경우에만 가능하다.
분배 함수 ''Z''는 통계 역학의 여러 개념(예: 엔트로피)을 마르코프 네트워크에 적용하고 직관적인 이해를 가능하게 한다는 점에서 중요하다. 또한, 분배 함수를 통해 변분법을 문제 해결에 활용할 수 있다. 예를 들어, 하나 이상의 확률 변수에 외부 힘(driving force)을 가하고 네트워크의 반응을 탐색하는 섭동 이론을 적용할 수 있다. 그래프의 각 정점 ''v''에 구동 항 ''J''''v''를 추가하면 분배 함수는 다음과 같이 변형된다.
:
이 식을 ''J''''v''에 대해 미분하면 정점 ''v''와 관련된 확률 변수 ''X''''v''의 기댓값을 얻을 수 있다.
:
상관 함수도 유사한 방식으로 계산할 수 있다. 예를 들어, 두 점 간의 상관 관계는 다음과 같다.
:
그러나 로지스틱 마르코프 네트워크의 가능도(likelihood)는 볼록하지만, 모델의 가능도나 그 기울기를 평가하려면 모델에서의 추론이 필요하며, 이는 일반적으로 계산적으로 매우 어렵다.
5. 추론
베이즈 네트워크와 마찬가지로, 마르코프 랜덤 필드에서 특정 노드 집합 의 조건부 확률 분포는, 다른 노드 집합 의 값들이 주어졌을 때, 인 모든 노드 에 대한 가능한 모든 값 할당을 합산하여 계산할 수 있다. 이를 정확한 추론이라고 한다.
그러나 정확한 추론은 #P-완전 문제이기 때문에, 일반적인 경우에는 계산적으로 처리하기 매우 어렵다. 따라서 마르코프 체인 몬테카를로나 루피 신념 전파와 같은 근사 기법이 실제로는 더 유용하게 사용되는 경우가 많다.
트리 구조와 같은 특정 하위 클래스(차우-리우 트리 참조)는 다항 시간 안에 추론이 가능한 알고리즘을 가지며, 이러한 하위 클래스를 찾는 연구가 활발히 진행되고 있다. 또한 효율적인 MAP(Maximum A Posteriori), 즉 가장 가능성 높은 값 할당을 추론할 수 있는 MRF의 하위 클래스도 존재한다. 연관 네트워크(associative network)가 이러한 예시에 포함된다.[9][10]
또 다른 중요한 하위 클래스는 분해 가능한 모델(decomposable model)인데, 이는 그래프가 현 그래프인 경우를 말한다. 이 모델은 MLE(Maximum Likelihood Estimation)에 대한 닫힌 형식 해를 가지므로, 수백 개의 변수를 갖는 경우에도 일관된 구조를 찾아내는 것이 가능하다.[11]
6. 조건부 확률장
마르코프 무작위장의 주목할 만한 변형 중 하나는 '''조건부 무작위장'''이다. 조건부 무작위장에서는 각 확률 변수가 일련의 전역 관측치 에 따라 조건화될 수 있다. 이 모델에서 각 함수 는 클리크 ''k''와 관측치 에 대한 모든 할당을 음이 아닌 실수로 매핑한다. 이러한 형태의 마르코프 네트워크는 관측치에 대한 분포를 모델링하지 않는 판별 분류기를 생성하는 데 더 적합할 수 있다. 조건부 무작위장은 2001년에 존 D. 래퍼티, 앤드루 매컬럼, 페르난도 C.N. 페레이라에 의해 제안되었다.[12]
7. 응용
마르코프 랜덤 필드(MRF)는 컴퓨터 그래픽스부터 컴퓨터 비전, 기계 학습, 전산 생물학[13][14] 및 정보 검색에 이르기까지 다양한 분야에서 활용된다.[15]
MRF는 유연하고 확률적인 이미지 모델 생성이 가능하여 텍스처 생성에 사용된다. 이미지 모델링에서는 주어진 이미지의 적절한 강도 분포를 찾는 것이 중요한데, MRF는 이러한 작업에 효과적이다. 구체적으로 이미지 및 텍스처 합성, 이미지 압축, 이미지 복원, 이미지 분할, 2차원 이미지에서 3차원 이미지 추론, 이미지 등록, 텍스처 합성, 슈퍼 레졸루션, 스테레오 매칭 및 정보 검색 등 다양한 이미지 관련 문제 해결에 적용될 수 있다.[16]
또한, MRF 프레임워크는 에너지 최소화 문제나, 특징을 이용해 영역을 구별하고 범주를 예측하는 문제 등 다양한 컴퓨터 비전 문제를 해결하는 데 사용될 수 있다.[16] 마르코프 랜덤 필드는 아이징 모델을 일반화한 것으로, 조합 최적화 및 네트워크 분야에서도 널리 사용되고 있다.
참조
[1]
논문
Solvable Model of a Spin-Glass
[2]
서적
Markov Random Fields and Their Applications
http://www.cmap.poly[...]
American Mathematical Society
2012-04-09
[3]
서적
Markov Random Field Modeling in Image Analysis
https://books.google[...]
Springer
[4]
서적
Graphical models
Clarendon Press
1996
[5]
서적
Probabilistic Graphical Models
MIT Press
2009
[6]
간행물
Gibbs and Markov random systems with constraints
[7]
간행물
A note on Gibbs and Markov Random Fields with constraints and their moments
[8]
서적
Gaussian Markov random fields: theory and applications
CRC Press
[9]
간행물
Proceedings of the Twenty-First International Conference on Machine Learning (ICML 2004), Banff, Alberta, Canada, July 4-8, 2004
Association for Computing Machinery
[10]
간행물
Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 4-7, 2006
MIT Press
[11]
conference
Scaling log-linear analysis to high-dimensional data
http://www.tiny-clue[...]
IEEE
[12]
웹사이트
Two classic paper prizes for papers that appeared at ICML 2013
http://icml.cc/2013/[...]
2013
[13]
서적
Markov Random Fields and their Applications
American Mathematical Society
[14]
간행물
Enhancing gene regulatory network inference through data integration with markov random fields
2017-02-01
[15]
conference
A Markov random field model for term dependencies
ACM
[16]
간행물
Automatic Identification of Window Regions on Indoor Point Clouds Using LiDAR and Cameras
2014
[17]
서적
Markov Random Fields and Their Applications
American Mathematical Society
[18]
서적
グラフィカルモデル
講談社
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com