常见的特征选择方法：

• 过滤式 filter
• 包裹式 wrapper
• 嵌入式 embedding

2. 过滤式选择

先对数据集进行特征选择，然后再训练分类器，特征选择过程与后续学习无关。相当于先用特征选择过程，对初始特征进行过滤，再用过滤后的特征来训练模型。

Relief法：设计了一个相关统计量，度量特征重要性。这是一个向量，每个分量对应一个初始特征，特征子集的重要性是由子集中每个特征对应的相关统计分量之和决定。可指定分量阈值，可指定个数k。

如何确定相关统计量？

给定训练集，对每个样本，Relief先在其同类样本中寻找最紧邻的点，为猜中近邻。再从异类样本中寻找最近邻的点，称为猜错近邻。相关统计量对应于属性j的分量，计算公式为：

属性j为离散类型，则diff为指示函数。若为连续属性，则diff为距离差。

该式可看出：若猜中近邻与样本在属性j上的距离，小于猜错近邻与样本的距离，则该式为正，属性j对区分同类异类有益，分量值大于0起正面作用；若该式为负，说明属性j起负面作用，分量值小于0起负面作用。

最终对不同样本得到的估计结果进行平均，得到各属性的相关统计分量，分量值越大，对应属性的分类能力越强，越值得选。

相关统计量的计算，已然具有距离度量学习的意味。距离度量是每个属性上的权重，而相关统计量则是每个属性的统计分量。非常类似。

二分类扩展为多分类问题：

3. 包裹式选择

过滤式特征选择方法，不考虑后续学习器。而包裹式选择，直接把最终将要使用的学习器的性能作为特征子集的评价准则。

包裹式特征选择，目的就是为给定学习器选择最有利于其性能，量身定做的特征子集。

学习器性能上看，包裹式选择肯定好；但多次训练导致时间开销大。

LVW（Las Vegas Wrapper），拉斯维加斯方法：在拉斯维加斯方法框架下使用随即策略进行子集搜索，以最终分类器的误差为特征子集评价准则。

其和蒙特卡洛方法是以两个著名赌城命名的随机化方法。区别是，拉斯维加斯方法或者给出满足要求的解，或者不给出解。蒙方法一定会给出解，虽然未必满足要求（局部最优解）。若无时间要求，两者都能给出满足要求的解。

随机生成子集，通过在D上使用交叉验证法估计学习器的误差，该误差仅在特征子集上考虑。若比误差更小或误差想当但包含数目较少，则更新。

因计算开销很大，算法设置了停止条件控制参数。算法可能很长时间都达不到停止条件，若有时间限制，则给不出解。

蒙特卡洛和拉斯维加斯方法的特点对比，见这里。

4. 嵌入式选择与L1正则化

4.1 嵌入式选择

Lp范数是常用的正则化项。L2范数倾向于w的分量取值尽量均衡，非零分量个数尽量稠密。L0范数和L1范数倾向于w的分量尽量稀疏，即非零分量的个数尽量少。

过滤式、包裹式特征选择方法，特征选择过程和学习训练过程有明确的分别，一个完全分离，一个是按顺序进行。

嵌入式特征选择：将特征选择方法和学习训练过程融为一体。两者同在一个优化过程中完成。在学习器训练时自动进行特征选择。

给定训练集，考虑线性回归模型，以平方误差为损失函数，则优化目标为：

当样本特征较多，样本数量较少时，很容易过拟合。引入正则化项，使用L2范数正则化，则有：

上式称为岭回归（ridge regression）。

若采用L1正则化，则有：

上式称为LASSO（最小绝对收缩选择算子）回归。

L1和L2范数正则化，均有助于降低过拟合风险。但前者还有额外好处：比后者更容易获得稀疏解，求得的w会有更少的分量。

直观例子：假设x有两个属性，w则有两个分量。将其为坐标轴，绘制出上式第一项的等值线：即在（w1，w1）空间中平方误差项取值相同的点的连线，再分别绘制出L1范数和L2范数的等值线：即L1、L2范数取值相同的点的连线。如图：

上面两式子的解要在平方误差项和正则化项中折中，则两线相交处。采用L1正则项时，相交点常出现在坐标轴上（则某项为0）。L2范数时，两者交点在某象限中，均非0。这表明，L1范数比L2范数更容易得到稀疏解。

w取得稀疏解，意味着d个初始特征中仅有对应着w的非零分量的特征，才会出现在最终模型中。求解L1范数正则化的结果是得到了仅采用一部分初始特征的模型。

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

4.2 L1正则化问题的求解

近端梯度下降（Proximal Gradient Descent，PGD）

具体过程待续。