莊福振 錢明達 申恩兆， 張大鵬 何 清

(1.中國科學院計算技術研究所智能信息處理重點實驗室，北京，100190； 2.燕山大學信息科學與工程學院，秦皇島，066004)

引 言

機器學習作為人工智能的主體與核心，各種機器學習算法已經應用到各個領域，如語音識別、圖片分類、推薦系統(tǒng)、手寫輸入識別和漏洞發(fā)現(xiàn)等，極大地提高了計算機智能化程度和各種系統(tǒng)的性能。實際應用中許多數(shù)據(jù)并不能很好地表示數(shù)據(jù)規(guī)律，甚至對系統(tǒng)的學習產生副作用，這就需要獲得好的特征表示來改進算法的性能。然而隨著計算機以及互聯(lián)網的不斷發(fā)展，信息量不斷增大，信息復雜度也不斷提升，數(shù)據(jù)包含的信息日益龐雜、冗余，良好的特征工程成為影響機器學習成敗的關鍵因素。如何取得數(shù)據(jù)良好的特征表示，進而提升機器學習算法性能已經成為機器學習中一個關鍵的問題。

特征學習(Feature learning)又稱作表示學習(Representation learning)，是機器學習領域中的一個重要研究問題，它的目標是自動地學習一個從原始輸入到新特征表示的變換，使得新特征表示能夠有效應用在各種學習任務中，從而把人從繁瑣的特征工程中解放出來。根據(jù)訓練過程是否需要有標簽數(shù)據(jù)，可以把表示學習算法分為兩類：有監(jiān)督特征學習和無監(jiān)督特征學習。在有監(jiān)督特征學習中，通常需要利用有標簽數(shù)據(jù)，比如有監(jiān)督字典學習。無監(jiān)督特征學習中，不需要數(shù)據(jù)具有標簽，比如主成分分析、 獨立成分分析、 自動編碼機、矩陣分解[1]以及眾多形式的聚類算法[2-3]。

近幾年來神經網絡深度結構對特征的多層次抽象吸引了研究人員的廣泛關注，深度學習模型在各類學習任務中都取得了不錯的性能，且許多深度模型在實際應用場景中都表現(xiàn)良好[4-6]。自動編碼機已經被證明在數(shù)據(jù)降維和特征提取上有著非常好的表現(xiàn)。目前自動編碼機已經發(fā)展出眾多變體，除了自動編碼機外，還有稀疏自動編碼機、降噪自動編碼機、堆疊自動編碼機及卷積自動編碼機等[7-9]。此外神經元的屏蔽、正則化、邊緣化等方法[10]都被運用于自動編碼機。在應用上，異常檢測中自動編碼機取得良好效果，深度自動編碼機也被運用到遷移學習中[11]。但以上的自動編碼機都是串行實現(xiàn)，不能滿足目前大數(shù)據(jù)環(huán)境下模型復雜、計算量大的實際問題。因此，單機串行實現(xiàn)的模型在應用層面具有很大的局限性。

隨著大數(shù)據(jù)時代的來臨，處理海量數(shù)據(jù)、建立大規(guī)模計算模型成為必然需求。本文提出了一種基于Spark的高效自動編碼機，利用Spark分布式內存計算的固有優(yōu)勢高效處理海量數(shù)據(jù)?，F(xiàn)有數(shù)據(jù)種類繁多，許多數(shù)據(jù)有非常稀疏的特點，比如推薦系統(tǒng)關系矩陣、文本詞袋模型等。而現(xiàn)有基于自動編碼機的特征提取算法沒有對稀疏數(shù)據(jù)做針對性優(yōu)化，計算過程中大量無效運算和存儲空間開銷使時間復雜度和空間復雜度隨數(shù)據(jù)維度成二次甚至三次增長，與有效數(shù)據(jù)成指數(shù)級增長。本文編碼算法是一種對稀疏數(shù)據(jù)針對性操作的優(yōu)化方法，使得稀疏數(shù)據(jù)處理開銷與有效數(shù)據(jù)成正比，極大優(yōu)化了算法運行的時間效率和空間效率。

1 基于Spark的高效并行自動編碼機

1.1 自動編碼機的概念

圖1 簡單的自動編碼機結構Fig.1 Structure of a simple auto-encoder

圖2 神經元Fig.2 Single neuron

圖1中的自動編碼機，作為前饋神經網絡，分別由輸入層、隱含層和輸出層組成。其中輸入層為數(shù)據(jù)直接表示，隱含層和輸出層中每個節(jié)點代表神經網絡的一個神經元。神經元由上層網絡輸出的加權和通過激活函數(shù)得到輸出，并提供下一層網絡使用。神經元可以簡單表示為如圖2所示，激活函數(shù)一般為非線性函數(shù)，本文使用Sigmoid函數(shù)，其函數(shù)表達式為

(1)

一般地，一個自動編碼機包括編碼部分和解碼部分。兩部分可以概括為

1.2 Spark分布式計算平臺

Apache Spark，2014年成為Apache基金頂級項目，以快速、通用、簡單等特點成為當前流行大數(shù)據(jù)處理模型。Spark提出的分布式內存計算框架，既保留了MapReduce的可擴展性、容錯性和兼容性，又彌補了MapReduce在這些應用上的不足。由于采用基于內存的集群計算，所以Spark在這些應用上相對MapReduce有100倍左右的加速[13]。此外Spark可以部署在Hadoop集群環(huán)境下，擁有直接訪問HDFS文件系統(tǒng)的能力。但不同于MapReduce中間過程和計算結果需要讀寫HDFS，Spark將計算結果保存在內存中，從而不必頻繁讀寫HDFS，減少了IO操作，提升了算法運行效率，使算法運算時間大幅縮短。

圖3 系統(tǒng)結構圖Fig.3 Structure of system

值得強調的是，分布式系統(tǒng)需要一個統(tǒng)一調度角色，一般稱為管理者(Manager)，而其他各運算節(jié)點稱為工作者(Worker)。一般情況下，并行程序運行過程中由Workers分別計算相對獨立的并行步驟，Manager統(tǒng)一調度、管理和統(tǒng)計。

1.3 基于Spark的高效并行自動編碼機基本原理

基于Spark的高效并行自動編碼機(Parallel auto-encoder，PAE)是對現(xiàn)有自動編碼機完成針對稀疏數(shù)據(jù)的修改后，將其遷移到Spark計算平臺上的成果。系統(tǒng)的結構包括一個負責分發(fā)Job、收集數(shù)據(jù)、調度任務的Manager以及若干個負責具體計算的Worker。系統(tǒng)結構如圖3所示。圖中，系統(tǒng)于分布式系統(tǒng)的各計算節(jié)點初始化同樣的神經網絡。每計算一定量的數(shù)據(jù)，對模型的參數(shù)進行收集歸并，不斷迭代得到最終權值。

上述過程基于神經網絡的性質：相同初始值的神經網絡，對同分布下不同數(shù)據(jù)樣本進行擬合，最終所擬合數(shù)據(jù)分布相同，即得到網絡參數(shù)分布相近。本文算法以此為基礎，在初始化時保證網絡完全一致，達到自動編碼機并行運算的目的。

此外，本系統(tǒng)針對自動編碼機低效處理稀疏數(shù)據(jù)的缺陷，提出避免計算過程中無效計算和無效存儲開銷的方案。使用指示器函數(shù)對算法進行改進，指示器函數(shù)為

通過指示器函數(shù)的選擇，在計算中系統(tǒng)只關注有效值及其對應神經元，且反向傳播時避免無效計算與操作。本文系統(tǒng)成功地將時間復雜度由二次復雜度降為線性復雜度，在保證計算正確性的前提下，大幅度提高了模型訓練速度。

2 基于Spark的高效并行自動編碼機算法

2.1 編碼機算法模型

為實現(xiàn)基于Spark的高效并行自動編碼機，本文選擇反向傳播來進行學習和優(yōu)化，此外目標函數(shù)學習使用了梯度下降思想。另外，為提高算法運行效率，本文采用隨機梯度下降算法，即計算每一條樣本，實時更新學習模型。

當模型訓練開始，Manager首先進行Map操作，將初始化參數(shù)分發(fā)至各Worker節(jié)點，包括數(shù)據(jù)規(guī)模、隱藏層配置、輸入數(shù)據(jù)路徑、正則化參數(shù)及隨機數(shù)種子等。此后每個Worker獨立讀取數(shù)據(jù)，利用隨機數(shù)種子分別初始化自動編碼機的各項參數(shù)，其中由相同的隨機種子保證各Worker上神經網絡初始狀態(tài)一致。

隨后Worker分別利用各自數(shù)據(jù)分片訓練自動編碼機，Worker每次處理一條數(shù)據(jù)樣本，將讀入樣本進行正向傳播，即利用輸入數(shù)據(jù)計算隱藏層和輸出層的結果。完成后進行反向傳播，利用得到的輸出數(shù)據(jù)誤差計算出神經網絡的參數(shù)梯度。利用所得梯度，完成網絡參數(shù)更新，至此完成模型的一次迭代。整個訓練過程需要重復迭代，保證所分得數(shù)據(jù)分片中的每一例樣本至少計算一遍。

各Worker利用一部分數(shù)據(jù)完成模型訓練后，進行Reduce操作，將各節(jié)點計算結果進行約減。其中約減操作定義為Worker將計算所得模型參數(shù)上傳至 Manager，由Manager對各參數(shù)取平均。至此完成系統(tǒng)的一次迭代。

對系統(tǒng)進行迭代，保證所有Worker均完全訓練，至少保證訓練集中所有數(shù)據(jù)均參與到系統(tǒng)模型的訓練中。最終在Manager上得到一個訓練完畢的模型。值得指出的是，實際操作中可以根據(jù)集群實際情況，對數(shù)據(jù)進行多種劃分模式，包括但不限于差異化節(jié)點數(shù)目、節(jié)點間不同數(shù)據(jù)條數(shù)、各次迭代處理的數(shù)據(jù)條數(shù)以及系統(tǒng)整體對數(shù)據(jù)比例劃分。

以上模型可具體表示為：

正向傳播

h=sigmoid(W1x+b1)

(4)

(5)

反向傳播

(6)

(7)

(8)

(9)

權值更新

W=W+φ(xinΔW-αW)

(10)

式(4～10)中符號表示含義如表1所示。

表1 公式符號含義

表中：N為輸入數(shù)據(jù)樣本數(shù)量；M為輸入數(shù)據(jù)維度；K表示隱藏層節(jié)點目。

2.2 自動編碼機的實現(xiàn)

根據(jù)2.1節(jié)描述可以實現(xiàn)基于Spark的高效并行自動編碼機。Worker上隨機梯度下降(Stochastic gradient descent，SGD)偽代碼如算法1所示，基于Spark的高效并行自動編碼機偽代碼如算法2所示。

算法1隨機梯度下降算法

輸出：自動編碼機學習到的參數(shù)W1,b1,W2,b2

For：對輸入數(shù)據(jù)集中的每一個樣本：

(1)根據(jù)式(4，5)，進行正向傳播。并計算網絡中每個單元的輸出；

(2)根據(jù)式(6，7)，利用已求有輸出分別求得網絡各節(jié)點的殘差；

(3)由式(8，9)，利用已有殘差分別計算網絡模型各參數(shù)的梯度；

(4)按照式(10)，更新自編碼機權值。

算法2基于Spark的高效并行自動編碼機

輸出：自動編碼機學習到的參數(shù)W1,b1,W2,b2

(1)初始化，由Manager根據(jù)Nworker將網絡參數(shù)size,τ進行分發(fā)，并根據(jù)實際情況，將xin隨機劃分為若干部分，分別派發(fā)給Worker。Worker根據(jù)Manager下發(fā)的size來構建網絡，τ來初始化矩陣;

算法2流程如圖4所示。由算法2得到的所有Worker上的參數(shù)，可以得到最終的模型參數(shù)。

圖4 基于Spark高效并行自動編碼機Fig.4 Efficient parallel auto-encoder based on Spark

3 實驗與結果分析

本節(jié)在兩個學習任務上驗證算法的有效性以及高效性，即分類任務和協(xié)同過濾。本文實驗包括：(1)直接對源數(shù)據(jù)利用支持向量機(SVM)得到分類結果與PAE分類結果進行比較。(2)利用Matlab Deeplearning Tool(http://www.mathworks.com/matlabcentral/fileexchange/38310-deep-learning-toolbox)中SAE單機壓縮數(shù)據(jù)后，再利用SVM分類結果與PAE得到的壓縮數(shù)據(jù)分類結果進行比較，分別驗證算法不同方面的能力和表現(xiàn)。其中SAE串行算法的有效性已經被眾多事實所驗證，公認其獲得的特征可以有效提升機器學習算法性能，故而在此不再重復討論。(3)將PAE應用到推薦系統(tǒng)中，得到推薦結果分別與基準算法進行比較，進而驗證PAE在推薦系統(tǒng)中的有效性。

3.1 數(shù)據(jù)集和預處理

為了驗證PAE算法的有效性和并行效率，本文采用文本數(shù)據(jù)集20Newsgroups(http://qwone.com/～jason/20Newsgroups/)，該數(shù)據(jù)集包含20個主題，每個主題有大約1 000個樣本文件，數(shù)據(jù)維度為61 188，數(shù)據(jù)以稀疏數(shù)據(jù)的方式存儲。20個主題按照題材簡單分類后如表2所示。為了構造分類問題，本文以文檔主題作為分類預期結果，總共20類。

表2 20Newsgroups數(shù)據(jù)集主題

在PAE應用于推薦系統(tǒng)的實驗中，本文基于兩個個性推薦系統(tǒng)公共數(shù)據(jù)集MovieLens(http://grouplens.org/datasets/movielens/)和NetFlix(http://www.prea.gatech.edu/download.html)進行實驗。

MovieLens是一套公共推薦系統(tǒng)數(shù)據(jù)集，數(shù)據(jù)為用戶對自己看過的電影進行的評分，分值為1～5。顯然，數(shù)據(jù)集中用戶和電影構成的評分矩陣極度稀疏。數(shù)據(jù)集中包括3個不同大小的庫，100 K數(shù)據(jù)集中包括1 000位用戶對1 700部電影進行評分的100 000個評分記錄；1 M數(shù)據(jù)集中包括6 000位用戶對4 000部電影打分的100萬條記錄；10 M數(shù)據(jù)集中包括了72 000位用戶對10 000部電影進行評分的1 000萬條記錄和10萬標簽記錄。

NetFlix和MovieLens一樣也是用戶電影評分數(shù)據(jù)集，同樣分值分布為1～5，但前者數(shù)據(jù)量遠遠高于后者。該數(shù)據(jù)集反映了自1998年10月到2005年12月期間的評分記錄分布。NetFlix中包括了從48萬名用戶對17 000部電影的評分中隨機選取的1億條評分記錄。此外還包括了電影的發(fā)行時間和發(fā)行標題。

3.2 特征表示學習

特征表示學習實驗中主要分為兩部分，分別驗證PAE的有效性和高效性。

(1)在驗證PAE有效性實驗中，本文首先訓練SVM分類器，得到源數(shù)據(jù)分類準確率基準值；隨后由PAE在不同數(shù)目的Worker下對數(shù)據(jù)進行壓縮降維，利用壓縮后的降維特征訓練分類器得到分類準確率。其中SVM作為基準分類器使用LibSVM[14]庫。實驗從所有數(shù)據(jù)中分別隨機選取60%,70%,80%,90%作為訓練集，剩下的作為測試集。為了保證分布式算法在不同節(jié)點情況下充分測試，本文分別測試了2，3，4個Worker的情況。

(2)本文也比較了Matlab Deeplearning Tool中SAE作為特征的提取方法。由SAE對數(shù)據(jù)進行降維壓縮，得到的特征表示由SVM進行學習并構造分類器，通過測試集得出分類準確率。實驗中利用自動編碼機將原有61 188維稀疏數(shù)據(jù)提取特征降維到100維。為了驗證PAE對海量數(shù)據(jù)處理性能，本文將18 774個樣本的數(shù)據(jù)集進行擴展、復制，進而得到海量數(shù)據(jù)。通過海量數(shù)據(jù)測試將PAE與SAE進行對比，驗證算法運行效率。

3.3 特征表示學習實驗結果

3.3.1 PAE正確性分析

表3給出了PAE有效性實驗的實驗結果，所列數(shù)據(jù)均為5次實驗平均值。表中還記錄了不同數(shù)目的Worker下本文并行算法執(zhí)行結果。由表3中結果可以看到，SVM分類準確率隨著訓練比的不斷提高而提高，經過PAE降維后的數(shù)據(jù)在SVM分類器的表現(xiàn)普遍優(yōu)于同訓練比例的原始數(shù)據(jù)。這是由于原始數(shù)據(jù)維度非常高，通過降維可以得到更好的特征表示。實驗結果證明了PAE提取特征的正確性和有效性。

表3 SVM分類準確率

3.3.2 PAE效率分析

在保證正確性的情況下，與Matlab Deeplearning Tool中SAE做效率對比，同樣地將源數(shù)據(jù)集由61 188維度壓縮為100維度。SAE及PAE算法運行時間統(tǒng)計結果如圖5所示。值得指出的是，SAE在數(shù)據(jù)量達到8 000條時，報出了內存不足的異常，亦即單機Matlab Deeplearning Tool中SAE處理數(shù)據(jù)的極限不足8 000條。并且由圖5顯示，SAE時間開銷是隨數(shù)據(jù)量的變化成二次變化。運行環(huán)境為：Intel CoreTMi7-4790 3.6 GHz CPU，8 GB 內存，500 GB 硬盤，操作系統(tǒng)為 Windows 7，64位專業(yè)版。

圖5 SAE和PAE運算時間開銷對比Fig.5 Time cost comparison between SAE and PAE

同樣的數(shù)據(jù)，在PAE實驗過程中設置不同的Worker數(shù)。由圖5看到在數(shù)據(jù)量較小時，PAE時間開銷相對較大，變化趨勢與數(shù)據(jù)量并無明顯聯(lián)系，這是因為數(shù)據(jù)量較小時，分布式計算中平臺通訊開銷所占系統(tǒng)時間開銷比例較大。隨著數(shù)據(jù)量的不斷增大，可以看出當數(shù)據(jù)量達到60 000條時，系統(tǒng)時間開銷開始有明顯的增長，此時系統(tǒng)的計算時間占比逐漸變大，計算時間的變化對系統(tǒng)總時間開銷的影響開始顯現(xiàn)出來。與單機運行SAE對比，首先PAE能夠處理的數(shù)據(jù)量遠遠大于SAE；其次由圖線對比得出，在數(shù)據(jù)量逐漸增大的過程中，系統(tǒng)時間開銷隨數(shù)據(jù)量增大而線性增長，相比SAE二次增長的時間曲線，具有明顯優(yōu)勢。

3.4 PAE在推薦系統(tǒng)中的應用

在推薦系統(tǒng)的應用實驗中，本文使用了非負矩陣分解(Non-negative matrix factorization，NMF)與概率矩陣分解(Probabilistic matrix factorization, PMF)作為與PAE比較的參考算法，其中NMF與PMF均來自于PREA[15]工具包。

個性化推薦算法工具包(Personalized recommendation algorithms toolkit，PREA)是一個個性化推薦算法的工具包，其中包括了大量推薦算法的實現(xiàn)，提供了便捷的接口可供調用。學術界提出的各種推薦算法常與它進行對比，驗證準確率及效率。

在實驗過程中，本文利用均值絕對誤差(Mean absolute error，MAE)和均值平方根誤差(Root mean squared error， RSME)作為衡量算法效果的度量值。實驗中利用PAE分別以user和item作為維度坐標進行壓縮降維。為表述方便本文將兩種方法表示為PAEu和PAEi。不同算法5次實驗結果的平均值如表4所示。

表4 推薦系統(tǒng)實驗數(shù)據(jù)

由表4可以看出，當數(shù)據(jù)量較小時，在推薦結果的準確性和推薦效果的穩(wěn)定性方面NMF表現(xiàn)相對較好，而且在算法運行時間上也有一定優(yōu)勢。但隨著實驗數(shù)據(jù)量的增大，NMF與PMF均出現(xiàn)了內存不足的情況，在基于海量數(shù)據(jù)推薦任務中，兩種算法并不能很好地給出結果。而PAE的兩種算法，盡管在準確性和穩(wěn)定性方面稍弱于NMF和PMF，但可以應對海量數(shù)據(jù)的推薦任務。結果充分表明PAE可以應用于推薦系統(tǒng)中，特別是在海量數(shù)據(jù)下的應用場景。

4 結束語

本文提出了一種基于Spark的高效并行自動編碼機。通過對自動編碼機進行并行化，使之能夠高效處理稀疏大數(shù)據(jù)，同時具備正常處理非稀疏數(shù)據(jù)能力。此外，將其遷移到Spark分布式平臺，面向稀疏數(shù)據(jù)進行針對性優(yōu)化，使其大幅減少IO操作，提升算法運行效率，算法運算時間明顯縮短。本文做了大量實驗來驗證PAE的可行性與有效性，實驗建立在兩個實際應用任務上，其中分類任務驗證了PAE的高效性和PAE對特征提取的有效性。在保證特征提取有效性的前提下本文將PAE應用在推薦系統(tǒng)中，利用自動編碼機提取到的數(shù)據(jù)特征對原有數(shù)據(jù)進行填充預測，進而得出推薦結果，通過與對比算法的比較進一步驗證本算法的有效性和高效性。

[1] Srebro N, Rennie J D M, Jaakkola T. Maximum-margin matrix factorization[J]. Advances in Neural Information Processing Systems, 2004,37(2):1329-1336.

[2] Coates A, Ng A Y, Lee H. An analysis of single-layer networks in unsupervised feature learning[J]. Journal of Machine Learning Research, 2011,15:215-223.

[3] Dance C, Willamowski J, Fan L, et al. Visual categorization with bags of key points[C]// ECCV International Workshop on Statistical Learning in Computer Vision. Prague:[s.n.], 2004:1-22.

[4] 盧宏濤,張秦川.深度卷積神經網絡在計算機視覺中的應用研究綜述[J].數(shù)據(jù)采集與處理,2016,31(1):1-17.

Lu Hongtao, Zhang Qinchuan. Applications of deep convolutional neural network in computer vision[J]. Journal of Data Acquisition and Processing, 2016,31(1):1-17.

[5] 李思雯,呂建成,倪勝巧.集成的卷積神經網絡在智能冰箱果蔬識別中的應用[J].數(shù)據(jù)采集與處理,2016，31(1)：205-212.

Li Siwen, Lü Jiancheng, Ni Shengqiao. Integrated convolutional neural network and its application in fruits and vegetables recognition of intelligent refrigerator[J]. Journal of Data Acquisition and Processing, 2016，31(1)：205-212.

[6] 楊陽,張文生.基于深度學習的圖像自動標注算法[J]. 數(shù)據(jù)采集與處理,2015,30(1):88-98.

Yang Yang, Zhang Wensheng. Image auto-annotation based on deep learning[J]. Journal of Data Acquisition and Processing, 2015,30(1):88-98.

[7] Le Q V, Ranzato M A, Monga R, et al. Building high-level Ieatures using large scale unsupervised learning[C]//Proceedings of the International Conference on Machine Learning (ICML). Edinburgh, UK:[s.n.],2012:107-114.

[8] Vincent P, Larochelle H, Bengio Y, et al. Extracting and composing robust features with denoising autoencoders[C]//Proceedings of the 25th International Conference on Machine Learning. Canada:[s.n.], 2008:1096-1103.

[9] Gupta A, Maida A S, Ayhan M. Natural image bases to represent neuroimaging data[C]//30th International Conference on Machine Learning. Atlanta, Georgia, USA: International Machine Learning Society, 2013:987-994.

[10] Chen M, Xu Z, Weinberger K, et al. Marginalized denoising autoencoders for domain adaptation[J]. Computer Science, 2012: 2012arXiv1206.4683C.

[11] Zhuang F, Cheng X, Luo P, et al. Supervised representation learning: Transfer learning with deep autoencoders[C]//Proc of the 24th International Joint Conference on Artificial Intelligence. Buenos Aires, Argentina: AAAI Press, 2015:4119-4125.

[12] Bengio Y. Learning deep architectures for AI[J]. Foundations & TrendsR in Machine Learning, 2009,2(1):1-127.

[13] 黎文陽.大數(shù)據(jù)處理模型Apache Spark研究[J].現(xiàn)代計算機：普及版,2015(8):55-60.

Li Wenyang. Research on apache spark for big data processing[J]. Modern Computer, 2015(8):55-60.

[14] Chang C C, Lin C J. LIBSVM: A library for support vector machines[J]. ACM Transactions on Intelligent Systems & Technology, 2011,2(3):389-396.

[15] Lee J, Sun M, Lebanon G. PREA: Personalized recommendation algorithms toolkit[J]. Journal of Machine Learning Research, 2012,13(3):2699-2703.