《机器学习》笔记-特征选择与稀疏学习（11）

刘才权

写在最前面

如今机器学习和深度学习如此火热，相信很多像我一样的普通程序猿或者还在大学校园中的同学，一定也想参与其中。不管是出于好奇，还是自身充电，跟上潮流，我觉得都值得试一试。对于自己，经历了一段时间的系统学习（参考《机器学习/深度学习入门资料汇总》），现在计划重新阅读《机器学习》[周志华]和《深度学习》[Goodfellow et al]这两本书，并在阅读的过程中进行记录和总结。这两本是机器学习和深度学习的入门经典。笔记中除了会对书中核心及重点内容进行记录，同时，也会增加自己的理解，包括过程中的疑问，并尽量的和实际的工程应用和现实场景进行结合，使得知识不只是停留在理论层面，而是能够更好的指导实践。记录笔记，一方面，是对自己先前学习过程的总结和补充。 另一方面，相信这个系列学习过程的记录，也能为像我一样入门机器学习和深度学习同学作为学习参考。

章节目录

• 子集搜索与评价
• 过滤式选择
• 包裹式选择
• 嵌入式选择与L1正则化
• 稀疏表示与字典学习
• 压缩感知

（一）子集搜索与评价

我们称样本属性为“特征”（feature），对当前学习任务有用的属性称为“相关特征”（relevant feature）、没什么用的属性称为“无关特征”（inrelevant feature）。从特征集合中选择相关特征子集的过程，称为“特征选择”（feature selection）。
特征选择是一个重要的“数据预处理”（data preprocessing）过程，在现实机器学习中，获得数据之后通常进行特征选择，之后再进行训练学习器。
特征选择的原因主要包括：
* 首先，我们在现实任务中经常会遇到维数灾难问题，这是由于属性过多而造成的，若能从中选择出重要的特征，使得后续学习过程仅需要在一部分特征上构建模型，则维数灾难问题会大为减轻（降维和特征选择是处理高维数据的两大主流技术）。
* 其次，去除不相关特征，只留下关键因素，往往会降低学习任务的难度。

从初始的特征集合中选取一个包含了所有重要信息的特征子集，涉及两个关键环节：
* “子集搜索”（subset search）
搜索策略包括“前向”（forward）搜索，“后向”（backward）搜索和”双向“（bidirectional）搜索；
* ”子集评价“（subset evaluation）
子集评价采用信息增益作为评价准则；

将特征子集搜索机制与子集评价机制相结合，即可得到特征选择方法。
常见的特征选择方法大致可分为三类：过滤式（filter）、包裹式（wrapper）和嵌入式（embedding）。

（二）过滤式选择

过滤式方法先对数据集进行特征选择，然后再训练学习器，特征选择过程与后续学习器无关。这相当于先用特征选择过程对初始特征进行”过滤“，再用过滤后的特征来训练模型。
其中，Relief（Relevant Feature）是一种著名的过滤式特征选择方法，该方法设计了一个”相关统计量“来度量特征的重要性。

（三）包裹式选择

与过滤式特征选择不考虑后续学习器不同，包裹式特征选择直接把最终将要使用的学习器的性能作为特征子集的评价准则。换言之，包裹式特征选择的目的就是为给定的学习器选择最有利其性能、“量身定做”的特征子集。
一般而言，由于包裹式特征选择方法直接针对给定学习器进行优化，因此从最终学习器性能来看，包裹式特征选择比过滤式特征选择更好，但另一方面，由于在特征选择过程中需多次训练学习器，因此包裹式特征选择的计算开销通常比过滤式特征选择大得多。
LVW(Las Vegs Wrapper)式一个典型的包裹式特征选择方法。

（四）嵌入式选择与L1正则化

在过滤式和包裹式特征选择方法中，特征选择过程与学习器训练过程有明确的分别；与此不同，嵌入式特征选择是将特征选择过程与学习器训练过程融为一体，两者在同一过程中完成，即在学习器训练过程中自动地进行了特征选择。
当样本特征很多，而样本数较少时，训练很容易陷入过拟合。为了缓解过拟合问题，引入正则化项。
L1范数和L2范数都有助于降低过拟合风险，但前者会带来一个额外的好处：它比后者更容易获得“稀疏(sparse)解”，即它求得的w会有更少的非零分量。

（五）稀疏表示与字典学习

把数据集D考虑成一个矩阵，其每一行对应于一个样本，每列对应与于一个特征。特征选择所考虑的问题是特征具有“稀疏性”，即矩阵中的许多列与当前学习任务无关，通过特征寻找去除这些列，则学习器训练过程仅需在较小的矩阵上进行，学习任务的难度可能有所降低，涉及的计算和存储开销会减少，学得模型的可解释性也会提高。
现在考虑另一种稀疏性：D所对应的矩阵中存在很多零元素，但这些零元素并不是以整列、整行形式存在的。
当样本具有这样的稀疏表达形式时，对学习任务来说会有不少好处。例如具有高度的稀疏性使大多数问题变得线性可分。同时，稀疏样本并不会造成存储上的巨大负担，因为稀疏矩阵已有很多高效的存储方法。
为普通稠密表达的样本找到合适的字典，将样本转化为合适的稀疏表示形式，从而使学习任务得以简化，模型复杂度得以降低，通常称为”字典学习“（dictionary learning），亦称”稀疏编码“(sparse coding)。这两个称谓稍有差别，”字典学习“更侧重于学得字典的过程，而”稀疏编码“则更侧重于对样本稀疏表达的过程。

（六）压缩感知

与特征选择、稀疏表示不同，压缩感知关注的是如何利用信号本身所具备的稀疏性，从部分观测样本中恢复原信号。通常认为，压缩感知分为”感知测量“和”重构恢复“这两个阶段。”感知测量“关注如何对原始信号进行处理以获得稀疏样本表示；”重构恢复“关注的是如何基于稀疏性从少量观测中恢复原信号，这是压缩感知的精髓，当我们谈到压缩感知时，通常是指该部分。
基于部分信息来恢复全部信息的技术在许多现实任务中有重要应用。例如网上书店通过收集读者在网上对书的评价，可根据读者的读书偏好来进行新书推荐，从而达到定向广告投放的效果。显然，没有哪位读者读过所有的书，也没有那本书被所有读者读过，因此，网上书店所搜索到的仅有部分信息，如下图所示，

那么，能够将上图中通过读者评价得到的数据当做部分信号，基于压缩感知的思想恢复出完整的信号呢？
矩阵补全（matrix completion）技术可用于解决这个问题。