非負矩陣分解的分布式算法

徐富盛,曹飛龍

(中國計量大學 理學院,浙江 杭州 310018)

非負矩陣分解的分布式算法

徐富盛,曹飛龍

(中國計量大學 理學院,浙江 杭州 310018)

提出一種解決大規(guī)模非負矩陣分解的分布式算法.非負矩陣分解一直是矩陣分解領域中的熱點問題之一,已有一些相關的算法.但是,對于大規(guī)模的非負矩陣,至今尚無高效的方法.本文采用近來解決大數據的分布式思想和并行式計算方法,并將它們與傳統(tǒng)的矩陣分解算法相結合,提出一種基于并行式計算的分布式網絡算法,以此實現大規(guī)模的非負矩陣分解問題.實驗結果表明,所提出的算法較一般的分布式算法與集中式矩陣分解的算法更加有效和快速.

大規(guī)模非負矩陣;矩陣分解;分布式學習算法;并行式計算

眾所周知,矩陣型數據的分析在現實生活中變得越來越重要.例如,圖像的處理和分析[1]、人臉識別分析[2]、壓縮感知[3]、音樂分類[4]等都是典型的矩陣型數據分析問題.至今,矩陣型數據的分析,特別是非負矩陣分解問題,已成為研究熱點之一.然而,由于現階段單臺計算機儲存和計算能力的局限性,對一些規(guī)模較大和結構較為復雜的矩陣,傳統(tǒng)方法難以處理.例如,矩陣逆計算就需要耗費很大的空間用于儲存和大量的時間來完成計算.當然,傳統(tǒng)的矩陣分解方法已經很成熟,例如:交替乘法更新法[5-6]、梯度下降法[7]、交替最小二乘算法[8]等,除了只能解決小規(guī)模矩陣的弊端外,仍具備較多優(yōu)勢,如運算簡便、易于理解,以及能夠較準確地分解非負矩陣.

因此,鑒于傳統(tǒng)非負矩陣分解方法的優(yōu)越性,本文將這些優(yōu)越性和分析多維復雜數據的分布式網絡結合起來,以此解決大規(guī)模非負矩陣的分解問題.所謂分布式網絡[9]是指基于數據分塊的一種學習網絡,即先將高維復雜數據分割成相對較小的數據塊,然后,再將數據塊導入到網絡中的每一個節(jié)點上進行處理,每一個節(jié)點均是一個處理器.最后,把每一個節(jié)點所得到的信息進行一致平均[10]處理,使得分割成數據塊的處理與原問題的處理等價.分布式學習的框架示意圖如圖1.

從圖1中可以看到,網絡節(jié)點相互連接,其目的是能相互分享有效信息.它們的連接方式稱為拓撲結構.需要指出的是,在分布式網絡中用何種拓撲結構更為合適或高效,至今尚無理論證明.故本文取某一概率值來決定兩個節(jié)點是否直接相連.此外,將各個節(jié)點上所得到的參數或者信息如何進行一致平均是影響分布式計算準確的一個重要因素.對此,很多研究者針對不同的實際問題給出了他們的平均一致方法.例如,文獻[11]給出了最為簡單的一致平均法,也稱一步平均法,即直接把在每個節(jié)點所得到的參數進行算術平均.這樣的一致平均法在效率上較快,并且對文獻[11]中的問題得到了較好的結果.然而,文獻[12]用一步平均法在處理UCI中的幾個數據集時,發(fā)現所得到結果并不是全部較優(yōu)的.所以,文獻[12]采用了另一種利用加權迭代的方法[13]來得到所有參數的“平均”.但是,這種一致平均算法需要各節(jié)點把參數全部求解得到,之后才能進行迭代求解全局參數,即它是一種同步算法,迭代過程較緩慢.關于該問題,文獻[14]把這種一致平均策略的迭代步驟分解到每一個節(jié)點中,以此實現交互.這種做法把原本需要等所有節(jié)點全部計算完所需要的參數轉化成只需要求解相連節(jié)點的參數,即將同步的一致平均轉化為異步一直平均,保持收斂性不變,但效率更快.然而,文獻[14]的解法也存在著缺陷,即相連的節(jié)點還是需要其中一個或者多個節(jié)點求解完之后才能求解.為此,考慮到現階段處理大數據的并行式計算方法,結合文獻[15][16],本文將并行式計算運用到分布式的網絡中,即先對所設置的分布式網絡節(jié)點進行著色處理,把不相連的節(jié)點描成同一種顏色,然后并行計算相同顏色節(jié)點上的數據塊.實驗表明,我們所給出的分布式網絡計算速度比一般的分布式網絡計算速度快得多,并且在精度上,所提出的算法也優(yōu)于一般分布式以及集中式方法.

本文組織如下,在第一節(jié)中,我們將給出非負矩陣的分解問題以及分解方法.在第二節(jié),我們將給出分布式的一致平均算法、分布式網絡的著色方法以及本文的大規(guī)模非負矩陣分解的分布式算法.在第三節(jié)中,我們將通過效率和精確度來衡量所給出的算法的優(yōu)劣.最后,在第四節(jié),我們對本文進行簡要的總結.

1 預備知識

在這一部分,我們將給出所提算法需要解決的問題和解決該類問題的一個經典算法.

1.1 問題提出

本文主要目的是解決大規(guī)模非負矩陣分解問題:

(1)

其中:V是原始的大規(guī)模非負矩陣,X和Y是由V分解得到的非負矩陣,XY被稱為V的非負矩陣分解.

1.2 非負矩陣分解算法

對于上述的非負矩陣分解問題,Lee和Seung[5]提出了一種簡便和實用的交替更新準則:先給定一組X和Y的初值,然后固定其中的X(或者Y),則問題(1)就轉化為一個關于Y(或者X)的線性最小二乘問題.其更新準則如下:

(2)

(3)

其中:αij和βij是梯度下降法中的權值.在文獻[6]中,Lee等人給出了如下權值更新方式:

(4)

由此,可以得出X和Y的交替迭代更新:

(5)

(6)

在文獻[6]中,Lee等人證明了這種交替迭代更新法則的收斂性,下面，我們將給出該算法與分布式網絡相結的學習算法.

2 分布式網絡的學習算法

在這一節(jié)中,我們將給出分布式網絡的一致平均算法、分布式網絡的著色方法以及大規(guī)模非負矩陣的分布式學習算法.

2.1 分布式的一致平均算法

文獻[13]提供一致平均法,它是一種計算全局參量的線性迭代方法.對一個通路的無向圖，該算法經過線性迭代使得各個節(jié)點上的參量收斂到相同的極限值,從而達到所需的一致平均.下面,我們闡述該類一致平均法.

通常,我們假設一個網絡中有L個節(jié)點,節(jié)點之間存在著一定概率地相互連接,并且每一個節(jié)點只能和自己直接相連的節(jié)點進行信息交互和共享.我們標注ks[n]作為第s個節(jié)點第n次迭代的參量估計值,并且設定其初始值為ks[0].那么,對于節(jié)點s第n次的迭代值實際上就是對與它直接相連的周圍節(jié)點的值做一次加權平均:

(7)

其中:Ns是與節(jié)點s直接相連的節(jié)點的集合,Wsj是權值矩陣W中的元素,權值矩陣W依賴于網絡節(jié)點的拓撲結構,它的取法可以有很多種,可參見文獻[17]、[18].但是,為了證明該平均一致的算法收斂,文獻[17]給出了該連接矩陣需要滿足的兩個條件:

W·1=1,

(8)

(9)

其中:1是分量均為1的列向量,ρ(·)是矩陣的譜半徑.本文選擇權值矩陣W如下:

(10)

其中:s∈Njs表示與節(jié)點s直接連接節(jié)點的集合,但是不包括節(jié)點s本身,ds表示節(jié)點s的度,d是所有節(jié)點中最大的度,本文中度是指與節(jié)點連接的邊的數目.

最后,我們給出平均一致收斂的準則,即當每一個節(jié)點上參數的前后兩次更新差的范數小于所設定的閾值ε:

(11)

2.2 分布式網絡的著色方法

對于給定的網絡圖ζ,著色的策略實質上是給網絡中每一個節(jié)點安排一個數字,相同的數字代表著相同的顏色,而相連節(jié)點的數字不相同.事實上,關于分布式網絡,已經有很多的節(jié)點染色算法被提出[19-21],這里假定分布式網絡圖的顏色集合為m={1,2,…,M},sm表示第s個節(jié)點染的是第m種顏色.本文采用Welch Powell法[22]用于網絡節(jié)點的著色,其算法如下.

步驟1:將無向圖ζ的節(jié)點按照度數遞減的次序排列;

步驟2:用第一種顏色對第一個節(jié)點進行著色,并且按照節(jié)點排列的次序,對與前面著色點不相連接的每一個點著以相同的顏色,對這些標上相同顏色的節(jié)點標上相同的數字;

步驟3:用第二種顏色對尚未著色的點重復步驟,并且標上數字;

步驟4:用第三種顏色繼續(xù)這種做法,直到所有點染色完畢為止.

2.3 大規(guī)模非負矩陣分解的分布式學習算法

首先,將大規(guī)模非負矩陣進行分割,再應用分布式拓撲結構進行計算.這里矩陣分割方式是按列分割,即

V=[V1,V2,…,VL]=X·[Y1,Y2,…,YL],

其中:X被稱為公用矩陣,Yi(i=1,…,L)被稱為每一個節(jié)點上的私用矩陣,它包含著不便分享的信息.然后,下面給出兩個大規(guī)模非負矩陣分解的分布式學習算法.

算法1:基于一致平均的矩陣分解分布式算法

輸入:大規(guī)模非負矩陣V,分布式網絡的節(jié)點數L以及節(jié)點相互連接的概率值p,一致收斂的最大迭代次數N和閾值ε,矩陣分解的迭代數i、誤差閾值e以及最大迭代數T;

輸出:分解得到的矩陣X和Y,每次迭代的誤差值err;

初始化:隨機初始化矩陣X0和Y0,i=0;

步驟1:按照節(jié)點連接的概率值p建立一個隨機網絡,將矩陣V按列分成L份導入到不同的節(jié)點上;

步驟5:重復步驟2到步驟4,直到誤差值err小于閾值e或者達到最大迭代數T.

算法2:基于著色網絡的矩陣分解分布式算法

輸入:大規(guī)模非負矩陣V,分布式網絡的節(jié)點數L以及節(jié)點相互連接的概率值p,一致收斂的最大迭代數N和閾值ε,矩陣分解的迭代數i、誤差閾值e以及最大迭代次數T;

輸出:分解得到的矩陣X和Y,每次迭代的誤差值err;

初始化:隨機初始化矩陣X0和Y0,i=0;

步驟1:按照節(jié)點連接的概率值p建立一個隨機網絡,利用Welch Powell法對建立的網絡進行著色,將矩陣V按列分成L份導入到不同的節(jié)點上;

步驟3:對于剩余顏色集合內的節(jié)點也采用并行式計算,計算方法與步驟2相同,直到所有節(jié)點上的X都更新完成;

步驟5:重復步驟2到步驟4,直到誤差值err小于閾值e或者達到最大迭代次數T.

3 實驗結果與分析

本節(jié)通過實驗說明所提出算法的優(yōu)越性和有效性.實驗采用了兩個不同規(guī)模的矩陣測試我們算法,為了更好地展現所提出的算法,我們用傳統(tǒng)的矩陣分解以及算法1與我們提出的算法2進行比較.

3.1 參數的選擇

在實驗中,我們選取的兩個矩陣維數分別是1 000×15 000和1 000×20 000,并且對于不同規(guī)模的矩陣,我們設立了五種概率不同的隨機分布式學習網絡,概率值分別取0.1、0.25、0.5、0.75和0.9,一致平均算法的最大迭代次數取300、閾值為10-6,矩陣分解的最大迭代次數是2 000、閾值為10-10.文中所有實驗均在MATLAB 8.4(2014 b),8核2.39 GHz處理器和8 GB RAM環(huán)境下運行.

3.2 結果分析

我們將對比以下三種算法:集中式的矩陣分解算法(Foc)、基于一致平均的分布式算法(DAC-Lee)以及基于著色網絡的分布式算法(D-Col).對于1 000×15 000的矩陣,算法視圖效果如圖2.

從圖2中可以看出,我們改進的算法誤差曲線明顯低于其余兩種算法的誤差曲線,即所提出算法的精度相對較高.而且,三條曲線隨著迭代次數的增大越來越接近,這表明原問題的解與我們得到的子解間的誤差較小.此外,三條曲線到最后都趨于平穩(wěn).可以得到,三種算法都是收斂和有效的.最后,為了更加清晰地對比三種算法的效果以及算法的時間效率,我們做了對應于上述圖2的表1.

圖2 不同概率的分布式網絡中規(guī)模為1 000×15 000矩陣的分解誤差變化Figure 2 Error change of different probabilities of distributed network for 1 000×15 000 matrix

由表1可見,對于同一個規(guī)模上的矩陣分解,我們所提出的基于著色網絡的分布式學習算法無論是從精度上還是效率上都比一般的分布式算法要好得多,同時比不進行分布式處理的算法效果還略微好一些.

接下來,我們針對規(guī)模更大的矩陣(1 000×20 000),給出我們算法的效果圖,如圖3.

首先,由圖3可見,它與圖2非常近似,總的來看,我們所改進的方法的誤差要比原來方法的誤差都要小,這就說明我們的算法對于規(guī)模較大矩陣是非常適用的.其次,顯而易見,所有曲線趨于平緩時的迭代次數更加少了,這也說明我們的算法快速.下面,我們依舊從數字上對比三種算法的優(yōu)劣性,見表2.

表1 三種算法針對1 000×15 000矩陣的分解精度和時間對比表Table 1 Decomposition of accuracy and time for three kinds of algorithms on 1 000×15 000 matrix

由表2可以看出,在規(guī)模較大的非負矩陣分解中,三種算法在精度上相差不大,但是在時間效率上,我們改進后的算法要比之前的算法好得多.所以從時間和精度的兩方面來看,我們所提出的算法要優(yōu)于另外兩種算法.

4 總結與展望

隨著計算機的發(fā)展,其儲存性能會越來越完善,之后所需要處理的數據也會越來越龐大和復雜.本文所提出的著色網絡的分布式算法可以較好地解決關于大規(guī)模非負矩陣分解問題,同時也為矩陣形式的數據分析提供了一個新的思路.此外,比起一般的分布式算法,本文所提出的算法還結合了并行式計算的思想,這樣可以更有效地提高效率.最后,我們的實驗表明了所提算法的有效性和可行性.

圖3 不同概率的分布式網絡中規(guī)模為1 000×20 000矩陣的分解誤差變化Figure 3 Error change of different probabilities of distributed network for 1 000×20 000 matrix

表2 三種算法針對1 000×20 000矩陣的分解精度和時間對比表Table 2 Decomposition of accuracy and time for three kinds of algorithms on 1 000×20 000 matrix

[1] 盧浩浩,卜祥曬,田旺,等.XRF-mapping圖像處理方法的研究[J].科技視界,2016(1):179-180. LU H H, PU X S, TIAN W，et, al. Study of XRF-mapping image processing method[J].Horizon of Science and Technology,2016(1):179-180.

[2] WANG Y, JIA Y, HU C, et al. Non-negative matrix factorization framework for face recognition[J].International Journal of Pattern Recognition and Artificial Intelligence,2005,19(4):495-511.

[3] NOWAK R D, WRIGHT S J. Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems[J].IEEE Journal of Selected Topics in Signal Processing,2007,1(4):586-597.

[4] FEVOTTE C, BERTIN N, DURRIEU J L. Nonnegative matrix factorization with the Itakura-Saito divergence: With application to music analysis[J].Neural Computation,2009,21(3):793-830.

[5] LEE D D, SEUNG H S. Algorithms for non-negative matrix factorization[C]//Advances in Neural Information Processing Systems. Denver: NIPS,2000:556-562.

[6] LEE D D, SEUNG H S. Learning the parts of objects by non-negative matrix factorization[J].Nature,1999,401(6755):788-791.

[7] KOMPASS R. A generalized divergence measure for nonnegative matrix factorization[J].Neural Computation,2007,19(3):780-791.

[8] PAATERO P. Least squares formulation of robust non-negative factor analysis[J].Chemometrics and Intelligent Laboratory Systems,1997,37(1):23-35.

[9] VERYKIOS V S, BERTINO E, FOVINO I N, et al. State-of-the-art in privacy preserving data mining[J].ACM Sigmod Record,2004,33(1):50-57.

[10] GEORGOPOULOS L, HASLER M. Distributed machine learning in networks by consensus[J].Neurocomputing,2014,124:2-12.

[11] SHAMIR O, SREBRO N, ZHANG T. Communication-efficient distributed optimization using an approximate newton-type method[C]// Proceedings of the 31st International Conference on Machine Learning. Beijing: JMLR.2014:1000-1008.

[12] SCARDAPANE S, WANG D, PANELLA M, et al. Distributed learning for random vector functional-link networks[J].Information Sciences,2015,301:271-284.

[13] XIAO L, BOYD S, LALL S. A scheme for robust distributed sensor fusion based on average consensus[C]//Fourth International Symposium on Information Processing in Sensor Networks. Los Angeles: IEEE, 2005:63-70.

[14] FORERO P A, CANO A, GIANNAKIS G B. Consensus-based distributed support vector machines[J].Journal of Machine Learning Research,2010,11(5):1663-1707.

[15] AKYILDIZ I F, SU W, CAYIRCI E, et al. Wireless sensor networks: a survey[J].Computer Networks,2002,38(4):393-422.

[16] MOTA J F C, XAVIER J M F, AGUIAR P M Q, et al. D-ADMM: a communication-efficient distributed algorithm for separable optimization[J].IEEE Transactions on Signal Processing,2013,61(10):2718-2723.

[17] OLFATI-SABER R, FAX J A, MURRAY R M. Consensus and cooperation in networked multi-agent systems[J].Proceedings of the IEEE,2007,95(1):215-233.

[18] ZHANG H T, CHEN Z. Consensus acceleration in a class of predictive networks[J].IEEE Transactions on Neural Networks and Learning Systems,2014,25(10):1921-1927.

[19] KUHN F, WATTENHOFER R. On the complexity of distributed graph coloring[C]//Proceedings of the Twenty-fifth Annual ACM Symposium on Principles of Distributed Computing. Denver: ACM,2006:7-15.

[20] DUFFY K R, O’CONNELL N, SAPOZHNIKOV A. Complexity analysis of a decentralized graph coloring algorithm[J].Information Processing Letters,2008,107(2):60-63.[21] LINIAL N. Locality in distributed graph algorithms[J].SIAM Journal on Computing,1992,21(1):193-201.

[22] 王海英,黃強,李傳濤,等.圖論算法及其MATLAB實現[M].北京:北京航空航天大學出版社,2010:147-150.

A distributed learning algorithm for nonnegative matrix factorization

XU Fusheng, CAO Feilong
(College of Sciences, China Jiliang University, Hangzhou 310018, China)

A distributed learning algorithm is put forward for dissolving the factorization of large-scale nonnegative matrixes.. The factorization of nonnegative matrixes is a hot problem in this field with many effective algorithms. However, the large-scale nonnegative matrixes, there have not been any highly valid algorithms. We combined the distributed concept and the parallel computing with the traditional matrix factorization methods to develop a distributed learning algorithm for complex nonnegative matrix factorization. The simulation experiments show that the proposed algorithm is more efficient and faster than the traditional distributed learning algorithm and matrix factorization methods.

large-scale nonnegative matrix; matrix factorization; distributed learning algorithm; parallel computing

2096-2835(2017)01-0119-07

10.3969/j.issn.2096-2835.2017.01.021

2016-12-12 《中國計量大學學報》網址：zgjl.cbpt.cnki.net

國家自然科學基金資助項目(No.61674277,91330118).

徐富盛(1991- )，男，浙江省衢州人，碩士研究生，主要研究方向為大數據的分布式算法等.E-mail:810447189@qq.com 通信聯(lián)系人：曹飛龍，男，教授.E-mail:flcao@cjlu.edu.cn

TP391

A