11.1 子集搜索与评价

子集搜索与评价的目的是找到具有关键特征的子集。

所以我们要从特征集合中挑选出相关特征子集，这个过程称为特征选择“feature selection”。这个特征选择是一个数据预处理(data processing)过程，在机器学习任务中，获得数据之后通常先进性特征选择，此后在训练学习器，为什么要进行特征选择呢？

• 1.减轻维数灾难问题，属性过多容易造成维数灾难问题。与PCA是处理高维数据的两大主流技术。
• 2.去除不相关特征往往会降低学习任务的难度，就像侦探破案，去掉纷繁复杂的因素，只留下关键的因素，往往更容易得到最终的真相

有的时候，冗余特征是有益的，例如，这个时候我们估算体积更容易。所以确切点说，如果冗余特征对应了学习任务的”中间概念“，则该冗余特征是有益的。

上述候选子集的方法中有两个重要的环节：如何根据评价结果获取下一个个候选子集？如何评价候选特征子集的好坏？

特征子集搜索

第一个环节是”子集搜索”(subset search)问题。给定特征集合，我们可以将每个特征看作一个候选子集，对这个候选单特征子集进行评价，假定最优，于是将作为第一轮的选定集；然后在上一轮的选定集中加入一个特征，构成包含两个特征的候选子集，假定在这个候选两特征子集中最优，且优于，于是将作为本轮的选定集；…假定在第轮时，最优的候选特征子集还不如上一轮的选定集，则停止生成候选子集，并将上一轮选定的特征集合作为特征选择结果。这样逐渐增减相关特征的策略称为”前向”(forward)搜索。
类似地，如果我们从完整的特征集合开始，每次尝试去掉一个无关特征，这样逐渐减少特征的策略称为”后向”(backward)搜索。
还可以将前向和后向搜索结合起来，每一轮增加选定相关特征（这些特征在后续轮中确定不会被去除）、同时减少无关特征，这样的策略称为”双向策略“。
但是，上述策略是贪心的。因为它们仅考虑了使本轮选定集最优，例如在第三轮假定选择优于，于是选定集为，然而在第四轮却可能是比所有的都更优（即：只考虑单个的最优问题，而不考虑特征组合起来的效果，会产生错误的评估）。遗憾的是，若不进行穷举搜索，这样的问题无法避免。

子集评价

第二个环节是”子集评价”(subset evaluation)问题。给定数据集，假定中第类样本所占的比例为。为便于讨论，假定样本属性均为离散型。对属性子集，假定根据其取值将分成了个子集，每个子集中的样本在上取值相同，于是我么可以计算属性子集的信息增益

解析：此为信息增益的定义式，对数据集和属性自己，假设根据的取值将分为了个子集，那么信息增益的定义为划分之前数据集的信息熵和划分之后每个子数据集的信息熵的差。熵用来衡量一个系统的混乱程度，因此划分前和划分后熵的差越大，表示划分越有效，划分带来的”信息增益”越大。

其中信息熵定义为

解析：此为信息熵的定义式，其中表示中第类样本所占的比例。可以看出，样本越纯，即时。越小，其最小值为0.此时必有

信息增益越大，意味着特征子集包含的有助于分类的信息越多，于是，对每个候选特征子集，我们可以基于训练集来计算其信息增益，以此作为评价准则。

特征选择方法

。例如：将前向搜索与信息熵结合，这与决策树算法非常相似。决策树树算法是可以用于特征选择的，树节点的划分属性所组成的集合就是选择出的特征子集。其他的一些特征选择方法不一定像决策树特征选择这么明显，但它们本质上都是显示或隐式地结合了某种（或多种）子集搜索机制和子集评价机制

11.2 过滤式选择

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

显然，Relief的关键是如何确定相关统计量，给定训练集,对每个示例,Relif先在的同类样本中寻找其最近邻称为“猜中近邻”(near-hit)，再从的异类样本中寻找最近邻，称为“猜错近邻”(near-miss)。然后，相关统计量对应于属性的分量为

其中表示样本在属性上的取值，取决于属性的类型；若属性为离散型，则时，，否则为1；若属性为连续型，则，注意已规范化到区间。

• 从上式可以看出，若与其猜中近邻在属性上的距离小于与其猜错近邻的距离，则说明属性对区分同类与异类样本时有益的，于是增大属性所对应的统计量分量；
• 反之，若与猜中错近邻在属性上的距离大于与猜错近邻的距离，说明属性起负面作用，于是减小属性所对应的统计量分量。
• 最后，对基于不同样本得到的估计结果进行平均，就得到各属性的相关统计量分量，分量值越大，则对应属性的分类能力就越强。

上式中的指出了用于平均的样本下标，实际上Relief只需在数据集的采样上而不必在整个数据集上估计相关统计量。显然，Relie的时间开销随采样次数及原始特征数线性增长，因此是一个运行效率很高的过滤式特征选择算法。
Relief是为二分类问题设计的，其扩展变体Relief-F能处理多分类问题。假定数据集中的样本来自个类别。对示例，若它属于第类()，则Relief-F先在第类的样本中寻找的最近邻示例并将其作为猜中近邻，然后再第类之外的每个类中找到一个的最近邻示例作为猜错近邻，记为。于是，相关统计量对应属性的分量为：

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

11.3 包裹式选择

与过滤式特征选择不考虑后续学习器不同，包裹式特征选择直接把最终要使用的学习器的性能作为特征子集的评价准则。换言之，包裹式特征选择的目的就是为给定学习器选择最有利于其性能、”量身定做”的特征子集。
一般而言，由于包裹式特征选择方法直接针对给定学习器进行优化，因此从最终学习器性能来看，包裹式特征选择比过滤式特征选择更好，另一方面，由于在特征选择过程中许多次训练学习器，因此包裹式特征选择的计算开销常比过滤式特征选择大得多。
LVW（Las Vegas Wrapper）是一个典型的包裹式特征选择方法。它在拉斯维加斯方法(Lass Vegas method)框架下使用随机策略来进行子集搜索，并以最终分类器的误差为特征子集评价准则，算法描述如下图所示。

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

上图算法第8行是通过在数据集上，使用交叉验证法来估计学习器的误差，注意这个误差是在仅考虑特征子集时得到的，即特征子集上的误差，若它比当前特征子集上的误差更小，或误差相当但中包含的特征数更少，则将保留下来。
需注意的是，由于LVW算法中特征子集搜索采用了随即策略，而每次特征子集评价都需要训练学习器，计算开销很大，因此算法设置了停止条件控制参数。然而，整个LVW算法是基于拉斯维加斯方法框架，若初始特征数很多（即很大）、T设置较大，则算法可能运行很长时间都达不到停止条件。换言之，若有运行时间限制，则有可能给不出解。

11.4 嵌入式选择与L正则化

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

给定数据集，其中，我们考虑最简单的线性回归模型，以平方误差为损失函数，则优化目标为

解析：该式为线性回归的优化目标式，表示样本的真实值，而表示其预测值，这里使用预测值和真实值差的平方衡量预测值偏离真实值的大小。

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

其中正则化参数。上面式子(2)称为”岭回归”（ridge regression），通过引入L范数正则化，确实能显著降低过拟合的风险。
那么，能否将正则化项中的L**范数替换为L**范数？答案是肯定的，若令，即采用L范数，则有：

其中正则化参数。式子（3）称为LASSO（Least Absolute Shrinkage and Selection Operator）。
L范数和L范数正则化都有助于降低过拟合风险，但前者还会带来一个额外的好处：它比后者更易获得”稀疏”(sparse)解，即它求得的会有更少的非零分量。

事实上，对施加”稀疏约束”（即希望的非零分量尽可能少）最自然的是使用L范数，但L范数不连续，因此常使用L范数来近似。

为了理解这一点，我们来看一个直观的例子：假定仅有两个属性，于是式子（2）和式子（3）解出的都只有两个分量，即，我们将其作为两个坐标轴，然后再图中绘制出式子（2）和式子（3）的第一项的”等值线”，即在空间中平方误差项取值相同的点的连线，再分别绘制出L范数和L范数的等值线，即在空间中L范数取值相同的点的连线，以及L范数取值相同的点的连线，如图所示。
式子（2）和（3）的解要在平方误差项与正则化项之间折中，即出现图中平方误差项等值线与正则化项等值线相交处。

由图可以看出，采用L范数时平方误差项等值线与正则化项等值线的交点常出现在坐标轴上，即或为0，而在采用L范数时，两者的交点常出现在某个象限中，即或均非0；换言之，采用L范数比L范数更易于得到稀疏解。
注意到取得稀疏解意味着初始的个特征中仅有对应着的非零分量的特征才会出现在最终模型中.于是,求解L范数正则化的结果就是得到了仅采用一部分初始特征的模型;换言之,基于L正则化的学习方法就是一种嵌入式特征选择方法,其特征选择过程与学习器训练过程融为一体,同时完成.
L正则化问题的求解可使用近端梯度下降(Proximal Gradient Descent,简称PGD).具体来收,令表示微分算子,对优化目标

若可导，且满足L-Lipschitz条件，即存在常数使得

则在附近可将通过二阶泰勒展开式近似为

其中是与无关的常数，表示内积。

解析：首先注意优化目标式和式子（3）LASSO回归的联系和区别，该式（6）中的对应到式（3）的w，即我们优化的目标。 什么是L-Lipschitz条件(https://zh.wikipedia.org/wiki/利普希茨连续)，根据维基百科的定义：它是一个比通常[连续]（https://zh/wikipedia.org/wiki/连续函数）更强的光滑性条件。 直觉上，利普希茨连续函数限制了函数改变的速度，符合利普希茨条件的函数的斜率，必小于一个称为利普希茨常数的实数（该常数依函数而定）。注意这里可能存在一个笔误，在wiki百科的定义中，式子（5）应当写成 移项得： 由于上式对所有得都成立，由导数的定义，上式可以看成是的二阶导数恒不大于。即 得到这个结论以后，我们来推导式子（6），由泰勒公式，附近的通过二阶泰勒展开式可近似为： 其中，

显然，式子（4）的最小值在如下获得：

这个很容易理解，因为L范数的最小值为0，当时，恒成立，同理，，因此反复迭代能使的值不断下降。

于是，若通过梯度下降法对进行最小化，则每一步梯度下降迭代实际上等价于最小化二次函数。将这个思想推广到式子(4)，则能类似地得到其每一步迭代应为

式子（7）是用来优化的，而对于式子（4），优化的函数为，由泰勒展开式，优化的目标可近似为，根据式子(6)可知，的更新式子由式子（8）决定。

即在每一步对进行梯度下降迭代的同时考虑L范数最小化。
对于式子（8），可先计算，然后求解

令表示的第个分量，将式子（9）按分量展开可看出，其中不存在这样的项，即的各分量互不影响，于是式子（9）有闭式解

其中与分别是与的第个分量。因此，通过能使LASSO和其他基于L范数最小化的方法得以快速求解。

解析：令优化函数 这个式子表明优化可以被拆解为优化的各个分量的形式，对分量，其优化函数 求导得 其中 称为符号函数[1],对于得特殊情况，由于在点处不光滑，所以其不可导，需单独讨论。令，有 此式得解即为优化目标的极值点，因为等式两端均含有未知变量，故分情况讨论。

• 1.当时：
  • 假设，则，那么有与假设矛盾；
  • 假设，则，那么有和假设相符合，下面来检验是否使函数取得最小值。当时，

在定义域内连续可导，则的二阶导数 由于L是Lipschitz常数恒大于0，所以是函数的最小值。

• 2.当时：
  • 假设，则，那么有与假设矛盾
  • 假设，则，那么有与假设相符，由上述二阶导数恒大于0可知，是的最小值。
• 3.当:
  • 假设，则，那么有与假设矛盾
  • 假设，则，那么有与假设矛盾
• 4.当时：此时
  • 当时，由上述推导可知的最小值在处取得，令

因此当时，不会是函数的最小值。

• 当时，对于任何，有

因此是的最小值点。 综上所述，式子（10）成立。

11.5 稀疏表示与字典学习

上面的数据集是一个矩阵，这个矩阵每行对应的是一个样本，每列对应的是一个特征。特征选择的目的是特征具有”稀疏性”，即矩阵中的许多列与当前学习任务无关，通过特征选择去除这些列。从而降低学习难度，减少计算和存储开销。

这样的稀疏表达形式，会给学习任务带来许多好处。由于文本数据在使用上述的字频表示后具有高度的稀疏性，使得大多数问题线性可分。同时，稀疏样本降低存储负担。
如果，我们的数据集是稠密的，那么如何。什么是恰当稀疏？比如：使用康熙字典（4万多字）出来的空列太多了，就是”过度稀疏”，使用现代汉语常用字表（3500字）得到的是”恰当稀疏”.
怎么转换？上面的是文本处理，我们可以使用《现代汉语常用子表》，在其他的分类任务（例如：图像处理）中，我们没有这个字典，所以我们需要学习出这个字典。

学习出这个字典的过程，称为”字典学习”（dictionary learning），亦称”稀疏编码”(sparse coding)。
给定数据集，字典学习最简单的形式为：

其中为字典矩阵，称为字典的词汇量，通常由用户指定，则是样本的稀疏表示。显然，上式（11）的第一项是希望由能很好地重构，第二项则是希望尽量稀疏。

解析:这个式子表达的意思很容易,即希望样本的稀疏表示通过字典重构后和样本的原始表示尽量相似,如果满足这个条件,那么稀疏表示是比较好的.后面的1范数项是为了使表示更加稀疏.

与LASSO相比，式子（11）显然很麻烦，因为除了要学习类似式子（3）中的，还需要学习字典矩阵。在LASSO的启发下，我们可以使用变量交替优化的策略求解式子（11）.
第一步，固定字典：
若将式子（11）按分量展开，可以看出不涉及这样的交叉项，于是可以参照LASSO的解法求解下式，从而为每个样本找到相应的:

解析:为了优化(11),我们采用变量交替优化的方式(有点类似EM算法),首先固定变量,则式子(11)求解的是个样本相加的最小值,因此公式里没有样本的交互(即文中所述这样的形式,因此可以对每个变量做分别的优化求出.求解方法见式子(9)(10)

第二步，固定住更新字典，此时式子（11）写为

其中是矩阵的Frobenius范数。

解析:这时优化(11)的第二步,固定住,此时(11)的第二项为一个常数,优化(11)即优化.其写成矩阵相乘的形式为,将2范数扩展到范数记得优化目标为

式子（13）有多种求解方法，常用的有基于逐列更新策略的KSVD。令表示字典矩阵的第列，表示稀疏矩阵的第行，式子（13）可重写为：

解析:这个公式的难点在于推导.大致的思路是会生成和矩阵同样维度的矩阵,这个矩阵对应位置的元素是中对应位置元素的一个分量,这样的分量矩阵一共有个,把所有分量矩阵加起来就得到了最终结果.推导过程如下: 求和可得: 得证.将矩阵分解成矩阵列带来一个好处,即和式子(12)的原理相同,矩阵列与列之间无关,因此可以分别优化各个列,即将转化成了,得到第三行的等式之后,再利用文中介绍的KSVD算法求解即可.

在更新字典的第列时，其他各列是固定的，因此是固定的，于是最小化式子（13）原则上只需对进行奇异值分解以取得最大奇异值所对应的正交向量.然而,直接对进行奇异值分解会同时修改和,从而可能破坏的稀疏性.
为了避免这种情况发生,KSVD对和进行专门处理:仅保留非零元素,仅保留与的非零元素的乘积项,然后再进行奇异值分解,这样就保持了第一步所得到的稀疏性.
初始化字典矩阵之后,反复迭代上述两部,最终即可求得字典和样本的稀疏表示.在上述字典学习过程中,用户能过设置词汇量的大小来控制字典的规模,从而影响到稀疏程度.

11.6 压缩感知

假设有长度为的离散信号，不妨假定我们以远小于奈奎斯特采样定理要求的采样率进行采样，得到长度为的采样后信号，即

其中是对信号的测量矩阵，它确定了以什么频率进行采样以及如何将采样样本组成采样后的信号。

一般答案是：不能还原，由于，因此上述方程是欠定方程。
现在不妨假设存在某个线性变换，使得可表示为，于是可表示为:

其中。于是，若能根据恢复出，则可通过来恢复出信号。
恢复这个逆问题仍是欠定的，但是，如果具有稀疏性，这个问题就能解决。此时式子中的称为稀疏基，而的作用类似于字典，能将信号转换为稀疏表示。
生活中常用的声音或图像频域上的稀疏信号。

例子

基于部分信息来恢复全部信息的技术在许多现实任务中有许多重要应用。例如网上书店通过收集读者在网上对书的评价，可根据读者的读书偏好来进行新书推荐，从而达到广告投放的效果。但是，网上书店所搜集到的只是部分信息，例如下表4位读者的网上评价信息（根据喜好程度评分，5分最高）。由于读者仅对读过的书给出评价，因此表中出现很多未知项”?”。
表格：客户对书的喜好程度评分

我们要想从目前的数据基于压缩感知的思想恢复出完整信号，前提条件之一是信号有稀疏表示。读书喜好数据是否存在稀疏表示呢？
答案是肯定的，一般情形下，读者对书籍的评价取决于题材、作者、装帧等多种元素，为简化讨论，假定表中的读者喜好评分仅与题材有关。《笑傲江湖》和《云海玉弓缘》是武侠小说，《万历十五年》和《人类的故事》是历史读物，《人间词话》属于诗词文学。一般来说，相似题材的书籍会有相似的读者，若能将书籍按题材归类，则题材总数必然远远少于书籍总数，因此从题材的角度来看，表中反应的信号是稀疏的，因此，可以通过类似压缩感知的思想加以处理。
矩阵补全（matrix completion）技术可用于解决这个问题，其形式为：

其中，表示需恢复的稀疏信号，表示矩阵的秩，是如上表读者评分矩阵这样的已观测信号；是中非”?”元素的下标的集合。上式的约束项明确指出，恢复出的矩阵中应当与观测到的对应元素相同。上式也是一个NP难问题，注意到在集合上的凸包是的”核函数”

其中表示的奇异值，即矩阵的核范数为矩阵的奇异值之和，于是可通过最小化矩阵核范数来近似求解式子



上式是一个凸优化问题，可通过半正定规划(Semi-Definite Programming，简称SDP)求解。理论研究表明，在满足一定条件时，若的秩为，则只需观察到个元素就能完美恢复出。