[推薦演算法] 協同過濾NMF演算法--原理與應用

04-04

原理

發現寫關於非負矩陣的博文還是蠻多的，還是以自己的角度總結一下自己的最近看的若干東西以及對非負矩陣分解有用的一些資料鏈接。NMF，全稱為non-negative matrix factorization，中文為「非負矩陣分解」。

NMF的思想：V=WH（W權重矩陣、H特徵矩陣、V原矩陣），通過計算從原矩陣提取權重和特徵兩個不同的矩陣出來。屬於一個無監督學習的演算法，其中限制條件就是W和H中的所有元素都要大於0。

寫得有點匱竭難懂，看不懂建議去看看原論文，在《NMF引用》一文中有，下面是對於NMF符號偶的定義。

$V_{(F?N)}=W_{(F?K)}?H_{(K?N)}$

V : F?N 的矩陣

- F 為特徵（行）

- N 可以為觀察值、例子、特徵向量（列）

$v_n=(v_{1n},v_{2n},...,v_{fn})x^{T}$ ,在集合N中第N個特徵向量

W:F?K 的字典矩陣

- $w_f$ 為W中的一個係數

- $w_k$ 是K個元素的基向量

H:K?N 擴展矩陣

- $h_n$ 列向量 the columsn vector of activation coeffcients for observation vn

- $h_k$ 行向量 the row cector of activation coefficients relating to basis vector wk

好奇的就是為什麼分解的矩陣式非負的呢，網上流傳一種很有利的解釋就是非負為了使數據有效，負數對於數據是無效的。這種方法我個人認為有道理，但論文作者實際的解釋是：

非負性會引發稀疏
非負性會使計算過程進入部分分解

回顧一下NMF的歷史，其實距離現在已經有35年歷史啦！在計算還沒有普及的年代NMF已經被發明了。

nonnegative rank fatorisation非負排名因子分解 (Jeter and Pye, 1981; Chen, 1984)裡面有個華人哦
positive matrix fatorisation 正矩陣因子分解(Paatero and Tapper, 1994)
直到1990年大神Lee(libSVM的作者)和 Seung 發了篇申神論文「learning the parts of objects」，NMF就名聲大噪，從那開始劃時代的變化就來臨啦，NMF被廣泛引用到各種領域當中。

當然，講到這裡NMF好像很簡單，只是對矩陣進行分解。不過仔細想想如果只是簡單對矩陣進行分解早就被人提出來引用了，正是因為如何分解矩陣才能更好地對矩陣進行可解析性，也就是如何解NMF矩陣本身就是一個難題。另外還有下面一些問題值得我們一起去探討的：

K選擇困難症

很多人（其實是我啦）發現對於K的選擇無棱兩可，但是對於一個適當的K選擇在於分解的時候又好重要，其中不同的K對於不同模型情況如下：

數據擬合：K越大那麼對於數據擬合更好
模型複雜性：一個更小的K模型更簡單（易於預測、少輸入參數等）

因此一個正確的K選擇就像我前一篇文章《NMF實站》裡面所說的應該根據數據矩陣V和實際業務去分析，沒有一個標準的答案。下面為聲頻處理時候不同K的表現。

解不唯一

對於V=WH;W>=0,H>=0，那麼任意一個矩陣Q有 $WQ>=0，Q^{?1}H>=0$

這就提供了一個可以替換的因子 $V=WH=(WQ)(Q^{?1}H)$ ，特殊情況下，Q可以為任意非負廣義置換矩陣。雖然解不唯一，但是也不用太擔心，一般情況下解不唯一僅僅是基向量Wk的縮放和轉置，意思就是換來換去還是它自己本身。

幾何意義

NMF假設數據是由W所產生的一個凸角 $C_w$ ，對於 $C_w$ 來說就很鬱悶啦，因為可以有很多個不用的 $w_i$ 來決定，因此很難確定到底是哪個 $C_w$ 。那，怎麼解決這個問題呢，學數學的人（我不是哈）就知道應該引入約束式來限制 $w_i$ 的選擇。對於怎麼選擇約束，業界已經出現了很多種方法：

稀疏約束：(e.g., Hoyer, 2004; Eggert and Korner, 2004);
形狀約束
對hk的空間或時間約束 : activations are smooth (Virtanen, 2007; Jia and Qian, 2009; Essid and Fevotte, 2013)
跨模態對應約束(Seichepine et al., 2013; Liu et al., 2013; Yilmaz etal., 2011)
幾何約束: 例如，選擇特殊的角點Cw(Klingenberg et al.,
2009; Essid, 2012)

2.應用概述

對比了一圈，NMF可以應用的領域很廣，源於其對事物的局部特性有很好的解釋。在眾多應用中，NMF能被用於發現資料庫中的圖像特徵，便於快速自動識別應用；能夠發現文檔的語義相關度，用於信息自動索引和提取；能夠在DNA陣列分析中識別基因等等。我們將對此作一些大致的描述。但是最有效的就是圖像處理領域，是圖像處理的數據降維和特徵提取的一種有效方法。

2.1 特徵學習

這一點思想類似（Principal Component Analysis）主成分分析，但是在實際工程環境當中都要比PCA效果要好，其中思想如下：

測試數據在NMF演算法上學習 $V_{train}→dictionaryW$
利用W去分解新的測試 $examples V_n$ : $v_n≈∑_{n=1}^{K}h_{kn}w_k，其中k_n>=0$

把 $h_n$ 作為example n的特徵向量

下面是對人物臉部特徵學習的NMF演算法，圖為把人的臉部的不同特徵顯示出來：

2.2 圖像分析

NMF最成功的一類應用是在圖像的分析和處理領域。圖像本身包含大量的數據，計算機一般將圖像的信息按照矩陣的形式進行存放，針對圖像的識別、分析和處理也是在矩陣的基礎上進行的。這些特點使得NMF方法能很好地與圖像分析處理相結合。人們已經利用NMF演算法，對衛星發回的圖像進行處理，以自動辨別太空中的垃圾碎片；使用NMF演算法對天文望遠鏡拍攝到的圖像進行分析，有助於天文學家識別星體；美國還嘗試在機場安裝由NMF演算法驅動的識別系統，根據事先輸入計算機的恐怖分子的特徵圖像庫來自動識別進出機場的可疑恐怖分子。

學術界中：（1）NMF首次被Lee教授用於處理人臉識別。（2）LNMF被宋教授後面提出用於提取人臉子空間，將人臉圖像在特徵空間上進行投影，得到投影係數作為人臉識別的特徵向量，用來進行人臉識別。一定程度上提高了識別率。（3）GNMF被楊教授提出，該演算法是基於gamma分布的NMF進行構建特徵子空間，採用最小距離分類對ORL人臉庫部分圖像進行識別。

對於人臉識別，其中以LNMF最為有效突出，比普通的NMF高效且精度高。

2.3 話題識別

文本在人類日常接觸的信息中佔有很大分量，為了更快更精確地從大量的文本數據中取得所需要的信息，針對文本信息處理的研究一直沒有停止過。文本數據不光信息量大，而且一般是無結構的。此外，典型的文本數據通常以矩陣的形式被計算機處理，此時的數據矩陣具有高維稀疏的特徵，因此，對大規模文本信息進行處理分析的另一個障礙便是如何削減原始數據的維數。NMF演算法正是解決這方面難題的一種新手段。NMF在挖掘用戶所需數據和進行文本聚類研究中都有著成功的應用例子。由於NMF演算法在處理文本數據方面的高效性，著名的商業資料庫軟體Oracle在其第10版中專門利用NMF演算法來進行文本特徵的提取和分類。為什麼NMF對於文本信息提取得很好呢？原因在於智能文本處理的核心問題是以一種能捕獲語義或相關信息的方式來表示文本，但是傳統的常用分析方法僅僅是對詞進行統計，而不考慮其他的信息。而NMF不同，它往往能達到表示信息的局部之間相關關係的效果，從而獲得更好的處理結果。

話題識別的話跟Probabilistic Latent Semantic Analysis概率隱語義分析相似。

首先假設V=[vfn]是一個單詞-文件的矩陣，vfn是單詞mf在文件dn的出現頻率；
假設wfk=P(tk)P(mf|tk)和hkn=P(dn|tk)；
那麼模型可以變成：[P(mf,dn)]=[vfn]=WH

在這裡，wk 可以被解釋成為與數據hk的主題相關度

2.4 語音處理

語音的自動識別一直是計算機科學家努力的方向，也是未來智能應用實現的基礎技術。語音同樣包含大量的數據信息，識別語音的過程也是對這些信息處理的過程。NMF演算法在這方面也為我們提供了一種新方法，在已有的應用中，NMF演算法成功實現了有效的語音特徵提取，並且由於NMF演算法的快速性，對實現機器的實時語音識別有著促進意義。也有使用NMF方法進行音樂分析的應用。復調音樂的識別是個很困難的問題，三菱研究所和MIT(麻省理工學院)的科學家合作，利用NMF從演奏中的復調音樂中識別出各個調子，並將它們分別記錄下來。實驗結果表明，這種採用NMF演算法的方法不光簡單，而且無須基於知識庫。

NMF處理聲頻產生局部特徵數據

2.5 時序分割（temporal segmentation）

這裡的話思想可以引用隱馬爾科夫模型hidden markov models HMM，可以處理時間序列的數據，例如音頻視頻：

同樣基於時序分割的想法下有了這樣一個語音處理項目，對很多人說的一段話進行語音特徵分割，識別出每段話屬於哪個人說的：

2.6 聚類

聚類最常用的方法是K-means，俗稱K均值演算法，NMF演算法比K-means演算法更優之處因為它是一種軟聚類方法（也就是一個元素可以被分為多種類型，不是K-means那種非彼則此），對於有可能重複的聚類方法NMF是簡單高效哦。

半年前做姓名聚類的時候一個老外的名字叫 Handsome Yokota, 有時候又寫成Hand. Yokota，當大量這種情況出現對於聚類是很不和諧的，用軟聚類可以有效過濾這種情況，降低後續數據處理壓力。

2.7 機器人控制

如何快速準確地讓機器人識別周圍的物體對於機器人研究具有重要的意義，因為這是機器人能迅速作出相應反應和動作的基礎。機器人通過感測器獲得周圍環境的圖像信息，這些圖像信息也是以矩陣的形式存儲的。已經有研究人員採用NMF演算法實現了機器人對周圍對象的快速識別，根據現有的研究資料顯示，識別的準確率達到了80%以上。

2.8 生物醫學工程和化學工程

生物醫學和化學研究中，也常常需要藉助計算機來分析處理試驗的數據，往往一些煩雜的數據會耗費研究人員的過多精力。NMF演算法也為這些數據的處理提供了一種新的高效快速的途徑。科學家將NMF方法用於處理核醫學中的電子發射過程的動態連續圖像，有效地從這些動態圖像中提取所需要的特徵。NMF還可以應用到遺傳學和藥物發現中。因為NMF的分解不出現負值，因此採用NMF分析基因DNA的分子序列可使分析結果更加可靠。同樣，用NMF來選擇藥物成分還可以獲得最有效的且負作用最小的新藥物。

2.9 濾波和源分離

參考 Independent Component Analysis, ICA 獨立成分分析

-----------------------萬能的分割線--------------------------

原創文章寫得俺手軟，兄弟姐妹將就著看一下，寫得不好一定要噴。畢竟是花了心血的東西，同樣歡迎轉載，轉載前註明作者（陳仲銘），zomi 在此謝謝。