접속 트리 알고리즘

Junction tree algorithm
연결 트리의 예

접속 트리 알고리즘('클리크 트리'라고도 함)은 일반적인 그래프에서 한계화를 추출하기 위해 머신러닝에 사용되는 방법이다. 본질적으로, 그것은 연결 트리라고 불리는 수정된 그래프에 믿음 전파 수행을 수반한다. 그래프는 데이터의 다른 섹션으로 나뉘기 때문에 트리라고 불린다. 변수의 노드는 가지들이다.[1] 사이클을 단일 노드로 클러스터링해 사이클을 없애는 것이 기본 전제다. 여러 가지 광범위한 질의 클래스를 동시에 더 큰 데이터 구조로 컴파일할 수 있다.[1] 특정 니즈를 충족하고 계산해야 할 사항에 대한 알고리즘은 서로 다르다. 추론 알고리즘은 데이터의 새로운 개발을 수집하고 제공된 새로운 정보를 바탕으로 이를 계산한다.[2]

접속 트리 알고리즘

후긴 알고리즘

  • 만약 그래프가 지시된다면, 그것을 지시하지 않도록 도덕화하라.
  • 증거를 소개하다.
  • 그래프를 삼각측량하여 화음으로 만드십시오.
  • 삼각형 그래프에서 연결 트리를 구성하십시오(접점 트리의 정점을 "슈퍼노드"라고 함).
  • 연결 트리를 따라 확률 전파(믿음 전파)

이 마지막 단계는 큰 트리 너비의 그래프에서는 비효율적이라는 점에 유의하십시오. 슈퍼노드 사이에 전달되는 메시지를 계산하는 것은 두 슈퍼노드의 변수에 대해 정확한 한계화를 수행하는 것을 포함한다. 따라서 트리 너비 k를 가진 그래프에 대해 이 알고리즘을 수행하면 시간 지수(k)가 걸리는 계산이 하나 이상 있게 된다. 그것은 메시지 패스 알고리즘이다.[3] Hugin 알고리즘은 Shafer-Shenoy에 비해 해결책을 찾는 데 더 적은 계산이 필요하다.

샤퍼-세노이 알고리즘

  • 재귀[3] 계산
  • Shafer-Shenoy 알고리즘을 여러 번 반복하면 Hugin 알고리즘이[4] 생성됨
  • 메시지 전달 방정식에[4] 의해 발견됨
  • 분리기 전위가 저장되지[5] 않음

Shafer-Shenoy 알고리즘은 접속 트리의 합계 산물이다.[6] 후긴 알고리즘보다 프로그램과 쿼리를 더 효율적으로 실행하기 때문에 사용된다. 알고리즘은 신념 함수에 대한 조건 계산을 가능하게 한다.[7] 지역 연산이 이루어지도록 하려면 공동 분포가 필요하다.[7]

기초이론

동적 베이시안 네트워크의 예

첫 단계는 베이지안 네트워크에만 관련된 것이며, 지시된 그래프를 비방향 그래프로 바꾸는 절차다. 우리는 방향과 상관없이 알고리즘의 보편적 적용이 가능하기 때문에 이렇게 한다.

두 번째 단계는 변수를 관측값으로 설정하는 것이다. 이것은 보통 조건부 확률을 계산할 때 필요하므로 조건부 변수의 값을 고정한다. 그 변수들은 또한 그들의 특정한 가치에 고정되어 있다고 한다.

코드 그래프의 예

세 번째 단계는 그래프가 이미 화음이 아니라면 화음이 되도록 하는 것이다. 이것이 알고리즘의 첫 번째 필수 단계다. 다음과 같은 정리를 이용한다.[8]

정리: 비방향 그래프 G의 경우 다음 속성이 동일하다.

  • 그래프 G는 삼각형이다.
  • G의 클라이크 그래프에는 접속 트리가 있다.
  • G에 대한 제거 순서가 있으며, 어떤 추가 에지로 이어지지 않는다.

따라서 그래프를 삼각측량함으로써 해당 접합 트리가 존재하는지 확인한다. 일반적인 방법은 노드에 대한 제거 순서를 결정한 다음 가변 제거 알고리즘을 실행하는 것이다. 가변 제거 알고리즘은 다른 쿼리가 있을 때마다 알고리즘을 실행해야 한다고 명시한다.[1] 이렇게 하면 초기 그래프에 더 많은 에지를 추가하게 되어 출력이 화음 그래프가 된다. 모든 화음 그래프에는 연결 트리가 있다.[4] 다음 단계는 접속 트리를 만드는 것이다. 그러기 위해 우리는 이전 단계의 그래프를 사용하고, 그에 상응하는 클라이크 그래프를 형성한다.[9] 이제 다음 정리는 우리에게 연결 트리를 찾을 수 있는 방법을 제공한다.[8]

정리: 삼각형 그래프를 지정하면 인접 클릭 A와 B의 교차점에 대한 카디널리티 A∩B 로 클릭 그래프의 가장자리에 가중치를 부여한다. 그러면 클라이크 그래프의 최대 중량 스패닝 트리는 접합 트리다.

연결 트리를 만들려면 클라이크 그래프에서 최대 중량을 추출하면 된다. 이것은 예를 들어 크러스칼의 알고리즘을 수정함으로써 효율적으로 수행될 수 있다. 마지막 단계는 얻은 접합 트리에 믿음 전파를 적용하는 것이다.[10]

사용: 접합 트리 그래프는 문제의 확률을 시각화하는 데 사용된다. 그 나무는 실제 나무의 건물을 형성하는 이진수 나무가 될 수 있다.[11] 그래프와 통과 네트워크를 대규모로 자동 결합하는 오토 인코더에서 특정한 용도를 찾을 수 있었다.[12]

추론 알고리즘

컷셋 컨디셔닝

루피 믿음 전파: 복잡한 그래프를 해석하는 다른 방법. 루피신앙 전파는 정확한 용액 대신 대략적인 용액이 필요할 때 사용된다.[13] 대략적인 추론이다.[3]

절단 조건화: 더 작은 변수 집합과 함께 사용된다. 컷셋 조절은 읽기 쉽지만 정확하지 않은 더 간단한 그래프를 허용한다.[3]

참조

  1. ^ a b c Paskin, Mark. "A Short Course on Graphical Models" (PDF). Stanford.
  2. ^ "The Inference Algorithm". www.dfki.de. Retrieved 2018-10-25.
  3. ^ a b c d "Recap on Graphical Models" (PDF).
  4. ^ a b c "Algorithms" (PDF). Massachusetts Institute of Technology. 2014.
  5. ^ Roweis, Sam (2004). "Hugin Inference Algorithm" (PDF). NYU.
  6. ^ "Algorithms for Inference" (PDF). Massachusetts Institute of Technology. 2014.
  7. ^ a b Kłopotek, Mieczysław A. (2018-06-06). "Dempsterian-Shaferian Belief Network From Data". arXiv:1806.02373 [cs.AI].
  8. ^ a b Wainwright, Martin (31 March 2008). "Graphical models, message-passing algorithms, and variational methods: Part I" (PDF). Berkeley EECS. Retrieved 16 November 2016.
  9. ^ "Clique Graph". Retrieved 16 November 2016.
  10. ^ Barber, David (28 January 2014). "Probabilistic Modelling and Reasoning, The Junction Tree Algorithm" (PDF). University of Helsinki. Retrieved 16 November 2016.
  11. ^ "Fault Diagnosis in an Industrial Process Using Bayesian Networks: Application of the Junction Tree Algorithm - IEEE Conference Publication". doi:10.1109/CERMA.2009.28. S2CID 6068245. {{cite journal}}: Cite 저널은 필요로 한다. journal= (도움말)
  12. ^ Jin, Wengong (Feb 2018). "Junction Tree Variational Autoencoder for Molecular Graph Generation". Cornell University. arXiv:1802.04364. Bibcode:2018arXiv180204364J.
  13. ^ CERMA 2009 : proceedings : 2009 Electronics, Robotics and Automotive Mechanics Conference : 22-25 September 2009 : Cuernavaca, Morelos, Mexico. Institute of Electrical and Electronics Engineers. Los Alamitos, Calif.: IEEE Computer Society. 2009. ISBN 9780769537993. OCLC 613519385.{{cite book}}: CS1 maint : 기타(링크)