【文章內(nèi)容簡介】 NMF 算法 9 第二章 NMF算法 本章通過講述幾個 BNMF 算法來為下一章的鋪墊，通過這些算法可以對 NMF有更好的理解，其中的 LS 算法為非負矩陣分解的先驅(qū)算法， ALS 算法是現(xiàn)存許多算法的框架， Lin 的投影梯度法是一個經(jīng)典的算法， BBNMF 算法是高效的非負矩陣分解算法。 LS基礎(chǔ) NMF算法 這個 非負矩陣分解 算法的標準是由 Lee和 Seung提出的，是目前解決非負矩陣分解實際問題最受歡迎的算法。 Lee和 Seung選擇固定因素之一， W 或 H ，然后通過迭代公式對另一個因素進行縮小， H 或 W 。細節(jié)的證明被在文獻 [2]中提供。此非負矩陣分解算法開始于對非負矩陣 W ,H 的初始化，而后應(yīng)用了每一步的更新規(guī)則，并進行循環(huán)。細節(jié)描述也在文獻 [2]中，能夠清楚的看到迭代過程以及維持了W ,H 的非負屬性。具體細節(jié)如下： 乘積更新規(guī)則（ LS算法） 1：初始化 jbaiHW bjia ,0,0 11 ??? 2：循環(huán) k=1,2， ………… aiHHW HVWW iaTkkk iaTkkiakia ,))(( ))((1 ??? （ 21） jbHWW VWHH bjkkTk bjTkkbjkbj ,))(())((1111 ?????? （ 22） Lee和 Seung證明了函數(shù)的值是非增的在每次迭代 之后： ),(),( 1 kkkk HWfHWf ?? 以及 ),(),( 111 kkkk HWfHWf ??? ? （ 23） 因為此算法是第一個被大家知曉的算法，與其他算法相比較，它是許多 NMF擴展算法的基礎(chǔ)。這個基礎(chǔ) NMF算法的數(shù)值實驗展現(xiàn)了這個算法收斂很慢，而且不穩(wěn)定。 Lee和 Seung聲明迭代序列 ??1},{ kkk HW 極限是一個穩(wěn)定點 (在 KKT條件下的一個點）。然而， Gonzales和 Zhang指出這個聲明是錯誤的，此方法是一個定點型算法，如果 0))( ?iaTkkk HHW 并且 01 ??? kiakia WW ，而后 iaTkkkiaTk HHWHV ))(())(( ? 推出 0),( ?? iakkW HWf 10 非負矩陣分解的算法及其應(yīng)用研究 故其只是滿足 KKT條件的一部分，因此乘積更新算法依舊缺乏最優(yōu)屬性。 要使此算法有定義，必須保證（ 21）和（ 22）為正，此外如果在 k步迭代之后 0?kiaW ，那么在剩下的每一步迭代中都將有 0?kiaW ，因此必須保證在任意 k情況下， 0?kiaW 和 0?bjH ，當(dāng)這些條件被滿足時，現(xiàn)在考慮計算的復(fù)雜度，在式（ 21）和（ 22）中， TkHV )( 和 VW Tk )( 1? 的計算復(fù)雜度都為 ()Onmr 。 可以計算（ 21）（ 22）的分母通過 THWH)( 或者 )( THHW (24) 前一個計 算也是 ()Onmr ，后一個復(fù)雜度是 2(max( , ) )O m n r 。由于 rmin(m,n)，故后一個更好。同樣的對于（ 24），要使用 HWWT )( 。這個討論指出了不論在任何 NMF代碼中時間復(fù)雜度小于 ()Onmr 計算的重要性。 總結(jié)：算法 1所有的成本為 迭代次數(shù) * )(nmrO 另注：本文中，所有時間復(fù)雜度分析假定 V ,W 與 H 為稠密矩陣。 ALS交替最小二乘 LS算法得出，雖然非負矩陣分解的問題函數(shù) ( , )f WH 對變量 W ,H 都是凸函數(shù)，但對于 ( , )WH 總體并不是凸函數(shù)。所以，當(dāng)確定 W 或 H ，我們可以采用最小二乘法（ LSM） ,來解決 H 和 W 的改變，在每次最小二乘法后，為了避免出現(xiàn)負數(shù)在矩陣 H 與 W 中，所有的負數(shù)將會被用 0替代。可以很容易的看到，這個算法的本質(zhì)是趨于稀疏，結(jié)果會擁有較多的零元素在 W 與 H 矩陣中，這種方法是一種最優(yōu)化問題的 ―塊坐標下降法 ‖，即其中一塊變量在約束條件下最小化，而其余剩余塊固定。 對于非負矩陣分解問題來說，這是最簡單的情況，即塊變量只有兩個即 W和 H。 交替非負最小二乘法： 1：初始化 jbaiHW bjia ,0,0 11 ??? 2：循環(huán) k=1,2， ………… ),(m i na r g01 kWk HWfW ?? ? (25) ),(m i na r g 101 HWfH kHk ??? ? (26) 現(xiàn)在我們考慮（ 25）和（ 26）作為 ALS算法的子問題，當(dāng)一個變量固定后， 第二章 NMF 算法 11 一個子問題可以變?yōu)閿?shù)個最小二乘問題可得出： 1?kH 的每一列 = 210 ||||min hWv kh ?? ? 這里的 v是 V的第 j列并且 h是矢量變量。 Cichocki (2020)[4]建議用投影牛頓法（ Lawson and Hanson,1974)來解決分解后的每一個問題。 現(xiàn)在關(guān)注 ALS算法的收斂性，可能有人認為它會是一個瑣碎的結(jié)果。舉例來說，Paatero(1999)[5]表述了交替非負最小二乘，無論它有多少的塊變量，收斂性都可以得到保證。然而，這個問題獲得了一些關(guān)注。塊坐標下降法的收斂性分析要求子問題有唯一解，但這個屬性在這里并不支持，子問題（ 25）和（ 26）是凸的，但它們并不是嚴格凸的。故這些子問題有數(shù)個最優(yōu)解。舉例來說，當(dāng) kH 是 0矩陣是，任何的 W 都是 (25）的最優(yōu)解。幸運的是當(dāng)有兩個塊變量時， Grippo and Sciandrone證明了這種獨一無二的情況是不需要的。我們有下列的收斂定理： 定理：任何序列 },{ kk HW 由算法而產(chǎn)生的極限點，都是式（ 12）中的穩(wěn)定點。 剩下的問題是是否序列 },{ kk HW 至 少有一個極限點（這里至少有一個收斂結(jié)果）。在最優(yōu)化分析中，這個屬性通常來自可行域的有界性，但我們約束條件下的 W和 H區(qū)域是無界的。在問題（ 12）中可以很容易添加一個所有變量的上界，這個改變?nèi)匀皇且粋€約束問題，由于定理成立 ALS算法可以應(yīng)用，如果在式（ 12）中有上界。相比之下目前尚不清楚如何輕松地修改乘法更新規(guī)則。 清楚的說比起相對簡單的 LS算法，解決子問題（ 25）和（ 26）的每一步迭代花費很大。其次， ALS算法可能較慢，即使它函數(shù)值在每步迭代都會減少。然而用此方法來解決子問題是潛在有效的。在接下來的 ，并討論了它為什么適合用來解決 ALS算法。 概括的說，相對于缺乏收斂結(jié)果的 LS算法， ALS算法有較好的優(yōu)化屬性。 如何正確地執(zhí)行非負在迭代約束仍在討論中。第一個為 NMF設(shè)計的 ALS算法被 Paatero[2]所提出，然后一些 ALS算法的修改在 [5][6]中，這增加了一些限制，我們將以進一步提高 ALS算法的效率為本文的下面討論的重點 ,本文的新算法也是基于ALS算法所產(chǎn)生的。 Lin的投影梯度法 梯度逼近設(shè)想 12 非負矩陣分解的算法及其應(yīng)用研究 Chu曾提出了數(shù)個投影類型逼近的方法，作為本章的子部分，我們簡短的介紹一下步長的選擇，和負梯度方向。在求解最優(yōu)化問題中，最速下降法是簡便的，即沿負梯度方向下降，是函數(shù)最優(yōu)選擇。 ),(11 kkWkk HWfWW ???? ? (27) ),(21 kkHkk HWfHH ???? ? (28) 這里的 k? 為步長，這個方法基本上已經(jīng)就是投影梯度法的主要部分了，只是在上述文獻中并沒有對它進行細致的 討論。 我們可以看出，如果選擇特定的步長， Tkkkkk HHW W )(1 ?? (29) kkkkk HWW W)(2 ?? (210) 可得到 LS算法的迭代公式。 Lin在文獻 [3]中提出了一種改進的投影梯度法，此方法具有很要的優(yōu)化性質(zhì)。 改進的投影梯度法 Lin提出的算法具體如下， 通常我們解決界約束優(yōu)化問題 )(min xfnRx?，定義 l和 u為上下界，假定 k為迭代次數(shù)，通過投影梯度法更新規(guī)則為： )]([1 kkkk xfxPx ???? ? (211) 這里的投影 P為 ??????????iiiiiiiiiiilxluxuuxlxxP ][ 使用 Armijo條件來線搜索，投影梯度法每步使用不同的步長 k? ，通過解決 ALS算法的一個子問題來實現(xiàn)迭代， 1：給定 10 ??? ， 10 ??? ，初始化矩陣變量 x（ W 或 H ）。設(shè)定初始步長為10?? 。 2：循環(huán) k=1,2…… 1??kk ?? 第二章 NMF 算法 13 若步長并滿足 )()()()( 11 kkTkkk xxxfxfxf ???? ?? ? （ 212） ??? /kk? 直至不滿足式（ 212），反之若步長不滿足式（ 212），則 ??? /kk? 直至滿足式（ 212） 3： )]([1 kkkk xfxPx ???? ? (213) 投影梯度法成功的將問題進行了轉(zhuǎn)化，并證明了算法的極限點是穩(wěn)定點，在NMF應(yīng)用求最優(yōu)解中有極大的幫助。 然而 PG算法雖然效果很好，但也有其自身的缺點，第一， 梯度下降也許是最容易實現(xiàn)的技術(shù)，但收斂性慢。其他方法，如共軛梯度法有 更快的收斂速度，至少在局部極小值附近，但比梯度下降更復(fù)雜的實現(xiàn)。基于梯度的方法也有缺點對步長的選擇敏感，這是很不方便的大型應(yīng)用程序 ， Lin的算法解決子問題時采用了梯度法 。 第二， Lin的方法使用單調(diào)線搜索技巧（ 212）來搜索步長，又通過簡單乘除固定小數(shù) ? 來改變步長，步驟繁瑣，這又增加了算法的復(fù)雜性。 BBNMF算法 在介紹解決非負矩陣分解問題的 BBNMF算法之前，我們先討論解決一般最優(yōu)化問題的常用算法 BB算法。 1988年， Barzilia和 Borwein提出了一種兩點步長梯度算法，其基本思想是利用迭代當(dāng)前點和前一點的步長信息來得到下一步的步長因子，步長 k? 滿足 21 ||||m in ?? kkk ys? （ 214) 或者 211 ||1||min ?? ? kkk ys ? (215) 通過上面的（ 214）與（ 215）分別得到步長， ?? ??? ?? ?? 11 11 , kk kkk ss ys? (216) 1111,kkk kksyyy???????? (217) 其中， 11 ?? ?? kkk HHs ， )()( 11 ?? ???? kkk HfHfy ， 1?k ， ,為內(nèi)積，為了提高收斂速度，盡量使步長不要靠近 0。 BB方法每次迭代只需要復(fù)雜度 0（ n）的浮14 非負矩陣分解的算法及其應(yīng)用研究 點運算和梯度評價。同時沒有矩陣計算和線搜索過程中的需要。這樣的 BB方法具有近似的準牛頓性，因此是有利有效的方法。由于 NMF問題可以轉(zhuǎn)化為一個界優(yōu)化問題，它是通常使用一個簡單的有利法 BB的方法。這項工作的目的是將 BB梯度法運用在解決非負矩陣分解的子問題的策略上，盡可能頻繁的接受給定的步長，只需一階信息的存儲過程。 Dai和 Flecther指出交替使用上面的公式效果會更好。 即??????是偶數(shù)如果是奇數(shù)如果k k 21kkk ??? BB算法有著優(yōu)秀的收斂效率，下降速度明顯，遠大于梯度法， ALS算法與 BB算法結(jié)合產(chǎn)生了一種 BBNMF算法， BBNMF算法是一個較新的算法，其基本思想是當(dāng) ALS算法將 NMF原問題分解為兩個子問題后，兩個子問題分別矩陣 W和矩陣 H的凸函數(shù)，那么就可以較容易通過投影的獲得適合子問題的迭代結(jié)果，故 BBNMF算法收斂速率很快，迭代效果好，本章提到 BBNMF算法的目的在于比較 BBNMF算法與本文第三章的改進算法進行比較