深度学习推荐系统实战_16_12_局部敏感哈希如何在常数时间内搜索Embedding最近邻
你好，我是王哲。
在深度学习推荐系统中，我们经常采用embedding召回这一准确又便捷的方法。
但是在面对百万甚至更高量级的候选集的时候，线性的逐一计算，embedding间的相似度往往会造成极大的服务延迟。
这个时候我们要解决的问题是怎么快速找到与一个embedding最相似的另一个embedding呢？这直接决定了召回层的执行速度，进而会影响服务器的响应延迟。
那今天我们就一起来学习一下业界解决近似embedding搜索的主要方法。
局部敏感哈希。
在深度学习推荐系统中，我们经常会使用embedding方法，对物品和用户进行向量化。
在训练物品和用户embedding池。
如果他们的embedding在同一个向量空间内，我们就可以通过内积余弦、欧式距离等相似度计算的方法计算它们之间的相似度，从而通过用户物品相似度进行个性化推荐，或者通过物品和物品之间的相似度，进行相似物品的查找。
那假设用户和物品的embedding都在一个k维的embedding空间中，物品的总数为n那遍历计算一个用户和所有物品向量相似度的时间复杂度是多少呢？那不断算出这个复杂度是k乘严。
那虽然这一复杂度是线性的，但物品总数n达到百万甚至千万量级时，线性的时间复杂度也是线上服务不能承受之重。
那换一个角度思考这个问题，由于用户和物品的embedding同处在一个向量空间内，因此召回与用户向量最相似的物品embedding.这个问题其实就是在向量空间内搜索最近邻的过程。
如果我们能够找到在高维空间内快速搜索最近邻的方法，那相似embedding的快速搜索问题也就迎刃而解了。
那遇到最近您搜索的问题，我想大部分同学直觉上肯定会想到两种解决方案，一种是聚类，他把相似的点聚类到一起，不就可以快速的找到彼此间的最近邻了吗？那另一种是索引，比如通过某种数据结构，建立起基于向量距离的索引。
那在查找最近邻的时候，通过索引快速缩小范围来降低复杂度。
这两种想法可不可行呢？那我们一一来尝试一下。
那对于聚类问题，我想最经典的算法当属k means.它完成聚类的过程主要有四个步骤，第一步是随机指定cake中心点。
第二步，让每个中心点代表一个分类，把所有的点按照距离的远近指定给距离最近的中心点代表的类。
第三步是计算每个类包含点的平均值作为新的中心点位置。
第四步是确定好新的中心点位置后，迭代进入第二步，直到中心点的位置收敛不再移动。
那整个k means的迭代过程就完成了它的更新过程。
我列在了文稿中的图二，大家可以看一下它的更新的例子。
那如果我们能够在离线利用k means计算好每个embedding向量的类别，在线上，我们只需要在同一个类别内的embedding向量内搜索就可以了，就会大大的缩小embedding的搜索范围，时间复杂度自然就下降了。
但是这个过程还存在一些边界的情况，所如聚类边缘的点的最近邻往往会包括相邻聚类的点。
那如果只在类别内搜索，就会遗漏掉这些近似点。
那此外，中心点的数量k也不那么好确定k选择太大，离线搜索的过程就会非常慢。
K选的太小，离线搜索的范围还是很大，并没有减少太多搜索的时间。
所以其余聚类的搜索还是有一定的局限性的。
解决这个问题，也会增加过多的冗余过程，得不偿失。
那既然聚类有局限性，那索引能不能奏效呢？我们这里可以尝试一下经典的向量空间索引方法。
Kd tree.那与聚类不同，它是为空间中的点，或者向量建立一个索引。
这该怎么理解呢？举个例子，你可以参考文稿中的点云图，我们先用红色的线，把点云一分为二，再用深蓝色的线把各自片区的点云一分为二，以此类推，直到每个片区只剩下一个点，这就完成了空间索引的构建。
如果我们能够把这套索引搬到线上，就可以利用二叉树的结构快速找到相邻点。
比如希望找到点q的m个相邻点，就可以先搜索它相邻子数下的点。
如果数量不够，可以向上回退一个层级搜索它负片区下的其他点，直到数量回够m个为止啊。
听上去KD tree索引似乎是完美的方案，但其实它还是无法完全解决边缘点最近邻的问题。
比如对于点q来说，它的邻界片区是右上角的片区，但它的最近邻却是深蓝色切分线下方的那个点。
所以，按照KD tree的索引方法，我们还是会遗漏掉最近邻点，它只能保证快速搜索到近似的最近邻点集合。
而且KD tree索引的结构并不简单，离线和在线维护的过程也相对复杂，这些都是它的弊端。
那有没有更完美的解决方法呢？为了拯救我们的推荐系统，召回层那局部敏感哈希这方法横空出世，它用简洁而高效的方法，几乎完美的解决了这一问题。
那他是怎么做到的呢？我们先来看看局部敏感哈希的基本原理。
那局部敏感哈希的基本思想是希望让相邻的点落入同一个桶。
这样再进行最近邻搜索的时候，我们只需要在一个桶内或者相邻的几个桶内的元素中进行搜索就可以了。
那如果保持每个桶中的元素个数在一个常数附近，我们就可以把最近邻搜索的时间复杂度降低到常数级别。
那怎么构建局部敏感哈希中的桶呢？接下来，我们以基于欧式距离的最近邻搜索为例，来解释构建局部敏感哈希桶的过程。
首先，我们必须要弄清楚一个问题，如果将高维空间中的点向低维空间进行映射，它的欧式相对距离是不是保持不变呢？那以文稿中的图四为例图，四中的中间的彩色的点处在二维空间中。
当我们把二维空间中的点，通过不同角度映射到ABC这三个一维空间时，可以看到原本相近的点在一维空间中都保持着相近的距离。
而原本远离的绿色点和红色点在一维空间a中处于接近的位置，却在空间b中处于远离的位置。
因此，我们可以得出一个定性的结论，欧式空间中将高维空间的点映射到低维空间，原本接近的点在低维空间中肯定依然接近，但原本远离的点则有一定概率变成接近的点。
那利用低维空间可以保留高维空间相近距离关系的性质，我们就可以构建局部敏感哈希的桶。
那么对于embedding项来说，由于embedding大量使用内积操作、计算相似度，因此我们也可以用内积操作来构建局部敏感哈希统。
具体的公式就是假设v是高维空间中的k k为embedding向量，x是随机生成的k为映射向量。
那我们利用内积操作，可以将v映射到一维空间得到数值HV,它其实就是v和x的内积。
而且我们刚刚说了一一维空间会部分保存高维空间的近似距离信息。
因此我们可以利用哈希函数HV进行分桶公式，就是x乘以v加b除以w那其中w是分桶的宽度，b是零到w间的一个均匀分布的随机变量，它是为了避免分桶边界的固化，呃，不过映射操作会损失部分的距离信息。
如果我们仅采用一个哈希函数进行分桶，而然存在相近点误判的情况。
因此我们可以采用m个哈希函数同时进行分桶。
如果两个点同时调进了m个桶，那它们是相似点的概率就会大大增加。
通过分桶找到相似点的候选集构后，我们就可以在有限的候选集合中，通过遍历找到目标点真正的k近邻了。
刚才我们讲的哈希策略是基于内积操作来制定的，内积相似度也是我们经常使用的相似度度量方法。
那事实上距离的定义有很多种，比如曼哈顿距离、切皮、雪夫距离、汉明距离等等。
那针对不同的距离定义，分桶函数的定义也有所不同，但局部敏感哈希通过分桶方式保留部分距离信息，大规模降低近邻点候选集的本质思想是通用的。
好，刚才我们讲到了可以使用多个分桶函数的方式来增加找到相似点的概率。
那你可能会有疑问，如果用多个分桶函数的话，我们该怎么处理不同桶之间的关系呢？这就涉及到局部敏感哈希的多种策略。
那这里我们举一个例子，假设有ABCDE五个点，有h一和h二两个分桶函数。
那使用h一来分桶的时候，a和b掉到了一个桶里，CDE调到了另一个桶里。
那使用h二来分桶的时候，ACD调到了一个桶里，b和e掉到了另一个桶里。
如果我们想找到点c的最近邻点，应该怎么利用两个分桶的结果来计算呢？事实上主要有两种操作方法，分别是且和或操作。
如果我们用且操作来处理两个分桶结果之间的关系，那结果是这样的，找到与点c在h一函数下同一个桶的点，且在h二函数下同一个桶的点作为最近邻的候选点。
那满足条件的点只有一个，就是点d我们也就可以说点d是最有可能成为点c的最近邻点的候选点。
所以说，用且操作作为多桶策略，可以最大程度的减少候选点数量。
但由于哈希分同函数不是一个绝对精确的操作点，d也只可能是它的最近邻点的候选点，却不一定是最近邻点，因此且操作其实也大大增加了漏掉最近邻点的概率。
那如果我们用或操作作为多桶策略呢，也就是找到与点c在h一函数下同一个桶的点，或者在h二函数下同一个同的点。
这个时候候选集中会有三个点ADE,我们增大了候选集的规模，减少了漏掉最近邻点的可能性，但增大了后续计算的开销。
当然，局部敏感哈希的多种策略还可以更加的复杂，比如使用三个分度函数进行分桶，同时落入两个同的点。
作为最近邻候选点等等，到底是选择且操作还是或操作，以及到底选择使用几个分桶函数，每个分度函数分几个桶，这还是一个工程上的权衡问题。
我虽然不能给出具体的最佳数值，但会给你一些取值的建议。
第一条点数越多，我们越应该增加每个分桶函数中桶的个数，相反点数越少，越应该减少桶的个数。
第二条embedding向量的维度越大，我们越应该增加哈希函数的数量，尽量采用且的方式作为多桶策略。
相反，embedding向量的维度越小越应该减少哈希函数的数量，多采用或的方式作为分桶策略。
最后，我们再回头来解决课程开头提出的问题。
局部敏感哈希能在常数时间内得到最近邻的结果吗？如果我们能够精确的控制，每个桶内点的规模是c假设每个imabegding的维度是n那找到最近邻点的时间开销将永远在c乘以n的量级。
采用多桶策略后，假设分桶函数数量是k那么时间开销也在k乘以c乘以n的量级仍然是一个常数。
现在我们已经知道了局部敏感哈希的基本原理和多桶策略，接下来我们一起进入实践的环节，利用spark reaces训练好的物品，embedding来实现局部敏感哈希的快速搜索吧。
为了保证跟embedding部分的平台统一，这一次我们继续使用spark ML leap完成局部敏感哈希，也就是LOSH的实现。
为了证影embedding数据转换成dance factor的形式之后，我们使用spark ML lip自带的IOS分桶模型来进行分桶。
其中最关键的部分是设定LSS模型中的bucket lines和number hush、 tables这两个参数。
那bucket lines指的就是公式，二中的分桶宽度。
W number、 hush、 tables指的是多桶策略中的分桶次数。
那清楚了模型中的关键参数执行的过程，就跟我们讲过的其他spark MLL模型一样了。
都是先调用fit函数训练模型，再调用transform函数，完成分桶的过程。
具体的实践你可以参考文稿中的代码好了，帮助你更加直观的看到分桶操作的效果。
我把使用IOS模型对电影embedding进行分桶得到的五个结果打印了出来。
结合文稿中的示例，你可以看到bucki ID这一列。
好了，我们之前设置了number hush, tables参数为三。
所以每一个embedding对应了三个bucket ID.在实际的最近您搜索过程中，我们就可以一用刚才讲的多统策略进行搜索了。
实实上在一些超大规模的最近搜索问题中，所以分统的策略还能进一步的复杂。
如果你有兴趣深入学习，我推荐你去了解一下facebook的开源向量。
最近您搜索库face,这是一个在业界广泛应用的开源解决方案。
好了，今天的重点内容讲完了，我们一起来做个小结。
那这节课我们一起解决了embedding最近邻搜索的问题。
事实上，对于推荐系统来说，我们可以把召回最相似物品embedding的问题看成在高维的向量空间内搜索。
最近邻的过程遇到最近邻搜索的问题，我们一般会采用聚类和索引两种方法，但是聚类和索引都无法完全解决边缘点。
最近邻的问题，而且对于聚类来说，中心点的索量k也并不好确定。
对于KD tree索引来说，KD tree索引的结构并不简单，离线和在线维护的过程也相对复杂。
因此，解决最近邻问题，最完美的办法就是使用局部名卡西。
在每个同类点的数量接近时，它能够把最近邻查找的时间控制在常数级别。
为了进一步提高最近邻搜索的效率或召回率，我们还可以采用多种策略，基于且操作的多重策略，能够进一步减小候选机规模，增加计算效率。
基于或操作的多重策略，则能够提高召回率，减少漏掉最近邻点的可能性。
啊，最后我把各种方法的优缺点列了出来，放在了文稿中，希望能帮你做一个快速的复盘。
结合今天的内容，我们来解决一道思考题。
如果让你在推荐服务器内部的召回层，实现最近邻搜索过程，你会怎样存储和使用我们在离线生成的分组数据，以及怎样设计线上的搜索过程呢？欢迎你在留言区写出你的答案。
更欢迎你把这一过程的实现提交per request到spell request项目中。
如果能够被采纳，你将成为这一开源项目的贡献者之一。
好了，我们下节课见。