Subspace Approximation for Approximate Nearest Neighbor Search in NLP
Jing Wang






Subspace Approximation for Approximate Nearest Neighbor Search in NLP
    Jing Wang jw998@rutgers.edu
    December 30, 2023
=====================================================================




	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.





§ INTRODUCTION

Artificial intelligence (AI) is a thriving field with active research topics and practical products, such as Amazon's Echo, Goolge's home smart speakers and Apple's Siri. The world becomes enthusiastic to communicate with these intelligent products. Take Amazon Echo for example,  you can ask Echo the calories of every food in your plate if you are on diet. Whenever you need to check your calendar, just ask “Alexa, what's on my calendar today?” It boosts the development of natural language processing which refers to the AI technology that makes the communication between AI products and humans with human language possible. It is shown that the communication between human and AI products are mainly in the format of question answering (QA). QA is a complex and general natural language task. Most of natural language processing tasks can be treated as question answering problem, such as word analogy task <cit.>, machine translation <cit.>, named entity recognition (NER) <cit.>, part-of-speech tagging (POS) <cit.>, sentiment analysis <cit.>.

There are many works designed for the question answering task, such as deep learning models <cit.>
, information extraction systems <cit.>. In this work, we propose to solve the question answering task by the approximate nearest neighbor search method.  Formally, given the question as a query q∈ R^d, the training data set P={p_1,⋯,p_n}∈ R^d× n, the nearest neighbor search aims to retrieve the nearest neighbor of the query q, denoted as p^∗ from P as the answer. We assume that p^∗ is within distance 1 from the query q, and all other points are at distance at least 1+ ϵ (ϵ∈ (0,1)) from the query q. The nearest neighbor p^∗ is called a (1+ϵ)-approximate nearest neighbor to q which can be expressed as:

    ∃ p^*∈ P, 
    q-p^*≤ 1  and 
       ∀  p∈ P∖{p^*}, q-p≥ 1+

However, in real-world natural language processing applications, there are usually noise in the data, such as spelling errors, non-standard words in newsgroups, pause filling words in speech. Hence, we assume the data set P with arbitrary noise t to create P̃ ={p̃_1,⋯,p̃_n}, where p̃_i = p_i+t_i. The query q is perturbed similarly to get q̃=q+t_q. We assume that the noise is bounded, that is t_i≤ϵ/25 and t_q≤ϵ/25.  

There are many approaches proposed to solve the approximate nearest neighbor search problem. Existing methods can be classified as two groups: the data-independent methods and the data-dependent methods. The data-independent approaches are mainly based on random projection to get data partitions, such as Local Sensitive Search, Minwise Hashing. Recently,  the data-dependent methods received interest for its outstanding performance. They utilize spectral decomposition to map the data to different subspace, such as Spectral hashing. However, theoretical guarantee about the performance is not provided. Existing methods can not handle natural language processing problems well for the following reasons. First the data set in natural language processing is usually in large scale which yields a huge search space. Moreover, the singular value decomposition which is widely used to obtain the low-rank subspace is too expensive here.  Second, the data is with noise. Existing data-aware projection is not robust to noisy data which cannot lead to correct partitions. 

To solve the above mentioned problem, we propose a novel iterated spectral based approximate nearest neighbor search framework for general question answering tasks (Random Subspace based Spectral Hashing (RSSH)). Our framework consists of the following major steps:

	
  * As the data is with noise, we first project the data to the clean low-rank subspace. We obtain a low-rank approximation within (1+δ) of optimal for spectral norm error by the randomized block Krylov methods which enjoys the time complexity O(nnz(X)) <cit.>. 
	
  * To eliminate the search space, we partition data to different clusters. With the low-rank subspace approximation, data points with are clustered corresponding to their distance to the subspace. 
	
  * Given the query, we first locate its nearest subspace and then search the nearest neighbor in the data partition set corresponding to the nearest subspace. 

With our framework, we provide theoretical guarantees in the following ways:

	
  * With the low-rank approximation, we prove that the noise in the projected subspace is small. 
	
  * With the data partition strategy, all data will fall to certain partition within O(log n) iterations.
	
  * We prove that our method can return the nearest neighbor of the query in low-rank subspace which is the nearest neighbor in the clean space. 


To the best of our knowledge, it is the first attempt of spectral nearest neighbor search for question answering problem with theory justification. Generally, our framework can solve word similarity task, text classification problems (sentiment analysis), word analogy task and named entity recognition problem.

The theoretical analysis in this work is mainly inspired by the work in <cit.>. The difference is that the subspace of data sets is computed directly in <cit.>, in our work, we approximate the subspace by a randomized variant of the Block Lanczos method <cit.>. In this way, our method enjoys higher time efficiency and returns a (1+ϵ/5)-approximate nearest neighbor.















































§ NOTATION

In this work, we let s_j(M) denote the j-th largest singular value
of a real matrix M.
M is used to denote the Frobenius norm of M.
All vector norms, i.e. v for v∈^d, refer to the ℓ_2-norm.

The spectral norm of a matrix X∈^n× d is defined
as 

    X = sup_y∈^d: y=1X y,

where all vector norms · refer throughout to the ℓ_2-norm. It is clear that M=s_1(M) equals the spectral norm of M.
The Frobenius norm of X is defined as X=(∑_ij
X_ij^2)^1/2, and let X^ denote the transpose of X.

A singular vector of X is a unit vector v ∈^d 
associated with a singular value s∈ and a unit vector 
u ∈^n such that X v = s u and u^ X = s v^. 
(We may also refer to v and u as a pair of right-singular and left-singular vectors associated with s.)

Let p_Ũ denote the projection of a point
p onto Ũ. Then the distance between a point x and
a set (possibly a subspace) S is defined as d(x,S) = inf_y∈ Sx-y.



§ PROBLEM


Given an n-point dataset P and a query point q,
both lying in a k-dimensional space U ⊂ ^d,
we aim to find its nearest neighbor q^* which satisfying that:

    ∃ p^*∈ P  such that q-p^*≤ 1  and ∀ p∈ P∖{p^*}, q-p≥ 1+

Assume that the data points are corrupted by arbitrary small noise t_i which is bounded t_i≤/16 for all i (∈(0,1)). The observed set P̃ consists of points p̃_i=p_i+t_i for all p_i∈ P
and the noisy query points q̃ = q+t_q with t_q≤/16.



§ ALGORITHM




 §.§ Subspace Approximation

We utilize a randomized variant of the Block Lanczos method proposed in <cit.> to approximate the low-rank subspace of the data set. 

  <cit.>
	For any A∈ R^m× d, the k-dimensional low-rank subspace obtained by singular value decomposition is denoted as A_k. Algorithm <ref> returns Z_k which forms the low-rank approximation _k = Z_k Z_k^⊤ A, then the following bounds hold with probability at least 9/10:
	
    A - _k_2 ≤ (1+η) A-A_k_2  ≤ (1+η) σ_k

	
    ∀ i ∈ [k],  |z_i^⊤ AA^⊤ z_i - u_i^⊤ AA^⊤ u_i|    =  |_i^2-σ_i^2 | 
       ≤ησ_k+1^2  .

	where _i is the i-th singular value of A.
	The runtime of the algorithm is O(md k log(m)/√(η)+ k^2(m+d)/η).

Algorithm <ref> returns the matrix Z_i which is  the approximation to the left singular vectors of data matrix A. We use Z^TA to approximate the  right singular vectors of data matrix A. 




 §.§ Data Partition


 <cit.>
	The nearest neighbor of q̃ in P̃ is p̃^*.



















	Algorithm <ref> terminates within O(log n) iterations.

 	Let U be the k-dimensional subspace of P with projection matrix V, let Ũ be the k-dimensional
	subspace of P̃ with projection matrix , let S be the low-rank approximation returned by Algorithm <ref> with projection matrix Z_k.
	The distance between data points and subspace is computed as:
	
    ∑_p̃∈P̃ d(,)^2    = ∑_p̃∈P̃inf_y∈||-y||_2^2 
       = inf||-_k_k^T||_2^2 .

	
	
    ∑_p̃∈P̃ d(,S)^2    = ∑inf_y∈ S||-y||_2^2 
       = inf||-Z_kZ_k^T||_2^2.

	
	According to Theorem <ref>, we can have:
	
    ||-Z_kZ_k^⊤||_2 ≤ (1+η)||-U_kU_k^⊤||_2
,
	We can get 
	
    ∑_p̃∈P̃ d(,S) ≤ (1+η)^2 ∑_p̃∈P̃ d(,).

	
	Since Ũ minimizes 
	the sum of squared distances from all p̃∈P̃ to Ũ,
	
    ∑_p̃∈P̃ d(p̃,Ũ)^2
    	≤∑_p̃∈P̃ d(p̃,U)^2
    	≤∑_p̃∈P̃p̃-p^2
    	≤α^2 n.

	Then, we can get:
	
    ∑_p̃∈P̃ d(p̃,S)^2 ≤ (1+η)^2α^2n.

	Hence, there are at most half of the points in P̃ with distance to
	S  greater than √(2)(1+η)α. The set
	M captures at least a half fraction of points. The
	algorithm then proceeds on the remaining set. 
	After O(log n) iterations all points of P̃ must be
	captured.


 
	The approximated subspace S that captures p̃^* returns this as the (1+/5)-approximate nearest neighbor of q̃ (in Ũ).


	Fix p≠ p^* that is captured by the same S,
	and use the triangle inequality to write 
	
    p - p̃_S   ≤p-p̃ + p̃ - p̃_S
       ≤α + √(2)(1+η) α≤ 4α.

	
	Similarly for p^*,
	p^* - p̃^*_S≤ 4α,
	and by our assumption
	q - q̃≤α.
	By the triangle inequality, we get 
	
    q̃ - p̃^*_S   ≤-p +p-^*_S
       ≤-q+q-p+p-^*_S
       ≤q-p+5α,

	
    q̃ - p̃^*_S   ≥-p-^*_S-p
       ≥q-p -q--^*_S-p
       ≥q-p-5α,

	Similarly, we bound  q̃ - p̃^*_S
	
    q̃ - p̃_S/q̃ - p̃^*_S   =  q-p ± 5α/ q-p^* ± 5α 
    	=     q-p ±15 / q-p^* ±15 
       ≥q-p - 15 /q-p^* + 15 ≥ q-p^*  + 45 / q-p^*  + 15 
    	> 1+15 .

	
	
	By using Pythagoras' Theorem 
	(recall both p̃_S,p̃^*_S∈ S),
	
    q̃_S - p̃_S/q̃_S - p̃^*_S
    	= q̃ - p̃_S - q̃ - q̃_S/q̃ - p̃^*_S - q̃ - q̃_S 
    	> (1+15 )^2.

	
	
	
	Hence, p̃^* is reported by 
	the k-dimensional subspace it is assigned to.




§ EXPERIMENT


In this experiment, we compare our algorithm with existing hashing algorithms. 


 §.§ Baseline algorithms


Our comparative algorithms include state-of-the-art learning to hashing algorithm such as

	
  * Anchor Graph Hashing (AGH) <cit.>
	
  * Circulant Binary Embedding (CBE) <cit.> 
	
  * Multidimensional Spectral Hashing (MDSH) <cit.>
	
  * Iterative quantization (ITQ) <cit.>
	
  * Spectral Hashing <cit.> 
	
  * Sparse Projection (SP) <cit.>

We refer our algorithm as Random Subspace based Spectral Hashing (RSSH). 


 §.§ Datasets.


Our experiment datasets include MNIST [http://yann.lecun.com/exdb/mnist/], CIFAR-10[https://www.cs.toronto.edu/ kriz/cifar.html/], COIL-20 [http://www.cs.columbia.edu/CAVE/software/softlib/coil-20.php] and the 2007 PASCAL VOC challenge dataset. 

MNIST. It is a well-known handwritten digits dataset from “0” to “9”. The dataset consists of 70,000 samples in feature space of dimension 784. We split the samples to a training and a query set which containing 69,000 and 1,000 samples respectively. 

CIFAR-10. There are 60,000 image in 10 classes, such as “horse” and “truck”. We use the default 59,000 training set and 1,000 testing as query set. The image is with 512 GIST feature. 

COIL-20. It is from the Columbia University Image Library which contains 20 objects. Each image is represented by a feature space 1024 dimension. For each object, we choose 60% images for training and the others are querying.


VOC2007. The VOC2007 dataset consists of three subsets as training, validation and testing. We use the  first two subsets as training containing 5,011 samples and the other as query containing 4,096 samples. We set each image to the size of [80, 100] and extract the HOG feature with cell size 10 as their feature space [http://www.vlfeat.org/]. All the images in VOC2007 are defined into 20 subjects, such as “aeroplane” and “dining tale”. For the classification task on each subject, there are 200 to 500 positive samples and the following 4,000 are negative. Thus, the label distribution of the query set is unbalanced. A brief description of the datasets are presented in Table <ref>.




 §.§ Evaluation Metrics

All the experiment datasets are fully annotated. We report the classification result based on the groundtruth label information. That is, the label of the query is assigned by its nearest neighbor. For the first three datasets in Table <ref>, we report the classification accuracy. For the VOC2007 dataset, we report the precision as the label distribution is highly unbalanced. The criteria are defined in terms of true positive (TP), true negative (TN), false positive (FP) and false negative (FN) as,

    Precision   = TP/TP+FP,
    Accuracy   = TP+TN/TP+TN+FP+FN.


For the retrieval task, we report the recall with top [1, 10, 25] retrieved samples. The true neighbors are defined by the Euclidean distance. 

We report the aforementioned evaluation criteria with varying hash bits (r) in the range of [2, 128].




 §.§ Classification Results

The classification accuracy on CIFAR-10, MNIST and COIL-20 are reported in Figure <ref>a, <ref>b and <ref>c. We can see that our algorithm achieves the best accuracy in terms of the number of hash bits in the three datasets. For example, on CIFAR-10 with r=48, the accuracy of our algorithm RSSN reaches 53.20% while the comparative algorithms are all less than 40.00%. The increase of hash bit promotes the accuracy of all algorithms, our algorithm remains the leading place. For example, on MNIST with r=96, ITH and SH reach the accuracy of 93.00%, but our algorithm still enjoys 4.00% advantage with 97.30%.  Moreover, our algorithm obtains significant good performance even with limited information, that is, the r is small. For instance, in terms of r=8, RSSN reaches the accuracy of 87.70%, much better than the comparative algorithms. 

For the classification results on VOC2007, we report the accuracy on 12 of 20 classes as representation in Figure <ref>. We can see that it is a tough task for all the methods, but our algorithm still obtains satisfying performance. For example, on the classification task of “horse”, our algorithm obtains around 10% advantage over the all the comparative algorithms. The average precision on all the 20 classes are presented on Figure <ref>. We can see that our algorithm obtains the overall best result.



 §.§ Retrieval Results

The retrieval results on MNIST, CIFAR-10 and COIL-20 are presented in Figure <ref>d to Figure <ref>l. Our algorithm obtains the best recall with varying number of retrieved samples. For example, on CIFAR-10 with Top 10 retrieval and r=96, our algorithm reaches the recall over 70%, while the others are less than 20%. On MNIST with Top 25 retrieved samples and r=128, the recall of RSSN reaches 90%, while the comparatives algorithms are around 40%. 








apalike
 

