Many problems in science and engineering require estimation of unknown quantities from a sequence of noisy and partial observations. In most cases, the problems can be easily solved, from a theoretical perspective, within a sequential Bayesian inference framework such that the unknown quantities can be inferred from posterior distributions that are recursively computed by the prior distributions of the unknown quantities and the likelihood functions of the observations. In practice, however, numerical approximate techniques are necessary due to the computational intractability of the theoretical methods.
As one of the approximate techniques, Sequential Monte Carlo (SMC) methods are a class of simulation-based methods designed to use random samples to recursively simulate the posterior distributions. Over the last few years, the methods have become extremely popular with their supportability of both nonlinearity and non-Gaussianity allowing the problems to be much more realistically modeled.
The basis of SMC methods is a Sequential Importance Sampling (SIS) algorithm that is a sequential version of an Importance Sampling (IS) algorithm in Monte Carlo (MC) methods. Because of the degeneracy problem of the SIS scheme, however, SMC methods only using SIS do not provide good estimation performance. To solve this problem, a Resampling algorithm is generally used. Even though it has some limitations such as the loss of diversity problem, there have been no better alternatives to the resampling scheme with respect to estimation accuracy, computational cost and algorithmic efficiency. As a result, the combination of SIS and resampling has been widely regarded as generic SMC methods in the most of literature and many advanced versions developed from the generic methods have been proposed for some improvements of the generic ones.
In this thesis, we propose a novel algorithm, called Dicing, designed to not only solve the degeneracy problem of the SIS but also avoid the loss of diversity problem of the resampling. With this proposed algorithm as the alternative to the resampling, we finally suggest the combination of SIS and Dicing as new generic SMC methods. By theoretical analysis and simulation study, we have consistently shown the justifications of the dicing algorithm and the large performance benefits of the new generic SMC methods.
과학 및 공학의 많은 문제들은 시스템의 특정 상태를 관련현상의 관찰을 통해서 추론하는 과정을 필요로 한다. 이론적으로, 대부분의 문제들은 수학적으로 정의된 베이지안 추론 기법 내에서 쉽게 해결된다. 하지만, 이 방법은 실제 문제에는 바로 적용이 불가능하며, 근사화 과정을 필요로 한다. 이 중 순차몬테칼로 방법은 표본추출을 기반으로 근사화하는 방법으로 시스템의 비선형성 및 비가우시안 특성까지 반영할 수 있기 때문에 매우 다양한 분야에서 활발하게 사용되고 있다. 이 방법은 순차중요표본추출이라는 기법을 그 기반으로 하며, 이는 중요한 정보를 담고 있는 지역의 표본들을 확률에 근거하여 중점적으로 추출되게 함으로써, 적은 수의 표본으로 정확한 근사화를 가능하게 한다. 하지만 이 순차중요표본추출 기법은 시간이 지남에 따라 표본들이 흩어지는 퇴보 문제를 가지고 있기 때문에, 표본재추출 기법을 이용하여 다시 표본을 추출하는 과정을 필요로 한다. 그러나 불행하게도 이 표본재추출 기법은 역으로 시간이 지남에 따라 표본들이 지나치게 뭉쳐지는 피폐 문제를 야기하게 된다. 그럼에도 불구하고, 현재까지 이 표본재추출 기법보다 더 나은 대안이 없었기 때문에 순차몬테칼로 방법은 순차중요표본추출 기법과 표본재추출 기법을 그 근간으로 하고 있다. 본 논문에서는 표본재추출 기법의 대안으로서 퇴보 및 피폐 문제를 동시에 해결할 수 있는 다이싱 기법을 제안한다. 나아가, 순차중요표본추출 기법과 다이싱 기법을 새로운 순차몬테칼로 방법으로 제안한다. 이론적인 분석 및 시뮬레이션 연구에 의해, 제안된 다이싱 알고리즘의 이론적 증명과 또한 제안된 순차몬테칼로 방법의 성능을 확인한다.