特征选择和降维，它们是处理高维数据的两大主流技术。

1. 维数灾难问题大为减轻
2. 往往会降低学习任务的难度

在特征选择中，涉及两个关键环节：1）如何获取特征子集 2）如何评价特征子集的好坏

我们不可能遍历所有的特征子集，因此使用的是基于贪心的策略。搜索子集有三种方法：前向搜索，后向搜索，双向搜索。在子集评价问题中，可以使用信息增益作为评价准则。

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

常见的特征选择方法有三类：过滤式、包裹式和嵌入式。

过滤式特征选择

先进行特征选择，然后用过滤后的特征来训练模型。这两个阶段是分离开的。

Relief是一种著名的过滤式特征选择方法。
该方法设计了一个“相关统计量”来度量特征的重要性。该统计量是一个向量，每一个分量分别对应一个初始特征，特征子集的重要性由子集中每个特征对应的相关统计量分量之和来决定。于是，可以指定一个阈值，然后选择比阈值大的相关统计量分量所对应的特征即可；或者，指定欲选取的特征个数$k$k，然后选择相关统计量分量最大的$k$k个特征。

Relief的关键是如何确定相关统计量。对于每一个示例$x_i$xi​，寻找其猜中近邻$x_{i,nh}$xi,nh​(从同类样本中寻找)和猜错近邻$x_{i,nm}$xi,nm​(从异类样本中寻找)。
相关统计量对应属性$j$j的分量计算公式是：

根据属性$j$j的类型，如果是离散型，两个样本属性$j$j相同，则diff为0，否则为1；如果是连续型，首先将属性取值规范化到[0,1]区间，然后取平方差。

由分量的计算公式可以看出，分量值越大，则对应属性的分类能力越强。

Relief的时间开销随采样次数以及原始特征数线性增长，因此是一个运行效率很高的过滤式特征选择方法。

上面介绍的Relief是为二分类问题设计的，其扩展变体Relief-F可以处理多分类问题。对每一个示例$x_i$xi​，假设其属于第$k$k类，在同类样本中寻找其猜对近邻$x_{i,nh}$xi,nh​，然后在除了$k$k类之外的其他每一个类中寻找其猜错近邻$x_{i,l,nm}$xi,l,nm​。

相关统计量对应属性$j$j的分量计算公式是：

其中$p_l$pl​为第$l$l类样本在数据集中所占的比例。

包裹式特征选择

直接将要使用的学习器的性能作为特征子集的评价准则。因此从最终学习器性能来看，包裹式特征选择比过滤式特征选择更好，但是包裹式特征选择的计算开销通常比过滤式特征选择大很多。

LVW(Las Vegas Wrapper)是一个典型的包裹式特征选择方法。它在拉斯维加斯方法框架下使用随机策略进行子集搜索，并以最终分类器的误差作为特征子集评价准则。

从上面LVW算法描述中，可以看到，如果连续T轮未更新则算法停止。

拉斯维加斯方法和蒙特卡罗方法是两个随机化方法。
蒙特卡罗算法：采样越多，越近似最优解；
拉斯维加斯算法：采样越多，越有机会找到最优解。
如果要求在有限采样内，必须给出一个解，但不要求是最优解，则采用蒙特卡罗方法；如果问题要求必须给出最优解，但对采样没有限制，则采用拉斯维加斯方法。

嵌入式特征选择

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

$L_1$L1​范数和$L_2$L2​范数正则化都有助于降低过拟合风险，但是$L_1$L1​范数更易获得稀疏解，即解有更少的非零分量。

基于$L_1$L1​正则化的学习方法就是一种嵌入式特征选择方法。

$L_1$L1​正则化问题的求解可使用近端梯度下降(PGD)。