Probabilistic Local Reconstruction for k-Nearest Neighbor Learning

Abstract

Data-dependent 커널(kernel)의 일종인 Locally Linear Embedding (LLE) 커널은 학습 데이터 셋(training set) 내 이웃하는 데이터들을 기준으로 두 개의 데이터 포인트(data point) 간 유사도를 평가하므로, 국지적 위상(local topology)를 반영한다. 그리고 커널 k-인접 이웃 예측 방법(kernelized k-nearest neighbor, k-NN prediction)에서의 사용은 통상적으로 사용하는 커널들에 비해 k 값에 강건하고 – 혹은, k-불변(k-invariant)하고 – 또한 더 정확한 예측 성능을 보인다. 하지만, 국지적 선형 재구축(Locally Linear Reconstruction, LLR)에 기반하는 LLE 커널은 임의의 쿼리 포인트(query point)에 대한 k-인접 이웃 기반의 국지적 재구축의 신뢰 구간(confidence interval)을 제시하지 못한다. 게다가, 쿼리 주변의 국지적 위상(underlying local topology)을 선형 구조(linear structure)로 표현하기 때문에, k 값이 너무 작거나 크게 설정될 경우 k-불변성을 보장하지 못하는 경우가 있다. 따라서 확률적 국지 재구축(Probabilistic Local Reconstruction, PLR)을 제안하고, 커널 k-인접 이웃 회귀(kernelized k-NN regression)에 적용한다. 이러한 확률적 관점의 국지적 선형 재구축은 - prior 가정에 의해 - k 이웃의 평균점에 위치한 재구축점(reconstructed point)을 쿼리 포인트에 가깝게 조정하는 학습 과정으로 해석 가능하다. 이 때, 학습 정도는 PLR의 노이즈(noise) 가정에 의해 조정되는데, 높은 노이즈 가정은 k 값이 작게 설정되어 있기 때문에 국지적 재구축 과정에 유익한(informative) 이웃이 없는 문제(small k problem)에 대한 해결 방안을 제시한다. 그리고 확률적 국지 재구축의 커널 구현(kernelized implementation)은 k 값이 크게 설정되어, 너무 과다하게 – 혹은, 광범위하게 – 이웃들을 설정한 경우에도 비선형(non-linear)의, 혹은 국지적으로 편향된(locally biased) 위상 구조를 도출한다. 15개의 벤치마크(benchmark) 회귀 문제들에 대한 사전 실험 결과, 제안하는, LLR에 대한 베이지안 커널 모형(Bayesian kernel model)이 예측 정확도와 k-불변성을 향상시킴을 확인하였다. 나아가, 확률적 국지 재구축에 기반한 k-인접 이웃 회귀의 예측 신뢰도(prediction reliance)를 제안한다. 확률적 국지 재구축의 k-인접 이웃 예측 신뢰도(PLR k-nearest neighbor prediction reliance)는 두 종류의 불확실성 요소, 즉, 재구축 불확실성(reconstruction uncertainty)과 타겟 불확실성(target uncertainty)를 동시에 고려한다. 그리고 가상 계측(Virtual Metrology, VM)은 예측 신뢰도의 제공이 상당히 중요한 회귀 문제인데, 가상 계측에 적용한 결과, 확률적 국지 재구축의 k-인접 이웃 예측에서 제공하는 불확실성 정보가, 확신이 없는 부정확한 예측을 피함으로써 적절한 의사 결정에 도움이 될 수 있음을 확인하였다.

Locally Linear Embedding (LLE) kernel, one of data-dependent kernels, assesses similarity of two data points in terms of neighboring points in the training set, thus, captures the local topology. Its use in the kernelized k-nearest neighbor (k-NN) prediction was shown to be more robust to k, i.e., "k-invariant" and accurate predictions than other conventional data-independent kernels. The LLE kernel, often named Locally Linear Reconstruction (LLR), however, does not provide a confidence interval for the k neighbors-based reconstruction of a query point, which is required in many real application domains. Moreover, fitting the fixed linear structure to the underlying local topology around a query point may not guarantee the k-invariant property with small or large k settings. Therefore, Probabilistic Local Reconstruction (PLR) as a probabilistic extension of LLR is proposed and applied to k-NN regression. This probabilistic extension of LLR is explained as the learning process of adjusting the reconstructed point at the average point of k neighbors - expected by the prior assumption - to be close to the corresponding query point. The learning degree is controlled by the additive noise assumption of PLR. High additive noise setting makes PLR avoid the small k problem which is due to no informative neighbors in the locally linear reconstruction. Moreover, the kernelized implementation of PLR is provided to capture the non-linear or locally biased topology embedded in too redundant neighbors with a large k setting. Preliminary experimental result on some benchmark regression problems demonstrated that the proposed Bayesian kernel treatment of LLR improves accuracy and k-invariance. Further, based on the PLR kernel, more reasonable prediction reliance estimation for k-NN regression is proposed. The PLR k-NN prediction reliance takes account of both two uncertainties - reconstruction uncertainty and target uncertainty. From the experiment on a real-world Virtual Metrology (VM) problem where it is critical to provide the reliance level of predictions, it was found that the uncertainty information on the k-NN prediction outcomes provided by the PLR kernel supports more appropriate decision making by rejecting the predictions of data points which would otherwise be unreliably and incorrectly predicted.