非负矩阵分解算法

1非负矩阵分解算法1摘要:非负矩阵分解（NMF）是一种处理多变量数据分解极为有效的方法。这里分析了两种不同的NMF多重算法。它们只在矫正规则2中使用的乘法因子上略有不同。一种算法可以昀小化传统的昀小二乘误差，而另一种算法则能将广义的Kullback-Leibler发散度昀小化。两种算法的单调收敛性均可使用类似于用于证明期望昀大化算法收敛的辅助函数来证明。这些算法采用对角比例梯度下降的方式，重新调整因子被昀优选择以确保收敛。关键词：非负矩阵分解，NMF多重算法,昀小二乘误差,K-L发散度一.介绍无监督的学习算法，如主成分分析和矢量量化，一种解释是对不同约束条件下的数据矩阵进行分解的算法。根据所使用的约束，所得到的因子可以显示出具有非常不同的表征性质。主成分分析仅执行弱1Translatedby卢天培.2updaterules.2正交约束3，导致了非常分散的表示，这种表示采用用消去法生成变异性[1,2]。另一方面，矢量量化使用一个有力的全局昀优约束，从而将数据聚类成互相独立的原型[3]。我们以前已经证明，非负性是矩阵分解中有用的约束来进行数据的部分性学习[4,5]。非负基学习向量用于分布式（仍然采用稀疏组合产生表达式）[6,7]。在本文中，我们详细分析了从数据中学习昀优非负因子的两种数值算法。二.非负矩阵分解我们正式考虑算法来解决以下问题：非负矩阵分解（NMF）给定非负矩阵𝑉，找到非负矩阵因子𝑊和𝐻，使得：𝑉≈𝑊𝐻(1)NMF可以以下列方式应用于多变量数据的统计分析。给定一组多元n维数据向量，将向量放置在n×m矩阵𝑉的列中，其中m是数据集中的示例数。然后将该矩阵近似分解为n×r矩阵𝑊和r×m矩阵𝐻.通常r小于n或m，使𝑊和𝐻小于原始矩阵𝑉.得到原始数据矩阵的压缩版本。3Principalcomponentsanalysisenforcesonlyaweakor-thogonalityconstraint,resultinginaverydistributedrepresentationthatusescancellationstogeneratevariability[1,2]3方程式(1)近似的意义在于它可以逐列重写为v≈𝑊𝐻，其中𝑣和ℎ是𝑉和𝐻的对应列。换句话说，每个数据向量𝑣近似的由𝑊的列进行线性组合，用ℎ的分量进行加权。因此，𝑊可以被认为是包含对于𝑉中的数据的线性近似优化的基础。由于相对较少的基向量用于表示许多数据向量，所以在数据中只有在基向量发现潜在的结构时才能实现良好的近似。本文不是关于NMF的应用，而是侧重于找到非负矩阵分解的技术方面。当然，其他类型的元分解因子在数值线性代数中已经得到了广泛研究，但是这种非负性约束使得以前的很多工作都不适用于目前的情况[8]。在这里，我们讨论了基于W和H的迭代矫正的两种NMF算法。由于这些算法易于实现，其收敛性能得到保证，我们发现它们在实际应用中非常有用。其他算法可能在整体计算时间内更有效，但是更难实现，并且不能将其推广到不同的成本函数。只有一个因素类似于我们的算法，已经被用于去卷积发射断层扫描和天文图像[9,10,11,12]。在我们的算法的每次迭代中，通过将当前值乘以取决于方程式（1）中的近似质量的一些因子来找到W或H的新值。我们证明近似的质量随着这些乘法矫正规则的应用而单调改善。实际上，这意味着矫正规则的重复迭代保证收敛到局部昀优矩阵分解。三.成本函数4为了找到一个近似分解𝑉≈𝑊𝐻，我们首先需要定义量化近似质量的成本函数。可以使用两个非负矩阵𝐴和𝐵之间的距离的一些度量来构造这样的成本函数。一个有用的方法只是𝐴和𝐵之间的欧几里得距离的平方[13]。𝐴−𝐵1=𝐴34−𝐵34134(2)下限为零，距离消失当且仅当𝐴=𝐵.另外一个有用等方法为：𝐷(𝐴|𝐵=(𝐴34𝑙𝑜𝑔;==−𝐴34+𝐵34)34(3)像欧几里德的距离一样，这也是下限为零，当且仅当A=B时才距离消失。但它不能被称为“距离”，它在A和B中不对称，所以我们把它称之为A对于B的“散度”。它减少到K-L散度或相对熵，当𝐴3434=𝐵34=134,使得A和B可以被认为是归一化的概率分布。我们现在考虑NMF的两种替代方案作为优化问题：问题1昀小化||V−WH||1用W和H，约束条件𝑊,H≥0.问题2昀小化𝐷(𝑉||𝑊𝐻)用W和H，约束条件𝑊,H≥0.尽管方程||V−WH||1和𝐷(𝑉||𝑊𝐻)在仅W下凸或在仅H下凸，它在两者之下不为凸。因此，期望一种算法在找到全局昀小值的意义上解决问题1和2是不切实际的。然而，有许多数值优化技术可以应用于寻找局部昀小值。5梯度下降法4可能是实现起来昀简单的技术，但其收敛速度可能很慢。其他方法如共轭梯度具有更快的收敛（至少在局部昀小值附近），但是比梯度下降更复杂[8]。并且，基于梯度的方法的收敛具有对步长选择非常敏感的缺点，这对于大型应用非常不方便。四．乘法矫正规则我们发现，以下“乘法矫正规则”是解决问题1和2的速度和易于实施的一个很好的妥协方法。理论1欧氏距离|𝑉−𝑊𝐻|在（4）的矫正规则下非减𝑯𝒂𝝁←𝑯𝒂𝝁(𝑾𝑻𝑽)𝒂𝒑(𝑾𝑻𝑾𝑯)𝒂𝒑 𝑾𝒊𝒂←𝑾𝒊𝒂(𝑽𝑯𝑻)𝒊𝒂(𝑾𝑯𝑯𝑻)𝒊𝒂 (4)当且仅当W和H同一点时，欧几里得距离固定。理论2散度D(V|WH)在（5）的矫正规则下非减𝑯𝒂𝝁←𝑯𝒂𝝁𝑾𝒊𝒂𝑽𝒊𝝁/(𝑾𝑯)𝒊𝝁𝒊𝑾𝒌𝒂𝒌 𝑾𝒊𝒂←𝑾𝒊𝒂𝑯𝒂𝝁𝑽𝒊𝝁/(𝑾𝑯)𝒊𝝁𝒊𝑯𝒂𝒗𝒗(5)当且仅当W和H处于静止状态时，散度是不变的。这些定理的证明在后面的部分给出。现在我们注意到，每个矫正都是乘以一个因子。特别地，当V = WH时，可以直观地看出这个乘数因子是一致的，所以完美的重构必然是矫正规则的固定一点点。4Gradientdescent6五．乘法与加法矫正规则可以将这些乘法矫正与梯度下降产生的矫正进行对比[14]。特别地，对于减小平方距离的H的简单加法矫正可以被写为：𝐻TU←𝐻TU+𝜂TU[(𝑊X𝑉)TU−(𝑊X𝑊𝐻)TU](6)如果𝜂TU设置为小正数，这相当于常规梯度下降方法。只要数字充分的小矫正会减少到|𝑉−𝑊𝐻|。如果我们对对角进行重新调整5变量并设置𝜂TU=Z[\(]^]Z)[\(7)那么我们获得在定理1中给出的H的矫正规则。注意，该重新调整会得出乘子因子（分母中的梯度的正分量和因子的分子中的负分量的绝对值）。对于散度，对角线重新调整梯度下降采取以下显示：𝐻TU←𝐻TU+𝜂TU[𝑊3T𝑉3U/(𝑊𝐻)3U3−𝑊3T3](8)同样的，如果𝜂TU设置为小正数，这相当于常规梯度下降方法。只要数字充分的小矫正会减少到D(V|WH)。如果设置：𝜂TU=Z[\𝑾𝒊𝒂(9)那么我们获得在定理2中给出的H的矫正规则。该重新调整同样会得出乘子因子（分母中的梯度的正分量和因子的分子中的负分量的绝对值）。5diagonallyrescale7由于我们对𝜂TU的取值不是很小，似乎不能保证这种重新缩放的梯度下降降低成本函数。令人惊讶的是，如下一节所示，这是确定的情况。六．衔接证明我们将利用类似于期望昀大化算法中使用的辅助函数[15,16]证明定理1和2。定义1G(h,ℎ′)是𝐹(ℎ)的辅助函数，如果下面的条件成立：𝐺ℎ,ℎd≥𝐹ℎ, 𝐺ℎ,ℎ=𝐹(ℎ)(10)辅助函数说一个有用对概念，因为下面引理（Fig.1中的插图）引理1如果𝐺是一个辅助函数，那么𝐹是非增在以下条件下：ℎefg=argmink𝐺(ℎ,ℎe)(11)证明：𝐹ℎefg𝐺ℎefg,ℎe≤𝐺ℎe,ℎe=𝐹(ℎe)注意到𝐹(ℎefg)=𝐹(ℎe)仅当ℎe是𝐺ℎ,ℎe局部昀小值时满足。如果𝐹的导数存在且在ℎe的短区间内连续，这也表明∇𝐹ℎe=0。因此通过Eq.11重复矫正，我们估计得到了下列方程的收敛局部昀小值ℎo3p=argmink𝐹(ℎ)：𝐹ℎo3p≤⋯𝐹ℎefg≤𝐹ℎe…≤𝐹(ℎ1)≤𝐹(ℎg)≤𝐹(ℎs)(12)我们接下去证明通过定义适当的辅助函数𝐺ℎ,ℎe对|𝑉−𝑊𝐻|和𝐷𝑉,𝑊𝐻,矫正规则对定理1和2遵循Eq.11.8图1:昀小化辅助函数𝐺ℎ,ℎe≥𝐹ℎ确保𝐹ℎefg≤𝐹ℎe对于ℎefg=argmink𝐺(ℎ,ℎe)理论2如果K(ℎe)是对角矩阵：𝐾Tvℎe=𝛿Tv(𝑊X𝑊ℎe)T/ℎTe(13)那么𝐺ℎ,ℎe= 𝐹ℎe+ℎ−ℎeX∇𝐹ℎe+g1ℎ−ℎeX𝐾(ℎe)(ℎ−ℎe)(14)是一个辅助函数对于𝐹ℎ=g1(𝑣3−𝑊3TℎTT)13(15)证明：因为显然𝐺ℎ,ℎ≥𝐹ℎ，我们只需要证明𝐺ℎ,ℎd≥𝐹ℎ，为了证明需要，我们对比 𝐹ℎ= 𝐹ℎe+ℎ−ℎeX∇𝐹ℎe+g1ℎ−ℎeX𝑊X𝑊ℎ−ℎe(16)和Eq.14来得到𝐺ℎ,ℎd≥𝐹ℎ等价于0≤ℎ−ℎeX[𝐾ℎe−𝑊X𝑊]ℎ−ℎe(17)9为了证明正向半定性6，考虑矩阵𝑀Tvℎe=ℎTe(𝐾ℎe−𝑊X𝑊)Tvℎve(18)只是𝐾ℎe−𝑊X𝑊的重新调整。那么𝐾ℎe−𝑊X𝑊具有正向半定性当且仅当M是且符合：𝑣X𝑀𝑣=𝑣T𝑀TvTv𝑣v(19)=ℎTe(𝑊X𝑊)Tvℎve 𝑣T1−Tv𝑣TℎTe(𝑊X𝑊)Tvℎve𝑣v=𝑊X𝑊TvℎTeℎve Tvg1𝑣T1+g1𝑣v1−𝑣T𝑣v=g1𝑊X𝑊TvℎTeℎve Tv(𝑣T−𝑣v)1≥0现在我们可以证明定理1的收敛性：定理1的证明在Eq.11中用Eq.14替换𝐺ℎ,ℎe得到矫正规则：ℎefg=ℎe−𝐾ℎezg∇𝐹(ℎe)(20)因为Eq.14为辅助函数，𝐹在矫正法则下非增，根据引理1，明确写出这个方程的组成部分，我们得到：ℎTefg=ℎTe(]^{)[(]^]k|)[(21)通过替换掉引理1和2中的𝑊和𝐻，𝐹可以被相似地证明在对𝑊矫正规则非增。我们现在考略接下去的辅助方程对于收敛花费方程：引理3定义𝐺ℎ,ℎe=𝑣3𝑙𝑜𝑔𝑣3−𝑣33+𝑊3TℎT−3T 𝑣3][k[|]}k}|}(𝑙𝑜𝑔𝑊3TℎT−𝑙𝑜𝑔][k[|]}k}|})3T(22)6positivesemidefiniteness
10为辅助方程对于 𝐹ℎ=𝑣3log{][k[[−𝑣3+𝑊3TℎTT3(23)证明：𝐺ℎ,ℎ=𝐹(ℎ)显然，为证明𝐺ℎ,ℎe≥𝐹ℎ，我们使用对数函数的凸度来导出不等式 −𝑙𝑜𝑔𝑊3TℎTT≤−𝛼T𝑙𝑜𝑔][k[[T(24)这适用于所有非负的求和基本单位𝛼T。设置𝛼T=][k[|]}k}|}(25)我们得到−𝑙𝑜𝑔𝑊3TℎTT≤−][k[|]}k}|}(𝑙𝑜𝑔𝑊3TℎT−𝑙𝑜𝑔][k[|]}k}|})T(26)对于这个不等式，遵循𝐺ℎ,ℎe≥𝐹ℎ而定理2遵循引理1等应用：定理1的证明𝐺ℎ,ℎe的昀小值需要考虑通过将梯度设置为零来确定h：‚ƒk,k|‚k[=−𝑣3][k[|]}k}|}gk[+3𝑊3T3=0(27)因此Eq.11矫正规则采取以下形式ℎTefg=k[|]„}}{]}k}|}𝑊3T3(28)因为𝐺是辅助函数对于𝐹在Eq.23非增，以矩阵形式重写，这等同于Eq.5中的矫正规则。通过反转H和W的作用，W的矫正规则可以类似地证明为非增。11七．讨论我们已经证明，应用矫正规则在Eq.4和Eq.5保证至少可以分别找到问题1和2的局部昀优解。收敛证据依赖于定义适当的辅助函数。我们正在努力将这些定理推广到更复杂的约束条件下。矫正规则本身非常容易在计