西瓜书-特征选择与稀疏学习

给定特征集合{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}。要解决这个问题，就只能进行穷举搜索。

子集评价

评价指标：信息熵增益、不合度量、相关系数等可以判断两个划分差异的都可以 对于离散型可以计算属性的信息增益,信息增益越大，特征子集包含的有助于分类信息越多。更一般，根据特征子集对数据集D进行划分，每个划分区对应特征子集的一个取值，而样本标记信息Y对应D的真实划分。与Y差异越小的划分，特征子集越好。

过滤式选择

简单来说，过滤式方法先对数据集进行特征选择，然后再训练学习器，特征选择过程与后续学习器无关，这相当于先用特征选择过程对初识特征进行“过滤”，然后再用过滤后的特征来训练模型。比如，Relief方法。

包裹式选择

包裹式选择特征不考虑后续学习器不同，包裹式特征选择直接把最终将要使用的学习器的性能作为特征子集的评价准则。换言之，包裹式特征选择的目的就是为给定学习器选择最有利于其性能，量身定做的特征子集。包裹式选择比过滤式特征选择更好，但是另一方面，计算开销却要大得多。比如LVW方法（Las Vegas Wrapper)。

LVW中特征子集搜索采用了随机策略，每次评价都得重新训练学习器，故计算开销是很大的。

推导过程

Lipschitz连续：以陆地为例。岛屿：不连续一般陆地：连续丘陵：李普希兹连续悬崖：非李普希兹连续山包：可导平原：线性半岛：非凸想了半天用什么来表达亚连续（semi-continuity），好像只能用瀑布了===稍微具体点的话，李普希兹连续就是说，一块地不仅没有河流什么的玩意儿阻隔，而且这块地上没有特别陡的坡。其中最陡的地方有多陡呢？这就是所谓的李普希兹常数。悬崖的出现导致最陡的地方有“无穷陡”，所以不是李普希兹连续。

目标函数是最小化: 如果f(x)可导，且f的梯度满足Lipschitz，就可以使得

嵌入式选择和L1正则化

在过滤式和包裹式特征选择方法中，特征选择过程与学习器训练过程有明显的分别（过滤式是先做特征选择，再用过滤后的特征做学习器训练，而包裹式是用学习器训练的结果作为特征选择的依据）；与此不同，嵌入式特征选择是将特征选择过程与学习器训练过程融为一体，两者在同一个优化过程中完成，即在学习器训练过程中自动地进行了特征选择。

L2正则化

L1正则化

范数和 范数都有助于降低过拟合风险，但前者还会带来一个额外的好处：它比后者更易于获得“稀疏”（sparse）解，即它求得的w会有更少的非零分量（更多的零分量）

注意到w取得稀疏解意味着初始的d个特征中仅有对应着w的非零分量的特征才会出现在最终模型中，于是求解 范数正则化的结果时得到了仅采用一部分初始特征的模型；换言之，基于 正则化的学习方法就是一种嵌入式特征选择方法，其特征选择过程和学习器训练过程融为一体，同时完成。

xk附近可将f(x)泰勒展开

式3

<·,·>表示内积，式3的最小值在如下获得：

进而将这个思想推广到优化目标函数，得到每一步迭代为：

即每一步对f(x)进行梯度下降迭代的同时要考虑l1范数最小化

通过PGD能使LASSO和其他基于L1范数最小化的方法得以快速求解。

稀疏表示和字典学习

稀疏性的两种形式： 剔除无关特征，缩小矩阵

1. 把数据集D看成一个矩阵，每行对应一个样本，每列对应一个特征。特征选择所考虑的问题是特征具有稀疏性，即矩阵中的许多列与当前学习任务无关，通过特征选择去除这些列，则学习器训练过程仅需在叫小的矩阵上进行，学习任务的难度可能有所降低，设计的计算和存储开销会减少，学得模型的可解释性也会提高。

**适当稀疏可以使得问题线性可分，找出适当稀疏的特征字典 ** 2. 对于稀疏性，还存在一种情况是：D所对应的矩阵中存在很多零元素，这些零元素不是整行或整列存在。这和直接去掉其中一个或若干个列的稀疏性不一样，直接去除整列，是做了无关性特征剔除，不管样本是否在这个特征上是否为零。这种存在零元素情况的矩阵，在学习任务中有不少，如文档分类任务，将每个文档看做一个样本，每个字或词作为一个特征，字或词在文档中出现的频率或次数作为特征的取值；即D所对应的矩阵，每行是一个文档，每列是一个字或词，行列交汇点就是某个字或词在某文档中出现的频率或次数。《康熙词典》中有47035个汉字，就是矩阵有4万多个列，就算是仅考虑《现代汉语常用字表》中的汉字，矩阵也有3500列。对给定的文档，相当多的字是不会出现在这个文档中，矩阵的每一行有大量的零元素，不同的文档，零元素出现的列也不相同。

目标函数为：