达观数据搜索引擎排序实践（上篇）

随着互联网的深入发展，人类已然进入大数据时代。如何在浩瀚的数据海洋里高速有效的获取有价值的信息，正是促使大数据技术具备走向众多企业的潜力。搜索引擎作为获取信息的有效入口，已然经历了20多年的发展，并一直试图理解用户搜索意图以及提升搜索的精准性。

Google是全球性的搜索引擎，看似简单的搜索框背后隐藏的是极其复杂的系统架构和搜索算法，其中排序（以下统称Ranking）的架构和算法更是关键部分。Google正是通过PageRank算法深刻改变搜索排序而一举击败众多竞争对手。

Ranking是搜索引擎的核心技术，本文以搜索引擎的Ranking技术为切入点，从搜索引擎架构、检索模型、机器学习算法、点击模型、搜索效果评估等方面将达观数据（www.datagrand.com）在搜索引擎Ranking的构建与优化过程中的一些实践经验与大家做分享。

达观数据（www.datagrand.com）一直致力于钻研和积累各种大数据技术、尤其在文本挖掘、搜索引擎、推荐系统等方面积累深厚，曾获得CIKM 2014数据挖掘竞赛（搜索意图识别）全球冠军（达观数据 桂洪冠 陈运文）

图1：达观团队获得CIKM数据挖掘竞赛冠军

经典搜索排序架构

通常在线搜索引擎要求实时响应（毫秒级）用户的搜索请求，使得在线对每个文档进行基于模型的Ranking复杂计算不太现实，因而搜索的过程被分成两个阶段。阶段一是使用相对简单的常用检索模型对用户query从索引中快速检索出Top-k候选结果集。

常用检索模型主要有向量空间模型(Vector Space Model)、布尔模型(Boolean Model)、概率检索模型BM25等，通常Top-k的候选集选取还结合离线计算质量分高的文档以排除掉文本相关但质量分太低的文档；阶段二则使用计算相对复杂的机器学习排序模型对Top-k候选结果集进行精确的重排序，因为Top-K的候选结果集数据量级一般不会很大，这一步计算可控。

图2：一个经典的搜索引擎排序架构

Ranking模型的训练数据主要由query、文档以及query与文档的相关度组成，相关度可以标记成好、不好两个级别或细粒度更高的Perfect、Excellent、Good、Fair、Bad五个级别。训练数据主要有两种获取方式：方式一是由搜索评测人员标记query与每个文档的相关度进行手工的评测整理；方式二是通过自动分析搜索点击日志生成。显然，对于大规模机器学习排序模型的训练数据人工标注的成本过高，而且人工也无法对模型进行相对实时的更新。

达观数据（www.datagrand.com）主要通过方式二生成训练数据，自动分析搜索点击日志，分析用户在同一个搜索session内对query的各种变换、对搜索结果中不同位置的文档的点击行为以及后继的筛选、翻页等行为，综合计算出一个可以标记训练数据的搜索满意度得分。

达观搜索的实践表明，通过分析搜索点击日志可以实现模型训练数据的自动生成和实时更新，同时也可以达到比较满意的搜索效果。（达观数据 桂洪冠 陈运文）

达观搜索引擎架构

图3 达观搜索引擎架构

达观搜索引擎架构从底往上分别是分布式数据存储层、索引构建与模型训练层、索引数据与模型数据分发层、搜索核心层、开放接口层，同时系统架构还支持搜索引擎的索引配置和Ranking策略配置、以及搜索分析与效果评估。

搜索核心层是由query分析引擎、索引引擎、Ranking引擎构成。其中query分析引擎（QUERY ANALYSIS ENGINE）负责对用户的query进行语义分析和意图识别，包括query分词、中心词提取、query纠错、query自动提示、query扩展等。

索引引擎（INDEX ENGINE）执行Top-k候选结果选取，这里我们综合考虑了检索模型的搜索相关性评分和文档的静态质量分（离线计算），另外在这一层还根据用户的筛选条件以及业务层面的搜索结果配置进行了搜索结果的筛选和融合。

排序引擎（RANKING ENGINE）利用机器学习模型对Top-k的候选集执行第二轮的精确排序。RANKING ENGINE内置一个算法插件框架，可以根据用户配置的搜索排序策略加载相应的排序算法插件以及排序算法模型，同时还支持用户对搜索流量划分到不同的排序算法插件，以实现多个算法策略的同时在线A/B testing对比。

检索模型的选择

常见的检索模型主要有布尔模型(Boolean Model)、向量空间模型(Vector Space Model)、概率检索模型BM25与BM25F。

布尔模型

布尔（Boolean）模型是基于集合论和布尔代数的一种简单检索模型。它的特点是查找那些对于某个查询词返回为“真”的文档。在该模型中，一个查询词就是一个布尔表达式，包括关键词以及逻辑运算符。通过布尔表达式，可以表达用户希望文档所具有的特征。由于集合的定义是非常直观的，Boolean模型提供了一个信息检索系统用户容易掌握的框架。查询串通常以语义精确的布尔表达式的方式输入。

布尔模型的主要优点是直观和简单，缺陷在于完全匹配会导致被返回的结果文档太多或者太少。

向量空间模型(Vector Space Model，VSM)

VSM概念简单，即把对文本内容的处理简化为向量空间中的向量运算，并且它以空间上的相似度表达语义的相似度，直观易懂。当文档被表示为文档空间的向量，就可以通过计算向量之间的相似性来度量文档间的相似性。文本处理中最常用的相似性度量方式是余弦距离。

向量空间模型中通常采用TF* IDF的方式计算权重。Wij = TFij * IDFij 表示termi在文档dj的权重，Wiq = TFiq * IDFiq 表示termi在query q中的权重。

VSM的优点：

1）对term的权重的计算可以通过对term出现频率的统计方法自动完成，使问题的复杂性大为降；

2）支持部分匹配和近似匹配，并可以根据query和文档之间的相似度对结果进行排序。

VSM缺点：

1）基于term之间的独立性假设，也即权重计算没有考虑term之间的位置关系，也没有考虑term的长度对权重的影响；

2）计算量大。新文档加入需要重新计算term的权重。

概率检索模型

概率统计检索模型(Probabilistic Retrieval Model)是另一种普遍使用的信息检索算法模型，它应用文档与查询相关的概率来计算文档与查询的相似度。

二元独立模型(BIM)

词汇独立性假设:文档里面出现的词没有任何关联，这样一个文档的出现就可以转为各个单词出现概率的乘积。

对于同时出现查询qi以及文档di的时候，对qi在di中出现的单词进行“相关文档/不相关文档”统计，即可得到查询与文档的相关性估计值

其中：

N表示是文档集中总的文档数；

R表示与query相关的文档数；

ri表示与query相关的文档中含有的第i个term文档个数；

ni表示含有的第i个term文档总数；

0.5是平滑因子，避免出现log(0)。

BM25 模型

BM25 模型在BIM模型的基础上考虑了查询词在Query以及Doc中的权重，并通过实验引入了一些经验参数。BM25模型是目前最成功的内容排序模型。

改进之后的 BM25 模型的拟合公式如下:

公式的第1部分同BIM独立模型，公式的第2部分是查询词的term在Doc中的权重，第3部分是查询词的term在查询本身的权重。

fi 表示term在D中的词频，K因子表示文档长度的考虑，其计算公式为:

其中：

k1为经验参数， k1一般设置为1.2；

b为调节因子，将b设为0时，文档长度因素将不起作用，经验表明一般b=0.75；

dl代表当前文档的长度；

avdl代表所有文档的平均长度；

qfi 表示在查询中的词频，k2也为调节因子，因为在短查询下这部分一般为1，为了放大这部分的差异，k2一般取值为 0~1000。

综上所述，BM25模型结合了BIM因子、文档长度、文档词频和查询词频进行公式融合，并利用k1，k2，b对各种因子进行权重的调整。

BM25F模型

BM25F模型对BM25模型的改进之处在于考虑了文档不同区域的加权统计，例如文档的标题和描述被赋予了不同的区域权重，在各个不同区域分别统计词频。

BM25F模型的计算公式为:

其中：

文档D来自不同的u个域；

各个域对应的全总为Wk；

fui 表示词频；

Bu表示各个域的长度；

ulu 为域的实际长度，uvulu表示域的平均长度；

bu 为各个域长度的调节因子。

检索模型总结

每种检索模型各有千秋，适用不同的场景和应用。布尔模型、空间向量模型、概率模型等传统检索模型的排序方法一般通过构造相关性函数实现，然后按照相关性进行排序。检索模型尤其概率模型比较适用于内容相关性排序，但内容相关性一般仅考虑query和doc的tf，idf，dl，avdl等因素，很难融合点击反馈、文档质量分、点击模型等更多的排序因素。一个大型搜索引擎排序因子往往多达数十个乃至上百个（Google搜索排序因子超过200个），如果模型中参数过多，调参会变得非常困难，也很容易导致过拟合现象。

但正如前文所述，搜索引擎需要快速响应用户搜索请求，无法在毫秒级时间内对每一个召回结果进行精确的机器学习排序，业界的主流的做法是首先进行第一轮的Top-k选取再对Top-k结果进行第二轮的精确重排序。传统检索模型尤其概率模型比较适用于文本内容相关性排序，能够满足快速获取 Top-k候选结果集的需求。

达观数据（www.datagrand.com）搜索在第一轮Top-k选取中选用的是BM25F检索模型。BM25F模型相比BM25模型考虑了文档不同区域的加权统计，可以获得更好的文本相关性，是目前最优的文本检索模型。

机器学习排序（Machine Learning to rank）方法很容易融合多种特征，且有成熟深厚的数学理论基础，通过迭代优化参数，对于数据稀疏、过拟合等问题也有比较成熟的理论和实践。

（达观数据 桂洪冠 陈运文）

未完待续

达观数据搜索引擎排序实践下篇

作者会为您介绍

机器学习排序

点击模型

敬请期待，感谢关注！

作者

桂洪冠，达观数据（www.datagrand.com）联合创始人&技术副总裁，中国计算机学会（CCF）会员。曾服务于阿里、盛大、腾讯几家公司，任腾讯文学、盛大文学数据中心高级研究员、阿里搜索技术专家等职务，主要负责搜索与广告团队。