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

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

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

文章出处 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, X. Zhu, Z. Ghahramani, and J. Lafferty. Semi-supervised learning using Gaussian fields and harmonic functions. ICML, D. Cai, X. He, and J. Han. Semi-supervised discriminant analysis. ICCV, 年9月8日 2016年9月8日 2016年9月8日 4

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

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

文章结构 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

半监督学习 动机：现实应用中缺少足够有标注的训练数据 半监督学习：通过利用有标注数据和未标注数据间的数 据分布关系来提升训练效果 方法： 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

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

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

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

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

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

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

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

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

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

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

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

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

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

实验 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

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

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

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

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

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

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

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