Binary Embedding: Theory and Applications

Abstract

본 논문은 이진 사상(binary embedding)과 일반적인 해싱 알고리즘에 대한 새로운 이론/경험적 분석을 소개한다. 이진 사상은 d차원 유클리디안 공간을 k차원 해밍 공간으로 변환하는 방법으로, 유클리디안 공간에서 정의된 데이터 유사도를 해밍 공간에서 보존하는 것이 목적이다. 본 논문의 기술적 기여는 다음과 같다.

1. (희소) 순환 이진 사상에 대한 이론적 분석. 본 논문에서는 (희소) 순환 이진 사상의 작동 원리를 분석하기 위한 (비)점근적 분석 방법을 제시한다. 첫째로, 순환 이진 사상이 일반적인 이진 사상과 유사한 성능을 제공한다는 점을 설명하기 위한 이론적 분석 방법론을 소개한다. 둘째로, 회소 순환 랜덤 행렬 기반의 희소 순환 이진 사상 알고리즘을 제안하고 고차원에서 일반적인 이진 사상 알고리즘과 유사함을 입증하기 위한 점근적 분석 방법을 제시한다.

2. 머서 커널에 대한 데이터 비종속 (쌍선형) 이진 사상. 본 논문에서는 첨가적 동종 커널(additive homogeneous kernel)과 이동 불변 커널(shift-invariant kernel)을 보존할 수 있는 데이터 비종속 (쌍선형) 이진 사상 알고리즘 및 이에 대한 이론적 분석을 소개한다. 첫째로, 첨가적 동종 커널을 위한 데이터 비종속 특징 매핑 알고리즘을 기반으로 개발한 데이터 비종속 이진 사상 알고리즘을 제안한다. 둘째로, 이동 불변 커널로 정의된 데이터 유사도를 보존하기 위한 쌍선형 이진 사상 알고리즘을 제안하고 가우시안 커널인 경우에 해당 알고리즘의 성질에 대한 이론적 분석을 제시한다.

3. 멀티모달 데이터를 위한 데이터 종속 이진 사상. 본 논문에서는 멀티모달 데이터에서 정의된 유사도를 보존할 수 있는 바이너리 코드를 생성하는 데이터 기반 이진 사상 알고리즘을 제안한다. 구체적으로, 이진 코드를 순차적으로 학습할 수 있는 알고리즘과 기존 앵커 그래프(anchor graph) 해싱 알고리즘을 멀티모달 데이터에 맞게 확장한 방법을 제안한다.

4. 대규모 이미지 데이터셋에 대한 유사 이미지(near-duplicate) 군집 알고리즘. 본 논문에서는 min-hashing 기법을 확장하여 10억장 이상의 대규모 이미지 데이터셋에서 유사 이미지군을 빠르게 찾을 수 있는 방법을 제안한다. 기존 방법들로 찾은 유사 이미지 군집은 10억장 이상의 데이터 규모에서는 거짓 양성(false positive)이 많은 단점이 존재하기 때문에 이를 극복하는 다양한 해쉬 함수 구성을 제안한다.

Binary embedding refers to methods for embedding points in d-dimensional Euclidean space into vertices in the Hamming cube of dimension k, such that the normalized Hamming distance preserves the similarity between vectors in the original space. In this thesis, we introduce our major contributions to data-(in)dependent binary embedding with various metrics including angular distance, shift-invariant kernels, and additive homogeneous kernels; First, we propose an asymptotic and non-asymptotic analysis to theoretically investigate the performance of binary embedding with structured matrices, when angular similarity is interested. Second, we present (bilinear) binary embedding with shift-invariant kernels and additive homogeneous kernels. Third, we introduce data-dependent binary embedding to seek compact integrated binary codes that preserve similarities averaged over multiple representations of objects. Finally, we show some applications including approximate nearest neighbor search and near-duplicate image discovery on one billion web images.