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

语文考第一的物理老师

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

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


--
01 机器学习算法发展

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


--
02 搜索引擎算法体系





1.搜索引擎框架

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







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



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



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

2.搜索技术变迁





首先是查询分析这块：
（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表，这是二分图概念。我们再加一些可有可无词又生成一个表，类似于三分图概念。



3.意图识别算法

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



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



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



4.搜索排序算法

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



首先介绍一个顶层的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允许用户跳转浏览，如从第一条跳到第三条结果，再继续浏览，可以消除用户浏览的偏置。



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


--
03 算法展望

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



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





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



下面是一些论文的推荐。


<hr/>关于我们

DataFun：专注于大数据、人工智能技术应用的分享与交流。发起于2017年，在北京、上海、深圳、杭州等城市举办超过100+线下和100+线上沙龙、论坛及峰会，已邀请超过2000位专家和学者参与分享。其公众号 DataFunTalk 累计生产原创文章800+，百万+阅读，14万+精准粉丝。