特征选择

1. 子集搜索与评价

对于一个学习任务来说，给定属性集，其中有些属性可能很关键，而另一些属性则可能没什么用。这里将属性称为“特征”，对当前学习任务有用的属性称为“相关特征”（relevant feature），没什么用的属性称为“无关特征”（irrelevant feature），从给定的特征集合中选择出相关特征子集的过程，称为特征选择（feature selection）。

特征选择是一个重要的数据预处理过程，现实任务中，获得数据后通常先进行特征选择，此后再训练学习器。进行特征选择有两个重要原因：

现实任务中经常遇到维数灾难的问题，若能从过多的特征中选择出重要特征，会使后续学习过程仅需要在一部分特征上构建模型，维数灾难问题会大为减轻，这与降维有相似的动机；
去除不相关特征往往会降低学习任务的难度，只留下关键特征，学习效果可能更好。

特征选择必须保证不丢失重要特征，否则后续学习过程会因为重要信息丢失而无法获得好的性能。给定数据集，根据学习任务的不同，相关特征也很可能不同，特征选择中的“无关特征”是指与当前学习任务无关。有一类特征称为“冗余特征”（redundant feature），其所包含的信息可以从其他特征中推演过来，冗余特征在很多时候不起作用，去除它们会减轻学习过程的负担。例如，若已知“底面长”和“底面宽”，则“底面积”则是冗余特征。但是当学习任务是估算立方体体积，“底面积”这个冗余特征的存在将使体积的估算更为容易，即冗余特征恰好对应了完成学习任务所需的“中间概念”，则该冗余特征是有益的。为简化说明，假定下述讨论不涉及冗余特征。

特征选择的两个关键环节：

子集搜索
子集评价

1.1. 子集搜索

搜索策略：

前向搜索（forward）：给定特征集合\(\{a_1,a_2,\cdots,a_d\}\)，可将每个特征看做一个候选子集，对这\(d\)个候选单特征子集进行评价，假定\(\{a_2\}\)最优，于是将\(\{a_2\}\)作为第一轮的选定集；然后，在上一轮的选定集中加入一个特征，构成包含两个特征的候选子集，假定在这\(d-1\)个候选两特征子集中\(\{a_2,a_4\}\)最优，且优于\(\{a_2\}\)，于是将\(\{a_2,a_4\}\)作为本轮的选定集，\(\cdots \cdots\)假定在第\(k+1\)轮时，最优的候选\((k+1)\)特征子集不如上一轮的选定集，则停止生成候选子集，并将上一轮选定的\(k\)特征集合作为特征选择结果。这是一种逐渐增加相关特征的策略；
后向搜索（backward）：与前向搜索类似，若从完整的特征集合开始，每次尝试去掉一个无关特征，这样逐渐减少特征的策略称为后向搜索；
双向搜索（bidirectional）：将前向与后向搜索结合起来，每一轮逐渐增加选定相关特征（这些特征在后续轮中将确定不会被移除）、同时减少无关特征，这样的策略称为双向搜索。

显然，上述策略都是贪心的，它们仅考虑了使本轮选定集最优的情况。例如，在第三轮中假定选择\(a_5\)优于\(a_6\)，于是选定集为\(\{a_2,a_4,a_5\}\)，然而在第四轮却可能是\(\{a_2,a_4,a_6,a_8\}\)比所有的\(\{a_2,a_4,a_5,a_i\}\)都更优。遗憾的是，若不进行穷举搜索，这样的问题无法避免。

1.2. 子集评价

给定数据集\(D\)，假定\(D\)中第\(i\)类样本所占的比例为\(p_i(i=1,2,\cdots,|\mathscr{Y}|)\)。为了便于讨论，假定样本属性均为离散型。对属性子集\(A\)，假定根据其取值将\(D\)分成了\(V\)个子集\(\{D^1,D^2,\cdots,D^V\}\)，每个子集中的样本在\(A\)上取值相同，于是我们可计算属性子集\(A\)的信息增益： \[Gain(A) = Ent(D) - \sum_{v=1}^V \frac{|D^v|}{|D|} Ent(D^v)\] 其中信息熵定义为 \[Ent(D) = - \sum_{k=1}^{\mathscr{Y}} p_k \log_2 p_k\] 信息增益\(Gain(A)\)越大，意味着特征子集\(A\)包含的有助于分类的信息越多。于是，对于每个候选特征子集，我们可基于训练数据集\(D\)来计算其信息增益，以此作为评价准则。
更一般的，特征子集\(A\)实际上确定了对数据集\(D\)的一个划分，每个划分区域对应着\(A\)上的一个取值，而样本标记信息\(Y\)对应着对\(D\)的真实划分，通过估算这两个划分的差异，就能对\(A\)进行评价。与\(Y\)对应的划分的差异越小，则说明\(A\)越好。信息熵仅是判断这个差异的一种途径，其他能判断两个划分差异的机制都能用于特征子集的评价。
将特征子集搜索机制与子集评价机制相结合，即可得到特征选择方法。例如将前向搜索与信息熵相结合，这显然与决策树算法非常相似。事实上，决策树可用于特征选择，树节点的划分属性所组成的集合就是选择出的特征子集。其他的特征选择方法未必像决策树特征选择这么明显，但它们本质上都是显式或隐式地结合了某种（或多种）子集搜索机制和子集评价机制。

常见的特征选择方法大致分为三类：

过滤式（filter）；
包裹式（wrapper）；
嵌入式（embedding）。

2. 过滤式选择

过滤式方法先对数据集进行特征选择，然后再训练学习器，特征选择过程与后续学习器无关。这相当于先用特征选择过程对初始特征进行“过滤”，再用过滤后的特征来训练模型。
Relief是一种著名的过滤式特征选择方法，该方法设计了一个“相关统计量”来度量特征的重要性。该统计量是一个向量，其每个分量分别对应于一个初始特征，而特征子集的重要性则是由子集中每个特征所对应的相关统计量分量之和来决定。于是，最终只需指定一个阈值\(\tau\)，然后选择比\(\tau\)大的相关统计量分量对应的特征即可；也可指定欲选取的特征个数\(k\)，然后选择相关统计量分量最大的\(k\)个特征。
显然，Relief算法的关键是如何确定相关统计量。给定训练集\(\{(\pmb{x}_1,y_1),(\pmb{x}_2,y_2), \cdots,(\pmb{x}_m,y_m)\}\)，对每个示例\(\pmb{x}_i\)，Relief先在\(\pmb{x}_i\)的同类样本中寻找其最近邻\(\pmb{x}_{i,nh}\)，称为“猜中近邻”（near-hit），再从\(\pmb{x}_i\)的异类样本中寻找其最近邻\(\pmb{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\] 其中\(x_i^j\)表示样本\(\pmb{x}_a\)在属性\(j\)上的取值，\(diff(x_a^j,x_b^j)\)取决于属性\(j\)的类型；若属性\(j\)为离散型，则\(x_a^j = x_b^j\)时\(diff(x_a^j,x_b^j) = 0\)，否则为\(1\)；若属性\(j\)为连续型，则\(diff(x_a^j,x_b^j) = |x_a^j - x_b^j|\)，注意\(x_a^j,x_b^j\)已经规范化到\([0,1]\)区间。

从上式可看出，若\(\pmb{x}_i\)与其猜中近邻\(\pmb{x}_{i,nh}\)在属性\(j\)上的距离小于\(\pmb{x}_i\)与其猜错近邻\(\pmb{x}_{i,nm}\)的距离，则说明属性\(j\)对区分同类与异类样本是有益的，于是增大属性\(j\)所对应的统计量分量；反之，若\(\pmb{x}_i\)与其猜中近邻\(\pmb{x}_{i,nh}\)在属性\(j\)上的距离大于\(\pmb{x}_i\)与其猜错近邻\(\pmb{x}_{i,nm}\)的距离，则说明属性\(j\)起负面作用，于是减小属性\(j\)所对应的统计量分量。最后，对基于不同样本得到的估计结果进行平均，就得到各属性的相关统计量分量，分量值越大，则对应属性的分类能力就越强。
公式中的\(i\)指出了用于平均的样本下标，实际上Relief算法只需在数据集的采样上而不必在整个数据集上估计相关变量。显然，Relief的时间开销随采样次数以及原始特征数线性增长，因此是一个运行效率很高的过滤式特征选择算法。

Relief算法是为二分类问题设计的，其扩展变体Relief-F能处理多分类问题。假定数据集\(D\)中的样本来自\(|\mathscr{Y}|\)个类别。对示例\(\pmb{x}_i\)，若它属于第\(k\)类\((k \in \{1,2,\cdots,|\mathscr{Y}|\})\)，则Relief-F算法先在第\(k\)类的样本中寻找\(\pmb{x}_i\)的最近邻示例\(\pmb{x}_{i,nh}\)并将其作为猜中近邻，然后在第\(k\)类之外的每个类中找到一个\(\pmb{x}_i\)的最近邻示例作为猜错近邻，即为\(\pmb{x}_{i,l,nm} (l = 1,2,\cdots,|\mathscr{Y}|; l \neq k)\)。于是，相关统计量对应于属性\(j\)的分量为 \[\delta^j = \sum_i - diff(x_i^j,x_{i,nh}^j)^2 + \sum_{l \neq k} (p_l \times diff(x_i^j, x_{i,l,nm}^j)^2)\] 其中\(p_l\)为第\(l\)类样本在数据集\(D\)中所占的比例。

3. 包裹式选择

与过滤式特征选择不考虑后续学习器不同，包裹式特征选择直接把最终将要使用的学习器的性能作为特征子集的评价准则，包裹式特征选择的目的就是为给定学习器选择最有利于其性能、“量身定做”的特征子集。
一般而言，由于包裹式特征选择方法直接针对给定学习器进行优化，因此从最终学习器性能来看，包裹式特征选择比过滤式特征选择更好。但另一方面，由于在特征选择过程中需多次训练学习器，因此包裹式特征选择的计算开销通常比过滤式特征选择大的多。
LVW（Las Vegas Wrapper）是一个典型的包裹式特征选择方法。它在拉斯维加斯方法（Las Vegas method）框架下使用随机策略进行子集搜索，并以最终分类器的误差为特征子集评价准则，算法如下：

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

拉斯维加斯方法与蒙特卡洛方法的主要区别：

若有时间限制，则拉斯维加斯方法或者给出满足条件的解，或者不给出解；而蒙特卡洛方法一定会给出解，虽然给出的解未必满足要求；
若无时间限制，两者都能给出满足要求的解。

4. 嵌入式选择与\(L_1\)正则化

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

给定数据集\(D = \{(\pmb{x}_1,y_1),(\pmb{x}_2,y_2),\cdots,(\pmb{x}_m,y_m)\}\)，其中\(\pmb{x} \in \mathbf{R}^d, y \in \mathbf{R}\)。这里考虑最简单的线性回归模型，以平方误差为损失函数，则优化目标为 \[\min_{\pmb{w}} \sum_{i=1}^m (y_i - \pmb{w}^T \pmb{x}_i)^2\] 当样本特征很多，而样本数相对较少时，上式很容易陷入过拟合。为了缓解过拟合问题，在上式中加入正则项，若使用\(L_2\)范数正则化，则有 \[\min_{\pmb{w}} \sum_{i=1}^m (y_i - \pmb{w}^T \pmb{x}_i)^2 + \lambda ||\pmb{w}||_2^2\] 其中正则化参数\(\lambda > 0\)，上式称为“岭回归”（ridge regression）。通过引入\(L_2\)范数正则化，的确能显著降低过拟合的风险。
若采用\(L_1\)范数，则有 \[\min_{\pmb{w}} \sum_{i=1}^m (y_i - \pmb{w}^T \pmb{x})^2 + \lambda ||\pmb{w}||_1\] 其中正则化系数\(\lambda > 0\)，上式称为LASSO（Least Absolute Shrinkage and Selection Operator），直译为“最小绝对收缩选择算子”。
\(L_1\)范数和\(L_2\)范数正则化有助于降低过拟合风险，\(L_1\)范数还有一个额外的好处：\(L_1\)范数比\(L_2\)范数更易于获得“稀疏”（sparse）解，即它求得的\(\pmb{w}\)会有更少的非零分量。

事实上，对\(\pmb{w}\)施加“系数约束”（即希望非零分量尽可能少）最自然的是使用\(L_0\)范数，但\(L_0\)范数不连续，难以优化求解，因此常用\(L_1\)范数来近似。

分别引入\(L_1\)和\(L_2\)的目标函数的解要在平方误差项与正则化项之间折中，即出现在图中平方误差项等值线与正则化项等值线相交处。从上图可以看出，采用\(L_1\)范数时平方误差项等值线与正则化项等值线的交点常出现在坐标轴上，即\(w_1\)或\(w_2\)为0；而在采用\(L_2\)范数时，两者的焦点常出现在某个象限中，即\(w_1\)和\(w_2\)均非0。采用\(L_1\)范数比\(L_2\)范数更易于得到稀疏解。

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

\(L_1\)正则化问题的求解可使用近端梯度下降（Proximal Gradient Descent，PGD）。具体地说，令\(\nabla\)表示微分算子，对优化目标 \[\min_{\pmb{x}} f(\pmb{x}) + \lambda ||\pmb{x}||_1 \tag{1}\] 若\(f(\pmb{x})\)可导，且\(\nabla f\)满足L-Lipschitz条件，即存在常数\(L > 0\)使得 \[||\nabla f(\pmb{x}') - \nabla f(\pmb{x})||_2^2 \leq L||\pmb{x}' - \pmb{x}||_2^2 \quad (\forall \pmb{x},\pmb{x}')\] 则在\(\pmb{x}_k\)附近可将\(f(\pmb{x})\)通过二阶泰勒展开式近似为 \[\begin{align} \hat{f}(\pmb{x}) & \simeq f(\pmb{x}_k) + <\nabla f(\pmb{x}_k),\pmb{x} - \pmb{x}_k> + \frac{L}{2} ||\pmb{x} - \pmb{x}_k||^2 \nonumber \\ & = \frac{L}{2} ||\pmb{x} - (\pmb{x}_k - \frac{1}{L} \nabla f(\pmb{x}_k))||_2^2 + const \nonumber \end{align}\] 其中\(const\)是与\(\pmb{x}\)无关的常数，\(<·,·>\)表示内积，显然，上式的最小值在如下\(\pmb{x}_{k+1}\)获得： \[\pmb{x}_{k+1} = \pmb{x}_k - \frac{1}{L} \nabla f(\pmb{x}_k)\] 若通过梯度下降法对\(f(\pmb{x})\)进行最小化，则每一步梯度下降迭代实际上等价于最小化二次函数\(\hat{f}(\pmb{x})\)。将这个思想推广到公式（1），则能类似地得到其每一步迭代应为 \[\pmb{x}_{k+1} = \arg \min_{\pmb{x}} \frac{L}{2} ||\pmb{x} - (\pmb{x}_k - \frac{1}{L} \nabla f(\pmb{x}_k))||_2^2 + \lambda ||\pmb{x}||_1\] 即每一步对\(f(\pmb{x})\)进行梯度下降迭代的同时考虑\(L_1\)范数最小化。
对于上式，可先计算\(\pmb{z} = \pmb{x}_k - \frac{1}{L} \nabla f(\pmb{x}_k)\)，然后求解 \[\pmb{x}_{k+1} = \arg \min_{\pmb{x}} \frac{L}{2} ||\pmb{x} - \pmb{z}||_2^2 + \lambda ||\pmb{x}||_1\] 令\(x^i\)表示\(\pmb{x}\)的第\(i\)个分量，将上式按分量展开可看出，其中不存在\(x^i x^j (i \neq j)\)这样的项，即\(\pmb{x}\)的各分量互不影响，于是上式有闭式解： \[x_{k+1}^i = \begin{cases} z^i - \lambda / L, \quad \lambda / L < z^i; \\ 0, \qquad \qquad |z^i| \leq \lambda / L; \\ z^i + \lambda / L, \quad z^i < \lambda / L. \end{cases}\]

其中\(x_{k+1}^i\)与\(z_i\)分别表示是\(\pmb{x}_{k+1}\)与\(z\)的第\(i\)个分量。因此，通过PGD能使LASSO和其他基于\(L_1\)范数最小化的方法得以快速求解。

闭式解推导：这里采用soft thresholding算法：
对于\(\pmb{x}\)的第\(i\)个分量\(x^i\): \[\begin{equation} f(x^i) = \frac{L}{2} ||x^i - z^i||^2 + \lambda ||x^i||_1 \nonumber \\ \partial f(x^i) = L(x^i - z^i) + \lambda ||x^i||_1 \end{equation}\] 若\(x_{k+1}^i\)为\(f(x)\)的最小值，应满足\(0 \in \partial f(x_{k+1}^i)\)，有如下推导： \[\begin{equation} 0 \in \partial f(x_{k+1}^i) \nonumber \\ 0 \in L(x^i - z^i) + \partial(\lambda ||x_{k+1}^i||_1) \nonumber \\ (z^i - x^i) \in \partial (\frac{\lambda}{L} ||x_{k+1}^i||_1) \end{equation}\] 根据\(x_{k+1}^i\)与0的关系分为三种情况：

若\(x_{k+1}^i > 0\)，则\(\partial (\frac{\lambda}{L} ||x_{k+1}^i||_1) = \frac{\lambda}{L}\)，所以有\(x_{k+1}^i = z^i - \lambda / L\)，此时\(\lambda/L < z^i\)；
若\(x_{k+1}^i < 0\)，则\(\partial (\frac{\lambda}{L} ||x_{k+1}^i||_1) = -\frac{\lambda}{L}\)，所以有\(x_{k+1}^i = z^i + \lambda / L\)，此时\(\lambda/L > z^i\)；
若\(x_{k+1}^i = 0\)，则\(\partial (\frac{\lambda}{L} ||x_{k+1}^i||_1) = [-\frac{\lambda}{L},\frac{\lambda}{L}]\)，所以有\(x_{k+1}^i = 0\)，此时\(|z^i| \leq \lambda / L\)；

所以有闭式解 \[x_{k+1}^i = \begin{cases} z^i - \lambda / L, \quad \lambda / L < z^i; \\ 0, \qquad \qquad |z^i| \leq \lambda / L; \\ z^i + \lambda / L, \quad z^i < \lambda / L. \end{cases}\]

其他部分的推导还有一些疑惑，只是简单的记一下，PGD参考