第十一章特征选择与稀疏学习

子集搜索与评价

特征选择：在属性集中可能存在无用的属性，即对结果判断不重要的属性，被称为“无关特征”，而有用的属性被称为“相关特征”，而从特征集合中选择出相关特征子集的过程，被称为特征选择。
进行特征选择的原因：
1、减轻维数灾难问题；
2、去除不相关特征会降低学习任务的难度。
需要注意的是特征选择过程必须确保不丢失重要特征。

另外，特征选择中也存在“冗余特征”，即可以用其他特征推出来的特征，对于此类特征，要针对学习任务来决定是否去除。此章不涉及冗余特征。

那么如何进行特征选择呢？
可行的做法是产生一个“候选子集”，评价它的好坏，基于评价结果产生下一个候选子集，再对其进行评价，持续到无法找到更好的候选子集为止。于是这样可以引出两个问题：
1、如何根据评价结果获取下一个候选特征子集？
2、如何评价候选特征子集的好坏？

对于第一个问题，即子集搜索问题。分有前向搜索和后向搜索、双向搜索。前向搜索，例如给定特征集合 $\{a_1,a_2,...,a_d\}$ ，我们可以把每个特征看作一个候选子集，于是对于d个候选单特征子集进行评价，假定 $\{a_2\}$ 最优，则将其作为第一轮的选定集，然后在上一轮的选定集中加入一个特征形成一个新的候选子集，共形成d-1个子集，若这些候选子集中存在优于 $\{a_2\}$ 的，则将那个包含两特征的候选子集作为本轮的选定集......假定在第k+1轮时，最优的候选(k+1)特征子集不如上一轮的选定集，则停止生成候选子集，并将上一轮选定的k特征集合作为特征选择的结果。这种逐渐增加相关特征的策略便是前向搜索。而对于后向搜索，自然就是作减法。而二者结合起来，每一轮逐渐增加选定相关特征、同时减少无关特征，便被称为双向搜索。

对于第二个问题，即子集评价问题。给定数据集D，假定D中第i类样本所占比例为 $p_i (i=1,2,3,...,|y|)$ .假定样本属性均为离散型，对于属性子集A，假定根据其取值将D分为V个子集，即 $\{D^1,D^2,...,D^V\}$ ,每个子集中的样本在A上的取值相同，则我们可以计算出A的信息增益：

其中信息熵：

信息增益越大，意味着A包含的有助于分类的信息越多。
对于每个候选特征子集，基于训练集D来计算其信息增熵，以此为评价准则。
常见的特征方法大致分为：1、过滤式；2、包裹式；3、嵌入式

过滤式选择

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

Relief过滤式特征选择方法

其基本过程：设计一个“相关统计量”来度量特征的重要性，该统计量是一个向量，其每个分量分别对应一个初始特征，而特征子集的重要性则是由子集中每个特征所对应的相关统计量分量之和来决定，只需要指定一个阈值，则选择比阈值大的相关统计量分量所对应的特征即可，亦可指定欲选取的特征个数k，然后选择相关统计量分量最大的k个特征。
显然，Relief的关键是如何确定相关统计量.Relief定义猜中近邻为某个样本的同类样本中最近邻 $x_{i,nh}$ ，而猜错近邻为异类样本中的最近邻 $x_{i,nm}$ ，那么定义相关统计量对应于属性 $j$ 的分量为：

若相关统计量越大，那么在属性上，猜中近邻的距离比猜错近邻的距离更小，于是属性也就越有益，反之，则无益。
Relief是为二分类任务设计的，对于多分类任务则使用其扩展变体Relief-F.另外过滤式方法是独立于后续学习器的，即是学习器无关的。

包裹式选择

包裹式选择和过滤式不同，包裹式特征选择直接把最终要用的学习器的性能作为特征子集的评价准则，即选择有利于提高给定学习器的性能的特征子集。从性能上看，包裹式比过滤式要好，但是包裹式要多次训练学习器，其计算开销会很大。
LVW是一个典型的包裹式特征选择方法，其使用的是拉斯维加斯方法框架。基本步骤：
1、每一轮循环都随机生成一个特征子集；
2、在生成的子集上通过交叉验证法推断当前特征子集的误差；
3、多次循环，得到误差最小的特征子集。

算法描述：

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

嵌入式特征选择是将特征选择过程与学习器训练过程融为一体，二者在同一个优化过程中完成，即在学习器训练过程中自动地进行了特征选择。

以线性回归为例子，设目标函数为：

加入L2正则化以避免过拟合，则有：

上式引入L2范数，又称为岭回归。

若将L2替换为L1，则为套索回归（LASSO），即：

目标优化的解会在平方误差和正则化项之间折中，而使用L1范数比L2更容易获得稀疏解，即存在参数0，在线性回归中，参数为0的项可看作对应特征被剔除了，即完成了特征选择。

稀疏表示和字典学习

将数据集化成一个矩阵，每行对应一个样本，每列对应一个特征。特征选择所考虑的问题是特征具有稀疏性，即矩阵中的许多列与当前学习任务无关，通过特征选择去除掉这些列，则学习器训练过程只需要在一个较小的矩阵上进行，降低了学习任务的难度。
我们来考虑另一种稀疏性，即不是每行每列都为0，当样本具有这样的稀疏表达形式时，对学习任务来说也有不少好处，比如线性支持向量机之所以能在文本数据上有很好的性能，正是因为文本数据具有高度稀疏性且线性可分，且有着高效的存储解决方案。
为普通稠密表示的样本通过寻求合适的字典而找到一个合适的稀疏表示形式的过程就叫做字典学习，或者稀疏编码，它可以使得学习任务简化，模型复杂程度降低。
给定数据集 $\{x_1,x_2,...,x_m\}$ ，字典学习最简单的形式为：

其中为字典矩阵，为字典的词汇量，通常由用户指定，则是的稀疏表示.上式的第一项是希望能很好地重构，第二项则是希望尽量稀疏。
对于上式，我们可以采用变量交替优化方式：
1、固定字典,参照LASSO的解法解得下式：

2、固定来更新字典，基于逐列更新策略的KSVD(一种求解方法):

为了避免直接做SVD分解会同时改变，也许会破坏稀疏性。所以这里会对它们做特殊处理：只保留非零元素，保留和的非零元素乘积项，然后再进行SVD。这样做可以保持第一步得到的稀疏性。
反复迭代上面两个步骤，最终可以得到字典和稀疏表示，而词汇量的大小会影响稀疏程度。

压缩感知

在现实任务中，我们常希望根据部分信息来恢复全部信息。压缩感知(compressed sensing)为解决此类问题提供了新的思路。
假设有长度为 $m$ 的离散信号 $x$ ，采样后得到的信号 $y$ 长度为 $n$ ，且 $n\ll m$ ，即：

其中是对信号的测量矩阵，它确定了以什么频率进行采用以及如何采样样本组成采样后的信号。因为上式是一个欠定方程，所以由无法恢复出.
假设存在一个线性变换，于是可以表示为：

如果能根据恢复出，则可以通过来恢复出信号.
与特征选择、稀疏表示不同，压缩感知关注的是如何利用信号本身所具有的稀疏性，从部分观测样本中恢复原信号。压缩感知分两阶段：
1、感知测量：对原始信号进行处理以获得稀疏样本表示，涉及傅里叶变换、小波变换、字典学习、稀疏编码;
2、重构恢复：基于稀疏性从少量观测中恢复信号，这是压缩感知的精髓

对于压缩感知的相关理论，极具代表性的是"限定等距性"（RIP）.
基于部分信息来恢复全部信息的技术在许多现实任务中有重要的应用，例如协同过滤，本书介绍了另一种技术——矩阵补全技术，来求解此问题，其形式为：

其中为需要恢复的稀疏信号，表示矩阵的秩。是已观测信号，是已知元素的下标。由于上式是NP难问题，注意到在集合上的凸包是的核范数:

其中表示的奇异值，于是可以通过最小化矩阵核范数来求得近似解：

上式是一个凸优化问题，可通过半正定规划（SDP）进行求解。
理论研究表明，在满足一定条件时，如果的秩为,,则只需要观察到个元素就可以完美恢复出.

第十一章 特征选择与稀疏学习