Subspace Approximation for Approximate Nearest Neighbor Search in NLP
This addresses efficiency and accuracy issues in NLP tasks like question-answering for researchers and practitioners, but it is incremental as it builds on existing approximate nearest neighbor methods with specific improvements.
The paper tackles the problem of approximate nearest neighbor search in NLP, which faces challenges from data noise and large-scale datasets, by proposing a framework that projects data to a subspace to eliminate noise and partitions the dataset to reduce search space from O(n) to O(log n), demonstrating outstanding performance on real-world NLP tasks.
Most natural language processing tasks can be formulated as the approximated nearest neighbor search problem, such as word analogy, document similarity, machine translation. Take the question-answering task as an example, given a question as the query, the goal is to search its nearest neighbor in the training dataset as the answer. However, existing methods for approximate nearest neighbor search problem may not perform well owing to the following practical challenges: 1) there are noise in the data; 2) the large scale dataset yields a huge retrieval space and high search time complexity. In order to solve these problems, we propose a novel approximate nearest neighbor search framework which i) projects the data to a subspace based spectral analysis which eliminates the influence of noise; ii) partitions the training dataset to different groups in order to reduce the search space. Specifically, the retrieval space is reduced from $O(n)$ to $O(\log n)$ (where $n$ is the number of data points in the training dataset). We prove that the retrieved nearest neighbor in the projected subspace is the same as the one in the original feature space. We demonstrate the outstanding performance of our framework on real-world natural language processing tasks.