在机器学习的理论学习中，我们经常过于关注模型，而忽略了其他的一些问题。在实际的机器学习问题中，选择一个好的特征可能和使用一个好的模型一样重要，甚至特征的选择会直接影响最后模型的结果。本文介绍机器学习中的特征选择与稀疏学习。
子集搜索与子集评价
为什么需要特征选择？
现实的任务中经常会遇到维数灾难问题，这是由于属性过多造成的，这里和降维的出发点一样，都是处理高维数据的两大主流技术；
去除不相关的特征往往会降低学习的难度。
冗余特征与无关特征
无关特性是指与当前学习任务无关的特征，而冗余特征是指可以从其他的特征推演出来的特征。冗余特征可能会让学习任务变得简单，尤其是冗余特征恰好对应于完成学习任务所需的”中间概率“。下面的讨论不涉及冗余特征，而是关注如何去除无关特征。
从初始的特征集合中选取包含所有重要信息的特征子集
根据先验知识选择
遍历所有可能的子集，但是实际中会遇到组合爆炸，不可行
产生一个候选子集，评价他的好坏，基于评价结果产生下一个候选子集，然后再评价，如此往复。涉及到两个关键环节：如何根据评价结果获取下一个候选特征子集？如何评价候选特征子集的好坏？
子集搜索
前向搜索：假设有d个特征集合，根据子集评价，依次选出k个特征
后向搜索：从完整的特征集合开始，每次尝试去掉一个无关的特征，剩下k个特征
双向搜索：结合前向搜索和后向搜索
子集评价
子集评价的方法，和决策树中选择划分特征的方式一模一样。下面用信息增益准则为例，其实所有可以用于决策树特征选择的准则都可以使用。
给定一个数据集合D，计算每一个属性A将数据集划分以后的信息增益，假设属性A将数据集合分成了V个子集。
$$
Gain(A) = Ent(D) - \sum_{v=1}^V \frac{D^v}{D} Ent(D^v)
$$
其中信息熵的定义为：
$$
Ent(D) = -\sum_{k=1}^{|y|} p_k log_2 p_k
$$
其中假定D中第i类样本所占的比例为$p_i$。
小结
将特征子集搜索和特征评价相结合，就可以得到特征选择的方法。
例如将前向搜索和信息熵结合，这个方法和决策树非常相似，事实上，决策树中树结点划分属性所组成的集合就是选择出的特征子集。
常见的特征选择方法大致分为三种：过滤式（filter）、包裹式（wrapper）和嵌入式（embedding）。
过滤式选择
过滤式方法先对数据集合进行特征选择，然后再训练学习器，特征选择过程与后续学习器无关。
Relief（二分类问题）
Relief是一种著名的过滤式特征选择方法，该方法设计了一个”相关统计量“用来度量特征的重要性。每个特征对应于一个特征统计量，特征子集的重要性则是由子集中每个特征所应用的相关统计量之和来决定。
如何选择特征：
设置一个阈值，选择比阈值大的相关统计分量对应的特征即可；如果选择k个特征，那么选择相关统计分量最大的k个特征。
如何确定相关统计量：
对于每一个样本特征，Relief先在该样本的同类中寻找其最近邻$x_{i,nh}$，称为猜中近邻
再从该样本的异类样本中寻找其最近邻$x_{i,nm}$，称为猜错近邻。
特征j的相关统计量为：
$$
\delta^j = \sum_i -diff(x_i^j,x_{i,nh}^j)^2 + diff(x_i^j,x_{i,nm}^j)^2
$$
其中$x_i^j$表示样本在j属性上的取值。而diff（）的取值取决于属性j的类型，如果j为离散性那么当两个离散型类别相同时，值为0，反之为1；如果属性j为数值型，那么取值为两个数值的差的绝对值（先规范化）。
从公式中可以看出，如果样本与其猜中近邻在属性j上的距离小于与其猜错近邻的距离，那么说明属性j对区分同类与异类样本是有益的，于是增大属性j的统计分量。反之，减少分量。
Relief-F（多分类问题）
为了将Relief应用于多分类问题，计算相关统计量的方式改为：
$$
\delta^j = \sum_i -diff(x_i^j,x_{i,nh}^j)^2 + \sum_{l\ne k}(p_l \times diff(x_i^j,x_{i,nm}^j)^2)
$$
其中$p_l$表示第k类样本在数据集D中的比例。
包裹式选择
前面介绍的过滤式特征选择不考虑后续学习器的不同，与之相对应的是包裹式选择方法，该方法直接把最终要使用的学习器的性能作为特征子集的评价准则。
包裹式特征选择方法直接针对给定的学习器进行优化，因此从最终的学习器性能来看，包裹式特征选择比过滤式特征选择更好。
LVM特征选择方法
算法描述如下：
算法在第8行通过在数据集D上，使用交叉验证来估计学习器的误差，这个误差是在仅考虑特征子集时得到的，如果在该特征子集上的误差比当前特征子集上误差更小，或者误差相当但是包含的特征数目更少，那么就将该特征子集存在来。
这个算法的开销很大。
嵌入式选择与L1正则化
前面的特征选择方法中，都是将选择过程与学习器训练过程区分开。嵌入式特征选择则是将二者融为一体，在学习器的训练过程中自动地进行特征选择。
L1正则化的效果就是，得到一个”稀疏“的解，即初始的d个特征中仅有对应w非0的分量的特征才会出现在最终模型中。
L1正则化问题的求解方法是近端点梯度下降法。近端点法的推到过程是，假设原目标函数满足L-Lipshitz梯度条件，将目标函数在点$x_k$点出用二阶泰勒展开，计算闭式解为：
$$
z = x_{k+1} = x_k - \frac{1}{L} \nabla f(x_k)
$$
将改思路拓展到L1正则化之后的目标函数中，得到闭式解：
$$
x_{k+1}^i =
=\left{
\begin{aligned}
&z^i-\lambda/L,&\lambda/L<z^i \
&0,&|z^i| \le \lambda/L \
&z^i+\lambda/L,&z^i<-\lambda/L
\end{aligned}
\right.
$$
其中i表示x中第i个分量。
稀疏表示与字典学习
如果把数据集合看一个矩阵，每一行是一个样本，每列是一个特征，那么特征选择的过程就是选择这个矩阵中的一部分列，用于表征这个矩阵的信息。
稀疏表示则是另外一种稀疏性：数据集合Ｄ中存在很多的０元素。稀疏表示有很多优点，例如稀疏表示的问题更容易线性可分，学习任务得以简化；此外有很多高效的稀疏矩阵存储方法，稀疏样本的存储并不会造成很多的负担。
那么如何将稠密的数据转为稀疏的表示呢？一般使用“字典学习”或称为“稀疏编码”。“字典学习”更加关注于学习字典的过程，而“稀疏编码”更加关注于对样本的稀疏表达过程。
字典学习的形式为：
$$
\mathop{min}\limits_{B,\alpha_i} \sum_{i=1}^m || x_i-B\alpha_i||2^2 + \lambda\sum{i=1}^m ||\alpha_i||_1
$$
其中B为大小为d×k的字典矩阵，$\alpha_i$为大小为k的向量，是样本的稀疏表示。第一项希望能够尽量重构样本，第二项则希望尽量稀疏。
它的优化算法是交替优化B和alpha。
压缩感知
压缩感知的任务与前面的特征提取任务相反，压缩感知是希望根据部分信息来恢复全部信息。
压缩感知相关理论比较复杂， 具体可以参见《机器学习》第11章第六节。
参考资料
1.《机器学习》第十一章