回顾·搜索引擎算法体系简介——排序和意图篇



转载请注明 AIQ - 最专业的机器学习大数据社区  http://www.6aiq.com

AIQ 机器学习大数据 知乎专栏 点击关注

本文根据刘老师在 DataFun Talk 算法架构系列活动“人工智能典型场景算法应用解析”中所分享的《搜索引擎算法体系介绍——排序和意图篇》编辑整理而成,在未改变中心思想的基础上稍做修改。

请在 WiFi 环境下服用,土豪随意 ~~

刘老师主要讲解的是关于搜索引擎方向的一些算法应用,由于这个体系过于庞大,他这次主要集中在排序和意图识别两个方向进行介绍,希望能够对大家实际工作上有一些启发。他首先对目前主流搜索算法以及这些年大概的发展趋势进行了一个介绍,然后分享了一些搜索方面具体内容和应用,最后介绍了最近搜索算法方面比较流行的论文。以下是具体内容概括。

2010 年前用的各种各种模型偏简单,各种模型都需要自己实现,当时数据量和计算机计算量规模都较小。主要使用简单模型,如 bayes、LR、SVM、决策树等,但是效果都还可以,例如 bayes 做查询词分类能达到 80% 精度,加一些策略之后可以达到 90% 左右;10 年到 13 年间运用一些略微复杂的算法,如 bayes 网络、点击模型、随机场模型,从决策树到 Ensemble,如 GBDT/RF 都用在机器学习的排序里面,这些在公司里面发展挺快;第三阶段就是深度学习算法,如 CNN、RNN 还有 Wide in Deep 都在公司得到广泛应用;目前不管使我们的算法和数据量都有一个大的提升,提出一些新的理论,如监督学习和非监督学习,还有增强学习这种新的思路也提出来了,先前就是棋牌游戏,目前大家都在探索如何将它应用于自己的实际场景中。

接下来讲一下搜索引擎框架体系,对于搜索引擎大家都不是很陌生,简单介绍一下。划分为三个阶段:第一个阶段就是一段三行十条结果,需要找到结果必须点到对应的文章里面自己查找。这个阶段涉及到文章、查询词分析以及查询词与文章相关性、个性化、时效性的建模,这样大致能满足要求,而不需要做更细致的分析;第二个阶段,搜索引擎变得更好看了,各家都接入了自己的一个开放平台,开放平台有一些更加细节的数据,比如查阅具体线路、周杰伦各种信息。这种查询形态对于我们搜索引擎背后的算法提出了更高的要求,因为他需要去精准的定位某一个用户所需要查询的信息,这样用户就可以在搜索页上消费这条信息,而不需要发生二次点击。这样搜索引擎智能化程度就有了一定的提升,它需要去识别一条更加细致的用户需求;第三个阶段基本上就是知识图谱 + 精准问答之类的,如某某的老婆是谁,演过什么样的电影。这在智能化的道路上又迈出了新的一步,相关算法主要涉及到一些图谱实体识别、实体间的关系挖掘的算法。

前面讲的搜索引擎框架都是基于产品的,现在从开发的角度讨论下搜索引擎,分为线上和线下。线下主要就是抓取、分类、聚类、打标签,然后这种图谱的实体识别、关系挖掘等操作,数据处理完后就给线上不同模块使用。图中中层就是对应前面说的几个阶段,最上层有一个模块对所有的模块返回的结果做一个整合,最后作为一个完整搜索页返回给用户。还有如查询词分析、意图识别都是在这里面完成,各个搜索引擎都是这种结构,当前是搜狗开发框架。

然后我们从算法的角度对搜索引擎做一下分析和刻画搜索引擎的组成部分。首先就是查询分析的组成部分,如查询词提示扩展、纠错、意图识别;第二个体系文章排序体系(这也是搜索引擎最重要的一个部分),相关考核指标如下图所示,右边的六个框框就是从不同层面对查询词和 Dock 之间的建模;第三个就是文章抓取和分析,就是刚才线下所提的一整套流程。如果你对某一算法感兴趣可以查阅论文和线下探讨。

第三部分我们主要进入算法部分,主要集中于排序和意图识别两个方向。下图展示了排序和意识算法这些年的发展。

首先是查询分析这块,(1)最早使用规则和文本挖掘来分析文本是由什么关键词组成的,分门别类,然后组合成一个查询词。如果符合我们的规则和模板描述就把它当做符合我们类别的需求,这样就完成分类。线上就是文本匹配、搜索、动态规划等,线下就涉及一些关联规则挖掘、page rank 等。(2)后来会使用一些分类器,如 bayes、LR 等,这主要在覆盖面上有个大的提升,现对于词表召回高,精度可能低点。(3)第三个阶段就开始用神经网络、深度学习来做查询词分类。

文章排序方面可能涉及更多,第一条线是 LTR,首先是各种线性模型、统计相关性和决策树,在辅助人工规则(搜狗 11 年前就是这种技术)。然后就是 LTR,搜狗使用的是 lambda Mart,在 LTR 之下还有一整套特征体系(如 page rank、trust rank 来计算相关性);另外一条线就是点击模型这块,直接利用用户的点击信息,然后来进行挖掘,他把用户的浏览行为做了一些假设(如顺序浏览,点击某一条结果不满意是否可以浏览下一条结果),目的是去掉排序位置的偏置;第三条体系类似于淘宝做的个性化,目前是 LR 模型,以及其他的深度模型。

接下来主要详细介绍这两个方向,偏重于思路。首先是意图识别算法,主要基于规则挖掘,基于 Bayes、LR、SVM 等传统分类模型,基于神经网络。上图右边是相关评测指标。

    规则识别算法,我们先来看一个例子“北京高清地图”,“北京”是一个地名,表明我要查哪的实体词,“地图”是一个类别倾向的词,“北京”是中心词“高清”是可有可无的部分“地图”就是一个 pattern。这种模型可以进行扩展,如“双中心词 +pat”或“中心词 + 属性”。大家可以觉得这个算法简单,在搜狗中可以覆盖 60% 的 query,所占类别 90%,应用范围广,精度高,反应速度快,聊天机器人用的很多。具体思路:首先要一个中心词(种子)的集合,其次查询词的大集合。比如“让子弹飞”,拿到这个查询词做切分划分为不同的前后缀,然后加上实体词本身,切分的前后缀可以计算词频信息、左右熵、可信度等。经过第一次扩展就可以得到一 pat 候选集合,如导演、演员表、影评这些热门词就可以挖到,然后根据候选词再返回查询词集合做切分,又可以得到一些前后缀,经过若干次迭代得到一些扩展后的中心词列表以及 pat 表,这是二分图概念。我们再加一些可有可无词又生成一个表,类似于三分图概念。

接下来讲一下两个具体的模型,也是比较常用的,一个是 bayes,第二个就是 SVM。以 bayes 为例说明,假如查询词分类,每个 term 间是独立的,就可以对概率进行一个拆分,得到一个公式类似于一个语言模型,就是用这种一元、二元、三元的模型进行打分,结合数据选择模型。SVM 也是一种类似的用法,也是将 term 打散当做向量作为学习类别。

再来看一个 FaceBook 的 FastText 模型,这个模型只有一个隐层,下面就是各种 embedding,上面就是 softmax 输出。主要特点计算速度快,几十万的词,几十万的类别很快就能跑出来。而且 Facebook 在这方面有开源的代码,有兴趣的可以试试。模型架构有点类似 cbow 模型,只是不是用的加法而是用一个隐层,最后用了一个层次化的 softmax 对其进行加速。

接下来是一个更加深度的模型,实现方法有差异。有些人用 CNN 对查询串的依赖进行建模,也有使用 RNN,也有把两者合在一起使用。CNN 首先对查询词分词,每次词可能有一个 N 维的向量 + 二三维长度的卷积核,最后形成针对查询词一个完整的 embedding 向量,然后对这个向量加一个回归或 softmax 层的输出。而 RNN 是将 CNN 换成一个 RNN 网络,这样做的好处是可以对稍微长一点的依赖关系进行建模。所以在分类中可以依据分类文本的长度选择相应的模型。

接下来是搜索排序,其体系还是比较复杂的。从底层数据的处理和挖掘、各种标签特征提取、计算,最后在线上在顶层用各种模拟拟合,打分,最后得到最终的打分进行排序。模型改进也是这个思路。

首先介绍一个顶层的 LTR 模型,右边是搜索排序指标,上边一引擎线下的一些排序指标,主要是进行人工评测的。NDCG 整体想法就是:一个相关的文章排在越靠前,NDCG 打分越高。LTR 模型整体分为左边的三种,大多数引擎选用的是 listwise 或 pairwise,微信中 Lambda Mart 引入了 NDCG 变化因子,直接优化最终评测指标。

FM 模型是主要做顶层特征的方法,这种模型适合对各种标签 0/1 特征的融合,然后进行一个交叉,比传统的 LTR 拟合强度更好。例如计算 query 和 Title 间的一个成本,去把他们分词,然后学习他的点击,具体特征就是查询词分词后 term 还有文档 title 分词后的 term,用这些 term 对是否点击进行一个拟合。使用 FM 实现,主要是逻辑回归 + 二次项,然后用 embedding 向量做一个优化。

CDSSM 在底层用不同的模型,对我们的查询词和 Dock 进行一个编码,在往上就是计算他们的距离,最终加一个 softmax 将其变换成一个概率;跟我们的点击和标注进行拟合算一个交叉熵。具体实现有用 CNN 也有用 RNN,方法类似,只是将 embedding 层换成各种不同网络,优点是机器自动识别特征。还有一个生成查询词特征的是做查询词扩展,传统的查询词扩展就是根据一些点击情况或查询词替换情况来发现查询词间的关系来进行挖掘,得出一个词改写为另一个词的概率。一开始是通过 SMT 的方法,后才发现 NMT 而提供一个很好的平台算法。对原始查询词进行一个编码,将编码后的 Embedding 向量作为 Decode 的状态传进去,然后将其翻译成另外的词。应用思路(1)将其翻译成不同查询词不同写法,分别和 dock 算相关性,利用相关性排序。(2)直接用 Decoder 对前十条行业结果的 title 进行计算出现的概率。

另外我们可能需要去做个性化建模,我们最开始使用的是逻辑回归,然后现在也在用 WDL 模型,具体模型的思路就是结合线性模型的记忆能力和 DNN 的泛化能力,同时训练 2 组参数,达到整体模型最优。这个是网上美团点评使用 WDL 后的效果对比,AUC 大概提升了 3 个点。

Click Modle 对用于浏览行为进行建模:(1)简单点击模型,假设用户在浏览排序结果的时候是顺序浏览一旦点击这次浏览就结束,这样只能对一次点击进行建模,缺点好多数据无法处理。(2)DBN 模型允许用户浏览发生多次点击,如果用户点击后发现不满意可以继续浏览,这其实也是顺序浏览的过程,并且对用户点击满意度也进行建模。(3)UBM 允许用户跳转浏览,如从第一条跳到第三条结果,再继续浏览,可以消除用户浏览的偏置。

接下来这张图就是比较了下不同的点击模型在线下不同指标的评测情况,在附录页的论文有更详细的对比,大家可以去看一下。

下面我们看一下稍微新一点的思路和算法:(1)首先就是 Ubias LTR,大多应用在人工标注的数据里做训练。比如一条结果分为 5 个档次,然后人工标注,机器再做拟合,这样成本很高,很多人是在用户点击行为中挖掘一些打分信息,比如有些文章用户点击次数较多,浏览时长较长,这样就可以给一个比较高的分档,就可以生成训练数据,这样容易常点击就排在前面。有的将“点击模型 +LTR”使用,假设每个排序都有一个被浏览到的概率,通过概率进行剔除来还原用户真实点击意愿。

(2)引入一些增强学习的思路,奖励函数、状态、动作和策略。具体应用就是将奖励函数抽象成点击数,还有价格等最后融合成一个打分函数,具体状态就是用户之前点击和购买商品的一些属性,这样可以描述用户当前所处的一个状态。最终我们是希望学习出一套策略针对用户不同状态给出不同策略。这样的好处是用户在当前页面点击一些东西,在翻页的时候我们可以调整一下排序策略以追求奖励最大化(下单最大化)。

(3)IRGAN 对抗网络,也可以做推荐。有一个生成模型和一个判别模型,前者生成干扰项(负例),判别模型进行排序,如果判别模型能判别出生成模型生成的干扰项,可以得到更好的效果,学习的过程也是一个迭代的过程。

下面是一些论文的推荐。

——END

如果您觉得这篇文章还不错,帮忙转发分享哈 ~~

DataFun社区是一个关注大数据、人工智能技术主题的社区,主要形式以组织线下的技术沙龙活动为主、线上运营为辅。希望将行业内资深从业者拉到大家面前,和大家进行一对一的面对面交流,促进同行间的沟通交流,推动大数据、人工智能技术在不同场景下的交流融合、共同进步。DataFun 的愿景是:为广大数据从业者和爱好者打造一个公益免费的分享、交流、学习、成长的平台。

    目前我们的活动已经覆盖了北京、深圳、上海等城市,希望大家多多支持,后期持续为大家推出更多干货的线下沙龙活动。


更多高质资源 尽在AIQ 机器学习大数据 知乎专栏 点击关注

转载请注明 AIQ - 最专业的机器学习大数据社区  http://www.6aiq.com