Effcient Bayesian Nonparametric Inference: Tree-Based Methods and Power-Law Models

Abstract

비모수 베이지안 모델 (Bayesian nonparametric model, BNP)은 기계학습의 다양한 분야에 널리 활용되고 있는 확률 모델이며, 그 중에서도 디리클레 과정 (Dirichlet process, DP), 베타 과정 (Beta process, BP)를 비롯하여 다양한 종류의 비모수 베이지안 사전 분포들을 포함하는 정규화된 랜덤 측도 (Normalized random measure, NRM)가 복잡한 실세계 데이터의 다양한 성질을 모델링하는데 사용되어왔다. 정규화된 랜덤 측도를 사전 분포로 가정하는 통계적 기계학습 모델은 사전 분포의 유연성 때문에 사후 분포 추론이 어렵다는 단점이 있는데, 기존의 연구에서는 수렴성이 보장되지만 대규모 데이터에서 비효율적인 Markov-Chain Monte Carlo (MCMC)를 주로 사용해왔고, 사후 분포 추론을 효율적으로 하기 위한 연구가 많이 수행되지 않았다. 본 학위논문에서는 정규화된 랜덤 측도 모델을 이용하는 비모수 베이지안 모델의 사후 분포 추론을 효율적으로 수행하기 위한 두 가지 방법론을 제시한다. 첫 번째 방법론은 트리 기반의 사후 분포 추론 알고리즘으로, 데이터의 군집 구조를 나타내는 이진 트리를 만들어 데이터를 군집화하고 그 결과물로 사후 분포를 근사할 수 있는 방법이다. 해당 트리 기반 근사 기법은 MCMC 방법보다 효율적이고, 대규모 데이터를 이용한 학습이나 온라인 학습에 적합하다는 장점이 있다. 두 번째 방법론은 변분 추론 방법이다. 기존에도 변분 추론을 이용하여 비모수 베이지안 모델의 사후 분포 추론을 근사하는 방법론이 있었지만, 디리클레 과정과 베타 과정과 같이 가장 간단한 사전 분포에 대해서만 연구가 되어 있었다. 본 학위논문에서는 최초로 멱법칙 (power-law)을 따르는 데이터를 생성할 수 있는 좀 더 일반화된 사전 분포를 유한 차원으로 근사하여 변분 추론을 이용한 효과적인 사후분포 추론이 가능한 방법론을 제시한다. 마지막으로, 그래프의 연결 수 (degree)가 멱법칙을 따르는 멱법칙 그래프 (power-law graph)를 생성할 수 있는 랜덤 그래프 모델을 제안하고, 변분 추론을 이용하여 해당 모델의 사후 분포를 효율적으로 추론할 수 있는 방법을 제시한다

Bayesian nonparametric models (BNP) have been applied to wide variety of applications in machine learning. Starting from the Dirichlet Process (DP) and Beta Process (BP), a broad class of prior processes called the Normalized Random Measure (NRM) has been studied to model complex real world data. However, despite the development of flexible priors, the posterior inference schemes of those models have not been studied well. Most of the NRM based model relies on MCMC that scales poor for large data. In this thesis, to overcome this limitations, we propose efficient posterior inference algorithms for general BNP models. We propose several methods that are categorized into two paradigms; tree-based inference and variational inferences. Tree-based inference builds binary trees that represents cluster structures of datasets to approximate marginal likelihoods of models, and we propose efficient algorithms that can be applied to online inference. We also propose novel finite-dimensional approximation scheme that enables the development of variational Bayesian inference algorithms for some BNP prior processes used to model power-law data. Finally, we propose a novel random graph model that generates random simple graphs with power-law degree distributions, and also propose an efficient variational inference algorithm for the posterior inference.