Coding for Random Projections

By Ping Li, Michael M. Mitzenmacher, Anshumali Shrivastava. 2013

49 citations recorded by the source corpus.

The method of random projections has become popular for large-scale applications in statistical learning, information retrieval, bio-informatics and other applications. Using a well-designed coding scheme for the projected data, which determines the number of bits needed for each projected value and how to allocate these bits, can significantly improve the effectiveness of the algorithm, in storage cost as well as computational speed. In this paper, we study a number of simple coding schemes, focusing on the task of similarity estimation and on an application to training linear classifiers. We demonstrate that uniform quantization outperforms the standard and influential method (Datar et al., 2004), which used a window-and-random offset scheme. Indeed, we argue that in many cases coding with just a small number of bits suffices. Furthermore, we also develop a non-uniform 2-bit coding scheme that generally performs well in practice, as confirmed by our experiments on training linear support vector machines (SVM). Proofs and additional experiments are available at arXiv:1308.2218. In the context of using coded random projections for approximate near neighbor search by building hash tables (arXiv:1403.8144) (Li et al., 2014), we show that the step of random off-set in (Datar et al., 2004) is again not needed and may hurt the performance. Furthermore, we show that, unless the target similarity level is high, it usually suffices to use only 1 or 2 bits to code each hashed value for this task. Section 7 presents some experimental results for LSH.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Representation & Self-Supervised Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Representation & Self-Supervised Learning

Citations in the corpus

Asymmetric LSH (ALSH) for Sublinear Time Maximum Inner Product Search (MIPS) (2014, background): “The recent work on coding for random projections [16] showed that L2LSH can be improved when the data are normalized for building large-scale linear classifiers as well as near neighbor search [17].”
COD3S: Diverse Generation with Discrete Semantic Signatures (2020, unknown): “14 Charikar (2002); Li et al. (2013) B Training Details fairseq-train --adam-betas "(0.9, 0.98)" --arch transformer_iwslt_de_en --criterion label_smoothed_cross_entropy --label-smoothing 0.1 --dropout 0.1 --weight-decay 0 --bpe sentencepiece --optimizer adam --clip-norm 0.1 --lr 5e-4 --lr-scheduler…”
Improved Asymmetric Locality Sensitive Hashing (ALSH) for Maximum Inner Product Search (MIPS) (2014, background): “Recently in [17, 18], it was observed that the quantization of random projections used by traditional L2-LSH scheme is not desirable when the data is normalized and in fact the shift b in Eq.”
Hashing for Similarity Search: A Survey (2014, background): “It is claimed that uniform quantization [72] without the offset b, hw(x) = ⌊ x r ⌋ is more accurate and uses fewer bits than the scheme with the offset.”
Coding for Random Projections and Approximate Near Neighbor Search (2014, methodology): “[4] elaborated the following advantages of (4) in the context of similarity est imation: 1.”
Asymmetric Minwise Hashing (2014, background): “As demonstrated by the recent work [26] on coding for random projections , there is a signiﬁcant advantage of SRP over L2LSH for near neighbor search.”