본문 바로가기

Enginius/Machine Learning

Gaussian Process Approximations (PITC, D2FAS)

 Gaussian process 는 non-parametric Bayesian regression의 대표적인 알고리즘으로 주어진 데이터를 가지고 새로운 위치에서 값을 regression할 때, 사용될 수 있는 알고리즘이다. 

 수학적인 얘기는 집어 치우고, 결국 이 알고리즘이 할 수 있는 것은 sparse한 (띄엄띄엄있는 의 pedantic 한 단어) 기상청에서 온도를 쟀을 때, 서울 전체에 대한 온도 지도를 만들 수 있다. 이 때 기상청의 위치들의 모음을 X라 하고, 해당하는 온도를 Y라 할 때, 새로운 위치 Z에서 온도를 구할 수 있는 알고리즘이 Gaussian process regression이다. 

 수학적으로 조금 들어가보면, Y = f(X)의 관계를 만족시키는 f를 구하는 것인데, f(Z) ~ N(muZ, sig2Z)에서 muZ와 sig2Z를 구하는데, 이를 위해서 (X, Z)에 대한 joint Gaussian distribution을 정의한다. 이렇게 하면, Gauss느님에 정의에 따라 f(Z)|Y에 대한 conditional Gaussian distribution을 자동으로 구할 수 있다. 

 '$f(Z)\sim N(\mu_Z, var_Z)$'

이고, 

 '$mu_Z = k(Z, X)(k(X, X)+\sigma^2_wI)^{-1}Y$'

 '$var_Z = z(Z, Z)+k(Z, X)(k(X, X)+\sigma^2_wI)^{-1}k(X, Z)$'

로 정의된다. 


여기서 문제가 '$(k(X, X)+\sigma^2_wI)^{-1}$'를 구하기 위해서 들어가는 computational cost가 '$O(N^3)$'이라는 점이다. '$N$'은 데이터의 수 (기상청의 수) 이다. 


 이러한 문제를 해결하기 위해서 여러 Approximation 기법들이 고안되었다. 이들 대부분은 SoD (Subset of Data) 기법으로 불릴 수 있는데, support set '$U\in R^m$'를 사용하는 알고리즘이다. ('$m < N$') 

 이번 포스팅에서 설명할 내용은 Partially Independent Training Conditional (PITC) 과 이 알고리즘을 분산화 시킨 Decentralized Data Fusion and Active Sensing (D2FAS) 이다. 

 자세한 내용은 논문을 참조 

"Decentralized Data Fusion and Active Sensing with Mobile Sensors for Modeling and Predicting Spatiotemporal Traffic Phenomena"

Abstract

 The problem of modeling and predicting spatiotemporal traffic phenomena over an urban road network is important to many traffic applications such as detecting and forecasting congestion hotspots. This paper presents a decentralized data fusion and active sensing (D2FAS) algorithm for mobile sensors to actively explore the road network to gather and assimilate the most informative data for predicting the traffic phenomenon. We analyze the time and communication complexity of D2FAS and demonstrate that it can scale well with a large number of observations and sensors. We provide a theoretical guarantee on its predictive performance to be equivalent to that of a sophisticated centralized sparse approximation for the Gaussian process (GP) model: The computation of such a sparse approximate GP model can thus be parallelized and distributed among the mobile sensors (in a Google-like MapReduce paradigm), thereby achieving efficient and scalable prediction. We also theoretically guarantee its active sensing performance that improves under various practical environmental conditions. Empirical evaluation on real-world urban road network data shows that our D2FAS algorithm is significantly more time-efficient and scalable than state-of-the-art centralized algorithms while achieving comparable predictive performance.

 

알고리즘 설명은 귀찮고, 그냥 논문에 있는 중요한 Definition과 Theorem을 올리자. 




일반적인 GPR, PITC, 그리고 D2FAS를 적용한 결과가 다음과 같다. 

결과

[GPR with 1000 input data 500 groups 10 support set] 

GP takes 2.361sec / GP-PITC takes 0.106sec (22.221 times faster) 

GP takes 2.361sec / GP-D2FAS takes 0.089sec (26.592 times faster) 

GP error: 0.009 / SGP error: 0.231 


코드

1. 메인 코드 (demo_GPR_PITC_D2FAS.m)


2. PITC 코드 (gpr_pitc.m)


3. D2FAS 코드 (gpr_d2fas.m)


4. GPR 코드 (gpr.m)


5. 커널 관련 코드

a. se_kernel.m


b. se_kernel_logderivative.m


6. 추가 유틸 코드

a. split_vec.m


b. varycolor.m


'Enginius > Machine Learning' 카테고리의 다른 글

Gaussian Process Mixture  (0) 2014.01.13
Computer science: The learning machines  (0) 2014.01.09
What is the future of Big data  (0) 2013.07.22
Principal component analysis (PCA) on data  (1) 2013.07.11
Dirichlet Process (DP)  (2) 2013.07.05