排序学习算法的一般模型研究

陈洪

华中农业大学理学院, 湖北武汉430070

排序学习算法的一般模型研究

陈洪

华中农业大学理学院, 湖北武汉430070

排序学习问题是机器学习与数据挖掘领域近来的研究热点之一。 本文通过分析和比较几种排序学习模型，提出基于这些模型的一般框架，从而为进一步的算法设计和理论分析奠定基础。

排序; 机器学习; 模型选择

随着排序机器学习算法在信息抽取，信用评价，产品推荐以及病理分析等领域的广泛应用，排序学习算法的设计和理论分析成为机器学习研究的热点课题之一。本文着重研究排序算法设计中的优化目标函数的选择问题。

一、排序学习的一般前提[3]

给定训练数据集合A，我们采用有向关系图G=(V,E)来表示数据间的序关系。同时用表示假设函数集合。详细来说，关系如下：

1.训练数据

这里描述的排序背景适合于分析和处理许多不同类型的经典排序模型。

二、几种排序模型

本节介绍几种常见的排序学习的目标函数，基于这些目标函数设计的排序学习算法在经验数据实验中显示了良好的性能。

1.二划分排序[1]

二划分排序问题是一种经典的排序问题，这里类别数只有两类。学习的目的就是使两类数据能顺利的区分开来。其对应的优化目标函数为

2.K-划分排序（详见[2]）

在K-划分排序排序问题中，给定的样本往往具有K个序标。因此，对应的优化目标函数为二排序优化目标函数的推广，其表达式如下

虽然基于此目标的推广误差的界已经在[2]中建立，但是该目标仅适合处理全相关的排序情形，在实际应用中受到很多限制。

3.推广的Wilcoxon-Mann-Whitney（WMW）统计

WMW统计原用于获得分类学习问题大偏差的界，近来被引入排序学习问题中。推广的WMW定义如下

基于此目标，一类快速的梯度下降算法在[3]中被提出，并且在数据实验中显示了良好的性能。然而，在实际排序问题中，往往更关注顶端的排序准确性，因而推广该目标到关注顶端排序问题是很有意义的一个课题。

4.p模排序

在文献[4]中，作者提出了一种新的优化目标函数，其优点在于能有效的强调排序问题顶端的排序性能。对应的目标函数定义为：

显然p模排序是基于二排序问题，其应用范围因此也受到较大限制。

三、排序学习的一般模型

基于以上几种排序优化函数，提出如下排序学习算法的一般模型：

该目标函数不仅能通过调整 p值的大小来强调顶端排序的准确性，也适合于处理各种排序关系问题，从而有更广泛的前景。

同时，从算法的理论分析来看，通过该模型的研究，有助于建立排序学习算法推广性能分析的统一理论基础，为进一步模型选择，算法设计以及参数选择提供理论指导。

该目标函数与前面几种目标函数的关系总结如下表：

?

四、小结

排序学习的理论和应用研究是近来机器学习和数据挖掘研究的热点问题之一。如何设计合理的算法模型是排序问题的关键。本文结合已有的模型，给出了一般条件下的优化目标模型。该模型适用更广泛的应用领域，且有助于建立排序学习算法统一的理论基础。

[1]S.Agarwal, et.al.Generalization bounds for the area under the ROC curve[J].JMLR,2005,6:393-425

[2]S.Rajaram,S.Agarwal．Generalization bounds for k-partite ranking[J].In NIPS, 2005

[3]V.C.Raykar, et.al.A fast algorithm for learning a ranking function from large-scale data sets[J].TPAMI, 2009, 30：1158--1170

[4]C.Rudin.The p-norm push: a simple convex ranking algorithm that concentates at the top of the list[J].JMLR, 2009,10：2233--2271

TP181

A

10.3969/j.issn.1001-8972.2011.13.081