가변 제거

Variable elimination

가변 제거(VE)는 베이시안 네트워크마르코프 무작위 필드확률론적 그래픽 모델에서 단순하고 일반적인 정확한 추론 알고리즘이다.[1]변수의 부분 집합에 대한 조건부 또는 주변 분포의 추정에 사용할 수 있다.알고리즘은 기하급수적인 시간 복잡성을 가지고 있지만 적절한 제거 순서를 사용할 경우 저나무 너비 그래프의 경우 실제로 효율적일 수 있다.

요인들

변수 의 잠재적 라고도 하는 알고리즘 복잡성 의 키 감소는 변수 f f}의{\ v}을(를 음수가 아닌 숫자로 인스턴스화(일반적으로 f)하는 것과 [2] 인자가 반드시 정해진 해석을 가지고 있는 것은 아니다.확률분포나 조건분포와 같이 서로 다른 표현의 인자에 대해 연산을 수행할 수 있다.[2]이 연산의 복잡성이 기하급수적이기 때문에 공동 분포는 종종 너무 커져서 감당할 수 없게 된다.따라서 변동 제거는 요소화된 실체를 계산할 때 더 실현가능해진다.

기본 운영

변수 합계

SO(Sum-out) 또는 한계화라고 하는 알고리즘 1은 인자 집합에서 단일 변수 을(를) 제거하고 결과 요인 집합을 반환한다.[3]알고리즘 수집 관련은 변수 을(를) 포함하는 에서 해당 요인을 반환하기만 하면 된다

알고리즘 1 합계( v )

= 과(와) 관련된 요인 수집
= 의 모든 요인의 제품


돌아오다

여기 공동 확률 분포가 있다. 변수는 최소 - (가) 나머지 변수에 대해 일치해야 하는 인스턴스화 집합 간에 요약될 수 있다. 값은 요약할 변수인 경우에는 관련이 없다.[2]

진실의 진실의 진실의 거짓의 거짓의 0.80
거짓의 진실의 진실의 거짓의 거짓의 0.20

}를 제거한 후 참조가 제외되고 나머지 변수와 각 인스턴스화의 합에 대해서만 분포가 남게 된다

진실의 진실의 거짓의 거짓의 1.0

합계 연산을 따르는 결과 분포는 }를 언급하지 않은 쿼리에만 응답하는 데 도움이 된다[2] 또한 합계 연산은 유사하다.

인자 곱하기

여러 요인 간에 제품을 계산하면 각 요인의 단일 인스턴스화와 호환되는 요인이 발생한다.[2]

알고리즘 2 다중 요소( [2]

= ( ),... . . ( m ){\ ...,의 제품 사이의 모든 변수의 결합.
= f f 대한 인수(모든f {\ f
z 에 대해
~ m 의 경우
= 변수 }의 인스턴스화(instimation)가 z 과(와) 일치함
돌아오다

인자 곱셈은 상호적일 뿐만 아니라 연관성도 있다.

추론

The most common query type is in the form where and are disjoint subsets of , and is observed taking value . A basic algorithm to computing p(X E = e) is called가변 제거(VE), 먼저 투입한다.[1]

이 알고리즘은 별도의 베이시안 네트워크 B에서 p ( = ) 을(를) 계산한다.[1]VE는 SO를 호출하여 변수를 하나씩 제거한다.좀 더 구체적으로, 알고리즘 2에서 (는) B에 대한 조건부 확률표("CPTs")의 집합 이고, X (는) 쿼리 변수 이며, 관찰된 값의 목록이며, 은 {이다.은(는) U- X 에 대한 제거 순서로서 E 은(는) X E을(으)를 가리킨다

가변 제거 알고리즘 VE( , , E, e , )

σ이 비어 있지 않은 상태에서 적절한 CPT로 요인 곱하기
▼ {\ \sigma 에서 첫 번째 변수 제거
} = sum-out(, )
( , = e) = 모든 요인 의 곱

돌아오다

주문

변수를 제거하는 최적의 순서를 찾는 것은 NP-하드 문제다.따라서 순서에 따라 성능을 더 잘 최적화하기 위해 다음과 같은 경험적 접근법이 따를 수 있다.

  1. 최소 도:가능한 가장 작은 요인을 구성하는 변수를 제거하십시오.[2]
  2. 최소 충만: 모든 CPT에 의해 표현된 가변 관계를 보여주는 비방향 그래프를 구성함으로써 제거 후 가장자리가 최소로 추가되는 변수를 제거하십시오.[2]

참조

  1. ^ a b c 장, N.L, 풀, D.:베이지안 네트워크 계산에 대한 간단한 접근법인: 제7회 캐나다 인공지능 회의,pp. 171-178.스프링거, 뉴욕 (1994년)
  2. ^ a b c d e f g h Darwiche, Adnan (2009-01-01). Modeling and Reasoning with Bayesian Networks. doi:10.1017/cbo9780511811357. ISBN 9780511811357.
  3. ^ Koller, D, Friedman, N.: 확률론적 그래픽 모델: 원리와 기법.MIT 프레스, 캠브리지, MA(2009)