非一致分布下的在線分位數回歸算法

楊鵬偉

(武漢大學數學與統計學院, 湖北武漢 430072)

1 引言

1.1 不同分布下的樣本

假設輸入空間(X,d)是Rn中的緊度量空間, 輸出空間Y ?R, 樣本空間Z = X ×Y.非一致分布下, 每一學習時刻t = 1,2,··· 產生的樣本點zt= (xt,yt) ∈Z 服從聯合概率分布ρ(t)(x,y), (x,y) ∈Z, 這里序列不一定相同. 在Smale, Zhou[1]提出的學習框架下, 假設在X 上的邊緣分布序列以多項式速度收斂于H?lder 空間Cs(X)(0

定義1.1稱概率分布序列以多項式速度收斂于(Cs(X))?中的概率分布ρX. 如果存在C >0,b>0 使得

由對偶空間(Cs(X))?的定義, 條件(1.1)等價于

指數b 衡量不同分布的差異程度, 當b=∞時, 條件(1.1)是獨立同分布.

對于滿足衰減條件(1.1)的實際情況已在文獻[1, 3]有詳細討論. 例如, 真實的抽樣分布ρX被噪聲干擾并且隨著時間t 增加而噪聲水平下降, 那么在不同時刻對應的抽樣概率分布收斂于ρX. 另外, 通過迭代和隨機密度核形成的積分算子, 反映了由動力系統誘導出不同分布的表現形式. 這些例子都說明研究滿足(1.1)衰減的分布是具有實際應用性的.

1.2 分位數回歸

對于任意的0<τ <1, 定義隨機變量Y 的τ 分位數函數Q(τ)為

其中F(y)是Y 的分布函數. Koenker, Bassett[4]提出線性分位數回歸理論, 擴展了經典的最小二乘回歸. Koenker[5]進一步提出分位數回歸可提供更多關于因變量的分布信息, 例如: 長尾性、厚尾性、多峰性. 分位數回歸描述因變量的條件分布, 不僅僅分析因變量的條件期望,并且對不同τ 刻畫了概率分布的具體性質.

在學習理論框架下, ρ 是Z 上的一個Borel 概率測度. 給定x ∈X 時, ρx(y),y ∈Y 是ρ的條件概率分布. 分位數回歸的目標函數fρ,τ(x)在x 的值定義為: ρx(·)的τ - 分位數是v,即存在v ∈Y 滿足

1.3 在線分位數回歸算法

再生核Hilbert 空間(RKHS)是由Mercer 核K :X×X →R 誘導出來的,K 是一個連續對稱函數,并且對于任意有限點集{x1,x2,··· ,xl}?X 生成的矩陣是半正定的. 由函數集{Kx=K(x,·):x ∈X}張成的完備線性閉包空間RKHS 記為HK(Aronszajn,1950[7]),記內積為= K(x,y). 在線算法也稱隨機梯度下降算法(SGD) 與批次算法中樣本一次性傳給機器不同, 在線算法的訓練樣本是按時間t 順序依次傳送給機器, 對算法不斷修正, 提高學習效率. 在線算法由于低復雜度, 在流式數據和大規模計算中有廣泛的應用. 具體可參考文獻[8].

定義1.2與RKHS 有關的在線分位數回歸算法定義為

其中t 是學習時間, λt>0 稱為正則參數, ηt>0 是步長.

在線算法(1.6)中, 正則參數λt隨著學習時間t 變化并且當λt≡λ1時, λt不會隨著步數t 變化而變化, 此時稱(1.6)為不完全在線算法.

2 非一致分布下在線分位數回歸的誤差

高斯函數在統計學領域, 用于表述正態分布; 在信號處理領域, 用于定義高斯濾波器; 在圖像處理領域, 二維高斯核函數常用于高斯模糊; 在數學領域, 主要是用于解決熱力方程和擴散方程. 高斯核函數作為最常用的徑向基函數, 在支持向量機等算法中的應用可以將數據映射到高維甚至無窮維. 由于高斯核具有良好的性質和應用廣泛, 因此將高斯核應用于以下與中位數回歸有關的在線算法(1.6)中.

對于f :X →R 的泛化誤差定義為

定理2.1假設以下假設均成立

1. RKHS HK由高斯函數產生;

5. ?x ∈X, 條件分布ρx(·)是區間[fρ(x)?1,fρ(x)+1]上的一致分布.

注1該定理反應了中位數回歸的在線算法收斂速度, (2.1)式說明了在線算法(1.6)在HK的收斂性, 稱為強收斂; 而結果(2.2)稱為算法的平均誤差. 由范數關系知道本定理結果(2.1)和(2.2)是合理的. 雖然本定理是考慮τ =, 但是從后面的證明過程知道本定理結果可以推廣到任意0<τ <1, 只需要修改常數?C1和?C2.

注2在線算法(1.6)的誤差估計分為抽樣誤差和逼近誤差兩部分, 其中抽樣誤差是本文的主要貢獻, 將在定理2.3 中給出; 逼近誤差由HK空間的復雜度和數據的分布ρ 決定. 假設5 采用一致分布估計逼近誤差. 事實上本定理適用于其他更一般的條件分布, 為了簡化本定理, 不再進一步討論. 具體可參考文獻[2, 3].

注3當b=∞, (2.1)和(2.2)式反映了數據抽樣z是獨立同分布的情況. 另外, 我們看到時, 本定理推導出無稀疏性的在線分位數回歸算法的收斂階, 可以通過調節的值控制算法的稀疏性同時不影響算法的收斂率.

2.1 抽樣誤差的估計

定義2.2對于λ>0, 正則化函數定義為

逼近誤差D(λ)定義為

定理2.3如果以下假設成立

1. 核函數K 與定理2.1 相同;

3. 分布{ρx:x ∈X}在(Cs(X))?中是Lipschitz s 的, 即存在一個常數使得

4. 逼近誤差滿足多項式衰減如下

令

則有

其中

CK,ρ,b,β是獨立于T 的一個常數且在證明中給出.

證本定理的證明借助了Hu,Zhou[3]的證明思想. 以下給出證明的主要步驟, 更詳細的過程參見Hu,Zhou[3]的定理26. 證明分為三個步驟.

第一步存在常數κ2s>0,

由K(x,x)=K(u,u)=1, 得

第二步由Ying,Zhou[8]引理3 知

其中

因此需要估計?t的上界(參考文獻[3] ). 不難證明存在常數使得. 根據關于第二變量的一階Taylor 展開, 可知

這里

將估計(2.9)式代入(2.8)式得

第三步根據, 知必然存在常數使得同時,注意到當, 可以引用文獻[9] 中引理3(b), 得到

所以用文獻[3] 定理20 的結果, 得到

將上述估計插入(2.10)式, 并按t=T,··· ,1 順序進行迭代, 得到本定理結論.

2.2 定理2.1 的證明

證將誤差分解為三項:

首先, 根據條件5 和在文獻[10]例6 知道, 在正則條件下

這里θ?:=min{2 ?2γ ?2α,α ?γ,b ?2γ}.

根據以上推導得到