人工智能降維

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

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

3、本矩陣：l其中向量xi為由第i個(gè)圖像的每一列向量堆疊成一列的MN維列向量,即把矩陣向量化,如下圖所示：Txxxx20021,.,訓(xùn)練階段訓(xùn)練階段l如：第i個(gè)圖像矩陣為l則xi為987654321963852741訓(xùn)練階段訓(xùn)練階段l第二步：計(jì)算平均臉 計(jì)算訓(xùn)練圖片的平均臉：20012001iiix訓(xùn)練階段訓(xùn)練階段l第三步：計(jì)算差值臉 計(jì)算每一張人臉與平均臉的差值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、計(jì)算量比較大，所以采用奇異值分解(SingularValue Decomposition ,SVD)定理，通過(guò)求解 的特征值和特征向量來(lái)獲得 的特征值和特征向量。TAAAAT訓(xùn)練階段訓(xùn)練階段l求出 的特征值 及其正交歸一化特征向量l根據(jù)特征值的貢獻(xiàn)率選取前p個(gè)最大特征向量及其對(duì)應(yīng)的特征向量l貢獻(xiàn)率是指選取的特征值的和與占所有特征值的和比，即：iAATiiiiiaiiipiii20011訓(xùn)練階段訓(xùn)練階段l一般取 即使訓(xùn)練樣本在前p個(gè)特征向量集上的投影有99%的能量 求出原協(xié)方差矩陣的特征向量 則“特征臉”空間為： %99a),.,2 , 1(1piAvuiiipuuuw，,.,21訓(xùn)練階段訓(xùn)練階

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

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

7、j111訓(xùn)練階段訓(xùn)練階段l 4求出協(xié)方差矩陣的特征值，選取其中最大特征值 對(duì)應(yīng)的正交特征向量 作為投影空間。 用投影矩陣Y的總離散度作為準(zhǔn)則函數(shù)J (U)來(lái)衡量投影空間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、,.,識(shí)別階段識(shí)別階段l 1測(cè)試樣本 向 空間投影后得到樣本W(wǎng)的特征矩陣 和主成分分量 ：nmRW*pXX .1)(),.,1 (pYYijij pijijtWXWXpYYY,.,),.,1 (1tY識(shí)別階段識(shí)別階段l 2根據(jù)測(cè)試樣本投影特征矩陣與所有訓(xùn)練樣本投影特征矩陣之間的最小距離來(lái)判斷測(cè)試樣本所屬的類別。定義如下的距離度量準(zhǔn)則:l其中 表示兩個(gè)特征向量之間的歐氏距離。 21,pntijtijnYnYYYp 2nYnYtij識(shí)別階段識(shí)別階段l3 若 則 屬于第q個(gè)人 tijjitqdYYpYYp,minmin,tYIntroduction to Compressive Sensing壓縮感

9、知概述目錄p背景現(xiàn)狀u理論產(chǎn)生背景u研究現(xiàn)狀p 壓縮感知描述u壓縮傳感u稀疏表示u測(cè)量矩陣u重構(gòu)算法u模擬實(shí)驗(yàn)u整體流程p 應(yīng)用展望u 應(yīng)用舉例u展望 一、背景現(xiàn)狀1、背景現(xiàn)狀1.1 理論產(chǎn)生背景采樣發(fā)的采樣數(shù)據(jù)壓縮原始圖像數(shù)據(jù)傳輸解壓縮恢復(fù)圖像通過(guò)顯示器顯示圖像大部分冗余信息在采集后被丟棄采樣時(shí)造成很大的資源浪費(fèi)能否直接采集不被丟棄的信息？被感知對(duì)象重建信號(hào)壓縮感知名詞解釋：壓縮感知直接感知壓縮后的信息基本方法：信號(hào)在某一個(gè)正交空間具有稀疏性（即可壓縮性），就能以較低的頻率（遠(yuǎn)低于奈奎斯特采樣頻率）采樣該信號(hào)，并可能以高概率重建該信號(hào)。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ǔ)。國(guó)內(nèi)也將其翻譯成壓縮傳感或壓縮采樣。1、背景現(xiàn)狀u理論一經(jīng)提出，就在信息論、信號(hào)處理、圖像處理等領(lǐng)域受到高度關(guān)注。u在美國(guó)、英國(guó)、德國(guó)、法國(guó)、瑞士、以色列等許多國(guó)家的

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

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

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

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

15、的研究方向，但目前確定性矩陣的重建精度不如隨機(jī)矩陣。隨機(jī)測(cè)量矩陣確定性測(cè)量矩陣高斯矩陣輪換矩陣傅里葉多項(xiàng)式矩陣貝努力哈達(dá)嗎矩陣非相關(guān)測(cè)量矩陣托普利茲矩陣結(jié)構(gòu)化隨機(jī)矩陣Chirp測(cè)量矩陣.2、CS描述2.4 重構(gòu)算法直接求解相當(dāng)困難。以下兩種解決方案：1 不改變目標(biāo)函數(shù)，尋求近似的方法求解 用近似的方法直接求解0范數(shù)問(wèn)題，如貪婪算法等。2 將目標(biāo)函數(shù)進(jìn)行轉(zhuǎn)化，變?yōu)楦菀浊蠼獾膯?wèn)題（1）將0范數(shù)問(wèn)題轉(zhuǎn)化為1范數(shù)問(wèn)題（2）采用光滑函數(shù)逼近0范數(shù)，從而將0范數(shù)問(wèn)題轉(zhuǎn)化為光滑函數(shù)的極值問(wèn)題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)計(jì)優(yōu)化算法2、CS描述2.5 模擬實(shí)驗(yàn)2、CS描述2.5 模擬實(shí)驗(yàn)2、CS描述2.5 模擬實(shí)驗(yàn)2、CS描述2.5 模擬實(shí)驗(yàn)OMP_time =0.051175s2、CS描述2.6 總體流程理論依據(jù)：設(shè)長(zhǎng)度為N的信號(hào)X在某個(gè)正交基上是K-稀疏的，如果能找到一個(gè)與不相關(guān)（不相干）的觀測(cè)基 ，用觀測(cè)基觀測(cè)原信號(hào)得到M個(gè)觀測(cè)值，KMN，得到觀測(cè)值Y，那么可以利用最優(yōu)化方法從觀測(cè)值中高概率重構(gòu)X。找到某個(gè)正交基 ，信號(hào)在該基上稀疏找到一個(gè)與不相關(guān)，且滿足一定條件的觀測(cè)基 對(duì)Y采用

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