特征选择与稀疏学习
原理
11.1 子集搜索与评价
- 对一个学习任务来说，给定属性集，其中有些属性可能很关键、很有用，另一些属性则可能没什么用。我们将属性称为“特征”(feature)，对当前学习任务有用的属性称为“相关特征”(relevant feature)、没什么用的属性称为“无关特征”(irrelevant feature)、从给定的特征集合中选择出相关特征子集的过程，称为“特征选择”(feature selection)。
- 特征选择是一个重要的“数据预处理”(data preprocessing)过程，在现实机器学习任务中，获得数据之后通常先进行特征选择，此后再训练学习器，那么，为什么要进行特征选择呢？
- 首先，我们在现实任务中经常会遇到维数灾难问题，这是由于属性过多而造成的，若能从中选择出重要的特征，使得后续学习过程仅需在一部分特征上构建模型，则维数灾难问题会大为减轻。从这个意义上说，特征选择与降维有着相似的动机；事实上，它们是处理高维数据的两大主流技术。
- 第二个原因是，去除不相关特征往往会降低学习任务的难度，这就像侦探破案一样，若将纷繁复杂的因素抽丝剥茧，只留下关键因素，则真相往往更易看清。
- 需注意的是，特征选择过程必须确保不丢失重要特征，否则后续学习过程会因为重要信息的缺失而无法获得好的性能。给定数据集，若学习任务不同，则相关特征很可能不同。因此，特征选择中所谓的“无关特征”是指与当前学习任务无关。有一类特征称为“冗余特征”(redundant feature)，它们所包含的信息能从其他特征中推演出来。冗余特征在很多时候不起作用，去除它们会减轻学习过程的负担。但有时冗余特征会降低学习任务的难度，更确切地说，若某个冗余特征恰好对应了完成学习任务所需的“中间概念”，则该冗余特征是有益的。
- 欲从初始的特征集合中选取一个包含了所有重要信息的特征子集，若没有任何领域知识作为先验假设，那就只好遍历所有可能的子集了；然而这在计算上却是不可行的，因为这样做会遭遇组合爆炸，特征个数稍多就无法进行。可行的做法是产生一个“候选子集”，评价出它的好坏，基于评价结果产生下一个候选子集，再对其进行评价，……这个过程持续进行下去，直到无法找到更好的候选子集为止。显然，这里涉及两个关键环节：如何根据评价结果获取下一个候选特征子集？如何评价候选特征子集的好坏？
- 第一个环节是“子集搜索”(subset search)问题。给定特征集合 {a1, a2, .., ad}，我们可将每个特征看作一个候选子集，对这 d 个候选单特征子集进行评价，假定 {a2} 最优，于是将 {a2} 作为第一轮的选定集；然后，在上一轮的选定集中加入一个特征，够成包含两个特征的候选子集，假定在这 d -1 个候选两特征子集中 {a2, a4} 最优，且优于 {a2}，于是将 {a2, a4} 作为本轮的选定集；……假定在第 k + 1 轮时，最优的候选 (k + 1) 特征子集不如上一轮的选定集，则停止生成候选子集，并将上一轮选定的 k 特征集合作为特征选择结果。这样逐渐增加相关特征的策略称为“前向”(forward)搜索。类似的，若我们从完整的特征集合开始，每次尝试去掉一个无关特征，这样逐渐减少特征的策略称为“后向”(backward)搜索。还可将前向与后向搜索结合起来，每一轮逐渐增加选定相关特征(这些特征在后续轮中将确定不会被去除)、同时减少无关特征，这样的策略称为“双向”(bidirectional)搜索。显然，上述策略都是贪心的，未必能得到最优解。
- 第二个环节是“子集评价”(subset evaluation)问题。信息增益 Gain(A)越大，意味着特征子集 A 包含的有助于分类的信息越多。于是，对于每个候选特征子集，我们可基于训练集 D 来计算其信息增益，以此作为评价准则。
- 将特征子集搜索机制与子集评价机制相结合，即可得到特征选择方法。例如将前向搜索与信息熵相结合，这显然与决策树算法非常相似。事实上，决策树可用于特征选择，树结点的划分属性所组成的集合就是选择出的特征子集。
- 常见的特征选择方法大致可分为三类：过滤式(filter)、包裹式(wrapper)和嵌入式(embedding)。
11.2 过滤式
- 过滤式方法先对数据集进行特征选择，然后再训练学习器，特征选择过程与后续学习器无关。这相当于先用特征选择过程对初始特征进行“过滤”，再用过滤后的特征来训练模型。
- Relief (Relevant Features) 是一种著名的过滤式特征选择方法，该方法设计了一个“相关统计量”来度量特征的重要性。该统计量是一个向量，其每个分量分别对应于一个初始特征，而特征子集的重要性则是由子集中每个特征所对应的相关统计量分量之和来决定。于是，最终只需指定一个阈值 t，然后选择比 t 大的相关统计量分量所对应的特征即可；也可指定欲选取的特征个数 k， 然后选择相关统计分量最大的 k 个特征。
11.3 包裹式选择
- 与过滤式特征选择不考虑后续学习器不同，包裹式特征选择直接把最终将要使用的学习器的性能作为特征子集的评价标准。换言之，包裹式特征选择的目的就是为给定学习器选择最有利于其性能、“量身定做”的特征子集。
- 一般而言，由于包裹式特征选择方法直接针对给定学习器进行优化，因此从最终学习器性能来看，包裹式特征选择比过滤式特征选择更好，但另一方面，由于在特征选择过程中需多次训练学习器，因此包裹式特征选择的计算开销通常比过滤式特征选择大得多。
- LVW (Las Vegas Wrapper) 是一个典型的包裹式特征选择方法。它在拉斯维加斯方法(Las Vegas method)框架下使用随机策略来进行子集搜索，并以最终分类器的误差为子集评价准则。
11.4 嵌入式与L1正则化
- 在过滤式和包裹式特征选择方法中，特征选择过程与学习器训练过程有明显的分别；与此不同，嵌入式特征选择是将特征选择过程与学习器训练过程融为一体，两者在同一个优化过程中完成，即在学习器训练过程中自动进行了特征选择。
- L1范数和L2范数正则化都有助于降低过拟合风险，但前者还会带来一个额外的好处：它必后者更易于获得“稀疏”(sparse)解，即它求得的 w 会有更少的非零分量。
11.5 稀疏表示与字典学习
- 不妨把数据集 D 考虑成一个矩阵，其每行对应于一个样本，每列对应于一个特征。特征选择所考虑的问题是特征具有“稀疏性”，即矩阵中的许多列与当前学习任务无关，通过特征选择去除这些列，则学习器训练过程仅需在较小的矩阵上进行，学习任务的难度可能有所降低，涉及的计算和存储开销会减少，学得模型的可解释性也会提高。
- 现在我们来考虑另一种稀疏性：D 所对应的矩阵中存在很多零元素，但这些零元素并不是以整列、整行形式存在的。当样本具有这样的稀疏表达形式时，对学习任务来说会有不少好处，例如线性支持向量机之所以能在文本数据上有很好的性能，恰是由于文本数据在使用上述的字频表示后具有高度的稀疏性，使大多数问题变得线性可分。同时，稀疏样本并不会造成存储上的巨大负担，因为稀疏矩阵已有很多高效的存储方法。
- 那么，若给定数据集 D 是稠密的，即普通非稀疏数据，能否将其转化为“稀疏表示”(sparse representation)形式，从而享有稀疏性所带来的好处呢？需要注意的是，我们所希望的稀疏表示是“恰当稀疏”，而不是“过度稀疏”。
- 显然，在一般的学习任务中（例如图像分类）并没有《现代汉语常用词表》可用，我们需学习出这样一个“字典”。我普通稠密表达的样本找到合适的字典，将样本转化为合适的稀疏表示形式，从而使学习任务得以简化，模型复杂度得以降低，通常称为“字典学习”(dictionary learning)，亦称“稀疏编码”(sparse coding)。这两个称为稍有差别，“字典学习”更侧重于学得字典的过程，而“稀疏编码”则更侧重于对样本进行稀疏表达的过程。
11.6 压缩感知
- 在现实任务中，我们常希望根据部分信息来恢复全部信息。压缩感知(compressed sensing)为解决此类问题提供了新的思路。
- 与特征选择、稀疏表示不同，压缩感知关注的是如何利用信号本身所具有的稀疏性，从部分观测样本中恢复原信号。通常认为，压缩感知分为“感知测量”和“重构恢复”这两个阶段。“感知测量”关注如何对原始信号进行处理以获得稀疏样本表示，这方面的内容涉及傅里叶变换、小波变换以及字典学习、稀疏编码等，不少技术在压缩感知提出之前就已在信号处理领域有很多研究；“重构恢复”关注的是如何基于稀疏性从少量观测中恢复原信号，这是压缩感知的精髓，当我们谈到压缩感知时，通常是指该部分。
网友评论