詳解并行邏輯回歸

編者按：回歸其實就是對已知公式的未知參數進行估計，Logistic regression是線性回歸的一種，是機器學習中十分常用的一種分類算法，在互聯網領域得到了廣泛的應用。本文來自騰訊馮揚的博客：并行邏輯回歸 ，主要從并行化的角度討論LR的實現。

CSDN推薦：歡迎免費訂閱《Hadoop與大數據周刊》獲取更多Hadoop技術文獻、大數據技術分析、企業實戰經驗，生態圈發展趨勢。

以下為原文：

邏輯回歸（Logistic Regression，簡稱LR）是機器學習中十分常用的一種分類算法，在互聯網領域得到了廣泛的應用，無論是在廣告系統中進行CTR預估，推薦系統中的預估轉換率，反垃圾系統中的識別垃圾內容……都可以看到它的身影。LR以其簡單的原理和應用的普適性受到了廣大應用者的青睞。實際情況中，由于受到單機處理能力和效率的限制，在利用大規模樣本數據進行訓練的時候往往需要將求解LR問題的過程進行并行化，本文從并行化的角度討論LR的實現。

1. LR的基本原理和求解方法

LR模型中，通過特征權重向量對特征向量的不同維度上的取值進行加權，并用邏輯函數將其壓縮到0~1的范圍，作為該樣本為正樣本的概率。邏輯函數為，曲線如圖1。

圖1 邏輯函數曲線

給定M個訓練樣本,其中X_j={x_ji|i=1,2,…N} 為N維的實數向量（特征向量，本文中所有向量不作說明都為列向量）；y_j取值為+1或-1，為分類標簽，+1表示樣本為正樣本，-1表示樣本為負樣本。在LR模型中，第j個樣本為正樣本的概率是：

其中W是N維的特征權重向量，也就是LR問題中要求解的模型參數。

求解LR問題，就是尋找一個合適的特征權重向量W，使得對于訓練集里面的正樣本，值盡量大；對于訓練集里面的負樣本，這個值盡量?。ɑ?img src="http://www.vxbq.cn/uploadfile/20140901/yjs/52fc40c418649.jpg" border="0" style="">

盡量大）。用聯合概率來表示：

對上式求log并取負號，則等價于：

                                                公式(1)

公式(1)就是LR求解的目標函數。

尋找合適的W令目標函數f(W)最小，是一個無約束最優化問題，解決這個問題的通用做法是隨機給定一個初始的W0，通過迭代，在每次迭代中計算目標函數的下降方向并更新W，直到目標函數穩定在最小的點。如圖2所示。

圖2 求解最優化目標函數的基本步驟

不同的優化算法的區別就在于目標函數下降方向D_t的計算。下降方向是通過對目標函數在當前的W下求一階倒數（梯度，Gradient）和求二階導數（海森矩陣，Hessian Matrix）得到。常見的算法有梯度下降法、牛頓法、擬牛頓法。

(1) 梯度下降法(Gradient Descent)

梯度下降法直接采用目標函數在當前W的梯度的反方向作為下降方向：

其中為目標函數的梯度，計算方法為：

公式（2）

(2) 牛頓法(Newton Methods)

牛頓法是在當前W下，利用二次泰勒展開近似目標函數，然后利用該近似函數來求解目標函數的下降方向:。其中Bt為目標函數f(W)在Wt處的海森矩陣。這個搜索方向也稱作牛頓方向。

(3) 擬牛頓法(Quasi-Newton Methods)：

擬牛頓法只要求每一步迭代中計算目標函數的梯度，通過擬合的方式找到一個近似的海森矩陣用于計算牛頓方向。最早的擬牛頓法是DFP（1959年由W. C. Davidon提出，并由R. Fletcher和M. J. D. Powell進行完善）。DFP繼承了牛頓法收斂速度快的優點，并且避免了牛頓法中每次迭代都需要重新計算海森矩陣的問題，只需要利用梯度更新上一次迭代得到的海森矩陣，但缺點是每次迭代中都需要計算海森矩陣的逆，才能得到牛頓方向。

BFGS是由C. G. Broyden, R. Fletcher, D. Goldfarb和D. F. Shanno各自獨立發明的一種方法，只需要增量計算海森矩陣的逆H_t=B_t^-1，避免了每次迭代中的矩陣求逆運算。BFGS中牛頓方向表示為：

L-BFGS(Limited-memory BFGS)則是解決了BFGS中每次迭代后都需要保存N*N階海森逆矩陣的問題，只需要保存每次迭代的兩組向量和一組標量即可：

在L-BFGS的第t次迭代中，只需要兩步循環既可以增量計算牛頓方向：

2. 并行LR的實現

由邏輯回歸問題的求解方法中可以看出，無論是梯度下降法、牛頓法、擬牛頓法，計算梯度都是其最基本的步驟，并且L-BFGS通過兩步循環計算牛頓方向的方法，避免了計算海森矩陣。因此邏輯回歸的并行化最主要的就是對目標函數梯度計算的并行化。從公式(2)中可以看出，目標函數的梯度向量計算中只需要進行向量間的點乘和相加，可以很容易將每個迭代過程拆分成相互獨立的計算步驟，由不同的節點進行獨立計算，然后歸并計算結果。

將M個樣本的標簽構成一個M維的標簽向量，M個N維特征向量構成一個M*N的樣本矩陣，如圖3所示。其中特征矩陣每一行為一個特征向量（M行），列為特征維度（N列）。

圖3 樣本標簽向量 & 特征向量

如果將樣本矩陣按行劃分，將樣本特征向量分布到不同的計算節點，由各計算節點完成自己所負責樣本的點乘與求和計算，然后將計算結果進行歸并，則實現了“按行并行的LR”。按行并行的LR解決了樣本數量的問題，但是實際情況中會存在針對高維特征向量進行邏輯回歸的場景（如廣告系統中的特征維度高達上億），僅僅按行進行并行處理，無法滿足這類場景的需求，因此還需要按列將高維的特征向量拆分成若干小的向量進行求解。

 (1) 數據分割

假設所有計算節點排列成m行n列（m*n個計算節點），按行將樣本進行劃分，每個計算節點分配M/m個樣本特征向量和分類標簽；按列對特征向量進行切分，每個節點上的特征向量分配N/n維特征。如圖4所示，同一樣本的特征對應節點的行號相同，不同樣本相同維度的特征對應節點的列號相同。

圖4 并行LR中的數據分割

一個樣本的特征向量被拆分到同一行不同列的節點中，即：

其中X_r,k表示第r行的第k個向量，X_(r,c),k表示X_r,k在第c列節點上的分量。同樣的，用W_c表示特征向量W在第c列節點上的分量，即：

(2) 并行計算

觀察目標函數的梯度計算公式(公式(2)),其依賴于兩個計算結果：特征權重向量W_t和特征向量X_j的點乘，標量和特征向量X_j的相乘?？梢詫⒛繕撕瘮档奶荻扔嬎惴殖蓛蓚€并行化計算步驟和兩個結果歸并步驟：

① 各節點并行計算點乘，計算，其中k=1,2,…,M/m，表示第t次迭代中節點(r,c)上的第k個特征向量與特征權重分量的點乘，W_c,t為第t次迭代中特征權重向量在第c列節點上的分量。

②對行號相同的節點歸并點乘結果：

計算得到的點乘結果需要返回到該行所有計算節點中，如圖5所示。
             
                                                           圖5 點乘結果歸并

③ 各節點獨立算標量與特征向量相乘：

G_(r,c),t可以理解為由第r行節點上部分樣本計算出的目標函數梯度向量在第c列節點上的分量。

④ 對列號相同的節點進行歸并：

G_c,t就是目標函數的梯度向量G_t在第c列節點上的分量，對其進行歸并得到目標函數的梯度向量：

這個過程如圖6所示。

圖6 梯度計算結果歸并

綜合上述步驟，并行LR的計算流程如圖7所示。比較圖1和圖7，并行LR實際上就是在求解損失函數最優解的過程中，針對尋找損失函數下降方向中的梯度方向計算作了并行化處理，而在利用梯度確定下降方向的過程中也可以采用并行化（如L-BFGS中的兩步循環法求牛頓方向）。

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈