白海江, 付應(yīng)雄, 李偉夫

(湖北大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)學(xué)院, 湖北 武漢 430062)

?

基于馬氏采樣的最小二乘正則化回歸的最優(yōu)速率

白海江, 付應(yīng)雄, 李偉夫

(湖北大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)學(xué)院, 湖北 武漢 430062)

摘要：建立基于一致遍歷的馬氏采樣的推廣界, 利用最小二乘正則化回歸算法給出基于一致遍歷馬爾可夫鏈樣本的誤差分析, 并得到最優(yōu)的學(xué)習(xí)速率O(m-1).

關(guān)鍵詞：最優(yōu)速率; 最小二乘正則化回歸算法; 一致遍歷馬氏鏈

近年來, 隨著統(tǒng)計學(xué)習(xí)理論研究的深入, 許多專家學(xué)者熱衷于研究基于馬爾可夫鏈樣本(以下簡稱馬氏樣本)上的統(tǒng)計學(xué)習(xí)[1-6], 正則化算法是處理學(xué)習(xí)理論中不適定問題的一個有力工具[7-9]. 通過ERM原則, 文獻(xiàn)[2]中得到了V-幾何馬氏樣本的泛化界，并且證明了樣本的一致性. 文獻(xiàn)[6]中研究了馬氏樣本的SVMR算法的最優(yōu)速率. 文獻(xiàn)[5]中證明了基于馬氏樣本的測度的集中不等式. 筆者通過引入投影算子和覆蓋數(shù), 得到基于一致遍歷馬爾可夫鏈(uniformly ergodic Markov chain, u.e.M.c.) 樣本的推廣界, 并利用最小二乘正則化回歸(least squares regularized regression, LSRR)算法給出了基于u.e.M.c.樣本的誤差分析, 得到了最優(yōu)學(xué)習(xí)速率.

1預(yù)備知識

下面我們給出u.e.M.c.的定義:

定義1[10]若存在某個0<φ<∞和0<β0<1滿足

文獻(xiàn)[11]中證明了u.e.M.c.的n步轉(zhuǎn)移概率Pn(·|·)滿足下面的Doeblin條件:

命題1[11]令{Zt}t≥1是一個有著轉(zhuǎn)移概率Pn(·|·)的馬氏鏈,μ是一個有著非零質(zhì)量ν1的非負(fù)測度. 若存在某一個整數(shù)n1滿足Pn1(S|z)≤μ(S)對所有的z∈Z和所有的可測集S都成立, 則有

(1)

這里β1=1-ν1.

1.2最小二乘正則化回歸考慮輸入空間為X?Rd, 輸出空間為Y=R. 機器學(xué)習(xí)的目的是估計一個可測函數(shù)f:X→Y, 通過最小化風(fēng)險泛函

R(f)=∫Z(f(x)-y)2dρ,

找到目標(biāo)函數(shù)fρ[12]

fρ(x)=∫Yydρ(y|x),x∈X,

其中ρ(y|x)是由分布ρ和x誘導(dǎo)產(chǎn)生的條件概率測度.

然而在大多數(shù)情況下, 我們只知道樣本

Z={z1=(x1,y1),z2=(x2,y2),…,zm=(xm,ym)},

但是分布ρ是未知的, 因此目標(biāo)函數(shù)不能被直接求出. 于是, 我們的目標(biāo)就是通過樣本集Z在假設(shè)空間中尋找在某種意義上對fρ的最佳逼近.

文獻(xiàn)[12]中給出等式

(2)

經(jīng)驗風(fēng)險最小化(ERM)原則[13]利用最小化經(jīng)驗風(fēng)險Rm(f)來代替最小化期望風(fēng)險R(f)：

為了防止過擬合, 一般采用正則化的方法. 考慮假設(shè)空間是由Mercer核誘導(dǎo)生成的再生核希爾伯特空間. 這里Mercer核K：X×X→R是一個連續(xù)、對稱且正定的函數(shù).HK定義為由函數(shù)集{Kx=K(x,·):x∈X}張成的線性空間的閉包[14]. 在空間定義內(nèi)積<·，·>HK=<·，·>K,HK的再生性表現(xiàn)為

K=f(x),?x∈X,?f∈HK.

(3)

這里λ=λ(m)>0稱為正則化參數(shù). 假設(shè)存在一個常數(shù)M, 對?y∈Y都有|y|≤M, 則對?x∈X都有|fρ(x)|≤M. 利用投影算子π將fz,λ限制到區(qū)間[-M,M]上來改進誤差估計.

定義2[15]定義在可測函數(shù)f:X→Y上的投影算子π=πM為

(4)

通過考慮推廣誤差:

(5)

來度量一個算法的學(xué)習(xí)能力.估計(5)就是我們的目標(biāo), 為了達(dá)到這一目標(biāo), 我們定義一個正則化誤差D(λ)和正則化函數(shù)fλ來形成誤差分解. 在假設(shè)空間HK中fρ的正則化誤差定義為:

(6)

(7)

為了估計fz,λ的推廣誤差, 筆者給出如下命題:

{R(π(fz,λ))-Rm(π(fz,λ))+Rm(fλ)-R(fλ)}+D(λ)

(8)

命題2的證明不難驗證下面兩個不等式

由其可得，當(dāng)λ>0時, 有

{Rm(fλ)-R(fλ)}+{R(π(fz,λ))-Rm(π(fz,λ))}+

通常我們把(8)式左邊一項稱為樣本誤差, 右邊一項稱為逼近誤差.

定義3[16]稱fρ能夠被HK以指數(shù)0<γ≤1逼近, 如果存在常數(shù)c1滿足對?λ>0有

D(λ)≤c1λγ

(9)

估計樣本誤差首先要估計假設(shè)空間HK的容量, 采用覆蓋數(shù)來刻畫HK的容量. 覆蓋數(shù)的定義為:

定義4[17]若G是一個度量空間的一個子集, 對?ε>0, 函數(shù)集G的覆蓋數(shù)定義為G上半徑為ε的球覆蓋數(shù)的最小個數(shù).

令BR={f∈HK:‖f‖K≤R}, 不難知道BR是假設(shè)空間HK的一個子集[12]. 假設(shè)B1的覆蓋數(shù)為N(ε)=N(B1,ε),?ε>0.

定義5[16]如果存在Cs>0, 使得lnN(ε)≤Cs(1/ε)s,?ε>0

(10)

則稱HK的復(fù)雜度以指數(shù)為s>0的多項式衰減.

2主要工具

為了得到主要結(jié)果, 本文中引入一些關(guān)于馬氏鏈的集中不等式.

引理1[18]令G是由可數(shù)個有界可測函數(shù)組成的類,Z1,…,Zm是u.e.M.c.樣本. 假設(shè)存在一個常數(shù)B滿足0≤g(z)≤B,?g≤G,?z≤Z,那么有

引理2[18]在引理1的條件下, 對?ε>0, 有

3主要結(jié)論

基于前期的準(zhǔn)備知識, 本文中的主要結(jié)論為:

其中

本文中利用迭代方法[6]來提高定理1中的誤差估計. 主要結(jié)論可表述為定理2.

這里

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

4.1命題3的證明令S(z,λ)表示樣本誤差, 則有S(z,λ)=S1(z,λ)+S2(z,λ)，其中

S1(z,λ)=[R(π(fz,λ))-R(fρ)]-[Rm(π(fz,λ))-Rm(fρ)]，

S2(z,λ)=[Rm(fλ)-Rm(fρ)]-[R(fλ)-R(fρ)].

(11)

利用基本不等式

則對任意0<δ<1, 至少以置信1-δ成立

(12)

下面估計S1(z,λ)的界. 由于π(fz,λ)依賴于樣本z, 因此很難估計S1(z,λ)的值. 利用ERM原則和覆蓋數(shù)來確定該項的界. 由引理2可知, 對函數(shù)集GR,R>0,有

GR={g(z)=(π(f(x))-y)2-(fρ(x)-y)2:f∈BR},

因此

E(g)=R(π(f))-R(fρ)≥0，

g(z)=(π(f(x))-fρ(x)){(π(f(x))-y)+(fρ(x)-y)}.

由于π(f(x))≤M,|fρ(x)|≤M, 易知‖g(z)‖∞≤b:=4M2. 根據(jù)引理2, 對?ε>0, 有

(13)

方便起見,令R′(f)表示R(f)-Rm(f). 對?g1,g2∈GR,有

|g1-g2|=|(π(f1(x))-y)2-(π(f2(x))-y)2|≤

|π(f1(x))-π(f2(x))‖(π(f1(x))-y)+(π(f2(x))-y)|≤

4M‖f1-f2‖∞.

因此

‖g1-g2‖∞≤4M‖f1-f2‖∞,?g1,g2∈GR.

將不等式(10)式帶入上式, 令不等式右邊等于δ, 則有

因此

由文獻(xiàn)[9]知, 令c1,c2>0,s>q>0,方程xs-c1xq-c2=0有唯一解且滿足

x*≤max{(2c1)1/(s-q),(2c2)(1/s)}.

(14)

結(jié)合(8), (12)及(14)式, 對任意0<δ<1, 至少以置信1-2δ成立

(15)

因此, 將δ替換為δ/2, 即完成了命題3的證明.

4.2定理1的證明不難驗證, 由fz,λ的定義, 對于函數(shù)f=0，對?z∈Zm, 有

(16)

因此

(17)

不等式(17)式表明存在一個測度不大于δ的VR?Zm滿足

(18)

其中C0是獨立于m的正常數(shù). 對(18)式進行迭代, 找到一個以很高的置信水平去包含fz,λ的小球BR.

因此

根據(jù)W(R(J))的定義, 則

(19)

代入不等式(18), 有

5參考文獻(xiàn)

[1] Zou B，Xu Z，Chang X. Generalization bounds of ERM algorithm with V-geometrically Ergodic Markov chains[J].Advances in Computational Mathematics, 2012(1): 99-114.

[2] Zou B,Zhang H,Xu Z B. Learning from uniformly ergodic Markov chain samples[J]. J Complexity, 2009(2): 188-200.

[3] Zou B, Li L Q, Xu Z B.Generalization performance of least-square regularized regression algorithm with Markov chain samples[J].J Math Anal Appl, 2012(1): 333-343.

[4] Marton K.A measure concentration inequality for contracting Markov chains[J]. Geom Funct Anal, 1996(3): 556-571.

[5] Samson P M. Concentration of measure inequalities for Markov chains and -mixing processes[J].Ann Probab, 2000(1): 416-461.

[6] Xu J.Optimal rate for support vector machine regression with Markov chain samples[J].International Journal of Wavelets, Multiresolution and Information Processing, 2014(6);1450045(16).

[7] Evgeniou T,Pontil M, Poggio T.Regularization networks and support vector machines[J].Advances in Computational Mathematics, 2000(1): 171-203.

[8] Becker S，Thrun S，Obermayer K，et al.On the mathematical foundations of learning[J].Bulletin of the Ams, 2001(1): 1-49.

[9] Cucker F,Smale S.Best choices for regularization parameters in learning theory: on the bias—variance problem[J].Foundations of Computational Mathematics, 2008, 2(4): 413-428.

[10] Vidyasagar M. Learning and Generalization with Applications to Neural Networks[M].2nd edition. London: Springer, 2003.

[11] Meyn S P,Tweedie R L. Markov chains and Stochastic Stability[M]. Verlag: Springer, 1993.

[12] Cucker F,Smale S.On the mathematical foundations of learning[J].Bull Amer Math Soc, 2001(1): 1-49.

[13] Vapnik V. Statistical Learning Theory[M]. New York: John Wiley, 1998.

[14] Aronszajn N. Theory of reproducing kernels[J].Trans Amer Math Soc, 1950(3): 337-404.

[15] Chen D R, Wu Q, Ying Y M,et al.Support vector machine soft margin classifiers: error analysis[J].Journal of Machine Learning Research, 2004(3):1143-1175.

[16] Wu Q,Ying Y M, Zhou D X. Learning rates of Least-Square regularized regression[J].Found Comput Math, 2006(2): 171-192.

[17] Zhou D X.The covering number in learning theory[J].Journal of Complexity, 2002(3): 739-767.

[18] Xu J, Tang Y Y, Zou B, et al.Generalization performance of Gaussian kernels SVMC based on Markov sampling[J].Neural Networks, 2014(5): 40-51.

(責(zé)任編輯趙燕)

Optimal rate for least squaress regularized regression with Markov chain samples

BAI Haijiang, FU Yingxiong，LI Weifu

(Faculty of Mathematics and Statistics, Hubei University, Wuhan 430062, China)

Abstract:We establish the bound on the learning rates of regularization regression based on uniformly ergodic Markov chain samples. We give an error analysis and obtain the optimal learning rateO(m-1) for the least squares regularized regression algorithm based on uniformly ergodic Markov chain samples.

Key words:optimal rate; least squares regularized regression; uniformly ergodic Markov chain

文章編號:1000-2375(2016)03-0326-07

收稿日期:2015-12-17

基金項目：國家自然科學(xué)基金(11371007)資助

作者簡介：白海江(1988-), 男, 碩士生; 李偉夫, 通信作者, 碩士生, E-mail: wfli@student.hubu.edu.cn

中圖分類號:R917

文獻(xiàn)標(biāo)志碼:A

DOI:10.3969/j.issn.1000-2375.2016.04.012