对一个学习任务来说，给定属性集，其中有些属性可能很关键、很有用，另一些属性则可能没什么用，我们将属性称为“特征”（feature），对当前学习任务有用的属性称为“相关特征”（relevant feature）、没什么用的属性称为“无关特征”（irrelavant feature）。从给定的特征集合中选择出相关特征子集的过程，称为“特征选择”（feature selection）。

【注意】：

特征的相关与无关是相对当前学习任务而言，若更换学习任务则有可能使得原本相关特征变为无关特征。例如姓名特征对于预测年龄几乎没有什么作用，但对于预测性别则有一定的参考价值。
特征选择过程必须确保不丢失重要特征，否则后续学习过程会因为重要信息的缺失而无法获得好的性能。

特征选择是一个重要的“数据预处理”过程，在现实机器学习任务中，获得数据之后通常先进行特征选择，此后再训练学习器，那么为什么要进行特征选择呢？

首先，我们在现实任务中经常会遇到维数灾难问题，这是由于特征过多而造成的，若能从中选择出重要的特征，使得后续学习过程仅需在一部分特征上构建模型，则维数灾难问题会大为减轻。从这个意义上来说，特征选择与降维有相似的动机；事实上，特征选择与降维是处理高维数据的两大主流技术。
去除不相关特征往往会降低学习任务的难度。这就像侦探破案一样，将纷繁复杂的因素抽丝剥茧，只留下关键因素，则真相往往更易看清。

【冗余特征（redundant feature）】：所包含的信息能从其他特征中推演出来。例如，考虑立方体对象，若已有特征“底面长”、“底面宽”，则“底面积”是冗余特征，去除它们会减轻学习过程的负担。但有时冗余特征会降低学习任务的难度，例如若学习目标是估算立方体的体积，则“底面积”这个冗余特征的存在将使得体积的估算更容易；更确切地说，若某个冗余特征恰好对应了完成学习任务所需的“中间概念”，则该冗余特征是有益的。

了解了上述基本概念后，我们该如何从初始的特征集合中选取一个包含所有重要信息的特征子集？

任何领域知识作为先验假设来选择特征；
遍历所有可能的子集：这种做法在计算上不可行，因为会遭遇组合爆炸，特征个数稍多就无法进行；
挑选“候选子集”：首先产生一个“候选子集”，评价出它的好坏，基于评价结果产生下一个候选子集，再对其进行评价。该过程持续进行下去，直至无法找到更好的候选子集为止。

第三个方案涉及两个关键环节：

如何根据评价结果获取下一个候选特征子集？
如何评价候选特征子集的好坏？

子集搜索

第一个环节是“子集搜索”（subset search）问题。

前向搜索（forward）

给定特征集合 ${a_1, a_2,\cdots, a_d}$，我们可将每个特征看作一个候选子集，对这 d 个候选单特征子集进行评价，假定 ${a_2}$ 最优，于是将 ${a_2}$ 作为第一轮的选定集；然后，在上一轮的选定集中加入一个特征，构成包含两个特征的候选子集，假定在这 d - 1 个候选两特征子集中 ${a_2, a_4}$ 最优，且优于 ${a_2}$，于是将 ${a_2, a_4}$ 作为本轮的选定集。假定在第 k + 1 轮时，最优的候选 (k + 1) 特征子集步入上一轮的选定集，则停止生成候选子集，并将上一轮选定的 k 特征集合作为特征选择结果。

后向搜索（backward）

从完整的特征集合开始，每次尝试去掉一个无关特征。

双向搜索（bidirectional）

将前向和后向搜索结合起来，每一轮逐渐增加选定相关特征（这些特征在后续轮中将确定不会被去除）、同时减少无关特征。

上述策略都是贪心的，因为它们仅考虑使本轮选定集最优，例如在第三轮假定选择 a5 优于 a6，于是选定集为 ${a_2, a_4, a_5}$，然而在第四轮却可能是 ${a_2, a_4, a_6, a_8}$ 比所有的 ${a_2, a_4, a_5, a_i}$ 都更优。遗憾的是，若不进行穷举搜索，则这样的问题无法避免。

【思考】：无论是前向、后向还是双向搜索都是贪心策略，这让我想起吴恩达老师的深度学习课程中所讲的集束搜索策略。集束搜索策略是指什么呢？我们在特征子集搜索的每一步过程中多选择几个特征，例如按照最优的结果降序排列，我们选择最前面的 3 个特征。假设选择的是 ${a_2}, {a_4}, {a_5}$，然后分别以这三个子集作为起点出发，继续寻找最优的 3 个特征子集，那么此时可获得 9 个特征子集（有可能会重复，例如 ${a_2, a_4}, {a_4, a_2}$），再从这 9 个特征子集中选择最优的 3 个特征子集进入到下一轮搜索过程。也就是说，最终我们可以得到 3 个特征子集，而 3 就是集束搜索的集束宽，这个参数我们可以自行设置，参数越大计算开销也越大，但获取最优解的概率也越高。关于集束搜索的详细内容可以参考吴恩达老师深度学习课程的笔记传送门-3.3 集束搜索（Beam Search）