非負矩陣分解數(shù)學的奇妙力量

1、計算機是人類解決難題、探索未知以及提供娛樂的絕佳工具。在高效運行著的各種計算機應(yīng)用背后，融匯了人類在物理、電子和數(shù)學等多門學科的高超智慧。嚴密的數(shù)學使得計算機能高效執(zhí)行人類指令，控制內(nèi)部各種數(shù)據(jù)流的走向，因此在現(xiàn)代計算機科學研究中，數(shù)學的基礎(chǔ)地位和重要作用無可替代：它使我們最大程度利用有限的硬件、軟件資源，它使我們能夠在浩瀚的數(shù)據(jù)海洋中快速查到所關(guān)心的信息數(shù)學與計算機科學一起演繹了許多精彩的故事！一、NMF的發(fā)展及原理著名的科學雜志Nature于1999年刊登了兩位科學家D.D.Lee和H.S.Seung對數(shù)學中非負矩陣研究的突出成果。該文提出了一種新的矩陣分解思想非負矩陣分解(Non-neg

2、ative Matrix Factorization，NMF)算法，即NMF是在矩陣中所有元素均為非負數(shù)約束條件之下的矩陣分解方法。該論文的發(fā)表迅速引起了各個領(lǐng)域中的科學研究人員的重視：一方面，科學研究中的很多大規(guī)模數(shù)據(jù)的分析方法需要通過矩陣形式進行有效處理，而NMF思想則為人類處理大規(guī)模數(shù)據(jù)提供了一種新的途徑；另一方面，NMF分解算法相較于傳統(tǒng)的一些算法而言，具有實現(xiàn)上的簡便性、分解形式和分解結(jié)果上的可解釋性，以及占用存儲空間少等諸多優(yōu)點。信息時代使得人類面臨分析或處理各種大規(guī)模數(shù)據(jù)信息的要求，如衛(wèi)星傳回的大量圖像、機器人接受到的實時視頻流、數(shù)據(jù)庫中的大規(guī)模文本、Web上的海量信息等。處理這

3、類信息時，矩陣是人們最常用的數(shù)學表達方式，比如一幅圖像就恰好與一個矩陣對應(yīng)，矩陣中的每個位置存放著圖像中一個像素的空間位置和色彩信息。由于實際問題中這樣的矩陣很龐大，其中存放的信息分布往往不均勻，因此直接處理這樣的矩陣效率低下，這對很多實際問題而言就失去了實用意義。為高效處理這些通過矩陣存放的數(shù)據(jù)，一個關(guān)鍵的必要步驟便是對矩陣進行分解操作。通過矩陣分解，一方面將描述問題的矩陣的維數(shù)進行削減，另一方面也可以對大量的數(shù)據(jù)進行壓縮和概括。在科學文獻中，討論利用矩陣分解來解決實際問題的分析方法很多，如PCA(主成分分析)、ICA(獨立成分分析)、SVD(奇異值分解)、VQ(矢量量化)等。在所有這些方法

4、中，原始的大矩陣V被近似分解為低秩的V=WH形式。這些方法的共同特點是，因子W和H中的元素可為正或負，即使輸入的初始矩陣元素是全正的，傳統(tǒng)的秩削減算法也不能保證原始數(shù)據(jù)的非負性。在數(shù)學上，從計算的觀點看，分解結(jié)果中存在負值是正確的，但負值元素在實際問題中往往是沒有意義的。例如圖像數(shù)據(jù)中不可能有負值的像素點；在文檔統(tǒng)計中，負值也是無法解釋的。因此，探索矩陣的非負分解方法一直是很有意義的研究問題，正是如此，Lee和Seung兩位科學家的NMF方法才得到人們的如此關(guān)注。NMF是一種新的矩陣分解算法，它克服了傳統(tǒng)矩陣分解的很多問題，通過尋找上下文有意義的解決方法，提供解釋數(shù)據(jù)的更深看法。NMF通過尋找

5、低秩，非負分解那些都為非負值的矩陣。這在現(xiàn)實的應(yīng)用中有很多例子，如數(shù)字圖像中的像素一般為非負數(shù)，文本分析中的單詞統(tǒng)計也總是非負數(shù)，股票價格也總是正數(shù)等等。NMF的基本思想可以簡單描述為：對于任意給定的一個非負矩陣A，NMF算法能夠?qū)ふ业揭粋€非負矩陣U和一個非負矩陣V，使得滿足 ，從而將一個非負的矩陣分解為左右兩個非負矩陣的乘積。由于分解前后的矩陣中僅包含非負的元素，因此，原矩陣A中的一列向量可以解釋為對左矩陣U中所有列向量(稱為基向量)的加權(quán)和，而權(quán)重系數(shù)為右矩陣V中對應(yīng)列向量中的元素。這種基于基向量組合的表示形式具有很直觀的語義解釋，它反映了人類思維中“局部構(gòu)成整體”的概念。研究指出，非負矩

6、陣分解是個NP問題，可以劃為優(yōu)化問題用迭代方法交替求解U和V。NMF算法提供了基于簡單迭代的求解U，V的方法，求解方法具有收斂速度快、左右非負矩陣存儲空間小的特點，它能將高維的數(shù)據(jù)矩陣降維處理，適合處理大規(guī)模數(shù)據(jù)。利用NMF進行文本、圖像大規(guī)模數(shù)據(jù)的分析方法，較傳統(tǒng)的處理算法速度更快、更便捷。NMF思想的提出迅速得到了很多人的重視，并有很多將這種思想應(yīng)用到實際中成功解決具體實際問題的例子。通過圖1中的面部特征提取例子可領(lǐng)略NMF處理數(shù)據(jù)的方式。最左邊的大矩陣由一系列的小圖組成，這些小圖是分析數(shù)據(jù)庫中包含的2429個臉部圖像的結(jié)果，每幅圖像由19×19個像素組成。傳統(tǒng)方法中這樣的小圖是

7、一幅完整的人臉圖像，但是在NMF方法中，每個小圖是通過一組基圖像乘以一個權(quán)重矩陣而產(chǎn)生的面部特征圖，經(jīng)過這樣處理的每幅小圖像恰好表示了諸如“鼻子”、“嘴巴”、“眼睛”等人臉局部概念特征，這便大大壓縮了存放的圖像數(shù)據(jù)量。左邊的大矩陣由每幅小圖像的19列一起組成矩陣的一列，那樣它就是19×19=361行，2429列。由于NMF不允許基圖像或中間的權(quán)重矩陣中出現(xiàn)負值，因此只有相加組合得到的正確基圖像才允許，最后通過處理后的重構(gòu)圖像效果是比較滿意的。這個例子中，NMF方法用基圖像來代表眼、眉毛、鼻子、嘴、耳朵、胡子等，它們一起組成了數(shù)據(jù)庫中的臉。這樣給人最先的直覺就是它很好地壓縮了數(shù)據(jù)。事實

8、上Lee和Seung在他們的論文中更深入地指出，與人類識別事物的過程相似，NMF也是一種優(yōu)化的機制，近似于我們的腦分析和存儲人臉數(shù)據(jù)的過程。這個例子中，原圖像表示這些局部特征的加權(quán)組合，這與人類思維中“局部構(gòu)成整體”的概念是相吻合的。因此，NMF算法似乎體現(xiàn)了一種智能行為。                  圖1  NMF提取面部特征的實例事實上，在Lee和Seung發(fā)表他們的研究成果之前，針對非負矩陣的研究早在20

9、世紀70年代已經(jīng)有數(shù)學家做了一些相關(guān)的工作，但是沒有引起過多的關(guān)注。20世紀90年代早期，科學家開始將數(shù)學上非負矩陣的研究成果用于環(huán)境處理和衛(wèi)星遙控的應(yīng)用，但是對于非負矩陣的應(yīng)用意義和價值的理解仍只局限于少數(shù)科學家中，人們還沒有廣泛重視這種方法。直到1999年Lee和Seung的非負矩陣研究成果發(fā)表在Nature雜志之后，這一切才得以改變。盡管同年有另兩位科學家也發(fā)表了與Lee和Seung相近的研究結(jié)果，但由于論文刊登在并非如Nature那樣具有極高聲譽的學術(shù)雜志上，因此其工作并沒有得到如Lee和Seung同樣的關(guān)注，這也從一個側(cè)面折射了高水平學術(shù)雜志對研究工作的推動作用。二、應(yīng)用領(lǐng)域NMF是

10、一個很有效的算法，它力圖在大規(guī)模的矩陣數(shù)據(jù)中發(fā)現(xiàn)具有解釋功能的關(guān)系，相比當前文獻中公布的其他方法來說，使用NMF的算法也是非常精確和快速的。NMF算法思想能為世界上權(quán)威的學術(shù)刊物所接受并非偶然，因為該理論本身蘊涵了巨大的潛能，這種潛在的力量將通過各種具體的應(yīng)用來得以體現(xiàn)。計算機能通過NMF算法更快更好地處理哪些實際問題呢？在眾多應(yīng)用中，NMF能被用于發(fā)現(xiàn)數(shù)據(jù)庫中的圖像特征，便于快速自動識別應(yīng)用；能夠發(fā)現(xiàn)文檔的語義相關(guān)度，用于信息自動索引和提??；能夠在DNA陣列分析中識別基因等等。我們將對此作一些大致的描述。(1) 圖像分析NMF最成功的一類應(yīng)用是在圖像的分析和處理領(lǐng)域。圖像本身包含大

11、量的數(shù)據(jù)，計算機一般將圖像的信息按照矩陣的形式進行存放，針對圖像的識別、分析和處理也是在矩陣的基礎(chǔ)上進行的。這些特點使得NMF方法能很好地與圖像分析處理相結(jié)合。人們已經(jīng)利用NMF算法，對衛(wèi)星發(fā)回的圖像進行處理，以自動辨別太空中的垃圾碎片；使用NMF算法對天文望遠鏡拍攝到的圖像進行分析，有助于天文學家識別星體；美國還嘗試在機場安裝由NMF算法驅(qū)動的識別系統(tǒng)，根據(jù)事先輸入計算機的恐怖分子的特征圖像庫來自動識別進出機場的可疑恐怖分子。(2) 文本聚類/數(shù)據(jù)挖掘文本在人類日常接觸的信息中占有很大分量，為了更快更精確地從大量的文本數(shù)據(jù)中取得所需要的信息，針對文本信息處理的研究一直沒有停止過。文

12、本數(shù)據(jù)不光信息量大，而且一般是無結(jié)構(gòu)的。此外，典型的文本數(shù)據(jù)通常以矩陣的形式被計算機處理，此時的數(shù)據(jù)矩陣具有高維稀疏的特征，因此，對大規(guī)模文本信息進行處理分析的另一個障礙便是如何削減原始數(shù)據(jù)的維數(shù)。NMF算法正是解決這方面難題的一種新手段。NMF在挖掘用戶所需數(shù)據(jù)和進行文本聚類研究中都有著成功的應(yīng)用例子。由于NMF算法在處理文本數(shù)據(jù)方面的高效性，著名的商業(yè)數(shù)據(jù)庫軟件Oracle在其第10版中專門利用NMF算法來進行文本特征的提取和分類。為什么NMF對于文本信息提取得很好呢？原因在于智能文本處理的核心問題是以一種能捕獲語義或相關(guān)信息的方式來表示文本，但是傳統(tǒng)的常用分析方法僅僅是對詞進行統(tǒng)計，而不

13、考慮其他的信息。而NMF不同，它往往能達到表示信息的局部之間相關(guān)關(guān)系的效果，從而獲得更好的處理結(jié)果。(3) 語音處理語音的自動識別一直是計算機科學家努力的方向，也是未來智能應(yīng)用實現(xiàn)的基礎(chǔ)技術(shù)。語音同樣包含大量的數(shù)據(jù)信息，識別語音的過程也是對這些信息處理的過程。NMF算法在這方面也為我們提供了一種新方法，在已有的應(yīng)用中，NMF算法成功實現(xiàn)了有效的語音特征提取，并且由于NMF算法的快速性，對實現(xiàn)機器的實時語音識別有著促進意義。也有使用NMF方法進行音樂分析的應(yīng)用。復(fù)調(diào)音樂的識別是個很困難的問題，三菱研究所和MIT(麻省理工學院)的科學家合作，利用NMF從演奏中的復(fù)調(diào)音樂中識別出各個調(diào)子，

14、并將它們分別記錄下來。實驗結(jié)果表明，這種采用NMF算法的方法不光簡單，而且無須基于知識庫。(4) 機器人控制如何快速準確地讓機器人識別周圍的物體對于機器人研究具有重要的意義，因為這是機器人能迅速作出相應(yīng)反應(yīng)和動作的基礎(chǔ)。機器人通過傳感器獲得周圍環(huán)境的圖像信息，這些圖像信息也是以矩陣的形式存儲的。已經(jīng)有研究人員采用NMF算法實現(xiàn)了機器人對周圍對象的快速識別，根據(jù)現(xiàn)有的研究資料顯示，識別的準確率達到了80%以上。(5) 生物醫(yī)學工程和化學工程生物醫(yī)學和化學研究中，也常常需要借助計算機來分析處理試驗的數(shù)據(jù)，往往一些煩雜的數(shù)據(jù)會耗費研究人員的過多精力。NMF算法也為這些數(shù)據(jù)的處理提供了一種新的高效快速的途徑?？茖W家將NMF方法用于處理核醫(yī)學中的電子發(fā)射過程的動態(tài)連續(xù)圖像，有效地從這些動態(tài)圖像中提取所需要的特征。NMF還可以應(yīng)用到遺傳學和藥物發(fā)現(xiàn)中。因為NMF的分解不出現(xiàn)負值，因此采用NMF分析基因DNA的分子序列可使分析結(jié)果更加可靠。同樣，用NMF來選擇藥物成分還可以獲得最有效的且負作用最小的新藥物。此外，NMF算