베이 즈 넷에서의 변수 제거

Question

최근에 변수 제거법을 연구했으며 교사는 varibale 제거를 더 효율적으로 만드는 베이지안 네트워크임을 강조했습니다. 나는 이것에 대해 약간 혼란 스럽습니다. 왜 이런 경우입니까? 너희들이 나에게 약간의 아이디어를 주길 바래, 많은 감사.

로버트

Answer 1

나는 하나가 제거 할 수있는 변수가 하나 그것에 의존하는 하나의 변수가 하나이기 때문에 그것은 생각합니다. Bayes net에서는 단일 자식 노드가 있기 때문에 쉽게 찾을 수 있습니다.

Answer 2

베이지안 네트워크는, 구체적. 인해 내장 조건부 독립성 가정의

를 변수 제거의 순서를 이용할 조인트 분포 P (A, B, C, D)를 갖는 상상하고 알고 싶어 할 한계 P (a). 조건부 독립에 대해 아무 것도 모른다면 b, c 및 d를 합하여 계산할 수 있습니다. 도메인에 k-ary 도메인이 있다면 O (k^3) 작업을 수행해야합니다.

한편, A가 루트이고 B가 A의 하위이고 C가 B의 하위이고 D가 C의 하위 인 베이 넷이 있다고 가정합니다. 그런 다음 접합을 다시 작성할 수 있습니다 P (a | b) P (b | c) P (c | d) P (d)와 같이 계산하고 가능한 한 방정식의 오른쪽까지 3 개의 합계를 나눕니다. 실제로 P (a)를 계산하려면 sum_d P (d)의 값을 사전 계산하여이 함수를 저장할 수 있습니다. 마찬가지로, P (c | d) * sum_d P (d)의 값을 미리 계산하여 저장할 수 있습니다.

이렇게하면 O (k^w * + 1)의 작업이 끝납니다. 여기서 W *는 베이 넷의 모든 노드에있는 자식 중 가장 큰 수입니다. 이 경우 우리는 O (k^2)의 작업을 수행하는데, 이는 또한 우리가 기억해야만하는 가장 큰 조건부 확률 테이블의 크기입니다. 이것이 우리의 원래 O (k^3) 결과보다 낫다는 것에주의하십시오. 더 많은 변수가 있다면 더 좋을 것입니다.

요약하면 BN의 조건부 독립성으로 인해 변수를보다 효율적으로 소외시킬 수 있습니다. 이것에 대한 또 다른 설명은 http://www.cs.uiuc.edu/class/sp08/cs440/notes/varElimLec.pdf에서 찾을 수 있습니다.