基于双线性型的非负矩阵集分解

《基于双线性型的非负矩阵集分解》由会员分享，可在线阅读，更多相关《基于双线性型的非负矩阵集分解（16页珍藏版）》请在装配图网上搜索。

1、 . . . 计算机学报2009年8期基于双线性型的非负矩阵集分解国家自然科学基金项目60872084乐 章毓晋（清华信息科学与技术国家实验室，100084；清华大学电子工程系，100084） 摘 要: 非负矩阵分解（non-negative matrix factorization，NMF)是一种常用的非负多元数据描述方法。处理数据矩阵集时，NMF描述力不强、推广性差。为解决这两个问题，并保留NMF的好特性，本文提出了非负矩阵集分解（non-negative matrix set factorization，NMSF)的概念，并在NMSF的框架下系统研究了基于双线性型的非负矩阵集分解（bil

2、inear form-based non-negative matrix set factorization，BFBNMSF)和构造了单调下降的BFBNMSF算法。理论分析和实验结果均表明：处理数据矩阵集时，BFBNMSF比NMF描述力强、推广性好。由此可认为，此时BFBNMSF比NMF更善于抓住数据的本质特征。关键字：非负矩阵集分解 双线性型 非负矩阵分解 多元数据描述 图像描述 特征提取Bilinear Form-Based Non-negative Matrix Set FactorizationLi Le, Zhang Yu-Jin（TsinghuaNational Laborator

3、y for Information Science and Technology, Tsinghua University, Beijing 100084, China;Department of Electronic Engineering, Tsinghua University, Beijing 100084，China）Abstract: Non-negative matrix factorization (NMF) is a popular technique for representations of non- negative multivariate data. While

4、treating a set of matrices, NMFis confronted with two main problems (unsatisfactory accuracy of representation and bad generality). In this paper, non-negative matrix set factorization (NMSF) is conceived to overcome the two problems and to retain NMFs good properties. Under the frame of NMSF, bilin

5、ear form-based non-negative matrix set factorization (BFBNMSF) is systematically studied, and a monotonic algorithm of BFBNMSF is put forward. Theoretical analysis and experimental results show that while processing a data matrix-set, BFBNMSF results in more accurate representation and holds better

6、generality than NMF, therefore it tends to extract more essential features of data matrix sets thanNMF.Keywords: non-negative matrix set factorization (NMSF); bilinear form; nonnegative matrix factorization (NMF); multivariate data representation; image representation; feature extraction1. 引言在信号处理、神

7、经网络、模式识别、计算机视觉以与图象工程的研究中，如何构造一个能使多维观测数据被更好地描述出来的变换方法始终是一个有基础的重要性的问题。通常，一个好的变换方法应具备两个基本特性：可以使数据的某种潜在结构变得清晰；能使数据的维数得到一定程度的约减。主分量分析、投影寻踪、因子分析、冗余归约和独立分量分析是一些最常用的数据变换方法。这些方法都可理解为在一定的限制下对数据进行变换或分解, 不同的方法间因施加于其上的限制条件不同而有本质区别, 但它们却有两个共同的特点：允许负的分解量存在（即：允许减性的描述方式）；实现线性的维数约减。不同于它们，一种新的方法非负矩阵分解(non-negative mat

8、rix factorization, NMF)由Lee和Seung在Nature上提出1, 它使分解后的所有分量均为非负值（即：要求进行纯加性的描述），并且同时实现非线性的维数约减。NMF的心理学和生理学构造依据是对整体的感知基于对组成整体的部分的感知构成（感知的过程是纯加性的过程）24, 这也符合直观的理解：整体由部分组成1. 因此，它在某种意义上抓住了生物或智能数据描述的本质。此外，纯加性（或非负性）限制的引入导致了NMF分解结果在一定程度上的稀疏性1，稀疏的描述是处于完全分布式的描述和单一活跃分量的描述间的一种有效数据描述形式5。有关NMF的研究进展可以参见新近的一篇综述文章6。作为一种

9、有效的特征提取方法，近年来NMF在计算机视觉、信号处理、模式识别和图象工程等研究领域均获得了大量的应用，其原因可归结为：NMF稀疏的描述使对数据的解释变得方便（仅有少量分量活跃使数据的组成方式变得清晰直观）1,7；NMF纯加性的描述使对数据的分析显得合理（许多物理信号中不可能存在负的组成成分）1,7；NMF相对稀疏的特征能在一定程度上抑制由外界变化（如：拍摄图像时可能遇到的物体被部分遮挡、光照条件变化和物体旋转等）给特征提取带来的不利影响8。在很多应用中，数据样本常以矩阵的形式呈现（如：灰度图像）。因为NMF的处理对象本质上是向量集，所以一般的做法是将这些数据矩阵先向量化，然后再放到NMF模型

10、中去处理1,7,8。这样做的结果是用于学习的样本量可能远远小于被学习参数的维数（典型的小样本学习问题），这会导致：NMF对数据的描述能力不强（描述的准确度不够）； NMF结果的推广性差。（图12直观地诠释了上述问题，本文第2部分会对此做详细说明）。为解决上述问题，并保留NMF的好特性，本文提出了非负矩阵集分解（non-negative matrix setfactoriz-ation，NMSF)的概念。不同于NMF处理矩阵的向量化结果，NMSF直接处理数据矩阵集中矩阵。在NMSF的框架下，本文系统研究了基于双线性型的非负矩阵集分解（bilinear form-based non-negativ

11、e matrix set factorization，BFBNMSF)，构造了一个单调下降的BFBNMSF算法。从整体上看，BFBNMSF把训练用全部数据矩阵看成一个集合做整体处理，提取出全部矩阵所共有的描述矩阵；从局部上看，BFBNMSF对矩阵集中的每一个矩阵都进行了一次新形式的（3因子）NMF。BFBNMSF对数据矩阵集的描述力强，由它得出结果的推广性也好。本文如下各节这样安排：第2节介绍NMF与其存在的问题；第3节提出并分析NMSF和BFBNMSF，构造BFBNMSF算法（严格的数学推导见附录）；第4节对BFBNMSF的性质（描述力强、推广性好）做实验验证；第5节总结全文。2. NMF与

12、其存在的问题对一个M维的随机向量进行了N次的观测，记这些观测为向量集，取，其中。定义1：NMF是求取非负的维基矩阵和非负的维系数矩阵使1 (1)的方法。由于通常设定, 所以只有在包含了随机变量的本质特征时，才可使（即：用很少量的特征可描述很大量的数据）9。NMF的实质是：在加性描述的限制下，在尽可能保持信息完整的情况下，将高维的随机模式（）简化为低维的随机模式（），这种简化的基础是估计出数据中的本质结构。从代数的观点看，的列是基，要依的存在而存在。从机器学习的角度看，包含了随机向量的某些本质特性，它除了要被用于描述训练数据外还要被用于描述非训练数据，且定了后依据一定的和间差异度量准则也就定了，

13、所以蕴涵了NMF学习结果的全部容，它是学习过程中被学习的唯一参数。此外，无论依据哪种和间差异度量准则，均为在上的非线性投影结果（或者说，对于随机向量的任意一次实现有，为对做非线性投影的结果，可为训练数据，也可为非训练数据），所以NMF体现了一种非线性的数据维数约减思路。从计算的角度讲，NMF可归结为对如下的优化问题求解： (2)其中刻画了和间的差异性，可以是任意的距离度量或散度。已有的研究结果显示，可利用的任何形式的均不是的凸函数，所以对于计算机视觉、模式识别以与图象工程等研究领域中所处理的大规模问题求解NMF的全局最优解并不现实8，可行的办法是通过交替地优化和得到相应NMF问题的一个局部解

14、1,8,9。这里应强调，交替优化过程中，求只是为了辅助求，求是进行NMF学习的根本目的。如果观测数据不是向量集，而是维的矩阵集，通常的做法是将它们矢量化为，再对做NMF得到相应的和 1,7,8，这是因为NMF的处理对象本质上是向量集。如前所述，是NMF学习过程的被学习参数；学习的过程是一个用N个样本去学习维参数的过程，它常成为典型的小样本学习过程，此时被学习对象的维数和样本量间差距巨大，两者比为，其往往达数百甚至数千。根据大数定律，小样本问题通常会导致参数估计不准确。参数估计不准确就意味着，参数对总体的刻画不准确，训练样本一般被认为是总体的简单随机抽样，那么，参数估计不准确时，模型对训练样本的

15、描述能力不会很好。训练样本的数量不够意味着，相对其所在的总体而言，训练样本显得稀疏。参数是由训练样本得到的，小样本情况下，其兼顾总体中非训练样本性质的能力不会很强，所以，此时模型推广性一般很差。综上所述，处理数据矩阵集时，NMF对数据矩阵集的描述能力通常不强，NMF结果的推广性一般很差，图1和图2直观地揭示了这两个问题。图1显示了将ORL数据库10中400幅图像（大小为）进行NMF后，利用得到的分解结果重建人脸图像的一个示例（L是保留基的个数），显然：重建图像的质量虽然随保留基的个数增多而逐渐变好，但即使保留160个基（此时压缩率仅为2.41）重建效果也不能令人满意，这说明NMF对数据矩阵集的

16、描述能力不强。在图2中，左边3幅从上到下分别取自YALE数据库11、PIE数据库12和UMIST数据库13，右边3幅从上到下依次为用构造图1时得到的那160个NMF基对左边3幅图进行重建的结果，这里的3幅重建图的质量远差于图1中用这160个NMF基得到的重建图（图1中右下角那幅图）的质量，这说明NMF对训练图的描述能力远远好于对非训练图的描述能力，即：此时NMF的推广性很差。需说明，图1和图2是基于Lee和Sueng构造的（最小二乘）算法8得到的（文中后续实验结果也都基于这个算法得到，它是事实上的NMF基准算法），当用其他算法时也一定会得到类似的结果，因为NMF处理数据矩阵集时遇到的问题源于N

17、MF本身，它不是依赖于具体算法而存在的。图2. NMF的推广性（以非训练用人脸图像的重建质量说明） JF 图1. NMF的描述力（以训练用人脸图像的重建质量说明，训练数据为ORL库的全部400幅图 ）3. NMSF和BFBNMSFNMF自被提出后受到了广泛地研究与应用，这是因为它有诸多优点，且在认知学上具有可解释性，NMF的这些优势主要源于非负性限制的引入1。但是，如上节所述，NMF处理数据集时，描述力不强，推广性差，为使矩阵集可被NMF处理而对矩阵集中的矩阵逐一矢量化是造成这两个问题的原因之一。取NMF之长（也对分解结果施加非负性限制），补NMF之短（避免矢量化操作，直接处理数据矩阵集中的矩

18、阵，文14也用类似的思路解决了PCA存在的问题），本文提出了NMSF的概念。在NMSF的框架下，文中系统研究BFBNMSF。3.1 NMSF的定义与分析对一个维的随机矩阵进行了N次的观测，记这些观测为矩阵集。定义2：NMSF是求取非负的维矩阵集、非负的维矩阵集、非负的维矩阵集以与非负的维矩阵集使 (3)的方法。这里定义的是一个一般性的操作框架，的取值要依具体模型而定，而且使，的取值也要依具体模型而定。通常，且不很大，那么只有包含了随机矩阵的本质特征时，才可能使（即：用很少量的特征可描述很大量的数据）。NMSF和NMF间有本质的区别，它们是两类完全不同的方法，因为NMF的处理对象本质上是向量集，

19、而NMSF的处理对象本质上是矩阵集；NMSF和NMF的性质会有相近之处，因为它们都对分解结果施加了非负的限制。此外，NMSF继承了NMF将高维的随机模式（）简化为低维的随机模式（）和非线性数据维数约减的特点。从机器学习的角度看，包含了随机矩阵的某些本质特性，（码本）除了要被用于描述训练数据外还要被用于描述非训练数据，且定了后依据一定的和间差异度量准则（编码）也就定了，所以蕴涵了NMSF学习结果的全部容，它们是学习过程中被学习的参数。从计算的角度讲，NMSF可归结为对如下的优化问题求解： (4)刻画了与间的差异性，可以是任意的距离度量或散度。学习的过程是用N个样本学习维参数的过程（指行维与列维的

20、乘积），只要不很大，N不特别小，这就不再是小样本学习问题。并且，无论N为多少，只要K不非常大，此时样本量和被学习参数的维数之比一定远小于做NMF时的样本量和被学习参数的维数之比。所以，可推断在处理数据矩阵集时，只要NMSF方法设计合理(包括和取值的确定，数据表示模型和优化模型选择），它会比NMF描述准确、推广性好。3.2 BFBNMSF的定义与分析NMSF是解决NMF处理数据矩阵集时遇到问题的一个一般性操作框架。从应用NMSF的角度考虑，需在NMSF框架下定义具体的NMSF方法，并用算法实现它。本文研究BFBNMSF，依NMSF的定义，此时取、和，有如下的BFBNMSF定义。定义3：BFBNM

21、SF是求取非负的维描述矩阵、非负的维描述矩阵以与非负的维双线性型矩阵集使 (5)的方法。从整体上看，BFBNMSF把所有训练用数据矩阵看成一个对象做处理，提取出全部矩阵所共用的描述因子和；从局部上看，BFBNMSF对矩阵集中的每一个矩阵都进行一次新形式的（3因子）NMF（）。 需要强调，BFBNMSF是NMSF的一种实现形式，因此BFBNMSF具有NMSF的通性，它应比NMF描述力强、推广性好。和代表了整个矩阵集的公共特性，依和而确定，和是BFBNMSF训练过程中被学习的参数，它们蕴涵了BFBNMSF学习结果的全部。3.3 对BFBNMSF的代数学和认知学解释设和是域上的线性空间，规定是维的，

22、它的基为，是维的，它的基为，定义、。考虑为上的个数据点，为上的个数据点。定义的双线性型15集合的一个子集为。，使，有 (6)即，其中，为在和下对应的矩阵表示,它与是一一对应的，常称为（与对应的）二次型矩阵。式(5)表示了一个近似产生模型，从代数学的观点看，被处理矩阵集中的所有矩阵均可被近似理解为由上的数据点和上的数据点通过双线性型映射而来（像式(6)那样），不同的被分解矩阵间的差异只源于数据产生时使用的双线性型不同。双线性型在式（5）表示的模型中起了基础性的作用，正因为此，把由式(5)表示的非负矩阵集分解命名为基于双线性型的非负矩阵集分解。从认知学的角度分析，BFBNMSF继承了NMF的构造特

23、点，考虑到了感知的特性（感知是一个纯加性的生理过程），BFBNMSF模型也要求所有分解量均为非负值，和代表了特征，代表了因感知而对和的响应强度。此外，BFBNMSF并未对和的性质做任何的要求，并且和是潜在的、无非负限制的，它们在数学上的层次高于式（5）表示的BFBNMSF模型，如果说式（5）表示的模型与感知层的神经活动有关，那么和应可解释为与比感知更深一层次的神经活动相关，表示了这一层与感知层间的联系方式（或过程）。3.4 BFBNMSF的优化模型从算法的可实现性考虑，将式（4）中取为欧几里德距离的平方最好，因为这时可用高等代数学的方法对目标函数做分解从而使优化过程中每次操作对应的优化问题清晰

24、直观且易解（见对式（9）（11）的推导和求解）。那么，BFBNMSF可归结为如下的优化问题： (7)其中是与同大小的矩阵或向量，它中的所有元素均为（一个要多小有多小的正数）。引入、以与是为了避免算法推导和执行过程中出现数学上无定义的情况（除以零）。从优化的角度看，式（7）代表了一个典型的由N个子系统组成的大系统的优化问题，为局部决策变量，仅影响第k个子系统的性能，和为全局决策变量，它们影响整个大系统的性能。文16认为解这类问题时应该利用这种等级化的结构，交替地优化、和，使式（7）中的目标函数单调地下降从而得到问题的一个局部解。这里强调，求仅是为了辅助求和，求和是进行BFBNMSF学习的根本目的

25、。因为： (8)所以, 对的求解可归结为：在固定和的情况下，解 (9)对的求解可归结为：在固定和的情况下，解 (10)经推导（见附录的第3部分）知，对的求解可归结为：在除外、和均固定的情况下，解 (11)其中，。3.5 对BFBNMSF优化模型的统计学解释式(5)表示的BFBNMSF模型可通过引入维的误差项等价地变成如下的形式： (12)即认为由加随机扰动精确生成。为解得、和，可做最大似然估计，那么 (13)假定，那么 (14)假定间是统计独立的，则： (15)那么式(13)的最大似然估计等价于 (16)进一步假设常数，则式（16）等价于 (17)因此，式（7）表示的BFBNMSF优化模型实际

26、是在假定独立同正态分布的情况下对、和做最大似然估计。3.6 BFBNMSF算法根据3.4中的优化模型，可推得了如下4个定理（证明见附录）：定理1：在和固定的情况下，令是非负的，按 (18)调整可使式（7）中的BFBNMSF目标函数值下降且非负（和分别代表哈达马乘和除，在中写代表当前的状态，在中写代表更新后的状态）。 定理2：在和固定的情况下, 令是非负的，按 (19)调整可使式（7）中的BFBNMSF目标函数值下降且非负。INPUT: 以与随机初始化、和重复如下操作，直到收敛依定理1执行Eq. (18)依定理2执行Eq. (19)p从1到 N做： c从1到做： 如果 依定理3执行Eq. (20

27、) 否则q从1到做： 依定理4执行Eq.(21)OUTPUT: 、和图3. 伪码表示的BFBNMSF算法定理3：，记，如果，在除外的、和固定的情况下，令是非负的，按 (20)调整可使式（7）中的BFBNMSF目标函数值下降且非负。定理4：在除外的、和固定的情况下，式（7）中的BFBBNSF目标函数在 (21)处达到对有非负限制时的最小值（如果，不改变；如果，使取零）。根据定理14，可构造如图3所示的单调BFBNMSF算法（伪码表示）。4. 实验这部分利用一些实验验证处理数据矩阵集时，BFBNMSF比NMF描述力强、推广性好。由于主分量分析（principal component analysi

28、s, PCA）17是最常用的数据描述工具，所以在所有的比较实验中，PCA也被作为了被比较方法之一。为使通过实验得出的验证结论客观，本节中，每一验证实验都将基于多组数据进行，这些组数据在样本量和数据类型等方面存在差异。4.1 描述力比较这3种描述方法间在描述力上的差异，需设定统一的参照指标，这个指标定为压缩率最合理。假设被处理数据矩阵集为，是维的，根据压缩率的定义18，做BFBNMSF时的压缩率为，做NMF时的压缩率为，做PCA时的压缩率也为（PCA基矩阵的列维也用表示）。图4. BFBNMSF、NMF和PCA间的描述力比较（基于ORL人脸数据库）图5. BFBNMSF、NMF和PCA间的描述力

29、比较示例（示例中原图取自ORL人脸数据库）图7. BFBNMSF、NMF和PCA间的描述力比较示例（示例中原图取自PIE人脸数据库）图6. BFBNMSF、NMF和PCA间的描述力比较（基于PIE人脸数据库的子库） 图9. BFBNMSF、NMF和PCA间的描述力比较示例（示例中原图取自MIT行人数据库）图8. BFBNMSF、NMF和PCA间的描述力比较（基于MIT行人数据库）这里的实验共使用3组数据，它们分别是ORL人脸数据库的400幅图）、PIE人脸数据库子库（所有人的正面光照下的各种姿态图）的共884幅图和MIT行人数据库的924幅图19。利用这3组数据，3种被比较方法的描述力（用做处

30、理后重建出的数据与原始数据间的相对误差表示）分别在不同压缩率（压缩率约为2的1次到7次幂）下被计算，图4、图6和图8依次勾画了3种被比较方法基于这3组数据的log2(压缩率)（平均）相对误差曲线。图4、图6和图8的纵坐标均为（平均）相对误差，这是指：为了客观，图上有关BFBNMSF和NMF的每个数据点都是一样实验设置下10次随机初始化得到的10个解算得的相对误差的平均值；PCA是有解析解的方法，有关PCA的数据点仅由一次计算得到,它不需由多次计算取平均而得。BFBNMSF的曲线在图4、图6和图8中均始终列于最下方且基本上远离NMF和PCA的曲线，这说明同压缩率下，BFBNMSF比NMF和PCA

31、对矩阵集描述得准确得多。图5、图7和图9依次对图4、图6和图8所记录的比较结果给出了图示，这些图示直观地支持了上述结论。4.2 推广性本小节比较上述3种描述方法在推广性上的差异，统一的参照指标取为描述系数量。一样描述系数量下，BFBNMSF对训练数据的描述力通常要差于NMF和PCA（因为在一样描述系数量下，做BFBNMSF时的压缩率常常远高于做NMF时和做PCA时的压缩率），如果此时BFBNMSF对测试数据的描述力好于NMF和PCA，那么说明BFBNMSF对训练数据的描述力与对测试数据的描述力间差异小于NMF和PCA对训练数据的描述力与对测试数据的描述力间差异，即BFBNMSF比NMF和PCA

32、的推广性好。表1.BFBNMSF、NMF以与PCA间的推广性比较示例（训练数据为ORL人脸数据库）方法训练结果示例推广性测试结果示例取自ORL库取自YALE库取自PIE库取自UMIST库原图BFBNMS F/压缩率=44.3重建误差0.1010.1250.1200.1170.0930.1010.1050.1070.1210.1520.1410.115NMF/压缩率=1.71重建误差0.0920.1060.1030.2680.2680.2440.1800.1960.1730.2490.2270.233PCA/压缩率=1.71重建误差0.0600.6930.0770.2000.1840.1910.

33、1530.1530.1500.1920.1670.202注：1.训练数据为ORL库的全部400幅图；2. 压缩率指对训练数据的压缩率；3.误差指重建时的相对误差表2.BFBNMSF、NMF以与PCA间的推广性比较示例（训练数据为PIE人脸数据库的子库）方法训练结果示例推广性测试结果示例取自PIE库的子库取自YALE库取自ORL库取自UMIST库取自PIE库的其他子库原图BFBNMS F/压缩率=35.69重建误差0.0900.0960.1020.1350.1130.1090.1130.1290.1470.1580.1510.1290.1470.1180.179NMF/压缩率=5.40重建误差0

34、.0630.0560.0580.2710.2400.2280.1550.1660.1970.2560.2690.2430.2320.1660.247PCA/压缩率=5.40重建误差0.0420.0340.0350.1810.1660.1580.13601580.1590.1860.1890.1850.1920.1500.203注：1.训练数据为PIE库中由9号摄像机获取的1428幅图；2. 压缩率指对训练数据的压缩率；3.误差指重建时的相对误差；4.测试用PIE库图像从左到右分别由5、29和7号摄像机拍摄（与训练图的拍摄角度不同）。表3.BFBNMSF、NMF以与PCA间的推广性比较示例（训练

35、数据为MIT行人数据库）方法训练结果示例（取自MIT库）推广性测试结果示例(取自INRIA库)原图BFBNMS F/压缩率=19.35重建误差0.1650.1610.1680.1430.1700.1360.1620.1620.1470.135NMF/压缩率=3.39重建误差0.1410.1530.1310.1960.2390.2210.2180.2340.2250.204PCA/压缩率=3.39重建误差0.0850.1190.0830.1670.2080.1780.2020.1830.1690.178注：1.训练数据为MIT库的全部924幅图；2. 压缩率指对训练数据的压缩率；3.误差指重建时

36、的相对误差表1以ORL库的400幅图为训练数据，以YALE库、PIE库和UMIST库的图像为测试数据，给出了对这3种方法的推广性进行比较实验的示例。这时，在同保留225个描述系数的情况下，做BFBNMSF的压缩率（44.3）远高于做NMF和做PCA的压缩率(1.71)，BFBNMSF对训练数据的描述力差于NMF和PCA（见表1中“训练结果示例”下重建图与其对应的重建相对误差）；但BFBNMSF对YALE库、PIE库和UMIST库图像的描述力远远好于NMF和PCA（见表1中“推广性测试结果示例”下重建图与其对应的重建相对误差）。表2和表3也给出了对这3种方法的推广性进行比较的实验示例。与表1不同

37、的是：表2以PIE库子库（9号摄像机获取的所有人的不同光照下图像）的1428幅图为训练数据，以YALE库、ORL库、UMIST库以与PIE库的其他子库（所有人的正面光照下各种姿态图，共884幅，4.1小节中的实验用过这组数据）图像为测试数据；表3以MIT库的924幅图为训练数据，以INRIA库20图像为测试数据。表2和表3的构造原则与表1一致，它们中的图例和数据也都分别直观和客观地说明了BFBNMSF 在对训练数据的描述力差于NMF和PCA的情况下，对测试数据的描述力好于NMF和PCA。由表1、表2和表3可得到的共同结论是：训练数据为数据矩阵集时，BFBNMSF结果的推广性比NMF和PCA结果

38、的推广性要好得多。5.结论非负矩阵分解（NMF）是一个较新的但越来越常用的非负多元数据描述方法。NMF的处理对象本质上是向量集，为使数据矩阵集能适于用NMF处理，矩阵集中的矩阵要被逐一矢量化。这常使对应的NMF学习问题成为典型的小样本问题，从而使NMF结果的描述力不强、推广性差，最终使处理数据矩阵集时NMF的可应用性变差。取NMF之长，补NMF之短，本文提出了非负矩阵集分解（NMSF）的概念，在NMSF的框架下，重点研究了基于双线性型的非负矩阵集分解（BFBNMSF)，分析了BFBNMSF的基本属性，讨论了BFBNMSF的构造特点和优化模型，实现了一个单调的BFBNMSF算法。理论分析和实验结

39、果均表明：处理数据矩阵集时，BFBNMSF比NMF的描述力强、推广性好。此外，在实验比较中，最常用的数据描述方法PCA也被作为了被比较项之一，实验的结果还揭示出：处理数据矩阵集时，BFBNMSF也比PCA描述力强、推广性好。需要指出，更强的描述力和更好的推广性意味着由BFBNMSF提取出的数据矩阵特征要比由NMF和由PCA提取出的数据矩阵特征更为本质。本文中提出的NMSF为解决NMF处理数据矩阵集时遇到的问题提供了一个一般性的操作框架，不同的NMSF实现形式可被采用。不同实现形式的NMSF算法将蕴涵不同的代数学、认知学和统计学解释，将有不同的特性。实现蕴涵某种或某些期望特性的其他NMSF算法将

40、是进一步的研究目标。参考文献1 Lee D D, Seung H S. Learning the parts of objects by non-negative matrix factorization. Nature, 1999, 401(6755): 788-791.2 Palmer S E. Hierarchical structure in perceptual representation. Cognitive Psychology, 1977, 9(3): 441- 474.3 Wachsmuth E, Oram M W, Perrett D I. Recognition of

41、objects and their component parts: responses of single units in the temporal cortex of the macaque. Cerebral Cortex, 1994, 4(5): 509-522.4 Logothetis N K, Sheinberg D L. Visual objectrecognition. Annual Review of Neuro- science, 1996, 19(1): 577-621.5 Field DJ. What is the goal of sensory coding? Ne

42、ural Computation, 1994, 6(4):559601,.6 Li Le, Zhang Yu-jin. Survey on algorithms of non-negative matrix factorization. Acta Electronica Sinica, 2007, 36(4): 737-743. （乐, 章毓晋. 非负矩阵分解算法综述. 电子学报, 2008, 36(4): 737-743.）7 Hoyer P O. Non-negative matrix factorization with sparseness constraints. Journal o

43、f Machine Learning Research, 2004, 5(9): 1457-1469.8 Heiler M, Schnorr C. Learning sparse representations by non-negative matrix factorization and sequential cone programming. Journal of Machine Learning Research, 2006, 7(7):1385-1407.9 Lee D D, Seung H S. Algorithms for non-negative matrix factoriz

44、ation. Advance in Neural Information Processing Systems (NIPS).Cambridge: MIT Press,2000. 556-562.10 ORL face database, at the AT&T(Olivetti) Research Laboratory, 1992. .cl.cam.ac.uk/Research/DTG/attarchive/facedatabase.html.11 YALE face database, 1997. cvc.yale.edu/projects/yalefaces/yalefaces.html

45、.12 Sim T, Baker S,Bsat M. The CMU pose, illumination, and expression database. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25(12):1615-1618.13 UMIST face database, 1997. images.ee.umist.ac.uk/danny/database.html.14 Yang J, Zhang D,Frangi AF, Yang J Y. Two-dimensional PCA:

46、a new approach to appearance-based face representation and recognition. IEEE Transaction on Pattern Analysisand Machine Intelligence, 2004, 26(1): 131137.15 Zhang Xianke, Xu Puhua. Higher Algebra. 2nd edition. Beijing: TsinghuaUniversity Press,2004.（章贤科, 许普华. 高等代数学. 第2版. ：清华大学, 2004.）16 Bertsekas D.

47、 P. Nonlinear Programming. Belmont: Athena Scientific, 1999.17 I. T. Jolliffe. Principal Component Analysis. Springer-Verlag, 2nd edition, 2002.18 Zhang Yu-Jin. Image Engineering (Volume 1: Image Processing). 2nd edition. Beijing: TsinghuaUniversity Press,2006.(章毓晋. 图像工程(上册图像处理). 第2版. ：清华大学, 2006.)1

48、9 MIT CBCL PEDESTRIAN database, at MITCBCLCenter for Biological and Computational Learning. cbcl.mit.edu/soft- waredatasets/PedestrianData.html.20 INRIA Person Database.pascal.inrialpes.fr/data/human.附录对定理14的证明定义：如果，当且仅当时有，则称为为二元辅助函数。为之后推导方便，这里预先给出2个引理。引理1：如果为的二元辅助函数，且固定后，是的严格凸函数，则依照 (A1)调整可使严格单调下降。

49、和分别为的当前值和更新后的值。证明：。引理2：为一向量，为以的元素为对角线元素的对角阵，为与大小一样的对称阵，为的特征值，则为的特征值。证明：对做特征值分解有，为以的特征值为对角线元素的对角阵，是由的特征向量组成的矩阵且中特征向量的排放顺序与特征值在的对角线上的排放顺序一致，则。1.对定理1的证明要处理的优化问题为：在固定和的情况下，解 (A2)直接对式(A2)优化是很困难的，这里解决此难题的思路是构造一个辅助函数，通过优化它来优化式(A2)。这个辅助函数的基本特点是存在解析解，因此对其做优化非常简单（这种构造思路在以后的几个定理证明中也是要反复用到的，之后就不再赘述了）。的目标函数可精简为：

50、 (A3)令 ，。取 (A4)选. 依照文9中的思路，构造 (A5)显然。因为： (A6)所以。根据引理2，半正定当且仅当半正定。与以同样的方式定义, 但的所有元素均为.仿照文9中的思路，有(A7)那么， (A8)因此,。根据定义，是的二元辅助函数。固定、和，是的严格凸函数，所以在的唯一最小值处有 (A9)那么，此最小值点处， (A10)根据引理1, (A11)当仅考虑，由式(A10)有 (A12)取，则 (A13)令和分别为的当前值和更新后的值，把式（A13）用矩阵形式表示并把和的表达式带入式（A13）, 根据式（A11）有：在和固定的情况下，按 (A14)调整，可使BFBNMSF目标函数值

51、下降。令是非负的，则也是非负的，因为这时式（A14）右边的所有变量值都是非负的。和分别代表哈达马乘和除（矩阵对应元素间的乘和除）。需要指出，如果正文式（7）中没有引入的、和，按上述过程推导出的式（A14）将面临潜在的数学上无定义的情况（除以0）。对于下文将出现的式（A15）和式（A30），情况也是类似的，不再赘述。2.对定理2的证明与在中是对偶的关系，因此，通过一个与证明定理1相类似的过程（证明定理1时，从优化入手，这里从优化入手，证明思路完全一致）可得：在和固定的情况下, 令是非负的，按 (A15)调整，可使BFBNMSF目标函数值下降且非负。和分别代表的当前值和更新后的值。3.对定理3的证

52、明因为 (A16)所以，的目标函数是 (A17)记，。 因为 (A18)并且 (A19)所以的目标函数为 (A20)这样就完成了对正文式（11）中的目标函数的推导。 记，取 (A21)依照文9中的思路，构造 (A22)显然。仿照式（A6）的推导过程有 (A23)所以。根据引理2，半正定当且仅当 半正定。仿照式（A7）和式（A8）的推导过程有， (A24)所以。根据定义，是的二元辅助函数。固定除外的、 、和, 是的严格凸函数，所以在的唯一最小值处有 (A25)那么，最小值点为 (A26)根据引理1， (A27)当仅考虑，由（A26）式有 (A28)取，则 (A29)令和分别为的当前值和更新后的值

53、，用向量形式表示式（A29），并根据式（27）有，在固定除外的、和的情况下，按 (A30)调整，可使目标函数值下降。如果，且令是非负的，执行式(A30)后是非负的；如果不能被满足，执行式(A30)后未必非负，这样不能满足BFBNMSF对分解结果非负的要求，所以这时不能用式(A30)调整。4.对定理4的证明因为(A31)所以的目标函数为： (A32)是抛物线函数，在除外的、和固定的情况下，令代表被更新后的值，根据抛物线理论，为使达到对有非负限制时的最小值应这样操作：如果的最小值点处为非负值，取为此最小值点处的值；如果的最小值点处为负值，取为0。按照这样的思路，此时在 (A33)处达到对有非负限制

54、时的最小值（如果，不改变；如果，使取零）。乐 讲师，博士，主要研究方向为非负矩阵分解、非负矩阵集分解以与它们在图像工程中的应用。E-mail:(Li Le Lecturer and Ph.D. His research interests are mainly in non-negative matrix factorization, non-negative matrix set factorization and their application on image engineering.)章毓晋教授，博士生导师，研究方向：图象工程与相关学科。E-mail: . 个人主页： (Zhang

55、 Yu-Jin professor and Ph.D. supervisor. His research interests are in image engineering and related subjects. E-mail: . personal homepage:15 / 16BackgroundNon-negative matrix factorization (NMF) is a relatively new but more and more popular method for representations of nonnegative multivariate data

56、. NMF can reveal the latent structure, feature or pattern in the data, so that it has been applied in several research fields. However, NMFis confronted with two main problems (unsatisfactory accuracy of representation and bad generality) while the processed is a matrix-set, because the object proce

57、ssed by NMF is intrinsically a set of vectors, and because the necessary vectorization for every matrix in the processed matrix-set often make the dimension of the parameter in NMFlearning to be much greater than training sample size so that the learning becomes typical small-sample learning.In this

58、 paper supported by Project 60872084 of National Natural Science Foundation of China, non-negative matrix set factorization (NMSF) is conceived to overcome the problems above and to retain NMFs good properties. As opposed to NMF, NMSF directly processes original data matrices rather than vectorization results of them. Under the frame of NMSF, bilinear form-based