机器学习 学习笔记（16） 特征选择与稀疏学习

对当前学习任务有用的属性称为相关特征，没什么用的属性称为无关特征，从给定的特征集合中选择出相关特征自己的过程，称为特征选择。

进行特征选择的重要原因有：首先，在现实任务中经常会遇到维数灾难问题，这是由于属性过多而造成的，若能从中选择出重要特征，使得后续学习过程仅需在一部分特征上构建模型，则维数灾难问题会大为减轻。特征选择与降维是处理高维数据的两大主流技术。第二个原因是，去除不相关特征往往会降低学习任务的难度。

特征选择中的无关特征，是指与当前学习任务无关。冗余特征是指它们包含的信息能从其他特征中推演出来。冗余特征在很多时候不起作用，去除它们会减轻学习过程的负担。但有时候冗余特征会降低学习任务的难度。若某个冗余特征恰好对应了完成学习任务所需的中间概率，则该冗余特征是有益的。

想要从特征集合中选取一个包含了所有重要信息的特征子集，需要两个关键环节，子集搜索与子集评价。

子集搜索，给定特征集合

\{a_1,a_2,...,a_d\}

，可将每个特征看做一个候选子集，对这d个候选单特征字节进行平键，假定

\{a_2\}

最优，将

\{a_2\}

作为第一轮的选定集，然后在上一轮的选定集中加入一个特征，构成包含两个特征的候选子集，假定

\{a_2,a_4\}

最优，且优于

\{a_2\}

，于是将

\{a_2,a_4\}

作为本轮选定集，假定在k+1轮时，最优的（k+1）特征子集不如上一轮的选定集，则停止生产候选子集，并将上一轮选定的k特征集合作为特征选择结果。这样逐渐增加相关特征的策略为“前向”搜索。同样，从完整的特征集合开始，每次尝试去掉一个特征，这样逐渐减少特征的策略称为后向搜索。还可以将前向与后向结合起来，每一轮增加相关特征，同时减少无关特征，称为双向搜索。

子集评价，如信息增益。特征子集A实际上确定了对数据集D的一个划分，每个划分区域对应着A上的一个取值，而样本标记信息Y则对应着对D的真实划分，通过估算这两个划分的差异，就能对A进行评价，与Y对应的划分的差异越小，则说明A越好。能判断两个划分差异的机制都能用于特征子集评价。

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

常见的特征选择方法大致可以分为三类：过滤式（filter）、包裹式（wrapper）和嵌入式（embedding）。

过滤式选择

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

Relief是一种著名的过滤式特征选择方法，该方法设计了一个相关统计量来度量特征的重要性。该统计量是一个向量，其每个分量分别对应于一个初始特征，而特征子集的重要性则是由子集中每个特征所对应的相关统计量分量之和来决定，于是，最终只需要指定一个阈值

\tau

，然后选择比

\tau

大的相关统计量分量所对应的特征即可，也可指定欲选取的特征个数k，然后选择相关统计量分量最大的k个特征。

显然，Relief的关键是如何确定相关统计量。给定训练集

\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\}

，对每个示例

x_i

，Relief先在

x_i

的同类样本中寻找其最近邻

x_{i,nh}

，称为猜中近邻(near-hit)，再从

x_i

的异类样本中寻找其最近邻

x_{i,nm}

，称为猜错近邻(near-miss)，然后，相关统计量对应于属性j的分量为：

\delta ^j=\sum_{i} -diff(x^j_i,x^j_{i,nh})^2+diff(x^j_i,x^j_{i,nm})^2

x^j_a

表示样本

x_a

在属性j上的取值，

diff(x^j_a,x_b^j)

取决于属性j的类型，若j为离散型，则

x^j_a=x_b^j

时，

diff(x^j_a,x_b^j)=0

，否则为1，若属性j为连续型， 则

diff(x^j_a,x_b^j)=|x^j_a-x_b^j|

，注意

x^j_a,x_b^j

已经规范化到[0,1]区间。

从上式可以看出，若

x_i

与其猜中近邻

x_{i,nh}

在属性j上的距离小于

x_i

与其猜错近邻

x_{i,nm}

的距离，则说明属性j对区分同类与异类样本是有益的，于是增大属性j对应的统计量分量，反之说明属性j起负面作用，于是减小属性j所对应的统计量分量。最后，对基于不同样本得到的估计结果进行平均，就得到各属性的相关统计分量，分量值越大，则对应属性的分类能力就越强。

实际上Relief只需在数据集上采样，而不必在整个数据集上估计相关统计量。Relief的时间开销随着采样次数以及原始特征数线性增长，因此是一个运行效率很高的过滤式特征选择算法。

Relief是为二分类问题设计的，其扩展变体Relief-F能处理多分类问题。假定数据集D中的样本来自|y|个类别，对示例

x_i

，若它属于第k类，则Relief-F首先在第k类样本中寻找与

x_i

最近邻示例

x_{i,nh}

作为猜中近邻，然后在k类之外的每个类中找到一个

x_i

的最近邻作为其猜错近邻

x_{i,l,nm},l=1,2,...,|y|,l \neq k

。于是相关统计量对应于属性j的分量为：

\delta ^j=\sum_{i} -diff(x^j_i,x^j_{i,nh})^2+\sum_{l\neq k} p_l \times diff(x^j_i,x^j_{i,l,nm})^2

，

p_l

为第l类样本在数据集D中所占的比例。

包裹式选择

包裹式特征选择直接把最终要使用的学习器的性能作为特征子集的评价准则。

一般而言，由于包裹式特征选择方法直接针对给学习器进行优化，因此，从最终学习器性能来看，包裹式特征选择比过滤式特征选择更好，但另一方面，由于在特征选择过程中需多次训练学习器，因此包裹式特征选择的计算开销通常比过滤式特征选择大得多。

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

拉斯维加斯方法和蒙特卡罗方法是两个以著名赌城名字命名的随机化方法。两者的主要区别是，若有时间限制，则拉斯维加斯方法或者给出满足要求的解或者不给出解，而蒙特卡罗方法一定会给出解，虽然给出的解未必满足要求，若无时间限制，两者都能给出满足要求的解，

LVW算法描述：

输入：数据集D，特征集A，学习算法

\Im

，停止条件控制参数T

过程：

E=\infty

d=|A|

A^*=A

t=0

           while t < T do

               随机产生特征子集

A'

d'=|A'|

E'=CrossValidation(\Im (D^{A'}))

               if 

(E'<E)\vee ((E'=E)\wedge (d'<d))

 then

                   t=0

                   E=E'

                   d=d'

                   A*=A'

               else

                   t=t+1

               end if

           end while

输出：特征子集A*

由于LVW算法中特征子集搜索采用了随机策略，而每次特征子集评价都需要训练学习器，计算开销很大，因此算法设置了停止条件控制参数T。

嵌入式选择与L1正则化

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

给定数据集

D=\{(x_1,y_1),(x_2,y_2),...,(x_m,y_m)\}

，其中

x \in R^d

，

y \in R

。考虑最简单的线性回归模型，以平方误差为损失函数，则优化目标为：

min_{w} \sum_{i=1}^m(y_i-w^Tx_i)^2

当样本特征很多，而样本数相对较少时，很容易陷入过拟合，为了缓解过拟合问题，引入正则化项，若使用L2范数正则化，则有：

\min \limits_{w} \sum_{i=1}^m(y_i-w^Tx_i)^2+\lambda ||w||^2_2

其中正则化参数

\lambda >0

，上式称为岭回归。通过引入L2范数正则化，显著降低过拟合的风险。

将L2范数替换成Lp范数也是可以的，替换为L1范数，则：

\min \limits_{w} \sum_{i=1}^m(y_i-w^Tx_i)^2+\lambda ||w||_1

，其中正则化参数

\lambda >0

，上式称为LASSO(Least Absolute Shrinkage and Selection Operator)

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

岭回归是一种专用于线性数据分析的有偏估计回归方法，实质上是一种改良的最小二乘估计，通过放弃最小二乘法的无偏性，以损失部分信息降低精度为代价获得回归系数，更符合实际。更可靠的回归方法，对病态数据的拟合要强于最小二乘法。

L0范数是指向量中非0元素的个数

L1范数是指向量中各个元素绝对值之和

L2范数，指向量各元素的平方和再求平方根，让L2范数的正则项最小，可以使得W的每个元素都很小，都接近于0，但是不会让它等于0。

L2范数的好处：

（1）学习理论角度，L2范数可以防止过拟合，提升模型的泛化能力

（2）优化计算角度，L2范数有助于处理condition number不好的情况下矩阵求逆很困难的问题

L1范数结果不论扰动哪个特征，前后的变化都相同，平等的惩罚，按照同样的惩罚朝0前进，会导致稀疏的结果。

L2范数惩罚模型，不太可能有元素被置为0，值大的惩罚大，值小的惩罚小，元素朝0移动的速度越来越慢，一定程度上阻碍了稀疏性。

L1和L2都能防止过拟合，L1舍弃一些不重要的特征，L2控制所有特征的权重。

正则化：让模型简单，意味着要采取措施降低模型复杂度，过多参数会导致模型复杂，使用规则项来约束模型的特性，理解角度：

（1）经验风险=平均损失函数，结构风险=损失函数+正则化项（惩罚项），正则化是结构风险最小化的策略，正则化项一般是模型复杂度的单增函数，模型越复杂，正则化值越大

（2）正则化的引入利用了先验知识，体现了人对问题的理解的认知程度或者对解的估计，这样就可以将人堆该问题的理解和需求（先验知识）融入到模型的学习中，对模型参数设置先验，强行让学习到的模型具有人想要的特征，如稀疏，低秩平滑等等，L1正则是laplace先验，L2是高斯先验。

为什么要参数稀疏？特征选择问题的可解释性

（1）特征选择large-scale可能大部分的特征对最终输出的y无影响或者影响很小，训练时最小化目标函数，如果考虑这些特征会得到更小的误差，但是对新样本的预测结果产生影响，Lasso regularization的引入是为了完成特征自动选择，会在优化过程中自动去掉这些无用特征，把对应的特征置为0（L1）

（2）可解释性：例如回归问题，假设回归模型为

y=w_1x_1+w_2x_2+...+w_1000x_1000+b

，通过学习到的

w*

，只有很少的非0元素，大部分

w*

为0或者接近0.例如只有五个非0

w*

，那么可以认为y只接受这5个xi的影响，更有利于人们对问题的认识和分析，抓住影响问题的主要方面（因素），便符合认知习惯（L2）。

正则化的作用：（1）防止过拟合（平衡偏差和方差，拟合能力和泛化能力，结构风险与经验风险）（2）正则化导致的稀疏是有益的，特征选择以及把人们对问题的认知作为先验引入优化过程中（3）降低condition number，处理因其过大导致的不好求解的情况。

基于L1正则化的学习方法就是一种嵌入式特征选择方法，其特征选择过程与学习器训练过程融为一体，同时完成。

通过近端梯度下降（Proximal Gradient Descent，PGD）可以快速求解LASSO和其它基于L1范数最小化的方法。

稀疏表示和字典学习

当样本具有这样的稀疏表达形式时，对学习任务来说会有不少好处，例如，线性支持向量机之所以能在文本数据上有很好的性能，恰是由于文本数据在使用上述字频表示后具有高度稀疏性，使得大多数问题 变得线性可分。同时，稀疏样本并不会造成存储上的巨大负担，因为稀疏矩阵已有很多高效的存储方法。

为普通稠密表达的样本找到合适的字典，将样本转化为合适的稀疏表示形式，从而使学习任务得以简化，模型复杂度得以降低，通常称为字典学习（dictionary learning），亦称为稀疏编码。字典学习更侧重于学得字典的过程，而稀疏编码更侧重于对样本进行稀疏表达的过程。

给定数据集

\{x_1,x_2,...,x_m\}

，字典学习最简单的形式为：

\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\in R^{d \times k}

的字典矩阵，k为字典的词汇量，通常由用户指定，

\alpha _i\in R^k

则是样本

x_i\in R^d

的稀疏表示。上式的第一项希望由

\alpha _i

能很好地重构

x_i

，第二项则是希望

\alpha _i

尽量稀疏。

采用变量交替优化的策略来求解。

第一步，固定字典B，若将

\min \limits_{B,\alpha _i} \sum_{i=1}^m ||x_i-B\alpha _i||^2_2+\lambda \sum_{i=1}^m ||\alpha_i||_1

展开，发现其不设计

\alpha ^u_i\alpha ^v_i

这样的交叉项，于是可以参考LASSO的解法求解下式，从而为每个样本

x_i

找到相应的

\alpha _i

：

\min \limits_{\alpha _i}||x_i-B\alpha _i||^2_2+\lamdba ||\alpha _i||_1

第二步，以

\alpha _i

为初值来更新字典B，此时：

\min \limits_{B}||X-BA||^2_F

求解

\min \limits_{B}||X-BA||^2_F

常用的方法有基于逐列更新策略的KSVD，令

b_i

表示字典矩阵B的第i列，

\alpha ^i

表示稀疏矩阵A的第i行，则：

\min \limits_{B}||X-BA||^2_F = \min \limits_{b_i}||X-\sum_{j=1}^kb_j\alpha ^j||^2_F= \min \limits_{b_i} ||(X-\sum_{j\neq i}b_j\alpha ^j)-b_i\alpha _i ||^2_F

=\min \limits_{b_i}|| E_i-b_i\alpha ^i||^2_F

在更新字典的第i列时，其他各列都是固定的，因此

E_i=X-\sum_{j\neq i} b_j\alpha^j

是固定的，于是最小数上式只需要对Ei进行奇异值分解以取得最大奇异值所对应的正交向量。然而，直接对Ei进行奇异值分解会同时修改

b_i

和

\alpha ^i

，从而破坏A的稀疏性。为避免发生这种情况，KSVD对Ei和

\alpha ^i

进行专门处理：

\alpha ^i

仅保留非0元素，Ei仅保留了

b_i

和

\alpha ^i

的非零元素的乘积项，然后再进行奇异值分解，这样就保持了第一步所得到的稀疏性。

初始化字典矩阵B后反复迭代上述两步，最终可求得字典B和样本

x_i

的稀疏元素

\alpha ^i

，在上述字典学习过程中，用户能通过设置词汇量k的大小来控制字典的规模，从而影响到稀疏程度。

压缩感知

压缩感知关注的是如何利用信号本身所具有的稀疏性，从部分观测样本中恢复原信号。通常认为，压缩感知分为感知测量和重构恢复两个阶段。感知测量关注的是如何对原始信号进行处理以获得稀疏样本表示。重构恢复关注的是如何基于稀疏性从少量观测中恢复原信号，这是压缩感知的精髓。

在子集生成与搜索方面引入了很多人工智能搜索技术，如分支界限法，浮动搜索法等

在子集评价方法则采用了很多源于信息论的准则，如信息熵、AIC等。

参考：

1. 《机器学习》