焦作网站建设哪家权威,如何自学网站后台,小型手机网站建设多少钱,seo优化专员机器学习 第11章-特征选择与稀疏学习
11.1 子集搜索与评价
我们将属性称为“特征”(feature)#xff0c;对当前学习任务有用的属性称为“相关特征”(relevant feature)、没什么用的属性称为“无关特征”(irrelevant feature)。从给定的特征集合中选择出相关特征子集的过程对当前学习任务有用的属性称为“相关特征”(relevant feature)、没什么用的属性称为“无关特征”(irrelevant feature)。从给定的特征集合中选择出相关特征子集的过程称为“特征选择”(feature selection)。
特征选择是一个重要的“数据预处理”(data preprocessing)过程在现实机器学习任务中获得数据之后通常先进行特征选择此后再训练学习器。
特征选择过程必须确保不丢失重要特征否则后续学习过程会因为重要信息的缺失而无法获得好的性能。给定数据集若学习任务不同则相关特征很可能不同因此特征选择中所谓的“无关特征”是指与当前学习任务无关。有一类特征称为“冗余特征”(redundant feature)它们所包含的信息能从其他特征中推演出来。
冗余特征在很多时候不起作用去除它们会减轻学习过程的负担。但有时冗余特征会降低学习任务的难度例如若学习目标是估算立方体的体积则“底面积”这个冗余特征的存在将使得体积的估算更容易更确切地说若某个冗余特征恰好对应了完成学习任务所需的“中间概念”则该冗余特征是有益的。
对于子集搜索问题有三种基于贪心的策略
前向搜索将每个特征当做一个候选子集然后从当前所有的候选子集中选择出最佳的特征子集接着在上一轮选出的特征子集中添加一个新的特征同样地选出最佳特征子集最后直至选不出比上一轮更好的特征子集。
后向搜索类似于前向搜索但是每次是去掉一个无关特征。
双向搜索把前向和后向结合每次增加相关特征去除无关特征。
对于子集评价问题给定数据集 D D D假定 D D D中第 i i i类样本所占的比例为 p i ( i 1 , 2 , . . . , ∣ Y ∣ ) p_i(i1,2,...,|Y|) pi(i1,2,...,∣Y∣)。为便于讨论假定样本属性均为离散型。对属性子集 A A A假定根据其取值将 D D D分成了 V V V个子集 { D 1 , D 2 , . . . , D V } \{D^1,D^2,...,D^V\} {D1,D2,...,DV}每个子集中的样本在 A A A上取值相同于是我们可计算属性子集 A A A 的信息增益 G a i n ( A ) E n t ( D ) − ∑ v 1 V ∣ D v ∣ ∣ D ∣ E n t ( D v ) Gain(A)Ent(D)-∑^V_{v1}{|D^v|\over |D|}Ent(D^v) Gain(A)Ent(D)−v1∑V∣D∣∣Dv∣Ent(Dv) 其中信息熵定义为 E n t ( D ) − ∑ i 1 ∣ Y ∣ p k l o g 2 p k Ent(D)-∑^{|Y|}_{i1}p_klog_2p_k Ent(D)−i1∑∣Y∣pklog2pk 信息增益 G a i n ( A ) Gain(A) Gain(A)越大意味着特征子集 A A A包含的有助于分类的信息越多。于是对每个候选特征子集我们可基于训练数据集 D D D来计算其信息增益以此作为评价准则。
将特征子集搜索机制与子集评价机制相结合即可得到特征选择方法。
常见的特征选择方法大致可分为三类:过滤式(6lter)、包裹式(wrapper)和嵌入式(embedding)。
11.2 过滤式选择
过滤式方法先对数据集进行特征选择然后再训练学习器特征选择过程与后续学习器无关。
Relief(Relevant Features)是一种著名的过滤式特征选择方法该方法设计了一个“相关统计量”来度量特征的重要性。该统计量是一个向量其每个分量分别对应于一个初始特征而特征子集的重要性则是由子集中每个特征所对应的相关统计量分量之和来决定。
显然Relief的关键是如何确定相关统计量。给定训练集 { ( x 1 , y 1 ) ( x 2 , y 2 ) … 。 ( x m , y m ) } \{(x_1,y_1)(x_2,y_2)…。(x_m,y_m)\} {(x1,y1)(x2,y2)…。(xm,ym)}对每个示例 x i x_i xiRelief先在 x i x_i xi的同类样本中寻找其最近邻 x i , n h x_{i,nh} xi,nh称为“猜中近邻”(near-hit)再从KaTeX parse error: Expected group after _ at position 2: x_̲的异类样本中寻找其最近邻 x i , n m x_{i,nm} xi,nm称为“猜错近邻”(near-miss)然后相关统计量对应于属性j的分量为 δ j ∑ i − d i f f ( x i j , x i , n h j ) 2 d i f f ( x i j , x i , n m j ) 2 \delta ^j\sum_{i}-diff(x_i^j,x_{i,nh}^j)^2diff(x_i^j,x_{i,nm}^j)^2 δji∑−diff(xij,xi,nhj)2diff(xij,xi,nmj)2
Relief是为二分类问题设计的其扩展变体Relief-F能处理多分类问题。假定数据集 D D D中的样本来自 ∣ Y ∣ |Y| ∣Y∣个类别。对示例KaTeX parse error: Expected group after _ at position 2: x_̲若它属于第 k k k类 ( k ∈ { 1 , 2 , . . . , ∣ Y ∣ } (k∈\{1,2,...,|Y|\} (k∈{1,2,...,∣Y∣}则Relief-F先在第 k k k类的样本中寻找 x i x_i xi的最近邻示例 x i , n h x_{i,nh} xi,nh并将其作为猜中近邻然后在第 k k k类之外的每个类中找到一个 x i x_i xi的最近邻示例作为猜错近邻记为 x i , n m x_{i,nm} xi,nm ( l 1 , 2 , . … , ∣ Y ∣ ; l ≠ k ) (l1,2,.…,|Y|;l≠k) (l1,2,.…,∣Y∣;lk)。于是相关统计量对应于属性 j j j的分量为 δ j ∑ i − d i f f ( x i j , x i , n h j ) 2 ∑ l ≠ k ( p l ∗ d i f f ( x i j , x i , n m j ) 2 ) \delta ^j\sum_{i}-diff(x_i^j,x_{i,nh}^j)^2\sum_{l\neq k}(p_l*diff(x_i^j,x_{i,nm}^j)^2) δji∑−diff(xij,xi,nhj)2lk∑(pl∗diff(xij,xi,nmj)2)
11.3 包裹式选择
与过滤式特征选择不考虑后续学习器不同包裹式特征选择直接把最终将要使用的学习器的性能作为特征子集的评价准则。换言之包裹式特征选择的目的就是为给定学习器选择最有利于其性能、“量身定做”的特征子集
一般而言由于包裹式特征选择方法直接针对给定学习器进行优化因此从最终学习器性能来看包裹式特征选择比过滤式特征选择更好但另一方面由于在特征选择过程中需多次训练学习器因此包裹式特征选择的计算开销通常比过滤式特征选择大得多。
LVW是一种典型的包裹式特征选择方法。其在拉斯维加斯框架下使用随即策略来进行自己搜索并以最终分类器的误差为特征子集的评价准则。其算法描述如下图所示 需注意的是由于 LVW 算法中特征子集搜索采用了随机策略而每次特征子集评价都需训练学习器计算开销很大因此算法设置了停止条件控制参数T。然而整个 LVW 算法是基于拉斯维加斯方法框架若初始特征数很多(即4|很大)、T设置较大则算法可能运行很长时间都达不到停止条件。换言之若有运行时间限制则有可能给不出解。
11.4 嵌入式选择与 L 1 L_1 L1正则化
在过滤式和包裹式特征选择方法中特征选择过程与学习器训练过程有明显的分别与此不同嵌入式特征选择是将特征选择过程与学习器训练过程融为一体两者在同一个优化过程中完成即在学习器训练过程中自动地进行了特征选择。
给定数据集 D ( x 1 , y 1 ) ( x 2 , y 2 ) ⋯ ( x m , y m ) D{(x_1,y_1)(x_2,y_2)⋯(x_m,y_m)} D(x1,y1)(x2,y2)⋯(xm,ym)其中 x ∈ R d y ∈ R x∈R^dy∈R x∈Rdy∈R 我们考虑最简单的线性回归模型以平方误差为损失函数则优化目标为 m i n w ∑ i 1 m ( y i − w T x i ) 2 min_w∑^m_{i1}(yi−w^Txi)^2 minwi1∑m(yi−wTxi)2 当样本特征很多而样本数相对较少时很容易陷入过拟合。为了缓解过拟合问题可对引入正则化项。若使用 L 2 L_2 L2范数正则化则有 m i n w ∑ i 1 m ( y i − w T x i ) 2 λ ∣ ∣ w ∣ ∣ 2 2 min_w∑^m_{i1}(yi−w^Tx_i)^2λ||w||^2_2 minwi1∑m(yi−wTxi)2λ∣∣w∣∣22
可以使用别的 L p L_p Lp范数来替代原本的 L 2 L_2 L2范数如 L 1 L_1 L1范数。那么可以得到 m i n w ∑ i 1 m ( y i − w T x i ) 2 λ ∥ w ∥ 1 min_w∑^m_{i1}(yi−w^Tx_i)^2λ∥w∥_1 minwi1∑m(yi−wTxi)2λ∥w∥1 该式称为LASSO。
11.5 稀疏表示与字典学习
不妨把数据集 D考虑成一个矩阵其每行对应于一个样本每列对应于一个特征。特征选择所考虑的问题是特征具有“稀疏性”即矩阵中的许多列与当前学习任务无关通过特征选择去除这些列则学习器训练过程仅需在较小的矩阵上进行学习任务的难度可能有所降低涉及的计算和存储开销会减少学得模型的可解释性也会提高
现在我们来考虑另一种稀疏性D所对应的矩阵中存在很多零元素但这些零元素并不是以整列、整行形式存在的。
若给定一个稠密矩阵我们能通过某种方法找到其合适的稀疏表示可以使得学习任务更加简单高效我们称之为稀疏编码或字典学习。
给定一个数据集字典学习最简单的形式为 m i n B , α i ∑ i 1 m ∥ x i − B α i ∥ 2 2 λ ∑ i 1 m ∥ α i ∥ 1 min_{B,αi}∑^m_{i1}∥x_i−Bα_i∥^2_2λ∑^m_{i1}∥α_i∥_1 minB,αii1∑m∥xi−Bαi∥22λi1∑m∥αi∥1
11.6 压缩感知
在现实任务中我们常希望根据部分信息来恢复全部信息。例如在数据通讯中要将模拟信号转换为数字信号根据奈奎斯特(Nyquist)采样定理令采样频率达到模拟信号最高频率的两倍则采样后的数字信号就保留了模拟信号的全部信息换言之由此获得的数字信号能精确重构原模拟信号。然而为了便于传输、存储在实践中人们通常对采样的数字信号进行压缩这有可能损失一些信息而在信号传输过程中由于信道出现丢包等问题又可能损失部分信息。那么接收方基于收到的信号能否精确地重构出原信号呢压缩感知(compressed sensing)为解决此类问题提供了新的思路。
与特征选择、稀疏表示不同压缩感知关注的是如何利用信号本身所具有的稀疏性从部分观测样本中恢复原信号。通常认为压缩感知分为“感知测量”和“重构恢复”这两个阶段。“感知测量”关注如何对原始信号进行处理以获得稀疏样本表示这方面的内容涉及傅里叶变换、小波变换以及 11.5节介绍的字典学习、稀疏编码等不少技术在压缩感知提出之前就已在信号处理等领域有很多研究:“重构恢复”关注的是如何基于稀疏性从少量观测中恢复原信号这是压缩感知的精髓当我们谈到压缩感知时通常是指该部分。
