基于學(xué)習(xí)速率與更新向量的混合云數(shù)據(jù)冗余值迭代算法

張曉麗

(1.東北大學(xué) 機(jī)械工程與自動(dòng)化學(xué)院，遼寧 沈陽 110819;2.長(zhǎng)春師范大學(xué) 數(shù)學(xué)學(xué)院，吉林 長(zhǎng)春 130032)

0 引 言

混合云結(jié)合了私有云與公有云，是一種混合計(jì)算環(huán)境，其中私有云是一種IT組織或內(nèi)部數(shù)據(jù)中心，通常由公司管理和建立，而公有云則是以收費(fèi)模型為依據(jù)，致力于提供軟件服務(wù)、平臺(tái)服務(wù)、基礎(chǔ)設(shè)施服務(wù)的計(jì)算環(huán)境。和公有云計(jì)算環(huán)境相比，混合云計(jì)算環(huán)境的靈活性與安全性更高，能夠以工作負(fù)載為依據(jù)，提供高安全性、低成本、高伸縮性的服務(wù)[1]。當(dāng)出現(xiàn)工作負(fù)載波動(dòng)較為劇烈現(xiàn)象時(shí)，能夠利用公有云資源對(duì)混合云的服務(wù)水平進(jìn)行維持，并強(qiáng)化私有云的能力。當(dāng)前在混合云的應(yīng)用過程中所面臨的最大問題就是混合云數(shù)據(jù)的冗余問題，目前的混合云數(shù)據(jù)冗余值較多，因此，混合云數(shù)據(jù)冗余值迭代問題備受關(guān)注[2]。

吳繼康等[3]對(duì)混合云環(huán)境中多個(gè)用戶數(shù)據(jù)進(jìn)行研究，完善了用戶數(shù)據(jù)存儲(chǔ)機(jī)制，提供了數(shù)據(jù)共享解決方案，為混合云數(shù)據(jù)的研究奠定了基礎(chǔ)，但并未對(duì)云數(shù)據(jù)深入研究；在此基礎(chǔ)上，陳建平等[4]提出一種冗余值迭代算法，針對(duì)海量數(shù)據(jù)中的冗余值迭代問題進(jìn)行研究，插入一種新的權(quán)重因子，構(gòu)建迭代函數(shù)參數(shù)向量，完成冗余值迭代研究，該方法獲得了一定的研究成果，但數(shù)據(jù)收斂和平均回報(bào)值方面有待加強(qiáng)；郭瑞等[5]重點(diǎn)分析了數(shù)據(jù)冗余問題，提出了基于一階謂詞公式去除冗余數(shù)據(jù)的方法，利用一階謂詞公式表示數(shù)據(jù)關(guān)聯(lián)規(guī)則，構(gòu)建鄰接矩陣，刪除其中的冗余規(guī)則，該方法的數(shù)據(jù)冗余研究效果較好，但忽略了數(shù)據(jù)迭代這一問題，導(dǎo)致研究結(jié)果收斂性不高；惠宇等[6]提出了數(shù)據(jù)驅(qū)動(dòng)的最優(yōu)迭代學(xué)習(xí)控制方法，通過迭代擴(kuò)張狀態(tài)觀測(cè)器詳細(xì)分析了參數(shù)迭代規(guī)律，獲取了較好的數(shù)據(jù)驅(qū)動(dòng)控制方法，但收斂速度較低；眾多國(guó)外學(xué)者也研究了此問題，S.Nepal等[7]分析了混合云中大數(shù)據(jù)處理問題，給出提高混合云數(shù)據(jù)可信度的方法，保障數(shù)據(jù)的完整性和保密性；R.W.Allmendinger等[8]分析了以移動(dòng)設(shè)備為載體，分析使用過程中產(chǎn)生的數(shù)據(jù)冗余和數(shù)據(jù)不確定性問題，通過海量數(shù)據(jù)采集與處理，消除數(shù)據(jù)集中的冗余數(shù)據(jù)和不確定數(shù)據(jù)，但該方法的數(shù)據(jù)收斂速度不高；ZHENG S[9]提出支持向量數(shù)據(jù)描述(SVDD)模式分析模型，SVDD通過求解二次規(guī)劃問題進(jìn)行迭代；I.I.Rypina等[10]介紹了一種利用漂移器數(shù)據(jù)研究示蹤劑擴(kuò)散的多迭代統(tǒng)計(jì)方法，該方法通過使用一個(gè)簡(jiǎn)單的迭代過程，最佳地利用了可用的漂移數(shù)據(jù)，但迭代過程中數(shù)據(jù)的收斂效果不佳。

上述算法在混合云數(shù)據(jù)冗余值處理中，平均回報(bào)值較低且收斂速度控制效果較差。針對(duì)此問題，本文提出一種基于學(xué)習(xí)速率與更新向量的混合云數(shù)據(jù)冗余值迭代算法，構(gòu)建混合云數(shù)據(jù)冗余值值函數(shù)，基于深度學(xué)習(xí)中學(xué)習(xí)速率要求，獲取值函數(shù)的穩(wěn)定值，計(jì)算值函數(shù)穩(wěn)定值向量，結(jié)合哈希表完成混合云數(shù)據(jù)冗余值的迭代研究，并驗(yàn)證算法的平均回報(bào)值以及收斂速度。

1 基于學(xué)習(xí)速率與更新向量的混合云數(shù)據(jù)冗余值迭代算法設(shè)計(jì)

1.1 基于學(xué)習(xí)速率獲取值函數(shù)穩(wěn)定值

基于深度學(xué)習(xí)中學(xué)習(xí)速率要求，獲取混合云數(shù)據(jù)冗余值值函數(shù)的穩(wěn)定值。將混合云數(shù)據(jù)冗余值值函數(shù)視為深度學(xué)習(xí)中的學(xué)習(xí)速率，即將其視為一個(gè)常數(shù)，通過新參數(shù)的引進(jìn)與反復(fù)訓(xùn)練以獲取值函數(shù)的穩(wěn)定值。在深度學(xué)習(xí)中，學(xué)習(xí)速率需要接近0，梯度才不會(huì)上升，學(xué)習(xí)速率還要盡可能大，梯度才不會(huì)增加，在混合云數(shù)據(jù)冗余值迭代算法中引入深度學(xué)習(xí)這一概念，也就是混合云數(shù)據(jù)冗余值函數(shù)的數(shù)值需要接近0才能提升迭代算法的學(xué)習(xí)速率，值函數(shù)的值還需要接近1，才能保證迭代算法的收斂性。為了滿足這兩種需求，需要引入新參數(shù)并進(jìn)行反復(fù)訓(xùn)練。其中混合云數(shù)據(jù)冗余值值函數(shù)的公式為

(1)

式中：φ為混合云數(shù)據(jù)冗余值值函數(shù)；ΔWd，ΔWrg分別為混合云數(shù)據(jù)冗余值的2個(gè)權(quán)重向量。

在混合云數(shù)據(jù)冗余值的迭代中，當(dāng)0≤φ<1時(shí)，才能保證迭代算法的收斂。

權(quán)重向量ΔWd與ΔWrg的夾角需要滿足銳角條件，將參數(shù)k代入云數(shù)據(jù)冗余值值函數(shù)，計(jì)算φ值大小。計(jì)算φ值的分母，將分母與0作比較，當(dāng)分母的值為0時(shí)，φ值即為0，而當(dāng)分母的值不為0時(shí)，利用引進(jìn)的參數(shù)對(duì)φ值的分子進(jìn)行計(jì)算，計(jì)算完畢后驗(yàn)證φ值是否滿足0≤φ<1條件，并對(duì)值函數(shù)參數(shù)進(jìn)行計(jì)算：

ΔWr=k(1-φ)ΔWd+φWrg，

(2)

式中，ΔWr為值函數(shù)參數(shù)[11]。

接著利用值函數(shù)參數(shù)對(duì)權(quán)重向量ΔWd與ΔWrg進(jìn)行更新，并在更新中引進(jìn)一個(gè)新的參數(shù)μ，該參數(shù)為一個(gè)極小的正數(shù)，被稱為遺忘因子，引入μ后，權(quán)重向量ΔWd與ΔWrg的更新結(jié)果為

Wd=(1-μ)ΔWd-μk2，

(3)

Wrg=(1-μ)ΔWrg-μk2。

(4)

通過權(quán)重向量ΔWd與ΔWrg的更新加速了迭代算法的收斂速率，獲得了值函數(shù)的穩(wěn)定值，即

(5)

1.2 構(gòu)建值函數(shù)更新向量

利用獲取的值函數(shù)穩(wěn)定值對(duì)值函數(shù)更新向量進(jìn)行構(gòu)建，獲得混合云數(shù)據(jù)冗余值的期望輸出，計(jì)算值函數(shù)穩(wěn)定值向量，利用批量更新的方式獲取新權(quán)值，利用新的權(quán)值處理值函數(shù)向量，獲取值函數(shù)更新向量。

利用逼近替代函數(shù)查詢表對(duì)混合云數(shù)據(jù)冗余值進(jìn)行逼近替代，即

(6)

式中：V(x)為混合云數(shù)據(jù)冗余值;x′為x的后續(xù)狀態(tài);α為逼近替代函數(shù)值;R為立即獎(jiǎng)賞;γ為逼近替代系數(shù)。

利用公式(5)可以使混合云數(shù)據(jù)冗余值V(x)逐漸接近右邊的值[12]。接著對(duì)混合云數(shù)據(jù)冗余值V(x)進(jìn)行樣本訓(xùn)練，獲得混合云數(shù)據(jù)冗余值期望輸出P,

P=max 〈R+γV(x′)〉,

(7)

其中，P為混合云數(shù)據(jù)冗余值的期望輸出[13]。V(x)與V(x′)都是跟值函數(shù)φ相關(guān)的函數(shù)，通過樣本訓(xùn)練能夠調(diào)整值函數(shù)φ的梯度，使混合云數(shù)據(jù)冗余值V(x)能夠無限接近期望輸出值[14]。

獲得混合云數(shù)據(jù)冗余值的期望輸出P后，對(duì)值函數(shù)穩(wěn)定值φ的向量進(jìn)行計(jì)算：

式中：ΔW為值函數(shù)φ的向量;W為混合云數(shù)據(jù)冗余值更新結(jié)果[15]。

利用批量更新的方式對(duì)值函數(shù)向量的權(quán)值增量進(jìn)行改變，從而產(chǎn)生新的權(quán)值λ，利用新的權(quán)值處理值函數(shù)向量，獲取新的全局向量W，從而完成值函數(shù)更新向量的構(gòu)建，即

(9)

逼近替代會(huì)導(dǎo)致迭代算法的收斂加快，而批量更新方式會(huì)導(dǎo)致迭代算法的發(fā)散，二者能夠相互抵消，如圖1所示[16]。

圖1 收斂與發(fā)散的抵消過程

1.3 混合云數(shù)據(jù)冗余值迭代

利用值函數(shù)更新向量進(jìn)行混合云數(shù)據(jù)冗余值迭代，進(jìn)行混合云數(shù)據(jù)冗余值迭代研究[17]。

利用 Bellman 冗余求出混合云數(shù)據(jù)值函數(shù)更新向量的均方差E,

(10)

其中，E為混合云數(shù)據(jù)冗余值的均方差[18],而混合云數(shù)據(jù)冗余值均方差的權(quán)值增量則為

(11)

式中，ΔE為混合云數(shù)據(jù)冗余值均方差的權(quán)值增量[19]。

根據(jù)上述獲取的權(quán)值增量，結(jié)合哈希表完成迭代研究，具體迭代步驟如下。

(1)通過鏈地址法建立規(guī)模為m的哈希表，獲取依次進(jìn)入哈希表的項(xiàng)，可通過下述過程獲?。?/p>

針對(duì)首個(gè)進(jìn)入哈希表的項(xiàng)有

W1=(m-1)/m，

(12)

針對(duì)第二個(gè)進(jìn)入哈希表的項(xiàng)有

(13)

針對(duì)第三個(gè)進(jìn)入哈希表的項(xiàng)有

(14)

(2)混合云數(shù)據(jù)增值向量獲取。通常采用簡(jiǎn)單的散列手段即可獲取很好的防沖突效果[20-21]。但數(shù)據(jù)集保存在不同距離的存儲(chǔ)節(jié)點(diǎn)中，存在一定的差異，本節(jié)通過數(shù)據(jù)集存儲(chǔ)使用強(qiáng)度D(x)與數(shù)據(jù)節(jié)點(diǎn)迭代概率P(x)完成冗余值迭代，提高迭代質(zhì)量。在獨(dú)立存儲(chǔ)節(jié)點(diǎn)中完成數(shù)據(jù)集流接收，混合云數(shù)據(jù)集流符合指數(shù)為λ的泊松分布，同時(shí)存儲(chǔ)使用強(qiáng)度符合同一指數(shù)的泊松分布[22]。則數(shù)據(jù)集存儲(chǔ)使用強(qiáng)度D(x)的增值向量E[D(x)]符合

(W1+W2+W3),

(15)

(3)結(jié)合增值向量，利用權(quán)值增量獲取混合云數(shù)據(jù)冗余值迭代函數(shù),即

從而實(shí)現(xiàn)混合云數(shù)據(jù)冗余值迭代算法研究。

2 實(shí) 驗(yàn)

為了檢測(cè)本文提出基于學(xué)習(xí)速率與更新向量的混合云數(shù)據(jù)冗余值迭代算法的有效性，將本文算法與文獻(xiàn)[4-5，8-9]算法應(yīng)用于GridWorld問題中。GridWorld問題遵從均勻隨機(jī)決策中對(duì)所有行動(dòng)進(jìn)行迭代的原理，可以對(duì)迭代方法的收斂性能進(jìn)行驗(yàn)證。

GridWorld問題指的是格子世界問題，主要包括2個(gè)類型，分別是4×5格子和10×10格子。4×5格子包含1個(gè)起始狀態(tài)，1個(gè)終止?fàn)顟B(tài)，2個(gè)陷阱狀態(tài)。10×10格子包含1個(gè)起始狀態(tài)，1個(gè)終止?fàn)顟B(tài)。

目標(biāo)任務(wù)遷移至不同狀態(tài)時(shí)，所得獎(jiǎng)賞大小不同，在到達(dá)終止?fàn)顟B(tài)時(shí)，立即獎(jiǎng)賞最大，在到達(dá)陷阱狀態(tài)時(shí)，立即獎(jiǎng)賞最小。

2.1 實(shí)驗(yàn)參數(shù)

實(shí)驗(yàn)參數(shù)如表1所示。

2.2 實(shí)驗(yàn)過程

基于MATLAB實(shí)驗(yàn)平臺(tái)對(duì)混合云數(shù)據(jù)冗余值迭代算法進(jìn)行加載，實(shí)驗(yàn)數(shù)據(jù)來源于(hybrid cloud database management，HDM)，設(shè)定本次實(shí)驗(yàn)的最大情節(jié)數(shù)為200，在情節(jié)不同的情況下，對(duì)混合云數(shù)據(jù)冗余值迭代算法的總回報(bào)值進(jìn)行計(jì)算，從而獲得算法的平均回報(bào)值(在起始狀態(tài)到終止?fàn)顟B(tài)的過程中，目標(biāo)任務(wù)所獲得的獎(jiǎng)賞和回報(bào)值)。為了保證實(shí)驗(yàn)的有效性，使用文獻(xiàn)[4-5，8-9]算法與本文提出基于學(xué)習(xí)速率與更新向量的混合云數(shù)據(jù)冗余值迭代算法進(jìn)行比較，觀察實(shí)驗(yàn)結(jié)果，比較各個(gè)算法的平均回報(bào)值、樣本計(jì)算耗時(shí)與時(shí)間步數(shù)。

表1 實(shí)驗(yàn)參數(shù)

2.3 實(shí)驗(yàn)結(jié)果

文獻(xiàn)[4-5，8-9]算法和基于學(xué)習(xí)速率與更新向量的混合云數(shù)據(jù)冗余值迭代算法的平均回報(bào)值對(duì)比如圖2所示。

圖2 4×5 GridWorld問題中不同算法平均回報(bào)值對(duì)比

通過圖2可知，文獻(xiàn)[4]算法在第161個(gè)情節(jié)左右達(dá)到最優(yōu)收斂；文獻(xiàn)[5]算法在第130個(gè)情節(jié)左右達(dá)到最優(yōu)收斂；文獻(xiàn)[8]算法在第130個(gè)情節(jié)左右達(dá)到最優(yōu)收斂；文獻(xiàn)[9]算法在第155個(gè)情節(jié)左右達(dá)到最優(yōu)收斂。上述4種算法的平均回報(bào)值不超過0.5，但本文基于學(xué)習(xí)速率與更新向量的混合云數(shù)據(jù)冗余值迭代算法的最大平均回報(bào)值約為0.96，該算法在第80個(gè)情節(jié)左右達(dá)到最優(yōu)收斂。通過比較可知，基于學(xué)習(xí)速率與更新向量的混合云數(shù)據(jù)冗余值迭代算法的平均回報(bào)值最高，并且收斂速度也最快。

為驗(yàn)證本文算法在大規(guī)模動(dòng)作中的適應(yīng)性問題，更換格子類型，將4×5格子更換為10×10格子，在此種情況下計(jì)算回報(bào)值，不同算法的對(duì)比結(jié)果如圖3所示。相比其他幾種算法，基于學(xué)習(xí)速率與更新向量的迭代算法具有較好的收斂性，在情節(jié)數(shù)為90左右時(shí)，該算法趨于收斂，之后的每個(gè)情節(jié)均處于終止?fàn)顟B(tài)，證明該算法具有較高的穩(wěn)定性。

圖3 10×10 GridWorld問題中不同算法平均回報(bào)值對(duì)比

在不同空間維度內(nèi)，算法性能亦不同，為驗(yàn)證算法性能，在不同空間維度的格子問題中，計(jì)算幾種不同算法的耗時(shí)情況，由耗時(shí)長(zhǎng)短判定算法性能。由表2可以看出，在相同空間維度下，本文算法耗時(shí)較少，且隨著空間維度的增加，耗時(shí)始終低于其他算法。

幾種算法在不同情節(jié)到達(dá)終止?fàn)顟B(tài)所需的步長(zhǎng)對(duì)比如圖4所示。從圖4可以看出，在情節(jié)數(shù)為50左右時(shí)，本文迭代算法已到達(dá)收斂狀態(tài)，隨著情節(jié)數(shù)的不斷增加，可以看出本文迭代算法步數(shù)較少，迭代較為穩(wěn)定，具有更快的收斂速度。

3 結(jié) 語

本文提出基于學(xué)習(xí)速率與更新向量的混合云數(shù)據(jù)冗余值迭代算法，由值函數(shù)更新向量構(gòu)建，實(shí)現(xiàn)了混合云數(shù)據(jù)冗余值的迭代。通過實(shí)驗(yàn)結(jié)果可知，基于學(xué)習(xí)速率與更新向量的迭代算法在引入權(quán)重因子與遺忘因子后，加快了迭代速率，使收斂速度得到保證，迭代算法穩(wěn)定性能得到了保證。該算法適用于較大規(guī)?？臻g維度問題，為進(jìn)一步提高迭代穩(wěn)定性，使適用范圍更為廣泛，提高值函數(shù)參數(shù)更新向量的速率是下一步的研究方向。

表2 不同算法在不同GridWorld問題中耗時(shí)對(duì)比

圖4 不同算法時(shí)間步數(shù)對(duì)比