子采样排序与相关熵排序的学习理论研究

In this project, we will study the mathematical theory of learning to rank. Considering the computation difficulty of ranking with a large number of data, we introduce Nyström approximation and Markov sampling approaches for the ranking model and provide the fast optimization algorithms. We focus on the study of learning theory foundations of the subsampling ranking, and provide the theory analysis including consistency and convergence rate in terms of error analysis associated with the operator approximation and the capacity estimation of assumption space. This study will demonstrate the role of sampling method on generalization ability and computation complexity. Meanwhile, considering the non-Gaussian noises and outliers of the ranking data, we introduce the information theoretic learning to the ranking problem and construct the ranking model under maximum correntropy criterion, and provide the theory analysis on its generalization ability and robustness. Finally, the proposed algorthms are applied to bioinformatic data, and their effectiveness is verified on the drug discovery and the protein homology detection. This project is expected to break through the limitation of traditional ranking for a large number of data, and establish the mathematical foundations of learning to rank.

本项目研究排序机器学习的数学理论基础。针对大规模数据下排序算法的计算难题，将Nyström逼近和Markov采样引入排序学习模型，构建快速排序算法，重点探讨其学习理论基础，分别利用基于容量估计和基于算子逼近的误差分析方法建立其一致性和收敛速度的分析，阐明采样方法对排序学习泛化能力和计算复杂性的影响机制。同时，针对数据中非高斯噪声和噪点问题，将信息理论学习引入排序模型，构建基于最大相关熵准则的排序学习算法，探讨其泛化能力和鲁棒性能。最后，将设计算法应用于生物信息数据，探索其在药物发现和蛋白质同源检测等排序任务中的有效性。本项目期望在面向大规模数据的排序算法设计和数学理论分析方面取得突破，建立排序机器学习的数学理论基础。

本项目对正则排序相关算法的学习理论与应用进行了深入的研究。项目组按照研究计划，有序推进研究工作，圆满完成了研究目标。主要研究成果包括三个部分：一是建立了几类正则排序算法学习率的刻画，分析了分布式、去偏置及交互策略对泛化能力的影响，通过数据实验验证了相关策略提升计算效率和预测性能的有效性； 二是证明了基于Nyström采样和Markov采样正则学习算法的误差界，阐明了采样机制与计算复杂性、泛化性的关系；三是设计了几类稀疏可加模型，给出了其泛化误差界和变量选择一致性分析，并在高维数据挖掘中验证了其良好的性能。本项目相关研究不仅发展和丰富了排序学习的数学基础，也为大规模数据情形的算法设计和应用提供了理论指导。