Large scale nearest neighbor search is of great importance to many applications such as Information Retrieval and Duplicate detection of document or image. The difficulty of this problem not only comes from the requirement of low computational complexity, but also of unsupervised learning. Recently, many research results show that similarity preserving hashing is a promising approach to this problem. However, most existing hash methods are designed only for similarity preserving property which cannot directly guarantee optimal performance of Receiver Operating Characteristic (ROC) curve. In this paper, we analyze the condition on hash function to achieve optimal False Alarm Rate (FAR) and Detection rate ($P_D$) and propose a novel hashing method based on the condition. The experimental result shows that proposed method outperforms other methods for various applications including duplicate image detection, large-scale image search, and object recognition.
대용량 최단 이웃점 탐색 문제(Large-scale nearest-neighbor search problem)는 정보(문서, 영상 등)검색, 복제 문서 검출 등 다양한 응용분야에서 활용된다. 특히, 인터넷의 급격한 발전에 의해 데이터의 양이 기하급수적으로 증가함에 따라 대용량 자료에 대한 빠른 최단 이웃점 탐색 문제의 중요성이 높아지고 있다. 하지만, 이 문제는 대용량 자료를 다루기 때문에, 학습(training) 과정의 복잡도나 최단 이웃점을 찾기 위한 시간복잡도가 매우 작아야하며, 지도 학습(supervised learning)이 아닌 자율 학습(unsupervised learning)에 의해 이루어져야한다는 어려움이 있다. 최근의 여러 연구들에 의하면 해싱(hashing)기법을 이용하여 이진코드를 생성하는 방법이 대용량 최단 이웃점 탐색 문제를 푸는데 효과적이라고 알려져 있다. 그 이유는 첫째, 생성된 이진코드는 높은 수준으로 압축되어있기 때문에 main memory에 직접 저장해서 연산하는 것이 가능하기 때문이며 둘째, 두 이진코드 사이의 거리는 xor연산을 통해 효율적으로 계산이 될 수 있기 때문이다. 해싱 기법은 실수 형태의 입력 자료들을 이진코드에 대응시키는 해시 함수(hash function)을 만들고, 이에 해당하는 해시 배열(hash table)을 생성하여 빠른 속도로 최단 이웃점을 탐색할 수 있는 방법이다. 일반적으로 잘 정의된 해시 함수와 해시 배열에 대해 최단 이웃점을 탐색하는 것은 시간복잡도 O(1)이라고 알려져 있으며, 세부 기법 분류에 따라 해시 코드를 생성하는 시간복잡도 또한 O(1)으로 만들 수 있다. 해싱 기법 중에는 사영을 이용한 해싱방법과 무리화(grouping)을 이용한 해싱 기법이 있는데, 이 논문에서는 최단 이웃점을 찾기 위한 시간복잡도가 O(1)인 사영을 이용한 해싱 기법만을 고려한다. 사영을 이용한 기존의 여러 해싱 기법 중에는 특히 원본의 거리를 보존하는 성질(similarity preserving property)을 가지는 해싱 기법들이 부각되고 있는데, 제한된 시간 복잡도에서 이 성질을 최적화 하는 것은 불가능하며, 최적화하더라도 성능이 최적화되지는 않는다는 문제점이 있다.
대용량 최단 이웃점 탐색 문제에 대한 성능을 평가하는 방법에는 이 문제를 최단 이웃점 탐지 문제로 생각하여, 탐지 또는 필터의 성능을 평가하는 수신자 조작 특성 곡선(ROC curve)을 사용하거나, 인식문제로 생각하여 정확도-재현율 곡선(Precision and recall curve)을 사용한다. 이 논문에서는 탐지의 관점에서 수신자 조작 특성 곡선을 최적화하기 위한 새로운 기법을 제시한다. 먼저, 탐지 정확률(detection rate)과 헛경보 비율(false alarm rate)를 같은 라벨을 갖는 무리의 중심과 각 무리의 원소들의 분포에 대해 수학적으로 정의한 후에 모델링을 통해 각 값을 최적화하기 위한 조건을 살펴본다. 이 조건을 바탕으로 자율학습에 기반한 최신 해싱 기법(Spectral Hashing(SH), Iterative Quantization(ITQ), Principal Component Analysis-hasing(PCA-hashing), Locality Sensitive Hashing(LSH))들의 성능을 탐지 정확률과 검출 한계값(threshold)의 관계, 헛경보 비율과 검출 한계값의 관계의 관점에서 수학적으로 비교 분석하고, 실용적으로 사용되는 헛경보 비율의 영역에서 최신 해싱 기법들 중에는 PCA-hashing기법이 최적임을 밝힌다. 마지막으로, 위 모든 분석들을 바탕으로 헛경보 비율을 최적화하면서 탐지 정확률이 높은 새로운 기법인 Uncorrelated Component Analysis-hashing을 제안하며, 이 기법으로 생성되는 해시코드는 uncorrelated성질을 가져서 최적의 헛경보율을 보이며, PCA-hashing보다 높은 탐지율을 보이게 되는 것을 증명한다. 또한, Independent Component Analysis-hashing(ICA-hashing)기법도 이러한 성질을 가지지만, 추정값을 사용함에 따른 한계를 가짐을 밝힌다. 다양한 해시코드 비트수에 대해 실험한 결과에 따르면, 제안된 해싱 기법은 고정된 검출 한계값에 대해 기존의 방법들 보다 낮은 헛경보 비율을 가지며, 최적의 헛경보 비율을 가지기 위한 조건을 만족하는 방법들 중에 가장 높은 정확률을 가지고, 관심 헛경보율 영역에서의 ROC 곡선에서 최적의 성능을 보인다. 또한, 제안된 기법은 기존의 방법들과 비교해 비교적 빠른 시간 안에 계산이 가능한 것으로 나타났다.
