3. Monte Carlo Methods - Markov chain Monte Carlo, Stochastic Approximation Monte Carlo3

(1) Stochastic Approximation Monte Carlo (SAMC)

확률적 근사 몬테카를로(Stochastic Approximation Monte Carlo, SAMC) 알고리즘은 일반화 Wang-Landau(GWL) 알고리즘을 개선한 고급 몬테카를로 알고리즘이다.

일반적으로 표본이 추출되는 분포가 매우 복잡한 현상을 가질 때 그 분포에 여러 최빈수가 있는 경우가 흔하게 발생한다. 이러한 경우 표본(예로 Metropolis Hastings 표본)들이 임의의 한 최빈수근처에서 계속 추출되어 전체 공간의 최소값(Global Minima)을 구하지 못하는 국소 트랩(Local Trap)의 문제점을 가지게 된다. 이런 편향된 표본들은 좋은 추정량을 구할 수 없어 이러한 문제점을 벗어나기 위해 지금까지 많은 연구가 이루어 졌는데 대부분 표본의 수렴에 대한 이론이 없고, 있어도 수렴하는데 매우 오랜 시간이 걸려 추정치의 불확실성과 효율성 측면에서 단점을 가지고 있다. SAMC는 이러한 단점을 개선시키기 위해 GWL 알고리즘에 확률적 근사를 접근시킨 수정된 WL-GWL의 알고리즘이다.

SAMC 알고리즘의 가장 큰 특징은 표본 공간의 분할에 있다. SAMC에서의 표본 공간은 주어진 함수(예로, 베이지안 통계에서는 사후분포)에 따라 여러 부분 영역으로 나뉘어 지고, 각 부분 영역의 방문 빈도수를 기록해 모든 표본 부분 공간이 동등한 빈도수를 가지도록 조절 인자를 이용한다. 즉, 방문 빈도수가 과도하게 많은 부분 영역은 방문을 줄이고, 방문 빈도수가 과도하게 적은 부분 영역은 방문을 늘려 주어 알고리즘이 자동으로 모든 표본 공간을 넓게 탐색할 수 있게 만든다. SAMC는 이러한 자기 조절(Self Adjusting) 능력을 가지고 있으므로 국소 트랩을 쉽게 벗어나 원하는 분포의 최적(Optimization)의 값을 구할 수 있는 장점을 가지고 있다.

SAMC의 응용분야로 Importance Sampling, Model Selection, HPD Interval Construction, Marginal Density Estimation, Normalizing Constant Estimation, Neural Network Training, Protein Simulation 등이 있다.

▣ 국제 논문

1. Cheon, S. and Liang, F. (2008.01). Phylogenetic Tree Construction Using Sequential Stochastic Approximation Monte Carlo. BioSystems(1.784), 91, 1, 94-107.

2. Cheon, S. and Liang, F. (2009.11). Bayesian Phylogeny Analysis via Stochastic Approximation Monte Carlo, Molecular Phylogenetics and Evolution(3.609), 53, 2, 394-403.

3. Liang, F. and Cheon, S. (2009.12). Monte Carlo dynamically weighted importance sampling for spatial models with intractable normalizing constants, Journal of Physics: Conference Series, 197.

4. Kim, J. and Cheon, S. (2010.06). Bayesian Multiple Change-point Estimation with Annealing Stochastic Approximation Monte Carlo, Computational Statistics (0.276), 25, 2, 215-239.

5. Kim, J. and Cheon, S. (2010.07). Bayesian Multiple Change-point Estimation Using SAMC, Proceedings of the Tenth Islamic Countries Conference on Statistical Sciences (ICCS-X), Volume II, The Islamic Countries Society of Statistical Sciences, Lahore: Pakistan, 823-830.

6. Kim, J. and Cheon, S. (2010.09). A Bayesian regime-switching time series model, Journal of Time Series Analysis(0.761), 5, 31, 365-378.

7. Cheon, S. and Liang, F. (2011.09). Folding small proteins via Annealing Stochastic Approximation Monte Carlo, BioSystems(1.784), 105, 3, 243-249.

8. Jung, B.C., So, S. and Cheon, S. (2014.03), Exact inference in contingency tables via Stochastic approximation Monte Carlo, Journal of the Korean Statistical Society(0.465), 43, 1, 31-45.

9. Cheon, S., Liang, F., Chen, Y, Yu, K. (2014.07), Stochastic Approximation Monte Carlo Importance Sampling for Approximating Exact Conditional Probabilities, Statistics and Computing(1.429), 24, 4, 505-520.

10. Cheon, S. and Kim, J. (2014.07), A Bayesian structural change analysis via Stochastic Approximation Monte Carlo and Gibbs Sampler. Journal of Statistical Computation and Simulation(0.629), 84, 7, 1444-1470.

11. Kim, J. and Cheon, S. (2014.10), Stochastic approximation Monte Carlo Gibbs sampling for structural change inference in a Bayesian heteroscedastic time series model. Journal of Applied Statistics(0.449), 41, 10, 2157-2177.

12. Lim, H-K., Lee, J. and Cheon, S. (2017.01), Stochastic approximation Monte Carlo EM for change point analysis, Journal of Statistical Computation and Simulation(0.767), 87, 1, 69-87.

13. Kim, J, Cheon, S. and Jin, Z. (2020.03), Bayesian multiple change-points estimation for hazard with censored survival data from exponential distributions, Journal of the Korean Statistical Society(0.557), 49, 1, 15-31.

▣ 국내 논문

1. Cheon, S. and Jeong, S.H. (2008.12). Applications to Bayesian model selection problems via Stochastic Approximation Monte Carlo, Journal of the Korean Data Analysis Society, 10, 6, 3043-3056.

2. Cheon, S. (2009.06). Real protein prediction in an off-lattice BLN model via Annealing Contour Monte Carlo. 응용통계연구, 22, 3, 627-634.

3. Cheon, S. and Kim, H.S. (2009.06). Bayesian Inference in Phylogeny via Sequential Stochastic Approximation Monte Carlo, Journal of the Korean Data Analysis Society, 11, 3, 1221-1231.

4. Cheon, S., Lee, E. and Jin, S. (2009.08). Cluster Analysis via Stochastic Approximation Monte Carlo, Journal of the Korean Data Analysis Society, 11, 4, 1749-1760.

5. Cheon, S. and Lee, H.C. (2011.04). Bayesian Regime-switching Analysis via Stochastic Approximation Monte Carlo, Journal of the Korean Data Analysis Society, 13, 2. 599-609.

6. 전수영, 이희찬 (2012.02). 불완전 자료에 대한 Metropolis-Hastings Expectation Maximization 알고리즘 연구. 응용통계연구, 25, 1, 183-196.

7. Cheon, S. (2012.10). Approximating Exact Test of Mutual Independence in Multiway Contingency Tables via Stochastic Approximation Monte Carlo. 응용통계연구, 25, 5, 837-846.

8. 전수영 (2013.02). Exact Inference for Three-way Interaction Effects. Journal of the Korean Data Analysis Society, 15, 1, 41-51.

9. Kim, J and Cheon, S. (2013.11). Bayesian Multiple Change-point Estimation and Segmentation. Communications for Statistical Applications and Methods, 20, 6, 439-454.

10. 이승찬, 이재준, 전수영 (2017.02). MCEM을 이용한 정규혼합분포 추정. Journal of the Korean Data Analysis Society, 19, 1(B), 185-196.

11. 강효은, 전수영 (2018.04). 로지스틱 회귀모형에서 SAMCIS 알고리즘을 이용한 정확추론. Journal of the Korean Data Analysis Society, 20, 2, 621-632.

12. 김지용, 박원경, 전수영 (2019.04). 소셜네트워크자료를 위한 잠재적 위치군집 분석 개선 연구. Journal of the Korean Data Analysis Society, 21, 2, 661-672.

13. 전수영 (2019.10). 미디어자료 분할표 분석을 위한 정확추론. Journal of the Korean Data Analysis Society, 21, 5, 2303-2312.

14. 김민정, 장성봉, 서영수, 전수영 (2020.10). SAMC 알고리즘을 이용한 미디어 패널 개인화 추천 알고리즘. Journal of the Korean Data Analysis Society, 22, 5, 1835-1847.

15. 박원경, 전승환, 서영수, 전수영 (2021.02). MH-SAMC 알고리즘을 이용한 소셜네트워크 분석. Journal of the Korean Data Analysis Society, accepted.