복잡한 함수의 탐사를 위한 최적해 기반의 마르코프 연쇄 몬테 카를로

Abstract

A lot of researches and scientific literatures have been devoted to the problem of analyzing a nonlinear objective function over a compact set. One of the most laborious parts among them is sampling from complex objective function which basically has expensive evaluation cost and additionally is nonlinear, nonconvex, high-dimensional, multi-modal, non-elliptical, extremely skew, and heavy-tailed. In this thesis, the problem to be solved is sampling for exploring complex objective function, and we divide it into two cases that one has information of the derivatives and the other has no information of the derivatives. An obvious approach to solve the problem is Markov chain Monte Carlo. However, it has many difficulties in the problem such as no guarantees of the existence of a stationary distribution, uncertain and slow convergence behavior, and the need of too many objective function evaluations. To overcome such difficulties, we develop two algorithms corresponding respectively to two cases which are that one called Opt-DREAMz combines the local optimization technique and the delayed rejection method with Differential Evolution Adaptive Metropolis algorithm, and the other called O-GPMC marries ideas from adaptive direction sampling and Gaussian Process so that it effectively reduces the number of objective function evaluations by utilizing surrogate function based on Gaussian Process which is easily evaluated. Opt-DREAMz has the advantages of differential evolution, subspace exploration, sampling from past states, optimized and quadratic approximated delayed rejection. Main features of O-GPMC are (a) the local and global optima information revealed by a Gaussian Process scheme is explicitly used for determining directions (b) sequential experimental design based on Gaussian Process provides effective and accurate 1-dimensional objective function approximation along a promising direction. Additionally, we study on Gaussian Process for sequential experimental design to achieve affordable 1-dimensional function approximation on minimal objective function evaluations to determine models of Gaussian Process in O-GPMC. Finally, we compare our algorithms with other typical existing methods applicable to the problem. The experimental results on simulated data show that the proposed algorithms have more efficient performance over the existing available MC methods on our problem.

밀집 데이터 집합 (Compact set) 위에 정의된 비선형 목적함수를 분석하기 위해 수많은 연구들과 과학적 자료들이 진행되었다. 그 중 복잡한 함수로부터 샘플 추출하는 것은 가장 어려운 부분 중 하나이다. 이 논문에서 정의한 복잡한 함수란, 주로 계산이 어려운 고비용 함수, 추가적으로 비선형성, 비볼록 형태 (nonconvex), 고차원, 다모드 (multi-modal), 비타원형, 왜곡형태, 두터운 꼬리 형태 등의 성질을 가지는 함수를 뜻한다. 이 논문에서는 해결한 문제로 복잡한 목적 함수의 탐사를 위한 샘플링으로 정의하였고, 세부적으로 미분정보들이 유무에 따라 두 가지 경우로 나누어 해결하고자 한다. 이러한 문제를 해결하기 위한 가장 대표적인 방법은 몬테 카를로 마코프 체인 방식이다. 그러나 위의 목적 함수들에 적용을 할 때 기존의 방식들은 정상 분포의 존재성에 대한 의문, 불특정하고 느린 수렴 행동성, 그리고 너무 많은 함수 계산의 필요성 등의 문제점을 가지게 된다. 이러한 문제점들을 극복하기 위해 위에서 언급한 두 가지 경우에 대응하는 두 가지 알고리즘을 제안하고자 한다. 첫째는, 미분정보가 있는 경우에 대해 함수의 국지적 정보와 지연거절 방식을 DREAMzs와 결합한 형태인 Opt-DREAMz를 제안하고, 둘째는, 미분정보가 없는 경우에 대해 쉽게 계산 가능한 가우시안 프로세스 (Gaussian Process)에 기초하여 대리 함수를 만들고 이를 이용하여 직접적인 목적함수의 계산을 줄이는 가우시안 프로세스와 조정 가능한 방향성 샘플 추출 (Adaptive direction sampling)의 결합 알고리즘인 O-GPMC를 제안하고자 한다. 3장에서는 미분정보가 없는 경우에 대해 기존 DREAM 시리즈 알고리즘들보다 효율성 및 효과성을 개선한 Opt-DREAMz를 제안하였다. 이는 목적 함수 혹은 분포의 지역 정보와 지연거절 방식을 스누커 업데이트 (snooker updating)을 제외한 DREAMzs와 결합함으로 인해서 적응 가능한 제안함수, 여러 개의 체인들, 지역정보의 활용과 같은 성질들을 포함하고 있다. 이 알고리즘은 에르고딕성(ergodicity)을 가지고 있으며 세부 균형 (detailed balance)을 만족시킨다. 또한, 분산 계산을 적용할 수 있다. 세 가지의 실험을 통해 Opt-DREAMz가 다른 DREAM 시리즈 알고리즘들에 비해 고차원, 다모드, 복잡한 시스템에 대해 강건(robust)하고 정확하고 효율적인 것을 확인하였다, 더불어, 이 알고리즘이 다른 알고리즘들에 비해 더 빠르게 수렴하는 것과 목적 함수의 더 정확한 추정을 가능하게 함을 확인하였다. 4장에서는 O-GPMC에서 사용할 가우시안 프로세스의 모델을 정하기 위해 최소한의 목적 함수의 계산 수를 사용하여 적절한 1차원 함수를 추정하는 연속적 실험 계획에 대한 가우시안 프로세스의 활용을 분석하고자 한다. 먼저 함수 추정과 최적화를 위해 최소한의 목적 함수의 계산을 이용하고자 하고 교차검증 표준오차 (Cross-validation root mean square error)를 종료 조건으로 활용하는 가우시안 프로세스에 기반한 일반적인 조정 가능한 연속적 실험 계획을 소개한 뒤에, 실험을 통해 교차검증 표준오차 편향성에 대해 연속적 실험 계획에서 가우시안 프로세스의 분산 함수와 베이지안 최적화의 습득 함수의 모델 선택이 미치는 영향을 확인했다. 우선 1차원 함수 추정에 대해 실험을 하고, 그 뒤에 더 고차원의 함수 추정과 최적화에 대해 실험을 진행하였다. 혼합 스튜던트 분포(Mixture of Student-t distribution)들에 실험한 결과 분산 습득 함수가 평균증진 습득 함수보다 함수 추정에 효과적임을 확인하였다. 추가적으로, 함수 추정에 대해서는, 마턴 (Matern) 분산 함수 (ν=3/2)와 분산 습득 함수의 조합이 교차검증 표준오차의 편향성에 대해서 가장 좋은 선택임을 알 수 있었고, 더 높은 차원에 대해서는 제곱 지수 분산 함수는 어울리지 않음을 확인하였다. 이것은 제곱 지수 분산 함수의 경우에 교차검증 표준오차가 기준치보다 더 큰 값에 수렴하거나 실제 표준오차보다 더 작아지게 될 수 있기 때문이다. 후자의 경우 부정확한 추정을 가져오게 된다. 또한, 이 실험을 통해 교차검증 표준오차의 편향성을 2차원 이상일 때 큰 고려사항이 되지 않음을 알 수 있었다. 베이지안 최적화의 관점에서는 마턴 분산 함수 (ν=1/2)는 어울리지 않음을 확인하였다. 5장에서는 가우시안 프로세스와 조정 가능한 방향성 샘플 추출을 이용하는 O-GPMC를 제안하였다. 이 알고리즘의 주된 특징은 방향성을 결정하기 위해 가우시안 프로세스를 통해 얻어진 국소 최적해와 광역 최적해가 사용된다는 것과 정해진 방향에 대해 가우시안 프로세스에 기반한 연속적 실험 계획을 이용해 1차원 목적 함수 추정을 진행하는 것이다. 여기서 쓰이는 가우시안 프로세스의 모델들은 4장의 결과로부터 얻어진 모델들을 사용하였다. 그 결과, 1차원 추정과 최적해 기반 방향성을 통해 주어진 문제에서 몬테 카를로 마코프 체인의 문제점들을 해결할 수 있었다. 추가적으로, 덩어리 샘플 추출, 희박 근사, 그리고 제한된 훈련 집합들을 적용하여 제안된 알고리즘의 계산 비용을 줄여주었고, 목적 함수의 최소한의 계산 비용을 제안하였다. 이 알고리즘의 효율성을 보이기 위해 혼합 스튜던트 분포들에 대해 가장 대표적인 두 가지 알고리즘 MT-DREAMzs와 CGMC와의 비교를 진행하였고, 결과적으로 O-GPMC로부터 얻어진 샘플들의 질이 가장 좋은 것과 O-GPMC의 수렴 효율성이 다른 알고리즘들과 비슷한 것을 보여주었다. 본 논문의 주된 의의는 복잡한 함수의 탐사를 위한 샘플 추출에 적합하도록 몬테 카를로 알고리즘 두 가지 경우에 따라 각각 알고리즘을 제안하였고, 특히 미분 정보가 없는 경우에 대해 가우시안 프로세스로부터 얻어지는 저비용의 대리 함수를 활용한 접근법을 최초로 제안하였으며, 제안된 알고리즘들의 우수함을 데이터 실험을 통하여 실증적으로 보여주었다는 것에 있다. 추가적으로 이러한 목적 함수에 어울리는 가우시안 프로세스의 모델에 대한 실험을 진행했다는 것도 의의가 있다. 본 논문에서 사용한 모델 말고도 다양한 가우시안 프로세스의 모델이 존재하므로 이들에 대한 추가적인 연구, O-GPMC의 아이디어의 다양한 추정 방법론들과 조정 가능한 방향성 샘플 추출 접근법들에 대한 응용, 그리고 O-GPMC의 설정 모수들에 대한 추가 연구, 마지막으로 다양한 형태의 추가 실험과 여러 방면의 실제 데이터 응용을 통한 알고리즘 견고성 검증 등을 앞으로 진행해 볼 필요가 있을 것이다.