培訓(xùn)先進(jìn)人機(jī)通信技術(shù)聯(lián)合實(shí)驗(yàn)室TrainingAdvancedHumanComputerCommunicationTechnologyJointLaboratory精課件

1、2022年8月20日1Semi-supervised Learning by Sparse RepresentationShuicheng Yan Huan WangLecturer: Yitao Zhai2022/8/20作者的相關(guān)信息Shuicheng Yan第一作者新加坡國(guó)立大學(xué)助理教授簡(jiǎn)歷2019和2019年分別從北京大學(xué)獲得應(yīng)用數(shù)學(xué)的學(xué)士和博士學(xué)位分別在微軟亞洲研究院，UIUC，香港中文大學(xué)做過研究工作研究方向圖像與視頻中的行為檢測(cè)子空間學(xué)習(xí)與流形學(xué)習(xí)物體識(shí)別與分類生物識(shí)別醫(yī)學(xué)圖像分析論文期刊: 36, 會(huì)議: 69.個(gè)人主頁: .sg/stfpage/eley

2、ans/作者的相關(guān)信息Huan Wang第二作者00-04 浙江大學(xué) 信息與電子工程學(xué)院04-07 香港中文大學(xué) 信息工程學(xué)院目前在耶魯大學(xué)計(jì)算機(jī)學(xué)院研究方向計(jì)算機(jī)視覺，機(jī)器學(xué)習(xí)，信源編碼，嵌入式系統(tǒng)等發(fā)表論文第一作者論文5篇 ：CVPR 08; IJCAI 07(oral); CVR07; ICML07( oral); ACM MM06主頁.hk/huan/Welcome.htmljoyousprince.spaces.live/2022年8月20日3文章出處S. Yan and H. Wang. Semi-supervised learning by sp

3、arse representation. SIAM International Conference on Data Mining(SDM09).相關(guān)文獻(xiàn)J. Wright, A. Ganesh, A. Yang, and Y. Ma: Robust face recognition via sparse representation. TPAMI, in press, 2019.X. Zhu, Z. Ghahramani, and J. Lafferty. Semi-supervised learning using Gaussian fields and harmonic function

4、s. ICML, 2019.D. Cai, X. He, and J. Han. Semi-supervised discriminant analysis. ICCV, 2019.2022年8月20日4SIAM 簡(jiǎn)介工業(yè)和應(yīng)用數(shù)學(xué)學(xué)會(huì) (Society for Industry and Applied Mathematics ,SIAM) 于二十世紀(jì)五十年代前期在美國(guó)成立，是一個(gè)以促進(jìn)應(yīng)用和計(jì)算數(shù)學(xué)的研究、發(fā)展、應(yīng)用為目的的協(xié)會(huì)SIAM以出版的高水準(zhǔn)和頗具聲譽(yù)的期刊而自豪。SIAM中共包括13種期刊，這13種同行評(píng)審的研究期刊在應(yīng)用和計(jì)算數(shù)學(xué)的高等研究領(lǐng)域非常著名，它們涵蓋了整個(gè)應(yīng)用和計(jì)算數(shù)

5、學(xué)領(lǐng)域，內(nèi)容豐富而全面。根據(jù)ISI公司2019年出版的期刊引用報(bào)告JCR，幾乎所有SIAM的期刊的影響因子都接近或超過1。 SIAM Review獲得“數(shù)學(xué)”領(lǐng)域前所未有的高影響因子6.118 在應(yīng)用數(shù)學(xué)領(lǐng)域的162種期刊中，SIAM的期刊占據(jù)了前25位中的7席主頁： /2022年8月20日5摘要本文中，我們提出了一種基于L1 Graph的半監(jiān)督學(xué)習(xí)框架。L1 Graph 受啟發(fā)于每個(gè)樣本可以通過訓(xùn)練數(shù)據(jù)的稀疏線性加和進(jìn)行重建。通過一個(gè)求解L1優(yōu)化問題，可以得到稀疏重建的系數(shù)，然后利用這些系數(shù)作為L(zhǎng)1 Graph的邊的權(quán)重。傳統(tǒng)的構(gòu)造圖的方法包含兩個(gè)獨(dú)立的步驟：確定邊是否鄰接；

6、計(jì)算邊的權(quán)重。L1 Graph將這兩個(gè)步驟合并進(jìn)行，而且構(gòu)造L1 Graph的過程是與參數(shù)無關(guān)的。受啟發(fā)于稀疏表示在人臉識(shí)別領(lǐng)域的成功應(yīng)用，我們提出了基于L1-Graph的半監(jiān)督學(xué)習(xí)框架。在半監(jiān)督人臉識(shí)別與圖像分類上的大量實(shí)驗(yàn)證明了我們的L1Graph框架的優(yōu)越性。2022年8月20日6文章結(jié)構(gòu)AbstractIntroductionTraditional Graph ConstructionL1-Graph：Motivation and ConstructionSemi-supervised Learning over L1-GraphExperimentsConclusion and Fu

7、ture Work2022年8月20日7講解提綱圖模型稀疏表示與L1-GraphL1-Graph與半監(jiān)督學(xué)習(xí)L1-Graph與半監(jiān)督辨別分析實(shí)驗(yàn)結(jié)論及未來工作2022年8月20日8講解提綱圖模型稀疏表示與L1-GraphL1-Graph與半監(jiān)督學(xué)習(xí)L1-Graph與半監(jiān)督辨別分析實(shí)驗(yàn)結(jié)論及未來工作2022年8月20日9圖模型訓(xùn)練集可以看做一個(gè)無向有權(quán)圖G=X,WX：頂點(diǎn)集，每個(gè)訓(xùn)練樣本是圖中的一個(gè)頂點(diǎn) ，N為訓(xùn)練樣本數(shù)W：相似度矩陣， 表示樣本i和樣本j的相似度傳統(tǒng)的圖模型構(gòu)造方法分為兩步：確定兩個(gè)頂點(diǎn)間是否存在一條邊計(jì)算邊權(quán)重 2022年8月20日10Step1：選擇邊 近鄰如果兩個(gè)樣本點(diǎn)滿

8、足 ，則兩個(gè)樣本間存在一條邊常常導(dǎo)致若干個(gè)獨(dú)立的子圖K最近鄰如果 是 的最近鄰的K個(gè)樣本之一，那么這兩個(gè)樣本間存在一條邊2022年8月20日11Step2：計(jì)算邊的權(quán)重高斯核歐式距離的倒數(shù)局部線性重建系數(shù)：通過最小化L2重建誤差，用樣本的近鄰樣本對(duì)其進(jìn)行重建2022年8月20日12傳統(tǒng)圖模型的缺點(diǎn)選擇邊和計(jì)算權(quán)重分開進(jìn)行嚴(yán)重依賴與參數(shù) 中的 ，K近鄰中的K尤其是 ，很難選取一個(gè)合適的應(yīng)用于分類任務(wù)時(shí)往往效果很差歐式距離下最近鄰的樣本往往并非同類樣本2022年8月20日13需要什么樣的圖自適應(yīng)的調(diào)整樣本間關(guān)系傳統(tǒng)方法中，不同的數(shù)據(jù)分布就需要不同的參數(shù)Parameter-Free稀疏性表征樣本間局

9、部關(guān)系的稀疏圖包含對(duì)分類有用的信息1存儲(chǔ)開銷辨別能力更好的用于分類任務(wù)目標(biāo)：同類樣本間權(quán)重較高，不同類樣本間權(quán)重較低1M. Belkin and P. Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 2019.2022年8月20日14講解提綱圖模型稀疏表示與L1-GraphL1-Graph與半監(jiān)督學(xué)習(xí)L1-Graph與半監(jiān)督辨別分析實(shí)驗(yàn)結(jié)論及未來工作2022年8月20日152022年8月20日稀疏表示：示例fromSubject 1down

10、-sampleto 12x10對(duì)應(yīng)兩個(gè)最大的系數(shù)擴(kuò)展YaleB上隨機(jī)選取1207個(gè)樣本作為基，使用最小化L1范式后得到的稀疏系數(shù)?？梢钥闯觯瑢?duì)應(yīng)最大的兩個(gè)系數(shù)都是測(cè)試樣本的同類樣本。稀疏表示受啟發(fā)與稀疏表示在人臉識(shí)別上的成功應(yīng)用1任一訓(xùn)練樣本可以由其余訓(xùn)練樣本的線性組合來重構(gòu)（允許一定重構(gòu)誤差），重構(gòu)系數(shù)是稀疏的使用重構(gòu)系數(shù)做為兩個(gè)樣本之間的權(quán)重，表征樣本間關(guān)系求解稀疏表示是一個(gè)最小化L1范式問題 是一組基，y為待表示樣本， 為重建系數(shù)1 J. Wright, A. Ganesh, A. Yang, and Y. Ma: Robust face recognition via sparse r

11、epresentation. TPAMI, in press, 2019.2022年8月20日17最小化L1范式最小化L1范式問題：特征維數(shù)遠(yuǎn)大于樣本數(shù)目時(shí)，往往得不到稀疏的表示 L1 Graph的做法：對(duì)任一樣本，用除它之外的所有樣本做基求解最小化L1范式問題求解方法基追蹤（Basis pursuit）匹配追蹤（Matching pursuit）最小全變分法迭代閾值法2022年8月20日18L1 Graph2022年8月20日19L1-Graph優(yōu)點(diǎn)L1-Graph 是稀疏的通過最小化L1范式得到的非零系數(shù)一般遠(yuǎn)小于特征維數(shù)L1-Graph是自適應(yīng)的L1-Graph中每個(gè)樣本近鄰的數(shù)目是通過

12、最小化L1范式來確定的，不需要人工設(shè)置參數(shù)L1-Graph包含辨別信息權(quán)重較大邊往往連接了同類的樣本2022年8月20日20L1 VS L2LLE也是最小化重建誤差最小化L1： 為什么不用LLE？LLE一般得不到稀疏表示LLE的最小化重建誤差僅涉及部分樣本LLE需要確定參數(shù)2022年8月20日21不同Graph的鄰接矩陣Yale上165幅圖片b: k=3 ?2022年8月20日22講解提綱圖模型稀疏表示與L1-GraphL1-Graph與半監(jiān)督學(xué)習(xí)L1-Graph與半監(jiān)督辨別分析實(shí)驗(yàn)結(jié)論及未來工作2022年8月20日23半監(jiān)督學(xué)習(xí)動(dòng)機(jī)：現(xiàn)實(shí)應(yīng)用中缺少足夠有標(biāo)注的訓(xùn)練數(shù)據(jù)半監(jiān)督學(xué)習(xí)：通過利用有標(biāo)

13、注數(shù)據(jù)和未標(biāo)注數(shù)據(jù)間的數(shù)據(jù)分布關(guān)系來提升訓(xùn)練效果方法：EM with generative mixture models self-training co-trainingtransductive support vector machines,graph-based methods.2022年8月20日24基于圖的半監(jiān)督學(xué)習(xí)Graph Preserving Criteria其中 ， ， 是表征樣本 屬于不同類的概率的向量，即 其中K是類別數(shù)， 是給定類別k時(shí) 屬于此類的概率對(duì)于半監(jiān)督學(xué)習(xí)， ， 是有標(biāo)注樣本的概率向量， 是無標(biāo)注樣本的概率向量對(duì)于 2022年8月20日25直觀解釋當(dāng)樣本 非常

14、相似時(shí)，那么他們之間的邊的權(quán)重 就比較大，通過最小化這個(gè)目標(biāo)函數(shù)使得樣本之間的類別概率向量 相似，即 之間的類別信息相似。相似樣本屬于同一類2022年8月20日26目標(biāo)函數(shù)化簡(jiǎn) 其中 D為 對(duì)角矩陣， 即W每行的元素和，其余元素全為0， 為W每列的元素的和。 ，其中C是對(duì)稱矩陣2022年8月20日27推導(dǎo)過程的部分詳解標(biāo)準(zhǔn)二次型矩陣的跡等于矩陣對(duì)角元素的和2022年8月20日28半監(jiān)督學(xué)習(xí)求解公式 對(duì)Y求導(dǎo)，得到 即 可以推出： 利用這個(gè)公式就可以求出未標(biāo)注樣本的類別2022年8月20日29講解提綱圖模型稀疏表示與L1-GraphL1-Graph與半監(jiān)督學(xué)習(xí)L1-Graph與半監(jiān)督辨別分析實(shí)驗(yàn)

15、結(jié)論及未來工作2022年8月20日30L1-Graph+SDASDASemi-supervised Discriminant Analysis，是一種基于圖的半監(jiān)督降維方法，可以同L1 Graph結(jié)合起來把在低維特征空間定義的平滑正則項(xiàng)（Smoothness Regularization term)同類內(nèi)散度結(jié)合起來，通過廣義特征值分解找到最優(yōu)的投影方向2022年8月20日31SDA：MotivationLDA很強(qiáng)大，但無法直接用于半監(jiān)督學(xué)習(xí)，此時(shí)由于部分樣本類別信息的缺失，不能很好的估記類內(nèi)散度矩陣SDA使用有類別樣本最大化不同類間的可分性，使用所有樣本（有類別和無類別）估計(jì)數(shù)據(jù)間的內(nèi)在結(jié)構(gòu)

16、數(shù)據(jù)間的內(nèi)在結(jié)構(gòu)：總體散度矩陣，圖模型2022年8月20日32RDALDA目標(biāo)函數(shù)：當(dāng)訓(xùn)練樣本不足時(shí)，為了防止overfitting，有時(shí)會(huì)加入一個(gè)正則項(xiàng)，即RDA（Regularized Discriminant Analysis）2022年8月20日33RDA當(dāng)有部分無類別樣本時(shí)，設(shè)計(jì) 使其包含數(shù)據(jù)的流形結(jié)構(gòu)對(duì)于降維，近鄰樣本應(yīng)該有近似的低維表示使用圖來表征近鄰樣本間關(guān)系2022年8月20日34SDA定義正則項(xiàng)：最小化這個(gè)正則項(xiàng)，使得原始空間中臨近的樣本在映射后的低維空間中仍然相鄰。目標(biāo)函數(shù)： 直觀解釋：最大化類間散度矩陣的同時(shí)，最小化總體散度矩陣，并使得原始空間中臨近的樣本在映射后的低維

17、空間中仍然相鄰2022年8月20日35SDA求解目標(biāo)函數(shù)：D為對(duì)角矩陣，對(duì)角元素為W各行元素的和原目標(biāo)函數(shù)化為：求解 可得到映射2022年8月20日36講解提綱圖模型稀疏表示與L1-GraphL1-Graph與半監(jiān)督學(xué)習(xí)L1-Graph與半監(jiān)督辨別分析實(shí)驗(yàn)結(jié)論及未來工作2022年8月20日37實(shí)驗(yàn)6個(gè)人臉識(shí)別庫XM2VTS：295人，每人4張共1180幅圖片，分辨率36*32ORL： 40人每人10張共400幅圖片，分辨率32*28FERET：70人，每人6張圖片共420幅圖片，32*32CMU PIE：68人，每人選7幅（C27，C05，C29，C09，C07，及光照變化的8和11），32*32Yale：15人，每人11幅圖片，32*32FRGC：275人的5628幅圖片，每人圖片數(shù)從4到6不等，32*32物體分類的數(shù)據(jù)庫ETH-80：8類圖片，每類10個(gè)不同的物體共80個(gè)，每個(gè)物體41幅圖片2022年8月20日38對(duì)比圖L1-GraphLLE-GraphK=3或K=6KNN-Graph K=3或K=6高斯核 高斯核2022年8月20日39實(shí)驗(yàn)結(jié)果2022年8月20日40L1-Graph+SDA2022年8月20日41圖對(duì)參數(shù)的敏感性實(shí)驗(yàn)FERET上的實(shí)驗(yàn)2022年8月20日42標(biāo)注樣本的影響2022年8月20日43講解提綱圖模型稀疏表示與L1-GraphL1-Graph與