特征选择与稀疏学习

子集搜索与评价

魔门将属性称为”特征”，对当前学习任务有用的属性称为”相关特征”、没什么用的属性称为”无关特征”.从给定的特征集合中选择出相关特征子集的过程,称为”特征选择”。

特征选择是一个重要的”数据预处理”过程,在现实机器学习任务中，获得数据之后通常先进行特征选择，再训练学习器。

为什么要进行特征选择？

我们在现实任务中经常会遇到维数灾难问题，这是由于属性过多造成的,若能从中许纳泽出重要的特征,使得后续学习过程仅需在一部分特征上构建模型，则维数灾难问题会大大减轻
去除不相关特征往往会降低学习任务的难度

欲从初始的特征集合中选取一个包含了所有重要信息的特征子集,若没有任何领域知识作为先验假设,那就只好遍历所有可能的子集了;然而这在计算上却是不可行的,因为这样做会遭遇组合爆炸,特征个数稍多就无法进行了,可行的做法是产生一个”候选子集”,评价出它的好坏,基于评价结果产生下一个候选子集,再对其进行评估,…..这个过程持续进行下去,直至无法找到更好的候选子集为止。显然,这里涉及两个关键环节:如何根据评价结果获取下一个候选特征子集？如何评价候选特征子集的好坏？

第一个环节是”子集搜索”问题，三种策略：
前向搜索：初始将每个特征当做一个候选特征子集，然后从当前所有的候选子集中选择出最佳的特征子集；接着在上一轮选出的特征子集中添加一个新的特征，同样地选出最佳特征子集；最后直至选不出比上一轮更好的特征子集。
后向搜索：初始将所有特征作为一个候选特征子集；接着尝试去掉上一轮特征子集中的一个特征并选出当前最优的特征子集；最后直到选不出比上一轮更好的特征子集。
双向搜索：将前向搜索与后向搜索结合起来，即在每一轮中既有添加操作也有剔除操作。

第二个环节是”子集评价”问题
评价方法可以采用信息增益(决策树的技巧)

常见的特征选择大致分为三类:过滤式(filter)、包裹式(wrapper)和嵌入式(embedding)

过滤式选择

过滤式方法先对数据集进行特征选择,然后再训练学习器,特征选择过程与后续学习器无关.这相当于先用特征选择过程对初始特征进行”过滤”,再用过滤后的特征来训练模型.

Relief是一种著名的过滤式特征选择方法,该方法设计了一个”相关统计量”来度量特征的重要性.该统计量是一个向量,其每个分量分别对应于一个初始特征,而特征子集的重要性则是由子集中每个特征所对应的相关统计量分量之和来决定.于是,最终只需指定一个阈值r，然后选择比r大的相关统计量所对应的特征即可;也可指定欲选取的特征个数k,然后选择相关统计量分量最大的k个特征。

给定训练集${(x_1,y_1),(x_2,y_2),…(x_m,y_m)}$,对每个示例$x_i$,Relief先在$x_i$的同类样本中寻找其最近邻$x_{i,nh}$称为”猜中近邻”,再从$x_i$的异类样本中寻找其最近邻$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_a^j$表示样本$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]区间.

上面的Relief是为2分类问题设计的,其扩展变体Relief-F能处理多分类问题.

$\delta^j=\sum_i-diff(x_i^j,x_{i,nh}^j)^2+\sum_{l≠k}(p_l×diff(x_i^j,x_{i,l,nm}^j)^2)$

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

包裹式选择

与过滤式特征选择不考虑后续学习器不同,包裹式特征选择直接把最终将要使用的学习器的性能作为特征子集的评价准则。换言之,包裹式特征选择的目的就是为给定学习器选择最有利于其性能、”量身定做”的特征子集。

LVW是一个典型的包裹式特征选择方法.

上面的E是error(误差)。

嵌入式选择与L1正则化

给定数据集考虑最简单的线性回归模型，优化目标为:

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

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

$min_w\sum_{i=1}^m(y_i-w^Tx_i)^2+\lambda||w||_ 2^2$

也可以用L1范数

$min_w\sum_{i=1}^m(y_i-w^Tx_i)^2+\lambda||w||_ 1$

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

稀疏表示与字典学习

不妨把数据集D考虑成一个矩阵,其每行对应于一个样本,每列对应于一个特征.特征选择所考虑的问题是特征具有”稀疏性”,即矩阵中的许多列与当前学习任务无关,通过特征选择去除这些列,则学习器训练过程仅需在较小的矩阵上进行,学习任务的难度可能有所降低,涉及的计算和存储开销会减少,学得模型的可解释性也会提高.

当样本数据是一个稀疏矩阵时，对学习任务来说会有不少的好处，例如很多问题变得线性可分，储存更为高效等。这便是稀疏表示与字典学习的基本出发点。稀疏矩阵即矩阵的每一行/列中都包含了大量的零元素，且这些零元素没有出现在同一行/列，对于一个给定的稠密矩阵，若我们能通过某种方法找到其合适的稀疏表示，则可以使得学习任务更加简单高效，我们称之为稀疏编码（sparse coding）或字典学习（dictionary learning）。

西瓜书重读（十）