ZHANG Ji-xiong，WANG Jian-li ，SHENG Bao-huai ＊

（1.College of Science，Hangzhou Normal University，Hangzhou 310036，China；2.Department of Mathematics，Shaoxing University，Shaoxing 312000，China）

Error Analysis on Regularized Learning

ZHANG Ji-xiong1，WANG Jian-li2，SHENG Bao-huai2＊

（1.College of Science，Hangzhou Normal University，Hangzhou 310036，China；2.Department of Mathematics，Shaoxing University，Shaoxing 312000，China）

This paper proposed the error analysis on a kind of regularization learning algorithm，offered the sample error by the large number law，and provided the estimation for approximation error with a K-functional.

learning theory；regularization framework；function reconstruction；reproducing kernel Hilbert spaces

1 Introduction

It is known that the Shannon sampling theorem is the core of function reconstruction which is the theory foundation of signal process and many other related fields（see e.g.[1-4]）.To deal with the noise in the sampling data，S.Smale and D.X.Zhou considered，from the view of learning theory and regression analysis，the regularization learning algorithm for random sampling and provided an error analysis in probability（see[4]）.In the present paper，we shall give some further investigations on the estimate of the error analysis for the algorithm.To this end，we need to state the learning framework.

Such maps are called Mercer kernels.

Let Pbe a non-negative Borel measure on X×R，PXbe the marginal measure induced by Pon X，i.e.，the measure on Xdefined by PX（S）＝P（π－1（S）），whereπ：X×R→Xis the projection.Notice that P（x，y），P（y｜x）and PX（x），x∈X，satisfy the following relation（see e.g.[1]，[5]）

This“breaking”of Pinto the measure P（y｜x）and PX（x）corresponds to looking at X×Ras the product of Xand R.

2 The Robustness

Before showing Theorem 1we give the robustness of the solutions.

Proposition 1 Let P，Qbe distributions on Z with｜P｜2＜＋∞，｜Q｜2＜＋∞.K（x，y）are Mercer kernels on X×Xsatisfying （2）.α（P）andα（Q）are solutions of scheme（7）for distributions Pand Q respectively，（x）＝.Then，there holds

Lemma 1 Let Pbe a distribution on Z＝X×Rsuch that｜P｜2＜＋∞.K（x，y）are kernels on X×X satisfying（2）.Then，

i）There exists uniquely a minimizer ofα（P）of problem （7）and

ii）There holds the following relation

3 The Sample Error

The definitions ofαz，γ，α（P）and f＊yields

Proposition 2 Let K（x，y）be a Mercer kernel on X×Xsatisfying（2）.Pis a distribution on Z with｜P｜2＜＋∞，α（P）andαz，γare defined as in（7）and（6）respectively.Then，for any 0＜δ＜1，with confidence 1－δ，there holds

4 Proof of Theorem 1

By（16）and（25）we have

[1]Cucker F，Smale S.On the mathematical foundations of learning theory[J].Bull Amer Math Soc，2001，39（1）：1-49.

[2]Cucker F，Zhou Dingxuan.Learning theory：an approximation theory viewpoint[M].New York：Cambridge University Press，2007.

[3]Han Deguang，Zayed A I.Sampling expansios for functions having values in a Banach space[J].Proc Amer Math Soc，2005，133（12）：3597-3607.

[4]Smale S，Zhou Dingxuan.Shannon sampling and function reconstruction from point values[J].Bull（New Series）Amer Math Soc，2004，41（3）：279-305.

[5]Cucker F，Smale S.Best choices for regularization parameters in learning theory：on the biasvariance problem[J].Found Compt Math，2002，2（3）：413-428.

[6]Carmeli C，De Vito E，Toigo A.Vector valued reproducing kernel Hilbert spaces of integrable functions and Mercer theorem[J].Anal Appl，2006，4（4）：377-408.

[7]Sun Hongwei.Mercer theorem for RKHS on noncompact sets[J].J Complexity，2005，21（2）：337-349.

[8]Devroye L，Györfi L，Lugosi G.A probabilistic theory of pattern recognition[M].New York：Springer-Verlag，1997.

[9]Micchelli C A，Xu Yuesheng，Zhang Haizhang.Universal kernels[J].J Mach Learn Res，2006，7：2651-2667.

[10]Smale S，Zhou Dingxuan.Estimating the approximation error in learning theory[J].Anal and Appl，2003，1（1）：17-41.

[11]Sheng Baihuai，Xiang Daohong.The convergence rate for a K-functional in learning theory[J].J Inequality and Appl，2010，DOI：10.1155／2010／249507.

[12]Sheng Baohuai.Estimates of the norm of the Mercer kernel matrices with discrete orthogonal transforms[J].Acta Math Hungar，2009，122（4）：339-355.

正则化学习算法的误差分析

张际雄1，王建力2，盛宝怀2
（1.杭州师范大学理学院，浙江 杭州 310036；2.绍兴文理学院数学系，浙江 绍兴 312000）

给出了一类正则化样本学习算法的误差分析.借助于大数定律给出了样本误差，用一种K-泛函给出了逼近误差的估计.

学习理论；正则化模型；函数重构；再生核Hilbert空间

O174.41 MSC2010：68Q32；68T05Article character：A

1674-232X（2011）01-0027-07

10.3969／j.issn.1674-232X.2011.01.006

date：2010-09-10

Supported by the National NSF（10871226）of PRC.

Biography：ZHANG Ji-xiong（1985—），male，born in Jiujiang，Jiangxi Province，master，engaged in learning theory.

＊Corresponding author：SHENG Bao-huai（1962—），male，born in Baoji，Shaanxi Province，Ph.D.，professor，engaged in learning theory.E-mail：bhsheng＠usx.edu.cn