Subspace Approximation for Approximate Nearest Neighbor Search in NLP
  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.
