[ML/Lecture] 5. Inference in BN

 

< Inference in Bayesian Networks >

burglary부분에서 sum의 부분을 실질적으로 구현하기 위해서는 for loop을 통해 계속해서 계산을 할 수 있을 것이다. 각 variable의 value들에 대해 enumeration을 진행한다고 하면 CPT만큼의 space가 필요하겠지만 time-complexity는 기하급수적으로 늘어나게 될것이다. 

위의 트리를 보면 알 수 있다. +는 전체 sum을 뜻하는데 각각의 길목마다 sum을 해서 올라가야 하는 구조이다. 이런식으로 계산하게 되면 중복되는 부분이 많아진다. 즉 계산했던 부분들이 반복되는 문제점이 있다. 이는 낭비이다. 이 부분이 exponential time complexity를 만들어 내는 것이다. 다음 의사코드를 확인해보자.

결국 recursion이 반복되는 모습이다. 이를 피하기 위해서는 어떻게 하면 좋을까?  

이런 방식을 피하기 위해서는 이전의 값을 저장하는 방식으로 접근한다. 즉 top->down 보다 bottom->up으로 접근하면 더 편리하다. variable elimination algorithm이란 variable들을 특정 value값으로 지정하면서 올라오는 것이다. 이 방식으로는 같은 계산을 반복할 필요가 없다.  f4와 f5는 다음과 같이 조건 a가 true인지 false인지에 따라 다음과 같이 계산하면 된다. 

f3은 조금 복잡한데, a,b,e가 전부 정해지지 않았기 때문에 각각의 경우에 대해 8가지의 값이 나오게 된다. 이와 관련된 sumation을 계속 진행하게 되면 다음과 같이 전개가 되면서 간략화된다. 주의할 점은 matrix product가 아니라 pointwise product라는 점이다.

다음 앞의 두개의 product와 pointwise product를 수행한다고 하면 다음과 같은 계산이 이루어진다. 4x4로 16가지 경우의 수가 나오는 것이 아니라 겹치는 항목들은 생략하면서 계속 수행하게 된다. 

 

sumation( p(m|a) )는 결국 값이 1이 된다. m이 true일 확률과 false일 확률을 다 더한 값이기 때문이다. 따라서 위의 그림에서 m이라는 variable은 irrelevant variable,즉 필요없는 value이다. 이는 관련 이론이 있는데 j에 대해서는 j의 모든 조상들이 아니고서는 irrelevant하다.

위의 두가지 경우 처럼 여러가지 베이지안 네트워크에서 두개의 노드가 연결된 경우의 수가 여러개일 경우에는 CPT개수가 linear하지 않고 기하급수적으로 늘어날 수 있다. 

확률을 계산하기 위해서 exact inference by enumeration는 앞에서부터 계산하기 때문에 recursion에 의해 했던 계산을 계속 반복하게 되지만 (top-bottom) variable elimination은 bottom up 방식으로 계산된 값을 가지고 뒤에서부터 계산해 나가므로 했던 계산에 대한 반복을 피할 수 있다. 하지만 결국 multiple connect라면 계산은 힘들어 질 수 밖에 없다. 

따라서 NP-Hard한 문제를 세밀하게 계산하는 방식이 아닌 근사치를 구하는 방법이 이용되기도 한다. 시뮬레이션을 통해 근사치를 구하는 것이다. 방법은 rejection sampling, likeihood weighting, markov-chain-monte-carlo가 있다. 

먼저 direct sampling method를 알아보자. 

coin이라는 노드가 있고, coin이 head일 확률이 0.5라고 하자.  direct sampling은 ramdom한 반복에 의해 simulation을 할 수 있다. 그 결과를 따라 관심있는 확률을 계산하겠다는 것이다. 

위의 네트워크에는 4개의 variable이 있다. 따라서 하나의 sampling은 각각의 노드가 true/false의 값을 갖는 하나의 케이스가 될 것이다. 

cloudy가 true로 sampling 되었기 때문에 springkler가 true일 확률은 10%로 다시 샘플링을 하는 것이다. 마찬가지 rain도 동일하게 진행한다. 

랜덤하게 sampling을 한 결과 sprinkler가 false, rain은 true가 되었다. 이때는 wet grass가 true일 확률을 0.9로 시뮬레이션을 진행하게 된다. 

 결과적으로 true, false, true, true가 하나의 sample case가 되었다. 이런 sample을 수많이 반복한다. 그리고 나서, 예를 들어 p에 rain이 false, sprink true, 뭐 이런식으로 하나의 경우를 지정해서 그 확률을 구하고 싶다고 하자, 이때 이제 확률을 구한다고 하면, 전체 케이스에 대해서 해당 조건을 만족하는 만족하는 sample들만 추려내면 된다. 그 샘플들에 대해서 원하는 현상이 일어난 경우만 보면 확률이 된다. 즉, 조건에 해당하는 케이스 수 분에 해당케이스 수 를 하면 되는 것이다. 이 방식으로 계산하면 근사치를 쉽게 알아낼 수 있다. 

  rejection sampling은 단순하게 100개의 sampling을 할 때에 sample의 조건인 e를 만족하는 것만 저장을 하고, 그렇지 않은 것들은 어짜피 계산에 필요하지 않기 때문에 저장을 하지 않겠다는 것이다. 즉, condition을 만족하는 것만 저장을 하겠다는 것이다! 

  하지만 rejection sampling역시 단점이 존재하는데 p(e)의 개수가 굉장히 작다는 것이다. 경우가 작게 나온 만큼 충분한 경우를 확보하지 못해 오류가 발생할 확률이 크다. 따라서 충분한 보기를 확보하기 위해서는 loop를 굉장히 많이 돌아야 할 수도 있다.

이를 모든 variable에 대해서 열어놓고 sampling을 하는 것이 아니라, evidence variable들은 fix를 해 놓고, non-evidenece variable들에 대해서만 sampling을 하고 그것의 weight를 축적하자는 것이 likelihood weighting 방법이다. 예를 들어 보면 다음과 같다. 

지금은 sprinkler와 wetgrass가 true인 경우 다른 확률들을 보고싶은 것이다.여기서는 rain이 true일 확률. 따라서 여기에 대해서는 sampling을 하지 않는다.(fix) 대신에 이 evidence가 나오기 위한 weight을 1로 지정하고 시작한다. 

sampling을 했더니 cloudy가 true가 나왔다. 그런데 cloudy가 true일때 sprinkler가 true가 나올 확률이 0.1이므로 weight로 추가를 한다. 좀 rare한 케이스이기 때문이다. 바로 sample하나하나가 weight을 가지게 되는 것이다. 여기서 다시 rain이 true가 나왔다.

이때 sprinkler도 true, rain도 true, wetgrass도 true라면 이는 1x0.1x0.99의 가중치를 가지는 sample이다. 이런방식으로 각각의 sample에 대해서 weight정보를 더해서 쌓아가게 된다. 

따라서 전체 weight의 합중에서 원하는 케이스에 해당하는 weight의 합을 계산하면 원하는 값을 계산할 수 있다.

 =>   < rain이 true인 경우의 weight을 축적, rain이 false인 weight을 축적 >

 그 다음은 mcmc이다. markov-chain은 다음단계에 대한 상태정보가 현재상태의 상태정보만 유의미하게 작동하며 과거의 상태는 영향을 미치지 않는다는 것이였다.  

즉 non-evidence에 따라 상태를 나누는 것이다. 이때 gibbs sampling(mcmc의 종류)은 현재 sampling이 된 state를 기준으로, 하나의 variable만 매번 change하는 것이다. 

  결과적으로 나오는 sampling을 살펴보자. 두 sprin과 wet은 fix가 되어있고, cloudy와 rain만 바뀌는데 각 state마다 둘중 하나만 바뀐다. cloudy가 false일때 rain이 true일 확률은 0.2이다. 이런 식으로 sample을 모으게 되면 모든 경우는 evidence는 만족하게 된다. 이 중에서 원하는 조건에 해당하는 확률을 구하는 것이다. MCMC는 sampling하는 단계부터 계산하는 것이 차이점이라 할 수 있다. 

  이때 sampling을 할때 non-evidence varialbe의 최소한으로 만족하는 조건은 markov blanket에 대한 확률값이 주어져야 계산이 가능하다는 것이다.