Introduction Data-Independent Methods The hash 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) MinHash (Broder et al.,1998)and the extensions (Li and Konig, 2011) Hash function:random projections or manually constructed. They do not belong to learning to hash methods.Hence,this kind of methods will not be included in this tutorial. Li (http://cs.nju.edu.cn/lwj) Learning to Hash CS.NJU 11 /210
Introduction Data-Independent Methods The hash 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). MinHash (Broder et al., 1998) and the extensions (Li and K¨onig, 2011) Hash function: random projections or manually constructed. They do not belong to learning to hash methods. Hence, this kind of methods will not be included in this tutorial. Li (http://cs.nju.edu.cn/lwj) Learning to Hash CS, NJU 11 / 210
Introduction Data-Dependent Methods Hash functions are learned from a given training dataset. o Compared with data-independent methods,data-dependent methods(also called learning to hash methods)can achieve comparable or even better accuracy with shorter binary codes. Seminal papers:(Salakhutdinov and Hinton,2007,2009;Torralba et al., 2008;Weiss et al.,2008) Two categories: o Unimodal 。Supervised methods given some supervised(semantic)information,such as pairwise labels sij.point-wise labels yi or triplet labels (xj,) .Unsupervised methods 。Multimodal 。Supervised methods Unsupervised methods 日卡三4元，互Q0 Li (http://cs.nju.edu.cn/lwj) Learning to Hash CS.NJU 12/210
Introduction Data-Dependent Methods Hash functions are learned from a given training dataset. Compared with data-independent methods, data-dependent methods (also called learning to hash methods) can achieve comparable or even better accuracy with shorter binary codes. Seminal papers: (Salakhutdinov and Hinton, 2007, 2009; Torralba et al., 2008; Weiss et al., 2008) Two categories: Unimodal Supervised methods given some supervised (semantic) information, such as pairwise labels sij , point-wise labels yi or triplet labels (xi , xj , xk) Unsupervised methods Multimodal Supervised methods Unsupervised methods Li (http://cs.nju.edu.cn/lwj) Learning to Hash CS, NJU 12 / 210
Introduction (Unimodal)Unsupervised Methods No labels to denote the categories of the training points. o PCAH:principal component analysis. SH:(Weiss et al.,2008)eigenfunctions computed from the data similarity graph. AGH:anchor graph-based hashing (Liu et al.,2011). ITQ:(Gong and Lazebnik,2011)orthogonal rotation matrix to refine the initial projection matrix learned by PCA. IsoHash:(Kong and Li,2012b)orthogonal rotation matrix to make the variances of different directions isotropic (equal) DGH:(Liu et al.,2014)directly learn the discrete binary code SGH:(Jiang and Li,2015)scalable graph hashing with feature transformation 口卡24元互Q0 Li (http://cs.nju.edu.cn/lwj) Learning to Hash CS.NJU 13/210
Introduction (Unimodal) Unsupervised Methods No labels to denote the categories of the training points. PCAH: principal component analysis. SH: (Weiss et al., 2008) eigenfunctions computed from the data similarity graph. AGH: anchor graph-based hashing (Liu et al., 2011). ITQ: (Gong and Lazebnik, 2011) orthogonal rotation matrix to refine the initial projection matrix learned by PCA. IsoHash: (Kong and Li, 2012b) orthogonal rotation matrix to make the variances of different directions isotropic (equal) DGH: (Liu et al., 2014) directly learn the discrete binary code SGH: (Jiang and Li, 2015) scalable graph hashing with feature transformation Li (http://cs.nju.edu.cn/lwj) Learning to Hash CS, NJU 13 / 210
Introduction (Unimodal)Supervised (semi-supervised)Methods Class labels or pairwise constraints: SSH (SPLH):Semi-supervised hashing (Wang et al.,2010a,b) exploiting both labeled data and unlabeled data MLH:Minimal loss hashing (Norouzi and Fleet,2011)based on the latent structural SVM framework LDAHash:Linear discriminant analysis based hashing (Strecha et al., 2012) KSH:Kernel-based supervised hashing (Liu et al.,2012) LFH:Latent factor models for supervised hashing(Zhang et al., 2014) FastH:(Lin et al.,2014)Supervised hashing using graph cut and decision trees SDH:(Shen et al.,2015)Supervised discrete hashing with point-wise labels COSDISH:(Kang et al.,2016)Scalable discrete hashing with pairwise supervision Li (http://cs.nju.edu.cn/lwj) Learning to Hash CS.NJU 14 /210
Introduction (Unimodal) Supervised (semi-supervised) Methods Class labels or pairwise constraints: SSH (SPLH): Semi-supervised hashing (Wang et al., 2010a,b) exploiting both labeled data and unlabeled data MLH: Minimal loss hashing (Norouzi and Fleet, 2011) based on the latent structural SVM framework LDAHash: Linear discriminant analysis based hashing (Strecha et al., 2012) KSH: Kernel-based supervised hashing (Liu et al., 2012) LFH: Latent factor models for supervised hashing (Zhang et al., 2014) FastH: (Lin et al., 2014) Supervised hashing using graph cut and decision trees SDH: (Shen et al., 2015) Supervised discrete hashing with point-wise labels COSDISH: (Kang et al., 2016) Scalable discrete hashing with pairwise supervision Li (http://cs.nju.edu.cn/lwj) Learning to Hash CS, NJU 14 / 210
Introduction Ranking-based Methods The supervised information is ranking labels,such as triplets(xi,xj,x). HDML:Hamming distance metric learning(Norouzi et al.,2012) o OPH:Order preserving hashing for approximate nearest neighbor search (Wang et al.,2013b) o RSH:Learning hash codes with listwise supervision(Wang et al., 2013a) oRPH:Ranking preserving hashing for fast similarity search(Wang etal,2015) 日卡三4元，互Q0 Li (http://cs.nju.edu.cn/lvj) Learning to Hash CS.NJU 15/210
Introduction Ranking-based Methods The supervised information is ranking labels, such as triplets (xi , xj , xk). HDML: Hamming distance metric learning (Norouzi et al., 2012) OPH: Order preserving hashing for approximate nearest neighbor search (Wang et al., 2013b) RSH: Learning hash codes with listwise supervision (Wang et al., 2013a) RPH: Ranking preserving hashing for fast similarity search (Wang et al., 2015) Li (http://cs.nju.edu.cn/lwj) Learning to Hash CS, NJU 15 / 210