解析周志华《机器学习》之特征选择与稀疏学习

2019-10-20 本文已影响0人 LiBiscuit

我又上线啦！前几天收到简信，才知道小李在简书耍了一年啦！承蒙各位厚爱，小李还能坚持更新嘻嘻嘻！感恩！！现在的更新就随着组会的任务啦！
————————

特征选择

特征选择，从字面上来说就是选择特征，特征其实就是样本集的属性。我们在做一个学习任务的时候，应该有类似“取其精华，去其糟粕”的思想，也就是要选择对我们当前学习任务有用的属性留下来，没有用的属性丢弃。这里将有用的属性称之为相关特征，没有用的属性称之为无关特征。故，我们把从给定的特征集合中选择出相关子集的过程，称为特征选择。

举个例子：选择西瓜的时候，我们去掉无关特征，只留下了有用的根蒂和声音的特征。特征选择的优点：
（1）减轻维数灾难，在少数属性上构建模型
（2）降低学习难度，留下关键信息
需要注意的是，特征选择的过程中必须确保不丢失重要特征。
这里还有一个其他特征“冗余特征”
定义：如果属性Y=F(A,B,C,),且A,B,C属于属性集，那么Y是冗余特征。
exp1：如果属性4，可以用属性1和属性2综合表示出来，那么属性4为冗余特征。
exp2：体积V可以用长l,宽w,高h表示为V=F(l,w,h),那么V就是冗余特征
选择的时候是否需要去除冗余特征？→考虑“中间概念”
就比如说，学习目标是估算立方体体积，则“底面积”这个冗余特征的存在使得体积的估算更容易，这时候就可不去除。
子集搜索与评价

想从初始特征集合中选取一个包含了所有重要信息的特征子集，若没有相关领域的知识作为先验假设，那就只好遍历所有可能的子集了（穷举）；然而很明显，这在计算上是不可行的，因为这样做会组合爆炸，特征个数稍多一点就无法进行。因此，可行的做法是产生一个候选子集，评价出它的好坏，然后基于评价结果产生下一个候选子集，再进行评价，……以此类推，这个过程持续进行下去，直至无法找到更好的候选子集为止。

显然，有两个关键环节：
1.如何根据评价结果获取下一个候选特征子集?
2.如何评价候选特征子集的好坏?
第一个环节，涉及的是子集搜索。有三种搜集方法：前向搜索、后向搜索、双向搜索
给定一个特征集合 {a1，a2，...，ad} 将每个特征看成一个候选子集进行评价，假定a2 最优，把它作为第一轮的选定集；然后，在上一轮的选定集中加入一个特征，构成包含两个特征的候选子集。假定在这中 {a2，a4}最优，且优于 {a2}，于是将 {a2，a4} 作为本轮的选定集。假定在第 k+1 轮时，最优的候选 k+1特征子集不如上一轮的选定集，则停止生成候选子集，并将上一轮选定的 k 特征集合作为特征选择结果，这样逐渐增加相关特征的策略称为前向(fòrward) 搜索。
综上可以发现：这三种其实都是基于贪心策略即仅考虑使本轮选定集最优。
第二个环节即评价准则，这边采用信息增益。
信息增益越大，意味着特征子集包含的有助于分类的信息越多
信息熵来源于决策树，故与决策时联系：事实上，决策树就可以用于特征选择，树节点的划分属性所组成的特征集合就是选择出的特征子集。
特征选择的方法

将特征子集搜索机制与子集评价机制相结合，即可得到特征选择方法。
常见的方法大致可分为三类：
过滤式(fiter)、包裹式(wrapper)、嵌入式(embedding)

1.过滤式

过滤式：先对数据集进行特征选择，然后再训练学习器，特征选择过程与后续学习器无关。先用特征选择过程过滤原始数据，再用过滤后的特征来训练模型。
经典算法是：Relief
Relief的核心：引入“相关统计量”---度量特征重要性的向量，其中每个分量代表着相应特征的重要性，故我们可根据这个统计量各个分量的大小来选择出合适的特征子集。
具体：对于数据集中的每个样例xi，先找出与xi同类别的最近邻与不同类别的最近邻,称为猜中近邻(near-hit)与猜错近邻(near-miss),便可以分别计算出相关统计量中的每个分量。相关统计量对应于属性 j 的分量为: 实际上 Relief 是一个运行效率很高的过滤式特征选择算法。是专门为二分类问题设计的。其扩展变体 Relie-F 能处理多分类问题。
其中pl表示第l类样本在数据集中所占的比例，易知两者的不同之处在于：标准Relief 只有一个猜错近邻，而Relief-F有多个猜错近邻。
注：Relief只需在数据集的采样上而不必在这个数据集上估计相关统计量，且属于高效的过滤式特征选择算法。
2.包裹式

与过滤式特征选择不考虑后续学习器不同，包裹式特征选择直接把最终将要使用的学习器的性能作为特征子集的评价准则。换句话说，包裹式特征选择的目的就是为给定学习器选择最有利于其性能、"量身走做"的特征子集。
一般而言，由于包裹式特征选择方法直接针对给定学习器进行优化，因此从最终学习器性能来看，包裹式特征选择比过滤式特征选择更好；但另一方面，由于在特征选择过程中需多次训练学习器，因此包裹式特征选择的计算开销通常比过滤式特征边择大得多。
LVW (Las Vegas Wrapper) 是一个典型的包裹式特征选择方法。
它在拉斯维加斯方法(Las Vegas method) 框架下使用随机策略来进行子集搜索，并以最终分类器的误差为特征子集评价准则。
拉斯维加斯:采样越多，越有机会找到最优解，不一定会给出解，且给出的解一定是正确解。
exp: 有一把锁，100把钥匙，只有1把是对的。每次随机拿1把试，打不开就再换1把。试的次数越多，打开的机会就越大，但在打开之前，那些错的钥匙都是没有用的。
找钥匙—尽量找最好的，但不保证能找到。
具体：1.在循环的每一轮随机产生一个特征子集
2.在随机产生的特征子集通过交叉验证推断当前特征子集的误差
3.进行多次循环，在多个随机产生的特征子集中选择误差最小的特征子集作为最终解

3.嵌入式

在过滤式和包裹式特征选择方法中，特征选择过程与学习器训练过程有明显的分别；与此不同，嵌入式特征选择是将特征选择过程与学习器训练过程融为一体，两者在同一个优化过程中完成，即在学习器训练过程中自动地进行了特征选择。
以均方误差为损失函数,优化目标为:

样本特征很多,而样本数相对少，容易过拟合--------引入正则化项。

分析：L1范数是向量中每个元素的绝对值之和,在优化目标函数的过程中.会使w尽可能地小,起到了防止过拟合的作用,同时与L2范数不同的是,L1范数会使得部分w变为0,达到特征选择的效果。
对比：在0附近,L1的下降速度大于L2,L1能很快地下降到0,
L2在0附近的下降速度慢，因此较大可能收敛在0的附近。 L1正则化更易于得到稀疏(多数为零)解，w有更少的非0的分量，达到了特征选择的效果。
求解L1范数正则化的结果是得到了仅采用一部分初始特征的模型。
（PGD ：近端梯段下降）：转化为最小值求解：

稀疏学习

稀疏表示与字典学习

特征选择考虑的是特征具有稀疏性
(矩阵中许多列与当前学习任务无关，通过特征选择去除）
另一种稀疏性：
D所对应的矩阵中存在很多零元素，但这些零元素不是以整列、整行的形式存在的。
故稀疏表示其实就是用尽可能少的资源表示尽可能多的有用的知识
优势：数据具有稀疏性，使得问题变为线性可分。
问题来了-----若给定数据集是稠密的，即普通非稀疏数据，能否转化为“稀疏表示”的形式？（稀疏为恰当稀疏）
这个时候我们寻找一个合适的字典，也就是采用字典学习。
求解：借鉴LASSO→交替优化的策略
经典算法：K-SVD
核心思想：最大不同在字典更新，K-SVD对误差矩阵进行奇异值分解，取最大奇异值对应的正交向量更新字典的一个原子，同时并更新其稀疏系数，直到所有原子更新完毕，重复迭代几次即可得到优化的字典和稀疏系数。【总结：K次迭代，且每一次迭代都要使用SVD分解】具体流程：
压缩感知

在现实任务中，我们常希望根据部分信息来恢复全部信息。然而在现实中，总有各种信息的损失存在。那么基于收到的信号，能否精确地重构出原信号呢？压缩感知(compressed sensing) 为解决此类问题提供了新的思路。
与特征选择、稀疏表示不同，压缩感知关注的是如何利用信号本身所具有的稀疏性，从部分观测样本中恢复原信号。
通常认为，压缩感知分为感知测量和重构恢复这两个阶段。
感知测量：关注如何对原始信号进行处理以获得稀疏样本表示；
重构恢复：关注的是如何基于稀疏性从少量观测中恢复原信号，这是压缩感知的精髓。

数学表达：
举个例子：【A为原图，D为从C重构的】
求解：
y=ΦΨs，把ΦΨ合并成一个矩阵，称之为传感矩阵。
即令Θ=ΦΨ ，则y=ΘS。
问题即为：已知y和Θ，求解S。
求解S后：由x=Ψs即可得到恢复出的原信号x。
然而在正常情况下，方程的个数远小于未知数的个数，方程是没有确定解的，无法重构信号。但是，由于信号是K稀疏，若Φ满足有限等距性质(RIP)，则K个系数就能够从M个测量值准确重构（得到一个最优解）。