Basic sampling methods로 Forward/Rejection/Importance sampling이 있다.
Forward sampling:
-먼저 Bayesian Network가 있을 때
Ex)
도둑이 들 확률은 0.001, 지진이 일어날 확률은 0.002, (P(Buglary=T)=0.001, P(Earthquake=T)=0.002)
도둑이 들었고 지진이 일어났을 때 알람이 울릴 확률은 0.95, (P(Alarm=T|Buglary=T and Earthquake=T) = 0.95)
도둑이 들었고 지진이 일어나지 않았을 때 알람이 울릴 확률은 0.94
...
알람이 울렸을 때 John이 call할 확률은 0.90 (P(JohnCalls=T|Alarm=T) = 0.90)
알림이 울리지 않았을 때 John이 call할 확률은 0.05 (P(JohnCalls=T|Alarm=F) = 0.05)
마찬가지로 Mary가 call하는 확률도 앎
Foward sampling의 과정은
1. Generate a sample from the Bayesian network
-Follow topological order and create such sample many, many, many times
2. Count the samples match the case, (예를 들면 P(Earthquake=T|MaryCalls=T)을 알고 싶다면)
-Buglary부터 MaryCalls까지 주어진 가정하의 확률로 sampling을 엄청많이 해서, MaryCalls가 T인 case내에 Earthquake가 T인 것들의 비율을 세서, 알고 싶은 P(E|MC)을 추정하는 방식이다.
단점은
Bayesian Network가 꽤 클 때, 계산량이 너무 많다.(Sampling을 무식하게 하다보니)
Rejection sampling:
Ex) 위의 예를 따라서
P(E=T|MC=T and A=F)을 알고자 하자.(목표설정)
Rejection sampling의 과정은 (Dicrete case)
1. Forward sampling하는 와중에 조건부확률의 조건(MC=T and A=F)에 맞지 않는다면 즉시 버리고 처음으로 돌아가서 sampling을 하는 것
Ex)
Buglary=F -> 문제 없음
Earthquake=T -> 문제 없음
Alarm = T -> 문제 있음(조건 A=F와 맞지 않음) -> 이후 JohnCalls와 MaryCalls에 대한 sampling하지 않고 다시 초기의 Buglary로 돌아감
2. Forward sampling과 마찬가지로 Count the samples match the case...
Rejection sampling의 과정은 (Continuous case)
1. 원하는 target distribution을 p(x)라 하자. (sampling하고 싶은 확률분포)
2. 다음 조건을 만족하는 보조 확률 분포(q(x))를 찾는다.(proposal distribution이라 한다.)
- sampling이 이미 가능한 확률분포(Uniform or Normal 등)
- 적당한 M값을 곱하여 p(x)를 envelope할 수 있는 확률분포, envelope한 다는 말은, 어느 x에서든 p(x)보다 Mq(x)가 큰
3. 다음 과정을 통해 sampling을 한다.
count = 0
while count < N:
sampling x ~ q(x)
sampling u ~ uniform(0,1)
if u < p(x)/Mq(x):
Accept x
count += 1
else:
Reject and resampling
여기서 p(x)/Mq(x)을 이해하는 것이 중요하다.
우리가 목표로하는 p(x)에 비해 "너무나 큰" Mq(x)라면 sampling하여 얻은 x를 그대로 취하기 보다는
"너무나 큰" 정도에 따라 "적절히" Accept하자는 것이다.
p(x)에 비해 너무나 큰 Mq(x)면 p(x)/Mq(x)가 매우 작을 것(Ex 0.01)이며
이에 따라 if u < p(x)/Mq(x)를 통과하기 힘들 것(0.01확률로 통과)
따라서, Mq(x)와 p(x) 사이의 영역이 Reject region이고 x축과 p(x)사이의 영역이 Accept region이 된다.
단점:
-Forward sampling보다는 sample의 개수가 적어도, 정확도는 높아 보이나, 어쨌든 reject region이 크면 그만큼 적당한 개수의 samples을 찾는데에 오래 걸릴 것이다.
-애초에 sampling할 p(x)와 유사한 q(x)를 잡지 않는 이상, sampling이 잘 안되서 현실에선 잘 사용하지 않음
Importance sampling:
-sampling을 해서 p(x)의 histogram을 그린다면, 이후 p(x)관련된 계산은 수월히 할 수 있지만, 원하는게 histrogram 전체가 아니라 특정 확률, 특정 기댓값을 원하는 상황이라면 그렇게 무식하게 histogram을 다 구하지 말고 그냥 원하는 것에만 집중하자는 컨셉이다. 따라서 "Use the wasted sample".
-E_(x~p)[X], P(X>3) 형태를 계산하는 것인데, 사실 확률은 기댓값으로 표현이 가능하기 때문에(Characteristic function) 대부분 자료들이 기댓값에 대해서 설명한다.
Importance sampling의 과정은 (Discrete case)
위와 마찬가지의 예제를 따라 P(Earthquake=T|MaryCalls=T and Alarm=F)=?
즉 구체적인 확률값을 근사하고자함 from sampling
SumSW = 0; NormSW= 0;
Iterate many:
SW = sample weight = 1
Generate a sample from the Bayesian network(즉 Buglary부터 MaryCalls까지 sampling)
(만약 Buglary=F, Earthquake=F, Alarm=F라면 P(Alarm=F|Buglary=F and Earthquak=F)=0.999를 SW에 곱)
