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

1、2022年8月20日1Semi-supervised Learning by Sparse RepresentationShuicheng Yan Huan WangLecturer: Yitao Zhai2022/8/20作者的相关信息Shuicheng Yan第一作者新加坡国立大学助理教授简历2019和2019年分别从北京大学获得应用数学的学士和博士学位分别在微软亚洲研究院，UIUC，香港中文大学做过研究工作研究方向图像与视频中的行为检测子空间学习与流形学习物体识别与分类生物识别医学图像分析论文期刊: 36, 会议: 69.个人主页: .sg/stfpage/eley

2、ans/作者的相关信息Huan Wang第二作者00-04 浙江大学 信息与电子工程学院04-07 香港中文大学 信息工程学院目前在耶鲁大学计算机学院研究方向计算机视觉，机器学习，信源编码，嵌入式系统等发表论文第一作者论文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).相关文献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 简介工业和应用数学学会 (Society for Industry and Applied Mathematics ,SIAM) 于二十世纪五十年代前期在美国成立，是一个以促进应用和计算数学的研究、发展、应用为目的的协会SIAM以出版的高水准和颇具声誉的期刊而自豪。SIAM中共包括13种期刊，这13种同行评审的研究期刊在应用和计算数学的高等研究领域非常著名，它们涵盖了整个应用和计算数

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

6、计算边的权重。L1 Graph将这两个步骤合并进行，而且构造L1 Graph的过程是与参数无关的。受启发于稀疏表示在人脸识别领域的成功应用，我们提出了基于L1-Graph的半监督学习框架。在半监督人脸识别与图像分类上的大量实验证明了我们的L1Graph框架的优越性。2022年8月20日6文章结构AbstractIntroductionTraditional Graph ConstructionL1-Graph：Motivation and ConstructionSemi-supervised Learning over L1-GraphExperimentsConclusion and Fu

7、ture Work2022年8月20日7讲解提纲图模型稀疏表示与L1-GraphL1-Graph与半监督学习L1-Graph与半监督辨别分析实验结论及未来工作2022年8月20日8讲解提纲图模型稀疏表示与L1-GraphL1-Graph与半监督学习L1-Graph与半监督辨别分析实验结论及未来工作2022年8月20日9图模型训练集可以看做一个无向有权图G=X,WX：顶点集，每个训练样本是图中的一个顶点 ，N为训练样本数W：相似度矩阵， 表示样本i和样本j的相似度传统的图模型构造方法分为两步：确定两个顶点间是否存在一条边计算边权重 2022年8月20日10Step1：选择边 近邻如果两个样本点满

8、足 ，则两个样本间存在一条边常常导致若干个独立的子图K最近邻如果 是 的最近邻的K个样本之一，那么这两个样本间存在一条边2022年8月20日11Step2：计算边的权重高斯核欧式距离的倒数局部线性重建系数：通过最小化L2重建误差，用样本的近邻样本对其进行重建2022年8月20日12传统图模型的缺点选择边和计算权重分开进行严重依赖与参数 中的 ，K近邻中的K尤其是 ，很难选取一个合适的应用于分类任务时往往效果很差欧式距离下最近邻的样本往往并非同类样本2022年8月20日13需要什么样的图自适应的调整样本间关系传统方法中，不同的数据分布就需要不同的参数Parameter-Free稀疏性表征样本间局

9、部关系的稀疏图包含对分类有用的信息1存储开销辨别能力更好的用于分类任务目标：同类样本间权重较高，不同类样本间权重较低1M. Belkin and P. Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 2019.2022年8月20日14讲解提纲图模型稀疏表示与L1-GraphL1-Graph与半监督学习L1-Graph与半监督辨别分析实验结论及未来工作2022年8月20日152022年8月20日稀疏表示：示例fromSubject 1down

10、-sampleto 12x10对应两个最大的系数扩展YaleB上随机选取1207个样本作为基，使用最小化L1范式后得到的稀疏系数。可以看出，对应最大的两个系数都是测试样本的同类样本。稀疏表示受启发与稀疏表示在人脸识别上的成功应用1任一训练样本可以由其余训练样本的线性组合来重构（允许一定重构误差），重构系数是稀疏的使用重构系数做为两个样本之间的权重，表征样本间关系求解稀疏表示是一个最小化L1范式问题 是一组基，y为待表示样本， 为重建系数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范式问题：特征维数远大于样本数目时，往往得不到稀疏的表示 L1 Graph的做法：对任一样本，用除它之外的所有样本做基求解最小化L1范式问题求解方法基追踪（Basis pursuit）匹配追踪（Matching pursuit）最小全变分法迭代阈值法2022年8月20日18L1 Graph2022年8月20日19L1-Graph优点L1-Graph 是稀疏的通过最小化L1范式得到的非零系数一般远小于特征维数L1-Graph是自适应的L1-Graph中每个样本近邻的数目是通过

12、最小化L1范式来确定的，不需要人工设置参数L1-Graph包含辨别信息权重较大边往往连接了同类的样本2022年8月20日20L1 VS L2LLE也是最小化重建误差最小化L1： 为什么不用LLE？LLE一般得不到稀疏表示LLE的最小化重建误差仅涉及部分样本LLE需要确定参数2022年8月20日21不同Graph的邻接矩阵Yale上165幅图片b: k=3 ?2022年8月20日22讲解提纲图模型稀疏表示与L1-GraphL1-Graph与半监督学习L1-Graph与半监督辨别分析实验结论及未来工作2022年8月20日23半监督学习动机：现实应用中缺少足够有标注的训练数据半监督学习：通过利用有标

13、注数据和未标注数据间的数据分布关系来提升训练效果方法：EM with generative mixture models self-training co-trainingtransductive support vector machines,graph-based methods.2022年8月20日24基于图的半监督学习Graph Preserving Criteria其中 ， ， 是表征样本 属于不同类的概率的向量，即 其中K是类别数， 是给定类别k时 属于此类的概率对于半监督学习， ， 是有标注样本的概率向量， 是无标注样本的概率向量对于 2022年8月20日25直观解释当样本 非常

14、相似时，那么他们之间的边的权重 就比较大，通过最小化这个目标函数使得样本之间的类别概率向量 相似，即 之间的类别信息相似。相似样本属于同一类2022年8月20日26目标函数化简 其中 D为 对角矩阵， 即W每行的元素和，其余元素全为0， 为W每列的元素的和。 ，其中C是对称矩阵2022年8月20日27推导过程的部分详解标准二次型矩阵的迹等于矩阵对角元素的和2022年8月20日28半监督学习求解公式 对Y求导，得到 即 可以推出： 利用这个公式就可以求出未标注样本的类别2022年8月20日29讲解提纲图模型稀疏表示与L1-GraphL1-Graph与半监督学习L1-Graph与半监督辨别分析实验

15、结论及未来工作2022年8月20日30L1-Graph+SDASDASemi-supervised Discriminant Analysis，是一种基于图的半监督降维方法，可以同L1 Graph结合起来把在低维特征空间定义的平滑正则项（Smoothness Regularization term)同类内散度结合起来，通过广义特征值分解找到最优的投影方向2022年8月20日31SDA：MotivationLDA很强大，但无法直接用于半监督学习，此时由于部分样本类别信息的缺失，不能很好的估记类内散度矩阵SDA使用有类别样本最大化不同类间的可分性，使用所有样本（有类别和无类别）估计数据间的内在结构

16、数据间的内在结构：总体散度矩阵，图模型2022年8月20日32RDALDA目标函数：当训练样本不足时，为了防止overfitting，有时会加入一个正则项，即RDA（Regularized Discriminant Analysis）2022年8月20日33RDA当有部分无类别样本时，设计 使其包含数据的流形结构对于降维，近邻样本应该有近似的低维表示使用图来表征近邻样本间关系2022年8月20日34SDA定义正则项：最小化这个正则项，使得原始空间中临近的样本在映射后的低维空间中仍然相邻。目标函数： 直观解释：最大化类间散度矩阵的同时，最小化总体散度矩阵，并使得原始空间中临近的样本在映射后的低维

17、空间中仍然相邻2022年8月20日35SDA求解目标函数：D为对角矩阵，对角元素为W各行元素的和原目标函数化为：求解 可得到映射2022年8月20日36讲解提纲图模型稀疏表示与L1-GraphL1-Graph与半监督学习L1-Graph与半监督辨别分析实验结论及未来工作2022年8月20日37实验6个人脸识别库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幅图片，每人图片数从4到6不等，32*32物体分类的数据库ETH-80：8类图片，每类10个不同的物体共80个，每个物体41幅图片2022年8月20日38对比图L1-GraphLLE-GraphK=3或K=6KNN-Graph K=3或K=6高斯核 高斯核2022年8月20日39实验结果2022年8月20日40L1-Graph+SDA2022年8月20日41图对参数的敏感性实验FERET上的实验2022年8月20日42标注样本的影响2022年8月20日43讲解提纲图模型稀疏表示与L1-GraphL1-Graph与