特征选择与稀疏学习

在机器学习中特征选择是一个重要的“数据预处理”(data preprocessing)过程,即试图从数据集的所有特征中挑选出与当前学习任务相关的特征子集,接着再利用数据子集来训练学习器;稀疏学习则是围绕着稀疏矩阵的优良性质,来完成相应的学习任务。
展开查看详情

1.徐淼

2.第十一 章 :特征选择与稀疏学习

3.特征 特征 描述物体的 属性 特征的 分类 相关特征 : 对 当前学习任务 有用的 属性 无关特征 : 与 当前学习任务 无关的 属性 冗余 特征* : 其所包含信息能由其他特征 推演出来 * 为简化讨论,本章 暂不 涉及冗余 特征

4.例子:西瓜的特征 西瓜的 特征 颜色 纹理 触感 根 蒂 声音 相关 特征 无关特征 好 瓜 坏 瓜 当前任务 :西瓜是否是好瓜

5.特征选择 特征选择 从给定的特征集合中选出 任务相关 特征 子集 必须确保不丢失重要特征 原因 减轻维度灾难:在少量属性上构建 模型 降低学习难度:留下关键信息

6.例子 :判断是否好瓜时的特征选择 西瓜的 特征 颜色 纹理 触感 根 蒂 声音 相关 特征 无关特征 好 瓜 坏 瓜 当前任务 :西瓜是否是好瓜 特征选择:选择当前任务相关特征

7.特征选择的一般方法 遍历所有可能的子集 计算上遭遇组合爆炸, 不可行 可行方法 两个关键环节:子集搜索和子集评价

8.子集 搜索 前向搜索:逐渐增加相关特征 后向搜索:从完整的特征集合开始,逐渐减少特征 双向搜索:每一轮逐渐增加相关特征,同时减少无关特征 用贪心策略选择包含重要信息的特征子集

9.特征集合 最优子 集   特征集合 - { }   最优子集 + { }   从特征集合中选出最优特征   当前 最优 子集优于 上一轮最优 子集? Y N 前向搜索 最优子集初始为空集,特征集合初始时包括所有给定特征 结束

10.子集 评价 特征子集确定了对数据集的一个划分 每个划分区域对应着特征 子集 的某种取值 样本标记对应着对 数据 集的真实划分 通过估算这两个划分的差异,就能对 特征 子集进行评价;与样本标记对应的划分的差异越小,则说明当前特征子集越好

11.用信息熵进行子集 评价 特征子集 确定了对数据集 的一个划分 上的取值将 数据 集 分为 份 ,每一份用 表示 表示 上的信息熵 样本标记 对应着对 数据 集 的真实划分 表示 上的 信息熵   特征子集 的信息增益为:   上的信息熵定义为 第 类样本所占比例为  

12.常见的特征选择方法 常见的特征选择方法大致分为如下三类: 过滤式 包裹式 嵌入式 将特征子集搜索机制与子集评价机制相结合,即可得到特征选择方法

13.过滤式选择 Relief (Relevant Features) 方法 [Kira and Rendell, 1992 ] 为 每个初始特征 赋予一个 “ 相关统计量 ”,度量特征的重要性 特征子集的重要性由子集中每个特征所对应的相关统计量之和决定 设计一个阈值,然后选择比阈值大的相关统计量分量所对应的特征 或者指定欲选取的特征个数,然后选择相关统计量分量最大的指定个数特征 如何确定相关统计量? 先用特征选择 过程过滤原始数据, 再用过滤后的特征来训练模型 ;特征选择 过程与后续学习器 无关

14.Relief 方法中相关统计量的确定 猜中近邻( near-hit ): 的同类样本中的最近邻 猜错近邻( near-miss ) : 的 异 类 样本中的最近邻 相关统计量对应于属性 的分量为 相关统计量越大, 属性 上 ,猜对近邻比猜错近邻越近,即 属性 对 区分对错越 有用 Relief 方法的时间开销随采样次数以及原始特征数线性增长,运行效率很高   若 为离散型,则 时 ,否则为 ;若 为连续型, 则 ,注意 已规范化到 区间  

15.Relief 方法的多类拓展 数据集中的样本来自 个类别,其中 属于第 类 猜中近邻:第 类中 的最近邻 猜错近邻:第 类之外的每个类中找到一个 的最近邻作为猜错近邻,记为 相关统计量对应于属性的分量为   Relief 方法是为二分类问题设计的,其扩展变体 Relief-F [ Kononenko , 1994] 能处理多分类问题 为第 类样本在数据集 中所占的比例  

16.包裹式选择 包裹式特征选择的目的就是为给定学习器选择最有利于其性能、“量身定做”的特征 子集 包裹式选择方法直接针对给定学习器进行优化,因此从最终学习器性能来看,包裹式特征选择比过滤式特征选择更好 包裹式特征选择过程中需多次训练学习器,计算开销通常比过滤式特征选择大得多 包裹式选择直接把最终将要使用的学习器的性能作为特征子集的评价准则

17.LVW 包裹式特征选择方法 基本步骤 在循环的每一轮随机产生一个特征子集 在随机产生 的特征子集上通过交叉验证推断当前特征子集的 误差 进行多次循环,在多个随机产生的特征子集中选择误差最小的特征子集作为最终解 * * 若有运行时间限制,则该算法有可能给不出解 LVW ( Las Vegas Wrapper ) [Liu and Setiono , 1996] 在拉斯维加斯方法框架下使用随机策略来进行子集搜索,并以最终分类器的误差作为特征子集评价 准则

18.嵌入式选择 考虑最简单的线性回归模型,以平方误差为损失函数,并引入 范数正则化项防止过拟合,则有 将 范数替换为 范数,则有 LASSO [Tibshirani, 1996]   嵌入式特征选择是将特征选择过程与学习器训练过程融为一体,两者在同一个优化过程中完成,在学习器训练过程中自动地进行特征选择 岭回归 (ridge regression) [Tikhonov and Arsenin , 1977] 易获得稀疏解,是一种嵌入式特征选择方法

19.使用 范数正则化易获得稀疏解   假设 仅有两个属性, 那么 有两个分量 . 那么目标优化的解要在平方误差项与正则化项之间折中 , 即出现在图中平方误差项等值线与正则化等值线相交处 . 从图中看出 , 采用 范数时交点常出现在坐标轴上 , 即产生 为 0 的稀疏解 .   等值线即取值相同的点的连线

20.正则化问题的求解 (1)   写出 的二阶泰勒展式 假设 满足 L-Lipschitz 条件, 即存在常数 使得   近端梯度下降( Proximal Gradient Descend ,简称 PGD )解法 [ Boyd and Vandenberghe , 2004]

21.L1 正则化问题的求解 (2) L-Lipschitz 条件代入泰勒展式,可 得 将上式关于 的近似代入到原优化问题中,得  

22.L1 正则化问题的求解 (3) 每次在 的 附近寻找最优点,不断迭代, 即寻找 假设 ,上式有闭式解  

23.稀疏表示 将数据集考虑成一个矩阵,每行对应一个样本,每列对应一个特征 矩阵中有很多零元素,且非整行整列出现 稀疏表达的 优势 : 文本数据线性可 分 存储高效 能否 将稠密表示的数据集转化为“稀疏表示”,使其享受稀疏表达的 优势 ?

24.字典学习 给定数据 集 学习目标是字典矩阵 以及样本的稀疏表示 称为字典的词汇量,通常由用户指定 则最简单的字典学习的优化形式为   为普通稠密表达的样本找到合适的 字典 ,将样本转化为稀疏表示,这一过程称为 字典学习

25.字典学习的解法 (1) 固定字典 ,参考 LASSO 的方法求解 以 为初值求解字典 基于逐列更新策略的 KSVD [ Aharon et al., 2006]   是矩阵的 Frobenius 范数 表示矩阵 的第 列, 表示矩阵 的第 行  

26.字典学习的解法 (2) 上式可以变化为 对 进行奇异值分解,取得最大奇异值对应的正交向量 反复迭代以获得最优解   为了 不 破坏 的 稀疏 性, 仅保留非 零 元素, 仅保留 与 非零元素的乘积项

27.压缩感知 数据传输中,能否利用接收到的压缩、丢包后的数字信号,精确重构出原信号? 压缩 感知 (compressive sensing ) [ Cándes et al., 2006, Donoho , 2006] 为解决 此类 问题提供了新的思路 . 能否利用部分数据恢复全部数据?

28.长度为 的离散信号 ,用远小于奈奎斯特采样定理的要求的采样率采样得到长度为 的采样后信号 , ,即 一般情况下, , 不能 利用 还原 , 但是 若存在某个线性变换 ,使得 , 是 稀疏向量 ,即   具有 “限定等距性” 时,可以近乎完美地恢复   如傅里叶变换,余弦变换,小波变换等

29.限定等距 性 限定等距 性 ( Restricted Isometry Property , 即 RIP ) [ Cándes , 2008] : ,若 存在常数 使得对于任意向量 和 的所有子矩阵 有 则称 满足 - 限 定 等距 性 ( -RIP )