非负矩阵分解的分布式算法

徐富盛,曹飞龙

(中国计量大学 理学院,浙江 杭州 310018)

非负矩阵分解的分布式算法

徐富盛,曹飞龙

(中国计量大学 理学院,浙江 杭州 310018)

提出一种解决大规模非负矩阵分解的分布式算法.非负矩阵分解一直是矩阵分解领域中的热点问题之一,已有一些相关的算法.但是,对于大规模的非负矩阵,至今尚无高效的方法.本文采用近来解决大数据的分布式思想和并行式计算方法,并将它们与传统的矩阵分解算法相结合,提出一种基于并行式计算的分布式网络算法,以此实现大规模的非负矩阵分解问题.实验结果表明,所提出的算法较一般的分布式算法与集中式矩阵分解的算法更加有效和快速.

大规模非负矩阵;矩阵分解;分布式学习算法;并行式计算

众所周知,矩阵型数据的分析在现实生活中变得越来越重要.例如,图像的处理和分析[1]、人脸识别分析[2]、压缩感知[3]、音乐分类[4]等都是典型的矩阵型数据分析问题.至今,矩阵型数据的分析,特别是非负矩阵分解问题,已成为研究热点之一.然而,由于现阶段单台计算机储存和计算能力的局限性,对一些规模较大和结构较为复杂的矩阵,传统方法难以处理.例如,矩阵逆计算就需要耗费很大的空间用于储存和大量的时间来完成计算.当然,传统的矩阵分解方法已经很成熟,例如:交替乘法更新法[5-6]、梯度下降法[7]、交替最小二乘算法[8]等,除了只能解决小规模矩阵的弊端外,仍具备较多优势,如运算简便、易于理解,以及能够较准确地分解非负矩阵.

因此,鉴于传统非负矩阵分解方法的优越性,本文将这些优越性和分析多维复杂数据的分布式网络结合起来,以此解决大规模非负矩阵的分解问题.所谓分布式网络[9]是指基于数据分块的一种学习网络,即先将高维复杂数据分割成相对较小的数据块,然后,再将数据块导入到网络中的每一个节点上进行处理,每一个节点均是一个处理器.最后,把每一个节点所得到的信息进行一致平均[10]处理,使得分割成数据块的处理与原问题的处理等价.分布式学习的框架示意图如图1.

从图1中可以看到,网络节点相互连接,其目的是能相互分享有效信息.它们的连接方式称为拓扑结构.需要指出的是,在分布式网络中用何种拓扑结构更为合适或高效,至今尚无理论证明.故本文取某一概率值来决定两个节点是否直接相连.此外,将各个节点上所得到的参数或者信息如何进行一致平均是影响分布式计算准确的一个重要因素.对此,很多研究者针对不同的实际问题给出了他们的平均一致方法.例如,文献[11]给出了最为简单的一致平均法,也称一步平均法,即直接把在每个节点所得到的参数进行算术平均.这样的一致平均法在效率上较快,并且对文献[11]中的问题得到了较好的结果.然而,文献[12]用一步平均法在处理UCI中的几个数据集时,发现所得到结果并不是全部较优的.所以,文献[12]采用了另一种利用加权迭代的方法[13]来得到所有参数的“平均”.但是,这种一致平均算法需要各节点把参数全部求解得到,之后才能进行迭代求解全局参数,即它是一种同步算法,迭代过程较缓慢.关于该问题,文献[14]把这种一致平均策略的迭代步骤分解到每一个节点中,以此实现交互.这种做法把原本需要等所有节点全部计算完所需要的参数转化成只需要求解相连节点的参数,即将同步的一致平均转化为异步一直平均,保持收敛性不变,但效率更快.然而,文献[14]的解法也存在着缺陷,即相连的节点还是需要其中一个或者多个节点求解完之后才能求解.为此,考虑到现阶段处理大数据的并行式计算方法,结合文献[15][16],本文将并行式计算运用到分布式的网络中,即先对所设置的分布式网络节点进行着色处理,把不相连的节点描成同一种颜色,然后并行计算相同颜色节点上的数据块.实验表明,我们所给出的分布式网络计算速度比一般的分布式网络计算速度快得多,并且在精度上,所提出的算法也优于一般分布式以及集中式方法.

本文组织如下,在第一节中,我们将给出非负矩阵的分解问题以及分解方法.在第二节,我们将给出分布式的一致平均算法、分布式网络的着色方法以及本文的大规模非负矩阵分解的分布式算法.在第三节中,我们将通过效率和精确度来衡量所给出的算法的优劣.最后,在第四节,我们对本文进行简要的总结.

1 预备知识

在这一部分,我们将给出所提算法需要解决的问题和解决该类问题的一个经典算法.

1.1 问题提出

本文主要目的是解决大规模非负矩阵分解问题:

(1)

其中:V是原始的大规模非负矩阵,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 分布式网络的学习算法

在这一节中,我们将给出分布式网络的一致平均算法、分布式网络的着色方法以及大规模非负矩阵的分布式学习算法.

2.1 分布式的一致平均算法

文献[13]提供一致平均法,它是一种计算全局参量的线性迭代方法.对一个通路的无向图，该算法经过线性迭代使得各个节点上的参量收敛到相同的极限值,从而达到所需的一致平均.下面,我们阐述该类一致平均法.

通常,我们假设一个网络中有L个节点,节点之间存在着一定概率地相互连接,并且每一个节点只能和自己直接相连的节点进行信息交互和共享.我们标注ks[n]作为第s个节点第n次迭代的参量估计值,并且设定其初始值为ks[0].那么,对于节点s第n次的迭代值实际上就是对与它直接相连的周围节点的值做一次加权平均:

(7)

其中:Ns是与节点s直接相连的节点的集合,Wsj是权值矩阵W中的元素,权值矩阵W依赖于网络节点的拓扑结构,它的取法可以有很多种,可参见文献[17]、[18].但是,为了证明该平均一致的算法收敛,文献[17]给出了该连接矩阵需要满足的两个条件:

W·1=1,

(8)

(9)

其中:1是分量均为1的列向量,ρ(·)是矩阵的谱半径.本文选择权值矩阵W如下:

(10)

其中:s∈Njs表示与节点s直接连接节点的集合,但是不包括节点s本身,ds表示节点s的度,d是所有节点中最大的度,本文中度是指与节点连接的边的数目.

最后,我们给出平均一致收敛的准则,即当每一个节点上参数的前后两次更新差的范数小于所设定的阈值ε:

(11)

2.2 分布式网络的着色方法

对于给定的网络图ζ,着色的策略实质上是给网络中每一个节点安排一个数字,相同的数字代表着相同的颜色,而相连节点的数字不相同.事实上,关于分布式网络,已经有很多的节点染色算法被提出[19-21],这里假定分布式网络图的颜色集合为m={1,2,…,M},sm表示第s个节点染的是第m种颜色.本文采用Welch Powell法[22]用于网络节点的着色,其算法如下.

步骤1:将无向图ζ的节点按照度数递减的次序排列;

步骤2:用第一种颜色对第一个节点进行着色,并且按照节点排列的次序,对与前面着色点不相连接的每一个点着以相同的颜色,对这些标上相同颜色的节点标上相同的数字;

步骤3:用第二种颜色对尚未着色的点重复步骤,并且标上数字;

步骤4:用第三种颜色继续这种做法,直到所有点染色完毕为止.

2.3 大规模非负矩阵分解的分布式学习算法

首先,将大规模非负矩阵进行分割,再应用分布式拓扑结构进行计算.这里矩阵分割方式是按列分割,即

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

其中:X被称为公用矩阵,Yi(i=1,…,L)被称为每一个节点上的私用矩阵,它包含着不便分享的信息.然后,下面给出两个大规模非负矩阵分解的分布式学习算法.

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

输入:大规模非负矩阵V,分布式网络的节点数L以及节点相互连接的概率值p,一致收敛的最大迭代次数N和阈值ε,矩阵分解的迭代数i、误差阈值e以及最大迭代数T;

输出:分解得到的矩阵X和Y,每次迭代的误差值err;

初始化:随机初始化矩阵X0和Y0,i=0;

步骤1:按照节点连接的概率值p建立一个随机网络,将矩阵V按列分成L份导入到不同的节点上;

步骤5:重复步骤2到步骤4,直到误差值err小于阈值e或者达到最大迭代数T.

算法2:基于着色网络的矩阵分解分布式算法

输入:大规模非负矩阵V,分布式网络的节点数L以及节点相互连接的概率值p,一致收敛的最大迭代数N和阈值ε,矩阵分解的迭代数i、误差阈值e以及最大迭代次数T;

输出:分解得到的矩阵X和Y,每次迭代的误差值err;

初始化:随机初始化矩阵X0和Y0,i=0;

步骤1:按照节点连接的概率值p建立一个随机网络,利用Welch Powell法对建立的网络进行着色,将矩阵V按列分成L份导入到不同的节点上;

步骤3:对于剩余颜色集合内的节点也采用并行式计算,计算方法与步骤2相同,直到所有节点上的X都更新完成;

步骤5:重复步骤2到步骤4,直到误差值err小于阈值e或者达到最大迭代次数T.

3 实验结果与分析

本节通过实验说明所提出算法的优越性和有效性.实验采用了两个不同规模的矩阵测试我们算法,为了更好地展现所提出的算法,我们用传统的矩阵分解以及算法1与我们提出的算法2进行比较.

3.1 参数的选择

在实验中,我们选取的两个矩阵维数分别是1 000×15 000和1 000×20 000,并且对于不同规模的矩阵,我们设立了五种概率不同的随机分布式学习网络,概率值分别取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环境下运行.

3.2 结果分析

我们将对比以下三种算法:集中式的矩阵分解算法(Foc)、基于一致平均的分布式算法(DAC-Lee)以及基于着色网络的分布式算法(D-Col).对于1 000×15 000的矩阵,算法视图效果如图2.

从图2中可以看出,我们改进的算法误差曲线明显低于其余两种算法的误差曲线,即所提出算法的精度相对较高.而且,三条曲线随着迭代次数的增大越来越接近,这表明原问题的解与我们得到的子解间的误差较小.此外,三条曲线到最后都趋于平稳.可以得到,三种算法都是收敛和有效的.最后,为了更加清晰地对比三种算法的效果以及算法的时间效率,我们做了对应于上述图2的表1.

图2 不同概率的分布式网络中规模为1 000×15 000矩阵的分解误差变化Figure 2 Error change of different probabilities of distributed network for 1 000×15 000 matrix

由表1可见,对于同一个规模上的矩阵分解,我们所提出的基于着色网络的分布式学习算法无论是从精度上还是效率上都比一般的分布式算法要好得多,同时比不进行分布式处理的算法效果还略微好一些.

接下来,我们针对规模更大的矩阵(1 000×20 000),给出我们算法的效果图,如图3.

首先,由图3可见,它与图2非常近似,总的来看,我们所改进的方法的误差要比原来方法的误差都要小,这就说明我们的算法对于规模较大矩阵是非常适用的.其次,显而易见,所有曲线趋于平缓时的迭代次数更加少了,这也说明我们的算法快速.下面,我们依旧从数字上对比三种算法的优劣性,见表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可以看出,在规模较大的非负矩阵分解中,三种算法在精度上相差不大,但是在时间效率上,我们改进后的算法要比之前的算法好得多.所以从时间和精度的两方面来看,我们所提出的算法要优于另外两种算法.

4 总结与展望

随着计算机的发展,其储存性能会越来越完善,之后所需要处理的数据也会越来越庞大和复杂.本文所提出的着色网络的分布式算法可以较好地解决关于大规模非负矩阵分解问题,同时也为矩阵形式的数据分析提供了一个新的思路.此外,比起一般的分布式算法,本文所提出的算法还结合了并行式计算的思想,这样可以更有效地提高效率.最后,我们的实验表明了所提算法的有效性和可行性.

图3 不同概率的分布式网络中规模为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 通信联系人：曹飞龙，男，教授.E-mail:flcao@cjlu.edu.cn

TP391

A