2016年9月8日 2016年9月8日 2016年9月8日 1 Semi-supervised Learning by Sparse Representation Shuicheng Yan Huan Wang Lecturer: Yitao Zhai.

Presentation on theme: "2016年9月8日 2016年9月8日 2016年9月8日 1 Semi-supervised Learning by Sparse Representation Shuicheng Yan Huan Wang Lecturer: Yitao Zhai."— Presentation transcript:

1 2016年9月8日 2016年9月8日 2016年9月8日 1 Semi-supervised Learning by Sparse Representation Shuicheng Yan Huan Wang Lecturer: Yitao Zhai

2 2016-9-8 作者的相关信息 Shuicheng Yan— 第一作者 新加坡国立大学助理教授 简历 1999 和 2004 年分别从北京大学获得应用数学的学士和博士学位 分别在微软亚洲研究院， UIUC ，香港中文大学做过研究工作 研究方向 图像与视频中的行为检测 子空间学习与流形学习 物体识别与分类 生物识别 医学图像分析 论文 期刊 : 36, 会议 : 69. 个人主页 : http://www.ece.nus.edu.sg/stfpage/eleyans/http://www.ece.nus.edu.sg/stfpage/eleyans/

3 作者的相关信息 Huan Wang—— 第二作者 00-04 浙江大学 信息与电子工程学院 04-07 香港中文大学 信息工程学院 目前在耶鲁大学计算机学院 研究方向 计算机视觉，机器学习，信源编码，嵌入式系统等 发表论文 第一作者论文 5 篇 ： CVPR 08; IJCAI 07(oral); CVR07; ICML07( oral); ACM MM06 主页 http://mmlab.ie.cuhk.edu.hk/~huan/Welcome.html http://joyousprince.spaces.live.com/ 2016年9月8日 2016年9月8日 2016年9月8日 3

4 文章出处 S. Yan and H. Wang. Semi-supervised learning by sparse 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 functions. ICML, 2003. D. Cai, X. He, and J. Han. Semi-supervised discriminant analysis. ICCV, 2007. 2016年9月8日 2016年9月8日 2016年9月8日 4

5 SIAM 简介 工业和应用数学学会 (Society for Industry and Applied Mathematics,SIAM) 于二十世纪五十年代前期在美国成立，是 一个以促进应用和计算数学的研究、发展、应用为目的的协会 SIAM 以出版的高水准和颇具声誉的期刊而自豪。 SIAM 中共包 括 13 种期刊，这 13 种同行评审的研究期刊在应用和计算数学的 高等研究领域非常著名，它们涵盖了整个应用和计算数学领域 ，内容丰富而全面。根据 ISI 公司 2005 年出版的期刊引用报告 JCR ，几乎所有 SIAM 的期刊的影响因子都接近或超过 1 。 SIAM Review 获得 “ 数学 ” 领域前所未有的高影响因子 6.118 在 " 应用数学 " 领域的 162 种期刊中， SIAM 的期刊占据了前 25 位 中的 7 席 主页： http://www.siam.org/ 2016年9月8日 2016年9月8日 2016年9月8日 5

6 摘要 本文中，我们提出了一种基于 L1 Graph 的半监督学习框 架。 L1 Graph 受启发于每个样本可以通过训练数据的稀 疏线性加和进行重建。通过一个求解 L1 优化问题，可以 得到稀疏重建的系数，然后利用这些系数作为 L1 Graph 的边的权重。 传统的构造图的方法包含两个独立的步骤：确定边是否 邻接；计算边的权重。 L1 Graph 将这两个步骤合并进行 ，而且构造 L1 Graph 的过程是与参数无关的。 受启发于稀疏表示在人脸识别领域的成功应用，我们提 出了基于 L1-Graph 的半监督学习框架。在半监督人脸识 别与图像分类上的大量实验证明了我们的 L1Graph 框架的 优越性。 2016年9月8日 2016年9月8日 2016年9月8日 6

7 文章结构 Abstract Introduction Traditional Graph Construction L1-Graph ： Motivation and Construction Semi-supervised Learning over L1-Graph Experiments Conclusion and Future Work 2016年9月8日 2016年9月8日 2016年9月8日 7

8 讲解提纲 图模型 稀疏表示与 L1-Graph L1-Graph 与半监督学习 L1-Graph 与半监督辨别分析 实验 结论及未来工作 2016年9月8日 2016年9月8日 2016年9月8日 8

9 讲解提纲 图模型 稀疏表示与 L1-Graph L1-Graph 与半监督学习 L1-Graph 与半监督辨别分析 实验 结论及未来工作 2016年9月8日 2016年9月8日 2016年9月8日 9

10 图模型 训练集可以看做一个无向有权图 G={X,W} X ：顶点集，每个训练样本是图中的一个顶点 ， N 为训练样本数 W ：相似度矩阵， 表示样本 i 和样本 j 的相似度 传统的图模型构造方法分为两步： 确定两个顶点间是否存在一条边 计算边权重 2016年9月8日 2016年9月8日 2016年9月8日 10

11 Step1 ：选择边 近邻 如果两个样本点满足 ，则两个样本 间存在一条边 常常导致若干个独立的子图 K 最近邻 如果 是 的最近邻的 K 个样本之一，那么 这两个样本间存在一条边 2016年9月8日 2016年9月8日 2016年9月8日 11

12 Step2 ：计算边的权重 高斯核 欧式距离的倒数 局部线性重建系数：通过最小化 L2 重建误差，用 样本的近邻样本对其进行重建 2016年9月8日 2016年9月8日 2016年9月8日 12

13 传统图模型的缺点 选择边和计算权重分开进行 严重依赖与参数 中的 ， K 近邻中的 K 尤其是 ，很难选取一个合适的 应用于分类任务时往往效果很差 欧式距离下最近邻的样本往往并非同类样本 2016年9月8日 2016年9月8日 2016年9月8日 13

14 需要什么样的图 自适应的调整样本间关系 传统方法中，不同的数据分布就需要不同的参数 Parameter-Free 稀疏性 表征样本间局部关系的稀疏图包含对分类有用的信息 [1] 存储开销 辨别能力 更好的用于分类任务 目标：同类样本间权重较高，不同类样本间权重较低 [1]M. Belkin and P. Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 2003. 2016年9月8日 2016年9月8日 2016年9月8日 14

15 讲解提纲 图模型 稀疏表示与 L1-Graph L1-Graph 与半监督学习 L1-Graph 与半监督辨别分析 实验 结论及未来工作 2016年9月8日 2016年9月8日 2016年9月8日 15

16 2016年9月8日 2016年9月8日 2016年9月8日 稀疏表示：示例 from Subject 1 down-sample to 12x10 对应两个最大的系数 扩展 YaleB 上随机选取 1207 个样本作为基，使用最 小化 L1 范式后得到的稀疏系数。可以看出，对应 最大的两个系数都是测试样本的同类样本。

17 稀疏表示 受启发与稀疏表示在人脸识别上的成功应用 [1] 任一训练样本可以由其余训练样本的线性组合来重构 （允许一定重构误差），重构系数是稀疏的 使用重构系数做为两个样本之间的权重，表征样本间 关系 求解稀疏表示是一个最小化 L1 范式问题 是一组基， y 为待表示样本， 为重 建系数 [1] J. Wright, A. Ganesh, A. Yang, and Y. Ma: Robust face recognition via sparse representation. TPAMI, in press, 2008. 2016年9月8日 2016年9月8日 2016年9月8日 17

18 最小化 L1 范式 最小化 L1 范式问题： 特征维数远大于样本数目时，往往得不到稀疏的表示 L1 Graph 的做法：对任一样本，用除它之外的所有样本 做基求解最小化 L1 范式问题 求解方法 基追踪（ Basis pursuit ） 匹配追踪（ Matching pursuit ） 最小全变分法 迭代阈值法 2016年9月8日 2016年9月8日 2016年9月8日 18

19 L1 Graph 2016年9月8日 2016年9月8日 2016年9月8日 19

20 L1-Graph 优点 L1-Graph 是稀疏的 通过最小化 L1 范式得到的非零系数一般远小 于特征维数 L1-Graph 是自适应的 L1-Graph 中每个样本近邻的数目是通过最小化 L1 范式来确定的，不需要人工设置参数 L1-Graph 包含辨别信息 权重较大边往往连接了同类的样本 2016年9月8日 2016年9月8日 2016年9月8日 20

21 L1 VS L2 LLE 也是最小化重建误差 最小化 L1 ： 为什么不用 LLE ？ LLE 一般得不到稀疏表示 LLE 的最小化重建误差仅涉及部分样本 LLE 需要确定参数 2016年9月8日 2016年9月8日 2016年9月8日 21

22 不同 Graph 的邻接矩阵 Yale 上 165 幅图片 b: k=3 ? 2016年9月8日 2016年9月8日 2016年9月8日 22

23 讲解提纲 图模型 稀疏表示与 L1-Graph L1-Graph 与半监督学习 L1-Graph 与半监督辨别分析 实验 结论及未来工作 2016年9月8日 2016年9月8日 2016年9月8日 23

24 半监督学习 动机：现实应用中缺少足够有标注的训练数据 半监督学习：通过利用有标注数据和未标注数据间的数 据分布关系来提升训练效果 方法： EM with generative mixture models self-training co-training transductive support vector machines, graph-based methods. 2016年9月8日 2016年9月8日 2016年9月8日 24

25 基于图的半监督学习 Graph Preserving Criteria 其中 ， ， 是表征样本 属于不同类的概率 的向量，即 其中 K 是类别数， 是给定类别 k 时 属于此类的概率 对于半监督学习， ， 是有标注样本的概率向量， 是无标注样本的概率向量 对于 2016年9月8日 2016年9月8日 2016年9月8日 25

26 直观解释 当样本 非常相似时，那么他们之间的 边的权重 就比较大，通过最小化这个 目标函数使得样本之间的类别概率向量 相似，即 之间的类别信息相似。 相似样本属于同一类 2016年9月8日 2016年9月8日 2016年9月8日 26

27 目标函数化简 其中 D 为 对角矩阵， 即 W 每行的元素和，其余元素全为 0 ， 为 W 每列的元素的和。 ， 其中 C 是对称矩阵 2016年9月8日 2016年9月8日 2016年9月8日 27

28 推导过程的部分详解 标准二次型 矩阵的迹等于矩阵对角元素的和 2016年9月8日 2016年9月8日 2016年9月8日 28

29 半监督学习求解公式 对 Y 求导，得到 即 可以推出： 利用这个公式就可以求出未标注样本的类 别 2016年9月8日 2016年9月8日 2016年9月8日 29

30 讲解提纲 图模型 稀疏表示与 L1-Graph L1-Graph 与半监督学习 L1-Graph 与半监督辨别分析 实验 结论及未来工作 2016年9月8日 2016年9月8日 2016年9月8日 30

31 L1-Graph+SDA SDA Semi-supervised Discriminant Analysis ，是一种 基于图的半监督降维方法，可以同 L1 Graph 结 合起来 把在低维特征空间定义的平滑正则项（ Smoothness Regularization term) 同类内散度结 合起来，通过广义特征值分解找到最优的投影 方向 2016年9月8日 2016年9月8日 2016年9月8日 31

32 SDA ： Motivation LDA 很强大，但无法直接用于半监督学习 ，此时由于部分样本类别信息的缺失，不 能很好的估记类内散度矩阵 SDA 使用有类别样本最大化不同类间的可分性，使 用所有样本（有类别和无类别）估计数据间的 内在结构 数据间的内在结构：总体散度矩阵，图模型 2016年9月8日 2016年9月8日 2016年9月8日 32

33 RDA LDA 目标函数： 当训练样本不足时，为了防止 overfitting ，有时会加入一 个正则项，即 RDA （ Regularized Discriminant Analysis ） 2016年9月8日 2016年9月8日 2016年9月8日 33

34 RDA 当有部分无类别样本时，设计 使其包 含数据的流形结构 对于降维，近邻样本应该有近似的低维表 示 使用图来表征近邻样本间关系 2016年9月8日 2016年9月8日 2016年9月8日 34

35 SDA 定义正则项： 最小化这个正则项，使得原始空间中临近 的样本在映射后的低维空间中仍然相邻。 目标函数： 直观解释：最大化类间散度矩阵的同时， 最小化总体散度矩阵，并使得原始空间中 临近的样本在映射后的低维空间中仍然相 邻 2016年9月8日 2016年9月8日 2016年9月8日 35

36 SDA 求解 目标函数： D 为对角矩阵，对角元素为 W 各行元素的和 原目标函数化为： 求解 可得到映射 2016年9月8日 2016年9月8日 2016年9月8日 36

37 讲解提纲 图模型 稀疏表示与 L1-Graph L1-Graph 与半监督学习 L1-Graph 与半监督辨别分析 实验 结论及未来工作 2016年9月8日 2016年9月8日 2016年9月8日 37

38 实验 6 个人脸识别库 XM2VTS ： 295 人，每人 4 张共 1180 幅图片，分辨率 36*32 ORL ： 40 人每人 10 张共 400 幅图片，分辨率 32*28 FERET ： 70 人，每人 6 张图片共 420 幅图片， 32*32 CMU PIE ： 68 人，每人选 7 幅（ C27 ， C05 ， C29 ， C09 ， C07 ，及 光照变化的 8 和 11 ）， 32*32 Yale ： 15 人，每人 11 幅图片， 32*32 FRGC ： 275 人的 5628 幅图片，每人图片数从 4 到 6 不等， 32*32 物体分类的数据库 ETH-80 ： 8 类图片，每类 10 个不同的物体共 80 个，每个物体 41 幅 图片 2016年9月8日 2016年9月8日 2016年9月8日 38

39 对比图 L1-Graph LLE-Graph K=3 或 K=6 KNN-Graph K=3 或 K=6 高斯核 高斯核 2016年9月8日 2016年9月8日 2016年9月8日 39

40 实验结果 2016年9月8日 2016年9月8日 2016年9月8日 40

41 L1-Graph+SDA 2016年9月8日 2016年9月8日 2016年9月8日 41

42 图对参数的敏感性实验 FERET 上的实验 2016年9月8日 2016年9月8日 2016年9月8日 42

43 标注样本的影响 2016年9月8日 2016年9月8日 2016年9月8日 43

44 讲解提纲 图模型 稀疏表示与 L1-Graph L1-Graph 与半监督学习 L1-Graph 与半监督辨别分析 实验 结论及未来工作 2016年9月8日 2016年9月8日 2016年9月8日 44

45 结论及未来工作 我们提出了一种与参数无关的构建图的方法并将其应用 于半监督学习。 L1 Graph 受启发与每个样本可以通过训 练数据的稀疏线性加和进行重建。通过求解一个 L1 优化 问题，我们将构造图的两个步骤统一起来。在半监督人 脸识别与图像分类上的大量实验证明了 L1-Graph 的优越 性 L1 Graph 为我们进行数据降维的研究开启了一个新方向 ，未来工作包括 基于 L1 Graph 的无监督图像聚类 基于 L1 Graph 的半监督回归 利用 L1 Graph 与图嵌入的框架进行数据降维 2016年9月8日 2016年9月8日 2016年9月8日 45