아일랜드 알고리즘
Island algorithm섬 알고리즘은 숨겨진 마르코프 모델 또는 그 일반화 동적 베이지안 네트워크에 대한 추론을 수행하기 위한 알고리즘입니다.관찰된 노드에 따라 관찰되지 않은 각 노드에 대한 한계 분포를 계산합니다.
섬 알고리즘은 믿음 전파의 변형이다.더 적은 메모리 사용량을 더 긴 실행 시간으로 교환합니다.신뢰 전파에는 O(n)시간과 O(n)메모리가 소요되지만 아일랜드 알고리즘에는 O(n log n)시간과 O(log n)메모리가 소요됩니다.프로세서의 수가 무제한인 컴퓨터에서는, O([1]log n) 메모리만을 사용하면서, 합계 시간을 O(n)로 단축할 수 있습니다.
알고리즘
단순화를 위해 숨겨진 마르코프 모델에 대한 알고리즘을 설명한다.접속 트리를 사용하면 동적 베이지안 네트워크로 쉽게 일반화할 수 있습니다.
신뢰 전파에는 첫 번째 노드에서 두 번째 노드로 메시지를 보낸 후 이 메시지를 사용하여 두 번째 노드에서 세 번째 노드로 메시지를 계산하고 마지막 노드(노드 N)까지 계속합니다.독립적으로 노드 N에서 시작하여 역순으로 동일한 절차를 수행합니다.i번째 메시지는 (i-1)번째 메시지에 의존하지만 반대 방향으로 가는 메시지는 서로 의존하지 않습니다.노드의 한계 분포를 계산하려면 양쪽에서 온 메시지가 필요합니다.통상의 신뢰 전파에서는, 모든 메세지가 보존되어 O(n) 메모리가 사용됩니다.
섬은 평소처럼 메시지를 전달하는 것으로 시작하지만 (i+1)번째 메시지를 보낸 후 i번째 메시지를 버립니다.두 개의 메시지 전달 절차가 중간에 만나면 알고리즘은 체인의 각 절반에서 반복됩니다.
체인은 각 재귀 단계에서 둘로 분할되므로 재귀의 깊이는 log(N)가 됩니다.모든 메시지는 각 깊이 수준에서 다시 전달되어야 하므로 알고리즘은 단일 프로세서에서 O(n log n) 시간이 걸립니다.각 재귀 단계마다 2개의 메시지를 저장해야 하므로 알고리즘은 O(log n) 공간을 사용합니다.log(N) 프로세서를 지정하면 알고리즘을 O(n) 시간 내에 실행할 수 있습니다.따라서 각 재귀 스텝(N/2 + N/4 + N/8...)을 실행하는 것은 N/2 + N/4 + N/8...= 단일 프로세서에서 N시간).
