韓永杰，陳 潔,2

(1.西華大學(xué)理學(xué)院，四川 成都 610039； 2.波鴻大學(xué)數(shù)學(xué)系，德國 北萊茵-威斯特法倫州 波鴻市 44787-44894)

令C(X)表示定義在X上的連續(xù)函數(shù)的全體，并賦予范數(shù)

當(dāng)H是C(X)中的緊子集，且學(xué)習(xí)過程發(fā)生在H中，則稱H為假設(shè)空間。

給定一個假設(shè)空間H，任意函數(shù)f∈H在H中的誤差

ΕH(f)=Ε(f)-Ε(fH)

稱為正規(guī)誤差。可以看出對任意f∈H有ΕH(f)≥0,且ΕH(fH)=0。

根據(jù)最小二乘誤差和正規(guī)誤差的定義，有

Ε(fz)=ΕH(fz)+Ε(fH)。

(1)

考慮和式ΕH(fz)+Ε(fH)[2-3]，第1項ΕH(fz)稱作樣本誤差[4-5]，第2項Ε(fH)和假設(shè)空間相關(guān)，但是獨(dú)立于樣本z，稱作逼近誤差[6]。

我們的目標(biāo)是計算Ε(fz)，等式(1)把目標(biāo)轉(zhuǎn)化成兩個不同的問題：計算樣本誤差和逼近誤差。注意到第1個問題是在假設(shè)空間H上提出的，第2個問題和樣本z無關(guān)。固定H，樣本誤差隨著采樣點(diǎn)數(shù)目m的增加而減少；固定樣本點(diǎn)數(shù)目，逼近誤差會隨著假設(shè)空間H的增大而減少，同時樣本誤差會增大。第二個特征被稱作偏差-方差平衡[7-8]。

本文利用樣本誤差ΕH(fz)和逼近誤差Ε(fH)的已有結(jié)果，將最小二乘誤差Ε(fz)統(tǒng)一為一個表達(dá)式。

1 預(yù)備知識和主要結(jié)果

令X表示距離空間，如果對于映射K:X×X→R滿足以下3個條件：

1)K(x,t)=K(t,x)，任意x,t∈X；

2)矩陣(K(xi,tj))k×k是半正定的，xi,tj∈X；

3)映射K是連續(xù)的，則稱K是Mercer核。

〈Kx，g〉K=g(x),?x∈X,g∈HK,

稱HK是再生核希爾伯特空間。HK是由連續(xù)函數(shù)構(gòu)成的空間，‖·‖K是由內(nèi)積誘導(dǎo)出的范數(shù)，且映射IK:HK→C(X)是有界的嵌入映射[9]。

在機(jī)器學(xué)習(xí)中，假設(shè)空間一般是Mercer核生成的再生核希爾伯特空間中的球。在以下部分我們默認(rèn)IK(BR)為假設(shè)空間，其中BR={f:f∈HK,‖f‖K≤R}。

令s>0，Sobolev空間Hs定義如下：

Hs(Rn)={f:f∈L2(Rn), ‖f‖Hs<∞},

集合K是賦范線性空間(X,‖·‖)的一個子集，對任意ε>0,集合K的ε-勢定義如下：

Ne(K)=min{N:z1,…,zN∈Rm,e(K,{z1,…,zN})≤ε}。

Zhou等研究了高斯核學(xué)習(xí)各向同性索伯列夫空間Hs的樣本誤差和逼近誤差的收斂階[6]，但是沒有給出最小二乘誤差的收斂階。本文在添加適當(dāng)條件后，得到了最小二乘誤差的估計。

在下文中，符號C表示不同位置可能不同的正常數(shù)。

定理A[11]令集合H是巴拿赫空間C(X)上的M-有界緊子集(即對任意的x∈H,都有M>0，使得x≤M)，則對于任意的ε>0，

下面給出本文的主要結(jié)論。

定理1 令R>0，f(x)∈Hs(X)，c0=4n(6n+2)，當(dāng)

E(f)≤C(lnR)-s/8。

注：定理1、2中的最小二乘誤差估計并不是最優(yōu)的，但將其統(tǒng)一為一個表達(dá)式可方便實際中的應(yīng)用。

2 主要結(jié)論的證明

定理1的證明。已知假設(shè)空間的半徑為R，則逼近誤差的收斂階是顯然的。

下面計算樣本誤差。由假設(shè)空間是IK(BR)，可以令M=R。根據(jù)定理A，有

(2)

(3)

其中c0=4n(6n+2)。對式(3)兩邊作取指數(shù)運(yùn)算，可以得到

那么式(2)就可以化為

進(jìn)一步化簡得到

(4)

根據(jù)微分中值定理和f(x)=ex的單調(diào)遞增性質(zhì)有

即

根據(jù)上式，直接計算可得

(5)

化簡式(5)

(6)

(7)

根據(jù)定理A、B，綜合可得最小二乘誤差為

E(f)≤C(lnR)-s/8。

定理2的證明。先考慮樣本誤差。由于假設(shè)空間是IK(BR)，不妨取M=R。類似定理1的證明過程，可以得到

令

(8)

其中c2>1。式(8)通過移項化簡為

(9)

對式(9)兩邊同時作取對數(shù)運(yùn)算，得到

根據(jù)拉格朗日中值定理，有

當(dāng)ε≤16R2e-(1/c0)1/(n+1)時，有

根據(jù)定理A、B，最小二乘誤差為：

[1]CUCKER F, SMALE S. On the mathematical foundations of learning[J]. Bulletin of the American Mathematical Society, 2001, 39(1): 1.

[2]COX D D. Approximation of least squares regression on nested subspaces[J]. Annals of Statistics, 1988, 16(2): 713.

[3]NIYOGI P, GIROSI F. On the relationship between generalization error, hypothesis complexity and sample complexity for radial basis functions[J]. Neural Computation, 1989, 8(9): 819.

[4]DEVROYE L, GYORFI L, LUGOSI G. A probabilistic theory of pattern recognition[M]. Berlin: Springer-Verlag, 1996.

[5]ANTHONY M, BARTLETT P. Neural network learning: theoretical foundations[M]. New York: Cambridge University Press, 1999.

[6]CUCKER F, ZHOU D X. Learning theory: an approximation theory viewpoint[M]. New York: Cambridge University Press, 2007.

[7]GOLUB G, HEAT M, WAHBA G. Generalized cross-validation as a method for choosing a good ridge parameter[J]. Technometrics, 1979, 21(2): 215.

[8]BISHOP C M. Neural networks for pattern recognition[M]. New York: Oxford University Press, 1996.

[9]ARONSZAJN N. Theory of reproducing kernels[J]. Transactions of the American Mathematical Society, 1950, 68(3): 337.

[10]MAIOROV V E. Kolmogorov’s (n,δ)-widths of spaces of smooth functions[J]. Sbornik Mathematics, 1994, 79(2): 265.

[11]ZHOU D X. The covering number in learning theory[J]. Journal of Complexity, 2002, 18(3): 739.

[12]SMALE S, ZHOU D X. Estimating the approximation error in learning theory[J]. Analysis and Applications, 2003, 1(1): 17.