鄒智康,羅元

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

1.引言

隨著移動(dòng)互聯(lián)網(wǎng)技術(shù)的迅速發(fā)展,數(shù)據(jù)信息安全問(wèn)題逐漸為人們所重視.現(xiàn)實(shí)生活中,數(shù)據(jù)的存儲(chǔ)方式往往是分散的,由于數(shù)據(jù)傳輸成本以及機(jī)器存儲(chǔ)的限制,互聯(lián)網(wǎng),金融,電子商務(wù)等行業(yè)會(huì)按區(qū)域分散設(shè)置服務(wù)器收集和存儲(chǔ)數(shù)據(jù).如何實(shí)現(xiàn)數(shù)據(jù)在不出本地機(jī)的前提下完成聯(lián)合建模是當(dāng)下亟待解決的技術(shù)性難題.而分布式計(jì)算是解決此問(wèn)題的有效途徑之一,并且由于其高可靠,可容錯(cuò)和易擴(kuò)展的天然優(yōu)勢(shì),結(jié)合大數(shù)據(jù)時(shí)代背景,在高維回歸問(wèn)題中極具應(yīng)用前景.

至今為止,衍生出了許多分布式計(jì)算方法.比如說(shuō),文[1-2]通過(guò)平均不同本地計(jì)算機(jī)上的結(jié)果來(lái)估計(jì)實(shí)際參數(shù).Jordan等[3]開(kāi)發(fā)了一種通信有效的替代似然函數(shù)方法,即CLS(Communication-efficient Surrogate Likelihood).CLS可用于低維模型參數(shù)估計(jì),高維正則估計(jì)和貝葉斯推斷.WANG等[4]通過(guò)在不同的本地機(jī)上使用梯度信息解決?1正則化M估計(jì)問(wèn)題并提高了計(jì)算效率.

另一方面,高維稀疏條件下的特征篩選和參數(shù)估計(jì)一直是統(tǒng)計(jì)相關(guān)學(xué)科關(guān)注的熱點(diǎn)之一.其中,懲罰方法扮演著重要的角色.Tibshirani[5]提出了?1正則化方法,即Lasso(The Least Absolute Shrinkage and Selectionator operator)方法.然而Lasso方法通常會(huì)過(guò)度壓縮較大的系數(shù),從而導(dǎo)致估計(jì)有偏差,因此統(tǒng)計(jì)學(xué)家考慮使用非凸懲罰,比如,FAN和LI[6]提出的SCAD(The Smoothly Clipped Absolute Deviation)方法以及ZHANG[7]提出的MCP(The Minimax Concave Penalty)方法都是解決此類(lèi)問(wèn)題的代表性成果.但是,在解超高維問(wèn)題,尤其當(dāng)維度p是樣本n的指數(shù)級(jí)時(shí),即p=O(exp(n)),正則化方法存在不穩(wěn)定不收斂等問(wèn)題.為此,HUANG[8]提出了交替選擇支撐集并在支撐集上估計(jì)參數(shù)的SDAR方法來(lái)解決?0懲罰問(wèn)題.SDAR方法是基于?0正則化最小二乘問(wèn)題的KKT條件所提出來(lái)的,具有收斂快,精度高的優(yōu)點(diǎn),且可以估計(jì)出真實(shí)的支撐集并得到參數(shù)的Oracle估計(jì).本文在SDAR算法的基礎(chǔ)上,提出了一種分布式的SDAR方法,簡(jiǎn)記為GDSDAR.在GDSDAR算法中,我們利用梯度下降法來(lái)解決SDAR算法中一系列的最小二乘問(wèn)題,其中梯度信息的傳遞保證了在聯(lián)合建模過(guò)程中原始數(shù)據(jù)的私密性,同時(shí)滿(mǎn)足高維稀疏計(jì)算以及數(shù)據(jù)安全的要求.

2.問(wèn)題簡(jiǎn)介

3.實(shí)驗(yàn)結(jié)果與分析

由表3.1結(jié)果分析可知,其他參數(shù)保持不變,隨著樣本總量N的增加,三種算法的相對(duì)誤差(RE)值的變化沒(méi)有統(tǒng)一趨勢(shì),但在每種情形下,GDSDAR算法的精準(zhǔn)度都是最優(yōu)的.對(duì)于正確指標(biāo)覆蓋率ICR,LASSO與其他兩種方法相比,覆蓋率最小,SCAD方法在樣本量偏低時(shí)表現(xiàn)最好,而當(dāng)樣本總量N增加到一定程度后,GDSDAR方法的ICR指標(biāo)最優(yōu).此外,從計(jì)算時(shí)間的角度分析,三種算法運(yùn)行所需的平均時(shí)長(zhǎng)會(huì)隨著樣本總量N的增加而延長(zhǎng).但是在每一種情況下,GDSDAR算法的平均時(shí)長(zhǎng)最短且波動(dòng)幅度與另外兩種算法相近.綜上所述,GDSDAR算法在每種情形下都有著最好的精準(zhǔn)度和最高的計(jì)算效率,且當(dāng)樣本總量偏大時(shí),正確指標(biāo)覆蓋率表現(xiàn)更優(yōu).

表3.1 不同樣本總量N下三種算法的比較

根據(jù)表3.2中的數(shù)據(jù)分析可知,在其他參數(shù)保持不變情況下,隨著稀疏度s的不斷增大,三種方法中只有GDSDAR結(jié)果的RE值在不斷下降,始終保持著最高的精準(zhǔn)度,而另外兩種方法的RE值則不斷增加,與GDSDAR的精度差距逐漸拉大,說(shuō)明我們的方法對(duì)中等稀疏問(wèn)題仍然有效.至于正確指標(biāo)覆蓋率,GDSDAR和SCAD方法隨著s值的增加,ICR指標(biāo)都穩(wěn)步提升,一度達(dá)到99%的準(zhǔn)確率,LASSO方法的ICR指標(biāo)在大幅降低,從一開(kāi)始的96.72%陡降至62.67%,說(shuō)明LASSO方法不適用于中等稀疏問(wèn)題.綜上所述,在保證較高指標(biāo)覆蓋率的前提下,GDSDAR擁有更高的精準(zhǔn)度,且在稀疏度K較大時(shí),表現(xiàn)更好.

表3.2 不同稀疏度s下三種算法結(jié)果比較

分析表3.3數(shù)據(jù)可知,其他參數(shù)保持不變,當(dāng)數(shù)據(jù)相關(guān)性ρ變高時(shí),GDSDAR、LASSO結(jié)果的相對(duì)誤差都在不斷降低,而SCAD結(jié)果的相對(duì)誤差則在不斷增大,從總體上看,GDSDAR算法的RE值最小,精準(zhǔn)度最高.對(duì)于正確指標(biāo)覆蓋率,GDSDAR、SCAD兩種方法在相關(guān)性變高時(shí),ICR指標(biāo)逐漸增大,而LASSO方法表現(xiàn)呈下滑趨勢(shì).相比而言,GDSDAR在低相關(guān)性條件下更有優(yōu)勢(shì),SCAD在高相關(guān)性條件下會(huì)略勝一籌.綜上所述,GDSDAR算法在相關(guān)性變動(dòng)的情況下,精準(zhǔn)度都有良好的保證,且正確指標(biāo)覆蓋率較高.

表3.3 不同相關(guān)程度ρ下三種算法結(jié)果比較

4.結(jié)語(yǔ)

本文提出了一種求解分布式情形下高維稀疏參數(shù)估計(jì)的算法GDSDAR.創(chuàng)新點(diǎn)主要體現(xiàn)在兩個(gè)方面.一方面,GDSDAR方法可以解決分散存儲(chǔ)數(shù)據(jù)的聯(lián)合建模問(wèn)題,在運(yùn)算過(guò)程中,發(fā)生信息交互的僅僅是梯度向量而非數(shù)據(jù)本身,所以能夠保證本地?cái)?shù)據(jù)的私密性,考慮到當(dāng)今社會(huì)對(duì)于信息安全的重視程度,這一特性使得GDSDAR算法擁有廣泛的應(yīng)用前景.另一方面,在高維稀疏的假定下,GDSDAR算法通過(guò)對(duì)?0約束最小化KKT條件的改進(jìn),交替選擇支撐集的方式并在支撐集上估計(jì)參數(shù).實(shí)驗(yàn)表明,相較于經(jīng)典的?1正則化方法,GDSDAR無(wú)論在精準(zhǔn)度或是指標(biāo)正確覆蓋率兩方面都有著優(yōu)異的表現(xiàn),穩(wěn)定性也十分出色.

除了上述的創(chuàng)新點(diǎn),GDSDAR算法仍然存在一些后續(xù)的問(wèn)題.例如在每次運(yùn)行算法前,我們需要依據(jù)經(jīng)驗(yàn)事先確定模型大小,然后據(jù)此得到相應(yīng)的模型.在接下來(lái)的研究中,我們考慮運(yùn)用交叉驗(yàn)證或者統(tǒng)計(jì)學(xué)中的HBIC指標(biāo)輔助判斷合適的模型大小,這種改進(jìn)將會(huì)使GDSDAR算法更適用于真實(shí)數(shù)據(jù)的建模計(jì)算.