人工智能降維

1、 人工智能人工智能 - 降維方法降維方法 PPT講解：奚蒙 PPT制作：劉磊 2015年12月10日 降維是把采集的數(shù)據(jù)從一個高維空間映射到維度要低得多的一個新的空間的過程。而這個過程是與信息（有損）壓縮概念密切相關(guān)的。有以下幾個原因，以減少數(shù)據(jù)的維數(shù)。 首先，高維數(shù)據(jù)帶來對計算的極大挑戰(zhàn)。并且，在某些情況下，高維可能會導(dǎo)致算法的學(xué)習(xí)具有較差的泛化能力（例如，在最近鄰分類的樣品的復(fù)雜性隨著維度增加呈現(xiàn)指數(shù)增加）最后，降維可以用于數(shù)據(jù)的解釋性，為發(fā)現(xiàn)有意義的數(shù)據(jù)結(jié)構(gòu)，并說明其用途。主成分分析法簡介主成分分析法簡介lPrincipal Component Analysis（PCA）l主成分分析(P

2、rincipal Component Analysis, 簡稱PCA)是一種常用的基于變量協(xié)方差矩陣對信息進行處理、壓縮和抽提的有效方法。基于基于PCA算法的人臉識別算法的人臉識別lPCA方法由于其在降維和特征提取方面的有效性，在人臉識別領(lǐng)域得到了廣泛的應(yīng)用。lPCA方法的基本原理是:利用K-L變換抽取人臉的主要成分，構(gòu)成特征臉空間，識別時將測試圖像投影到此空間，得到一組投影系數(shù)，通過與各個人臉圖像比較進行識別。l利用特征臉法進行人臉識別的過程由訓(xùn)練階段和識別階段兩個階段組成 l其具體步驟如下： 訓(xùn)練階段訓(xùn)練階段l第一步：假設(shè)訓(xùn)練集有200個樣本，由灰度圖組成，每個樣本大小為M*Nl寫出訓(xùn)練樣

3、本矩陣：l其中向量xi為由第i個圖像的每一列向量堆疊成一列的MN維列向量,即把矩陣向量化,如下圖所示：Txxxx20021,.,訓(xùn)練階段訓(xùn)練階段l如：第i個圖像矩陣為l則xi為987654321963852741訓(xùn)練階段訓(xùn)練階段l第二步：計算平均臉 計算訓(xùn)練圖片的平均臉：20012001iiix訓(xùn)練階段訓(xùn)練階段l第三步：計算差值臉 計算每一張人臉與平均臉的差值ixdii訓(xùn)練階段訓(xùn)練階段l第四步：構(gòu)建協(xié)方差矩陣TiTiiAAddC20012001200120021,.,dddA訓(xùn)練階段訓(xùn)練階段l第五步：求協(xié)方差矩陣的特征值和特征向量，構(gòu)造特征臉空間 協(xié)方差矩陣的維數(shù)為MN*MN，考慮其維數(shù)較大，

4、計算量比較大，所以采用奇異值分解(SingularValue Decomposition ,SVD)定理，通過求解 的特征值和特征向量來獲得 的特征值和特征向量。TAAAAT訓(xùn)練階段訓(xùn)練階段l求出 的特征值 及其正交歸一化特征向量l根據(jù)特征值的貢獻率選取前p個最大特征向量及其對應(yīng)的特征向量l貢獻率是指選取的特征值的和與占所有特征值的和比，即：iAATiiiiiaiiipiii20011訓(xùn)練階段訓(xùn)練階段l一般取 即使訓(xùn)練樣本在前p個特征向量集上的投影有99%的能量 求出原協(xié)方差矩陣的特征向量 則“特征臉”空間為： %99a),.,2 , 1(1piAvuiiipuuuw，,.,21訓(xùn)練階段訓(xùn)練階

5、段l第六步l 將每一幅人臉與平均臉的差值臉矢量投影到“特征臉”空間，即200,.,2 , 1idwiTi識別階段識別階段l第一步：將待識別的人臉圖像 與平均臉的差值臉投影到特征空間，得到其特征向量表示：Tw識別階段識別階段l第二步：定義閾值200,.,2 , 1,max21,jijiji識別階段識別階段l第三步：采用歐式距離來計算 與每個人臉的距離i200,.,2 , 122iii識別階段識別階段l 為了區(qū)分人臉和非人臉，還需要計算原始圖像 與由特征臉空間重建的圖像 之間的距離l其中：f22fwf識別階段識別階段l 根據(jù)以下規(guī)則對人臉進行分類：l1)若 ，則輸入圖像不是人臉圖像；l2)若 ，且

6、 ， 則輸入圖像包含未知人臉；l3)若 ，且 ， 則輸入圖像為庫中第k個人的人臉。iiii2D-PCAl2D-PCA是在基本PCA算法上的改進，主要不同是協(xié)方差矩陣構(gòu)造方法不同，選取前P個最大特征值和特征向量也有所不同。訓(xùn)練階段訓(xùn)練階段l 1設(shè)訓(xùn)練樣本集合為：l其中： i表示第i個人，即類別數(shù)， j表示第i個人的第j幅圖像 N表示識別的人數(shù)， K表示每個人包含K幅圖像， M表示樣本總數(shù)且M=NKKJNiRsnmij,.,2 , 1,.,2 , 1,訓(xùn)練階段訓(xùn)練階段l 2 計算所有訓(xùn)練樣本的平均圖像NiKjijSMS111訓(xùn)練階段訓(xùn)練階段l 3計算樣本的協(xié)方差矩陣： SSSSMGijTNiKji

7、j111訓(xùn)練階段訓(xùn)練階段l 4求出協(xié)方差矩陣的特征值，選取其中最大特征值 對應(yīng)的正交特征向量 作為投影空間。 用投影矩陣Y的總離散度作為準(zhǔn)則函數(shù)J (U)來衡量投影空間U的優(yōu)劣： puu .1pXX .1 uStrUJ訓(xùn)練階段訓(xùn)練階段lSu是投影矩陣Y的協(xié)方差矩陣， 是 的跡，且：l選取的特征向量為uStruS UxExxExEUSTTU pjijiXXUJXXXUjTip,.,2 , 1,; 0,maxarg,.,21訓(xùn)練階段訓(xùn)練階段l5 訓(xùn)練樣本 向 空間投影得到： KjNisij,.,2 , 1,.,2 , 1,pXX .1pmijijpijiijijRpYYXSXSY)(),.,1 (

8、,.,識別階段識別階段l 1測試樣本 向 空間投影后得到樣本W(wǎng)的特征矩陣 和主成分分量 ：nmRW*pXX .1)(),.,1 (pYYijij pijijtWXWXpYYY,.,),.,1 (1tY識別階段識別階段l 2根據(jù)測試樣本投影特征矩陣與所有訓(xùn)練樣本投影特征矩陣之間的最小距離來判斷測試樣本所屬的類別。定義如下的距離度量準(zhǔn)則:l其中 表示兩個特征向量之間的歐氏距離。 21,pntijtijnYnYYYp 2nYnYtij識別階段識別階段l3 若 則 屬于第q個人 tijjitqdYYpYYp,minmin,tYIntroduction to Compressive Sensing壓縮感

9、知概述目錄p背景現(xiàn)狀u理論產(chǎn)生背景u研究現(xiàn)狀p 壓縮感知描述u壓縮傳感u稀疏表示u測量矩陣u重構(gòu)算法u模擬實驗u整體流程p 應(yīng)用展望u 應(yīng)用舉例u展望 一、背景現(xiàn)狀1、背景現(xiàn)狀1.1 理論產(chǎn)生背景采樣發(fā)的采樣數(shù)據(jù)壓縮原始圖像數(shù)據(jù)傳輸解壓縮恢復(fù)圖像通過顯示器顯示圖像大部分冗余信息在采集后被丟棄采樣時造成很大的資源浪費能否直接采集不被丟棄的信息？被感知對象重建信號壓縮感知名詞解釋：壓縮感知直接感知壓縮后的信息基本方法：信號在某一個正交空間具有稀疏性（即可壓縮性），就能以較低的頻率（遠(yuǎn)低于奈奎斯特采樣頻率）采樣該信號，并可能以高概率重建該信號。1.1 理論產(chǎn)生背景1、背景現(xiàn)狀1.2 研究現(xiàn)狀2006

10、Robust Uncertainty Principles：Exact Signal Reconstruction fromHighly Incomplete Frequency InformationTerence Tao、Emmanuel Cands2006Compressed SensingDavid Donoho2007Compressive SensingRichard Baraniuk上述文章奠定了壓縮感知的理論基礎(chǔ)。國內(nèi)也將其翻譯成壓縮傳感或壓縮采樣。1、背景現(xiàn)狀u理論一經(jīng)提出，就在信息論、信號處理、圖像處理等領(lǐng)域受到高度關(guān)注。u在美國、英國、德國、法國、瑞士、以色列等許多國家的

11、知名大學(xué)(如麻省理工學(xué)院、斯坦福大學(xué)、普林斯頓大學(xué)、萊斯大學(xué)、杜克大學(xué)、慕尼黑工業(yè)大學(xué)、愛丁堡大學(xué)等等)成立了專門的課題組對CS進行研究。u此外，萊斯（Rice）大學(xué)還建立了專門的Compressive Sensing網(wǎng)站，及時報道和更新該方向的最新研究成果。1.2 研究現(xiàn)狀1、背景現(xiàn)狀u西安電子科技大學(xué)石光明教授在電子學(xué)報發(fā)表綜述文章，系統(tǒng)地闡述了壓縮傳感的理論框架以及其中涉及到的關(guān)鍵技術(shù)問題。燕山大學(xué)練秋生教授的課題組針對壓縮感知的稀疏重建算法進行了系統(tǒng)深入的研究，提出一系列高質(zhì)量的圖像重建算法。中科院電子所的方廣有研究員等，探索了壓縮感知理論在探地雷達三維成像中的應(yīng)用。u除此之外，還有很

12、多國內(nèi)學(xué)者在壓縮感知方面做了重要的工作，如清華大學(xué)、天津大學(xué)、國防科技大學(xué)、廈門大學(xué)、湖南大學(xué)、西南交通大學(xué)、南京郵電大學(xué)、華南理工大學(xué)、北京理工大學(xué)、北京交通大學(xué)等等單位，在此不一一列舉。1.2 研究現(xiàn)狀1、背景現(xiàn)狀二、壓縮感知描述2、CS描述2.1 壓縮傳感x是K稀疏的，并且y與滿足一定關(guān)系時2、CS描述2.1 壓縮傳感yx (1) 很顯然，由于的維數(shù)遠(yuǎn)遠(yuǎn)低于的維數(shù)，方程1有無窮多個解，即該方程是不適定的，很難重構(gòu)信號。然而如果原信號是K稀疏的，并且y與滿足一定關(guān)系時，理論證明，方程是可以通過求解最優(yōu)范數(shù)問題精確重構(gòu)0argmin. .xxstxy (2)式中，為向量的范數(shù)，表示向量中非零

13、元素的個數(shù)，Cands指出，如果要精確重構(gòu)，測量次數(shù)M必須滿足M=O(Kln(N) ,并且滿足約束等距性條件。2、CS描述2.1 壓縮傳感2、CS描述2.1 壓縮傳感2、CS描述2.2 稀疏表示 如果一個信號中只有少數(shù)元素是非零的，則該信號是稀疏的。通常時域內(nèi)的信號是非稀疏的，但是在某個變換域可能是稀疏的。2、CS描述2.2 稀疏表示 如果長度為N的信號X，在變換域個系數(shù)不為零（或者明顯不大于其他系數(shù)），且KN，那么可以認(rèn)為信號X在域中是稀疏的并可記為K-稀疏（不是嚴(yán)格定義）。2、CS描述2.2 稀疏表示2、CS描述2.2 稀疏表示2、CS描述2.3 測量矩陣2、CS描述2.3 測量矩陣yx

14、(3)為了重構(gòu)稀疏信號，Terence Tao、Emmanuel Cands 給出并證明了必須滿足約束等距性條件，對于任意和常數(shù)，有222222(1)(1)kkccc (4)2、CS描述2.3 測量矩陣 Baraniuk給出了約束等距性條件的等價條件是測量矩陣和稀疏表示基不相關(guān)，即要求的行不能由的列稀疏表示，且的列不能由的行稀疏表示。由于是固定的，要使得滿足約束等距性條件，可以通過設(shè)計測量矩陣來解決，有證明，當(dāng)時高斯隨機矩陣時， 能以較大概率滿足約束等距性條件。2、CS描述2.3 測量矩陣 隨機矩陣重建性能好，但不易于硬件實現(xiàn)。 確定性測量矩陣因為其占用存儲空間少，硬件實現(xiàn)容易，是未來測量矩陣

15、的研究方向，但目前確定性矩陣的重建精度不如隨機矩陣。隨機測量矩陣確定性測量矩陣高斯矩陣輪換矩陣傅里葉多項式矩陣貝努力哈達嗎矩陣非相關(guān)測量矩陣托普利茲矩陣結(jié)構(gòu)化隨機矩陣Chirp測量矩陣.2、CS描述2.4 重構(gòu)算法直接求解相當(dāng)困難。以下兩種解決方案：1 不改變目標(biāo)函數(shù)，尋求近似的方法求解 用近似的方法直接求解0范數(shù)問題，如貪婪算法等。2 將目標(biāo)函數(shù)進行轉(zhuǎn)化，變?yōu)楦菀浊蠼獾膯栴}（1）將0范數(shù)問題轉(zhuǎn)化為1范數(shù)問題（2）采用光滑函數(shù)逼近0范數(shù)，從而將0范數(shù)問題轉(zhuǎn)化為光滑函數(shù)的極值問題2、CS描述2.4 重構(gòu)算法（1）匹配追蹤系列：匹配追蹤（Matching Pursuit, MP）正交匹配追蹤(O

16、rthogonal Matching Pursuit, OMP)稀疏自適應(yīng)匹配追蹤(Sparse Adaptive MP, SAMP)正則化正交匹配追蹤(Regularized OMP, ROMP)等（2）方向追蹤系列：梯度追蹤(Gradient Pursuit, GP)共軛梯度追蹤(Conjugate GP,CGP)近似的共軛梯度追蹤(Approximation CGP, ACGP)貪婪算法2、CS描述2.4 重構(gòu)算法凸優(yōu)化算法（1）基追蹤法(Basis Pursuit, BP)（2）最小角度回歸法(Least Angle Regression, LARS)（3）梯度投影法(Gradient

17、 Projection for Sparse Reconstruction, GPSR) 另類算法（1）Bayesian類的統(tǒng)計優(yōu)化算法2、CS描述2.5 模擬實驗2、CS描述2.5 模擬實驗2、CS描述2.5 模擬實驗2、CS描述2.5 模擬實驗OMP_time =0.051175s2、CS描述2.6 總體流程理論依據(jù)：設(shè)長度為N的信號X在某個正交基上是K-稀疏的，如果能找到一個與不相關(guān)（不相干）的觀測基 ，用觀測基觀測原信號得到M個觀測值，KMN，得到觀測值Y，那么可以利用最優(yōu)化方法從觀測值中高概率重構(gòu)X。找到某個正交基 ，信號在該基上稀疏找到一個與不相關(guān)，且滿足一定條件的觀測基 對Y采用

18、最優(yōu)化重建， 均是其約束。以觀測真實信號，得到觀測值Y主要解決的問題：1. 信號的稀疏表示2. 觀測基的選取3. 重構(gòu)算法的設(shè)計三、應(yīng)用展望3、應(yīng)用展望3.1 應(yīng)用舉例國防科技大學(xué)從壓縮感知的角度對熱光源關(guān)聯(lián)成像進行了研究。國防科技大學(xué)從壓縮感知的角度對熱光源關(guān)聯(lián)成像進行了研究。 隨機熱光源輻射的光束通過分束器分為完全相同的兩束，一束稱為檢測隨機熱光源輻射的光束通過分束器分為完全相同的兩束，一束稱為檢測光束，使其照射被成像物體，利用光學(xué)器件將透射的光束會聚為一點，并由光束，使其照射被成像物體，利用光學(xué)器件將透射的光束會聚為一點，并由“單像素單像素”光電檢測器記錄該點光強；另一束為參考光束，由光電檢測器記錄該點光強；另一束為參考光束，由 CCD CCD 陣列直陣列直接記錄光強。通過計算單像素點與接記錄光強。通過計算單像素點與 CCD CCD 陣列光強之間的互相關(guān)，可得到物