k-部排序学习算法的可学习性分析  

Analysis of Learnability for k-Partite Ranking Learning Algorithm

作　　者：兰美辉[1] 甘健侯[2] 任友俊[1] 高炜[2] 

机构地区：[1]曲靖师范学院计算机科学与工程学院,云南曲靖655011 [2]云南师范大学信息学院,昆明650500

出　　处：《西南大学学报（自然科学版）》2016年第3期177-183,共7页Journal of Southwest University(Natural Science Edition)

基　　金：国家自然科学基金项目(61262071);云南省教育厅科学研究基金项目(2014C131Y)资助

摘　　要：分析在特定假设空间下k-部排序学习算法的可学习性.给出k-部排序可学习和可有效学习的概念,得到样本复杂度的上界以及k-部排序算法可有效学习的一个充分条件,同时给出与计算复杂度相关的若干结果.最后,将部分结果推广到限制模型中.One basic problem in statistical learning theory is the learnability of learning algorithms.In this paper,we analyze the learnability of the k-partite ranking algorithm for a given hypothesis space.The definitions of learnability and efficient learnability of k-partite ranking are given,the upper bound of sample complexity is obtained,and a necessary condition of efficient learnability of the k-partite ranking algorithm is deduced.Furthermore,some computational complexity-related results are presented.At last,several results are extended to the restricted model.

关 键 词：统计学习理论 可学习性 k-部排序算法 样本复杂度 计算复杂度 

分 类 号：TP393.092[自动化与计算机技术—计算机应用技术]