4.8 Stochastic Approximation Monte Carlo

Neural Network의 Multimodality issue. 패러미터는 p개인데 equation은 q개. q가 p보다 훨씬 작아서 관계성이 식으로밖에 나오지 않음. 따라서 identifiability 이슈가 발생하기 때문. gradient descent 방법으로 최적해 찾아내다 뭐 이렇게 말을 하는데 사실 이걸 최적해로 말할 수 없음.

combinatorial optimization에도 로컬 최적해가 다수 존재하고 글로벌 최적해 파악이 어려우므로 유사하게 multimodal issue 존재.

SAMC는 과거의 샘플 전체를 이용하므로 Monte Carlo긴 하나 MCMC는 아님.

에너지 펑션 \(-\log \psi (x)\), $ (x)$는 unnormalized density. 이 에너지 펑션을 U(X)로 둔다면 이는 결국 y축에 대응되는 값. 이 U(X)를 파티션한다. 이렇게 나눈 영역 E_i들은 각각 고유한 weight를 보유하고 있음. 난수 1개를 샘플링했을 때 이 난수가 영역 E_i에서 나왔다고 한다면, 이 영역 E_i에 배정되었던 weight를 줄이고 다른 모든 구간의 weight를 높인다. 이를 통해서 모든 영역에서의 고른 샘플링을 기대할 수 있음. 이 weight의 증감량을 얼마만큼 시킬 것인지가 stochastic Approximation을 통해서 얻어짐.

이를 모두 반영한 식은

c (x) _{i=1}^m I(X E_i)

이때 이의 denominator는 E_i에 대한 weight이며, 이것이 결국 c에 대응하는 부분인데 영역이 partition되었으므로 이를 mixture distribution의 형태로 나타내줌.

여기서 ^{(i)}=log g_i이고, g_i = _{E_i} (x). 따라서 이를 exp의 승으로 만드는 것은 log를 취했던 것을 벗기는 작업임.

_i : 구간 i에서 얼마만큼의 샘플을 생산할 것인가. 보통은 구간별 생산 갯수를 동일하게 하는 것을 목적으로 함. 이에 의해서 보통 이 알고리즘을 flat-histrogram 알고리즘이라고 부름.

gain factor sequence { k }{k=0}^. 이는 Stochastic Approximation에 필요함. gain factor _k = . 이때 t_0는 prospected value. 따라서 첫 이터레이션때는 1로 유지되고, 이후에 빠르게 감소함. 따라서 weight도 이에 영향받아 첫번째 이터레이션때는 일정하게 유지되다가 이후에 떨어진다. t_0가 크면 수렴이 빠르지만 그렇기 때문에 지나치게 커서는 안됨.

이렇게 생산한 샘플을 그냥 써서는 안되고, 획득한 샘플 ^{(t)}와 weight (theta^{(t)} )= g_i를 사용하여 Importance Sampling을 한번 해서 그 결과물을 사용해야 함.

????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????????

3시 18분