11.特征选择和稀疏学习
11.1子集搜索与评价
对象都有很多属性来描述，属性也称为特征（feature），用于刻画对象的某一个特性。对一个学习任务而言，有些属性是关键有用的，而有些属性则可能不必要纳入训练数据。对当前学习任务有用的属性称为相关特征（relevant feature）、无用的属性称为无关特征（irrelevantfeature）。从给定的特征集合中选择出相关特征子集的过程，称为特征选择（feature selection）。
特征选择时一个数据预处理（data preprocessing）过程，在现实机器学习任务中，基于避免维数灾难和降低不相关特征带来的学习难度，在获得数据之后往往会先进行特征选择再训练学习器。当然特征选择要确保不丢失重要特征。给定数据集，若学习任务不同，则相关特征很可能不同，因此无关特征是指与当前学习任务无关。若一个属性是从其他属性中推演而出的，则成为冗余特征（redundant feature）。
假定数据中不涉及冗余特征，并假定初始的特征集包含了所有的重要信息，那么如何进行特征选择呢？要从初始的特征集合中选取一个包含了所有重要信息的特征子集，若没有任何领域知识作为先验假设，那就只有遍历所有子集，这计算开销相当大，一旦属性稍多就会出现组合爆炸。较为可行的一个做法是：先产生一个候选子集，然后评价，基于评价结果产生下一轮候选子集，再评价…如此下去，直至无法找到更好的候选子集。这个做法就关系两个很重要的过程：如何评价候选子集的优劣？又如何根据评价结果遴选下一轮候选子集呢？
1）子集搜索（subsetsearch）
给定特征集合{a1,a2,…,ad}，可将每个特征看做一个候选子集，对这d个候选单特征子集进行评价，选出一个最优的，然后加入一个特征，构成包含两个特征的候选子集…假定在k+1轮时，最后的候选（k+1）个特征子集不如上一轮的选定集，则停止生成候选子集，并将上一轮选定的k特征集合作为特征选择结果。上述这种逐渐增加相关特征的策略称为前向（forward）搜索。如果从完整的特征集合开始，每次尝试去掉一个无关特征，这样逐渐减少特征的策略称为后向（backward）搜索。也可将前后和后向搜索结合起来，每一轮逐渐增加选定相关特征、同时减少无关特征，这样的策略称为双向（bidirectional）搜索。
上述策略是贪心的，因为它们仅仅考虑了使本轮选定集最优，如在第三轮假定a5优于a6，于是选定集为{a2,a4,a5}，然后在第四轮却可能是{a2,a4,a6,a8}优于所有的{a2,a4,a5,ai}。要解决这个问题，就只能进行穷举搜索。
2）子集评价（subsetevaluation）
给定数据集D，假定D中第i类样本所占的比例为pi(i=1,2,…,|y|)，假定样本属性均为离散型。对属性子集A，假定根据其取值将D分成了V个子集{D1,D2,…,DV}，每个子集中的样本在A上取值相同，计算属性子集A的信息增益：
