2023年7月29日发(作者：)

KSH算法　　 这⼏天看了算法，这篇博客主要是把⾃⼰的⼀些理解记下来，最近记性⽐较差。。。哈哈⼀ KSH算法原理　　　KSH算法，出⾃⽂章《Supervised Hashing with Kernels》，从⽂章名字就可以⼤概了解到，这篇论⽂提出了⼀种基于监督学习和核的Hash算法。利⽤kernel主要是为了解决线性不可分问题，监督学习则是为了学习到更discriminative的hash value,使得我们可以直接使⽤hash后的value作为特征，⼤⼤降低特征维数。（1） hash函数的⽣成　　　 该算法⾸先随机选取了M个样本（anchor）,之后构造了如下式的prediction函数：

　　上式中，k代表核函数(论⽂选择了⾼斯径向基kernel),得到f(x)后，哈希函数h(x) = sgn(f(x)) 。上式中参数主要是a(b可以化解掉)，也是监督学习的⽬标；

注意，上式只⽣成了⼀个bit的hash value,若⽣成r bit 特征，那么就需要训练r次，⽣成r组a参数（论⽂中逐bit⽣成参数a）。(2) ⽬标函数　　 在训练中，⽂章选择的⽬标函数是在汉明空间，最⼤化类间距离、最⼩化累内距离。但是在实现⽅式上，由于汉明距离数学表达上的不⽅便，采⽤了code inner products的⽅式来计算汉明距离：

（3）优化算法　　 由于不同bit hash函数是相互独⽴的，且总得代价函数值是有每⼀bit代价函数值相加得来的，因此如果我们使每⼀bit的代价函数取得最⼩值，那么就可以得到总得最优解；论⽂中采⽤贪婪算法，逐位采⽤梯度下降求解最优解。KSH与原始LSH算法的区别　　 个⼈理解KSH与原始LSH算法不同主要在于以下⼏个⽅⾯：

　　1. 哈希函数⽣成⽅式的区别

　　 原始LSH（汉明空间）的哈希函数为随机选取bit，使得在汉明空间距离近的特征，哈希后，在同⼀个桶的可能性很⼤；

　　　⽽KSH采⽤监督学习的⽅式⽣成hash函数（hash函数的整体框架算法给出，通过监督学习来学习其中的参数a）；

　　2. 哈希⽣成value的区别

　　　原始LSH算法对特征hash后，⽣成⼀串⼆进制数字，这串⼆进制数再进⾏⼆次哈希，映射到⼀个个bucket⾥；KSH算法哈希产⽣nbit的码，这串码直接可以作为原始特征的新特征（维度更低）。

　　3. 特征索引⽅式的差别

　　　原始LSH采⽤的hash函数可以将距离近的特征投射到同⼀bucket,检索时，先确定query位于哪个bucket，之后在桶内暴⼒⽐较（⽐较原始特征）；KSH算法由于采⽤监督学习的⽅式，其哈希函数产⽣的value区分性好且较短，因此，可以直接暴⼒搜索；新的哈希算法　　　KSH是2012年CVPR的⼀篇⽂章，距离今天短短三年，但是由于在 large scale中进⾏图像检索应⽤越来越⼴，哈希技术的发展也⽇新⽉异，KSH也慢慢成为了各种算法的背景。。。哈哈。当然，提起⼈⼯智能近⼏年的发展，深度学习功不可没，因此利⽤深度学习提取图像特征，进⽽hash的end to end ⽅法也出现了，效果也很不错。