Logistic回歸的CPU並行化及其 Batch Gradient Ascent 的實現

（本文實現了一種二類線性分類的Logistic回歸的分類器，對於一般的PC來說，能做到100%的壓榨CPU，同時引入了批量訓練在不給CPU太大鴨梨的情況下最大程度的（bao）壓（zhen）榨（shu）內（ju）存（liang），這樣的一份程序，對於大多數最小完備數據集大小沒有大到出格的應用場景已經是夠用了，而且大家都知道我這個尿性的，先實戰再理論~）

代碼諸位自己下著玩：

DataScienceNote/ParallelLogistic at master · TsingJyujing/DataScienceNote · GitHub

Part Ⅰ ：簡介

Logistic回歸恐怕是最常見的分類演算法了，應該沒有之一，而且大家都愛用它。

主要原因還是Logistic回歸在處理大量數據的時候易於並行的優勢所致吧！

其實有相當一部分的機器學習的演算法是可以並行的，只要是建立一個數學模型，有代價函數的，那麼做梯度下降的時候肯定就能並行化，方法也很簡單：把數據切成若干個小塊兒分別求梯度即可。

要用Logistic回歸，首先要明白Logistic回歸用在什麼地方。

首先是Logistic回歸背後的假設：Logistic回歸假設數據符合Logistic分布，也就是大約是醬子的：

這是1維的Logistic分布，藍色的正類樣本的出現概率，紅色是負類樣本的出現概率。兩者在0處交匯。

Logistic回歸的本質，就是假設數據符合這個分布，隨後使用極大似然估計法做參數的估計。

那麼理論上說，只要數據符合Logistic分布就能愉快的搞起了，但是，我們要解決這個問題：

數據不是都是一維的，有高維的分布嗎？

沒有高維的分布。所謂的高維，其實是想辦法降維成1維以後數據大致符合Logistic分布。

（其實在最後的一維空間里只要可以用一個點做到大致可分就差不多了，沒人會去真的管什麼Logistic分布的，但是這個點在哪裡卻是Logistic的損失函數決定的）

至於怎麼降維，最常用的就是線性降維了，也就是，讓數據和一個向量做內積，得到的結果就是降維成1維後的數據。

以2維為例：

插圖懶得畫了，直接用PRML上的了。可以看到，每一個數據點都垂直的映射到紫色直線上，最後的結果只保留紫色直線所在的1維空間。

如果是3維的也好理解，首先在三維世界給定一塊2維平面，隨後所有的數據都收縮到該平面的法線上成為1維。

對於N維空間，我們就只保留其1維，其它的N-1維全部壓縮。

那麼這麼看來Logistic回歸是一種線性分類演算法咯？

Nope~！

誰說Logistic回歸一定是線性的了，只要其中的映射變化一下，就可以不是線性的！

假設輸入向量是，那麼假設有一個非線性映射：

，隨後使用線性分類器對做分類就可以得到針對原始數據集的一個非線性分類！

是不是感覺和核函數有點像？

不同的地方在於，核函數可以是無窮維的，這裡的Logistic回歸的核心仍然是線性的，不接受無窮維的向量。要接受無窮維的向量，首先要更改Logistic的模型，讓其中內積的部分從顯式表達變為隱式表達，這樣一處理，Logistic針對大數據集的優勢就不見了。

所以還是使用顯式的非線性預處理解決這個問題吧！

線性Logistic回歸的偏導數的推導在此我不打算在這一篇文章中展示，因為我有更大的陰毛。

Part Ⅱ：並行化的數學原理

本篇的重點，主要是討論Logistic回歸的並行化。

如我們所知，Logistic回歸偏導數的求法是這樣的：

在這裡，我們如果把數據集打散（註：即「劃分」，要滿足不重、不漏兩個條件）成C塊：

就可以加速了，就是這麼簡單。

很容易證明上面兩條公式是等價的。

Part Ⅲ：如何編程？

我們實驗的環境是Linux，嚴格地說是Ubuntu 15.04 (AMD64)，CPU是奔騰的雙核E5200，很老的CPU了，但是老當益壯，看看B站什麼的毫無壓力。內存2G。

使用了純C進行編寫，符合ANSI標準，可以隨便移植，移植的時候要支持POSIX標準，也就是要能#include<pthread.h>。

編譯以後生成動態鏈接庫，可以被各種程序調用，演示的時候用了Matlab，本來想用Python的，不幸的是matplotlib掛了，死活不出圖……

一般的，Linux和Unix上是無壓力

這次我們寫的是個內存演算法，就算是數據完全能放進內存的演算法。當然，這個程序也可以修改成外存演算法，最簡單的想辦法直接把SSD映射成一片假的RAM就結了。

代碼在此：

首先是整段數據的指針傳入，其次是根據Batch的信息和分成幾個線程的信息得到每一個線程該跑哪些數據。

最後得到以後直接把每一個數據得到的偏導數求和還回去，最後由主線程統一求和，再除以N。

代碼段如下：

for (j = 0; j <size_dim; ++j){n gradient_vec[j] = 0.0f;n for (i = 0; i<parallel_pool_count; ++i){n gradient_vec[j]+=n gradient_result[i*size_dim+j];n }n gradient_vec[j] /= sum_all;n}n

這樣就結束啦！

最後使用Matlab調用就好了：

Part Ⅳ：幾個線程才是墜吼滴？

每個CPU是不一樣的，就以我的CPU，E5200為例，我們計算在不同的數據量的時候選用多少線程合適：

可以看到，在數據量最少（2萬條數據）的時候，隨著線程數上升效率是下降的，下降之嚴重可以到5倍左右！

究其原因是因為每個線程算的時間短，但是要創建這麼多進程花費的時間開銷卻不少，要一個個malloc一片兒空間給他們存放參數。

所以，數據多的時候還是線程多一點兒效率高，可以把CPU♂塞♂的♂滿♂滿♂的♂。

一般的，我的CPU在數據量大的時候開64線程效率最高。

從數據量上我們也可以看出，數據越多，越是能把CPU的效率發揮出來。

所以還是稍微實驗一下，知道自己CPU的情況再做決定。

如果你是土豪使用32核的Xeon的CPU，加上32G內存之類的配置，可以試試喪心病狂的開512線程之類的。

什麼時候需要用這麼喪心病狂的塞滿CPU的方法呢？

答：數據量偏大，但是沒有大到喪盡天良的地步的時候。

綜上所述，線程數量一般是CPU核心數量的32蓓沒什麼大問題。

Part Ⅴ：如果數據量太大，喪（hao）盡（jing）天（nei）良（cun）怎麼辦？

如果數據量大的喪盡天良，這個時候首先考慮抽樣，隨機的抽樣，抽出你內存能放得下的數據，例如你的內存高達8G，你可以試試抽個4~6G的數據出來。

但是要跑4~6G之多的數據還是太費力，這個時候我們就要引入Batch Normalization，也就是一整段的數據一次吃不下我分10次吃，每次吃十分之一。（這裡的十也可以是其他數字）

明明有4000M數據，每次只有400Mb的數據參與訓練，並且做梯度下降，這個時候速度會快很多，又能保證不收斂到其他奇奇怪怪的地方去，因為每次的400Mb數據都不一樣。

在最後可以用整段的數據訓練3~5次做最後的收斂。模型基本就是準確的了。

這玩意兩個用途，1是數據維度太高，梯度太小的時候用，2是數據太多，跑不完又要快速收斂的時候用。

可以看到，引入了Batch Normalization以後，權值的變化存在震蕩（我放大了，否則看不出來），但還是收斂到了一個不錯的結果上。

（註：紅色藍色點我各只畫了1000個示意一下，意思到了就行~饒過我的顯卡吧！）

引入了10等分的Batch Gradient Ascent以後，速度快了10倍，效果基本沒什麼折扣，真是令人Excited~啊~一顆賽艇。

（PS：一般海量的數據都是可以精簡的，有的時候百分之一，甚至萬分之一的隨機抽樣就可以保證數據是完備的了，這個時候最適合使用抽樣+Batch的方法進行訓練，在保證速度和數據量的前提下達到較好的效果，唯一需要注意的是做到隨機抽樣）

下回予告：

1，Logistic回歸背後的數學原理是什麼？

2，如何利用線性的Logistic回歸做出非線性的決策超平面？

3，如何在數據量太大的時候獲取最小的完備的數據集？

多餘的話：

1，在 parallel_logistic_kernel.h裡面有這麼一段代碼

#ifndef _PARALLEL_LOGISTIC_KERNEL_n#define _PARALLEL_LOGISTIC_KERNEL_n//#define DEBUG_FLAGn#ifdef DEBUG_FLAGn #include <stdio.h>n#endifn#include <math.h> n

其中

//#define DEBUG_FLAGn

如果不注釋可能出錯，如果你是用C調用的時候需要調試就取消注釋。

2，C語言的調用方法已經在 unit_test_so.c給出，注意吧so文件拷貝到/lib下才能用

如果你修改了parallel_logistic_kernel.h中關於調用的一些介面或者函數定義之類的，記得同步修改liblogistic.h，同時Matlab的代碼肯定也要改。你也可以寫一個函數把和調用有關的一些東西包起來，我以前喜歡這個干，今天懶。

3，Matlab裡面傳入的必須是列向量，原因很簡單，Matlab記錄矩陣的方法是縱向折回記錄的（恕我口拙說不清楚），Matlab這麼定義的原因十有八九是因為BLAS裡面也是按縱向量存儲的，所以這算歷史遺留問題。
推薦閱讀：