稀疏正则化最小二乘排序算法

论文摘要

一般的排序问题,就是要寻找一个实值排序函数,然后根据给定的输入问题对一系列的样本评分并进行排序。排序算法以各种形式在很多领域都得到广泛应用,如网页检索,文件恢复。由于其广泛应用,排序在机器学习中也很受关注。本文介绍了排序学习问题的相关背景知识；文中提到的算法是基于最小化以排错样本对总数作为排序损失函数的最小二乘逼近,是再生性希尔伯特空间中的正则化核排序算法；算法计算量与训练样本个数呈立方关系,因此,当样本集很大,且核函数为非线性函数时,算法将很难实现,文中提出算法的稀疏逼近；同时,利用算法稳定性概念对排序算法进行推广界分析。特别地,文中提到的算法也满足稳定性条件。因此,推广界结论可以应用到文中提到的算法。论文结构如下：第1章介绍排序问题的背景、意义和主要研究方法。第2章给出了算法的正则化,利用表示定理得出排序函数,并且利用对偶正则化最小二乘排序对问题进行求解。第3章主要讨论第2部分得出的最优解的稀疏性,来减少求解排序函数的计算量。第4章的主要目的是利用排序算法的稳定性推广界对文中提到的算法进行分析,并得出推广界。第5章是对本文工作的总结和展望。

论文目录

• 摘要
• Abstract
• 第1章 引言
• 1.1 排序问题的提出及研究现状
• 1.2 排序问题
• 第2章 正则化排序算法
• 2.1 正则化框架
• 2.2 对偶正则化排序
• 第3章 排序算法的稀疏逼近
• 3.1 正则化排序的稀疏
• 3.2 稀疏性
• 3.3 贪婪逼近
• 3.3.1 正交化过程
• 3.3.2 选择规则
• 3.3.3 Cholesky分解
• 3.4 Nystrom逼近
• 3.4.1 Nystrom方法
• 3.4.2 选取过程
• 第4章 稳定排序算法的推广界
• 4.1 排序算法的稳定性
• 4.2 稳定排序算法的推广性
• 4.3 正则化排序算法的稳定性
• 4.3.1 希尔伯特空间正则化
• 第5章 结果及展望
• 参考文献
• 致谢