机器学习(十二)——机器学习中的矩阵方法(2)特征值和奇异值
http://antkillerfarm.github.io/
QR分解(續)
令A=[a1,?,an],其中ai為列向量。則:
u1u2u3uk=a1,=a2?proju1a2,=a3?proju1a3?proju2a3,?=ak?∑j=1k?1projujak,e1e2e3ek=u1∥u1∥=u2∥u2∥=u3∥u3∥?=uk∥uk∥
即:
a1a2a3ak=?e1,a1?e1=?e1,a2?e1+?e2,a2?e2=?e1,a3?e1+?e2,a3?e2+?e3,a3?e3?=∑j=1k?ej,ak?ej
這個過程又被稱為Gram–Schmidt正交化過程。
因此:
Q=[e1,?,en]andR=????????e1,a1?00??e1,a2??e2,a2?0??e1,a3??e2,a3??e3,a3??………????????
矩陣的特征值和特征向量
設A是一個n階方陣,λ是一個數,如果方程Ax=λx存在非零解向量,則稱λ為A的一個特征值(Eigenvalue),相應的非零解向量x稱為屬于特征值λ的特征向量(eigenvector)。
上面這個描述也可以記作:
(A?λI)x=0(1)
這個公式本身通常用于:已知特征值,求解對應的特征向量。
其中,A?λI被稱為特征矩陣,而∣A?λI∣=0被稱為特征方程。求解特征方程可得到特征值。
特征值和特征向量在有的書上也被稱為本征值和本征向量。
特征值和特征向量的特性包括:
1.特征向量屬于特定的特征值,離開特征值討論特征向量是沒有意義的。不同特征值對應的特征向量不會相等,但特征向量不能由特征值唯一確定。
2.在復數范圍內,n階矩陣A有n個特征值。在這些特征值中,模最大的那個特征值即主特征值(對于實數陣即絕對值最大的特征值),主特征值對應的特征向量稱為主特征向量。
更多內容參見:
http://course.tjau.edu.cn/xianxingdaishu/jiao/5.htm
QR算法
對矩陣A進行QR分解可得:A=QR
因為Q是正交陣(QT=Q?1),所以正交相似變換QTAQ和A有相同的特征值。
證明:
|QTAQ?λI|=|QTAQ?QT(λI)Q|=|QT(A?λI)Q|=|QT|?|A?λI|?|Q|=|QTQ|?|A?λI|=|I|?|A?λI|=|A?λI|
這里的證明,用到了行列式的如下性質:
|I|=1
|AB|=|A|?|B|
因為QTAQ和A的特征方程相同,所以它們的特征值也相同。證畢。
由此產生如下迭代算法:
Repeat until convergence {
1.Ak=QkRk(QR分解)
2.Ak+1=QTkAkQk=Q?1kQkRkQk=RkQk
}
這個算法的收斂性證明比較復雜,這里只給出結論:
limk→∞Ak=???????λ10…0u12λ2…0……?…u1nu2n…λn???????
其中,λi為矩陣的特征值。uij表示任意值,它們的極限可能并不存在。
QR算法于1961年,由John G.F. Francis和Vera Nikolaevna Kublanovskaya發現。
注:John G.F. Francis,1934年生,英國計算機科學家,劍橋大學肄業生。
2000年,QR算法被IEEE計算機學會評為20世紀的top 10算法之一。然而直到那時,計算機界的數學家們竟然都沒有見過Francis本尊,連這位大神是活著還是死了都不知道,仿佛他在發表完這篇驚世之作后就消失了一般。
2007年,學界的兩位大牛:Gene Howard Golub(SVD算法發明人之一,后文會提到。)和Frank Detlev Uhlig(1972年獲加州理工學院博士,Auburn University數學系教授),經過不懈努力和人肉搜索終于聯系上了他。
他一點都不知道自己N年前的研究被引用膜拜了無數次,得知自己的QR算法是二十世紀最NB的十大算法還有點小吃驚。這位神秘大牛竟然連TeX和Matlab都不知道。現在這位大牛73歲了,活到老學到老,還在遠程教育大學Open University里補修當年沒有修到的學位。
2015年,University of Sussex授予他榮譽博士學位。
相關內容參見:
http://www.netlib.org/na-digest-html/07/v07n34.html
Vera Nikolaevna Kublanovskaya,1920~2012,蘇聯數學家,女。終身供職于蘇聯科學院列寧格勒斯塔克羅夫數學研究所。52歲才拿到博士學位。
需要指出的是,QR算法可求出矩陣的所有特征值,如果只求某一個特征值的話,還有其他一些更快的算法。詳見:
https://en.wikipedia.org/wiki/Eigenvalue_algorithm
矩陣的奇異值
在進一步討論之前,我們首先介紹一下矩陣特征值的幾何意義。
首先,矩陣是對線性變換的表示,確定了定義域空間V與目標空間W的兩組基,就可以很自然地得到該線性變換的矩陣表示。
線性空間變換的幾何含義如下圖所示:
圖中的坐標軸,就是線性空間的基。
線性變換主要有三種幾何效果:旋轉、縮放、投影。
其中,旋轉和縮放不改變向量的維數。矩陣特征值運算,實際上就是將向量V旋轉縮放到一個正交基W上。因為V和W等維,所以要求矩陣必須是方陣。
正交化過程,代表旋轉變換,又被稱為等距同構。(旋轉變換,可以理解為向量的正向旋轉,也可以理解為坐標軸的反向旋轉,這里理解為后者,會容易一些。)特征值代表縮放變換的縮放因子。
而對于一般矩陣而言,我們還需要進行投影變換,將n維向量V映射為m維向量W。那么投影變換選擇什么矩陣呢?
我們知道,對于復數z,可寫成:
z=(z|z|)|z|=(z|z|)zˉz??√
其中zˉ是z的共軛復數。也就是說,一個復數可以表示為一個單位向量乘以一個模。
類似的,我們定義共軛矩陣M?ij=Mjiˉˉˉˉˉ,這實際上就是矩陣M轉置之后,再將每個元素值設為它的共軛復數。因此:
M?=(Mˉˉˉˉ)T=MTˉˉˉˉˉˉ
仿照著復數的寫法,矩陣M可以表示為:M=SM?M?????√
這里的S表示等距同構。(單位向量相當于給模一個旋轉變換,也就是等距同構。)由于M?M?????√是正定對稱方陣,因此它實際上也是能夠被正交化的。所以對于一般矩陣來說,我們總能夠找到兩個正交基,并在這兩個基之間進行投影變換。
注意:我們剛才是用與復數類比的方式,得到投影變換矩陣M?M?????√。但是類比不能代替嚴格的數學證明。幸運的是,上述結論已經被嚴格證明了。
我們將矩陣M?M?????√的特征值,稱作奇異值(Singular value)。可以看出,如果M是對稱方陣的話,則M的奇異值等于M的特征值的絕對值。
參見:
https://www.zhihu.com/question/22237507/answer/53804902
http://www.ams.org/samplings/feature-column/fcarc-svd
奇異值分解
奇異值分解(Singular value decomposition,SVD)定理:
設M∈Rm×n,則必存在正交矩陣U=[u1,…,um]∈Rm×m和V=[v1,…,vn]∈Rn×n使得:
UTMV=[Σr000]
其中,Σr=diag(σ1,…,σr),σ1≥?≥σr>0。
當M為復矩陣時,將U、V改為酉矩陣(unitary matrix)即可。(吐槽一下,酉矩陣這個翻譯真的好爛,和天干地支半毛錢關系都沒有。)
奇異值分解也可寫為另一種形式:
M=UΣV?
其幾何意義如下圖所示:
雖然,我們可以通過計算矩陣M?M?????√的特征值的方法,計算奇異值,然而這個方法的計算量十分巨大。1965年,Gene Howard Golub和William Morton Kahan發明了目前較為通用的算法。但該方法比較復雜,這里不作介紹。
參見:
http://www.doc88.com/p-089411326888.html
Gene Howard Golub,1932~2007,美國數學家,斯坦福大學教授。
William Morton Kahan,1933年生,加拿大數學家,多倫多大學博士,UCB教授。圖靈獎獲得者(1989)。IEEE-754標準(即浮點數標準)的主要制訂者,被稱為“浮點數之父”。ACM院士。
矩陣的秩
一個矩陣A的列(行)秩是A的線性獨立的列(行)的極大數。
下面不加證明的給出矩陣的秩的性質:
1.矩陣的行秩等于列秩,因此可統稱為矩陣的秩。
2.秩是n的m×n矩陣為列滿秩陣;秩是n的n×p矩陣為行滿秩陣。
3.設A∈Mm×n(F),若A是行滿秩陣,則m≤n;若A是列滿秩陣 ,則n≤m。
4.設A為m×n列滿秩陣,則n元齊次線性方程組AX=0只有零解。
5.線性方程組AX=B對任一m維列向量B都有解?系數矩陣A為行滿秩陣。
參見:
http://wenku.baidu.com/view/9ce143eb81c758f5f61f6730.html
奇異矩陣
對應的行列式等于0的方陣,被稱為奇異矩陣(singular matrix)。
奇異矩陣和線性相關、秩等概念密切相關。
下面不加證明的給出奇異矩陣的性質:
1.如果A為非奇異矩陣?A滿秩。
2.如果A為奇異矩陣,則AX=0有無窮解,AX=b有無窮解或者無解。如果A為非奇異矩陣,則AX=0有且只有唯一零解,AX=b有唯一解。
對于A不是方陣的情況,一般使用ATA來評估矩陣是否是奇異矩陣。
向量的范數
范數(norm,也叫模)的定義比較抽象,這里我們使用閔可夫斯基距離,進行一個示意性的介紹。
Minkowski distance的定義:
d(x,y)=∑i=1n∣xi?yi∣λ??????????√λ
顯然,當λ=2時,該距離為歐氏距離。當λ=1時,也被稱為CityBlock Distance或Manhattan Distance(曼哈頓距離)。
這里的λ就是范數。
總結
以上是生活随笔為你收集整理的机器学习(十二)——机器学习中的矩阵方法(2)特征值和奇异值的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 机器学习(十一)——机器学习中的矩阵方法
- 下一篇: 机器学习(十四)——协同过滤的ALS算法