《机器学习》-- 第十一章 特征选择与稀疏学习
正文共：4811字 预计阅读时间：6 分钟
前文推送
本文目录：
- 11.1 子集搜索与评价
- 11.2 过滤式
- 11.3 包裹式
- 11.4 嵌入式
- 11.5 稀疏表示
- 11.6 压缩感知
第十一章 特征选择与稀疏学习
对于数据集中的一个对象及组成对象的零件元素：
统计学家常称它们为观测（observation）和变量（variable）；数据库分析师则称其为记录（record）和字段（field）；数据挖掘/机器学习学科的研究者则习惯把它们叫做样本/示例（example/instance）和属性/特征（attribute/feature）。
在机器学习中特征选择是一个重要的“数据预处理”（data preprocessing）过程，即试图从数据集的所有特征中挑选出与当前学习任务相关的特征子集，再利用数据子集来训练学习器；稀疏学习则是围绕着稀疏矩阵的优良性质，来完成相应的学习任务。
11.1 子集搜索与评价
在机器学习中，我们将属性称为“特征”( feature), 对当前学习任务有用的属性称为“相关特征”( relevant feature)、没什么用的属性称为“无关特征”(irrelevant feature), 从给定的特征集合中选择出相关特征子集的过程, 称为“特征选择”(feature selection)。
特征选择是一个重要的“数据预处理”( data preprocessing)过程, 在现实机器学习任务中,获得数据之后通常先进行特征选择, 此后再训练学习器。
进行特征选择有两个很重要的原因: 首先,我们在现实任务中经常会遇到维数灾难问题，若能从特征中选择出重要的特征, 使得后续学习过程仅需在一部分特征上构建模型, 则维数灾难问题会大为减轻；其二, 去除不相关特征往往会降低学习任务的难度。
需注意的是, 特征选择过程必须确保不丢失重要特征,否则后续学习过程会因为重要信息的缺失而无法获得好的性能。给定数据集, 若学习任务不同, 则相关特征很可能不同, 因此, 特征选择中所谓的“无关特征”是指与当前学习任务无关。有一类特征称为“冗余特征”( redundant feature), 它们所包含的信息能从其他特征中推演出来。例如,考虑立方体对象,若已有特征“底面长”，“底面宽”,则“底面积”是冗余特征,因为它能从“底面长”与“底面宽”得到。冗余特征在很多时候不起作用, 去除它们会减轻学习过程的负担。但有时冗余特征会降低学习任务的难度，例如若学习目标是估算立方体的体积,则“底面积”这个冗余特征的存在将使得体积的估算更容易; 更确切地说,若某个冗余特征恰好对应了完成学习任务所需的“中间概念”,则该冗余特征是有意义的。
简言之，特征选择直接剔除那些与学习任务无关的属性而选择出最佳特征子集。
最佳特征子集的选择涉及到两个关键环节：1.如何生成候选子集（子集搜索，subset search）；2.如何评价候选子集的好坏。
子集搜索分为三种贪心策略：
前向(forward)搜索：初始将每个特征当做一个候选特征子集，然后从当前所有的候选子集中选择出最佳的特征子集；接着在上一轮选出的特征子集中添加一个新的特征，同样地选出最佳特征子集；直至选不出比上一轮更好的特征子集。后向(backward)搜索：初始将所有特征作为一个候选特征子集；接着尝试去掉上一轮特征子集中的一个特征并选出当前最优的特征子集；直到最后选不出比上一轮更好的特征子集。双向(bidireactional)搜索：将前向搜索与后向搜索结合起来，即在每一轮中既有添加操作也有剔除操作。
特征子集的评价，书中给出了一些想法及基于信息熵的方法。信息熵仅是判断候选子集优劣的一种途径, 其他能判断的机制都能用于特征子集评价。
btw，若将前向搜索策略与信息增益结合在一起，与决策树十分相似，树节点划分属性组成的集合便是选择出的特征子集。
常见的特征选择方法大致可分为三类: 过滤式(filter)、包裹式(wrapper)和嵌入式(embedding)
11.2 过滤式选择
过滤式方法是一种将特征选择与学习器训练相分离的特征选择技术，首先将相关特征挑选出来，再使用选择出的数据子集来训练学习器。
Relief 是其中著名的代表性算法，它使用一个“相关统计量”来度量特征的重要性，该统计量是一个向量，其中每个分量分别对应于一个初始特征，特征子集的重要性由子集中每个特征所对应的相关统计量分量之和来决定。只需指定一个阈值
，然后选择比大的相关统计量分量所对应的特征即可;也可指定欲选取的特征个数
，然后选择相关统计量分量最大的
个特征。
Relief算法的核心在于如何计算出该相关统计量。对于数据集中的每个样例
，Relief首先找出与
同类别的最近邻
与不同类别的最近邻
，分别称为猜中近邻（near-hit）与猜错近邻（near-miss），接着便可以分别计算出相关统计量中的每个分量。对于特征
分量：
直观上理解：对于猜中近邻，两者
属性的距离越小越好，对于猜错近邻，
属性距离越大越好。其中
表示样本
在属性
上的取值，
取决于属性
的类型: 若
为离散属性，diff取海明距离 ,即相同取0，不同取1；若
为连续属性，则diff为曼哈顿距离，
,即取差的绝对值。分别计算每个分量，最终取平均便得到了整个相关统计量。
Relief 只需在数据集的采样上而不必在整个数据集上估计相关统计量，时间开销随采样次数以及原始特征数线性增长，是一个运行效率很高的过滤式特征选择算法。
Relief算法只适用于二分类问题，变体 Relief-F 则解决了多分类问题。两者的区别在于猜错近邻的个数，Relief-F 在第
类之外的 每个类 中找到一个
的最近邻示例作为猜错近邻，记为
其中
表示第
类样本在数据集中所占的比例。
11.3 包裹式选择
包裹式选择将学习器性能评价指标作为特征选择的评价准则，因此包裹式选择可以看作是为某种学习器量身定做的特征选择方法，由于在每一轮迭代中，包裹式选择都需要训练学习器，在获得较好性能的同时也产生了较大的开销。
一种经典的包裹式特征选择方法 Las Vegas Wrapper (LVW)，它在拉斯维加斯方法(Las Vegas method)框架下使用随机策略来进行特征子集的搜索。
蒙特卡罗算法：采样越多(时间限制)，越近似最优解，一定会给出解，但给出的解不一定是正确解；拉斯维加斯算法：采样越多(时间限制)，越有机会找到最优解，不一定会给出解，但给出的解一定是正确解。
LVW算法流程：
LVW.png
LVW 特征子集搜索采用随机策略，每次特征子集评价都需训练学习器，计算开销很大，因此设置了停止条件控制参数
11.4 嵌入式选择与正则化
过滤式中特征选择与后续学习器完全分离，包裹式则是使用学习器作为特征选择的评价准则；嵌入式是一种将特征选择与学习器训练完全融合的特征选择方法，即将特征选择融入学习器的优化过程中。
在之前《经验风险与结构风险》中已经提到：经验风险指的是模型与训练数据的契合度，结构风险则是模型的复杂程度，机器学习的核心任务就是：在模型简单的基础上保证模型的契合度。例如：岭回归就是加上了L2范数的最小二乘法，有效地解决了奇异矩阵、过拟合等诸多问题，下面的嵌入式特征选择则是在损失函数后加上了L1范数。
L1范数又名 Lasso Regularization，指的是向量中每个元素的绝对值之和，这样在优化目标函数的过程中，就会使得w尽可能地小，在一定程度上起到了防止过拟合的作用，同时与L2范数（Ridge Regularization ）不同的是，L1范数会使得部分w变为0， 从而达到了特征选择的效果。
总的来说：L1范数会趋向产生少量的特征，其他特征的权值都是0；L2会选择更多的特征，这些特征的权值都会接近于0。这样L1范数在特征选择上就十分有用，而L2范数则具备较强的控制过拟合能力。可以从下面两个方面来理解：
（1）下降速度：L1范数按照绝对值函数来下降，L2范数按照二次函数来下降。因此在0附近，L1范数的下降速度大于L2范数，故L1范数能很快地下降到0，而L2范数在0附近的下降速度非常慢，因此较大可能收敛在0的附近。
6.png
（2）空间限制：L1范数与L2范数都试图在最小化损失函数的同时，让权值W也尽可能地小。我们可以将原优化问题看做为下面的问题，即让后面的规则则都小于某个阈值。从图中可以看出：L1范数相比L2范数更容易得到稀疏解
7.png
L_norm.png
11.5 稀疏表示与字典学习
当样本数据是一个稀疏矩阵时，对学习任务来说会有不少的好处，例如很多问题变得线性可分，储存更为高效等。这便是稀疏表示与字典学习的基本出发点。
稀疏矩阵即矩阵的每一行/列中都包含了大量的零元素，且这些零元素没有出现在同一行/列（特征选择则考虑的是去除全为零的特征列），对于一个给定的稠密矩阵，若我们能通过某种方法找到其合适的稀疏表示(sparse representation)，则可以使得学习任务更加简单高效，我们称之为稀疏编码（sparse coding）或字典学习（dictionary learning）。
例如在文档分类任务中,通常将每个文档看作一个样本,每个字(词)作为一个特征,字(词)在文档中出现的频率或次数作为特征的取值;换言之，数据集
所对应的矩阵的每行是一个文档,每列是一个字(词),行、列交汇处就是某字(词)在某文档中出现的频率或次数。那么,这个矩阵有多少列呢?以汉语为例,《康熙字典》中有47035个汉字,这意味着该矩阵可有4万多列, 即便仅考虑《现代汉语常用字表》中的汉字,该矩阵也有3500列。然而,给定一个文档,相当多的字是不出现在这个文档中的,于是矩阵的每一行都有大量的零元素;对不同的文档,零元素出现的列往往很不相同。
假如使用《现代汉语常用字表》，相对《康熙字典》，更能使学习任务变得简单。
显然, 在一般的学习任务中(例如图像分类)并没有《现代汉语常用字表》可用，于是我们需学习出这样一个“字典”，即字典学习，为普通稠密表达的样本找到合适的字典，将样本转化为合适的稀疏表达形式，从而简化学习任务。
给定一个数据集，字典学习/稀疏编码 最简单形式如下式：
dictionary_learning
最终的目标就是求得字典矩阵B 及稀疏表示α，书中使用变量交替优化的策略 求解。
11.6 压缩感知
压缩感知(compressed sensing)与特征选择、稀疏表达不同的是：它关注的是通过欠采样信息来恢复全部信息，即根据部分信息（利用其稀疏性）来恢复全部信息。
通常认为，压缩感知分为“感知测量“，”重构恢复”这两个阶段。“感知测量”关注如何对原始信号进行处理以获得稀疏样本表示,这方面的内容涉及傅里叶变换、小波变换以及字典学习、稀疏编码等,不少技术在压缩感知提出之前就已在信号处理等领域有很多研究；“重构恢复”关注的是如何基于稀疏性从少量观测中恢复原信号, 这是压缩感知的精髓,当我们谈到压缩感知时,通常是指该部分。
形象易懂讲解压缩感知
一个应用方向案例：
网上书店通过收集读者在网上对书的评价，可根据读者的读书偏好来进行新书推荐（典型的“协同过滤”(collaborative filtering 任务），从而达到定向广告投放的效果。显然，没有哪位读者读过所有的书，也没有哪本书被所有读者读过。因此，网上书店所搜集到的仅有部分信息。例如表11-1 给出了四位读者的网上评价信息，这里评价信息经过处理，形成了“喜好程度”评分(5分最高)。由于读者仅对读过的书给出评价，因此表中出现了很多未知项“?”
image-20210223105200298
一般情形下，读者对书籍的评价取决于题材、作者、装帧等多种因素，为简化讨论，假定读者喜好评分仅与题材有关.《笑傲江湖》和《云海玉弓缘》是武侠小说，《万历十五年》和《人类的故事》是历史读物，《人间词话》属于诗词文学。一般来说，相似题材的书籍会有相似的读者，若能将书籍按题材归类，则题材总数必然远远少于书籍总数，因此从题材的角度来看，表中反映出的信号应该是稀疏的。于是， 应能通过类似压缩感知的思想加以处理。矩阵补全( matrix completion)技术（亦称“低秩矩阵恢复”）可用于解决这个问题。
11.7 阅读材料
在具体的学习与优化求解方面，不同的度量学习方法往往采用了不同的技术，例如 [Yang et al. ,2006][^11.1] 将度量学习转化为判别式概率模型框架下基于样本对的二分类问题求解, [ Davis et al.,2007][^11.2] 将度量学习转化为信息论框架下的 Bregman优化问题,能方便地进行在线学习
[^11.1]: Yang, L, R Jin, R. Sukthankar, and Y. Liu(2006). "An efficient algorithmfor local distance metric learning. In Proceedings of the 21st National Con-ference on Artificial Intelligence(AAAI), 543-548, Boston, MA
[^11.2]: Davis, J. V, B. Kulis, P. Jain, S Sra, and I.S. Dhillon(2007)."Informationtheoretic metric learning. 'In Proceedings of the 24th International Confer-ence on Machine Learning(ICML), 209-216, Corvalis, OR
本文项目地址：
https://github.com/firewang/lingweilingyu/blob/master/contents/Machine_Learning_Zhi-Hua_Zhou.md
(喜欢的话，Star一下)
参考网址：
- 周志华 著. 机器学习, 北京: 清华大学出版社, 2016年1月.
- https://github.com/Vay-keen/Machine-learning-learning-notes