推荐算法学习（十五）：Learning to Rank

发表于 | 分类于

待完成

网站在提供推荐服务时，一般是给用户一个个性化的推荐列表，这种推荐叫做TopN推荐。在TopN推荐中，我们面对和需要处理的数据往往是海量高维的，怎样快速地从海量高维数据集合中找到与某个数据最相似的一个数据或多个数据成为了一个难点和问题。如果是低维的小数据集，我们通过线性查找就可以容易解决；但如果是对一个海量的高维数据集采用线性查找匹配的话，会非常耗时，因此，需要采用一些类似索引的技术来加快查找过程，通常这类技术称为最近邻查找（Nearest Neighbor,NN），当处理大规模数据时，还可采用近似最近邻查找（Approximate Nearest Neighbor, ANN）。而局部敏感哈希（Locality-Sensitive Hashing，LSH）是ANN中的一类方法。

LSH算法

Hash

主要的索引技术有：基于树的索引技术（二叉树，B-Tree,B+Tree）、基于哈希的索引技术以及基于词的倒排索引。面对海量数据的检索，Hash是一种重要的索引技术。

Hash一般翻译做“散列”，就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出。通俗的说Hash就是找到一种数据内容和数据存放地址之间的映射关系（ f : key —> address）。

LSH

传统的哈希表用于检索数据，无法将相似的数据放到同一个Bucket中，比如h=x mod w； LSH将相邻的数据，通过映射后依然保持相邻的关系，即保持局部的敏感度Locality-Sensitive。

0

LSH通过Hash Function，每个Bucket会落入一些原始数据，属于同一个桶内的数据有很大可能是相邻的（也存在不相邻的数据被hash到了同一个桶内），将原始数据集合分成了多个子集合，每个子集合中的数据大概率是相邻的，而且子集合中的元素个数较少。这样可在一个很小的集合里查找相邻元素，实现快速近邻查找。

MinHash算法

TopN推荐中一个最基本的问题就是比较两个文档的相似度。文档中任意长度为k的字符串称为k-shingle，也称为k-gram。将每篇文档可以表示成文档中出现一次或者多次的k-shingle的集合。如果两个文档相似，那么他们会有很多的shingles也是相同的。一般文本越长，K取值越大，K的经验值参考——短文本K=5，长文本K=10。可用下图所示的0-1矩阵来描述待计算相似度的文档（shingle的顺序是随机的）。

0

一般文档相似程度计算可采用Jaccard相似度：0

当面对海量高维的文档数据时，0-1矩阵会变得非常大，传统方法十分耗时，需要找到一个Hash函数，将原来的Jaccard相似度计算，等同于降维后的相似度矩阵计算（ Input Matrix => Signature Matrix），即原来文档的Jaccard相似度高，那么它们的hash值相同的概率高，原来文档的Jaccard相似度低，那么它们的hash值不相同的概率高。针对Jaccard相似度的为MinHashing(最小哈希)。

0

MinHash值是特征矩阵按行进行随机排列后，第一个列值为1的行的行号。例如下图中，h(C1)=2，h(C2)=1，h(C3)=1，h(C4)=3。

0

两个文档MinHash值相同的概率能否用来估计它们的Jaccard相似度呢？接下来探讨上图中Ci与Cj的MinHash相等的概率P(h(Ci)=h(Cj))，与Ci,Cj Jaccard相似度的关系。对于Ci,Cj，对应行有三种可能：A类，两列的值都为1；B类，其中一列的值为0，另一列的值为1；C类，两列的值都为0。C类行对于结果计算没有影响，可以删除，另外矩阵行是随机排列的，因此，P(h(Ci)=h(Cj))=P(删掉C类后，第一行为A类)=A类行的个数/所有行的个数=a/(a+b)，即P(h(Ci)=h(Cj))= sim(Ci,Cj)。也就是说，用Ci，Cj的MinHash值相等的概率对它们的Jaccard相似度进行估计是合理的。

MinHash算法主要步骤：（1）分别经过3次随机置换（红、黄、蓝）；（2）每次置换后，采用MinHash得到Signature；（3）使用Sig矩阵相似度用来近似估计原始矩阵Input Matrix的Jaccard相似度。

0

MinHash执行：如何对海量数据进行排序 => 存储空间，计算时间=> 有多个hash函数,通过hash(i)得到最新的行号，如果此时列上第i行的元素为1，而且新行号比原来记录的M值小，那么更新M值（打擂法：只保留最小行号，一直更新即可，不用保存n个变换后的矩阵）。

对于hash函数，h(x)= x mod 5，g(x)=(2x+1) mod 5：

  1. 行数+1（即第0行置换到h(1)和g(1)行），每次进行h和g函数运算

  2. 如果列上的值为1，那么查看Hash得到的数值是否更小，更小则更新

  3. 通过m个针对row index的Hash函数，完成m次行向量的置换（解决了行向量置换的问题）

    0

MinHash+LSH

除了要解决Ci和Cj两两之间相似度的计算问题，当数据量大（>100万）的时候，两两之间相似度计算次数为${c_N^2}$,计算量非常大。为了解决这一问题，将可能相似的用户以较大概率分到同一个桶内，这样每一个用户的“相似用户候选集”就会少很多，大大降低计算复杂度。LSH是相似度的近似求解方式，在MinHash基础上，将Signature向量分成多段(band)，主要步骤：

  1. 将Signiture矩阵分成b组，每组由r行组成

  2. 对每一组进行hash，各个组设置不同的桶空间。只要两列有一组的MinHash相同，那么这两列就会hash到同一个桶而成为候选相似项

00

假设对于某行，两列Signature值相同的概率为s（两列的相似度），在某个band，值都相等的概率是$s^r$，在某个band，值不相同的概率是$1-s^r$，两个文档存在b个band，这b个band都不相同的概率是$(1-s^r)^b$，b个band里，至少有一个相同的概率是$1-(1-s^r)^b$=> 两列成为候选相似对的概率是$1-(1-s^r)^b$。称之为And then OR方法，先要求每个band的所有对应元素必须都相同，再要求多个band中至少有一个相同。符合这两条，才能发生hash碰撞。下图为b=20, r=5时的概率表。

0

当s超过某个阈值后，两个用户成为candidate用户的概率会迅速增加并接近于1。这个阈值，也就是概率变化最陡的地方，近似为0.

在LSH算法使用过程中，我们需要确定：（1）Smin，相似用户的阈值定义（近邻定义）；（2）Signature向量的长度，降到k维embedding。针对b和r的取值，我们需要考虑：（1）如果想要尽可能少的出现false negative，需要选择b和r使得概率变化最陡的地方小于Smin（比如s在0.5以上才属于相似用户，选择b和r使得S曲线的最陡处小于0.5）；（2）如果想要保证计算速度较快，并且尽可能少出现false positive，那么最好选择b和r使得概率变化最陡的地方较大（比如b=20，r=6）这样，s较小的两个用户就很难成为candidate用户，但同时也会有一些“潜在”的相似用户不会被划分到同一个桶内

MinHash+LSH总结

  • Minhash=>针对高维数据=>编码：特征降维，且保持Jaccard相似度=>Signature矩阵

  • LSH=>针对大规模数据,两两之间相似度计算次数太多=>分桶：数据规模N的“降维”，减少查找范围

LSH的一般定义

Locality-Sensitive Hashing是满足一定条件的Hash函数簇。

令d1<d2是定义在距离测定d下得两个距离值，如果一个函数簇的每一个函数f满足：

  • 如果d(x,y)<=d1,则f(x)=f(y)的概率至少为p1，即P(f(x)=f(y)) >= p1

  • 如果d(x,y)>=d2,则f(x)=f(y)的概率至多为p2，即p(f(x)=f(y)) <= p2

那么称F为(d1,d2,p1,p2)-sensitive的函数簇。

0

Jaccard相似性对应的LSH为MinHash是(d1,d2,1-d1,1-d2)-sensitive。

SimHash算法

汉明（Hamming）距离是指两个二进制串中不同位的数量。比如10001001和10110001，有3位不同，因此汉明距离=3。向量相似度越高，对应的汉明距离越小。在图片的识别中，汉明距离在0-10之间认为是相似的，采用汉明距离计算相似度可以大幅提升效率。

SimHash算法是LSH局部敏感哈希的一种。Google就是采用SimHash算法进行网页查重。

SimHash算法=>文档指纹=>计算文档间汉明距离：

  1. 设置SimHash的位数，比如32位，需要综合考虑存储成本以及数据集的大小

  2. 初始化SimHash，将各位初始化为0

  3. 提取文本中的特征，比如采用2-Shingles，”the cat sat on the mat”=>{“th”, “he”, “e “, “ c”, “ca”, “at”, “t “, “ s”, “sa”, “ o”, “on”, “n “, “ t”, “ m”, “ma”}

  4. 使用传统的hash函数计算各个word的hashcode，比如：”th”.hash = -502157718 ，”he”.hash = -369049682，……

  5. 对各word的hashcode的每一位，如果该位为1，则simhash相应位的值加它的权重（通常是出现的频率），否则减它的权重

  6. 计算最后得到的32位的SimHash，如果该位大于1，则设为1；否则设为0

  7. 通过SimHash算法得到每篇文档的指纹（fingerprint），计算两个文档指纹的海明距离，通常2篇文档的Hamming距离在3以内，就认为相似度比较高，即两篇文档基本相同

    0

如何通过SimHash进行相似文档的检索呢？假设我们有10亿文档(2^34)，每来一个新文本我们都需要做10亿次的汉明距离计算，计算量太大。假设SimHash签名为64位，我们认为两个文档SimHash的Hamming距离在3以内就是相似的。通过抽屉原理，如果K=3，那么可以将SimHash分成 K+1=4段，如果两个SimHash的Hamming距离为3，那么至少有一段（16位）的SimHash是相同的。采用索引的方式进行查找加速，取出每一段相同的候选文本。文档库中有2^34个签名，那么匹配上每个段的结果最多有2^(34-16)=262144个候选结果，四个段返回的结果总数=4*262144（大概100万）。原本需要比较10亿次 => 现在只需要比较100万次了，即在100万个候选结果中进行比较。

0

0

总结

  • MinHash适用于集合表示，或者0-1数据类型（one-hot词向量）的降维与近邻查找
  • SimHash适合长文本

相关工具

  • LSH算法工具
    1. datasketch，海量数据相似查找Python工具，支持多种统计方式，对常见的统计需求，在精确度，存储成本，计算成本之间进行了折衷，对每一个计算元素只接触一次的情况下，得到精度相当高的统计结果
    2. SimHash，https://github.com/leonsim/simhash,Python实现的SimHash，可以得到某个文本的SimHash，以及SimHash距离

实例：使用MinHashLSHForest对微博新闻句子进行检索

  • 数据集：weibo.txt
  • 处理文本（以。！？作为分隔符，去掉\n换行符号）；设置停用词，将句子进行分词；使用datasketch工具中的MinHashLSHForest()训练模型（训练数据载入LSHForest系统）； 针对某句话进行检索，查找Top-3相似的句子

代码：https://github.com/Alice1214/RS/tree/master/RS09/MinHashLSHForest-weibo