基于排序学习算法的智能检索系统

王镇宇，郑扬飞

(华北计算技术研究所系统八部，北京 100083)

0 引 言

面对庞大的数据量和复杂的数据组织结构，传统的关系型数据库在存储和检索数据方面的性能并不令人满意。鉴于存储和检索数据的复杂性，对信息检索功能提出了更高的要求。工业界常用方法是将数据迁移到集成了数据存储和检索功能的垂直分布的搜索引擎[1]，例如Solr、Elasticsearch等。尽管垂直分布式搜索引擎[2]提供的域指定语言(Domain Specific Language, DSL)查询可以满足大多数复杂的检查请求，但它要求工程师对检索请求和文档之间的相关性进行详细分析，并对垂直领域的数据有详尽的了解，在此之上进行信号的过滤、放大等建模。这对提高检索模块的可扩展性和检索性能等功能带来了挑战。本文基于Elasticsearch(ES)进行文本的初步检索和排序，使用机器学习排序算法(Learning to Rank, LTR)[3]建模对返回的结果进行排序，以最大程度地检查请求和结果之间的相关性[4]，同时优化相关性评分策略使评价标准考虑文本的词频及文本长度，设计并实现一套智能检索系统。

1 排序学习算法

1.1 排序学习算法分类

典型的排序学习模型如图1所示，训练集为向量化的检索集，通过学习系统学习出的模型，对测试集中的检索q进行排序相似度预测打分。排序学习算法按照输入输出空间、损失函数等定义的不同，可以分为3类。

图1 排序学习模型框架

1.1.1 Pointwise方法

输入为单个文本的特征向量，输出则包括了每一个文本的相关性评分，通过对相关性评分[5]的排序输出排序学习的结果。常用的Pointwise方法有梯度提升树(Gradient Boosting Decision Tree, GBDT)、支持向量机(Support Vector Machine, SVM)等。由于并未考虑文本之间的相互依赖，且在检索评价标准中很多都是基于检索语句级别和位置定位级别的，因此Pointwise方法的局限性很大。

1.1.2 Pairwise方法

Pairwise方法的输入为特征向量化的文本对，输出为文本选择为{+1,-1}，通过得分函数得出每对文本的相关性评分来进行排序，当每一对文本对都严格有序，则整个输出空间的文本有序。常用的Pairwise方法有RankSVM、LambdaRank等。这种方法的局限性也很明显，譬如一对相关度都很低的文本对，它们的相对顺序没有办法反应它们在最终检索结果中的最终位置，因此传递的信息依赖于结果文本对的数量。

1.1.3 Listwise方法

相较于前2种方法，Listwise的输入为特征向量化的文本集，输出为一个有序结果表。Listwise的评分方法本质上还是采用Pairwise的评分方法，但不同的是将文本对作为一个样本，从而考虑整体排序来进行文本打分，因此相较而言Listwise的性能是优于前2种方法的。常用的有LambdaMART等。

1.2 信息检索的评价标准

本节介绍在给定测试集的情况下，常规的几种对信息检索结果度量的相关标准。主要分为：无序检索结果集合的评价，评价标准有正确率P、召回率R以及平衡F值[6]；有序检索结果的评价标准有平均准确率均值(Mean Average Precision, MAP)和归一化折损累计增益(Normalized Discounted Cumulative Gain, NDCG)。

1.2.1 无序检索结果集合的评价

正确率(Precision, P)计算公式见式(1)，表示返回的文本中相关性文本的比重。

(1)

召回率(Recall, R)计算公式见式(2)，表示返回的文本占所有相关性文本的比重。

(2)

通过表1可以更直观地理解P和R的概念，于是有P的计算公式(3)和R的计算公式(4)。

表1 正确率召回率相关概念

(3)

(4)

(5)

1.2.2 有序检索结果的评价方法

MAP是一种常用的有序检索结果的评价方法。假定信息需求qj∈Q，所有满足条件的相关文本集合为d1,…dmj,Rjk是返回结果中满足条件的文本集合，则有MAP的计算公式(6)。

(6)

NDCG是另一种在机器学习的排序方法中常常使用的评价指标。NDCG@k表示基于前k个检索结果进行计算。计算某个查询集合Q，假设R(j,d)是人工给出的文本d对查询j的相关性评分，则有公式(7)，其中Zj,k是归一化因子。

(7)

ROC曲线及AUC。ROC称为受试者工程特征曲线，基于False Positive画出True Positive而得到的曲线，在此基础之上，为了能够量化使用ROC曲线进行性能评估，定义AUC为ROC曲线下的面积。面积越大则表示模型性能越好。

2 智能检索系统设计与实现

2.1 排序学习建模

搜索的本质分为2个阶段：token匹配和文本排名系统。提升检索效率是一个相关性工程，问题的关键在如何提升用户提出的检索需求和返回文本的相关性。数据资产管理系统中的数据往往杂乱无章，且数据治理程度不高，但用户进行检索时只会对几个特定类别的数据进行查询。为了解决相关性反馈部分遇到的文本分类的困境，本文引入机器学习领域基于相关性预测搜索结果和查询条件相关性的排序学习技术[7]。本节介绍基于Pointwise的RankSVM模型、梯度提升树GBDT模型和基于Pairwise的LambdaRank模型在文本排序领域的相关改进和优化。

2.1.1 基于RankSVM构建LTR模型

本节介绍使用改进的排序支持向量机RankSVM构建排序学习模型的过程。RankSVM是一种基于支持向量机SVM实现的排序算法。通常在使用SVM的过程中都会使用很多技巧来提升其性能。文本分类问题通常都是在高维空间进行，这意味着数据是线性不可分的，SVM引入核函数来解决这个问题，解决思路类似于数据的降维过程，将数据映射到高维平面再进行逐步的线性分类。基于RankSVM构建排序学习模型过程如下：

(8)

(9)

图2 RankSVM使用的Hinge Loss函数

2.1.2 基于GBDT构建LTR模型

本节介绍基于改进的梯度提升树[8]GBDT来构建排序学习模型，此时排序问题被简化为一个多分类问题。GBDT的主要思想是通过迭代来拟合多个决策树的残差，树状结构很适合进行决策分类问题，且和其它排序模型结合就可以进行排序学习[9]。本文的基于GBDT构建的排序学习模型过程如下：

(10)

(11)

接着定义得分函数f用来将分类结果转化为排序得分，即将分类器的输出转化为概率。定义g(k)是相关性为k的一个单调递增函数，则一个文本的最终排序得分计算见公式(12)。

(12)

2.1.3 基于LambdaRank构建LTR模型

RankNet[10]提出将错误对最少作为优化目标的排序算法，但有时候仅以这种目标来评价排序结果是不准确的。例如使用NDCG@k指标时并不会关注所有结果，只会取前k个结果进行加权评估，从而会导致评价指标不可导，因此无法采用机器学习进行迭代优化参数。LambdaRank算法则另辟蹊径，没有进行定义损失函数和计算梯度这2步操作，直接定义梯度来解决排序问题[11]。因此，LambdaRank的训练收敛速度更快且可以直接对问题求解。

本节介绍基于LambdaRank构建排序学习模型的过程，采用将基于位置的权重引入Pairwise损失函数[12]的方法，这种评估方法直接用于定义训练过程中每个文本对的梯度，来使得对应的损失函数可以和最终的排序结果更加一致。假设只有2个相关文本x1与x2，使用NDCG@1作为评价指标，它们的相关性如图3所示。如果将x1或x2移动到列表的顶端，则可以获得最大的NDCG@1。

图3 使用NDCG@1的文本相关性评价

从图3中可以看出将x1向上移动更加方便，因为工作量会比移动x2小很多。因此可以定义x1排名得分的梯度要大于x2排名分数的梯度，将移动的工作量抽象为优化过程中存在的一个隐式损失函数L，见公式(13)。

(13)

上面提到的梯度称为Lambda函数，定义r(·)为文本在上一轮训练中的排名位置，使用NDCG来优化训练过程时有如下的Lambda函数，见公式(14)。

(14)

对于每一对文本xu和xv，每一次优化之后它们的得分分别提升了+λ和-λ。实验中采用公式(14)中推导的Lambda函数，使得算法可以让目标函数达到局部最优。

2.2 排序学习算法模型的嵌入

本节首先介绍实验中所使用的文本分类特征选择方法，然后介绍在不同的排序学习模型下构建特征集和参数选择的相关信息。主要介绍对训练数据的特征工程、基于线性SVM的RankSVM模型的构建、基于XGBoost构建的梯度提升树和LambdaRank模型的相关参数选择、模型的训练过程以及验证，最后展示将机器学习模型以插件的形式作为ES打分功能的过程。

2.2.1 构建评价表

首先使用数据资产[11-12]构建评价表，生成评价表为csv文件格式，列分别为评分-分类-文本id，评分为分类算法给出的评分，标准化后落到区间[1,10]之内。譬如，分类器给出评分为0.238，则落到区间内为2.38，向下取整为2，分数越高则表示分类器认为该文本属于当前类的可能性更高。本文认为分类器评分大于5的文本为与实际分类正相关的文本，采用过滤器来组合对应符合查询的文本id。

与传统的机器学习算法的特征不同的是，为了能够将模型以插件的形式嵌入ES中，因无法使用特征数值化和正规化等处理[13]，考虑到数据资产管理平台上的数据大都是结构化数据，从每一行数据的角度来看，可以拆分成特征个的字典，因此本文将数据集处理成libSVM的矢量数据格式，其格式如下：

<类别><字段1>:<值1><字段2>:<值2>…<字段N>:<值N>

其中，类别为相关性，1为正相关，0为负相关，后续为字段名∶值对。考虑到数据资产检索使用ES的场景，结合检索模块的设计，本文在对模型训练时选取的特征都是文本类型。

2.2.2 构建LTR query

接着需要构造LTR query来提供使用排序学习模块进行打分的功能，这里需要注意使用filter模块，从而不会让LTR的再评分影响到搜索引擎本身的评分策略。LTR字段提供3个属性：name表示使用的LTR模型；field表示查询的字段；params表示查询关键词，可以是多个参数。

2.2.3 LTR模型嵌入

ES支持自定义式插件来提供额外的功能，用户可以其支持的格式开发出满足自己需求的应用以插件的形式嵌入即可。有了上一节训练的排序学习模型参数，可以通过POST给ES添加排序学习插件。如果想要更新或者删除排序学习模型，可以通过DELETE指令来删除已有的模型，可以看到ES本身是不会自己去对数据进行处理并对模型进行任何操作的，本质上以插件的模式提供的是模型输出的决策树参数。这就让ES通过LTR模块进行查询的时候，利用排序学习的知识来对每一步的判断作出选择。也正因此，可以通过定制模型来让ES返回相关度更高的检索结果。

2.2.4 使用LTR搜索

使用LTR的检索本质上是对检索结果的某个字段进行再次打分，通过过滤的方法对结果进行再次排序。考虑到实际使用场景，用户使用LTR模块进行搜索的数据量可能会非常大。例如初次检索满足条件的文本数目为10万条，则在给用户返回数据之前，需要通过LTR对每个文本的字段进行再打分。这将消耗非常多的服务器资源，且耗时很长使得检索体验变差。综合考虑用户对数据资产检索的习惯，若前端展示设置为每页展示10条结果，则一般情况下用户不会翻到100页去查看第1000条检索结果，这也不符合正常查询的习惯。因此，采用对topN的检索结果进行LTR再打分，N的默认值为100。

2.3 调整相关性评分策略

在信息检索的过程中信号建模和评价函数的设计相互影响[14-15]，决定了检索结果的质量。在ES当中每个字段都可以定义不同的相关性评分策略，这就可以让人们根据字段数据类型的不同选择对应的评分策略，从而提高文本评分的准确度。

BM25[16]是ES默认的相关性评分策略，是一种基于词项频率、文本长度等要素来建立概率模型的方法：对于文本d，给文本中的每个查询词项赋权值，计算公式如式(15)，其中，检索状态值RSV指最后用于排序的状态值，dft是包含t的文本数目，N为文本总数。

(15)

本文通过引入词项的频率[17]和文本长度[18-19]，对BM25的相关计算公式进行调整后的公式见式(16)。其中，tftd定义为词项t在文本d中的权重，Ld为文本d的长度，Lave是整个文本集中文本的平均长度。k1和b这2个参数用来对文本中的词项频率进行缩放控制[20]。

(16)

3 系统实验

3.1 实验数据

本节主要对比排序学习模块各算法在文本分类[21]和文本排序任务[22]上的表现。选取10类共25091条数据，数据选取的类别及数目见表2。

表2 数据类别及数量

3.2 排序学习模型实验结果

针对3种LTR模型进行排序结果展示，评价标准为NDCG@100和AUC，结果见表3。

表3 排序学习模型性能

GBDT在排序实验中对不同类别的数据表现也会有很大的波动，而RankSVM和LambdaRank则表现较为稳定。

3.3 智能检索系统检索实验结果

表4展示了3种排序学习模型对不同文本类型的检索效果，从R均值可以看出，默认配置的ES对数据的检索效率和GBDT相近，RankSVM和LambdaRank则在前两者基础上，大大提升对相关性文本的检索效率。

表4 检索结果前100准确性对比

4 系统整体架构

系统架构如图4所示，主要分为数据源、采集、索引、检索和结果展示5个模块。

图4 系统架构图

从数据流的角度来看，系统对数据的处理有如下几个过程：首先是确定待整合数据类型，然后按照数据源类型配置采集任务，在ES中构建或者更新索引导入数据，接着对索引中数据进行检索，经过信号放大及过滤、使用排序学习模型重新打分，最后返回结果给用户。

5 结束语

本文针对工程项目中采用关系型数据库进行全文查询效率低下的问题，研究并基于排序学习算法构建了智能检索系统，有效地解决了多源数据导入步骤繁杂、检索数据相关性低及全文检索耗时长等问题。试验结果表明，使用排序学习模块可以有效地提升返回文本的相关性评分，使得检索准确度得到提升。本文设计的智能检索系统可以有效地解决全文检索效率低下等常见的问题，但还有很多可以改进的地方，譬如支持异构数据的接入[21]、使用自然语言处理技术[22]来支持通用查询等。