首页 > 人工智能 > Google 的大规模稀疏数据相似对查找算法

Google 的大规模稀疏数据相似对查找算法

 

在大量数据中找出相似的数据,是一个常见的问题。最Naive的算法需要数据量的平方级别的计算时间,这在百万以上数据量上是不可忍受的。在实际应用中没有最佳解法,需要根据数据情况设计合适的算法。Google的“Scaling Up All Pairs Similarity Search”这篇论文适用于千万量级以上,上千万维度的稀疏数据聚类,在工程层面将算法进行了高度优化。该论文发表于2007年,引用数超过400。

相似度定义为两向量的余弦夹角,本文假设所有向量已被归一化,在这种情况下,相似度等于向量的内积,即:

sim(x,y) = dot(x,y) = ∑ix[i]⋅y[i]

算法的任务是从向量集合中,找出相似度大于阈值t的向量对。找出这样的向量对,就可以通过寻找连通图的办法,将向量聚类为按连通部分定义的cluster。

该论文解决此问题使用搜索引擎算法,即对每个维度建立倒排表,用向量x做为query去查找与它相似的其他向量。并利用阈值t对算法进行了高度的工程优化,使算法的性能相比于最平凡的搜索算法,提升了两个数量级以上。该文主要在以下这些方面对算法进行优化:

  1. 由于相似是对称的,对于对称的向量对(x,y)和(y,x),相似度只计算一次;
  2. 不建立完整的倒排表,最简单的算法需要将一个向量挂到它所有不为0的维度对应的倒排表上,优化后,只需要挂到其中一部分倒排表上;
  3. 利用基于hash的方法计算相似度,充分利用阈值t,达不到阈值的就不再计算。

下面先将基本的算法给出,然后再给出逐步优化的步骤。

算法ALL-PAIRS-0:遍历所有向量,从倒排表查找与它相似的向量,并动态建立倒排表;
输入:所有向量集合V,相似度阈值t;
输出:所有相似对集合O

算法ALL-PAIRS-0:
1 O = Φ
2 I1,...,Im = Φ  // Ij为第j个维度上的倒排表,m为维度数量
3 对所有x ∈ V:
4     O = O ∪ FIND-MATCHES-0(x,I1,...,Im,t)
5     对所有x[i]>0的i: 
6         Ii = Ii ∪ {(x,x[i])}  // 对向量x的字段i,建入倒排索引
7 return O

算法FIND-MATCHES-0:对一给定向量,在倒排表中查找与它相似的向量;
输入:向量x,倒排表I1,…,Im,相似度阈值t
输出:与x相似的向量集合M

算法FIND-MATCHES-0:
1 A = Φ  // 从向量id到相似度的map,初始化为空集
2 M = Φ
3 对所有x[i]>0的i:
4     对所有(y,y[i]) ∈ Ii5         A[y] += x[i]⋅y[i]
6 对A中所有权值>0的y:
7     如果A[y] ≥ t:
8         M = M ∪ {(x,y,A[y])}  // 将y输出为x的相似向量
9 return M

注意算法FIND-MATCHES-0计算权值时,不是一次计算一个向量的权值,而是一次计算一个维度,用hashmap保存中间结果,这避免了倒排表归并算法。算法ALL-PAIRS-0对倒排表的建立是动态的,一个向量的相似向量查找完成后,再把该向量加到倒排表中,这节省了一半的比较时间。

接下来,在ALL-PAIRS-0的基础上,对算法进行了一个关键优化:基本算法中,每个向量的每一个不为0的维度,都需要在倒排表中占据一个节点;而利用阈值t的限定,只对向量的部分不为0的维度建立倒排表节点,可以大大减少插入倒排表的节点数量,从而大大节省空间和计算时间。算法如下:

算法ALL-PAIRS-1:
1  对m个维度进行排序,该维度非0的值越多,排在越前
2  维度i在所有向量中的最大取值,记为maxweighti(V)
3  O = Φ
4  I1,...,Im = Φ
5  对所有x ∈ V:
6      O = O ∪ FIND-MATCHES-1(x,I1,...,Im,t)
7      b = 0
8      递增访问i,如果x[i]>0:
9          b += maxweighti(V)⋅x[i]
10         如果b ≥ t:
11             Ii = Ii ∪ {(x,x[i])}
12             x[i] = 0  // 向量x被索引的维度置为0,用x'来表示向量x未被索引的部分
13 return O
算法FIND-MATCHES-1:
1  A = Φ  // 从向量id到相似度的map,初始化为空集
2  M = Φ
3  对所有x[i]>0的i:
4      对所有(y,y[i]) ∈ Ii5          A[y] += x[i]⋅y[i]
6  对A中所有权值>0的y:
7          s = A[y] + dot(x,y')  // y'是向量y没有被索引的部分,下面再解释
8          如果s ≥ t:
9              M = M ∪ {(x,y,s)}
10 return M

以上算法最关键的优化在于ALL-PAIRS-1的的第7到12行。对于向量x,如果其前i个维度所贡献的相似度的最大可能值小于t,那么向量x就不在前i个维度的倒排表中建立节点。不用担心与x相似的其他向量在倒排表中找不到x。因为如果dot(x,y) ≥ t,那么必然有一个j>i,前j个维度贡献的相似度最大可能值≥t,那么j以后的维度就会建入索引。假设x建了索引的维度集合为D,没建索引的维度集合为D’,那么与x相似的向量y,必然有一个非零维度属于D,因为y与x在维度集合D’上贡献的点积是小于t的。

由于x只有部分维度建入了索引,因此需要记录一个向量x’,x’是x未建索引的维度,即x’建了索引的维度值都等于0。再引入向量x”,表示x建入索引的向量。那么,

dot(x,y) = dot(x”,y) + dot(x’,y)

这保证了算法FIND-MATCHES-1第7行的正确性。

而ALL-PAIRS-1算法第1行,对所有维度按频度从高到低排序,可以尽可能减少倒排表的长度,因为越排在前面的维度,越有可能不被建入索引,这样原本越长的倒排表,减少的节点越多。

这一步的优化让我叹为观止。通过仔细理解一个向量出现在倒排表中多处的事实,利用一个很简单但很不容易想到的策略,大大减少倒排索引的大小,从数量级上提升了性能。

接下来,进一步利用细化策略,将性能又提升了一个数量级。算法如下:

算法ALL-PAIRS-2:
1  对m个维度进行排序,该维度非0的值越多,排在越前
2  维度i在所有向量中的最大取值,记为maxweighti(V)
3  向量x的所有维度中最大的值,记为maxweight(x)
4  将V中的所有向量,按maxweight(x)降序排序
5  O = Φ
6  I1,...,Im = Φ
7  对所有x ∈ V:
8      O = O ∪ FIND-MATCHES-2(x,I1,...,Im,t)
9      b = 0
10     递增访问i,如果x[i]>0:
11         b += MIN(maxweighti(V),maxweight(x))⋅x[i]
12         如果b ≥ t:
13             Ii = Ii ∪ {(x,x[i])}
14             x[i] = 0
15 return O

以上算法的优化在于引入了每个向量的最大维度值,并将所有向量按最大维度值降序排序。由于maxweight(x)降序,所以x的维度i能贡献的权值不会超过maxweight(x)⋅x[i],由此保证了引入ALL-PAIRS-2的第11行的正确性。

算法FIND-MATCHES-2:
1  A = Φ
2  M = Φ
3  remscore = ∑x[i]⋅maxweighti(V)
4  minsize = t / maxweight(x)
5  对所有x[i]>0的i:
6      将倒排表Ii头部,|y|<minsize的(y,w)节点移除  // |y|是指向量y不为零的维度数量
7      对所有(y,y[i]) ∈ Ii8              如果A[y] > 0或者remscore ≥ t:
9                  A[y] += x[i]⋅y[i]
10     remscore -= x[i]⋅maxweighti(V)
11 对A中所有权值>0的y:
12     如果A[y]+min(|y'|,|x|).maxweight(x).maxweight(y') ≥ t:
13         s = A[y] + dot(x,y')
14         如果s ≥ t:
15             M = M ∪ {(x,y,s)}
16 return M

上面的优化在三个地方。一是引入了remscore,这是剩下的维度所能贡献的最大权值。如果对某一个向量y,已经计算的权值为0,且剩下维度所能贡献的最大权值也小于t,那么这个向量就不再需要参与计算了,从而减少需要计算实际权值的向量数量。

二是引入minsize,由于所有向量已被归一化,每个维度所能贡献的最大相似度值不大于maxweight(x),所以与x相似的向量至少需要minsize=t/maxweight(x)这么多个非零维度。由于所有向量按maxweight(x)的值降序排序,因此minsize是越来越大的,因此非零维度数量小于当前的minsize的向量,可以直接从倒排表中移除。

三是FIND-MATCHES-2的第12行,引入一个能快速计算的相似度上限,这样可以大大减少实际相似度权值的计算量。这样可以避免很多情况下对向量未索引部分的读取,在稀疏数据上,这些未索引的维度数量可能是非常大的。

从本文可以看出,Google的强大在于将算法与工程的紧密结合。只有深入钻研,才可能在那些一般人看不到的地方,似乎不可能处,发现突破口,将不可能变为现实。

最后编辑:
作者:linecong
这个作者貌似有点懒,什么都没有留下。

留下评论

你的email不会被公开。