培训先进人机通信技术联合实验室TrainingAdvancedHumanComputerCommunicationTechnologyJointLaboratory

1、2021年10月21日1semi-supervised learning by sparse representationshuicheng yan huan wanglecturer: yitao zhai2021-10-21作者的相关信息shuicheng yan第一作者 新加坡国立大学助理教授简历 1999和2004年分别从北京大学获得应用数学的学士和博士学位 分别在微软亚洲研究院，uiuc，香港中文大学做过研究工作研究方向 图像与视频中的行为检测 子空间学习与流形学习 物体识别与分类 生物识别 医学图像分析论文 期刊: 36, 会议: 69.个人主页: http:/www.ece.nu

2、.sg/stfpage/eleyans/作者的相关信息huan wang第二作者 00-04 浙江大学 信息与电子工程学院 04-07 香港中文大学 信息工程学院 目前在耶鲁大学计算机学院研究方向 计算机视觉，机器学习，信源编码，嵌入式系统等发表论文 第一作者论文5篇 ：cvpr 08; ijcai 07(oral); cvr07; icml07( oral); acm mm06主页 .hk/huan/welcome.html http:/ yan and h. wang. semi-supervised learning by spar

3、se representation. siam international conference on data mining(sdm09).相关文献 j. wright, a. ganesh, a. yang, and y. ma: robust face recognition via sparse representation. tpami, in press, 2008. x. zhu, z. ghahramani, and j. lafferty. semi-supervised learning using gaussian fields and harmonic function

4、s. icml, 2003. d. cai, x. he, and j. han. semi-supervised discriminant analysis. iccv, 2007.2021年10月21日4siam 简介工业和应用数学学会 (society for industry and applied mathematics ,siam) 于二十世纪五十年代前期在美国成立，是一个以促进应用和计算数学的研究、发展、应用为目的的协会siam以出版的高水准和颇具声誉的期刊而自豪。siam中共包括13种期刊，这13种同行评审的研究期刊在应用和计算数学的高等研究领域非常著名，它们涵盖了整个应用和计

5、算数学领域，内容丰富而全面。根据isi公司2005年出版的期刊引用报告jcr，几乎所有siam的期刊的影响因子都接近或超过1。 siam review获得“数学”领域前所未有的高影响因子6.118 在应用数学领域的162种期刊中，siam的期刊占据了前25位中的7席主页： /2021年10月21日5摘要本文中，我们提出了一种基于l1 graph的半监督学习框架。l1 graph 受启发于每个样本可以通过训练数据的稀疏线性加和进行重建。通过一个求解l1优化问题，可以得到稀疏重建的系数，然后利用这些系数作为l1 graph的边的权重。传统的构造图的方法包含两个独

6、立的步骤：确定边是否邻接；计算边的权重。l1 graph将这两个步骤合并进行，而且构造l1 graph的过程是与参数无关的。受启发于稀疏表示在人脸识别领域的成功应用，我们提出了基于l1-graph的半监督学习框架。在半监督人脸识别与图像分类上的大量实验证明了我们的l1graph框架的优越性。2021年10月21日6文章结构abstractintroductiontraditional graph constructionl1-graph：motivation and constructionsemi-supervised learning over l1-graphexperimentscon

7、clusion and future work2021年10月21日7讲解提纲图模型稀疏表示与l1-graphl1-graph与半监督学习l1-graph与半监督辨别分析实验结论及未来工作2021年10月21日8讲解提纲图模型稀疏表示与l1-graphl1-graph与半监督学习l1-graph与半监督辨别分析实验结论及未来工作2021年10月21日9图模型训练集可以看做一个无向有权图g=x,w x：顶点集，每个训练样本是图中的一个顶点 ，n为训练样本数 w：相似度矩阵， 表示样本i和样本j的相似度传统的图模型构造方法分为两步： 确定两个顶点间是否存在一条边 计算边边权重 2021年10月21

8、日10ijw12 ,., dnixx xxxrstep1：选择边 近邻 如果两个样本点满足 ，则两个样本间存在一条边 常常导致若干个独立的子图k最近邻 如果 是 的最近邻的k个样本之一，那么这两个样本间存在一条边2021年10月21日11-ball|ijxxixjxstep2：计算边的权重高斯核欧式距离的倒数局部线性重建系数：通过最小化l2重建误差，用样本的近邻样本对其进行重建2021年10月21日122|, if and are neighbors0, otherwisexxijtijexxijw1|ijijwxx2()| , s.t. 1iijjijijwxw xw传统图模型的缺点选择边和

9、计算权重分开进行严重依赖与参数 中的 ，k近邻中的k 尤其是 ，很难选取一个合适的应用于分类任务时往往效果很差 欧式距离下最近邻的样本往往并非同类样本2021年10月21日13-ball-ball需要什么样的图自适应的调整样本间关系 传统方法中，不同的数据分布就需要不同的参数 parameter-free稀疏性 表征样本间局部关系的稀疏图包含对分类有用的信息1 存储开销辨别能力 更好的用于分类任务 目标：同类样本间权重较高，不同类样本间权重较低1m. belkin and p. niyogi. laplacian eigenmaps for dimensionality reduction a

10、nd data representation. neural computation, 2003.2021年10月21日14讲解提纲图模型稀疏表示与l1-graphl1-graph与半监督学习l1-graph与半监督辨别分析实验结论及未来工作2021年10月21日152021年10月21日稀疏表示：示例fromsubject 1down-sampleto 12x10对应两个最大的系数扩展yaleb上随机选取1207个样本作为基，使用最小化l1范式后得到的稀疏系数。可以看出，对应最大的两个系数都是测试样本的同类样本。稀疏表示受启发与稀疏表示在人脸识别上的成功应用1 任一训练样本可以由其余训练样本

11、的线性组合来重构（允许一定重构误差），重构系数是稀疏的 使用重构系数做为两个样本之间的权重，表征样本间关系求解稀疏表示是一个最小化l1范式问题 是一组基，y为待表示样本， 为重建系数1 j. wright, a. ganesh, a. yang, and y. ma: robust face recognition via sparse representation. tpami, in press, 2008.2021年10月21日171 arg m in | | , . .aas t x ay12 ,.,nxx xxa最小化l1范式最小化l1范式问题：特征维数远大于样本数目时，往往得不到稀

12、疏的表示 l1 graph的做法：对任一样本，用除它之外的所有样本做基求解最小化l1范式问题求解方法 基追踪（basis pursuit） 匹配追踪（matching pursuit） 最小全变分法 迭代阈值法2021年10月21日181 arg m in | | , . .aas t x ay, xxx i l1 graph2021年10月21日19l1-graph优点l1-graph 是稀疏的 通过最小化l1范式得到的非零系数一般远小于特征维数l1-graph是自适应的 l1-graph中每个样本近邻的数目是通过最小化l1范式来确定的，不需要人工设置参数l1-graph包含辨别信息 权重较

13、大边往往连接了同类的样本2021年10月21日20l1 vs l2lle也是最小化重建误差最小化l1： 为什么不用lle？ lle一般得不到稀疏表示 lle的最小化重建误差仅涉及部分样本 lle需要确定参数2021年10月21日212min| , s.t. 1iijjijijwxw xw1 arg m in | | , . .aas t x ay不同graph的邻接矩阵yale上165幅图片b: k=3 ?2021年10月21日22讲解提纲图模型稀疏表示与l1-graphl1-graph与半监督学习l1-graph与半监督辨别分析实验结论及未来工作2021年10月21日23半监督学习动机：现实

14、应用中缺少足够有标注的训练数据半监督学习：通过利用有标注数据和未标注数据间的数据分布关系来提升训练效果方法： em with generative mixture models self-training co-training transductive support vector machines, graph-based methods.2021年10月21日24基于图的半监督学习graph preserving criteria其中 ， ， 是表征样本 属于不同类的概率的向量，即 其中k是类别数， 是给定类别k时 属于此类的概率对于半监督学习， ， 是有标注样本的概率向量， 是无标注样

15、本的概率向量 对于 2021年10月21日252,min( )|ijiji je ywyy12,.,nyy yyiyixiy ( )( |),1,2,.,ikp k xkk( |)ip k xix ,luyy ylyuyi1, x belongs to the th class0, otherwise( )kiy k ly直观解释当样本 非常相似时，那么他们之间的边的权重 就比较大，通过最小化这个目标函数使得样本之间的类别概率向量 相似，即 之间的类别信息相似。相似样本属于同一类2021年10月21日26ixjxijw2,min( )|ijiji je ywyyiyjyixjx目标函数化简 其

16、中 d为 对角矩阵， 即w每行的元素和，其余元素全为0， 为w每列的元素的和。 ，其中c是对称矩阵2021年10月21日272,ttijjjji,ttijjimin( )| (y+y) y+y() () ( (ijiji jttiiijiijjiji jttiiijjjijijijijtttte ywyyywy wy ywy ywy dy dy yy y wtr ydyyd yy wwytr y) ()ttll ytr ycyiiijijdwd,tldw ldwcll推导过程的部分详解标准二次型矩阵的迹等于矩阵对角元素的和2021年10月21日28ttiiiiiiiiiiy d y(y d y

17、 )=()ttrtr ydy11112222211122212.,.,.ttttiiiinnnnitnnnny d yy d yy d yy dydydyy yyydydy半监督学习求解公式 对y求导，得到 即 可以推出： 利用这个公式就可以求出未标注样本的类别2021年10月21日29( )()te ytr ycy0yc ( )0llluluuluuccy ycc1ulluuuyyc c 讲解提纲图模型稀疏表示与l1-graphl1-graph与半监督学习l1-graph与半监督辨别分析实验结论及未来工作2021年10月21日30l1-graph+sdasda semi-supervised

18、 discriminant analysis，是一种基于图的半监督降维方法，可以同l1 graph结合起来 把在低维特征空间定义的平滑正则项（smoothness regularization term)同类内散度结合起来，通过广义特征值分解找到最优的投影方向2021年10月21日31sda：motivationlda很强大，但无法直接用于半监督学习，此时由于部分样本类别信息的缺失，不能很好的估记类内散度矩阵sda 使用有类别样本最大化不同类间的可分性，使用所有样本（有类别和无类别）估计数据间的内在结构 数据间的内在结构：总体散度矩阵，图模型2021年10月21日32rdalda目标函数：当训

19、练样本不足时，为了防止overfitting，有时会加入一个正则项，即rda（regularized discriminant analysis）2021年10月21日33argmaxargmax()argmaxtbopttawtbopttawbtbopttata s aaa s aa s aaass aa s aaa s aargmax( )tbopttata s aaa s aj arda当有部分无类别样本时，设计 使其包含数据的流形结构对于降维，近邻样本应该有近似的低维表示使用图来表征近邻样本间关系2021年10月21日34argmax( )tbopttata s aaa s aj a(

20、 )j asda定义正则项：最小化这个正则项，使得原始空间中临近的样本在映射后的低维空间中仍然相邻。目标函数： 直观解释：最大化类间散度矩阵的同时，最小化总体散度矩阵，并使得原始空间中临近的样本在映射后的低维空间中仍然相邻2021年10月21日352( )()ttijijijj aa xa xwargmax( )tbopttata s aaa s aj asda求解目标函数：d为对角矩阵，对角元素为w各行元素的和原目标函数化为：求解 可得到映射2021年10月21日362( )() 22 2() 2ttijijijttttiiiiiijjiijttttj aa xa xwa x d x aa x s x aa x dw x aa xlx aargmaxargmax( )()ttbbopttttaatta s aa s aaa s aj aasxlxa()tbts asxlxaa讲解提纲图模型稀疏表示与l1-graphl1-graph与半监督学习l1-graph与半监督辨别分析实验结论及未来工作2021年10月21日37实验6个人脸识别库 xm2vts：295人，每人4张共1180幅图片，分辨率36*32 orl： 40人每人10张共400幅图片，分辨率32*28 feret：70人，每人6张图片共420幅图片，32*32 cmu pie：