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

白海江, 付應雄, 李偉夫

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

?

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

白海江, 付應雄, 李偉夫

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

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

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

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

1預備知識

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

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

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

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

(1)

這里β1=1-ν1.

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

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

找到目標函數fρ[12]

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

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

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

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

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

文獻[12]中給出等式

(2)

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

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

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

(3)

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

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

(4)

通過考慮推廣誤差:

(5)

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

(6)

(7)

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

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

(8)

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

由其可得，當λ>0時, 有

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

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

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

D(λ)≤c1λγ

(9)

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

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

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

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

(10)

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

2主要工具

為了得到主要結果, 本文中引入一些關于馬氏鏈的集中不等式.

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

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

3主要結論

基于前期的準備知識, 本文中的主要結論為:

其中

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

這里

4主要結論的證明

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原則和覆蓋數來確定該項的界. 由引理2可知, 對函數集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. 根據引理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)式帶入上式, 令不等式右邊等于δ, 則有

因此

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

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

(14)

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

(15)

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

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

(16)

因此

(17)

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

(18)

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

因此

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

(19)

代入不等式(18), 有

5參考文獻

[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.

(責任編輯趙燕)

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

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

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

中圖分類號:R917

文獻標志碼:A

DOI:10.3969/j.issn.1000-2375.2016.04.012