Introduction Problem Definition 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://www.cs.sjtu.edu.cn/-livujun Learning to Hash CSE,SJTU 11/45
Introduction Problem Definition 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://www.cs.sjtu.edu.cn/~liwujun) Learning to Hash CSE, SJTU 11 / 45
Introduction Existing Methods Data-Independent Methods The hashing function family is defined independently of the training dataset: Locality-sensitive hashing (LSH):(Gionis et al.,1999;Andoni and Indyk,2008)and its extensions (Datar et al.,2004;Kulis and Grauman,2009;Kulis et al.,2009) SIKH:Shift invariant kernel hashing(SIKH)(Raginsky and Lazebnik 2009) Hashing function:random projections. 日卡三4元，互Q0 (http://www.cs.sjtu.edu.cn/-livujun Learning to Hash CSE.SJTU 12 /45
Introduction Existing Methods Data-Independent Methods The hashing function family is defined independently of the training dataset: Locality-sensitive hashing (LSH): (Gionis et al., 1999; Andoni and Indyk, 2008) and its extensions (Datar et al., 2004; Kulis and Grauman, 2009; Kulis et al., 2009). SIKH: Shift invariant kernel hashing (SIKH) (Raginsky and Lazebnik, 2009). Hashing function: random projections. Li (http://www.cs.sjtu.edu.cn/~liwujun) Learning to Hash CSE, SJTU 12 / 45
Introduction Existing Methods Data-Dependent Methods Hashing functions are learned from a given training dataset. oRelatively short codes Two categories: ●Supervised methods 8(ri,x）=1or0 oUnsupervised methods 日卡三4元，互Q0 Li (http://www.cs.sjtu.edu.cn/-livujun) Learning to Hash CSE,SJTU 13/45
Introduction Existing Methods Data-Dependent Methods Hashing functions are learned from a given training dataset. Relatively short codes Two categories: Supervised methods s(xi , xj ) = 1 or 0 Unsupervised methods Li (http://www.cs.sjtu.edu.cn/~liwujun) Learning to Hash CSE, SJTU 13 / 45
Introduction Existing Methods Unsupervised Methods No labels to denote the similarity (neighborhood)between points. o PCAH:principal component analysis. ITQ:(Gong and Lazebnik,2011)orthogonal rotation matrix to refine the initial projection matrix learned by PCA. 日卡三4元，互Q0 Li (http://www.cs.sjtu.edu.cn/-livujun Learning to Hash CSE.SJTU 14/45
Introduction Existing Methods Unsupervised Methods No labels to denote the similarity (neighborhood) between points. PCAH: principal component analysis. ITQ: (Gong and Lazebnik, 2011) orthogonal rotation matrix to refine the initial projection matrix learned by PCA. Li (http://www.cs.sjtu.edu.cn/~liwujun) Learning to Hash CSE, SJTU 14 / 45
Introduction Existing Methods Supervised (semi-supervised)Methods Training dataset contains additional supervised information,(e.g.class labels or pairwise constraints). SH:Spectral Hashing (SH)(Weiss et al.,2008)adopts the eigenfunctions computed from the data similarity graph. SSH:Semi-Supervised Hashing (SSH)(Wang et al.,2010a,b)exploits both labeled data and unlabeled data for hash function learning. MLH:Minimal loss hashing (MLH)(Norouzi and Fleet,2011)based on the latent structural SVM framework. AGH:Graph-based hashing (Liu et al.,2011) 日卡三4元，互Q0 Li (http://www.cs.sjtu.edu.cn/-livujun Learning to Hash CSE.SJTU 15/45
Introduction Existing Methods Supervised (semi-supervised) Methods Training dataset contains additional supervised information, (e.g. class labels or pairwise constraints). SH: Spectral Hashing (SH) (Weiss et al., 2008) adopts the eigenfunctions computed from the data similarity graph. SSH: Semi-Supervised Hashing (SSH) (Wang et al., 2010a,b) exploits both labeled data and unlabeled data for hash function learning. MLH: Minimal loss hashing (MLH) (Norouzi and Fleet, 2011) based on the latent structural SVM framework. AGH: Graph-based hashing (Liu et al., 2011). Li (http://www.cs.sjtu.edu.cn/~liwujun) Learning to Hash CSE, SJTU 15 / 45