机器学习 第11章-特征选择与稀疏学习

11.1 子集搜索与评价

我们将属性称为“特征”(feature)，对当前学习任务有用的属性称为“相关特征”(relevant feature)、没什么用的属性称为“无关特征”(irrelevant feature)。从给定的特征集合中选择出相关特征子集的过程，称为“特征选择”(feature selection)。

特征选择是一个重要的“数据预处理”(data preprocessing)过程，在现实机器学习任务中，获得数据之后通常先进行特征选择，此后再训练学习器。

特征选择过程必须确保不丢失重要特征，否则后续学习过程会因为重要信息的缺失而无法获得好的性能。给定数据集，若学习任务不同，则相关特征很可能不同，因此，特征选择中所谓的“无关特征”是指与当前学习任务无关。有一类特征称为“冗余特征”(redundant feature)，它们所包含的信息能从其他特征中推演出来。

冗余特征在很多时候不起作用，去除它们会减轻学习过程的负担。但有时冗余特征会降低学习任务的难度，例如若学习目标是估算立方体的体积，则“底面积”这个冗余特征的存在将使得体积的估算更容易；更确切地说，若某个冗余特征恰好对应了完成学习任务所需的“中间概念”，则该冗余特征是有益的。

对于子集搜索问题，有三种基于贪心的策略：

前向搜索：将每个特征当做一个候选子集，然后从当前所有的候选子集中选择出最佳的特征子集；接着在上一轮选出的特征子集中添加一个新的特征，同样地选出最佳特征子集；最后直至选不出比上一轮更好的特征子集。

后向搜索：类似于前向搜索，但是每次是去掉一个无关特征。

双向搜索：把前向和后向结合，每次增加相关特征，去除无关特征。

对于子集评价问题，给定数据集$D$，假定$D$中第$i$类样本所占的比例为$p_i(i=1,2,...,|Y|)$。为便于讨论，假定样本属性均为离散型。对属性子集$A$，假定根据其取值将$D$分成了$V$个子集 { D 1 , D 2 , . . . , D V } \{D^1,D^2,...,D^V\} {D1,D2,...,DV}，每个子集中的样本在$A$上取值相同，于是我们可计算属性子集 $A$ 的信息增益
$$Gain(A)=Ent(D)-\sum _{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$$
其中信息熵定义为
$$Ent(D)=-\sum _{i=1}^{|Y|}{p}_{k}lo{g}_2{p}_k$$
信息增益 $Gain(A)$越大，意味着特征子集 $A$包含的有助于分类的信息越多。于是，对每个候选特征子集，我们可基于训练数据集$D$来计算其信息增益，以此作为评价准则。

将特征子集搜索机制与子集评价机制相结合，即可得到特征选择方法。

常见的特征选择方法大致可分为三类:过滤式(6lter)、包裹式(wrapper)和嵌入式(embedding)。

11.2 过滤式选择

过滤式方法先对数据集进行特征选择，然后再训练学习器，特征选择过程与后续学习器无关。

Relief(Relevant Features)是一种著名的过滤式特征选择方法，该方法设计了一个“相关统计量”来度量特征的重要性。该统计量是一个向量，其每个分量分别对应于一个初始特征，而特征子集的重要性则是由子集中每个特征所对应的相关统计量分量之和来决定。

显然，Relief的关键是如何确定相关统计量。给定训练集$\{(x_1,y_1)，(x_2,y_2)，\dots 。，(x_m,y_m)\}$，对每个示例$x_i$，Relief先在$x_i$的同类样本中寻找其最近邻 $x_{i,nh}$，称为“猜中近邻”(near-hit)，再从KaTeX parse error: Expected group after '_' at position 2: x_̲的异类样本中寻找其最近邻 $x_{i,nm}$，称为“猜错近邻”(near-miss)，然后，相关统计量对应于属性j的分量为
$${\delta }^j=\sum _i-diff(x_i^j,x_{i,nh}^j{)}^2+diff(x_i^j,x_{i,nm}^j{)}^2$$

Relief是为二分类问题设计的，其扩展变体Relief-F能处理多分类问题。假定数据集$D$中的样本来自$|Y|$个类别。对示例KaTeX parse error: Expected group after '_' at position 2: x_̲，若它属于第$k$类 ( k ∈ { 1 , 2 , . . . , ∣ Y ∣ } (k∈\{1,2,...,|Y|\} (k∈{1,2,...,∣Y∣}，则Relief-F先在第$k$类的样本中寻找$x_i$的最近邻示例 $x_{i,nh}$并将其作为猜中近邻，然后在第$k$类之外的每个类中找到一个$x_i$的最近邻示例作为猜错近邻，记为$x_{i,nm}$ $(l=1,2,.\dots ,|Y|;l\ne k)$。于是，相关统计量对应于属性$j$的分量为
$${\delta }^j=\sum _i-diff(x_i^j,x_{i,nh}^j{)}^2+\sum _{l\ne k}(p_l\ast diff(x_i^j,x_{i,nm}^j{)}^2)$$

11.3 包裹式选择

与过滤式特征选择不考虑后续学习器不同，包裹式特征选择直接把最终将要使用的学习器的性能作为特征子集的评价准则。换言之，包裹式特征选择的目的就是为给定学习器选择最有利于其性能、“量身定做”的特征子集

一般而言，由于包裹式特征选择方法直接针对给定学习器进行优化，因此从最终学习器性能来看，包裹式特征选择比过滤式特征选择更好，但另一方面由于在特征选择过程中需多次训练学习器，因此包裹式特征选择的计算开销通常比过滤式特征选择大得多。

LVW是一种典型的包裹式特征选择方法。其在拉斯维加斯框架下使用随即策略来进行自己搜索，并以最终分类器的误差为特征子集的评价准则。其算法描述如下图所示：

需注意的是，由于 LVW 算法中特征子集搜索采用了随机策略，而每次特征子集评价都需训练学习器，计算开销很大，因此算法设置了停止条件控制参数T。然而，整个 LVW 算法是基于拉斯维加斯方法框架，若初始特征数很多(即4|很大)、T设置较大，则算法可能运行很长时间都达不到停止条件。换言之若有运行时间限制，则有可能给不出解。

11.4 嵌入式选择与$L_1$正则化

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

给定数据集$D=(x_1,y_1)，(x_2,y_2)，\cdots ，(x_m,y_m)$，其中$x\in R^d，y\in R$， 我们考虑最简单的线性回归模型，以平方误差为损失函数，则优化目标为
$$mi{n}_w\sum _{i=1}^m(yi-w^{T}xi{)}^2$$
当样本特征很多，而样本数相对较少时，很容易陷入过拟合。为了缓解过拟合问题，可对引入正则化项。若使用$L_2$范数正则化，则有
$$mi{n}_w\sum _{i=1}^m(yi-w^T{x}_i{)}^2+\lambda ||w|{|}_2^2$$

可以使用别的$L_p$范数来替代原本的$L_2$范数，如$L_1$范数。那么可以得到：
$$mi{n}_w\sum _{i=1}^m(yi-w^T{x}_i{)}^2+\lambda \Vert w{\Vert }_1$$
该式称为LASSO。

11.5 稀疏表示与字典学习

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

现在我们来考虑另一种稀疏性：D所对应的矩阵中存在很多零元素，但这些零元素并不是以整列、整行形式存在的。

若给定一个稠密矩阵，我们能通过某种方法找到其合适的稀疏表示，可以使得学习任务更加简单高效，我们称之为稀疏编码或字典学习。

给定一个数据集，字典学习最简单的形式为：
$$mi{n}_{B,\alpha i}\sum _{i=1}^m\Vert x_i-B{\alpha }_i{\Vert }_2^2+\lambda \sum _{i=1}^m\Vert {\alpha }_i{\Vert }_1$$

11.6 压缩感知

在现实任务中，我们常希望根据部分信息来恢复全部信息。例如在数据通讯中要将模拟信号转换为数字信号，根据奈奎斯特(Nyquist)采样定理，令采样频率达到模拟信号最高频率的两倍，则采样后的数字信号就保留了模拟信号的全部信息；换言之，由此获得的数字信号能精确重构原模拟信号。然而，为了便于传输、存储，在实践中人们通常对采样的数字信号进行压缩，这有可能损失一些信息，而在信号传输过程中，由于信道出现丢包等问题，又可能损失部分信息。那么，接收方基于收到的信号，能否精确地重构出原信号呢？压缩感知(compressed sensing)为解决此类问题提供了新的思路。

与特征选择、稀疏表示不同，压缩感知关注的是如何利用信号本身所具有的稀疏性，从部分观测样本中恢复原信号。通常认为，压缩感知分为“感知测量”和“重构恢复”这两个阶段。“感知测量”关注如何对原始信号进行处理以获得稀疏样本表示，这方面的内容涉及傅里叶变换、小波变换以及 11.5节介绍的字典学习、稀疏编码等，不少技术在压缩感知提出之前就已在信号处理等领域有很多研究:“重构恢复”关注的是如何基于稀疏性从少量观测中恢复原信号，这是压缩感知的精髓，当我们谈到压缩感知时，通常是指该部分。