Timezone: »

 
Poster
Random Projections with Asymmetric Quantization
Xiaoyun Li · Ping Li

Tue Dec 10 05:30 PM -- 07:30 PM (PST) @ East Exhibition Hall B + C #33
in Algorithms -- Large Scale Learning »

The method of random projection has been a popular tool for data compression, similarity search, and machine learning. In many practical scenarios, applying quantization on randomly projected data could be very helpful to further reduce storage cost and facilitate more efficient retrievals, while only suffering from little loss in accuracy. In real-world applications, however, data collected from different sources may be quantized under different schemes, which calls for a need to study the asymmetric quantization problem. In this paper, we investigate the cosine similarity estimators derived in such setting under the Lloyd-Max (LM) quantization scheme. We thoroughly analyze the biases and variances of a series of estimators including the basic simple estimators, their normalized versions, and their debiased versions. Furthermore, by studying the monotonicity, we show that the expectation of proposed estimators increases with the true cosine similarity, on a broader family of stair-shaped quantizers. Experiments on nearest neighbor search justify the theory and illustrate the effectiveness of our proposed estimators.

Keywords: Information Theory · Similarity and Distance Learning · Algorithms · Theory
[ Paper]  [ Slides] 

Author Information

Xiaoyun Li (Rutgers University)

Xiaoyun Li is a 4th year PhD student from the Department of Statistics at Rutgers University, supervised by Professor Ping Li. His research interests include statistical learning, hashing, randomized algorithms and optimization.

Ping Li (Baidu Research USA)

More from the Same Authors