欢迎光临 x-algo
关注算法在工业界应用
Hi, 这是一个关注大数据算法在工业界应用的网站

Wand算法

Wand(weak and)算法有些年头了,最近要做基于文章的推荐,需要根据当前文章推荐出Top K个最相似的文章。一种直观的想法是对当前文章提取关键词,将关键词和其权重看做是检索的Query,对候选文章(百万量级)进行毫秒级的实时检索。

搜索的困境

一般的建立「倒排索引」的步骤为:

  1. 分词
  2. 去停用词/提取关键词
  3. 根据词建立倒排(如果倒排太长过长可能需要截断)
  4. 根据一定的规则对倒排队列预先排序(比如按照时间、doc质量分)

经过上面步骤,我们就可以得到一个「倒排表」,其中key是词,value是doc列表。如下:

对于某一次查询,如果Query中的词对应的倒排队列长度比较短,就可以计算每一个文档的得分,然后综合排序即可。但是如果队列特别长,全部计算一遍性能不允许,这时就面临一个性能的困境。比较笨的方法是我放弃全局最优解(损失召回),通过抽样、规则进行剪枝,只计算其中一部分,从而得到「次优」的结果。

wand算法也是一种「剪枝」的算法,但是召回率要远远高于普通的规则、抽样方法。在一些场景下,可以实现召回0损失。

Wand(Weak AND)算法

算法的输入是n个倒排队列,输出是topK个得分最高的doc。算法分为下面几步:

对每个队列的doc按照id排序

每一个doc都有一个唯一的id,同一个doc是会出现在多个队列中(比如这个doc包含多个query中的词),每个队列按照doc的id升序排列。这一个操作看起来有一些无厘头,看完算法就会明白为什么必须这么操作了。排序完成之后,队列格式为:

确定每个队列的得分上限

对某个 \(doc_j\) 来说,他的算分公式有很多种方法,我们这里为了讨论问题方便,选择一种简单的计算方法。假设得分只和query有关,例如query中有n个词,第i个词记为 \(key_i\) ,每个词有其对应的得分权重 \(s_i\)\(doc\) 的算分公式为:

\(score(doc_j)=\sum_{key_i \in doc_j}{s_i}\)

那么,队列 \(i\) 的得分是固定的,所以队列 \(i\) 的得分上限为:

\(UP_i=s_i\)

这里费劲定义上限得分的目,是为了后面方便进行剪枝。

比如我们先随机挑选了k个doc,并计算了他们的得分,最高分和最低分的doc分别为 \(doc_{hight},doc_{low}\) ,接下来想要从候选队列中找到新的 \(doc_{new}\) ,用来替换最低分 \(doc_{low}\) 。那么问题就来了,如果找到这个合适的 \(doc_{new}\) ,下面开始介绍优化的方法。

容易想到的优化方法

最笨的获取合适的 \(doc_{new}\) 的方法,就是把剩余的doc都计算得分,然后和 \(doc_{low}\) 对比,如果得分比 \(doc_{low}\) 高,就进行替换。这种方法没有问题,就是慢啊!

聪明如你可能又想到了一种方法,类似快排partition可以做到O(n)的复杂度求topK大数字的算法。这个方法的问题在于需要算出所有doc的得分,计算每一个doc的得分的复杂度是词的个数,接下来介绍的剪枝方法不需要计算每一个doc的得分,只需要计算得分有可能打败 \(doc_{low}\)\(doc\) 的得分

还有就是多路归并的方法,核心问题也是需要计算每一个文档的得分。

Wand剪枝算法

选择id最小的k个doc作为初始doc,并计算得分,并按照得分排序,作为初始候选集。

从队列剩余doc中选择得分有可能打败 \(doc_{low}\) 且id最小的 \(doc_{new}\)\(doc_{new}\) 如果得分大于 \(doc_{low}\) ,就需要其上限得分必然满足:

\(UPscore(doc_{new})=\sum_{key_i \in doc_{new}}{UP_i} \ge score(doc_{low})\)

 

所以只需要计算UPscore满足条件的doc即可,下面的伪代码就设计了一种算法,可以实现不漏掉任何一个满足UPscore条件的doc,并且得到每一个候选doc的时候是按照其id从小到大的顺序。

所以整个算法可以表述为,对每个队列按照当前搜索到的id升序排列,从第0个队列开始寻找UP得分之和大于 \(doc_{low}\) 的位置,记为pivot,记最大的id为 \(id_{max}\) 。如果前pivot个队列当前搜索到的id全部相等,此id就为候选id,同时将第pivot个队列的搜索id后移一个;如果前pivot个队列当前搜索到的id不全相等,找到一个id小于 \(id_{max}\) 的队列,将其搜索id变为当前队列中第一个大于等于 \(id_{max}\) 的id

上面的一段描述看不明白也没有问题,我已经尽可能简单的描述了,下面为论文中的伪代码:

初看这个函数,瞬间就懵逼的感觉,下面介绍每个变量和函数的意义,反复多看几遍应该就可以理解了。

  • 参数 \(\theta\) 就是每次迭代的的阈值,即 \(doc_{low}\) 的得分。
  • items是query分词之后的key,每一个key对应一个倒排队列。
  • posting存储的是每个队列当前搜索到的id(队列中doc的id都是按照生序排列的)
  • sort(items,posting)表示将将队列按照当前搜索到的id从小到大排序
  •  findPivotTerm(terms,θ)表示从编号0到 \(len(items)\) 中,找到第一个队列 \(i\) ,可以满足: \(\sum_{0 \le i < len(items)}{UP_i}>= \theta = doc_{low}\)
  • pickTerm(terms[0..pTerm])选择需要进行后移的队列,就是这个队列当前的id比较小,需要后移才可能找到合适的id。
  • aterm.iterator.next(pivot)表示当前队列,移动到第一个大于等于pivot的位置。
  • 当21行的判断为true的时候,说明找到了一个候选的doc,items[0:pTerm]的队列id相等
  • 当25行判断成立的时候,并不是将items[0:pTerm]中每一个队列都执行后移,之所以不每一个后移是为了更好的剪枝,例如挑选一个idf值最大的后移有更大的概率提升移动到一个id更大的值。

堆优化

算法的过程中有两个地方可以用到堆,一个是求阈值 \(doc_{low}\) 的堆。另外一个是执行pickTerm的过程如何快速找到UP最大的队列,每一次对items的排序其实只有一个元素变动,可以看成是一次swap(item_i,item_j)。这里会有两种情况:

  • 如果swap范围没有超越pTerm,堆只进行弹出即可,因为下一次执行findPivotTerm返回值是不变的。
  • 如果swap范围超越pTerm,pTerm的值可能还是不变(最优一个UP很大),这时还是不用处理。如果pTerm发生变化了,就需要将当前pTerm加入到堆中作为可以执行iteration的候选。

 

阈值 \(\theta\) 的选择

阈值的选择是「执行效率」和「准确性」的tradeoff, 当允许的检索时间太短,就可以通过调高阈值(例如选择阈值为 \((doc_{low} + doc_{hight})/2\) ),从而加快执行效率。

 

\(UP_i\) 的选择

表面上来看,选择一个「正确」的上限值不是困难的事情,可以证明只要「正确」,我们都不会漏掉任何一个doc。但是现实是,我们可以允许漏掉一些高分的doc,不奢望「全局最优解」,只需要得到的结果不要太偏离「全局最优解」就可以了。

通过迭代公式可以看出来,如果UP值「估高」不会对结果有影响,只会计算复杂度多了一些,例如极端情况下每个队列的UP值都是无穷大,那么每一个doc都可以作为候选进行计算,就会导致很多次更新 \(doc_{low}\) 失败。如果UP值「估低」,可以加快计算速度,因为符合要求的pivot值会变大,更多的队列参与到了计算候选之中,基本可以成为候选的doc的得分都可以击败 \(doc_{low}\) 。所以,如果想要加快执行速度,也可以调低每一个队列的UP值。

 

原始论文

未经允许不得转载:大数据算法 » Wand算法

分享到:更多 ()

评论 抢沙发

*

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注大数据算法在工业界应用

本站的GitHub关于本站