基于集成支撑矢量机排序的信息检索方法

摘要

本发明公开了一种基于集成支撑矢量机排序的信息检索方法，主要解决现有方法训练效率和排序精确度低的问题。实现步骤为：(1)将训练样本按照查询对象的不同分别进行模型训练得到初始模型组；(2)利用Ranking SVM算法中的排序算法根据模型组中各个模型对验证集分配排序分数，选择对集成之后排序分数的平均精确度有贡献的模型构成系统模型集；(3)系统模型集中的各模型给测试集中各特征向量分配排序分数，将对应于同一个特征向量的排序分数之和作为输出。本发明提高了排序学习方法用于信息检索的模型训练效率和排序的精确度，使其更具有通用性，可应用于网络搜索引擎、军事情报检索及机器翻译。

权利要求

1.一种基于集成支撑矢量机排序的信息检索方法，包括如下步骤：

1)设 定训 练 样本 集 其 中m表 示 查询 对 象 的总 个 数，表示与第i个查询对象关联的所有文件的特征向量， (j＝1，2，...，n(i))表示第j个关联文件的特征向量，n(i)表示与第i个查询对象关联的文件总数目，表示与x(i)对应的标签序列；

2)利用Ranking SVM算法中的训练算法，将Γ中每一个查询对象对应的关联文件和标(i) (i)签分别作为一个训练样本训练，将第i个查询对象的关联文件和标签(x ，y )训练得到(i)模型表示为ml ，m个查询对象的关联文件和标签训练组成模型组

3)设定验证集 作为Ranking SVM算法中的排序算法输入，并根据步骤(2)中所得模型组中的每个模型给V中所有的特征向量分配排序分数，得到排序分数向(i)量组 其中 表示与模型ml 对应的第i个排序分数向量，K表示验证集

(k) (k)

中查询对象的总数，f 为对应于验证集中的第k个查询对象x 的排序分数向量且维数等(k)于x 中特征向量的个数；

4)将排序分数向量组 中各向量随机进行顺序重排，得到一个向量队列，令F等于向量队列中第一个分数向量，根据F以及验证集标签 和平均精确度公式计算验证集排序分数的平均精确度mp，将第一个分数向量对应的模型保存至候选系统模型集；

5)对队列中第二个分数向量进行判断：设其对应的分数向量为F′，令新排序分数向量Fnew＝F+F′；根据Fnew计算新的验证集排序精确度mpnew，若mpnew≥mp则F＝Fnew，mp＝mpnew，将第二个分数向量对应的模型保存至候选系统模型集，否则进行向量队列中下一个分数向量的判断，直至步骤(4)中的向量队列结束，得到最终验证集平均精确度mplast＝mp；

6)将步骤(4)和(5)重复N次，得到N个候选系统模型集和与之对应的N个最终验证集平均精确度mplast，并对所有的mplast按升序排列，将处于队列中间位置的mplast对应的候选系统模型集选择为最终的系统模型集；

7)输入新的查询及其关联文件的特征向量，利用Ranking SVM的排序算法和步骤(6)所得的系统模型集给特征向量分配排序分数，将对应于同一个特征向量的排序分数之和作为排序系统的输出。

2.根据权利要求书所述的信息检索方法，其中步骤(2)所述的将Γ中每一个查询对象对应的关联文件和标签分别作为一个训练样本训练，是将Γ中每个查询对象对应的关联文件和标签分别作为Ranking SVM算法中训练算法的输入，训练算法经过迭代优化模型的参数使根据模型分配的排序分数与训练数据的标签达到最佳匹配。

3.根据权利要求书所述的信息检索方法，其中步骤(3)所述的根据步骤(2)中所得模型组中的每个模型给V中所有的特征向量分配排序分数，是将V作为Ranking SVM算法中的排序算法的输入，排序算法根据每个模型自动给V中所有的特征向量进行相关性评估并分配一个排序分数作为输出，特征向量与查询的相关性越大，排序分数越高。

说明书

基于集成支撑矢量机排序的信息检索方法

技术领域

[0001] 本发明属于信息检索领域，涉及一种机器学习的方法，具体地说是一种排序学习方法。可适用于信息检索。

背景技术

[0002] 信息检索起源于图书馆的参考咨询和文摘索引工作，随着1946年世界上第一台电子计算机问世，计算机技术逐步走进信息检索领域，并与信息检索理论紧密结合起来，脱机批量情报检索系统、联机实时情报检索系统相继研制成功并商业化。随着科技的不断进步，在信息处理技术、通讯技术、计算机和数据库技术的推动下，信息检索在教育、军事和商业等各领域高速发展，得到了广泛应用。比如文件检索、协同过滤、专家查找、反网络垃圾邮件、关键词提取、机器翻译等等。文件检索是其中一个最重要的应用，并且可以应用于网页搜索引擎。信息检索的核心问题是排序问题，好的排序算法可以有效的提高信息检索的效率和精确度，将机器学习理论用于排序的方法称为排序学习。近几年来，排序学习不论在机器学习领域还是信息检索领域都取得广泛的关注和快速的发展。排序学习的主要目的是希望能够根据已有的正确排序的训练样本自动训练出一个排序模型，使得此模型可以用于排序或者分类。当该系统用于信息检索时，排序系统根据输入的查询信息分别计算相应文件与查询信息的相关分数，最后根据相应的分数对文件进行排序，相关分数越大表示相应的文件与查询的相关度越大。排序学习的方法按照损失函数和训练方式的不同可以分为三类：点式法、对式法、列表式法。点式法是早期提出的算法，算法的性能均比不上之后出现的两种算法。对式法是在点式法之后提出的已经比较成熟的算法，并且成功应用于文件检索。这个方法的主要思想是将对式文件作为训练样本，使排序问题转化为分类问题。在学习过程中，它从排序列表中收集对式文件，并给每个对式文件分配一个标签作为这个对式文件中两个文件之间关系的标志。然后利用这些标签训练分类模型并将该模型应用于排序。由于对式法需要将训练数据转化为对式训练数据，使得算法的效率变得很低。Herbrich et al.(1999)最早提出利用对式法和SVM技术建立分类模型，并发展为经典的对式排序学习算法，即Ranking SVM，受到广泛关注，并且已经成功被应用于网页搜索引擎中。但是这个方法仍然存在以下问题：1算法的训练效率低，当训练数据集过大时训练难以进行；2在参数选择时需要进行多次的训练，大大增加了训练的时间；3排序的平均精确度比较低。

发明内容

[0003] 本发明的目的在于克服上述技术的不足，提出一种基于集成支撑矢量机排序的信息检索方法，以提高Ranking SVM法的训练效率，减少模型训练所用时间，提高排序的平均精确度。

[0004] 为实现上述目的，本发明将集成机器学习的思想引入Ranking SVM法，其具体步骤包括如下：

[0005] 1)设定训练样本集 其中m表示查询对象的总个数，表示与第i个查询对象关联的所有文件的特征向量， (j＝1，
(i) (j)
2，...，n )表示第j个关联文件的特征向量，n 表示与第i个查询对象关联的文件总数(i)
目， 表示与x 对应的标签序列；

[0006] 2)利用Ranking SVM算法中的训练算法，将Γ中每一个查询对象对应的关联文件(i) (i)和标签分别作为一个训练样本训练，将第i个查询对象的关联文件和标签(x ，y )训练(i)
得到模型表示为ml ，m个查询对象的关联文件和标签训练组成模型组

[0007] 3)设定验证集 作为Ranking SVM算法中的排序算法输入，并根据步骤(2)中所得模型组中的每个模型给V中所有的特征向量分配排序分数，得到排序分数向量组 其中 表示与模型ml(i)对应的第i个排序分数向量，K表示验证集中查询对象的总数，f(k)为对应于验证集中的第k个查询对象x(k)的排序分数向量且维数等于x(k)中特征向量的个数；

[0008] 4)将排序分数向量组 中各向量随机进行顺序重排，得到一个向量队列，令F等于向量队列中第一个分数向量，根据F以及验证集标签 和平均精确度公式计算验证集排序分数的平均精确度mp，将第一个分数向量对应的模型保存至候选系统模型集；

[0009] 5)对队列中第二个分数向量进行判断：设其对应的分数向量为F′，令新排序分数向量Fnew＝F+F′；根据Fnew计算新的验证集排序精确度mpnew，若mpnew≥mp则F＝Fnew，mp＝mpnew，将第二个分数向量对应的模型保存至候选系统模型集，否则进行向量队列中下一个分数向量的判断，直至步骤(4)中的向量队列结束，得到最终验证集平均精确度mplast＝mp；

[0010] 6)将步骤(4)和(5)重复N次，得到N个候选系统模型集和与之对应的N个最终验证集平均精确度mplast，并对所有的mplast按升序排列，将处于队列中间位置的mplast对应的候选系统模型集选择为最终的系统模型集；

[0011] 7)输入新的查询及其关联文件的特征向量，利用Ranking SVM的排序算法和步骤(6)所得的系统模型集给特征向量分配排序分数，将对应于同一个特征向量的排序分数之和作为排序系统的输出。

[0012] 本发明与现有算法相比具有如下优点：

[0013] 1.本发明由于将训练样本中各个查询对象分别进行模型训练，因此使时间复杂度2
由现有算法的O(M)减少为 其训练效率比现有高出m倍，易于训练
大规模数据集，M表示训练样本规模，m表示查询对象总数。

[0014] 2.本发明不需要在训练同一个模型时为选择参数进行多次训练，因此在相同条件下本发明训练模型所需的时间远小于现有算法。

[0015] 3.本发明由于在选择模型时只保留对平均精确度增加有贡献的模型，因此排序的平均精确度得到很大的提高。

附图说明

[0016] 图1是本发明的流程图；

[0017] 图2是本发明的模型训练子流程图。

具体实施方式

[0018] 参照图1，本发明的实现步骤包括如下：

[0019] 步骤1，设定训练样本集

[0020] 设定训练样 本集 其中m表示查询 对象的总个 数，表示与第i个查询对象关联的所有文件的特征向量， (j＝1，
2，...，n(i))表示第j个关联文件的特征向量，n(i)表示与第i个查询对象关联的文件总数目， 表示与x(i)对应的标签序列，Γ为M*l的矩阵，其中M＝
(1) (2) (m)
n +n +，...，+n 为矩阵的行数，l表示列数，第一列为标签列，第二列为查询对象(1)
编号，其余为关联文件的特征，第1行到第n 行是第一个查询对象关联文件的特征向(1) (1) (1) (1) (2)
量及标签，即(x ，y )，第n +1行到第n +n 行为第二个查询对象关联文件的特(2) (2)
征向量及标签(x ，y )，以此类推，第m个查询对象关联文件的特征向量和标签为第(1) (2) (m-1)
n +n +，...n +1行到第M行。

[0021] 步骤2，训练生成模型组

[0022] 参照图2，本步骤具体如下：

[0023] (2.1)将步骤1中的训练样本按照查询对象不同，分为m个子训练样本；

[0024] (2.2)将m个子训练样本分别输入到Ranking SVM方法中的训练算法进行模型的训练，得到各自对应的模型，训练算法调用工具包SVMlight中的训练算法，SVMlight的训练算法的参数-C随机从{1，0.1，0.01，0.001，0.0001，0.00001}中选取；

[0025] (2.3)将所有的模型构成模型组

[0026] 步骤3，生成验证集排序分数向量组

[0027] 将验证集 作为Ranking SVM算法中的排序算法输入，排序算法根(1)据步骤2中所得模型组中的第一个模型ml 对V中各特征向量进行关联度评估，并分配排(1) (2) (2)
序分数，得到排序分数向量F ，根据第二个模型ml 得到的排序分数向量是F ，依次进行得到分数向量组 其中Ranking SVM算法中的排序算法调用工具包SVMlight中的排(k) (k)
序算法，x 表示验证集中第k个查询对象的特征向量，y 为验证集中第k个查询对象的(i)
标签， 表示与模型ml 对应的第i个排序分数向量，K表示验证集中查询对象(k) (k) (k)
的总数，f 为对应于验证集中的第k个查询对象x 的排序分数向量且维数等于x 中特征向量的个数。

[0028] 步骤4，生成随机向量队列及初始化候选系统模型集

[0029] (4.1)将排序分数向量组 中各向量随机进行顺序重排，得到一个向量队列；

[0030] (4.2)令F等于向量队列中的第一个分数向量，根据F以及验证集中各查询对象的标签 和平均精确度公式计算验证集排序分数的平均精确度mp，将向量队列中的第一个分数向量对应的模型保存至候选系统模型集，其中平均精确度公式详见Turpin，A.& Scholer，F.(2006).User performance versus precision measures for simple search tasks.In Proceedings of the 29th Annual international ACM SIGIR Conference on Research and Development in Information Retrieval(pp.11-18)。

[0031] 步骤5，选择模型进入候选系统模型集

[0032] 对向量队列中第二个分数向量进行判断：设其对应的分数向量为F′，令新排序分数向量Fnew＝F+F′；根据Fnew计算新的验证集排序精确度mpnew，若mpnew≥mp则F＝Fnew，mp＝mpnew，将第二个分数向量对应的模型保存至候选系统模型集，否则进行向量队列中下一个分数向量的判断，直至步骤4中的向量队列结束，得到最终验证集平均精确度mplast＝mp。

[0033] 步骤6，选择系统模型集

[0034] (6.1)将步骤4和步骤5重复N次，得到N个候选系统模型集和与之对应的N个最终验证集平均精确度mplast，N取值为25；

[0035] (6.2)对所有的mplast按升序排列，将排在第13位的mplast对应的候选系统模型选择为最终的系统模型集。

[0036] 步骤7，输出

[0037] (7.1)输入测试查询及其关联文件的特征向量，利用Ranking SVM的排序算法和步骤6所得的系统模型集给特征向量分配排序分数；

[0038] (7.2)将对应于同一个特征向量的排序分数之和作为排序系统的输出。

[0039] 仿真实验

[0040] 本发明的效果可以通过以下实验进一步说明：

[0041] 1.仿真条件：

[0042] 在CPU为pentium(R)43.00GHZ、内存1G、WINDOWS XP系统上进行了仿真。

[0043] 2.仿真内容：

[0044] 本发明的实验数据是下载自微软亚洲研究院的LETOR团队网页的标准排序学习数据OHSUMED，该数据包含106个查询总共16140个文件的特征向量及标签，数据集包含5个文件夹，每个文件夹中包含三个数据集，即：训练集、验证集和测试集。各个文件夹的数据集包含的查询文件如表1所示，

[0045] 表1：各文件夹实验数据分布

[0046]训练集 验证集 测试集
文件夹1 查询对象1～63 查询对象64～84 查询对象85～106
文件夹2 查询对象22～84 查询对象85～106 查询对象1～21
文件夹3 查询对象43～106 查询对象1～21 查询对象22～42
文件夹4 查询对象1～2164～106 查询对象22～42 查询对象43～63
文件夹5 查询对象1～4285～106 查询对象43～63 查询对象64～84

[0047] 表1中的5个文件夹共同构成五倍交叉验证。

[0048] 本发明利用上述实验数据进行实验仿真，按照具体实现步骤，对每个文件夹中的数据进行如下操作：利用训练集训练模型组，利用验证集进行系统模型集的生成，将验证集和测试集分别作为步骤7中所述的输入数据，得到各自的排序分数，最后根据各自的排序分数和已知的数据标签进行算法性能的评估，评估方法为平均精确度MAP和均化折扣累积收益NDCG，MAP和NDCG是最常用的表征信息检索算法优劣的两个评价指标，信息检索算法越好，MAP和NDCG的值越高。

[0049] 将本发明与现有的Ranking SVM方法在MAP和NDCG评价指标上的进行仿真比较，其结果如表2和表3所示。

[0050] 表2：本发明与Ranking SVM在MAP评价指标上的结果比较

[0051] a：验证集上结果比较

[0052]Methods 文件夹1 文件夹2 文件夹3 文件夹4 文件夹5 平均值
本发明 0.4838 0.3624 0.4654 0.4711 0.5234 0.4612
Raking SVM 0.4653 0.3489 0.4566 0.4580 0.5070 0.4472[0053] b：测试集上结果比较

[0054]Methods 文件夹1 文件夹2 文件夹3 文件夹4 文件夹5 平均值
本发明 0.3447 0.4620 0.4648 0.5086 0.4674 0.4495
Raking SVM 0.3038 0.4468 0.4648 0.4990 0.4528 0.4334[0055] 表3：本发明与Ranking SVM在NDCG评价指标上的结果比较

[0056] a：验证集上结果比较

[0057]

[0058] b：测试集上结果比较

[0059]

[0060] \从表2和表3可以明显看出，不管在MAP评价指标还是在NDCG评价指标上本发明都比现有Ranking SVM方法在信息检索性能上有很大的提高。此外本发明方法在单个文件夹上的训练时间只有15分钟，仅为同等条件下Ranking SVM方法训练时间的1％，训练效率得到很大的提高，使得本发明易于训练Ranking SVM方法难以进行的大规模数据集。因此本发明比现有方法应用于信息检索具有优越性。