排序学习中基于直接优化信息检索评价准则算法的理论分析

摘要

随着互联网技术的迅速发展，互联网上的信息量也以惊人的速度不断地膨胀，从海量的互联网信息中准确快捷的获取所需信息也变得日益困难。搜索引擎的出现正是为了使人们能够从海量的互联网信息中快速和便捷地获取所需信息。搜索引擎背后的关键技术是网页排序算法。如何设计一个有效的网页排序算法是信息检索领域中十分重要和流行的课题。近年来，将机器学习方法引入排序学习获得了很大成功，吸引了越来越多研究人员的注意。
　　 在排序学习领域中，直接优化信息检索评价准则算法已经成为一个重要分支。由于信息检索评价准则（例如MAP和NDCG）的不连续和不可导性导致其难以优化。直接优化信息检索评价准则算法的核心思想是通过优化一个与信息检索评价准则近似的替代函数达到优化信息检索评价准则的目的。我们称此替代函数为替代评价准则。
　　 直接优化信息检索评价准则算法的一个关键性基础问题是一对替代评价准则的优化是否能保证对相应的信息检索评价准则的优化？这个问题的解答，将直接决定直接优化信息检索评价准则算法的理论正确性。因为，如果对替代评价准则的优化不能保证对相应的信息检索评价准则的优化，那么直接优化信息检索评价准则算法将无法从理论上保证能够获得一个性能良好的排序模型。然而目前并无任何工作对这个问题有深入的理论研究，故而研究人员对直接优化信息检索评价准则的理论性质并不了解。
　　 本论文以直接优化信息检索评价准则算法的一个关键性基础问题（对替代评价准则的优化是否能保证对相应的信息检索评价准则的优化）为主线，以探索直接优化信息检索评价准则算法的理论性质为目标，创新性的提出了直接性和趋势相关性两个概念，用于以衡量替代评价准则与相应的信息检索评价准则之间的关系。并以直接性和趋势相关性为分析工具，获得了主流的直接优化信息检索评价准则算法中替代评价准则的理论性质。最后通过在公共基准数据集LETOR上对各个直接优化信息检索评价准则算法的实验验证了本文所得的理论分析结果，说明了用直接性和趋势相关性来衡量替代评价准则与相应的信息检索评价准则之间关系的科学性和正确性。
　　 ·本论文首先提出直接性和趋势相关性两个概念以衡量替代评价准则与相应的信息检索评价准则的关系。我们从理论上证明了，如果一个替代评价准则，相对于一个信息检索评价准则而言，具有任意大的直接性，或者任意强的趋势相关性，则对此替代评价准则的优化能保证对相应的信息检索评价准则的优化。
　　 ·在理论研究结论的基础上，我们分析了主流的直接优化信息检索评价准则算法的直接性和趋势相关性。通过理论分析，证明了SoftRankNDCG，ApproxRankMAP，ApproxRankNDCG中所优化的替代评价准则，在合适的参数设置下（例如，令SoftRankNDGG中参数σs→以及ApproxRankMAP和ApproxRankNDCG中参数α→∞），对任意数据分布都能具有任意大的直接性和任意强的趋势相关性。证明了SVMMAP，DORMNDCG，PermuRankMAP，SVMNDCG所优化的替代评价准则在某类数据分布上不能具有任意大的直接性和任意强的趋势相关性。因此，我们得到了SoftRankNDCG，ApproxRankMAP，ApproxRankNDCG相比于SVMMAP， DORMNDCG，PermuRankMAP，SVMNDCG具备更好的理论性质，因而能获得更好的排序性能的结论。
　　 ·最后通过在公共基准数据集LETOR上的实验研究，我们验证了对主流直接优化信息检索评价准则算法所优化的替代评价准则的直接性和趋势相关性的理论研究结果，说明了用直接性和趋势相关性衡量替代评价准则与相应的信息检索评价准则直接关系的科学性和正确性。

目录

文摘

英文文摘

表格

插图

第1章 绪论

1.1 引言

1.2 本文的研究背景

1.2.1 信息检索

1.2.2 排序学习

1.2.3 基于直接优化信息检索评价准则的排序学习算法

1.3 本文的动机及研究内容

1.4 本文的创新和贡献

1.5 本文的章节安排

第2章 相关工作

2.1 引言

2.2 信息检索排序学习的算法框架

2.3 主流信息检索排序学习算法介绍

2.3.1 基于单文档的排序学习算法

2.3.2 基于文档对的排序学习算法

2.3.3 基于文档列的排序学习算法

2.3.4 主流排序学习算法小结

2.4 主流信息检索评价准则介绍

2.4.1 查准率(Precision)和查全率(Recall)

2.4.2 平均查准率的均值(MAP)

2.4.3 NDCG (Normalized Discounted Cumulative Gain)

2.5 本章小结

第3章 直接优化信息检索评价准则的排序学习算法

3.1 引言

3.2 主流直接优化信息检索评价准则排序学习算法简介

3.2.1 SVMMAP

3.2.2 DORMNDCG

3.2.3 PermuRankMAP

3.2.4 SoftRankNDCG

3.2.5 SVMNDCG

3.2.6 ApproxRankMAP和ApproxRankNDCG

3.3 本章小结

第4章 直接性

4.1 引言

4.2 直接性

4.2.1 直接性定义

4.2.2 直接性的理论性质

4.3 SoftRankNDCG和SVMNDCG的直接性分析

4.3.1 SoftRankNDCG

4.3.2 SVMNDCG

4.3.3 总结及讨论

4.4 实验结果

4.4.1 数据集

4.4.2 SoftRankNDCG和SVMMAP的直接性

4.4.3 直接性和优化复杂度的折中

4.4.4 直接性和排序性能的关系

4.5 本章小结

第5章 趋势相关性

5.1 引言

5.2 趋势相关性

5.2.1 趋势相关性的定义

5.2.2 趋势相关性的理论性质

5.3 主流直接优化信息检索评价准则算法的趋势相关性分析

5.3.1 SoftRankNDCG

5.3.2 ApproxRankMAP和ApproxRankNDCG

5.3.3 SVMMAP,DORMNDCG,PermuRankMAP,SVMNDCG

5.3.4 总结及讨论

5.4 实验结果

5.4.1 数据集

5.4.2 直接优化信息检索评价准则算法的趋势相关性

5.4.3 趋势相关性和优化复杂度的折中

5.4,4 趋势相关性和排序性能的关系

5.4.5 总结

5.5 本章小结

第6章 总结和展望

6.1 总结

6.2 展望

参考文献

致谢

在读期间发表的学术论文与取得的研究成果