正定矩陣低秩分解的交替二次規劃算法

馬婷婷

(遼寧師范大學，遼寧　大連　116000)

在模式識別和機器學習的學習[1-3]中，數據的內在特征結構可以通過矩陣分解得以發現，并且使得數據特征維數很大程度的降了.Lee等[4]發表了非負矩陣分解(non-negativematrixfactorization,NMF)算法，它將一個正定矩陣分解為兩個正定矩陣乘積，由于分解后的矩陣是正定的所以只包含非負元素，原矩陣中列向量可稱為所有列向量的加權和，矩陣中對應列向量中的元素稱為權重系數.因為其分解的結果中都是正數和零即不會有負值出現所以具有非常簡便的算法，具有廣泛的物理意義，所以可以運用于語音辨識、圖像識別、腦電信號提取等等各種問題中[3-6].這篇文章就是將正定矩陣分解算法模型轉化為凸二次規劃模型求解，從而使處理速度得到了很大的提高。

一、正定矩陣分解的概念與計算

對于m×n階的實正定矩陣A和正整數k

A≈WH(1)

下面就是歐式距離優化模型：

正定矩陣秩分解有很多種的方法[6-11]，一般可以分為兩種.第一個是優化逼近法.對于模型(2)可以直接采用優化方法求解，可以選擇廣義既約梯度法、廣義乘子法、梯度投影法等的局部最優化方法[11-16].這些方法的優點是算法都比較成熟，收斂性也已經得到證明；但缺點是不能保證全局最優解.也就是說可選擇區間方法、微分進化算法、隨機投點與隨機方向算法等這些全局最優化方法求解[15-16].這類方法的缺點是計算量遠大于一般的局部最優化方法。

第二個是公式逼近法，根據式(1)，構造出來某種迭代公式，通過同時迭代或交替迭代的方式，將Hk與Wk更新到Hk+1與Wk+1，并希望當k→+∞時，WkHk→A.這種方法優點是，具有很簡單的迭代公式，公式中的運算一般簡單非常基本的運算等，實現起來非常容易；但是其缺點是收斂性很難得到證明，并且收斂速度比較慢。

二、正定矩陣低秩分解的交替二次規劃算法

在對模型(2)采用局部優化計算時，這里f(x)是一個四次代數多元(p=m×k+k×n個變元)多項式函數，因為其高度復雜的極值點，運用模型(2)這種傳統優化算法是很不容易得出結果來的.那么對于這種模型，如果我們令W=W1也就是讓W選定為某個常數陣W1，那么有

這是一個關于H的二次規劃模型.

具體計算步驟為

步驟1令基矩陣W的初始值為W=Wk(k=1)，求Hk(k=1)，其中試探性地取參數λ值，然后限制對Hk取值為非負，記下Wk與H”k(k=1)中零元素的個數；

步驟2令H=HK，求Wk+1，得到Wk+1后再一次限制非負的，注意試探性的取值參數μ，使得NWk+1z≥NW”kz，然后再計算總誤差E2k(k=1)；

步驟3檢查是否滿足迭代終止條件：若E2k-1≥E2k(k=1)與NW2x≥NW1x同時成立，則令k+1→k繼續步驟1，否則停止，那么最優分解就是上一輪的結果.

注：①.初始基陣W1(k=1)的選取方法：只需W1中，盡可能多的零元素存在。無論W1取何值，交替二次規劃算法迭代的收斂性都不會受到影響，但如果想要減少迭代次數，那么W1選取得好是至關重要的。

②.參數λ與μ選取方法：滿足以下兩個條件即可：

(1)從Hk到Hk+1中零元素的個數NHkz到NWk+1z滿足NHkz≤NHk+1z；

(2)計算出的前后兩次總誤差值E2k-1到E2k滿足E2k-1≥E2k≥E2k+1。

Hk與Wk中元素非負性要求的實現：當模型取(2)這種一般的約束非線性規化時，則模型(2)可行域的邊界為H≥0,W≥0。為了上述方法中這些問題出現，這篇文章在交替二次規劃迭代計算過程中用零元素代替Hk與Wk中出現的負元素，從而減小了難度。

三、交替二次規劃算法的收斂性

由于交替二次規劃所產生的總誤差值列單調遞減并且有下界的數列{Ep}(p=1,2,3,…)一定有極限即：E1≥E2≥E3≥…≥Ep≥0,所以算法是收斂的，但是事實上很少算法在有限步終止，我們可以根據WH逼近A的精度E值的要求不同，每一步的結果，都可以作為需要分解的結果。

四、結語

因為有很多種正定矩陣低秩分解的方法，所以針對同一個問題可以用這些不同的方法，那么又怎樣來評定它們的優點和缺點呢？這篇文章的作者認為這就需要存在某些的評定標準，而這個評定標準中主要當然包含三個方面其一為總誤差E=Ea+Eb的大小，總誤差值當然是越小越好；其二為基矩陣W中列向量W1,W2,W3,…,線性獨立的Wi×Wj≈0(i≠j)程度，這種程度是用內積來描述的，當然是越接近0越好；其三為基矩陣W與系數矩陣H稀疏的程度.

交替二次規劃算法的提出，這篇文章的優點在于作者注意到了直接求解是非常困難并且非常復雜。所以作者在學習以前別人的基礎上，并且滿足評定標準中要求，經過長時間刻苦學習與專研給出了解決這樣問題的方法。我們通過了大量實際例子都可以了解到，這個方法與上面的要求大致上可以很好的完成。不僅僅算法非常明確，實現起來也很方便，并且由于簡單的迭代過程，使得有很小的計算量，這一點對特別是大型數據模型來說是至關重要的，也很容易證明算法的收斂性。

缺點是對Hk與Wk中的元素非負性要求，在迭代過程中如果出現了負元素直接用零元素取代的方案，但是對于普遍性的問題，是否存在特別情況不適用，目前還不是很不清楚，有待進一步的研究。

參考文獻：

[1]GAO Yuan CHURCHG G.Improving molecular cancer class discovery through sparse non-negative matrix factorization[J].Bioinformatics，2005，21(21)：3970-3975.

[2]Hoyer P O.Non-negative matrix factization with sparseness constraints[J].TheJournal of Machine Learning Reseaarch，2004，5：1457-1469.

[3]“10000個科學難題”數學編委會.10000個科學難題數學卷[M].北京：科學出版社，2009.

[4]LeeD D，SeungH S.Learingthepartsofobjectsbynon-negativematrixfactorization[J].Nature，1999，401(6755)：788-791.

[5]Lee D D，Seung H S.Algorithms for Non-negative matrix factorization[C]// A dvances in Neural Information Processing Systems.Cambridge：MIT Press，2001.

[6]蔣嬌嬌.非負矩陣分解算法的改進及應用[D].北京：北京工業大學，2001.

[7]楊洪禮.非負矩陣與張量分解及其應用[D].青島：山東科技大學，2011.

[8]張宇飛.加稀疏約束的非負矩陣分解[D].大連：大連理工大學，2010.

[9]趙燕斌.強噪聲中誘發電位信號的快速提取研究[D].大連：大連理工大學，2008.

[10]郭立.增量式非負矩陣分解方法研究[D].上海：復旦大學，2009.

[11]殷海青.圖象分析中的非負矩陣分解理論及其最優化和正則化方法研究[D].西安：西安電子科技大學，2011.

[12]王德人.非線性方程組解法與最優化方法[M].北京：人民教育出版社，1979.

[13]施吉林，張宏偉，金光日.計算機科學計算[M].北京：高等教育出版社，2005.

[14]席少霖，趙鳳治.最優化計算方法[M].上海：上海科學技術出版社，1983.

[15]張可村，李換琴.工程優化方法及其應用[M].西安：西安交通大學出版社，2007.

[16]陽明盛，羅長童.最優化原理、方法及求解軟件[M].北京：科學出版社，2006.