Rademacher复杂度在统计学习理论中的研究:综述  

Researches on Rademacher Complexities in Statistical Learning Theory: A Survey

作　　者：吴新星[1,2,3] 张军平[2,3] WU Xin-Xing ZHANG Jun-Ping(Department of Computer, Shanghai Technical Institute of Electronics and Information, Shanghai 201411 School of Computer Science, Fudan University, Shanghai 200433 Shanghai Key Laboratory of Intelligent Information Processing, Shanghai 200433)

机构地区：[1]上海电子信息职业技术学院计算机应用系,上海201411 [2]复旦大学计算机科学技术学院,上海200433 [3]上海市智能信息处理重点实验室,上海200433

出　　处：《自动化学报》2017年第1期20-39,共20页Acta Automatica Sinica

基　　金：国家自然科学基金(61673118;61273299);上海浦江人才计划(16PJ D009);上海市人才发展资金(201629)资助~~

摘　　要：假设空间复杂性是统计学习理论中用于分析学习模型泛化能力的关键因素.与数据无关的复杂度不同,Rademacher复杂度是与数据分布相关的,因而通常能得到比传统复杂度更紧致的泛化界表达.近年来,Rademacher复杂度在统计学习理论泛化能力分析的应用发展中起到了重要的作用.鉴于其重要性,本文梳理了各种形式的Rademacher复杂度及其与传统复杂度之间的关联性,并探讨了基于Rademacher复杂度进行学习模型泛化能力分析的基本技巧.考虑样本数据的独立同分布和非独立同分布两种产生环境,总结并分析了Rademacher复杂度在泛化能力分析方面的研究现状.展望了当前Rademacher复杂度在非监督框架与非序列环境等方面研究的不足,及其进一步应用与发展.Measuring the complexity of a hypothesis space plays a crucial role in statistical learning theory. Unlike those data-independent complexities, Rademacher complexity, which is data-dependent, can attain a much more compact generalization representation. In recent years, Rademacher complexity has attracted more attention and found broad applications in the development of statistical learning theory. Because of its importance, in this paper we review several complexity measures of function classes and their relations with Rademacher complexities. Next, we describe the techniques of Rademacher complexities in generalization analysis. Then, we present the recent researches of Rademacher complexity learning bounds for independent and identical distribution（i.i.d.） and non-independent and identical distribution（noni.i.d.）. Finally, we discuss the potential issues and possible directions of Rademacher complexities in statistical learning theory.

关 键 词：机器学习 统计学习理论 泛化界 Rademacher复杂度 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]