基于数据包络分析的排序学方法

摘要

本发明公开了一种基于数据包络分析的排序学方法。该发明以检索词为单位，每个检索词的关联文档构成一个决策单元集合，根据数据包络分析模型确定每个关联文档的最优权值向量，以之构建候选基本模型集合。最后，基于Boosting技术优化排序模型。本发明公开的方法能够有效改善当前排序学模型的性能，可应用于搜索引擎、机器翻译、推荐系统，以及生物信息等领域。

主权项

一种基于数据包络分析的排序学习方法，包括如下步骤：S1.给定训练数据集，包含三个部分：检索词集合关联文档集合和文档相关等级标记集合其中，N是训练集中检索词的个数；检索词包含有n_i篇关联文档：每个文档d_ij(j=1，...，n_i)都使用一个特征向量x_ij表示，每个维度对应一个检索词‑文档对特征，如PageRank，TF*IDF等；其中，r_ij代表d_ij与检索词q_i的相关程度；S2.对于任意检索词检索词‑文档对d_ij作为一个决策单元，从文档特征向量x_ij或者文档相关等级r_ij中选择一部分特征作为输入变量，一部分特征作为输出变量，构建一个多输入‑多输出的数据包络分析模型；S3.对于D_i中的每个文档，求解相关的数据包络分析模型，获得每个文档对应的最优权值向量；S4.重复步骤S2与S3，获得所有关联文档的最优权值向量，将其组成为候选基本模型集合Φ={ω₁，...，ω_m，...，ω_M}，其中M表示候选基本模型集合的大小，由于部分线性规划无最优解，$M\le \underset{i=1}{\overset{N}{\Sigma }}{n}_i;$S5.从Φ中选取一个候选基本模型ω_m，使用它预测训练集中每个文档的相关性分值，生成一组分值列表S_m={S_m1，...，S_mN}，其中S_mi是一个n_i维的向量，代表ω_m对检索词q_i所有关联文档的预测结果；S6.根据预测的S_mi和检索词q_i所有关联文档的真实相关等级R_i，计算候选基本模型ω_m在q_i上的排名精度E_mi，把ω_m在训练集中所有检索词的排名精度向量记为E_m，即E_m=(E_m1，...，E_mi，...，E_mN)；S7.根据S_ij和G_ij，评估候选基本模型ω_i在q_j上的排名精度E_ij∈R，记ω_i在训练集所有检索词上的排名精度向量为E_i=(E_i1，...，E_iN)；S8.重复步骤S5至S6，直到遍历尽Φ中的所有候选基本模型，使用所有候选基本模型的排名精度，构成一个M×N的排名精度矩阵E；S9.设定检索词的初始概率分布为P_i=1／N(i=1，...，N)，初始集成模型f=0；S10.将步骤S9学习得到的基本模型h_t，添加到集成模型f=f+β_th_t，计算集成模型在所有检索词上的精度向量其中表示集成模型f在检索词q_i上的排名精度，并基于下式更新检索词的概率分布：$P_i=\psi \left(E_i^{\left(f\right)}\right)$其中，ψ是一个单调递减函数，根据集成模型在不同检索词的表现做出相应调整，表现越好，相应检索词的概率值就下调，否则，则提升相应检索词的概率分值；S11.将步骤S9和S10重复T次，训练得到的集成模型是基本模型的线性组合：$f={\Sigma }_{t=1}^T{\beta }_t{h}_t;$S12.输入测试集中检索词‑文档对的特征向量，使用步骤S11训练得到的集成模型f，预测文档的相关分值。