On Design Choices in Similarity-Preserving Sparse Randomized Embeddings

Denis Kleyko, Dmitri A. RachkovskijIJCNN 2024 · DOI

TL;DR

This paper explores how different design choices in the FlyHash algorithm, a method for creating sparse, similarity-preserving embeddings, impact performance on similarity search tasks. They found that the right combination of preprocessing, random projection matrix properties, and non-linear activation functions can significantly improve search accuracy, highlighting the importance of these choices beyond just computational efficiency.

What Problem Does This Paper Address?

Similarity search is a fundamental task in many machine learning applications, from image retrieval to document analysis. Sparse randomized embeddings offer an efficient way to represent high-dimensional data while preserving similarity relationships, making them attractive for these tasks. The FlyHash algorithm, inspired by biological neural circuits, is one such method that uses a "Expand & Sparsify" principle to achieve this. However, FlyHash, like many algorithms, has several design choices (e.g., how to preprocess data, the distribution of values in the random projection matrix, and the choice of sparsifying function) that can significantly affect its performance. This paper aims to systematically investigate the impact of these choices on the effectiveness of FlyHash for similarity search, moving beyond just computational aspects to focus on the quality of the resulting embeddings.

Methods

The paper delves into several design choices within the FlyHash framework:

  • Preprocessing of Input Data: They explore various methods to prepare input vectors before embedding, including:
  • Original FlyHash Preprocessing: Biasing components to be non-negative and then rescaling the mean.
  • Mean Centering: Subtracting the mean of each feature across the dataset.
  • Normalization: Scaling vectors to have unit L2 norm.
  • Combined Mean Centering & Normalization: A combination of the above.
  • Random Projection (RP) Matrix Properties: The study investigates:
  • Distribution of Values: Comparing binomial and hypergeometric distributions for generating sparse binary RP matrices.
  • Density: Examining the effect of different densities (sparsity levels) of non-zero entries in the RP matrix.
  • Non-linear Transformation (Sparsifying Function): Beyond the standard k-Winner-Take-All (kWTA) function, they introduce and analyze:
  • Block Sparse Codes: A structured non-linearity that imposes a constraint on where non-zero elements can appear, leading to more compact representations. They explore two variants: "matching k" (same number of non-zero elements as kWTA) and "matching bits" (same number of bits to represent the embedding).
  • Sequential Processing: Investigating how processing embeddings block-by-block affects performance.

Datasets

The experiments were conducted on three standard datasets:

  • SIFT: (d=128) - Image descriptors.
  • GLOVE: (d=300) - Word embeddings.
  • MNIST: (d=784) - Handwritten digit images.

For each dataset, a subset of $N=10^4$ input vectors was selected. The paper does not introduce new benchmarks but uses these existing datasets to evaluate the impact of the design choices.

Key Insights and Ideas

  • Preprocessing is Crucial: The choice of data preprocessing significantly impacts similarity search performance. For instance, mean centering and normalization combined with angle-based ranking yielded excellent results, especially for dense datasets like GLOVE.
  • Angle vs. Euclidean Distance Ranking: The choice of similarity measure (Euclidean distance or angle) interacts strongly with preprocessing and embedding type. Binary embeddings, having fixed norms, make angle and Euclidean distance rankings equivalent, simplifying analysis.
  • Hypergeometric Distribution Benefits Sparsity: For dense input data (like GLOVE), using a hypergeometric distribution for the RP matrix offered substantial performance gains over the binomial distribution, particularly when the density of non-zero entries was low.
  • Block Sparse Codes Offer Efficiency: While standard kWTA is effective, block sparse codes, especially the "matching bits" variant, can achieve comparable or better performance while requiring fewer bits to store the embeddings. This suggests a better "performance per bit" trade-off.
  • Sequential Processing of Blocks: The ability to process embeddings sequentially in block sparse codes is demonstrated, showing that performance can be built up incrementally.

Key Results

  • Preprocessing Impact: Mean centering and normalization preprocessing, when combined with angle-based ranking, consistently outperformed other preprocessing methods across datasets and embedding types, especially for GLOVE.
  • RP Matrix Distribution: For dense datasets like GLOVE, the hypergeometric distribution for the RP matrix showed a significant improvement in MAP compared to the binomial distribution, especially at lower densities.
  • Block Sparse Codes: The "block sparse; matching bits" variant consistently outperformed the standard binary kWTA and the "block sparse; matching k" variant, demonstrating higher performance per bit. For example, in some configurations, it achieved higher MAP with fewer bits.
  • General Trend: In most cases, MAP increased with the number of active components ($k$), indicating that higher-dimensional embeddings generally lead to better similarity preservation.

Limitations and Future Work

  • Focus on Similarity Preservation: The study primarily focuses on preserving rankings and similarity measures between input vectors. The authors acknowledge that embeddings should ideally preserve the specific similarity measure beneficial for the downstream task.
  • Computational Cost of Block Sparse: While "block sparse; matching bits" offers better storage efficiency, the paper doesn't extensively detail its computational cost compared to kWTA.
  • Learned Projection Matrices: The paper mentions that learned projection matrices can improve performance but does not explore this avenue. Future work could investigate methods for generating sparse projection matrices adapted to input data.
  • Block Size vs. Number of Blocks: For block sparse codes, the paper explored increasing the number of blocks ($k'$) to match bits. Future work could investigate expanding the block size instead.
  • Binary vs. Non-binary Embeddings: The study primarily focused on binary embeddings. Future work could explore the performance trade-offs between binary and non-binary kWTA embeddings, especially concerning bit representation and density.
  • Hardware Implementation: The authors note that binary embeddings are amenable to specialized hardware, suggesting this as a practical consideration for future exploration.

Summary updated

BibTeX
@inproceedings{kleyko2024design,
  author = {Denis Kleyko and Dmitri A. Rachkovskij},
  title = {{On Design Choices in Similarity-Preserving Sparse Randomized Embeddings}},
  booktitle = {IJCNN},
  year = {2024},
  doi = {10.1109/ijcnn60899.2024.10651277},
}
Figure