动机
非负矩阵分解以加法成分重构非负量度。写出目标函数还不够:学生也要知道如何找到因子、更新为何合理,以及停止条件究竟证明了什么。可行域有边界,所以不能只令普通梯度为零,就宣称涵盖所有最优点。
乘法更新很吸引人,因为正系数会保持非负,公式亦没有明显的学习率。但其下降性来自特定上界,不是把梯度拆成两部分再相除便一定安全。本节完整推导这个上界,指出非负数据、正的目前系数及非零分母各自的角色。
另一条路是交替非负最小二乘。固定一个因子后,子问题是凸的,虽然联合问题并不凸。它可以启动一个错误地停在零的系数,也能用受限一阶条件检查停止状态。两种方法都不会自动决定成分数、唯一解释或全局最优。
定义
定义 6.1.1
(欧氏(Euclid) NMF 与分块二次式)
给定 及内维度 ,寻找 、,最小化
固定 及一列 ,记 、、,梯度为 。非负分块最优点满足 、,且每个 。
这些是正交象限限制下的 KKT 条件。对凸二次子问题,它们亦充分。正系数可向两边扰动,所以梯度必须为零;零系数不能下降,故容许正梯度。若零位置梯度为负,向上移动便能改善,不能视为最优。
概念视角几何
非负最小二乘即向锥体投影
集合 是由 各列生成的凸锥。这个分块问题要求的,是 在其上的欧氏(Euclidean)投影 。KKT 条件在几何上说的是同一件事:残差 与 的每一列的内积都不为正,而且与系数为正的每一列正交。
定义 6.1.2
(贴合于目前点的辅助上界)
若可行 皆满足 ,而 ,称 为辅助函数。固定 最小化它,便有
此处要最小化损失,所以用上界;EM 要最大化对数似然,所以用下界。共同逻辑是在目前点贴合。每个分块内的更新皆使用同一个旧向量;若逐项更改并把部分新值塞进同一比值,就是另一种算法,需要另作坐标下降论证。
定理/命题
定理 6.1.3
(有效的乘法分块更新)
若 没有全零列,且 ,则 逐项非负,。设
便有 与 。若每个 ,新向量仍严格为正。因此当 严格为正,而非负 没有全零行或列时,可持续交替执行正的乘法更新。
矩阵形式为
其中比值与 都逐项进行,其他相乘才是矩阵乘法。第二步用新 及旧 ;两个分块各自降低同一目标。若两因子同时由旧比值更新,以下交替下降证明并不适用。
定理 6.1.4
(NNLS 最优性与投影下降)
固定 ,上述 KKT 条件刻画 上的全局最小点。令 ,投影梯度步
满足 。最大值逐项取。若 ,分块目标为常数,不需要此步。
这提供完整的非负最小二乘内迭代。可以做到 KKT 残差足够小,再固定 求 的各行;也可以每次只作有限个已有下降证明的步骤。两者都不同于把无限制最小二乘答案的负数直接剪去。
证明思路或证明
证明
(对角二次上界的完整证明)
二次函数在 的展开是精确的:
设 ,把最后的 换成 定义 。任意 都有
展开平方并用 对称即可核对恒等式。非负性依赖 的逐项符号;仅知道它半正定,不足以保证此平方和各系数非负。又因 每列非零,,配合 ,得 。
严格凸的对角上界最小点为 ,逐项就是 。因 ,它本身可行,故辅助函数不等式链证明下降。对每个数据列套用,得 更新;把分解转置,交换两因子的角色,便得 更新。正因子配合数据无全零行列,确保每步分子仍为正。
证明透视
目标值收敛不等于因子收敛
损失不增且下界为零,所以损失数列有极限。但这个下降论证不能控制因子大小:把 某列乘 ,再把 相应行除以 ,重构完全不变。零系数也可能锁定在不满足 KKT 的位置。要说参数收敛至驻点或局部最小,还需要额外分析,不能由上界不等式直接跳到结论。
证明
(受限最优条件与投影步)
必要性可由逐坐标扰动得到:正位置可双向,零位置只能向上。若 满足 KKT,对任意可行 ,
首项因互补性等于 ,故条件充分。
投影步最小化 。其变分不等式取可行比较点 ,给 。另一方面 ,精确二次展开把损失增加量界于 之上。合并即得下降式。固定投影步亦恰好等价于 KKT,包括边界位置。
实现交替 NNLS 时,先初始化非负因子,对 各列作上述投影迭代,再对 各行作相同处理。报告应列目标值、因子尺度惯例、迭代数及 KKT 残差,例如 的范数。损失只在小数几位不变,是较弱停止信号,尤其系数接近边界或尺度不平衡时。若用 的可靠上界取代它,亦可沿同一论证选安全步长。
全零数据不必靠小常数掩饰。 的某列全零时,任意固定非负字典下,系数列取零就是精确最优答案。可先移除它,再作严格正的乘法迭代,最后还原零系数列。全零量度行也能由字典的一个零行精确重构。这种前处理清楚说明正值定理的适用范围,却不容许在任意因子位置随意放零;后者可能锁住本来有用的成分。字典某列全零时,它对乘积毫无贡献,要变成有用成分便须明确重新初始化或移除。
尺度亦影响停止残差的解读。两组因子乘积相同,系数量级却可差很远,因此没有尺度惯例的绝对梯度容差可能误导。比较实验时,可以把非零字典列单位化,反向缩放系数行,再相对指定数据尺度报容差。这是解读原则,不是新增收敛定理。不同初始化仍可得到不同乘积;只比较迭代次数,忽略最终重构质量与每次子问题的工作量,也不能判定哪个算法更好。选定内维度后,应一起报这些量,再谈表示质量。
例题详解
例题 6.1.5
(一步达到精确分块答案)
取 、、。则 、,乘法比值为二及三,新系数恰为 。损失由 降至零。这里二次式本来可分离,上界等于原函数;一般非正交字典会耦合系数,不能期待一步完成。
例题 6.1.6
(耦合字典中的一次下降)
令 、、。得 、、,所以 。重构为 ,残差 ,新损失 ,旧损失一。精确 NNLS 答案其实是 、损失零;下降虽明显,仍未解完。
例题 6.1.7
(投影步可以启动零系数)
仍用上例 ,从 开始。梯度为 , 最大特征值是 。一次投影步使首系数成为 ,次系数仍为 。负梯度正确指出向上可改善;乘法更新则只要比值有限,就无法把原先的零变成正数。
常见错误
反例模式
零锁定固定点未必满足最优条件
上例在 的分母为 ,皆正。乘法一步仍得到自身:零乘 是零,第二比值是一。但梯度 违反 KKT。损失为 ,而 可得零。因此“每个非负乘法固定点都是驻点”没有一般成立。严格正值的迭代假设具有实质内容,不能删掉后仍引用原证明。
常见错误
(剪去负系数会改变其他系数的最佳值)
字典耦合时,剪去负最小二乘系数后,保留下来的系数也可能要重新调整。任意在每个分母加小常数,同样改变更新式;若没有新证明,原上界恒等式不再直接适用。零数据行列应明确处理,或使用可处理边界的 NNLS。数值措施需要说明其数学意义。
思想史
辅助函数的求解路线
Lee 与 Seung 的 NIPS 2000 原论文 以辅助函数处理欧氏及散度乘法算法。本节在明确条件下证明欧氏下降,并区分目标值极限与因子数列的较强收敛结论。散度版本需要另一个上界,本节没有证明。
总结
乘法比值最小化特定的对角二次上界,其正确性依赖符号、正系数及非零分母。交替 NNLS 解凸的受限分块,能让零系数重新启动。两者都需要明确停止测度;重构误差下降不等于唯一因子、全局最佳分解,亦不会替内维度提供统计理据。
练习
快速检查
(把新系数向量乘以 ,核对第二个例题,并精确算出新旧目标值。)
第一坐标保留十五分母。
解答 · 答案
。减去 得 ,范数平方 ,乘二分之一为 。旧重构 的残差为 ,故损失一,与下降证明一致。
快速检查
(证明在耦合例中 满足 KKT。为什么这能证明分块最优,却不能推出联合 NMF 的全局结论?)
先固定 W,计算重构与梯度。
解答 · 答案
,梯度为零,系数正且互补性成立,故是固定 的全局最小点。本例恰因零损失也达联合问题下界,所以也是联合全局解;一般正损失的分块最优,不能排除换一个 更好。交替分块最优没有自动的联合全局保证。
快速检查
(设 的列为 与 ,目标为 。求无约束最小二乘系数、剪去负数后的结果,并与真正的 NNLS 解比较。)
第一系数为零后,要再优化第二系数。
解答 · 答案
无限制精确解是 。剪后为 ,重构 ,损失 。在首系数零的边界,最小化 得 、损失 。此时残差 ,梯度 ,满足 KKT,故确为 NNLS 解。
快速检查
(为什么把 每个非零列单位化并相应缩放 的对应行,重构不变?这能证明唯一性或全局最优吗?)
在因子中间插入正对角矩阵及其逆。
解答 · 答案
对正对角 ,有 ,非负性亦保留。取 可把非零列单位化;零列不能除其范数,须另定惯例。这只移除一种尺度歧义,仍可有排列及其他分解歧义。损失没有改变,也没有提供全局最优证明。