[發(fā)明專利]基于ALMM的L1正則化核學(xué)習(xí)機的分布式訓(xùn)練方法

有效

• 申請?zhí)枺?/td>: 201510294216.8
• 申請日: 2015-06-01
• 公開（公告）號: CN104954973B
• 公開（公告）日: 2019-01-29
• 發(fā)明（設(shè)計）人: 侯義斌;及歆榮;侯翠琴
• 申請（專利權(quán)）人: 北京工業(yè)大學(xué)
• 主分類號: H04W4/70
• 分類號: H04W4/70;H04W84/18
• 代理公司: 北京思海天達知識產(chǎn)權(quán)代理有限公司 11203
• 代理人: 沈波

1.基于ALMM的L1正則化核學(xué)習(xí)機的分布式訓(xùn)練方法，本方法在核學(xué)習(xí)機訓(xùn)練過程中包括三個重要機制；

機制1：節(jié)點本地核學(xué)習(xí)機優(yōu)化問題求解方法；

在節(jié)點本地模型與鄰居節(jié)點間的局部最優(yōu)模型相一致的約束下，利用增廣拉格朗日乘子方法構(gòu)建和求解基于L1正則化的KMSE的分布式訓(xùn)練優(yōu)化問題；

機制2：節(jié)點本地稀疏模型求解；

利用交替方向乘子法對節(jié)點本地的L1正則化KMSE訓(xùn)練優(yōu)化問題進行稀疏模型求解；

機制3：鄰居節(jié)點間的協(xié)作機制；

為求解鄰居節(jié)點間的局部最優(yōu)模型、加快節(jié)點本地模型收斂和減少節(jié)點間數(shù)據(jù)傳輸量，相鄰節(jié)點間以傳輸稀疏模型的方式進行協(xié)作，并將接收到的稀疏模型中攜帶的樣本信息加入到本地樣本集；

基于機制1、機制2和機制3的L1正則化KMSE的分布式訓(xùn)練方法有四個階段，分別是：

1.節(jié)點本地初始化；2.節(jié)點本地稀疏模型求解和發(fā)送；3.節(jié)點接收鄰居節(jié)點發(fā)送過來的稀疏模型，計算局部最優(yōu)模型預(yù)測值，和本地乘子變量結(jié)果值；4.節(jié)點本地模型收斂條件判定；

基于ALMM的L1正則化核學(xué)習(xí)機的分布式訓(xùn)練方法，其是在以下前提條件下進行的：

a.網(wǎng)絡(luò)中每個節(jié)點都有唯一的ID號；

b.網(wǎng)絡(luò)結(jié)構(gòu)穩(wěn)定且連通；

c.網(wǎng)絡(luò)中各節(jié)點僅與其單跳鄰居節(jié)點通信；

d.網(wǎng)絡(luò)中各節(jié)點使用相同的核函數(shù)、相同的核參數(shù)值和正則系數(shù)；

其特征在于：該L1正則化核學(xué)習(xí)機的分布式訓(xùn)練方法的步驟如下：

步驟1：節(jié)點本地關(guān)鍵參數(shù)初始化和本地訓(xùn)練樣本數(shù)據(jù)預(yù)處理

步驟1.1：各節(jié)點初始化網(wǎng)絡(luò)規(guī)模J、鄰居節(jié)點集合B_j、本地訓(xùn)練樣本集合S_j:＝{(x_jn,y_jn),n＝{1,2,…,N_j}},確定核函數(shù)k(x_i,x_j)并初始化核參數(shù)σ和正則系數(shù)λ；

其中，B_j是由節(jié)點j及其鄰居節(jié)點構(gòu)成的集合；x_jn∈R^p是節(jié)點j的第n個訓(xùn)練樣本jn的特征向量，R為實數(shù)集合，p為實數(shù)特征向量維數(shù)，y_jn∈Y:＝{1,-1}是訓(xùn)練樣本jn對應(yīng)的類別標(biāo)簽，N_j是訓(xùn)練樣本數(shù)量；k(x_i,x_j)中x_i和x_j是兩個訓(xùn)練樣本，其作用是計算兩個訓(xùn)練樣本之間的距離，核參數(shù)σ是核函數(shù)中的一個常量參數(shù)，正則系數(shù)λ是L1正則項的一個常量參數(shù)，用于調(diào)節(jié)正則項在整個損失中的比例；

步驟1.2：各節(jié)點利用y＝(x-xmin)/(xmax-xmin)將本地訓(xùn)練樣本的特征信息歸一化到[0，1]區(qū)間；各節(jié)點為歸一后的訓(xùn)練樣本增加標(biāo)識字段node_ID和example_ID以唯一標(biāo)識每個訓(xùn)練樣本，增加發(fā)送標(biāo)識字段is_sended標(biāo)識該樣本是否已經(jīng)發(fā)送過，以避免重復(fù)發(fā)送；

其中，x為訓(xùn)練樣本的某一個特征信息，xmax和xmin分別為訓(xùn)練樣本該特征信息的最大值和最小值，y為訓(xùn)練樣本特征信息x歸一處理后的結(jié)果；

步驟2：節(jié)點本地稀疏模型求解和發(fā)送

步驟2.1：各節(jié)點在本地模型和鄰居節(jié)點間的局部最優(yōu)模型相一致約束下，利用ALMM構(gòu)建和求解基于L1正則化的KMSE的分布式訓(xùn)練優(yōu)化問題，構(gòu)建的優(yōu)化問題形式如式(1)，相應(yīng)的求解迭代形式如式(2)-式(4)；

在式(1)-式(4)中，f_j(x_jn)是節(jié)點j的本地模型對本地第n個樣本的預(yù)測值，為節(jié)點j及其鄰居節(jié)點間的局部最優(yōu)模型對節(jié)點j上第n個樣本的預(yù)測值；式(1)和式(2)中，λ||f_j||₁是對本地模型的L1正則化項，用于本地模型的稀疏求解；式(2)-式(4)中，p_j^k(x_jn)是約束的乘子變量，c為一個正常數(shù)，是約束的增廣系數(shù)；式(3)中，Num(B_j)是包括j在內(nèi)的鄰居節(jié)點數(shù)量；

步驟2.2：各節(jié)點利用核函數(shù)k(x_i,x_j)對本地歸一化后的訓(xùn)練樣本進行核矩陣計算和增廣，得到增廣矩陣K_j；

步驟2.3：各節(jié)點再次利用ADMM對式(2)的優(yōu)化問題進行稀疏模型求解，對應(yīng)的優(yōu)化問題形式如式(5)，求解迭代形式如式(6)-式(8)；

z_j^k+1:＝S_λ/ρ(α_j^k+1+u_j^k) (7)

u_j^k+1:＝u_j^k+α_j^k+1-z_j^k+1 (8)

在式(5)和式(6)中，K_j是本地訓(xùn)練樣本的增廣核矩陣，Y_j本地訓(xùn)練樣本的類別標(biāo)簽向量，I為本地樣本量加1，即N_j+1維的單位矩陣，α_j是要求解的本地訓(xùn)練樣本的權(quán)重向量，z_j是利用ADMM增加的輔助向量，輔助α_j求解；在式(6)-式(8)中，ρ是約束α_j-z_j＝0的增廣系數(shù)，是一個正常數(shù)，u_j為約束α_j-z_j＝0的乘子向量，S_λ/ρ()為軟閾值操作函數(shù)，其定義如式(9)，

步驟2.4：將解α_j^k+1中非零項和對應(yīng)的樣本信息提取出來作為節(jié)點j∈J本地的稀疏模型，如式(10)所示：

步驟2.5：節(jié)點整理本地稀疏模型，如果稀疏模型中訓(xùn)練樣本的is_sended字段為0，表示該樣本還沒有被發(fā)送過，此時需要將該訓(xùn)練樣本的原始特征信息保留在模型中；如果is_sended字段為1，代表該訓(xùn)練樣本的原始特征信息已經(jīng)發(fā)送過，此時只將該樣本的標(biāo)識字段信息保留在模型中；

步驟2.6：節(jié)點將本地整理好的稀疏模型發(fā)送給其單跳鄰居節(jié)點B_j；

步驟3：節(jié)點接收鄰居節(jié)點發(fā)送過來的稀疏模型，計算局部最優(yōu)模型預(yù)測值和本地乘子變量結(jié)果值

步驟3.1：節(jié)點j∈J接收鄰居節(jié)點發(fā)送過來的稀疏模型f_i^k+1(x_i),i∈B_j，并將每個稀疏模型中攜帶的樣本信息不重復(fù)的加入到本地訓(xùn)練樣本集；

步驟3.2：節(jié)點j∈J利用接收到的各稀疏模型對本地訓(xùn)練樣本進行預(yù)測，利用ALMM求解局部最優(yōu)模型預(yù)測值公式式(3)，求出本地訓(xùn)練樣本的局部最優(yōu)模型預(yù)測值

步驟3.3：節(jié)點j∈J本地利用ALMM求解乘子變量公式式(4)，求出節(jié)點本地乘子變量結(jié)果值p_j^k+1(x_j)；

步驟4：節(jié)點本地模型收斂條件判定

步驟4.1：節(jié)點本地判斷模型是否滿足收斂條件，收斂條件為節(jié)點本地樣本集穩(wěn)定并且節(jié)點前后兩次得到的模型相同；當(dāng)所有節(jié)點都滿足收斂條件時，執(zhí)行步驟4.3，否則轉(zhuǎn)步驟4.2；

步驟4.2：節(jié)點本地按照階段2、階段3的順序進行優(yōu)化求解；

步驟4.3：節(jié)點模型收斂f_j^*(x_j)，結(jié)束優(yōu)化求解過程；

最終通過相鄰節(jié)點間的協(xié)作就使每個節(jié)點得到與集中訓(xùn)練方式相當(dāng)?shù)念A(yù)測效果，且得到比集中訓(xùn)練方式更為稀疏的預(yù)測模型，最重要的是可以顯著降低核學(xué)習(xí)機訓(xùn)練過程中的數(shù)據(jù)通信代價。