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

有效

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

1.基于并行投影方法的L1正則化核學(xué)習(xí)機(jī)的分布式訓(xùn)練方法，本方法在核學(xué)習(xí)機(jī)訓(xùn)練過程中包括四個(gè)重要機(jī)制；

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

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

機(jī)制2：節(jié)點(diǎn)本地稀疏模型求解；

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

機(jī)制3：鄰居節(jié)點(diǎn)間的協(xié)作機(jī)制；

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

機(jī)制4：節(jié)點(diǎn)模型一致性；

當(dāng)各節(jié)點(diǎn)都收斂到穩(wěn)定模型后，僅依靠相鄰節(jié)點(diǎn)間傳輸稀疏模型的方式進(jìn)行協(xié)作，使每個(gè)節(jié)點(diǎn)上都接收到網(wǎng)絡(luò)中所有其他節(jié)點(diǎn)的模型，然后各節(jié)點(diǎn)本地對所有模型進(jìn)行平均以得到一致模型；

基于機(jī)制1、機(jī)制2、機(jī)制3和機(jī)制4的L1正則化核學(xué)習(xí)機(jī)的分布式訓(xùn)練方法有五個(gè)階段，分別是：

1.節(jié)點(diǎn)本地初始化；2.節(jié)點(diǎn)本地稀疏模型求解和發(fā)送；3.節(jié)點(diǎn)接收鄰居節(jié)點(diǎn)發(fā)送過來的稀疏模型，計(jì)算局部最優(yōu)模型預(yù)測值；4.節(jié)點(diǎn)本地模型收斂條件判定；5.節(jié)點(diǎn)模型一致性；

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

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

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

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

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

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

步驟1：節(jié)點(diǎn)本地初始化

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

其中，B_j是由節(jié)點(diǎn)j及其鄰居節(jié)點(diǎn)構(gòu)成的集合；x_jn∈R^p是節(jié)點(diǎn)j的第n個(gè)訓(xùn)練樣本jn的特征向量，p為特征向量維數(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是兩個(gè)訓(xùn)練樣本，其作用是計(jì)算兩個(gè)訓(xùn)練樣本之間的距離，核參數(shù)σ是核函數(shù)中的一個(gè)常量參數(shù)，正則系數(shù)λ是L1正則項(xiàng)的一個(gè)常量參數(shù)，用于調(diào)節(jié)正則項(xiàng)在整個(gè)損失中的比例；

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

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

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

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

在式(1)-式(3)中，f_j(x_jn)是節(jié)點(diǎn)j的本地模型對本地樣本的預(yù)測值，為節(jié)點(diǎn)j及其鄰居節(jié)點(diǎn)間的局部最優(yōu)模型對節(jié)點(diǎn)j上訓(xùn)練樣本x_jn的預(yù)測值；式(1)和式(2)中，λ||f_j||₁是對本地模型的L1正則化項(xiàng)，用于本地模型的稀疏求解，為節(jié)點(diǎn)本地模型和局部最優(yōu)模型相一致的并行投影形式；Num(B_j)是包括j在內(nèi)的鄰居節(jié)點(diǎn)數(shù)量；

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

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

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

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

在式(4)和式(5)中，K_j是本地訓(xùn)練樣本的增廣核矩陣，Y_j本地訓(xùn)練樣本的類別標(biāo)簽向量，I為本地樣本量加1，即N_j+1維的單位矩陣，α_j是要求解的本地訓(xùn)練樣本的權(quán)重向量，z_j是利用ADMM增加的輔助向量，輔助α_j求解；

在式(5)-式(7)中，ρ是約束α_j-z_j＝0的增廣系數(shù)，是一個(gè)正常數(shù)，u_j為約束α_j-z_j＝0的乘子系數(shù)向量，S_λ/ρ()為軟閾值操作函數(shù)，其定義如式(8)，

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

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

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

步驟3：節(jié)點(diǎn)接收鄰居節(jié)點(diǎn)發(fā)送過來的稀疏模型，計(jì)算局部最優(yōu)模型預(yù)測值；

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

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

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

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

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

步驟5：節(jié)點(diǎn)模型一致性

步驟5.1：節(jié)點(diǎn)j∈J將本地稀疏模型f_j^*(x_j)發(fā)送給單跳鄰居節(jié)點(diǎn)B_j；

步驟5.2：節(jié)點(diǎn)j∈J接收鄰居節(jié)點(diǎn)發(fā)送過來的稀疏模型f_i^*(x_i),i∈B_j，將模型保存在本地并去重處理；

步驟5.3：節(jié)點(diǎn)j∈J將新接收到的模型f_i^*(x_i),i∈B_j轉(zhuǎn)發(fā)給單跳鄰居節(jié)點(diǎn)B_j；

步驟5.4：當(dāng)各節(jié)點(diǎn)都得到所有節(jié)點(diǎn)的稀疏模型后，利用式(10)在節(jié)點(diǎn)本地進(jìn)行平均，得到一致模型；

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