邏輯回歸中的批量梯度下降算法并行化研究

李姚舜，劉黎志

智能機器人湖北省重點實驗室（武漢工程大學），湖北 武漢 430205

邏輯回歸算法是機器學習領域的經(jīng)典算法，雖然它使用起來比較簡單，但是在各個行業(yè)中使用效率很高。邏輯回歸模型僅在線性回歸的基礎上，套用了一個邏輯函數(shù)，使其成為了一種二分類算法，主要用于尋找危險因素、預測和判別等二分類模型［1-3］。有很多研究人員通過建立多個分類器或者改進邏輯回歸的損失函數(shù)等方法，讓邏輯回歸可以解決多分類問題［4-6］。隨著大數(shù)據(jù)時代的到來，數(shù)據(jù)量已經(jīng)不僅僅局限于PB的范圍，算法的計算過程還要求能夠快速處理大批量的數(shù)據(jù)集。邏輯回歸算法在計算過程中，不可避免需要對全局訓練數(shù)據(jù)進行遍歷以更新參數(shù)，這種串行運算隨著訓練數(shù)據(jù)集的增加，所消耗的資源也會難以估計，有很多研究人員也從硬件和算法優(yōu)化上提出了優(yōu)化的方法［7-8］。目前Apache基金會開發(fā)的Hadoop分布式框架，占據(jù)了大數(shù)據(jù)處理的龐大市場，已經(jīng)成為大數(shù)據(jù)開發(fā)的標準。Hadoop中的HDFS的數(shù)據(jù)管理能力、MapReduce處理任務時的高效率以及它的開源特性，使它在同類的分布式系統(tǒng)中大放異彩［9-11］。MapReduce是Hadoop中的一個分布式計算框架，它將一項繁雜的計算任務劃分為幾項相對較輕的計算任務，交由多個計算節(jié)點并行處理以加速任務進程［12-15］。本文就如何在MapReduce框架下改進邏輯回歸的參數(shù)訓練過程進行討論，并與單節(jié)點環(huán)境下的訓練過程進行比較，并通過實驗進行驗證。

1 研究背景

邏輯回歸的原理是將樣本的特征與樣本發(fā)生的概率聯(lián)系起來，計算結果是通過樣本的特征來擬合計算出一個事件發(fā)生的概率，它實際上是一種分類模型，主要用于解決二分類問題。

邏輯回歸的線性決策邊界形式如下［16］：

其中θn表示第n個特征參數(shù)，xn表示一行樣本的第n個特征值。

其回歸預測利用了Sigmoid函數(shù)，形式如下：

構造預測函數(shù)為：

hθ(x)的值表示結果取1的概率。設訓練數(shù)據(jù)集中的樣本數(shù)量為m，基于最大似然估計推導，得到的損失函數(shù)如下：

與線性回歸相比，邏輯回歸的損失函數(shù)并不能推導出一個正規(guī)方程解，即J(θ)并沒有數(shù)學的解析解，所以只能使用梯度法進行求解。此處J(θ)中乘了一個負的系數(shù)因此采用梯度下降算法求J(θ)取最小值時的θ為所需要的最佳系數(shù)，θ參數(shù)更新過程為：

其中α為學習率。對J(θ)求偏導數(shù)的結果為：

從參數(shù)更新過程中可以看出，式（6）（即計算梯度向量）是最基本的步驟，而式（6）中的在計算過程中只需要進行向量間的點乘、相加，此處可以將求和過程拆分成相互獨立的計算步驟，即對每行數(shù)據(jù)均單獨計算最后再歸并計算求和結果，并代入式（6）中得到目標函數(shù)的梯度向量。

通過分析，可以考慮對式（6）中的求和計算進行改進以達到并行化的目的。若將訓練數(shù)據(jù)集拆分為{Split(1),Split(2),…,Split(s)}等s個分片，每個分片中有p條數(shù)據(jù)（p不一定相同），將每個分片交由一個節(jié)點獨立計算，最后將結果進行匯總，則式（6）求偏導數(shù)過程可轉化為：

其中Spli（tt）表示第t個分片中的數(shù)據(jù)。綜上所述，θ的更新過程可以表示為：

2 批量梯度下降算法并行化

2.1 批量梯度下降算法

梯度法是一種基于搜索的最優(yōu)化方法，它是人工智能領域的一個非常重要的方法，但是它的作用是用于優(yōu)化一個目標函數(shù)，如果要最小化一個損失函數(shù)，使用的就是梯度下降法，如果要最大化一個效用函數(shù)，使用的是梯度上升法。

式（5）中采用梯度下降算法求解損失函數(shù)最小值，有兩種不同的形式：批量梯度下降（batch gradient descent，BGD）、隨機梯度下降（stochastic gradient descent，SGD）。由于SGD在每次迭代過程只用到一個訓練數(shù)據(jù)來更新參數(shù)，使得SGD并不是每次迭代都向著整體最優(yōu)化方向，其在解空間的搜索過程看起來很盲目。與SGD相比，BGD每次學習都使用整個訓練集，而邏輯回歸的是一個凸函數(shù)，沒有局部最優(yōu)解，只有唯一的全局最優(yōu)解，因此選用BGD求解J(θ)最小值。BGD可以保證每次更新都會朝著正確的方向進行，最后能夠使訓練過程收斂于全局極值點，而且BGD對每行樣本都進行了計算處理，因此也更能夠改進為并行化算法。

2.2 基于MapReduce的批量梯度下降

MapReduce是一種可用于數(shù)據(jù)處理的編程框架，采用“分而治之”的思想，把對大規(guī)模數(shù)據(jù)集的操作，分發(fā)給各個子節(jié)點共同完成，然后通過整合各個節(jié)點的中間結果，得到最終結果。MapReduce把處理過程高度抽象為map和reduce兩個函數(shù)，map負責把任務分解成多個子任務，reduce負責把分解后多個子任務處理的結果匯總起來。

圖1 MapReduce工作流程Fig.1 MapReduce workflow

在MapReduce框架下，采用JDK編程環(huán)境，矩陣運算在編程過程中均可轉化為循環(huán)操作，實驗過程中將矩陣向量均作為一維數(shù)組處理。

邏輯回歸中的BGD算法并行化步驟如下：

2.2.1 Split分片 將數(shù)據(jù)集放入HDFS文件系統(tǒng)下，當Job開始時，MapReduce會讀取數(shù)據(jù)文件并按照HDFS數(shù)據(jù)塊大小進行分片{Split(1),Split(2),…,Split(s)}，每一個分片交由一個Map節(jié)點進行處理。

2.2.2 解析鍵值對 MapReduce處理數(shù)據(jù)的最小單位是鍵值對，當分片Split（t）中的數(shù)據(jù)輸入map函數(shù)之前，會將其按照默認規(guī)則轉化為“<文本起始位置，文本內(nèi)容>”的鍵值對形式，分片中的每一行樣本便會轉化為一個輸入鍵值對

其中x(ni)表示第i行的第n個特征值，y(i)表示第i行的標簽值。

2.2.3 Map過程 每一個分片由一個Map節(jié)點處理，每解析出分片中的一條記錄便會調(diào)用一個map函數(shù)。只需要將value值x1(i),x(2i),…,x(ni),y(i)（此時為文本形式）通過Java分割函數(shù)分割為字符串數(shù)組然后將其中的特征值存儲到數(shù)組中，在存儲過程中，須對每一個數(shù)組手動添加一個參數(shù)偏移量x(0i)（此處取常量1.0）；將標簽值存儲到標簽變量 y=y(i)中，從而達到獲取特征值與標簽值的效果。

輸出完成后map函數(shù)結束，當分片Spli（tt）中的所有樣本均被map函數(shù)處理后，該分片的Map過程結束。當所有分片的Map過程均完成處理后，整個Job的Map過程結束，所有的輸出結果會溢出到HDFS本地磁盤中保存為一個文件。

2.2.4 Combine過程 此過程是對Reduce過程的優(yōu)化，如果將所有的鍵值對均傳輸給Reduce過程進行處理，勢必要耗費大量的網(wǎng)絡傳輸資源。因此Map在輸出結果到磁盤之前，會先將數(shù)據(jù)在Combine過程中提前處理，將鍵值對中key相同的value值進行求和，得到當前分片中的向量，將向量按照“＜參數(shù)序號的鍵值對形式整理后再進行輸出。

2.2.5 排序溢寫過程 每一個分片處理完成后均會輸出2.2.4中描述的鍵值對，所有分片的輸出結果會傳給排序溢寫（Shuffle）過程進行排序、歸并處理，再將結果傳給Reduce階段進行處理。整理結果會按照“＞＞”的鍵值對形式進行輸出。

2.2.6 歸并過程 歸并（Reduce）輸出時為保證將更新后的所有參數(shù)均同時輸出，在Job過程中設置Reduce的個數(shù)為1，即將所有的匯總結果均傳給同一個Reduce節(jié)點進行處理。將同一個key中value值進行求和運算，得到代入式（7）求和得到代入式（8）更新參數(shù)，將結果以“＜參數(shù)序號j,θj＞”的鍵值對形式輸出。輸出完成后Reduce過程結束，一次參數(shù)更新過程完成，循環(huán)上述過程，直至參數(shù)收斂，便完成訓練。

2.2.7 參數(shù)收斂過程判斷

1）判斷θ向量更新后的變化距離的平方和，若值d小于指定閾值，則判斷系數(shù)已經(jīng)收斂：

2）訓練數(shù)據(jù)集按設的次數(shù)結束迭代后，計算最后一次更新的θ與上一次θ的變化距離的平方和，即

3）若d小于指定閾值，則判斷系數(shù)已經(jīng)收斂。

2.3 算法的具體實現(xiàn)

Function map（regex，theta［］，data）

輸入：regex←訓練數(shù)據(jù)分割字符串，theta［］←回歸系數(shù)向量，data←訓練數(shù)據(jù)集文件夾路徑

2.3.2 算法2 Combiner過程歸并各分片輸出結果，計算

Function combiner（）

Begin

1： for value←values［0］to values［values.length-1］

2：do sum←sum+value End combiner

2.3.3 算法3 Reduce過程合并所有分片輸出結果，計算更新參數(shù)

Function reduce（，alpha）

輸出：鍵值對＜參數(shù)序號j,θj＞

2.3.4 算法4 開始一個訓練過程（Job），調(diào)用Map、Combiner、Reduce過程，輸出更新后參數(shù)

Function trainData（data，result，theta［］，last-Theta［］，alpha，regex，diff=100）

輸入：result←輸出文件夾路徑，lastTheta［］←上一次訓練的回歸系數(shù)向量，diff←誤差初始值輸出：更新后參數(shù)

3 實 驗

實驗用服務器為機械革命s1筆記本，其配置為1個物理CPU（Intel i7-8550u 1.8 GHZ，CPU含4核心8線程），16 GB內(nèi)存，1T硬盤，1個物理網(wǎng)卡。服務器安裝win10專業(yè)版操作系統(tǒng)，使用VMware Workstation Pro15軟件新建3個虛擬機，每個虛擬機的配置為1內(nèi)核CPU，2 GB內(nèi)存，20 GB硬盤，1個物理網(wǎng)卡。每個虛擬機安裝CentOS7操作系統(tǒng)，Hadoop 2.7.3分布式計算平臺，組成含1個主節(jié)點，2個從節(jié)點的集群。使用eclipse4.11、Java SE 1.8作為開發(fā)環(huán)境。

實驗內(nèi)容分為兩部分，第一部分驗證并行MapReduce并行化結果的正確性，第二部分將分布式集群運行結果與單節(jié)點運算結果進行比較，說明并行化集群的優(yōu)勢所在。

實驗中使用Java語言構建了一個針對大規(guī)模抵押貸款數(shù)據(jù)的邏輯回歸分類模型，用于預測客戶是否會如期歸還貸款，數(shù)據(jù)集中共包含5個樣本特征，數(shù)據(jù)集描述如表1所示。

表1 抵押貸款數(shù)據(jù)集描述Tab.1 Description of mortgage loan data set

取2001至2005年的數(shù)據(jù)樣本進行分析測試，每一年的數(shù)據(jù)文件中包含100萬條數(shù)據(jù)樣本，以9∶1的比例劃分訓練集和測試集，即在每一年的數(shù)據(jù)文件中取90萬條訓練數(shù)據(jù)集、10萬條測試數(shù)據(jù)集，最終試驗時共包含450萬條訓練數(shù)據(jù)和50萬條測試數(shù)據(jù)。

3.1 驗證并行化實驗結果正確

取50萬條訓練數(shù)據(jù)分別在集群環(huán)境和單節(jié)點環(huán)境下進行測試，單機訓練的過程此處不再進行贅述，實驗所得兩種環(huán)境下訓練結果相同，可以驗證并行化改進算法思路正確。參數(shù)訓練結果如表2所示。

表2 小數(shù)據(jù)集參數(shù)訓練結果Tab.2 Training results of small data set's parameters

3.2 集群與單機環(huán)境下訓練結果比較

在上一步測試的環(huán)境下，每次添加80萬條數(shù)據(jù)，在單機和集群中分別迭代運算1000次，統(tǒng)計兩者的運行時間，以訓練數(shù)據(jù)總量Data為橫坐標，集群與單機的運行時間比λ（倍）為縱坐標，畫出對應的散點圖如圖2所示。

理想情況下，集群中有3個節(jié)點參與運算，時間比λ應該在3倍左右。實際實驗中，在初期訓練數(shù)據(jù)集較小的情況下，運行效率沒有達到預測值，但是隨著訓練數(shù)據(jù)集的擴大，集群運行效率達到理想值，甚至超過理想值。原因在于MapReduce過程中分割文件、傳輸數(shù)據(jù)均包含大量的文件輸入輸出操作，在數(shù)據(jù)集較小時，消耗資源不能忽略不計。

圖2 集群與單機訓練時間比Fig.2 Time ratio between cluster and single machine training

4 結 語

本文基于MapReduce分布式計算框架，提出了邏輯回歸中BGD算法訓練參數(shù)時的并行處理辦法，實驗結果表明，這一思路可行，集群環(huán)境下的運算效率顯著提高。在實際應用過程中，隨著節(jié)點數(shù)量的增加以及集群計算性能的提升，單位時間內(nèi)能夠處理的數(shù)據(jù)量也會越來越多。在實驗過程中沒有從根本上改進BGD算法，只是將求和過程進行分解，驗證了并行化結果的正確以及高效性。在后續(xù)實驗和研究過程中，將試圖結合算法優(yōu)化以及集群平臺升級，從算法、軟件和硬件平臺三方面使邏輯回歸等機器學習算法能適應更多生產(chǎn)環(huán)境。