Learning to Hash Similarity Preserving Hashing h(Statue of Liberty)= h(Napoleon)= h (Napoleon)= 10001010 01100001 011001Q1 flipped bit Should be very different Should be similar 0Q0 Li (http://cs.nju.edu.cn/lvj) Big Learning CS.NJU 11/115
Learning to Hash Similarity Preserving Hashing Li (http://cs.nju.edu.cn/lwj) Big Learning CS, NJU 11 / 115
Learning to Hash Reduce Dimensionality and Storage Cost Gist vector Binary reduction 10 million images 20 GB 160MB 口卡+得二4元互)Q0 Li (http://cs.nju.edu.cn/lwj) Big Leaming CS.NJU 12 /115
Learning to Hash Reduce Dimensionality and Storage Cost Li (http://cs.nju.edu.cn/lwj) Big Learning CS, NJU 12 / 115
Learning to Hash Fast Query Speed o By using hash-code to construct index,we can achieve constant or sub-linear search time complexity. o In some cases,exhaustive search with linear time complexity is also acceptable because the distance calculation cost is low with binary representation. 日卡三4元，互Q0 Li (http://cs.nju.edu.cn/lwj) Big Leamning CS.NJU 13/115
Learning to Hash Fast Query Speed By using hash-code to construct index, we can achieve constant or sub-linear search time complexity. In some cases, exhaustive search with linear time complexity is also acceptable because the distance calculation cost is low with binary representation. Li (http://cs.nju.edu.cn/lwj) Big Learning CS, NJU 13 / 115
Learning to Hash Two Stages of Hash Function Learning Two main categories: oCategory I: Projection Stage (Dimension Reduction) Projected with real-valued projection function o Given a point x,each projected dimension i will be associated with a real-valued projection function fi(x)(e.g.,fi(x)=wx) Quantization Stage Turn real into binary o Essential difference between metric learning and learning to hash Category Il: Binary-Code Learning Stage Hash Function Learning Stage 日卡三4元，互Q0 Li (http://cs.nju.edu.cn/lvj) Big Leaming CS.NJU 14 /115
Learning to Hash Two Stages of Hash Function Learning Two main categories: Category I: Projection Stage (Dimension Reduction) Projected with real-valued projection function Given a point x, each projected dimension i will be associated with a real-valued projection function fi(x) (e.g., fi(x) = wT i x) Quantization Stage Turn real into binary Essential difference between metric learning and learning to hash Category II: Binary-Code Learning Stage Hash Function Learning Stage Li (http://cs.nju.edu.cn/lwj) Big Learning CS, NJU 14 / 115
Learning to Hash Our Contribution o Unsupervised Hashing Isotropic hashing (IsoHash)[NIPS 2012] Scalable graph hashing with feature transformation [IJCAl 2015] Supervised Hashing Supervised hashing with latent factor models [SIGIR 2014] Column sampling based discrete supervised hashing [AAAI 2016] Feature learning based deep supervised hashing with pairwise labels [arXiv 2015] Multimodal Hashing Large-scale supervised multimodal hashing with semantic correlation maximization [AAAl 2014] Multiple-Bit Quantization Double-bit quantization (DBQ)[AAAI 2012] Manhattan quantization (MQ)[SIGIR 2012] 口卡得三4元互)Q0 Li (http://cs.nju.edu.cn/lvj) Big Learning CS.NJU 15 /115
Learning to Hash Our Contribution Unsupervised Hashing Isotropic hashing (IsoHash) [NIPS 2012] Scalable graph hashing with feature transformation [IJCAI 2015] Supervised Hashing Supervised hashing with latent factor models [SIGIR 2014] Column sampling based discrete supervised hashing [AAAI 2016] Feature learning based deep supervised hashing with pairwise labels [arXiv 2015] Multimodal Hashing Large-scale supervised multimodal hashing with semantic correlation maximization [AAAI 2014] Multiple-Bit Quantization Double-bit quantization (DBQ) [AAAI 2012] Manhattan quantization (MQ) [SIGIR 2012] Li (http://cs.nju.edu.cn/lwj) Big Learning CS, NJU 15 / 115