Sparse Ternary Codes for similarity search have higher coding gain than dense binary codes
Sohrab Ferdowsi Slava Voloshynovskiy Dimche Kostadinov Taras Holotyak



Pulse length of ultracold electron bunches extracted from a laser cooled gas
    O.J. Luiten
    December 30, 2023
============================================================================



This paper addresses the problem of Approximate Nearest Neighbor (ANN) search in pattern recognition where feature vectors in a database are encoded as compact codes in order to speed-up the similarity search in large-scale databases. Considering the ANN problem from an information-theoretic perspective, we interpret it as an encoding, which maps the original feature vectors to a less entropic sparse representation while requiring them to be as informative as possible. We then define the coding gain for ANN search using information-theoretic measures. We next show that the classical approach to this problem, which consists of binarization of the projected vectors is sub-optimal. Instead, a properly designed ternary encoding achieves higher coding gains and lower complexity. 



Approximate Nearest Neighbor search, content identification, binary hashing, coding gain, sparse representation 




§ INTRODUCTION


















The problem of content identification, e.g., identification of people from their biometrics or objects from unclonable features was first formalized in information-theoretic terms by Willems et. al. in <cit.>. They defined the identification capacity as the exponent of the number of database items M that could reliably be identified in an asymptotic case where the feature dimension n →∞. They modeled the enrollment and acquisition systems as noisy communication channels while they considered the vectors as random channel codes. The authors then characterized the identification capacity as I(F;Q), the mutual information between the enrolled items F and the noisy queries Q. In this setup, however, the increase in n leads to an exponential increase in M ≃ 2^nI(F;Q). This incurs infeasible search/memory complexities, making the system impractical. Subsequent works attempted at decreasing these complexities. For example, <cit.> considered a two-stage clustering-based system to speed-up the search, while <cit.> considered the compression of vectors prior to enrollment and studied the achievable storage and identification rates.

Similar to the content identification problem, the pattern recognition community considers the similarity search based on Nearest Neighbors (NN's) to a given query within the items in a database. This problem is the basis for many applications like similar image retrieval, copy detection, copywrite protection, etc. The idea is that semantic similarity can be mapped to distances within a vectorial space ℝ^n. The search for similarity then reduces to search for NN's by comparing the vectorial representation of a given query to representations of items in a database. The challenge, however, is when M is huge, e.g., billions. The NN search based on linear scan then becomes the main bottleneck for the system. Approximative solutions, where performance is traded with memory and complexity, are then to be preferred. This is addressed in Approximate Nearest Neighbor (ANN) search, an active topic in computer vision and machine learning communities.[Refer to <cit.> for detailed review of ANN methods and applications.]

The methods introduced for ANN in pattern recognition communities can roughly be divided into two main categories. A first category of methods is based on quantization of the data. These methods mainly target memory constraints where every database item is given an index, or a set of indices which refer to codeword(s) from a trained codebook. At the query time, the items are reconstructed from the codebooks and matched with the given query, usually using look-up-tables.

A second family of methods for ANN, also considered in this work, is based on projecting the data from ℝ^n to a usually lower dimensional space. The projected data are further binarized using the sign function. The search in the binary space is faster since it is less entropic than the original ℝ^n. Moreover, this approach brings more practical advantage since the distance matching in the binary space using the Hamming distance is performed in fixed-point instead of the floating point operations in the original real space or the space of codebooks in quantization-based methods.   

While the content identification literature is rigorously studying the fundamental limits of identification under storage or complexity constraints for known source and channel distributions and infinite code-lengths, the literature of ANN search drops these information-theoretic assumptions and hence treats the problem from a more practical perspective. This work tries to bridge these approaches. While we do not assume the asymptotic case and hence do not consider fundamental limits with their achievability and converse arguments, we propose a practical systems where it is explicitly required to maximize the mutual information between the query and database codes. Moreover, to address complexity requirements, we further require the codes to be sparse and hence allowing efficient search and storage. Concretely, this work brings the following contributions:


  * Considering the projection approach to ANN, we introduce the concept of “coding gain” to quantify the efficiency of a coding scheme for similarity search. 



  * We then show that the standard approach in the literature, which is based on binarization of the projected values, is sub-optimal. Instead, as was also shown recently in <cit.>, the ternarization approach namely the Sparse Ternary Codes (STC) is to be preferred. While in <cit.> this advantage was shown from the signal approximation points of view, here we characterize it in terms of coding gain.





  * We next show how to design the STC codes to maximize the coding gain. As opposed to the Maximum Likelihood (ML) decoder, we consider a sub-optimal but fast decoder, which brings sub-linear search complexity. Considering the memory-complexity trade-offs, this provides a wealth of possibilities for design, much richer than the binary counterpart while maintains all its advantages. Based on this decoder, we simulate an identification scenario showing the efficiency of the proposed methodology.


The problem formulation, along with the definition of the proposed coding gain are discussed in section <ref>. Binary codes are summarized in section <ref> while the ternary encoding is discussed in section <ref>. Comparison of the two encoding schemes in terms of the coding gain and also complexity ratio is performed in section <ref>. Finally, section <ref> concludes the paper. 







§ PRELIMINARIES
 




 §.§ Problem formulation
 
We consider a database ℱ = {𝐟(1), ⋯, 𝐟(M)} of M items as vectorial data-points 𝐟(i)'s, where 𝐟(i) = [f_1(i), ⋯, f_n(i)]^T  ∈ℝ^n and 1 ⩽ i ⩽ M. We assume, for the sake of analysis, that each database entry 𝐟(i) is a realization of a random vector 𝐅 whose n elements are i.i.d. realizations of a random variable F with F ∼𝒩(0,σ_F^2). 


The query 𝐪 = [q_1, ⋯, q_n]^T ∈ℝ^n is a perturbed version of an item from ℱ. We assume the perturbation follows an AWGN model as 𝐐 = 𝐅 + 𝐏, where elements of 𝐏∼𝒩(0,σ_P^2 𝐈_n ) are independent from elements of 𝐅. For a given query, the similarity search is based on a distance measure 𝒟(·,·): ℝ^n  ×ℝ^n →ℝ^+, which is assumed here to be the ℓ_2 distance, i.e., 𝒟_ℓ_2(𝐪,𝐟(i)) = ||𝐪 - 𝐟(i)||_2.

In the case of the content identification problem, the search system finds the nearest item from ℱ to 𝐪, i.e., î = _1 ⩽ i ⩽ M[𝒟_ℓ_2(𝐪,𝐟(i))], or produces a list ℒ(𝐪) of nearest items in the more general (A)NN search, i.e., ℒ(𝐪)  = { i :  𝒟_ℓ_2(𝐪,𝐟(i))  ⩽ϵ n }, where ϵ > 0 is a threshold.



 §.§ Coding gain for similarity search
 

The above problem formulation implies a memoryless  observation channel for queries. In <cit.> the identification capacity is defined for this channel (along with another AWGN for the enrollment channel) as a measure for the number of items that can be reliably identified. While this analysis is based on the asymptotic assumption where the number of items M should grow exponentially with dimension n, it can be argued, however, that M is fixed in practice and can be even well below the amount that the capacity would accommodate. Moreover, the probability of correct identification might be only asymptotically achievable and is less than 1 in practice.

Therefore, in this work, instead of the channel coding arguments, we consider the practical case where the focus is on fast decoding for which the given database is encoded. This comes with the price of lower identification performance. 

To quantify the efficiency of a coding scheme for fast ANN search under the setup of section <ref>, we consider the coding gain as the ratio of mutual information between the encoded versions of the enrolled items and query and the entropy of the enrolled items, i.e.: 


    g_ℱ(ψ_e,ψ_i) = I(X;Y)/H(X),

where the encoding for enrollment provides X = ψ_e[F] and encoding for identification provides Y = ψ_i[Q].[Notice that, unlike the usual binary design, in the STC framework, these two stages need not be the same. In fact, they are designed according to the statistics of the observation channel.]




   


Mutual information in the definition of Eq. <ref> can directly be linked to channel transition probabilities. The choice of entropy, on the other hand, is justified by both memory and complexity requirements. Obviously, the cost of the database storage is directly linked to H(X) when source coding is used. Moreover, since the effective space size is |𝒳^n| ≈ 2^nH(X), a lower entropic space also implies a lower search complexity.





§ BINARY CODES
 
Binary encoding is a classical approach widely used in the pattern recognition literature to address fast search methods. As mentioned earlier, they are based on projecting the data to a lower-dimensional space and binarizing them.



 §.§ Random Projections
 
The projection of vectors of ℱ and 𝐪 in ℝ^n is performed using random projections to ℝ^l.[The recent trend in pattern recognition is favoring projectors which are learned from the data. However, in practice, it turns out that the performance boost obtained from these methods is limited to low bit-rate regimes only. Moreover, they are not straightforward for analytic purposes. Therefore, here we opt for random projections.] This choice is justified by results like Johnson-Lindenstrauss lemma <cit.>, where, under certain conditions, the pair-wise distances in the projected domain are essentially preserved with probabilistic guarantees.


Random projections are usually performed using an n × l unit-norm matrix W whose elements are generated as i.i.d. from a Gaussian distribution W ∼𝒩(0,1/n). In the case of binary codes, for memory constraints, usually l < n. For the ternary codes proposed in <cit.>, which we analyze next, however, since the entropy can be bounded by imposing sparsity, longer code lengths can be considered. In this case, the use of sparse random projections of <cit.> is justified, where performance guarantees require longer lengths. This is very useful since the sparsity in the projector matrix can be reduced to 𝒪(2nl/s) instead of 𝒪(nl), where s is the sparsity parameter as in 
W ∼±√(s/2n),      w.p.       2/s, 

   0,       w.p.         1- 2/s.

According to the data model assumed in section <ref>, the elements of the projected data F̃ and Q̃ will also follow Gaussian distribution as F̃∼𝒩(0,σ_F^2) and Q̃|F̃∼𝒩(F̃, σ_P^2), where 𝐅̃^T = 𝐅^T W and 𝐐̃^T = 𝐐^T W. This gives the joint-distribution of the projected data as a bivariate Gaussian with ρ = σ_F/√(σ_F^2 + σ_P^2), i.e.,  p(f̃,q̃) = 𝒩([0,0]^T,[         σ_F^2         σ_F^2;         σ_F^2 σ_F^2 + σ_P^2 ]).


 §.§ Binarizing the projections
 
Binary codes are obtained by binarizing the projected values using the sign function, i.e.,  X_b = sign (F̃) and Y_b = sign (Q̃). One can consider an equivalent to the observation channel in the encoded case. In <cit.>, for the i.i.d. Gaussian setup, this channel was derived as a BSC with I(X_b,Y_b) = 1 - H_2(P_b), where P_b = 𝔼_p(q̃)[𝒬(|q̃|/σ_P)] = 1/πarccos(ρ) is the probability of bit flip and 𝒬(u) = ∫_u^∞1/√(2π)e^-u'/2 du' is the Q-function.

The maximum-likelihood optimal decoder for the binary codes is simply the minimum Hamming-distance decoder, i.e., î = 1 ⩽ i ⩽ Margmin [𝒟_H(𝐲_b,𝐱_b(i))] with 𝒟_H (𝐲, 𝐱) = 1/l∑_j = 1^l y_j ⊕ x_j and ⊕ representing the XOR operator. As mentioned earlier, this has two main practical advantages. First, the cost of storage of any database vector will reduce to l bits. Second, the search is performed on the binary vectors using fixed-point operations. However, as we will show in the next section, better performance can be achieved with STC, the ternary counterpart of the binary codes.  




§ SPARSE TERNARY CODES (STC)
 
The idea behind the STC <cit.> is that different projection values have different robustness to noise which can be expressed as a bit reliability measure. This can be achieved by ignoring the values whose magnitude is below a threshold, i.e., X_t = ϕ_λ_X(F̃) and Y_t = ϕ_λ_Y(Q̃), where: 

    ϕ_λ(t) =
    
       +1,     t ⩾λ, 
    
       0,     -λ <t < λ, 
    
        -1,      t ⩽ -λ,

and λ_X and λ_Y are threshold values for the enrolled items and the query, respectively. The threshold values λ_X and λ_Y directly influence the sparsity ratios α, the ratio of the number of elements of 𝐗_t with non-zero values ({± 1 }'s)  to the code length l and γ, the ratio of the number of elements of 𝐘_t with non-zero values to the code length l. These values can be easily calculated as:

    α   =  ∫_-∞^-λ_X p(f̃) df̃ + ∫_λ_X^∞ p(f̃) df̃ = 2𝒬(λ_X/σ_F), 
    γ   =  ∫_-∞^-λ_Y p(q̃) dq̃ + ∫_λ_Y^∞ p(q̃) dq̃ = 2𝒬(λ_Y/√(σ_F^2 + σ_P^2)).


Complementary to <cit.> where the choice of ϕ_λ was justified as an approximation for the hard-thresholding function, the optimal solution to the direct sparse approximation problem, here we propose an information-theoretic argument.



 §.§ Information measures for STC

It is very useful to study the equivalent ternary channel between X_t and Y_t. The element-wise entropy of the ternary code is:

    H(X_t) = -2α log_2(α) - (1-2α)log_2(1-2α).


According to Eq. <ref>, this is only a function of the threshold value λ_X (see Fig. <ref>.a).















 
As for I(X_t;Y_t), unlike the binary case we cannot have a closed form expression. Instead, we calculate this quantity with numerical integration. 

Consider the transition probabilities for ternary channel:

    P = p(y|x)=
      [ p_+1|+1  p_0|+1 p_-1|+1;  p_+1|0   p_0|0  p_-1|0; p_+1|-1  p_0|-1 p_-1|-1;         ].

The elements of the transition matrix P are defined as the integration of the conditional distribution p(Q̃|F̃) = p(F̃,Q̃)/p(F̃) with proper integral limits and calculated numerically for these threshold values. For example, p_+1|+1 = p_Q̃|F̃(+1|+1) = ∫_λ_Y^∞∫_λ_X^∞ p(f̃,q̃) df̃ dq̃/∫_λ_X^∞ p(f̃) df̃ is the probability that values of F̃ greater than λ_X are queried with values greater than λ_Y while p_0|+1 = p_Q̃|F̃(0|+1) = ∫_-λ_Y^λ_Y∫_λ_X^∞ p(f̃,q̃) df̃ dq̃/∫_λ_X^∞ p(f̃) df̃ quantifies the probability that these values have magnitudes less than λ_Y in the query and hence will be assigned as `0' in the ternary representation. Out of these 9 transition probabilities, 5 are independent and the rest are replicated due to symmetry.


The mutual information in the ternary case is:

    I(X_t;Y_t) = H(X_t) + H(Y_t) - H(X_t,Y_t),

where H(X_t) is given by Eq. <ref>. Similarly, H(Y_t) = -2γ log_2(γ) - (1-2γ)log_2(1-2γ), where γ can be derived from its definition of Eq. <ref> or, equivalently γ = α (P(1,1) + P(1,3)) + (1-2 α) P(1,2). The joint entropy is then calculated from elements of P as:


    H(X_t,Y_t)    =  -2 αP(1,1)log(αP(1,1)) 
       -2 αP(1,2)log(αP(1,2)) -2 αP(1,3)log(αP(1,3))
       -2 (1-2α) P(2,1)log((1-2α) P(2,1))
        -(1-2α) P(2,2)log((1-2α) P(2,2)).

This, in fact, is a function only of λ_X, λ_Y and σ_P^2. We will use these quantities in section <ref> to compare the coding gain of these ternary codes with those of binary codes.  















 §.§ Fast sub-linear decoder
 

Given a ternary sequence 𝐲 = (y_1,⋯,y_l)^T, the maximum-likelihood rule to choose the optimal 𝐱(i) amongst the registered 𝐱(1),⋯,𝐱(M) is given as î = _1 ⩽ i ⩽ M  p_𝐘|𝐗(𝐲 |𝐱(i) ). This rule can be simplified as the maximization of the log-likelihood as: 

    î = _1 ⩽ i ⩽ M∑_j = 1^l logp_Y|X(y_j|x_j(i)).

This requires to take into account all the 9 transition probabilities of Eq. <ref>.

Similar to the binary codes, the above maximum-likelihood decoder should exhaustively scan all the M items in the database. However, by skipping the transitions to and from `0' and only considering elements of P containing `+1' and `-1', an alternative decoder can be considered as:




    î = _1 ⩽ i ⩽ M∑_j = 1^n [ ν (1_{ x_j = y_j = +1 } + 1_{ x_j = y_j = -1 }   ) 
    
    +ν' (1_{ x_j = +1, y_j = -1 } + 1_{ x_j = -1, y_j = +1 }   ) ],

where ν and ν' are voting constants that will be specified shortly and 1_{·} is the indicator function.


This decoder is sub-optimal in the ML sense since instead of taking into account all the 9 transitions (from which 5 independent), it considers only 4 transitions (from which 3 independent) and treats the other 5 as the same. However, it performs the search in sub-linear complexity instead of the otherwise exhaustive scan. As we will show next, this allows us to drastically reduce the search complexity. An algorithmic description of this decoder was given in <cit.> for practical scenarios. In this work, however, since we are assuming a known distribution for the data, we can calculate the optimal values of ν and ν' as Eq. <ref>, where ν encourages sign match and ν' is a negative value that penalizes sign mismatch. Since we are ignoring the `0' transitions, ν^0 is a bias term and compensates by considering the expectation of the occurrences of logp(y|x) terms in Eq. <ref>, when either x or y is `0'.


    ν   =  ν^0 + log(P(1,1)), 
    ν'    =  ν^0 + log(P(1,3)),
    ν^0    =  -[ 2αP(1,2) logP(1,2)
       + (1-2 α) (2P(2,1) logP(2,1) + P(2,2) logP(2,2))  ].






§ SIMULATION RESULTS
 


 §.§ Comparison of Sparse Ternary Codes with dense binary codes
 
Here we compare the coding gain of STC with dense binary codes. The mutual information of the ternary code depends on both λ_X and λ_Y, therefore, for different values of λ_X[In practice, this is chosen based on memory constraints.], we choose λ_Y that maximizes I(X_t;Y_t). Since there is no analytic expression for the maximum of I(X_t;Y_t), for a fixed λ_X, we use a simple grid search among different values of λ_Y for the maximizer of mutual information. Fig. <ref>.d shows the (λ_X, λ_Y^*) pairs under three different noise levels, as characterized by SNR = 10log_10σ_F^2/σ_P^2.



For fair comparison, we choose the code lengths of binary and ternary cases (l_b and l_t, respectively) to ensure the same code entropy, i.e., l_bH(X_b) = l_t H(X_t). We then compare 
l_bI(X_b,Y_b) with l_tI(X_t,Y_t) in Fig. <ref>.b.


























 





















 
















As is seen from this figure, the proper choice of thresholds leads to interesting regimes where, for the same entropy and hence the same number of bits, the ternary code preserves more mutual information compared to binary codes. 







 §.§ Identification performance

We consider the identification of synthetic data by comparing the probability of correct identification for different pairs of memory and complexity ratio in Fig. <ref>. Memory usage is measured by entropy of a coded block, i.e., l_bH(X_b) for the binary and l_tH(X_t) and ternary while complexity ratio is measured as l_b/n and 4αγ l_t/n, for the binary and ternary codes, respectively. Keeping the complexity of the sparse random projections stage the same in both cases in each experiment, for equal memory usage, a large gap is observed between the complexity ratios of the two counterparts. Furthermore, usually much better performance is achieved for the STC.








§ CONCLUSIONS
 
This work is an attempt to bridge the problem of content identification with that of similarity search based on Nearest Neighbors in pattern recognition. Based on information-theoretic insights, the concept of coding gain was proposed as a figure of merit. It was shown that the Sparse Ternary Codes posses higher coding gain than the classical dense binary hashing scheme and hence provide better performance-complexity-memory trade-offs. As a future work, the extension to compression-based setups for the STC will be studied.  







IEEEbib



