신뢰전파 - 위키백과, 우리 모두의 백과사전 신뢰전파 위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 신뢰전파 ( Belief Propagation ) 또는 Sum - product 메시지 전달 ( sum - product message passing ) 은 베이즈 네트워크 또는 마르코프 네트워크등의 그래프 모델상에 작용하는 메시지 전달 알고리즘이다. 이 알고리즘은 이미 관측한 노드의 상태를 토대로 아직 관측하지 않은 노드의 주변분포를 각각 계산한다. 신뢰전파는 주로 인공지능이나 정보이론의 분야에서 널리 사용되고 있으며 저밀도 패리티 검사 부호, 터보 부호, 자유에너지 근사, 충족 가능성 문제를 포함하며 응용에 다수 성공함이 경험적으로 확인된 상태다. 이 알고리즘은 1982년 주디아 펄 [ 1 ] 에 의해 제안된것으로 당초에는 트리 구조상의 그래프
, 자유에너지 근사, 충족 가능성 문제를 포함하며 응용에 다수 성공함이 경험적으로 확인된 상태다. 이 알고리즘은 1982년 주디아 펄 [ 1 ] 에 의해 제안된것으로 당초에는 트리 구조상의 그래프 모델에서 작용되는 알고리즘을 후에 일반적인 트리 구조 모델에서도 작용할 수 있도록 확장하였다 [ 2 ]. 현재는 이 알고리즘이 일반 그래프 구조에서도 근사치를 주는 것으로 알려져있다 [ 3 ]. 한 가지 예를 들어 X = ( Xv ) 를 결합확률질량함수p를 갖는 확률변수의 집합이라하면 특정 노드의 확률을 가리키는 주변분포 Xi는 단순히 p를Xi이외의 모든 노드에 대한 합을 구하는 것으로 포현가능하다 : p X i ( x i ) = [UNK] x [UNK] : x i [UNK] [UNK] x i p ( x [UNK] ). {
변수와 인자는 엣지로 연결되어있다. 이 그래프를 이용함으로써 결합확률질량함수를 아래와 같이 표현할 수 있다. p ( x ) = [UNK] u [UNK] U f u ( x u ) { [UNK] displaystyle p ( [UNK] mathbf { x } ) = [UNK] prod - { u [UNK] in U } f - { u } ( [UNK] mathbf { x } - { u } ) } 여기서 xu는 인자 노드 u에 연접해있는 변수를 뜻하는 벡터이다. 모든 베이즈 네트워크와 마르코프 네트워크는 인자그래프 형식으로 표현이 가능하다. 이 알고리즘은 " 메시지 " 로 불리는 변수 xv를 인수로 취하는 함수를 노드간의 엣지를 따라 전파된다. 이들의 메시지는 특정 변수가 타 변수에 주는 영향 또는 " 상호작용 " 을 내포하고 있다
는 모든 변수노드의 집합이 된다. N ( u ) [UNK] { v } { [UNK] displaystyle N ( u ) [UNK] setminus [UNK] { v [UNK] } } 가 공집합일 경우에는 [UNK] u → v ( x v ) = f u ( x v ) { [UNK] displaystyle [UNK] mu - { u [UNK] to v } ( x - { v } ) = f - { u } ( x - { v } ) } 가 된다. 보는바와같이 " 신뢰전파 " 의 이름의 유래는 위의 공식에서 오는 것임을 알수있다. 이 알고리즘에 의해서는 결합확률분포에 대한 주변분포를 계산하는 어려움이나 문제가 단순한 메시지의 곱과 합으로 감소된다. 트리 구조경우의 엄밀해 [ 편집 ] 신뢰전파의 가장 간단한 형태는 대상 인자그래프가 트리 구조인 경우이다. 이때
p를Xi이외의 모든 노드에 대한 합을 구하는 것으로 포현가능하다 : p X i ( x i ) = [UNK] x [UNK] : x i [UNK] [UNK] x i p ( x [UNK] ). { [UNK] displaystyle p - { X - { i } } ( x - { i } ) = [UNK] sum - { [UNK] mathbf { x }': x'- { i } [UNK] neq x - { i } } p ( [UNK] mathbf { x }'). } 그러나 이 계산방식은 만일 확률변수들이100개의 이진변수라 한다하여도 이 확률수 전체의 수는 299 [UNK] 6. 338 x 1029라는 엄청난 수에 달하며 컴퓨터상으로 계산하는 것은 매우 힘들어진다. 신뢰전파를 이용함으로써 대상 확률변수의 그래프 구조를 이용함으로써 주변분포의 계산을 보다
f propagation 알고리즘이라 불린다. 대상 그래프가 리프를 포함하지 않기 때문에 이 알고리즘은 신뢰전파의 전파규칙을 살짝 수정할 필요가 있다. 우선 모든 변수의 초기 메시지는 1로 초기화 한다. 다음, 각 반복회수에서 위의 정의에 따라서 메시지를 갱신한다. 이때 리프나 트리 구조의 부분그래프에서 기지의 메시지가 전달될때까지 ( 즉, 메시지가 수렴할때까지 ) 모든 메시지를 갱신한다. 대상 그래프가 트리구조인 경우 loopy belief propagation 알고리즘은 대상 그래프의 직경과 동등한 반복수내에 원래 알고리즘에 의한 신뢰전파로 얻을수 있는 메시지로 수렴한다. loopy belief propagation 알고리즘의 정확한 수렴조건은 아직 분명하지 않지만 통상 단일 루프 그래프에서는 수렴하는 것으로 알려져 있다 [ 4 ]
[UNK] [UNK] u [UNK] N ( v ) [UNK] u → v ( x v ). { [UNK] displaystyle p - { X - { v } } ( x - { v } ) [UNK] propto [UNK] prod - { u [UNK] in N ( v ) } [UNK] mu - { u [UNK] to v } ( x - { v } ). } 동일하게 어느 특정인자에 속해있는 변수집합의 주변분포는 변수에서의 메시지와 그 인자의 곱에 비례한다 : p X u ( x u ) [UNK] f u ( x u ) [UNK] v [UNK] N ( u ) [UNK] v → u ( x u ). { [UNK] displaystyle p - { X - { u } } ( [UNK] mathbf { x } - { u } ) [UNK] propto f - { u } ( [UNK] mathbf { x } - { u } ) [UNK] prod - { v [UNK] in N
하다. 주변화를위한 근사수법으로는 그 밖에도 변분법이나몬테칼로법을 포함한 몇가지 수법이 제안되어있다. 일반적인 그래프상에서 엄밀한 주변분포값을 구하기위해선 정션트리 알고리즘을 꼽을수 있다. 이 알고리즘은 대상그래프를 트리구조로 수정하여 그 후 신뢰전파를 적용한다. 정션트리에서는 루프를 포함한 클러스터를 한개의 노드로 묶어 루프를 제거하여 신뢰전파의 수렴성을 보존한다. 유사 알고리즘과 복잡성 [ 편집 ] 유사 알고리즘으로는 일반적으로 비터비 알고리즘을 꼽을수 있다. 비터비 알고리즘은 max - product 또는 min - sum 알고리즘으로도 알려져 있으며 관련된 모델의 최대화문제를 푸는데 쓰인다. 구체적으로 설명하자면 이 알고리즘은 주변분포를 구하는 것이 아니라 대역 함수를
max - product 또는 min - sum 알고리즘으로도 알려져 있으며 관련된 모델의 최대화문제를 푸는데 쓰인다. 구체적으로 설명하자면 이 알고리즘은 주변분포를 구하는 것이 아니라 대역 함수를 최대화하는 값 x { [UNK] displaystyle [UNK] mathbf { x } } 을 구한다. 이것은 확률적으로 가장 일어나기 쉬운 값을 선택하는 것과 같으며 arg max기호를 써서 정의할 수있다 : arg max x g ( x ). { [UNK] displaystyle [UNK] arg [UNK] max - { [UNK] mathbf { x } } g ( [UNK] mathbf { x } ). } 이 문제의 풀이방법은 신뢰전파와 거의 같으며 합연산을 최대치연산으로 직변하는 것으로 족하다. 그래프 모델상에서의 주변화나 최대화와 같은 추정
{ u } } ( [UNK] mathbf { x } - { u } ) [UNK] propto f - { u } ( [UNK] mathbf { x } - { u } ) [UNK] prod - { v [UNK] in N ( u ) } [UNK] mu - { v [UNK] to u } ( x - { u } ). } 이들의 계산은수학적귀납법에 의해 증명이 가능하다. 일반적인 그래프상의 근사 알고리즘 [ 편집 ] 기묘하게도 일반적인 그래프상에서도 트리 구조와 동일한 알고리즘을 사용할 수 있다. 이 알고리즘은 대상 그래프가 일반적으로 루프를 포함하고 있기 때문에 " loopy " belief propagation 알고리즘이라 불린다. 대상 그래프가 리프를 포함하지 않기 때문에 이 알고리즘은 신뢰전파의 전파규칙을 살짝 수정할 필요가 있다. 우선 모든 변수의 초기 메시지는 1로
신뢰전파(Belief Propagation) 또는 Sum-product 메시지 전달 (sum-product message passing)은 베이즈 네트워크 또는 마르코프 네트워크 등의 그래프 모델상에 작용하는 메시지 전달 알고리즘이다. 이 알고리즘은 이미 관측한 노드의 상태를 토대로 아직 관측하지 않은 노드의 주변분포를 각각 계산한다. 신뢰전파는 주로 인공지능이나 정보이론의 분야에서 널리 사용되고 있으며 저밀도 패리티 검사 부호, 터보 부호, 자유에너지 근사, 충족 가능성 문제를 포함하며 응용에 다수 성공함이 경험적으로 확인된 상태다. 이 알고리즘은 1982년 주디아 펄에 의해 제안된것으로 당초에는 트리 구조상의 그래프 모델에서 작용되는 알고리즘을 후에 일반적인 트리 구조 모델에서도 작용할 수 있도록 확장하였다. 현재는 이 알고리즘이 일반 그래프 구조에서도 근사치를 주는 것으로 알려져있다. 한 가지 예를 들어 X=(Xv)를 결합확률질량함수p를 갖는 확률변수의 집합이라하면 특정 노드의 확률을 가리키는 주변분포 Xi는 단순히 p를Xi이외의 모든 노드에 대한 합을 구하는 것으로 포현가능하다: p X i (x i) = ∑ x ′ : x i ′ ≠ x i p (x ′) . {\displaystyle p-{X-{i}}(x-{i})=\sum -{\mathbf {x} ':x'-{i}\neq x-{i}}p(\mathbf {x} ').} 그러나 이 계산방식은 만일 확률변수들이100개의 이진변수라 한다하여도 이 확률수 전체의 수는 299 ≈ 6.338 x 1029라는 엄청난 수에 달하며 컴퓨터상으로 계산하는 것은 매우 힘들어진다. 신뢰전파를 이용함으로써 대상 확률변수의 그래프 구조를 이용함으로써 주변분포의 계산을 보다 효율적으로 실행할 수 있다.