（计算机应用技术专业论文）模式表示非负矩阵分解算法的特性研究.pdf

摘要 摘要 非负矩阵分解算法( n m f ) 具有不要求信源统计独立、不要求信源为非高斯分布 的优点，因而引起了国内外学者的广泛关注。模式表示非负矩阵分解算法( p e - n m f ) 是对n m f 的一种扩展。这种改进后的算法解决了传统n m f 算法所获得的基不能 对分布不均匀数据进行有效表示的问题。 本文通过大量信号分离实验，分别从不同方面对p e - n m f 算法的特性做了以 下研究工作：( 1 ) 验证了i c a 模型在信源统计独立的情况下允许且仅允许1 个信源 为高斯分布的结论，并分别验证了p e - n m f 在信源分布统计相关以及信源为高斯 分布时均可以对信源进行有效分离的结论；( 2 ) 研究算法的初始化以及迭代次数对 算法性能的影响，实验表明初始值对算法分离效果有重要影响，并通过分析指出 这种影响不能单纯地靠增加迭代次数得到弥补；( 3 ) 研究信源之间的相关性对算法 性能的影响，实验表明算法性能随信源之间的相关性增大而降低，并指出在信源 相关性比较大时算法对信源虽然保持不错的恢复效果，却并不能很好地将不同的 真实信源区分开来；( 4 ) 研究不同强度的高斯噪声对算法性能的影响，实验表明算 法在观测信号存在高斯噪声的情况下，仍然对信源具有较强的恢复能力；( 5 ) 结合 前述研究结论，提出一种p e - n m f 结合i c a 进行信号分离的新方法，实验证明该 方法与传统的n m f 算法相比，具有对信源恢复能力更强以及可以自动确定信源个 数的优势。 关键词：非负矩阵分解模式表示非负矩阵分解独立分量分析 a b s t r a c ti i i a b s t r a c t n o n - n e g a t i v em a t r i xf a c t o r i z a t i o n ( n m f ) n o wr e c e i v e sb r o a da t t e n t i o nf o ri t s i n s e n s i b i l i t yo fw h e t h e rt h es o u r c e sa res t a t i s t i c a l l yd e p e n d e n ta n dw h e t h e rt h e yf o l l o w g a u s s i a nd i s t r i b u t i o n t h e a l g o r i t h m p a t t e r n e x p r e s s i o nn o n - n e g a t i v e m a t r i x f a c t o r i z a t i o n ( p e - n m f ) i se x t e n d e df r o mn m ff r o mt h ev i e wp o i n to fu s i n gb a s i s v e c t o r st oe x p r e s su n e v e n l yd i s t r i b u t e dd a t am o r ee f f e c t i v e l y r e s e a r c h e so nt h ec h a r a c t e r i s t i c so fp e - n m fc o n c e n t r a t eo nt h ef o l l o w i n ga s p e c t s ： ( 1 ) v e r i f y i n gt h ec o n c l u s i o nt h a ti n d e p e n d e n tc o m p o n e n ta n a l y s i s ( i c a ) m o d e lc a n o n l yp e r f o r mo nt h ec o n d i t i o nt h a tn o tm o r et h a n1s o u r c ef o l l o w sg a u s s i a nd i s t r i b u t i o n ， a n da l s ov e r i f y i n gt h ec o n c l u s i o nt h a tp e - n m _ fc a ng a i ng o o dp e r f o r m a n c ee i t h e rw h e n s o u r c e sa l es t a t i s t i c a l l yd e p e n d e n to rw h e ns o u r c e sf o l l o wg a u s s i a nd i s t r i b u t i o n ；( 2 ) s t u d y i n gt h ei n f l u e n c eo fi n i t i a l i z a t i o na n di t e r a t i o nt i m e so nt h ep e r f o r m a n c eo f p e - n m f e x p e r i m e n t ss h o wt h a tt h ei n i t i a l i z a t i o na f f e c t st h ep e r f o r m a n c es i g n i f i c a n t l y , a n di ti sp o i n t e do u tt h a tt h i se f f e c tc a nn o tb ec o u n t e r a c t e do n l yb yi n c r e a s i n gi t e r a t i o n t i m e s ；o ) s t u d y i n gt h ei n f l u e n c eo fc o r r e l a t i o na m o n gs o u r c e so nt h ep e r f o r m a n c eo f p e - n m f e x p e r i m e n t ss h o wt h a tt h ep e r f o r m a n c ed e c r e a s e sw i t l la st h ec o r r e l a t i o n a m o n gs o u r c e si n c r e a s e s a n di ti sa l s op o i n t e do u tt h a t ，a l t h o u g hi tg a i n sg o o d i s h p e r f o r m a n c et or e c o v e rt h es o u r c e s ，t h ea l g o r i t h mc a nn o td i s t i n g u i s ha m o n gr e a l s o u r c e s ；( 4 ) s t u d y i n gt h ei n f l u e n c eo fg a u s s i a nn o i s e so nt h ep e r f o r m a n c eo fp e - n m f e x p e r i m e n t ss h o wt h a ti tc a ne f f e c t i v e l yr e c o v e rs o u r c e sf r o mo b s e r v a t i o n sw h i c h c o n t a i ng a u s s i a nn o i s e s ；( 5 ) p r o p o s i n gan e wm e t h o dt or e s o l v es i g n a ls e p a r a t i o n p r o b l e m sb yu s i n gp e - n m fa s s i s t e db yi c a ，w h i c hh a st w oa d v a n t a g e sc o m p a r e dt o c l a s s i c a ln m f ：m u c hb e t t e r s i g n a ls e p a r a t i o np e r f o r m a n c ea n da u t o m a t i c a l l y a s c e r t a i n i n gt h en u m b e ro fs o u r c e s k e y w o r d ：n o nn e g a t i v em a t r i xf a c t o r i z a t i o n ( n m d ，p a t t e me x p r e s s i o nn o n n e g a t i v em a t r i xf a c t o r i z a t i o n ( p e - n m f ) ，i n d e p e n d e n tc o m p o n e n t a n a l y s i s ( i c a ) 独创性( 或创新性) 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 。究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中 不包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学 或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：马秘r 期塑：! ：三 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论 文在解密后遵守此规定) 本学位论文属于保密在一年解密后适用本授权书。 本人签名： 导师签名： 马 日期 丝墨：! ：妄 日期 垫垒：! ： 第一章绪论 第一章绪论 与目前广泛运用的独立分量分析( i n d e p e n d e n tc o m p o n e n ta n a l y s i s ，i c a ) 模型 相比，非负矩阵分解算法( n o n n e g a t i v em a t r i xf a c t o r i z a t i o n ，n m f ) 解决盲信号分离 问题，具有不要求信源统计独立、不要求信源为非高斯分布的优点，因而具有更 加广阔的应用前景。模式表示非负矩阵分解算法( p a t t e me x p r e s s i o nn o n n e g a t i v e m a t r i xf a c t o r i z a t i o n , p e - n m f ) 是对n m f 所做的重要改进，对其特性的研究具有重 要的意义。在这里，本文将首先介绍p e - n m f 的一些背景知识，然后给出文章的 结构和安排。 1 1 模式表示非负矩阵分解算法 1 1 1 非负矩阵分解算法概述 1 9 9 9 年l e e 和s e u n g t l 】在n a t u r e 上发表了非负矩阵分解算法( n m f ) ，该算法目 前已经成为一个研究的热点问题【2 - 8 1 。其计算模型与主分量分析( p e a ) t 9 1 、独立分量 分析( i c a ) l o 、矢量量化q ) 及因子分析( f a ) 等的计算模型类似，为v = 矿h ，其 n l g刀，一 中矿为行维样本空间中的聊个列样本矢量构成的观测矩阵。所不同的是对数据进 行分解的限制条件不同，非负矩阵分解以非负性为限制条件，寻找矩阵元素均大 于等于0 的形和日，同时使一定的目标函数最小。从计算的角度来看，矩阵分解 的结果中可以存在负值，但负值元素在实际问题中往往缺失物理意义。非负矩阵 分解方法则提供了一种新的矩阵分解思路，由于其分解算法实现简便、分解的结 果中不出现负值，而且具有可解释性和明确的物理意义，已经引起许多科学家和 研究人员的广泛重视。 n m f 的模型可以简单理解为对原始数据矩阵在一定条件限制下进行分解。我 们知道，盲信号分离问题可以描述为从混合的观测数据中恢复出来源信号。由此 看来，盲信号分离问题在数学上可以抽象成为矩阵的分解问题。故而n m f 算法适 用于盲信号分离问题模型。 在盲信号分离领域被广泛运用的i c a 算法有两个假设：( 1 ) 信源信号之间是统 计独立的；( 2 ) 信源信号是非高斯分布的。但是一些现实问题往往不能满足这些条 件，故而i c a 在盲信号分离领域的应用有诸多限制。另外，实际的应用问题往往 只涉及非负数据，负的数值往往是没有意义的。显然，这些都使n m f 作为一种盲 信号分离算法具有比i c a 更加广阔的应用前景。 2 模式表示非负矩阵分解算法的特性研究 1 1 2 模式表示非负矩阵分解算法的引出 在n m f 算法中，可以将分离出来的信源信号看作一组基矿，那么观测信号1 ， 就可以理解为在基形张成的空间中分布的向量【l l 】，而这些向量在基形上的坐标h 则对应于这些基在混合成观测信号时的系数。由于算法限制混合系数的矩阵是非 负的，也就是说所有的观测数据y 均是信源信号矿的加性组合，这使得基w 在空 间特性上表现为对数据y 的“夹紧 ，也就是所有的观测数据向量y 均被基向量， “包围”起来。 所谓数据的模式表示【1 2 ，可以理解为基向量w 对观测数据y 的表示能力。当 观测数据y 在空间中分布不均匀时，n m f 算法没有充分考虑基向量w 对数据表示 的有效性，有可能出现某一个基向量嵋太靠近观测数据矿的分布，而其它基向量w ， 却离观测数据y 太远的情况。基于这点考虑，模式表示非负矩阵分解算法( p e - n m f ) 在传统n m f 算法的目标函数上增加了两个惩罚项，改进了相应的迭代算法。而且 迭代算法的收敛性可以从理论上得到严格证明。 事实上，p e - n m f 算法是对n m f 算法的扩展，n m f 算法可以看作p e - n m f 在参数取定为6 9 = 侈= 0 时的一个特例。 1 2 本文工作及内容安排 本文在深入研究n m f 和p e - n m f 算法的基础上，通过大量信号分离实验，对 p e - n m f 算法分别从不同角度做了深入研究。 本文内容的安排如下： 第一章：简单介绍n m f 算法和p e - n m f 算法。 第二章：介绍n m f 算法的引出以及基本理论，并分析论证n m f 算法解决盲 信号分离的可行性及优势。 第三章：介绍p e - n m f 算法的基本理论及算法描述。 第四章：详细描述针对p e - n m f 的特性所设计的实验及结果分析。 研究工作主要有： 一：验证性实验 ( 1 ) i c a 与统计独立高斯分布信源的信号分离 ( 2 ) 统计独立统计相关的信号分离 ( 3 ) 统计独立高斯分布的信号分离 二：研究算法初始化及迭代次数对信号分离效果的影响 三：研究信源之间的相关性对算法的信号分离效果的影响 四：研究噪声对算法的信号分离效果的影响 第一章绪论 3 五：结合前述研究结论，提出一种p e - n m f 结合i c a 进行信号分离的新 方法。实验证明该方法与传统的n m f 算法相比，具有对信源恢复能力更强以 及可以自动确定信源个数两点优势 结束语：结束语为本文工作的一个总结，在简要回顾论文工作的基础上，总 结了本论文的主要研究成果及意义，并且指出了研究工作中存在的不足。 第二章n l v i f 算法理论概述 5 第二章n m f 算法理论概述 本文首先介绍了n m f 算法的引出以及发展，然后分别从问题描述、目标函数 和迭代规则三个方面详细讨论了n m f 算法的基本理论，最后讨论了运用n m f 方 法来解决盲信号分离问题的可行性及相对于i c a 的优势。 2 1 n m f 算法的引出 非负矩阵分解的思想可以追溯到1 9 9 4 年p a a t e r o 和t a p p e r 的一篇关于正 矩阵分解的文章【1 3 】。在这篇文章里他们尝试对环境方面的实际数据进行因子分析， 所得到的每一个因子是一系列的基本变量的正线性组合。在真实环境中，因子是 有具体的物理意义的，因子为正说明其起作用，因子为零说明其不起作用。因此， 对于这一类问题如果能够保证因子在进行推导、变换以及迭代运算中的非负性， 将会更加有意义。具体的问题模型如下： 设矩黼的每一列为实际观测值，矩阵矿的每一列为因子，而矩阵日的每一 行作为每一个因子的影响。用矩阵形来代表每一个元素的权重，权重代表每一个 观测值的可信度等级。p a a t e r o 和t a p p e r 提出了如下的优化模型： i i 形( y 一彳日) 1 1 2s u b j e c tt ov o ，h 0 ( 2 1 ) p a a t e r o 和t a p p e r 最先提出了利用有约束的最小二乘迭代算法( a l s ) 。这种方 法固定y 针对日进行优化。然后互换变量的角色固定日针对y 优化，重复迭代过 程。该算法的初始状态随机选定以试图得到全局最优解。 p a a t e r o 随后设计了多种算法来对上述的优化算法进行改进。他的第二个算 法，p m f 2 对上述算法进行了过多的修改，使整个应用过程复杂化不少【1 3 1 。接着 他又提出了一个更加通用的算法模型m u l t i l i n e a re n g i n e t l 4 】，来寻找满足非负条件 限制的多因子模型【1 5 】。该算法利用改进的变梯度算法来解决此优化问题。由上述 可知，p a a t e r o 等人在非负因子分析方面作了大量的工作。但是从现在的角度来看， 他们的文章中还是存在一些不足之处。首先，他们的研究只局限在非负矩阵分解 的某一具体应用领域，没有对该类算法的应用推广性做深入研究。其次，他们使 用的算法只能应用于特定的领域，无法直接推广到其他的领域。最后，他们没有 对所建立的模型进行相应的理论推导和研究，没有从理论上证明算法的收敛性以 及复杂度等，而是主要基于经验来提出，缺乏理论基础。 1 9 9 7 年，l e e 和s e u n g 在一篇关于无监督学习的文章【4 0 中独立的提出了非负 矩阵分解( n m f ) 的概念。他们研究的是如下的编码问题。假设矩阵矿的每一列是固 6 模式表示非负矩阵分解算法的特性研究 定的特征向量，为需要进行编码处理的输入向量。目标是使重构误差最小即 m i n 。i l a v h i | _ 2 。利用对于h 的不同限制我们可以得到不同的学习规则。例如独立 分量分析( e c n ) 算法对于无约束最小化，而矢量量化q ) 算法则要求h 为单位向 量。l e e 和s e u n g 提出了两种技巧对p c a 算法和v q 算法进行折衷：一种为凸编 码( c o n v e xc o d i n g ) ，即要求向量的元素均为非负且所有元素之和为l ：另一种则为 圆锥编码( c o n i cc o d i n g ) ，只要求向量的每一个元素均为非负。接着，l e e 和s e u n g 研究了如何为他们的编码策略找寻最佳的特征向量集合。这使得他们对矩阵的逼 近问题m i ni iv 一唧1 1 2 进行了研究。其中矩阵矿的每- - n 为观测数据，矽的列数远 小于y ，同时要求矿和日的每一个元素均大于零，同时要求矿的每一列的元素 和以及日的每一行的元素和l 。 为了解决上述最小化问题，他们提出了一种交替投影梯度算法。即： ” ( 1 ) 固定形，对目标函数针对日进行梯度下降法进行迭代； ( 2 ) 将日中的所有负元素置零； ( 3 ) 变换形和日的角色。固定日，对目标函数针对形进行梯度下降法进行 迭代； ( 4 ) 同时在算法中引进惩罚函数以保持形的每- - y u 的元素和以及日的每 行的元素和均为1 。 随机选取初始点并进行多次执行该算法以尝试达到全局最优解。利用这些算法， 他们发现凸编码方法能够发现隐藏在数据间的局部线性关系模型，而圆锥编码方 法能够揭示数据的特征。但是他们的文章并没有对算法提供证明，也没有进一步 研究其他可能使用的方法。 1 9 9 9 年l e e 和s e u n g 在n a t u r e 的一篇文章【1 7 】中提出了更为简化的计算矩阵分 解的两种算法。一种算法以最小化剩余的f r o b e n i u s - n o r m 为目标函数，另一种算 法则是最小化修正的k u l l b a c k - l i e b l e r 散度为目标函数。这两种算法均采用了多重 迭代梯度下降规则并选取多个不同的初始点。l e e 和s e u n g 同时对算法的迭代规则 的收敛性进行了证明，从理论上保证了算法的收敛性【1 8 】。l e e 和s e u n g 还将非负 矩阵分解算法应用到了多个领域。诸如人脸识别【1 9 1 、句法识别【2 0 1 、医学图像识别 【2 l 】等领域。至此，非负矩阵分解算法开始逐渐走入了研究人员的视线之中，成为 研究人员关注的热点问题1 2 2 - 3 0 1 。 2 2 n m f 算法理论 2 2 1 问题描述 给定n 维数据向量的集合圪。，其中m 为集合中数据样本的个数，寻找适当 第二章n m f 算法理论概述 7 的非负矩阵因子矿和h ，使得v w h 。这个矩阵可以近似的分解为矩阵和矩 阵h 的积。一般情况下选择，小于聆或者m ，从而形和日将会小于原始矩阵y 。 这样就得到了原始数据矩阵的一个压缩模型。如果假设1 ，和h 是矩阵v 和h 所对 应的列向量；则上式还可以写成列向量的形式：v = w h 。换句话说，每一个数据 列向量可以近似的看作为由以的分量为权重的矩阵形的列向量的线性组合。所以 矩阵形可以看作为对数据矩阵v 进行线性逼近的一组基。由于通常情况下可以用 少量的基向量组来表征大量的数据向量，当这些基向量能够代表数据之间潜在的 结构关系的话，那么我们会获得很好的逼近效果。 这里我们介绍两种基于形和日迭代的n m f 算澍3 1 1 由于这两种算法非常容易 进行实施同时它们的收敛特性是可以保证的，在实际应用中，两种算法的效果很 好。其他的算法可能在计算时间上更加有效，但是在具体实施上难度较大。在两 种算法的每一步迭代过程中，和日的新值通过当前值与一些因子的乘积来获 得。我们还将证明在这些迭代更新规则下，逼近的效果是可以保证的。在实际应 用中，这意味着只要根据规则重复迭代，算法一定会保证收敛到某个局部优解 2 2 2 目标函数 为了找到一个近似分解v w h ，我们首先需要定义一个可以决定逼近效果的 目标函数。这样一个目标函数可以用一些确定两个矩阵4 和曰之间“距离 的方 法来构造。一个有用的方法就是衡量彳和口之间简单的欧氏距离： | la - b l l 2 = ( 4 ，一岛) 2( 2 2 ) 耖 它的下限是o ，当且仅当a = b 的时候上式为0 另一个比较有用的尺度是： d ( a i b ) = z ( 4 , 1 0 9 詈一鸣+ 岛) ( 2 3 ) 0 “目 与欧氏距离一样，它也的下限也是0 ，而且也是当且仅当彳= 召的时候等0 。 但是它不能被称之为“距离 ，因为这里彳和召之间没有均衡性，所以我们谓之彳 和b 的“区别”。当 4 = 岛= 1 的时候它退化成为k u l l b a c k l e i b l e r 分歧，这 样4 和曰就可以看作规格化概率分布。 现在我们考虑n m f 的两个可选公式作为最优化问题 问题- - ：s u b j e c tt ow h 0 m i n i m i z ef iv w h 1 1 2 ，对于任意形，日 问题二：s u b j e c tt ow h 0 m i n i m i z ed ( vi lw h ) 对于任意形，日 8模式表示非负矩阵分解算法的特性研究 虽然上述两个目标函数| | v w h1 1 2 和d ( vi | w h ) 对于单独的y 或h 来讲均是 凸函数，但是同时对于w 和日来讲，却不是凸函数。因此要找到个解决上述两个 问题的全局最优解是不太现实的。但是还是有不少优化的技巧可以运用来寻找一 个局部优解。梯度算法也许是最简单，最易行的方法，但是其收敛速度非常缓慢。 而且基于梯度的收敛算法对于步长的选择非常灵敏，这对于实际应用来讲实在不 是非常方便。 2 2 3 迭代规则 定理一： 比卜比篙舞，既卜既黯 ( 2 - 4 ) i | v w h i l 2 单调不增，当w 和h 固定时，i lv w h i j 2 保持不变 定理二： 见“卜也哗糍 ，形。帆晋陆5 ， j d ( 矿| lw h ) 单调不增，当形和h 固定的时候，d ( v | iw h ) 保持不变 我们可以将这些迭代规则与梯度方法进行比较。在特定条件下，能够减小 | lv w h1 1 2 的h 的增量迭代规则写成如下形式： 月乙卜厶乙+ 仉。【( 形2y ) 。一( 形7w h ) 。】 ( 2 - 6 ) 如果上式中的均设为某一正的极小值时，则上式与梯度下降法等价。只要 这个数字足够小，迭代规则一定会使i lv w h1 1 2 减小。 如果我们假设。丽巧1 - 1 芴。t u 瓦这样我们就得到了定理一中有关h 的迭代规 则( 2 4 ) 。类似的还有 卜玩+ 陆击一莩既 同理，当取为某一正的极小值时，迭代规则一定会使d ( 矿l lw h ) 减小。如 果我们假设2 竺z , 量w 由于是我们得到了定理二中有关口的迭代规则( 2 5 ) 。这里需 要说明的是我们选择的其实并不一定足够小，似乎在理论上无法保证目标函数 递减。但是，已经证明收敛形是可以保证的【1 1 】。 第二章n m f 算法理论概述 9 2 3 盲信号分离与汪 盲信号分离( y - 称盲源分离) 具有极其广泛的应用。近年来，盲信号分离问题己 成为信号处理和神经网络等领域共同关注的研究热点【3 2 。3 9 】，并获得了迅速发展。 所谓盲信号分离，是从信源信号的混合信号中恢复出信源信号。这里“盲有两 个含义：( 1 ) 信源信号是未知的和需要估计的；( 2 ) 信源信号如何混合是未知的。 对于线性混合模型 x = as ( 2 8 ) m x n所x ，开 其中s 为由，个”维信源信号所构成的信源矩阵，x 为由m 个n 维观测信号构 成的观测矩阵，彳为垅r 混合矩阵，我们认为，盲信号分离问题实质上就是矩阵 分解问题：将观测信号所构成的矩阵x 分解为混合矩阵彳和信源信号所构成的矩 阵s 的乘积，从而从观测x 中恢复出信源信号s 。i c a 4 0 进行盲信号分离的基础 是中心极限定理：在一定条件下，多个非高斯分布统计独立随机变量( 信源) 的和的 分布更趋于高斯分布，因此i c a 方法实现盲信号分离的过程是这些方向的搜索过 程，使得观测在这些方向上投影的分布最不高斯。基于i c a 进行盲信号分离的上 述思路，i c a 在进行线性混合模型的盲信号分离上有两个明显的假设：( 1 ) 信源是 统计独立的；( 2 ) 信源是非高斯的。显然，这两个假设极大限制了i c a 在盲信号分 离上的应用和有效性，因为对于实际的盲信号分离问题，往往信源之间存在一定 程度的统计相关性，而运用i c a 进行盲信号分离的性能却因这两个假设的满足程 度而急速下降。 若信源信号是非负的，线性混合的混合系数也是非负的，我们称这样的线性 混合模型为非负线性混合模型，即 x = a s ，s o ，a 0( 2 9 ) 其中矩阵0 表示这个矩阵中的所有元素都0 。我们认为这样的线性混合模 型更符合多数实际的盲信号分离问题：在许多情况下信源信号取负值没有物理意 义( 如声音信号，信号能量，图像象素的亮度，基因表达水平等) ，而信号的混合也 只有“加 性混合而减运算却没有实际意义( 如信号能量的叠加，多幅图像的混叠， 基因表达水平的部分体积效应p a r t i a lv o l u m ee f f e c t l 4 1 1 、雷达回波等) 。从这个意义 上讲，非负线性混合模型比线性混合模型更有意义，而针对此模型的盲信号分离 结果也才有物理意义。实质上，基于此模型的盲信号分离问题( 这里称为非负盲信 号分离问题) 是一个非负矩阵分解问题。非负矩阵分解问题可描述为：已知一个非 负矩阵矿，要找出非负的n ，矩阵和非负的，m 矩阵何，使： ： v = w h ( 2 - 1 0 ) 由非负矩阵分解的上述描述知，n m f 是用非负性约束来获取数据表示的一种 l o 模式表示非负矩阵分解算法的特性研究 方法，这一约束导致了基于部分的表示，因为所获取的数据只允许是原始数据的 加性组合，而不存在减运算。若取式( 2 1 0 ) 的第f 列表示即1 ，= w h 。，其中v ，和h ，分 别是矿和日的第f 列，则每一数据v ，都是w 的列( 彬，形) 的正线性组合( 正线 性混合) ，组合的系数为h ，的元素值。这样，形就可认为是对y 进行线性估计而优 化了的基。、 我们认为，既然的列是非负数据空间的非负的基，它们就具有线性无关性， 而这种线性无关性，从统计的意义上说，即为一定程度的统计独立性。这可从以 下两方面加以说明，并记彬所对应随机变量为，w 。，w ，的归一化原点相关系数 为，( 嵋，w ，) ，即 帆，2 丽e ( w i w j ) 晶叫峨， 7 ( w i ，w j ) ：毒坠l , 1 芸1 丝、j 兰j 奖j 州形，) 7 2 面幕霄雨丽吖缈i ， ( 2 - 1 1 ) ( 2 - 1 2 ) 考虑形与形，线性无关的极端情况：形与，正交的情况。这是，有形1w = 0 ， 从而有，( w ，w ，) = 0 ，表明w i ，w ，一阶统计独立。 考虑形与形，线性无关的相反情况：形与形，线性相关的情况。这时有 彬= k w ，k 为某正常数。从而有，- ( 心，w ，) = + 1 ，表明w ，w ，是一阶统计相关的。 实际上，作为非负数据空间的非负基，形所具有的线性无关性本身就介于上 述两种情况之间，即彬，矿，的相关系数，( 彬，形，) ( 一1 ，1 ) ，从而所找到的非负基将允 许基向量之间一定程度的统计相关，这成为我们运用n m f 进行对非负线性混合模 型的非负盲信号分离的基础，即在用n m f 进行盲信号分离时，无须信源是统计独 立的，甚至无须信源是一阶统计独立的，只要求信源之间不存在一阶原点统计相 关( 从这个意义上，n m f 似乎可从观测数据中解一定程度的原点统计相关) ，同时 也没有信源为非高斯分布的假设。这些都将使n m f 作为一种盲信号分离方法，具 有比i c a 更为广阔的应用前景。 在我们的后续实验中，我们采用如下的n m f 算法【4 3 】： 第二章n m f 算法理论概述 既卜既高岳玩 既卜轰 见卜吃莩既面岳 ( 2 - 1 3 a ) ( 2 - 1 3 b ) ( 2 - 1 3 c ) 目前看到的所有有关n m f 应用的文章采用的均为这一算法，其中式( 2 1 3 b ) 是对的列的归一化，以避免矩阵分解中的s c a l i n g 问题。该算法的收敛性已得到 证明，详见文献【4 3 1 。 显然，为了运用n m f 获得对观测数据的盲信号分离结果，我们应该采用i c a 的转置模型，即 x r = s r a r ( 2 1 4 ) + 对上述模型进行n m f 所获得的结果形即为信源矩阵的转置s r ，即所获得的 形的列就对应了所恢复出的信源信号。 总之，n m f 算法可以解决盲信号分离问题，而且比广泛运用的i c a 具有2 点 优势：( 1 ) 不要求信源统计独立；( 2 ) 不要求信源非高斯分布。 02 4 本章小结 本章介绍n m f 的基本理论，从理论上分析了用n m f 做盲信号分离的可行性， 并着重分析了n m f 做盲信号分离对比i c a 的优势所在：( 1 ) 不要求信源统计独； ( 2 ) 不要求信源为非高斯分布。 。 大量实验表明n m f 算法本身并不总是收敛到希望的解上【l l 】，这是因为一个空 间的基理论上并不唯一，从而同一矩阵可以有多种不同的矩阵分解结果；另一个 原因是n m f 算法本身可能收敛到局部极小，这是i c a 算法也同样存在的问题。另 外，n m f 算法需要人为指定基的个数。 第三章p e - n m f 算法理论 第三章p e n m f 算法理论 本文第l 节将介绍数据的模式表示的概念；第2 节介绍基于这一概念对n m f 算法提出的一种改进算法，称之为模式表示非负矩阵分解算法( e x p r e s s i o nn o n n e g a t i v em a t r i xf a c t o r i z a t i o n ，p e - n m f ) ；第3 节是对p e - n m f 算法的详细描述。 3 1 数据的模式表示 设，w 2 w ，为，个线性无关的n 维向量，称由这，个向量的任意正线性组合 ( 组合系数均大于等于o ) 所构成的空间为由基，叱w ，所张成的正子空间并称 ，w 2 w ，为这一子空间的数据的模式表示。显然，由n m f 实现的对数据矩阵矿的 分解，所获得的基m ，w 2 嵋通常是非唯一的，如图3 1 所示。 图3 1 数据在子空间中的模式表示 如图3 1 所示，数据y 可由( w l ，w 2 ) 正线性表示，亦可由( w l ，w 2 ) 正线性表示。 因此我们的问题是： ( 1 ) 数据处于哪个正子空间； ( 2 ) 这个正子空间的特征基是怎样的： ( 3 ) 数据在这个特征基上表示是怎样的。 我们认为，在这里找数据的特征基是解决问题的关键。能够真正描述数据模 式的特征基应具有以下特点： ( 1 ) 特征基中的基向量应尽可能正交 以保证数据y 可由嵋，w 嵋的正线性组合表示； ( 2 ) 特征基应尽可能集中( 靠近数据集矿) 以使数据正好被夹在特征基所张的正子空间中； ( 3 ) 数据整体在特征基下每一基的表示系数应尽可能平衡 也就是说数据是这些基而不是其中的某个基或某些基张成的。即：在 表达数据模式上这组基中的每一个基都是不可缺少的。 1 4模式表示非负矩阵分解算法的特性研究 我们认为同时满足上述三条的基更具对数据的结构表征特征，是真正描述数 据模式的特征基。 图3 2 分别表示了基过于正交、基过于集中和夹紧数据的基所造成的数据在基 下表示的不平衡情况。显然，图3 2 1 的基( 磁，职) 过于正交，基( 彤，) 可以更 有效地表示数据的模式特征；图3 2 2 的基过于集中，不能保证数据在这组基上表 示系数的非负性；图3 2 3 示出的是数据分布不均匀，但基向量仍将数据整体夹紧 在其中的情况。由于数据分布的不均匀性( 靠近w 的数据密度高) ，使得w 对数 据模式具有更强的表达能力，显然这是不合理的。另外，本图中的y 与图3 2 1 中 的y 处于相同区域但分布不均匀，却与图3 2 1 中数据集有相同的基，这也从另一 个角度说明了这样的基不能很好的表达数据的模式特征。相反，( 嵋，) 具有更好 的数据模式表示能力。 o 3 2 1 基向量过于正交3 2 2 基向量过于集中3 2 3 基向量的数据表示能力不平衡 图3 2 特征基未满足模式表示要求的例子 从特征基对数据模式的表达能力上讲，图3 2 1 中的基基所造成的是数据只是 基( 彤，暇t ) 所张成的子空间的一个子集，这样的基虽然能够表达数据的模式( 这 即为目前n m f 所获得的分解，通常是非唯一的) ，但却造成了表达能力的浪费； 图3 2 2 的基所造成的只是一部分数据处在( 彤，暇 ) 所张成的正子空间中，从而这 组基( 彬，职) 无法正确的表达所有的数据，因此这样的基的数据表达能力不足； 对于图3 2 3 的情况，尽管数据正好处于( 彤，职- ) 所张成的子空间中，既没有造成 表达能力的浪费，又没有造成表达能力的不足，但却由于数据分布得不均匀而造 成了数据在各个基上的表达能力的不平衡，从而没有真正的实现对数据的有效表 达。作为描述数据模式的特征基，数据在其各个基上的表达能力显然应该具有平 衡性。 由此可以看到，同时满足上述三条的基对于数据具有最好的表达能力和结构 表征特征，是真正描述数据模式的特征基。 3 2 p e - n m f 的优化准则 以下基于特征基的三条要求，进行分别讨论。 第三章p e - n m f 算法理论 1 5 ( 1 ) 特征基中的基向量应尽可能正交，以保证数据v 可由，w 2 w r 的正线性 组合表示。如果出现图3 2 2 中所示向量过于集中情况，则日中会有小于 0 的数据出现，这样以来就不符合我们的非负前提，应当避免这种情况。 如此则要求： w m 寸m i n f ， ( 3 1 a ) ( 2 ) 特征基应尽可能集中( 也就是尽可能靠近数据集矿) ，以使数据正好被夹在 特征基所张的正子空间中。本条准则目的是尽量避免出现图3 2 1 所示向 量过于正交情况。 。 由于在算法的每次迭代过程中都将基向量w ，归一化为1 ，即w ，的分 量和为1 ，或，：w 撑= 1 ，显然这表明w i 是从原点到超平面，( 当为2 维 ，了。 时，是一过( 0 ，1 ) ，( 1 ，o ) ) 的直线的一个矢量，如图( 3 3 ) 所示依据特征基向量是 尽可能集中的特征向量显然有0jm i n ，即： m w 专m i n f = 1 ， ( 3 - l b ) ，圈3 3 特征基不慈图 ( 3 ) 数据整体在特征基下每一基的表示系数应尽可能平衡。 ，依据基向量应尽可能正交h 2 1 ，h j 描述了数据在w l ，w 2 w ，上的表示系 数，- 即在w 1 ，坼的表达能力，为使每个基在表达数据模式上具有尽可能相 同的表达能力，九应尽可能稀疏，即找这样的基w 使得h 尽可能稀疏，亦即t m i n ( 3 一l c ) 匐 、 这样我们就得出了p e - n m f 的数学描述： n 妇 以矾川2 j 1 陟一脚| | 2 + 口吾+ 等 ( 3 - 2 ) i - s 工 w ，0h 0 这个优化问题的解( 嵋，w 2 w r ) 即为样本数据矿的特征基。显然使 e ( 形，日) 专m i n 且结构误差& = 去陟一唧1 1 2 = 0 ( 或小于某给定的可接受的上限) 的，是数据v 所处特堑子空间的维数。一旦我们找到了数据的特征基w ，对于任意 1 6模式表示非负矩阵分解算法的特性研究 数据1 ，其在该特征基上的表示系数可以通过最小二乘法求解v = w h 获得，为 h = ( w7 形) 一1w r v 。 3 3 p e 心算法描述 对于式( 3 2 ) 的p e n m f 问题圪。= 。，h r 。，我们有如下的迭代算法以获取非 负矩阵w 和日： s t e p l ：进行初始化，将形，日赋以非负随机矩阵： s t e p 2 ：将w 的每- - y u 进行归一化 并用以下公式更新矿中任一行w 的元素w 口 w a t + l = _ w 口f 而开( v 丽h r ) ( 3 - 3 ) 其中v 为y 中与w 对应的行，肘为对角元素全为m 其余元素全为1 的r x 矩 阵。用以下公式更新日中任- - y u h 的元素吃 牡w 蒜： ( 3 - 4 ) 其中1 ，为矿中与h 对应的列，为元素全为1 的聆雠；列晦量二 s t e p 3 ：设定s 为一很小的数，若 e j 形，m 2 扣矿一掰1 1 2 + 口善嘞蒸岛 山 图4 1 6 不同信源个数时平均s n r 随迭代次数变化对比图 蓝色虚线：信源个数为2 ；红色实线：信源个数为3 。 现在分析图4 1 6 ： ( 1 ) 如蓝色虚线所示：信源个数为2 时，算法在不同初始化的情况下的信号分离效 果均是随迭代次数变得越来越好。但是，比较第3 0 0 0 次迭代的结果可以发现， 算法初始化不同时信号分离效果有相当大的差距，而且分离效果没有向某一 水平收敛的趋势。这在统计上表现为s n r 分布的s d m r 随迭代次数增大。 总之，在信源个数为2 的时候，算法初始化对分离效果有比较大的影响， 这种影响即使增加迭代次数也不能弥补。这一现象产生的根源是n m f 算法本 身并不总是收敛到希望的解上，因为一个空间的基理论上并不唯一，从而同 一矩阵可以有多种不同的矩阵分解结果。 ( 2 ) 如红色实线所示：当信源个数为3 时，算法陷入两个局部极小，分别是在 s n r = 1 4 及s n r = 2 9 附近。可以看到，不同的初始值分别以不同的速率靠近这 第四章实验分析与设计 3 5 两个局部极小。 。 总之，算法在信源个数为3 的时候，初始化的不同可能会使算法陷入不 同的局部极小，并且收敛到局部极小的速率也不同。 结论：算法初始化对信源分离效果有重要影响，且这种影响不能单纯地靠增加迭 代次数来得到弥补。 这种影响是因为算法陷入不同的局部极小。这种情况下，迭代次数的增 加可以使算法逼近局部极小，但是不能帮助算法跳出局部极小。 基于上述考虑，我们在应用中应该尽可能选取比较好的初始化值，而不是像 3 3 节算法描述中所述用随机值进行初始化。我们将在第4 6 节讨论的一种p e - n m f 结合i c a 的信号分离思路即是部分基于这一点考虑。 4 4 信源之间的相关性对p e n m f 信号分离效果的