動機
非負矩陣分解以加法成分重構非負量度。寫出目標函數還不夠:學生也要知道如何找到因子、更新為何合理,以及停止條件究竟證明了甚麼。可行域有邊界,所以不能只令普通梯度為零,就宣稱涵蓋所有最優點。
乘法更新很吸引人,因為正係數會保持非負,公式亦沒有明顯的學習率。但其下降性來自特定上界,不是把梯度拆成兩部分再相除便一定安全。本節完整推導這個上界,指出非負數據、正的目前係數及非零分母各自的角色。
另一條路是交替非負最小二乘。固定一個因子後,子問題是凸的,雖然聯合問題並不凸。它可以啟動一個錯誤地停在零的係數,也能用受限一階條件檢查停止狀態。兩種方法都不會自動決定成分數、唯一解釋或全域最優。
定義
定義 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 解。
快速檢查
(將 每個非零列單位化並相應縮放 的行,為何重構不變?這證明唯一性或全域最優嗎?)
在因子中間插入正對角矩陣及其逆。
解答 · 答案
對正對角 ,有 ,非負性亦保留。取 可把非零列單位化;零列不能除其範數,須另定慣例。這只移除一種尺度歧義,仍可有排列及其他分解歧義。損失沒有改變,也沒有提供全域最優證明。