질문 불가능 그리드 그래프에 왜 제목MRF의 정확한 추론이
에 기록 된대로 위의 이미지에서 3 × 3 격자 그래프가있다. 접합 트리로 변환 할 수 있습니다. 그런 다음 유추 (likelihood/posterior 등 추정)에 메시지 전달 (product-sum algorithm)을 사용할 수 있습니다. 그리드 그래프의 정확한 추론이 왜 그렇게 어려운지 궁금합니다.
그리드가 커지면 교차점 트리를 찾는 것이 불가능합니까?
짧은 답변 : nxn 그리드의 경우 복잡도는 적어도 지수 n입니다.
접합 트리는 MRF의 유도 그래프에서 생성되며 제거 순서 (먼저 한계를 계산하기 위해 제거하는 변수)에 따라 달라집니다. 제거 된 비용은 유도 된 그래프에서 가장 큰 파벌의 크기에서 기하 급수적입니다. 자세한 내용은 this 논문을 참조하십시오.
우리가 접합점 트리에서 정확한 추론을 사용할 수 있다고하더라도, 복잡성은 사용 된 제거 순서의 유도 된 그래프에서 가장 큰 도당의 크기가 기하 급수적 일 것입니다.
가능한 가장 좋은 제거 순서는 nxn 격자의 n 인 트리 폭과 동일한 최대 클록 크기를 산출합니다. 그러나 그것을 찾는 효율적인 알고리즘은 없습니다.