확률적 추론

확률적 추론은 확률 모델에서 관측된 증거가 주어졌을 때 쿼리 변수의 확률을 계산하는 것으로, 베이즈 네트워크 및 마르코프 네트워크에서 중심적인 추론 작업입니다.

Definition

확률적 추론은 지정된 확률 모델로부터 하나 이상의 쿼리 변수가 관측된 증거에 조건화된 확률과 같은 사후 분포를 정확하게 또는 근사적으로 계산합니다.

Scope

이 주제는 그래픽 모델에서 확률적 쿼리에 답하는 알고리즘을 다룹니다. 여기에는 변수 제거, 트리에서의 신념 전파, 조인 트리(클리크 트리) 알고리즘과 같은 정확한 방법과 루프형 신념 전파, 몬테카를로 샘플링(기각 샘플링, 우도 가중치, 마르코프 연쇄 몬테카를로)과 같은 근사 방법이 포함됩니다. 추론의 계산적 난이도와 정확성 및 확장성 간의 절충점을 다룹니다. 모델 자체의 구조는 베이즈 네트워크에서 다룹니다.

Core questions

• 전체 분포를 열거하지 않고 결합 모델에서 조건부 또는 주변 확률을 어떻게 계산합니까?
• 변수 제거는 효율적으로 정확한 답을 계산하기 위해 인수분해를 어떻게 활용합니까?
• 정확한 추론이 다루기 힘든 경우는 언제이며, 그 대신 어떤 근사 방법이 사용됩니까?
• 샘플링 기반 방법은 사후 확률을 어떻게 추정합니까?

Key concepts

• 주변 및 조건부 쿼리
• 변수 제거
• 신념 전파 (메시지 전달)
• 조인 트리 및 트리 폭
• 루프형 신념 전파
• 기각 샘플링 및 우도 가중치
• 마르코프 연쇄 몬테카를로
• 정확한 추론 대 근사 추론

Key theories

신념 전파

트리 구조 네트워크에서는 인접 노드 간에 지역 메시지를 전달하여 정확한 사후 확률을 계산할 수 있습니다. Pearl의 신념 전파는 이 분산 계산을 수행하며, 루프형 그래프에 적용될 경우 널리 사용되는 근사 추론 방법을 제공합니다.

조인 트리 (클리크 트리) 추론

일반 네트워크에서의 정확한 추론은 변수들을 클리크 트리로 클러스터링하고 그 위에서 메시지를 전파함으로써 조직될 수 있으며, 가장 큰 클리크(트리 폭)에 대해서만 지수적인 시간 복잡도를 가지면서 정확한 답을 제공합니다.

샘플링을 통한 근사 추론

정확한 추론이 불가능할 때, 우도 가중치 및 마르코프 연쇄 몬테카를로와 같은 몬테카를로 방법은 증거와 일치하는 샘플을 추출하여 사후 확률을 추정하며, 보장된 정확성을 확장성과 교환합니다.

Clinical relevance

추론 알고리즘은 확률 모델을 활용 가능하게 만듭니다. 이는 관측된 데이터가 주어졌을 때 숨겨진 변수의 확률을 계산함으로써 진단 및 의사결정 지원 시스템, 오류 수정 코드(신념 전파를 통해), 컴퓨터 비전, 음성 인식 및 생물정보학을 지원합니다.

History

Pearl의 신념 전파(1980년대)는 트리 네트워크에 대한 정확한 추론을 제공했으며, Lauritzen과 Spiegelhalter의 1988년 조인 트리 방법은 클리크에 대한 지역 계산을 통해 일반 네트워크로 정확한 추론을 확장했습니다. 일반적인 경우 정확한 추론이 NP-난해하다는 인식은 샘플링 및 변분 근사에 대한 광범위한 연구를 촉발했습니다.

Key figures

• Judea Pearl
• Steffen L. Lauritzen
• David J. Spiegelhalter
• Daphne Koller

Seminal works

• pearl1986
• lauritzen1988

Frequently asked questions

확률적 추론은 항상 다루기 쉽습니까?

아닙니다. 일반 베이즈 네트워크에서의 정확한 추론은 NP-난해하며, 그 비용은 네트워크의 트리 폭에 따라 증가합니다. 트리이거나 트리 폭이 낮은 네트워크의 경우 정확한 추론은 효율적이지만, 그렇지 않은 경우 샘플링 또는 루프형 신념 전파와 같은 근사 방법이 사용됩니다.

정확한 추론과 근사 추론의 차이점은 무엇입니까?

변수 제거 또는 조인 트리 알고리즘과 같은 정확한 추론은 참된 사후 확률을 계산합니다. 몬테카를로 샘플링 또는 루프형 신념 전파와 같은 근사 추론은 이를 추정하며, 이는 크거나 밀집하게 연결된 모델에 대해 정확한 계산이 너무 비쌀 때 필요합니다.