北京9月秋季班：貝葉斯、PCA、SVD

北京9月秋季班·機(jī)器學(xué)習(xí)初步極大似然估計(jì)、貝葉斯、PCA、SVD鄒博

2014年9月21日1機(jī)器學(xué)習(xí)機(jī)器學(xué)習(xí)比想象中要簡(jiǎn)單的多舉例：kNN用于分類在具體學(xué)習(xí)機(jī)器學(xué)習(xí)的過程中，往往是因?yàn)橥茖?dǎo)造成的障礙了解基本的高等數(shù)學(xué)知識(shí)是必要的2k近鄰分類(屬于有監(jiān)督學(xué)習(xí))3向量間相似度計(jì)算的方法歐式距離Pearson相關(guān)系數(shù)(Pearsoncorrelation)余弦相似度(cosinesimilarity)4k-均值聚類(屬于無監(jiān)督學(xué)習(xí))創(chuàng)建k個(gè)點(diǎn)作為起始質(zhì)心(如：隨機(jī)選擇起始質(zhì)心)當(dāng)任意一個(gè)點(diǎn)的簇分配結(jié)果發(fā)生改變時(shí) 對(duì)數(shù)據(jù)集中的每個(gè)數(shù)據(jù)點(diǎn)對(duì)每個(gè)質(zhì)心計(jì)算質(zhì)心與數(shù)據(jù)點(diǎn)之間的距離將數(shù)據(jù)點(diǎn)分配到距其最近的簇對(duì)每個(gè)簇，計(jì)算簇中所有點(diǎn)的均值并作為質(zhì)心思考：點(diǎn)的簇分配結(jié)果發(fā)生改變的標(biāo)準(zhǔn)如何判斷？實(shí)踐中可以選擇誤差的平方和最小為何如此選擇？5利用SSE進(jìn)行聚類后處理SSE:SumofSquaredError誤差平方和6二分k-均值聚類后的結(jié)果7線性回歸y=ax+b8多個(gè)變量的情形考慮兩個(gè)變量9最小二乘的目標(biāo)函數(shù)m為樣本個(gè)數(shù)，則一個(gè)比較“符合常理”的誤差函數(shù)為：10使用極大似然估計(jì)解釋最小二乘11似然函數(shù)12對(duì)數(shù)似然13計(jì)算極大似然函數(shù)的最優(yōu)解14最小二乘意義下的參數(shù)最優(yōu)解15貝葉斯準(zhǔn)則條件概率公式P(x|y)=P(x,y)/P(y)P(x,y)=P(x|y)*P(y)P(y|x)=P(x,y)/P(x)P(x,y)=P(y|x)*P(x)則P(x|y)*P(y)=P(y|x)*P(x)從而：P(x|y)=P(y|x)*P(x)/P(y)分類原則：在給定的條件下，哪種分類發(fā)生的概率大，則屬于那種分類。16樸素貝葉斯的假設(shè)一個(gè)特征出現(xiàn)的概率，與它相鄰的特征沒有關(guān)系（特征獨(dú)立性）每個(gè)特征同等重要（特征均衡性）17以文本分類為例樣本：1000封郵件，每個(gè)郵件被標(biāo)記為垃圾郵件或者非垃圾郵件分類目標(biāo)：給定第1001封郵件，確定它是垃圾郵件還是非垃圾郵件方法：樸素貝葉斯18分析類別c：垃圾郵件c1，非垃圾郵件c2詞匯表：統(tǒng)計(jì)1000封郵件中出現(xiàn)的所有單詞，記單詞數(shù)目為N，即形成詞匯表。將每個(gè)樣本si向量化：初始化N維向量xi，若詞wj在si中出現(xiàn)，則xij=1，否則，為0。從而得到1000個(gè)N維向量x。使用：P(c|x)=P(x|c)*P(c)/P(x)19分解P(c|x)=P(x|c)*P(c)/P(x)P(x|c)=P(x1,x2…xN|c)=P(x1|c)*P(x2|c)…P(xN|c)P(x)=P(x1,x2…xN)=P(x1)*P(x2)…P(xN)帶入公式：P(c|x)=P(x|c)*P(c)/P(x)等式右側(cè)各項(xiàng)的含義：P(xi|cj)：在cj(此題目，cj要么為垃圾郵件1，要么為非垃圾郵件0)的前提下，第i個(gè)單詞xi出現(xiàn)的概率P(xi)：在所有樣本中，單詞xi出現(xiàn)的概率P(cj)：(垃圾郵件)cj出現(xiàn)的概率20關(guān)于貝葉斯分類器的若干探討遇到生詞怎么辦？拉普拉斯平滑編程的限制：小數(shù)乘積怎么辦？問題：一個(gè)詞在樣本中出現(xiàn)多次，和一個(gè)詞在樣本中出現(xiàn)一次，形成的詞向量相同由0/1改成計(jì)數(shù)如何判定該分類器的正確率樣本中：K個(gè)生成分類器，1000-K個(gè)作為測(cè)試集交叉驗(yàn)證21復(fù)習(xí)：特征值和特征向量方陣A的特征值為λ，特征向量為x，則：Ax=λx取x為單位向量，兩邊左乘x’，得到x’Ax=λ將單位正交列向量x并排寫成矩陣Q，得到Q’AQ=ΣA=QΣQ-1Q是這個(gè)矩陣A的特征向量組成的矩陣，Σ是一個(gè)對(duì)角陣，每一個(gè)對(duì)角線上的元素就是一個(gè)特征值。22有趣的推導(dǎo)假定觀測(cè)到m個(gè)樣本為a1’,a2’…am’，每個(gè)樣本有n個(gè)維度，即A={ai}(m×n)。向量A*u=(a1’u,a2’u…am’u)’λ=Var(Au)=Σ(ai’u)2=(Au)’Au=u’A’Au左乘uA’Au=λuA’A是A的協(xié)方差矩陣，u是A’A的一個(gè)特征向量，λ的值的大小表示原始觀測(cè)數(shù)據(jù)經(jīng)在向量u的方向上投影值的方差的大小。實(shí)踐中，先將A去均值，然后得到A的協(xié)方差矩陣以上即為主成分分析PCA的核心推導(dǎo)過程。23PCA的兩個(gè)特征向量24PCA的重要應(yīng)用OBB樹OrientedBoundingBoxGIS中的重要應(yīng)用特征提取數(shù)據(jù)壓縮降維：人腦看電視對(duì)原始觀測(cè)數(shù)據(jù)A在λ值前k大的特征向量u上投影后，獲得一個(gè)A(m×n)Q(n×k)的序列，再加上特征向量矩陣Q，即將A原來的m×n個(gè)數(shù)據(jù)壓縮到m×k＋k×n個(gè)數(shù)據(jù)。25PCA的應(yīng)用——去噪和冗余利用PCA去噪實(shí)質(zhì)上是對(duì)PCA壓縮數(shù)據(jù)的一個(gè)還原（圖片在下頁P(yáng)PT）。左圖是二維原始觀測(cè)數(shù)據(jù)，向?qū)υ紨?shù)據(jù)主成分方向（圖中虛線方向）投影后，獲得1維列向量Au。此時(shí)可以看做數(shù)據(jù)壓縮過程。將此1維標(biāo)量序列重新經(jīng)u投影回原2維空間，即Auu’。此時(shí)得到二維空間的投影分布如右圖，可見實(shí)際上都分布在一條直線上，此過程可以看做對(duì)原數(shù)據(jù)方差較小方向上的信息丟棄，只保留u方向的信息，這也可以看做一個(gè)去噪過程，從數(shù)學(xué)角度而言去噪勢(shì)必導(dǎo)致原始信息的自由度的丟失，如右圖，雖然分布在一個(gè)二維的坐標(biāo)系上，但實(shí)際其只是分布在一個(gè)一維的直線上。26PCA的重要應(yīng)用——去噪27PCA的重要應(yīng)用——降維28關(guān)于特征值的進(jìn)一步推廣若A是m×n階矩陣，不妨認(rèn)為m>n，則A’A是n×n階方陣。按照上面的方法，得到：A=UΣV*v是n維列向量，組成方陣V；u是m維向量，組成方陣U。即：奇異值分解SVD29SVD的概念奇異值分解（SingularValueDecomposition）是線性代數(shù)中一種重要的矩陣分解，是矩陣分析中正規(guī)矩陣酉對(duì)角化的推廣。在信號(hào)處理、統(tǒng)計(jì)學(xué)等領(lǐng)域有重要應(yīng)用。奇異值分解在某些方面與對(duì)稱矩陣或Hermite矩陣基于特征向量的對(duì)角化類似。然而這兩種矩陣分解盡管有其相關(guān)性，但還是有明顯的不同。奇異值分解可以看做對(duì)稱方陣在任意矩陣上的推廣。突出的、奇特的、非凡的30奇異值分解的提法假設(shè)A是一個(gè)m×n階矩陣，其中的元素全部屬于域K，也就是實(shí)數(shù)域或復(fù)數(shù)域。如此則存在一個(gè)分解使得A=UΣV*，其中U是m×m階酉矩陣；Σ是半正定m×n階對(duì)角矩陣；而V*，即V的共軛轉(zhuǎn)置，是n×n階酉矩陣。這樣的分解就稱作M的奇異值分解。Σ對(duì)角線上的元素Σi,i即為M的奇異值。常見的做法是為了奇異值由大而小排列。如此Σ便能由A唯一確定了。U和V的列分別是A的奇異值的左、右奇異向量31SVD舉例已知4×5階實(shí)矩陣M，求M的奇異值分解M=UΣV*矩陣Σ的所有非對(duì)角元為0。矩陣U和V都是酉矩陣，它們乘上各自的共軛轉(zhuǎn)置都得到單位矩陣。在這個(gè)例子中，由于U和V都是實(shí)矩陣，故它們都是正交矩陣。32U、V的列向量是正交的：正交矩陣33奇異值分解不是唯一的由于Σ有一個(gè)對(duì)角元是零，故這個(gè)奇異值分解值不是唯一的。34奇異值分解中的U、V矩陣奇異值分解能夠用于任意m×n階矩陣，而特征分解只能適用于特定類型的方陣，故奇異值分解的適用范圍更廣：M=UΣV*關(guān)系式的右邊描述了關(guān)系式左邊的特征值分解：V的列向量（右奇異向量）是M*M的特征向量。U的列向量（左奇異向量）是MM*的特征向量。Σ的非零對(duì)角元（非零奇異值）是M*M或者M(jìn)*M的非零特征值的平方根。35直觀的解釋在矩陣A的奇異值分解中A=UΣV*U的列組成一套對(duì)A的正交"輸入"或"分析"的基向量。這些向量是AA*的特征向量。V的列組成一套對(duì)A的正交"輸出"的基向量。這些向量是A*A的特征向量。Σ對(duì)角線上的元素是奇異值，可視為是在輸入與輸出間進(jìn)行的標(biāo)量的“膨脹控制”。這些是A*A及AA*的奇異值，并與U和V的行向量相對(duì)應(yīng)。36SVD四個(gè)矩陣的大小關(guān)系實(shí)際中，往往只保留Σ前k個(gè)較大的數(shù)37求偽逆奇異值分解可以被用來計(jì)算矩陣的偽逆。若矩陣A的奇異值分解為A=UΣV*，那么A的偽逆為A+=VΣ+U*其中Σ+是Σ的偽逆，是將主對(duì)角線上每個(gè)非零元素都求倒數(shù)之后再轉(zhuǎn)置得到的。求偽逆通?？梢杂脕砬蠼庾钚《朔▎栴}。38廣義逆矩陣（偽逆）若A為非奇異矩陣,則線性方程組Ax=b的解為x=A^(-1)b，其中A的A的逆矩陣A^(-1)滿足A^(-1)A=AA^(-1)=I(I為單位矩陣)。若A是奇異陣或長(zhǎng)方陣,x=A+b。A+叫做A的偽逆陣。1955年R.彭羅斯證明了對(duì)每個(gè)m×n階矩陣A,都存在惟一的n×m階矩陣X，滿足：①AXA=A；②XAX=X；③(AX)*＝I；④(XA)*＝I。通常稱X為A的穆爾-彭羅斯廣義逆矩陣,簡(jiǎn)稱M-P逆，記作A+。在矛盾線性方程組Ax＝b的最小二乘解中,x=A+b是范數(shù)最小的一個(gè)解。統(tǒng)一前文使用極大似然得到的公式：39隱形語義索引LSI利用SVD方法的信息檢索被成為隱形語義索引（LatentSemanticIndexing，LSI）或隱形語義分析（LatentSemanticAnalysis，LSA）。在LSI中，一個(gè)矩陣由文檔和詞語組成。當(dāng)在該矩陣上應(yīng)用SVD時(shí)，就會(huì)構(gòu)建出多個(gè)奇異值。這些奇異值代表了文檔中的概念(主題)，這一特點(diǎn)可以用于高效的文檔搜索。同義詞的查找：在千篇相似文檔中抽取出概念，那么，相似詞就可以影射為同一個(gè)概念。比simHash更具有智能化意義。40參考文獻(xiàn)Prof.AndrewNg,MachineLearning,StanfordUniversity,2003PeterHarrington著，李銳，李鵬，曲亞東等譯，人民郵電出版社，2013年6月HansWackernagel,PrincipalComponentAnalysisforautocorrelateddata:ageostatisticalperspecitve,August,1998(PCA)MiaHubert,PeterJ.Rousseeuw,KarlienVandenBranden,ROBPCA:aNewApproachtoRobustPrincipalComponentAnalysis,October27,2003(PCA)/v_july_v/article/details/7624837(SVM)/2008/09/21/the-magical-bayesian-met