特征选择笔记

  |     |   本文总阅读量:

版权声明:本文原创,转载请留意文尾,如有侵权请留言, 谢谢

引言

  和降维类似,特征选择(Feature Selection)也是一个处理高维数据的主流技术,本文主要记录了过滤式、包裹式和嵌入式三种特征选择方法。
  为了方便起见,本文假定数据中不涉及冗余特征,都为离散型,并且假定初试的特征集合包含了所有的重要信息。

子集搜索与子集评价

  特征选择的过程其实也就是从初始的特征集和中选取一个包含了所有重要信息的特征子集。遍历所有的子集显然不可行,所以特征选择通常这是一个迭代的过程,先产生一个候选子集,评价出它的好坏,基于评价结果产生下一个候选子集,再对其进行评价,持续进行这个过程,直至无法找到更好的候选子集为止。这个过程通常也包括两个部分,即子集搜索和子集评价。
  子集搜索主要有两种方法,前向(forward)搜索和后向(backward)搜索。前者是不断尝试给特征子集加入新的特征直到最优,后者是不断尝试给特征子集去掉一个无关特征直到最优。其实还有两者相结合的双向(bidirectional)搜索,即每一轮逐渐增加选定相关特征(这些特征在后续轮中不会被去除),同时减少无关特征。本质上这几种方法都是贪心的,因为它们仅考虑使本轮选定集最优。
  子集评价即是判断这个特征子集的效果如何了。记给定数据集\(D\)中第\(i\)类样本所占的比例为\(p_{i}(i=1,2, \ldots,|\mathcal{Y}|)\),对属性子集\(A\),根据其取值将\(D\)分成了\(V\)个子集\(\left\{D^{1}, D^{2}, \ldots, D^{V}\right\}\),每个子集中的样本在\(A\)上取值相同。计算子集\(A\)的信息增益为: \[ \operatorname{Gain}(A)=\operatorname{Ent}(D)-\sum_{v=1}^{V} \frac{\left|D^{v}\right|}{|D|} \operatorname{Ent}\left(D^{v}\right) \\ \operatorname{Ent}(D)=-\sum_{i=1}^{|\mathcal{Y}|} p_{k} \log _{2} p_{k} \]   信息增益\(Gain(A)\)越大,意味着特征子集\(A\)包含有助于分类的信息越多。
  更一般的,特征子集\(A\)实际上确定了对数据集\(D\)的一个划分,每个划分区域对应着\(A\)上的一个取值,而样本标记信息\(y\)则对应着对\(D\)的真实划分,通过估算这两个划分的差异,就能对\(A\)进行评价。与\(Y\)对应的划分的差异越小,则说明\(A\)越好。信息嫡仅是判断这个差异的一种途径,其他能判断两个划分差异的机制都能用于特征子集评价。
  将特征子集搜索机制与子集评价机制相结合,即可得到特征选择方法。例如将前向搜索与信息嫡相结合,这显然与决策树算法非常相似.事实上,决策树可用于特征选择,树结点的划分属性所组成的集合就是选择出的特征子集.其他的特征选择方法未必像决策树特征选择这么明显,但它们在本质上都是显式或隐式地结合了某种(或多种)子集搜索机制和子集评价机制,常见的特征选择方法大致可分为三类:过滤式(filter)、包裹式(wrapper)和 嵌入式(embedding)。

过滤式选择

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

Relief(Relevant Features)

  Relief(Relevant Features)是一种著名的过滤式特征选择方法,该方法设计了一个相关统计量来度量特征的重要性,该统计量是一个向量,其每个分量分别对应于一个初始特征,而特征子集的重要性则是由子集中每个特征所对应的相关统计量分量之和来决定。最终只需指定一个阈值\(\tau\),然后选择比\(\tau\)大的相关统计量分量所对应的特征即可。也可指定欲选取的特征个数\(k\),然后选择相关统计量分量最大的\(k\)个特征。
  显然,Relief的关键是如何确定相关统计量。对每个示例\(\boldsymbol{x}_i\),Relief先在\(\boldsymbol{x}_i\)的同类样本中寻找其最近邻\(\boldsymbol{x}_{i,nh}\),称为“猜中近邻”(near-hit),再从\(\boldsymbol{x}_i\)的异类样本中寻找其最仅邻\(\boldsymbol{x}_{i,nm}\),称为“猜错近邻”(near-miss),然后,相关统计量对应于属性\(j\)的分量为: \[ \delta^{j}=\sum_{i}-\operatorname{diff}\left(x_{i}^{j}, x_{i, \mathrm{nh}}^{j}\right)^{2}+\operatorname{diff}\left(x_{i}^{j}, x_{i, \mathrm{nm}}^{j}\right)^{2} \]   其中\(x_a^j\)表示样本\(\boldsymbol{x}_{a}\)在属性\(j\)上的取值,\(\operatorname{diff}\left(x_{a}^{j}, x_{b}^{j}\right)\)取决于属性\(j\)的类型:

  • 若属性\(j\)为离散型,则\(x_{a}^{j} = x_{b}^{j}\)\(\operatorname{diff}\left(x_{a}^{j}, x_{b}^{j}\right)=0\),否则为1。
  • 若属性\(j\)为连续型, \(\operatorname{diff}\left(x_{a}^{j}, x_{b}^{j}\right)=| x_{a}^{j}-x_{b}^{j}\),其中\(x_{a}^{j}\)\(x_{b}^{j}\)已规范化到\([0,1]\)区间。

  分析下上式可以得出,若\(\boldsymbol{x}_i\)与其猜中近邻\(\boldsymbol{x}_{i,nh}\)在属性\(j\)上的距离小于\(\boldsymbol{x}_{i}\)与其猜错近邻\(\boldsymbol{x}_{i,nm}\)的距离,则说明属性\(j\)对区分同类与异类样本是有益的,于是增大属性\(j\)所对应的统计量分量;反之,则说明属性\(j\)起负面作用,于是减小属性\(j\)所对应的统计量分量。最后,对基于不同样本得到的估计结果进行平均,就得到各属性的相关统计量分量,分量值越大,则对应属性的分类能力就越强。
  上式中的\(i\)指出了用于平均的样本下标,实际上Relief只需在数据集的采样上而不必在整个数据集上估计相关统计量。显然,Relief的时间开销随采样次数以及原始特征数线性增长,因此是一个运行效率很高的过滤式特征选择算法。

Relief-F

  Relief是为二分类问题设计的,其变体Relief-F能处理多分类问题。假定数据集D中的样本来自\(|\mathcal{Y}|\)个类别。对示例\(\boldsymbol{x}_{i}\),若它属于第\(k\)类,则Relief-F先在第\(k\)类的样本中寻找\(\boldsymbol{x}_{i}\)的最近邻示例\(\boldsymbol{x}_{i,nh}\)并将其作为猜中近邻,然后在第\(k\)类之外的每个类中找到一个\(\boldsymbol{x}_{i}\)的最近邻示例作为猜错近邻,记为\(\boldsymbol{x}_{i, l, \mathrm{nm}}(l=1,2, \ldots,|\mathcal{Y}| ; l \neq k)\),相关统计量对应于属性\(j\)的分量为: \[ \delta^{j}=\sum_{i}-\operatorname{diff}\left(x_{i}^{j}, x_{i, \mathrm{nh}}^{j}\right)^{2}+\sum_{l \neq k}\left(p_{l} \times \operatorname{diff}\left(x_{i}^{j}, x_{i, l, \mathrm{nm}}^{j}\right)^{2}\right) \]   其中\(pl\)为第\(l\)类样本在数据集\(D\)中所占的比例。

包裹式选择

  与过滤式特征选择不考虑后续学习器不同,包裹式特征选择直接把最终将要使用的学习器的性能作为特征子集的评价准则。换言之,包裹式特征选择的目的就是为给定学习器选择最有利于其性能的特征子集。
  一般而言,由于包裹式特征选择方法直接针对给定学习器进行优化,因此从最终学习器性能来看,包裹式特征选择比过滤式特征选择更好,但另一方面,由于在特征选择过程中需多次训练学习器,因此包裹式特征选择的计算开销通常比过滤式特征选择大得多。

LVW(Las Vegas Wrapper)

  LVW是一个典型的包裹式 特征选择方法.它在拉斯维加斯方法(Las Vegas method)框架下使用随机策略来进行子集搜索,并以最终分类器的误差为特征子集评价准则,伪代码如下所示:

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

  由于LVW算法中特征子集搜索采用了随机策略,而每次特征子集评价都需训练学习器,计算开销很大,因此算法设置了停止条件控制参数\(T\)。然而,整个LVW算法是基于拉斯维加斯方法框架,若初始特征数很多,\(T\)设置较大,则算法可能运行很长时间都达不到停止条件,若有运行时问限制,则有可能给不出解。

嵌入式选择

  在过滤式和包裹式特征选择方法中,特征选择过程与学习器训练过程有明显的分别。与此不同,嵌入式特征选择是将特征选择过程与学习器训练过程融为一体,两者在同一个优化过程中完成,即在学习器训练过程中自动地进行了待征选择。
  以平方误差为损失函数,则优化目标为: \[ \min _{\boldsymbol{w}} \sum_{i=1}^{m}\left(y_{i}-\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}\right)^{2} \]   当样本特征很多,而样本数相对较少时,上式很容易陷入过拟合,因此我们需要引入正则化项,可以引入\(L_p\)范数,若\(p=2\)即采用\(L_2\)范数正则化,则有: \[ \min _{\boldsymbol{w}} \sum_{i=1}^{m}\left(y_{i}-\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}\right)^{2}+\lambda\|\boldsymbol{w}\|_{2}^{2} \]   若\(p=1\)即采用\(L_1\)范数正则化: \[ \min _{\boldsymbol{w}} \sum_{i=1}^{m}\left(y_{i}-\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}\right)^{2}+\lambda\|\boldsymbol{w}\|_{1} \]   其中正则化参数\(\lambda \gt 0\),上式也称为LASSO(Least Absolute Shrinkage and Selection Operator)。
  \(L_1\)范数和\(L_2\)范数正则化都有助于降低过拟合风险,但前者还会带来一个额外的好处,它比后者更易于获得稀疏解,即它求得的\(w\)会有更少的非零分量。举个例子:假定\(\boldsymbol{x}\)仅有两个属性,于是是用\(L_1\)范数或\(L_2\)范数解出的,都只有两个分量\((w_1,w_2)\),将其作为两个坐标轴,然后在图中绘制出平方误差损失函数的第一项的等值线,即在\((w_1,w_2)\)空间中平方误差项取值相同的点的连线,再分别绘制出\(L_1\)范数和\(L_2\)范数的等值线,即在\((w_1,w_2)\)空间中\(L_1\)范数取值相同的点的连线和在\((w_1,w_2)\)空间中\(L_2\)范数取值相同的点的连线。

  我们要求的解要在平方误差项与正则化项之间折中,即出现在图中平方误差项等值线与正则化项等值线相交处,由上图可看出,采用\(L_1\)范数平方误差项等值线与正则化项等值线的交点常出现在坐标轴上,即\(w_1\)\(w_2\)为0,而在采用\(L_2\)范数时,两者的交点常出现在某个象限中,即\(w_1\)\(w_2\)均非0,换言之,采用\(L_1\)范数比\(L_2\)范数更易于得到稀疏解。

其实对\(\boldsymbol{w}\)施加稀疏约束最好的是使用\(L_o\)范数,但因为\(L_o\)范数不连续,所以常用\(L_1\)范数来近似。

  \(\boldsymbol{w}\)取得稀疏解意味着初始的\(d\)个特征中仅有对应着\(\boldsymbol{x}\)的非零分量的特征才会出现在最终模型中,于是,求解\(L_1\)范数正则化的结果是得到了仅采用一部分初始特征的模型。也就是说,基于\(L_1\)正则化的学习方法就是一种嵌入式特征选择方法,其特征选择过程与学习器训练过程融为一体,同时完成。

PGD

  \(L_1\)正则化问题的求解可使用近端梯度下降(Proximal Gradient Descent, PGD)。令\(\nabla\)表示微分算子,优化目标: \[ \min _{x} f(x)+\lambda\|x\|_{1} \]   若\(f(x)\)可导,且\(\nabla f\)满足\(L\)-Lipschitz条件,即存在常数\(L \gt 0\)使得: \[ \left\|\nabla f\left(\boldsymbol{x}^{\prime}\right)-\nabla f(\boldsymbol{x})\right\|_{2}^{2} \leqslant L\left\|\boldsymbol{x}^{\prime}-\boldsymbol{x}\right\|_{2}^{2} \quad\left(\forall \boldsymbol{x}, \boldsymbol{x}^{\prime}\right) \]   则在\(\boldsymbol{x}_k\)附近可将\(f(\boldsymbol{x})\)通过二阶泰勒展式近似为: \[ \begin{aligned} \hat{f}(x) & \simeq f\left(\boldsymbol{x}_{k}\right)+\left\langle\nabla f\left(\boldsymbol{x}_{k}\right), \boldsymbol{x}-\boldsymbol{x}_{k}\right\rangle+\frac{L}{2}\left\|\boldsymbol{x}-\boldsymbol{x}_{k}\right\|^{2} \\ &=f\left(\boldsymbol{x}_{k}\right)+\left\langle\nabla f\left(\boldsymbol{x}_{k}\right), \boldsymbol{x}-\boldsymbol{x}_{k}\right\rangle+\left\langle\frac{L}{2}\left(\boldsymbol{x}-\boldsymbol{x}_{k}\right), \boldsymbol{x}-\boldsymbol{x}_{k}\right\rangle \\ &= f\left(\boldsymbol{x}_{k}\right)+\left\langle\nabla f\left(\boldsymbol{x}_{k}\right)+\frac{L}{2}\left(\boldsymbol{x}-\boldsymbol{x}_{k}\right), \boldsymbol{x}-\boldsymbol{x}_{k}\right\rangle \\ &= f\left(\boldsymbol{x}_{k}\right)+\frac{L}{2}\left\langle\frac{2}{L} \nabla f\left(\boldsymbol{x}_{k}\right)+\left(\boldsymbol{x}-\boldsymbol{x}_{k}\right), \boldsymbol{x}-\boldsymbol{x}_{k}\right\rangle \\ &= f\left(\boldsymbol{x}_{k}\right)+\frac{L}{2}\left\langle \boldsymbol{x}-\boldsymbol{x}_{k}+\frac{1}{L} \nabla f\left(\boldsymbol{x}_{k}\right)+\frac{1}{L} \nabla f\left(\boldsymbol{x}_{k}\right), \boldsymbol{x}-\boldsymbol{x}_{k}+\frac{1}{L} \nabla f\left(\boldsymbol{x}_{k}\right)-\frac{1}{L} \nabla f\left(\boldsymbol{x}_{k}\right)\right\rangle \\ &=f\left(\boldsymbol{x}_{k}\right)+\frac{L}{2}\left\|\boldsymbol{x}-\boldsymbol{x}_{k}+\frac{1}{L} \nabla f\left(\boldsymbol{x}_{k}\right)\right\|_{2}^{2}-\frac{1}{2 L}\left\|\nabla f\left(\boldsymbol{x}_{k}\right)\right\|_{2}^{2} \\ &=\frac{L}{2}\left\|\boldsymbol{x}-\left(\boldsymbol{x}_{k}-\frac{1}{L} \nabla f\left(\boldsymbol{x}_{k}\right)\right)\right\|_{2}^{2}+const \qquad (因为f\left(\boldsymbol{x}_{k}\right)和\nabla f\left(\boldsymbol{x}_{k}\right)是常数) \end{aligned} \]   显然,上式的最小值在如下\(\boldsymbol{x}_{k+1}\)获得: \[ \boldsymbol{x}_{k+1}=\boldsymbol{x}_{k}-\frac{1}{L} \nabla f\left(\boldsymbol{x}_{k}\right) \]   于是,若通过梯度下降法对\(f(\boldsymbol{x})\)进行最小化,则每一步梯度下降迭代实际上等价于最小化二次函数\(\hat{f}(\boldsymbol{x})\)。将这个思想推广到优化目标,则每一步迭代应为: \[ \boldsymbol{x}_{k+1}=\underset{\boldsymbol{x}}{\arg \min } \frac{L}{2}\left\|\boldsymbol{x}-\left(\boldsymbol{x}_{k}-\frac{1}{L} \nabla f\left(\boldsymbol{x}_{k}\right)\right)\right\|_{2}^{2}+\lambda\|\boldsymbol{x}\|_{1} \]   即在每一步对\(f(\boldsymbol{x})\)进行梯度下降迭代的同时考虑\(L_1\)范数最小化。对于\(\boldsymbol{x}_{k+1}\),可先计算\(\boldsymbol{z}=\boldsymbol{x}_{k}-\frac{1}{L} \nabla f\left(\boldsymbol{x}_{k}\right)\),然后再解: \[ \boldsymbol{x}_{k+1}=\underset{\boldsymbol{x}}{\arg \min } \frac{L}{2}\|\boldsymbol{x}-\boldsymbol{z}\|_{2}^{2}+\lambda\|\boldsymbol{x}\|_{1} \]   令\(x^i\)表示\(\boldsymbol{x}\)的第\(i\)个分量,将上式按分量展开可看出,其中不存在\(x^{i} x^{j}(i \neq j)\)这样的项,即\(\boldsymbol{x}\)的各分量互不影响,于是上式可以通过求导得到闭式解: \[ x_{k+1}^{i}=\left\{\begin{array}{ll}{z^{i}-\lambda / L,} & {\lambda / L<z^{i}} \\ {0,} & {\left|z^{i}\right| \leqslant \lambda / L} \\ {z^{i}+\lambda / L,} & {z^{i}<-\lambda / L}\end{array}\right. \]   其中\(x^i_{k+1}\)\(z^i\)分别是\(\boldsymbol{x}_{k+1}\)\(\boldsymbol{z}\)的第\(i\)个分量。因此,通过PGD能使LASSO和其他基于\(L_1\)范数最小化的方法得以快速求解。

字典学习(Dictionary Learning)

  把数据集D考虑成一个矩阵,其每行对应于一个样本,每列对应于一个特征。特征选择所考虑的问题是特征具有“稀疏性”,即矩阵中的许多列与当前学习任务无关,通过特征选择去除这些列,则学习器训练过程仅需在较小学习的矩阵上进行,学习任务的难度可能有所降低,涉及的计算和存储开销会减少,学得模型的可解释性也会提高。
  考虑另一种稀疏性:\(D\)所对应的矩阵中存在很多零元素,但这些零元素并不是以整列、整行形式存在的。在不少现实应用中我们会遇到这样的情形,例如在文档分类任务中,通常将每个文档看作一个样本,每个字作为一个特征,字在文档中出现的频率或次数作为特征的取值。假设一个汉语字典里共有47035个汉字,这意味着该矩阵可有4万多列,然而,给定一个文档,相当多的字是不出现在这个文档中的,于是矩阵的每一行都有大量的零元素。对不同的文档,零元素出现的列往往很不相同。 。
  当样本具有这样的稀疏表达形式时,对学习任务来说会有不少好处,例如线性支持向量机之所以能在文本数据上有很好的性能,恰是由于文本数据在使用上述的字频表示后具有高度的稀疏性,使大多数问题变得线性可分。同时,稀疏样本并不会造成存储上的巨大负担,因为稀疏矩阵己有很多高效的存储方法。
  那么,若给定数据集\(D\)是稠密的,即普通非稀疏数据,我们需要将其转化为稀疏表示(Sparse Representation)形式,从而享有稀疏性所带来的好处。需注意的是,我们所希望的稀疏表示是恰当稀疏,而不是“过度稀疏”。显然,在一般的学习任务中(例如图像分类)并没有汉语字典可用,我们需学习出这样一个“字典”,为普通稠密表达的样本找到合适的字典,将样本转化为合适的稀疏表示形式,从而使学习任务得以简化,模型复杂度得以降低,这就是字典学习(Dictionary Learning),也称稀疏编码(Sparse Coding)。这两个称谓稍有差别,字典学习更侧重于学得字典的 过程,而稀疏编码则更侧重于对样本进行稀疏表达的过程。由于两者通常是在同一个优化求解过程中完成的,因此下面我们不做进一步区分,笼统地称为字典学习。
  字典学习最简单的形式为: \[ \min _{\mathbf{B}, \boldsymbol{\alpha}_{i}} \sum_{i=1}^{m}\left\|\boldsymbol{x}_{i}-\mathbf{B} \boldsymbol{\alpha}_{i}\right\|_{2}^{2}+\lambda \sum_{i=1}^{m}\left\|\boldsymbol{\alpha}_{i}\right\|_{1} \]   其中\(\mathbf{B} \in \mathbb{R}^{d \times k}\)为字典矩阵,\(k\)称为字典的词汇量,通常由用户指定,\(\boldsymbol{\alpha}_{i} \in \mathbb{R}^{k}\)则是样本\(\boldsymbol{x}_{i} \in \mathbb{R}^{d}\)的稀疏表示。显然,上式的第一项是希望\(\boldsymbol{\alpha}_{i}\)能很好地重构\(\boldsymbol{x}_{i}\),第二项则是希望\(\boldsymbol{\alpha}_{i}\)尽量稀疏。
  与LASSO相比,除了\(\boldsymbol{\alpha}_{i}\),还需学习字典矩阵\(\mathbf{B}\)。不过,受LASSO的启发,我们可采用变量交替优化的策略来求解式上式,首先在第一步,我们固定住字典\(\mathbf{B}\),将上式按分量展开,可看出其中不涉及\(\alpha_{i}^{u} \alpha_{i}^{v}(u \neq v)\)这样的交叉项,于是可参照LASSO的解法求解下式,从而为每个样本\(\boldsymbol{x}_{i}\)找到相应的\(\boldsymbol{\alpha}_{i}\)\[ \min _{\boldsymbol{\alpha}_{i}}\left\|\boldsymbol{x}_{i}-\mathbf{B} \boldsymbol{\alpha}_{i}\right\|_{2}^{2}+\lambda\left\|\boldsymbol{\alpha}_{i}\right\|_{1} \]   接着,我们固定住\(\boldsymbol{\alpha}_{i}\)来更新字典\(\mathbf{B}\)\[ \min _{\mathbf{B}}\|\mathbf{X}-\mathbf{B A}\|_{F}^{2} \]   其中\(\mathbf{X}=\left(\boldsymbol{x}_{1}, \boldsymbol{x}_{2}, \ldots, \boldsymbol{x}_{m}\right) \in \mathbb{R}^{d \times m}\)\(\mathbf{A}=\left(\boldsymbol{\alpha}_{1}, \boldsymbol{\alpha}_{2}, \ldots, \boldsymbol{\alpha}_{m}\right) \in \mathbb{R}^{k \times m}\)\(\|\cdot\|_{F}\)是矩阵的Frobenius范数。上式有多种求解方法,常用的有基于逐列更新策略的KSVD [Aharon et al., 2006j.令\(\boldsymbol{b}_{i}\)表示字典矩阵\(\mathbf{B}\)的第\(i\)列,\(\boldsymbol{\alpha}_{i}\)表示稀疏矩阵\(\mathbf{A}\)的第\(i\)行,上式重写为: \[ \begin{aligned} \min _{\mathbf{B}}\|\mathbf{X}-\mathbf{B} \mathbf{A}\|_{F}^{2} &=\min _{\boldsymbol{b}_{i}}\left\|\mathbf{X}-\sum_{j=1}^{k} \boldsymbol{b}_{j} \boldsymbol{\alpha}^{j}\right\|_{F}^{2} \\ &=\min _{\boldsymbol{b}_{i}}\left\|\left(\mathbf{X}-\sum_{j \neq i} \boldsymbol{b}_{j} \boldsymbol{\alpha}^{j}\right)-\boldsymbol{b}_{i} \boldsymbol{\alpha}^{i}\right\|_{F}^{2} \\ &=\min _{\boldsymbol{b}_{i}}\left\|\mathbf{E}_{i}-\boldsymbol{b}_{i} \boldsymbol{\alpha}^{i}\right\|_{F}^{2} \end{aligned} \]   在更新字典的第\(i\)列时,其他各列都是固定的,因此\(\mathbf{E}_{i}=\sum_{j \neq i} \boldsymbol{b}_{j} \boldsymbol{\alpha}^{j}\)是固定的,于是最小化上式原则上只需对\(\mathbf{E}_{i}\)进行奇异值分解以取得最大奇异值所对应的正交向量。然而直接对\(\mathbf{E}_{i}\)进行奇异值分解会同时修改\(\boldsymbol{b}_{i}\)\(\boldsymbol{\alpha}_{i}\),从而可能破坏\(\mathbf{A}\)的稀疏性。为避免发生这种情况,KSVD对\(\mathbf{E}_{i}\)\(\boldsymbol{\alpha}_{i}\)进行专门处理,\(\boldsymbol{\alpha}_{i}\)仅保留非零元素,\(\mathbf{E}_{i}\)则仅保留\(\boldsymbol{b}_{i}\)\(\boldsymbol{\alpha}_{i}\)的非零元素的乘积项,然后再进行奇异值分解,这样就保持了第一步所得到的稀疏性。
  初始化字典矩阵\(\mathbf{B}\)之后反复迭代上述两步,最终即可求得字典\(\mathbf{B}\)和样本\(\boldsymbol{x}_{i}\)的稀疏表示\(\mathbf{\alpha}_{i}\)。在上述字典学习过程中,用户能通过设置词汇量\(k\)的大小来控制字典的规模,从而影响到稀疏程度。

压缩感知(Compressed Sensing)

  在现实任务中,我们常希望根据部分信息来恢复全部信息。例如在数据通讯中要将模拟信号转换为数字信号,根据奈奎斯特(Nyquist)采样定理,令采样频率达到模拟信号最高频率的两倍,则采样后的数字信号就保留了模拟信号的全部信息,由此获得的数字信号能精确重构原模拟信号。然而,为了便于传输、存储。在实践中人们通常对采样的数字信号进行压缩,这有可能损失一些信息,而在信号传输过程中,由于信道出现丢包等问题,又可能损失部分信息。那么,接收方基于收到的信号,能否精确地重构出原信号呢?压缩感知为解决此类问题提供了新的思路。
  假定有长度为\(m\)的离散信号\(\boldsymbol{x}\),以远小于奈奎斯特采样定理要求的采样率进行采样,得到长度为\(n\)的采样后信号\(\boldsymbol{y}\),其中\(n \ll m\),即: \[ \boldsymbol{y}=\boldsymbol{\Phi} \boldsymbol{x} \]   其中\(\Phi \in \mathbb{R}^{n \times m}\)是对信号\(\boldsymbol{x}\)的测量矩阵,它确定了以什么频率进行采样以及如何将采样样本组成采样后的信号。在已知离散信号\(\boldsymbol{x}\)和测量矩阵\(\Phi\)时要得到测量\(\boldsymbol{y}\)很容易,然而,若将测量值和测量矩阵传输出去,接收方不能还原出原始信号,因为\(n \ll m\)\(\boldsymbol{y}, \boldsymbol{x}, \mathbf{\Phi}\)组成的\(\boldsymbol{y}=\boldsymbol{\Phi} \boldsymbol{x}\)是一个欠定方程,无法轻易求出数值解。
  现在不妨假设存在某个线性变换\(\mathbf{\Psi} \in \mathbb{R}^{m \times m}\),使得\(\boldsymbol{x}\)可表示为\(\mathbf{\Psi} \boldsymbol{s}\),于是\(\boldsymbol{y}\)可表示为: \[ \boldsymbol{y}=\boldsymbol{\Phi} \boldsymbol{\Psi} \boldsymbol{s}=\mathbf{A} \boldsymbol{s} \]   其中\(\mathbf{A}=\boldsymbol{\Phi} \boldsymbol{\Psi} \in \mathbb{R}^{n \times m}\),若能根据\(\boldsymbol{y}\)恢复出\(\boldsymbol{s}\),则可通过\(\boldsymbol{x}=\boldsymbol{\Psi} \boldsymbol{s}\)来恢复出信号\(\boldsymbol{x}\)
  因为上式中恢复信号\(\boldsymbol{s}\)这个逆问题仍是欠定的,所以这个方程依然不好解。然而若\(\boldsymbol{\Psi}\)具有稀疏性,则这个问题竟能很好地得以解决。这是因为稀疏性使得未知因素的影响大为减少,此时上式中的\(\boldsymbol{\Psi}\)称为稀疏基,而\(\boldsymbol{A}\)的作用则类似于字典,能将信号转换为稀疏表示。
  事实上,在很多应用中均可获得具有稀疏性的\(\boldsymbol{S}\),例如图像或声音的数字信号通常在时域上不具有稀疏性,但经过傅里叶变换、余弦变换、小波变换等处理后却会转化为频域上的稀疏信号。
  显然,与特征选择、稀疏表示不同,压缩感知关注的是如何利用信号本身所具有的稀疏性,从部分观测样本中恢复原信号。通常认为,压缩感知分为感知测量和重构恢复这两个阶段。感知测量关注如何对原始信号进行处理以获得稀疏样本表示,这方面的内容涉及傅里叶变换、小波变换以及字典学习、稀疏编码等,不少技术在压缩感知提出之前就已在信号处理等领域有很多研究。重构恢复关注的是如何基于稀疏性从少量观测中恢复原信号,这是压缩感知的精髓,当我们谈到压缩感知时,通常是指该部分。

RIP

  压缩感知的相关理论比较复杂,下面仅简要介绍一下限定等距性(Restricted Isometry Property,RIP)。对大小为\(n \times m(n \ll m)\)的矩阵\(\boldsymbol{A}\),若存在常数\(\delta_{k} \in(0,1)\)使得对于任意向量\(\boldsymbol{s}\)\(\boldsymbol{A}\)的所有子矩阵\(\mathbf{A}_{k} \in \mathbb{R}^{n \times k}\)有: \[ \left(1-\delta_{k}\right)\|s\|_{2}^{2} \leqslant\left\|\mathbf{A}_{k} s\right\|_{2}^{2} \leqslant\left(1+\delta_{k}\right)\|s\|_{2}^{2} \]   则称\(\boldsymbol{A}\)满足\(k\)限定等距性(k-RIP),此时可通过下面的优化问题近乎完美地从中恢复出稀疏信号\(\boldsymbol{S}\),进而恢复出\(\boldsymbol{x}\)\[ \begin{array}{c}{\min _{\boldsymbol{s}}\|\boldsymbol{s}\|_{0}} \\ {\text { s.t. } \quad \boldsymbol{y}=\mathbf{A} \boldsymbol{s}}\end{array} \]   然而,上式涉及\(L_0\)范数最小化,这是个NP难问题。值得庆幸的是,\(L_1\)范数最小化在一定条件下与\(L_0\)范数最小化问题共解,于是实际上只需关注: \[ \begin{array}{l}{\min _{s}\|s\|_{1}} \\ {\text { s.t. } \quad y=\mathrm{A} s}\end{array} \]   这样,压缩感知问题就可通过\(L_1\)范数最小化问题求解,上式可转化为LASSO的等价形式再通过近端梯度下降法求解,即使用基寻踪去噪(Basms Pursuit De-Noising)。

矩阵补全(Matrix Completion)

  如上图所示,假设一个矩阵中一些信息已知,而一些信息未知,该如何补全未知的信息呢?矩阵补全技术可用于解决这个问题,其形式为: \[ \begin{array}{l}{\min _{\mathbf{X}} \operatorname{rank}(\mathbf{X})} \\ {\text { s.t. } \quad(\mathbf{X})_{i j}=(\mathbf{A})_{i j}, \quad(i, j) \in \Omega}\end{array} \]   其中\(\mathbf{X}\)表示需恢复的稀疏信号\(rank(\mathbf{X})\)表示矩阵\(\mathbf{X}\)的秩,\(\mathbf{A}\)是矩阵中的己观测信息。\(\Omega\)是A中非“?”元素\((\mathbf{A})_{ij}\)的下标\((i,j)\)的集合。上式的约束项明确指出,恢复出的矩阵中\((\mathbf{X})_{ij}\)应应当与已观测到的对应元素相同。
  上也是个NP难问题.注意到\(rank(\mathbf{X})\)在集合\(\left\{\mathbf{X} \in \mathbb{R}^{m \times n} :\|\mathbf{X}\|_{F}^{2} \leqslant 1\right\}\)的凸包是\(\mathbf{X}\)的核范数(nuclear norm): \[ \|\mathbf{X}\|_{*}=\sum_{j=1}^{\min \{m, n\}} \sigma_{j}(\mathbf{X}) \]   其中\(\sigma_{j}\)表示\(\mathbf{X}\)的奇异值,即矩阵的核范数为矩阵的奇异值之和,于是可通过最小化矩阵核范数来近似求解,即: \[ \begin{array}{l}{\min _{\mathbf{x}}\|\mathbf{X}\|_{*}} \\ {\text { s.t. } \quad(\mathbf{X})_{i j}=(\mathbf{A})_{i j}, \quad(i, j) \in \Omega}\end{array} \]   上式是一个凸优化问题,可通过半正定规划(Semi-Definite Programming, SDP)求解。理论研究表明,在满足一定条件时,若\(\mathbf{A}\)的秩为\(r(r \ll m)\),则只需观察到\(O\left(m r \log ^{2} m\right)\)个元素就能完美恢复出\(\mathbf{A}\)

Refer


坚持原创技术分享,您的支持将鼓励我继续创作,π(3.14)元就够啦!



文章目录
  1. 1. 引言
  2. 2. 子集搜索与子集评价
  3. 3. 过滤式选择
    1. 3.1. Relief(Relevant Features)
    2. 3.2. Relief-F
    3. 3.3. 包裹式选择
    4. 3.4. LVW(Las Vegas Wrapper)
  4. 4. 嵌入式选择
    1. 4.1. PGD
  5. 5. 字典学习(Dictionary Learning)
    1. 5.1. 压缩感知(Compressed Sensing)
    2. 5.2. RIP
    3. 5.3. 矩阵补全(Matrix Completion)
  6. 6. Refer
您是第 位小伙伴 | 本站总访问量 | 已经写了 609.8k 字啦

载入天数...载入时分秒...