{ x } ). } 이 문제의 풀이방법은 신뢰전파와 거의 같으며 합연산을 최대치연산으로 직변하는 것으로 족하다. 그래프 모델상에서의 주변화나 최대화와 같은 추정문제는 엄밀해나 상대오차이하의 근사값을 얻기위한 경우에는 NP - 난해 문제이다. 정확하게는 위에서 정의된 주변하 문제는 # P완성 문제이며, 최대화 문제는NP - 완성이다. 참조 [ 편집 ] ↑ Pearl, Judea ( 1982 ). 〈 Reverend Bayes on inference engines : A distributed hierarchical approach 〉 ( PDF ). 《 Proceedings of the Second National Conference on Artificial Intelligence 》. AAAI - 82 : Pittsburgh, PA. Menlo Park, California : AAAI Press. 133 - 136쪽. 2009년 3월 28일에 확인함. ↑ Kim, Jin H. ; Pearl, Judea ( 1983 ). 〈 A computational model for combined causal and diagnostic reasoning in inference systems 〉 ( PDF ). 《 Proceedings of the Eight
##에서는 리프노드에서 메시지를 계산하기 시작한다. 각각의 노드는 엣지를 통하여 받은 메시지를 루트노드를 향해 전파한다. 그래프가 트리구조이므로 대상 노드에게 메시지를 건네기 전에 모든 타 근접노드로부터 메시지를 받을수 있음이 보증된다. 이 전파법칙은 루트노드가 모든 근접노드로부터 메시지를 받을때까지 반복된다. 이단계 스테이지에서는 루트노드로부터 리프노드를 향하여 메시지를 보낸다. 이 경우, 메시지는 역방향으로전파된다. 모든 리프노드가 메시지를 받음으로 이 알고리즘은 종료한다. 계산이 종료된 후, 각 노드의 주변분포는 인접해있는 인자노드로부터의 메시지의 곱에 비례한다. p X v ( x v ) u N ( v ) u → v ( x v ). { displaystyle p - { X - { v } } ( x - { v } ) propto prod - { u in N ( v ) } mu - { u to v } ( x - { v } ). } 동일하게 어느 특정인자에 속해있는 변수집합의 주변분포는 변수에서의 메시지와 그 인자의 곱에 비례한다 : p X u ( x u ) f u (
##iagnostic reasoning in inference systems 〉 ( PDF ). 《 Proceedings of the Eighth International Joint Conference on Artificial Intelligence 》. IJCAI - 83 : Karlsruhe, Germany. 190 - 193쪽. 2009년 3월 28일에 확인함. ↑ Pearl, Judea ( 1988 ). 《 Probabilistic Reasoning in Intelligent Systems : Networks of Plausible Inference 》 2판. San Francisco, CA : Morgan Kaufmann. ISBN 1 - 55860 - 479 - 0. ↑ Weiss, Yair ( 2000 ). " Correctness of Local Probability Propagation in Graphical Models with Loops ". 《 Neural Computation 》 12 ( 1 ) : 1 - 41. doi : 10. 1162 / 089976600300015880. ↑ Mooij, J ; Kappen, H ( 2007 ). " Sufficient Conditions for Convergence of the Sum - Product Algorithm ". 《 IEEE Transactions on Information Theory 》 53 ( 12 ) : 44
} ( x - { v } ) } 는 균등분포가 된다. 인자노드u에서 변수노드v에 건네는 메시지. 메시지의 계산은 연접해있는 타 노드에서의 메시지의 곱을 취해 xv이외의 모든 변수에 대한 주변화를 실행하는 것으로 표현된다 : u → v ( x v ) = x u : x v = x v f u ( x u ) v N ( u ) { v } v → u ( x v ). { displaystyle mu - { u to v } ( x - { v } ) = sum - { mathbf { x }'- { u } : x'- { v } = x - { v } } f - { u } ( mathbf { x }'- { u } ) prod - { v ^ { * } in N ( u ) setminus { v } } mu - { v ^ { * } to u } ( x'- { v ^ { * } } ). } 여기서 N ( u ) 은 인자 노드 u에 연접해있는 모든 변수노드의 집합이 된다. N ( u ) { v } { displaystyle N ( u )
##다 : 변수 노드 v에서 인자노드 u로 건네는 메시지. 메시지의 계산은 인접해있는 모든 인자 그래프의 곱을 취하는 것으로 표현할 수있다 ( 그러나 대상 인자노드에서 온 메시지는 제외된다. 이것은 대상 인자노드에서는 메시지로 1을 보냈다고 간주하여도 무난하다 ) : v → u ( x v ) = u N ( v ) { u } u → v ( x v ). { displaystyle mu - { v to u } ( x - { v } ) = prod - { u ^ { * } in N ( v ) setminus { u } } mu - { u ^ { * } to v } ( x - { v } ). } 여기서 N ( v ) 은 변수노드v에 연접한 모든 인자노드의 집합이된다. N ( v ) { u } { displaystyle N ( v ) setminus { u } } 가 공집합일 경우에는 v → u ( x v ) { displaystyle mu - { v to u } ( x - { v } ) } 는 균등분포가 된다. 인자노드u에서 변수노드v에 건네는 메시지.
##있는 모든 변수노드의 집합이 된다. N ( u ) { v } { displaystyle N ( u ) setminus { v } } 가 공집합일 경우에는 u → v ( x v ) = f u ( x v ) { displaystyle mu - { u to v } ( x - { v } ) = f - { u } ( x - { v } ) } 가 된다. 보는바와같이 " 신뢰전파 " 의 이름의 유래는 위의 공식에서 오는 것임을 알수있다. 이 알고리즘에 의해서는 결합확률분포에 대한 주변분포를 계산하는 어려움이나 문제가 단순한 메시지의 곱과 합으로 감소된다. 트리 구조경우의 엄밀해 [ 편집 ] 신뢰전파의 가장 간단한 형태는 대상 인자그래프가 트리 구조인 경우이다. 이때, 신뢰전파는 주변분포의 엄밀해가 계산가능하며 이하 두 단계 스텝후에 종료된다. 이 알고리즘을 시작하기 전에 대상 그래프 안에 하나의 루트 노드를 정한다. 여기서 루트 노드가 아니며 엣지가 하나인 노드는 리프라 불린다. 일단계 스테이지에서는 리프노드에서 메시지를 계산하기 시작한다. 각각의 노드는 엣지를 통하여 받은 메시지를 루트노드를
##과 복잡성 5 참조 Sum - product알고리즘의 개요 [ 편집 ] 신뢰전파는 인자그래프상에서 실행되는 알고리즘이다. 여기서 인자그래프란 변수 " V " 와 인자 " U " 에 의해 구성되어있는 2부그래프이며 변수와 인자는 엣지로 연결되어있다. 이 그래프를 이용함으로써 결합확률질량함수를 아래와 같이 표현할 수 있다. p ( x ) = u U f u ( x u ) { displaystyle p ( mathbf { x } ) = prod - { u in U } f - { u } ( mathbf { x } - { u } ) } 여기서 xu는 인자 노드 u에 연접해있는 변수를 뜻하는 벡터이다. 모든 베이즈 네트워크와 마르코프 네트워크는 인자그래프 형식으로 표현이 가능하다. 이 알고리즘은 " 메시지 " 로 불리는 변수 xv를 인수로 취하는 함수를 노드간의 엣지를 따라 전파된다. 이들의 메시지는 특정 변수가 타 변수에 주는 영향 또는 " 상호작용 " 을 내포하고 있다. 메시지에는 두가지 종류가 있다 : 변수 노드 v에서 인자노드 u로 건네는 메시지. 메시지의 계산은 인접해있는 모든 인자 그래프의 곱을
Product Algorithm ". 《 IEEE Transactions on Information Theory 》 53 ( 12 ) : 4422 - 4437. doi : 10. 1109 / TIT. 2007. 909166. 원본 주소 " " 분류 : 그래프 알고리즘그래프 모형부호 이론숨은 분류 : 영어 표기를 포함한 문서 둘러보기 메뉴 개인 도구 로그인하지 않음토론기여계정 만들기로그인 이름공간 문서토론 변수 보기 읽기편집역사 보기 더 보기 검색 둘러보기 대문사용자 모임요즘 화제최근 문서 보기임의 문서로도움말기부 도구 여기를 가리키는 문서가리키는 글의 최근 올리기특수 문서 목록고유 링크문서 정보위키데이터 항목이 문서 인용하기 인쇄 / 내보내기 책 만들기PDF로 다운로드인쇄용 판 다른 언어 日 本 語 中 文 링크 편집 이 문서는 2019년 1월 10일 ( 목 ) 00 : 09에 마지막으로 편집되었습니다. 모든 문서는 크리에이티브 커먼즈 저작자표시 - 동일조건변경허락 3. 0에 따라 사용할 수 있으며, 추가적인 조건이 적용될 수 있습니다. 자세한 내용은 이용 약관을 참고하십시오. 미국 및 다른 국가에 등록되어 있는 Wikimedia Foundation, Inc.
신뢰전파 - 위키백과, 우리 모두의 백과사전 신뢰전파 위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 신뢰전파 ( Belief Propagation ) 또는 Sum - product 메시지 전달 ( sum - product message passing ) 은 베이즈 네트워크 또는 마르코프 네트워크등의 그래프 모델상에 작용하는 메시지 전달 알고리즘이다. 이 알고리즘은 이미 관측한 노드의 상태를 토대로 아직 관측하지 않은 노드의 주변분포를 각각 계산한다. 신뢰전파는 주로 인공지능이나 정보이론의 분야에서 널리 사용되고 있으며 저밀도 패리티 검사 부호, 터보 부호, 자유에너지 근사, 충족 가능성 문제를 포함하며 응용에 다수 성공함이 경험적으로 확인된 상태다. 이 알고리즘은 1982년 주디아 펄 [ 1 ] 에 의해 제안된것으로 당초에는 트리 구조상의 그래프 모델에서 작용되는 알고리즘을 후에 일반적인 트리 구조 모델에서도 작용할 수 있도록 확장하였다 [ 2 ]. 현재는 이 알고리즘이 일반 그래프 구조에서도 근사치를 주는 것으로 알려져있다 [ 3 ]. 한 가지 예를 들어 X = ( Xv ) 를 결합확률질량함수p를 갖는 확률변수의 집합이라하면 특정 노드의 확률을 가리키는 주변분포 Xi는 단순히
##합의 주변분포는 변수에서의 메시지와 그 인자의 곱에 비례한다 : p X u ( x u ) f u ( x u ) v N ( u ) v → u ( x u ). { displaystyle p - { X - { u } } ( mathbf { x } - { u } ) propto f - { u } ( mathbf { x } - { u } ) prod - { v in N ( u ) } mu - { v 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라는 엄청난 수에 달하며 컴퓨터상으로 계산하는 것은 매우 힘들어진다. 신뢰전파를 이용함으로써 대상 확률변수의 그래프 구조를 이용함으로써 주변분포의 계산을 보다 효율적으로 실행할 수 있다.