压缩回归学习算法的泛化界-论文.pdf

《压缩回归学习算法的泛化界-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、爨黝数学物理学报http：／／actams．wipm．ac．cn压缩回归学习算法的泛化界曹飞龙戴腾辉张永全(中国计量学院数学与信息科学系杭州310018)摘要：研究了压缩最小平方回归学习算法的泛化性问题．利用随机投影、覆盖数等理论以及概率不等式得到了该学习算法的泛化误差上界．所获结果表明：压缩学习虽以增大逼近误差的方式降低样本误差，但其增量是可控的．此外，通过压缩学习，在一定程度上克服了学习过程中所出现的过拟合现象．关键词：机器学习；压缩感知；回归学习算法；误差界；逼近．MR(20001主题分类：41

2、A25；41A63；42B08中图分类号：O174．41文献标识码：A文章编号：10033998(2014)04—905—121引言回归问题[7,12]，即利用有限样本估计未知函数近年来在机器学习领域中受到广泛的关注，涌现了许多相关的学习算法．在这些众多的学习算法中，最小平方回归学习算法因其所具有的实用性和灵活性而受到人们的青睐．然而，在实际应用中，当考虑以线性空间作为假设空间的时候，往往存在空间的维数远大于样本个数的现象，即模型中参数的个数大干样本的个数(即未知量的个数大于约束条件的个数)，由此导致

3、学习的过拟合现象．由于过拟合会降低学习算法的性能，甚至使算法失去泛化能力，因此，过拟合现象是机器学习中需要极力避免的．为了克服机器学习中的过拟合现象，学者们提出了一系列的方法．常用的典型方法有(1)正则算法：学习算法的解是通过极小化由经验误差和惩罚项所组成的目标函数而获得．例如厂=argra，in(，)+AIPfH~，p1或者p2∈_H其中>0是正则参数，并且正则项的选择依赖于实际问题．例如，z范正则项可以用来求解脊回归(ridge—regress)[，1可用来解决LASSO问题[13]．(2)最小范

4、数最小平方解：在满足1或最小的条件下，极小化经验误差，其数学表达式为a=argminll。r￡(或鲁棒解argmin1)．11o4中Q0：=yll虫Ot—一Yl1l2<￡收稿日期：2012—07—21；修订日期：2013—11—27E—mail：feilongcao@gmail．com基金项目：国家自然科学基金(61272023，91330118，11301494)资助906数学物理学报V()1．34A在上述式子中，。范所对应的解就是原始的最小平方解，而范所对应的解是稀疏解．稀疏解近年来已被广泛应用于

5、压缩感知领域[3-4,8J．在如何克服学习过程中过拟合现象的研究中，除了上述所提及的两种代表性方法外，人们发现压缩感知理论中的随机投影技术[1．5,1012]也可用于克服机器学习过程中所出现的过拟合现象．随机投影的思想可以简要地描述为以下两个步骤．首先，利用一个随机矩阵将高维线性空间变换到一个低维线性空间；然后，直接在低维空间上探讨和研究学习问题．随机投影技术的优越性主要体现在以下两个方面：(1)该技术能够有效地降低空间维数；(2)随机投影变换能够近似地保留向量之间的内积，从而可以保留算法的学习能力．

6、近年来，有关随机投影技术在机器学习领域的研究已经取得了一些较好的成果．例如Calderbank[6j等人应用支持向蕈机fSVM)算法[]在压缩数据空间上讨论了分类问题，并且重新建立了该算法的泛化误差界．在文献『2，14]中，作者首先展示了如何将一个核函数k(x，Y)一-(，，．)-()映射到低维空间并且能够近似保持内积不变，然后，建立了有关核函数的一个低维特征空间．Zhou等人在文献f191中讨论了压缩学习问题并且研究了基于压缩数据的LASSO估计『【】J题．Maillard等人在文献_11]中分析了

7、压缩最小平方回归学习的可能性．本文将随机投影技术应用于最小平方回归学习算法中，我们聚焦于当线性假设空间满足条件时，压缩最小方回归学习算法的泛化性估计问题．在研究中，我们要求假设空间所满足的条件是能够使得逼近误差的增量相对较小并且足可控制的．在证明过程中，我们先利用覆盖数理论和统计学中的概率不等式估计压缩回归学习算法的样本误差，然后利用逼近理论给该算法的逼近误差，最后结合这两者并建立该学习算法的泛化误差上界估计．2回归学习与压缩空间设(X，d)是一个度量空间，令Y=．设P是Z：=X×Y上的一个未知概率分

8、布．令z一{}一{(％玑))∈Z表示由m个样本所构成的样本集，该集合中的样本是依据分布P独立选取的．令Px，p(ylx)分别表示P的边缘概率测度和条件概率测度．函数f：X—y的泛化误差定义为(．，)：：厂(，(z))dp，，：X—y(2．1)Jz我们把使得(2．1)式达到最小的函数称作为回归函数，其定义表述为()=dp(I)，∈x．(2．2)本文假设Y={∈：in'r?z}，其中0