Learning to Hash Fast Query Speed o By using hashing scheme,we can achieve constant or sub-linear search time complexity. Exhaustive search is also acceptable because the distance calculation cost is cheap now. 日卡三4元，互Q0 Li (http://cs.nju.edu.cn/lwj) Big Leaming CS.NJU 16/79
Learning to Hash Fast Query Speed By using hashing scheme, we can achieve constant or sub-linear search time complexity. Exhaustive search is also acceptable because the distance calculation cost is cheap now. Li (http://cs.nju.edu.cn/lwj) Big Learning CS, NJU 16 / 79
Learning to Hash Two Stages of Hash Function Learning Projection Stage (Dimension Reduction) Projected with real-valued projection function Given a point r,each projected dimension i will be associated with a real-valued projection function fi()(e.g.fi()=w) ●Quantization Stage Turn real into binary 日卡三4元，互Q0 Li (http://cs.nju.edu.cn/lwj) Big Leaming CS.NJU 17 /79
Learning to Hash Two Stages of Hash Function Learning 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) = w T i x) Quantization Stage Turn real into binary Li (http://cs.nju.edu.cn/lwj) Big Learning CS, NJU 17 / 79
Learning to Hash Our Contribution Unsupervised Hashing [NIPS 2012]: Isotropic hashing(IsoHash) Supervised Hashing [SIGIR 2014]: Supervised hashing with latent factor models Multimodal Hashing [AAAI 2014]: Large-scale supervised multimodal hashing with semantic correlation maximization Multiple-Bit Quantization: Double-bit quantization (DBQ)[AAAI 2012] Manhattan quantization (MQ)[SIGIR 2012] 口卡+得二4元互)Q0 Li (http://cs.nju.edu.cn/lwj) Big Learing CS.NJU 18 /79
Learning to Hash Our Contribution Unsupervised Hashing [NIPS 2012]: Isotropic hashing (IsoHash) Supervised Hashing [SIGIR 2014]: Supervised hashing with latent factor models Multimodal Hashing [AAAI 2014]: Large-scale supervised multimodal hashing with semantic correlation maximization 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 18 / 79
Learning to Hash Isotropic Hashing Motivation Problem: All existing methods use the same number of bits for different projected dimensions with different variances. PCA2 PCAI XX ◆X Possible Solutions: oDifferent number of bits for different dimensions (Unfortunately,have not found an effective way) oIsotropic (equal)variances for all dimensions 口卡+得二4元互)Q0 Li (http://cs.nju.edu.cn/lvj) Big Leamning CS.NJU 19 /79
Learning to Hash Isotropic Hashing Motivation Problem: All existing methods use the same number of bits for different projected dimensions with different variances. Possible Solutions: Different number of bits for different dimensions (Unfortunately, have not found an effective way) Isotropic (equal) variances for all dimensions Li (http://cs.nju.edu.cn/lwj) Big Learning CS, NJU 19 / 79
Learning to Hash Isotropic Hashing PCA Hash To generate a code of m bits,PCAH performs PCA on X,and then use the top m eigenvectors of the matrixXXT as columns of the projection matrix W ERdxm.Here,top m eigenvectors are those corresponding to the m largest eigenvalues generally arranged with the non-increasing order1≥2≥…≥入m.LetA=[d,2,…,入mJT. Then A=WTXXTW diag(A) Define hash function h(x)=sgn(WTx) 日卡三4元，互)Q0 Li (http://cs.nju.edu.cn/lwj) Big Leamning CS.NJU 20/79
Learning to Hash Isotropic Hashing PCA Hash To generate a code of m bits, PCAH performs PCA on X, and then use the top m eigenvectors of the matrix XXT as columns of the projection matrix W ∈ R d×m. Here, top m eigenvectors are those corresponding to the m largest eigenvalues {λk} m k=1, generally arranged with the non-increasing order λ1 ≥ λ2 ≥ · · · ≥ λm. Let λ = [λ1, λ2, · · · , λm] T . Then Λ = WT XXTW = diag(λ) Define hash function h(x) = sgn(WT x) Li (http://cs.nju.edu.cn/lwj) Big Learning CS, NJU 20 / 79