【西瓜书】第十一章特征选择与稀疏学习

本文是周志华老师《机器学习》第十一章内容特征选择与稀疏学习的学习笔记

子集搜索与评价

在学习任务中，我们经常会需要对已有的特征进行选择，选出对当前学习任务有用的相关特征而排除无关特征。这样，既可以减轻维度灾难，又降低了学习难度。
由于直接计算所有特征的组合显然不可行，我们通常是先生成候选子集，然后评估其优劣，接着再生成下一个候选子集，如此往复直到结束。

那么，这里我们就需要考虑两个方面的方法，一个是子集搜索，一个是子集评价。

子集搜索上我们通常采用贪心的方法，有从0特征开始增加的前向搜索，也有全特征开始排除的后向搜索，以及同时开始增加和减少的双向搜索。
子集评价方面，信息熵是常见的指标。其定义为：

$Ent(D)=-\sum_{i=1}^{|y|}p_klog_2p_k$

那么信息增益就是：

$Gain(A)=Ent(A)-\sum_{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$

信息增益越大，说明包含有用信息越多。

过滤式

Relief方法是最常见的过滤式方法，这类方法主要是先用特征选择来对原始特征进行过滤，然后将过滤后的特征传入学习器。
Relief给每个初始特征赋予了一个相关统计量，用以衡量特征的重要性，然后设立一个相关统计量的阈值来进行过滤。
因此，这里的重点就在于如何确定相关统计量，Relief定义猜中近邻为某个样本的同类样本中最近邻$x_{i,nh}$，而猜错近邻为异类样本中的最近邻$x_{i,nm}$，那么定义相关统计量对应于属性$j$的分量为：

$\delta^j=\sum_i-\text{diff}(x_i^j,x_{i.nh}^j)^2+\text{diff}(x_i^j,x_{i,nm}^j)^2$

如果相关统计量越大，那么属性$j$上，猜对近邻比猜错近邻更近，那么属性$j$也就越有用。

上面的公式是针对二分类问题的，Relief也可以很容易地拓展到多类上去：

$\delta^j=\sum_i-diff(x_i^j,x_{i.nh}^j)^2+\sum_{l\ne k}p_k\times diff(x_i^j,x_{i,l,nm}^j)^2$

注意过滤式的方法是独立于后续学习器的，也就是学习器无关的。

包裹式

和过滤式不同，包裹式选择直接把最重要是用的学习器性能作为特征自己的评价标准，因此从性能上看，包裹式特征选择比过滤式特征选择更好，但是由于需要多次训练学习器，计算开销会大得多。

LVW是一种拉斯维加斯方法，使用随机策略来搜索。基本步骤为：

循环的每一轮随机产生特征子集
在产生的子集上通过交叉验证推断当前特征子集的误差
进行多次循环，在其中选择误差最小的那个特征子集

嵌入式和L1正则化

嵌入式特征选择将特征选择和学习器训练过程融为一体了，二者在同一个优化过程中完成，在学习器训练的过程中也自动地进行特征选择。
我们以线性回归为例，设目标函数为MSE，加入L2正则化来避免过拟合，那么我们就有：

$\underset{w}{min}(y_i-w^Tx_i)^2+\lambda\|w\|^2$

带L2惩罚项的线性回归又称岭回归。

这里我们将L2范数换成L1范数，就有了LASSO（套索回归）。

$\underset{w}{min}(y_i-w^Tx_i)^2+\lambda\|w\|_1$

我们知道，目标优化的解会在平方误差项和正则化项之间折中，而使用L1范数正则化的特点是，容易获得稀疏解，也就是有参数为0，在线性回归中，也就可以看作那项为0参数对应的特征被“剔除”掉了，实际上完成了特征选择。

稀疏表示和字典学习

我们将数据集化成一个矩阵，每行为样本，每列为特征，通过整行整列为0，我们可以筛选特征，但是我们来考虑另一种稀疏性，即不是每行每列为0.
这样的稀疏表达可以给学习任务带来好处，例如文本数据由于具有高度稀疏性而线性可分，而且有着高效的存储解决方案。
为普通稠密表示的样本通过寻求合适的字典而找到一个合适的稀疏表示形式的过程就叫做字典学习，或者稀疏编码。这二者稍有不同，前者更侧重于学得字典的过程，后者更侧重于稀疏表示的过程。
给定数据集，字典学习最简单的形式为：

$\underset{B,\alpha_i}{min}\sum_{i=1}^{m}\|x_i-B\alpha_i\|^2+\lambda\sum_{i=1}^m\|\alpha_i\|_1$

其中$B\in\mathbb{R}^{d\times k}$为字典矩阵，$k$为字典的词汇量，通常由用户指定，$\alpha_i\in\mathbb{R}^k$则是$x_i\in \mathbb{R}^d$的稀疏表示,类似于其他常见损失函数，式中第一项旨在希望很好的进行重构，第二项则是希望学到的表示尽量稀疏。

这里的求解可以采用变量交替优化的方式：

第一步固定住字典$B$，参照LASSO的解法求解下式：

$\min_{\alpha_i}\|x_i-B\alpha_i\|_2^2+\lambda\|\alpha_i\|_1$

第二步以$\alpha_i$为初值来更新字典$B$。以逐行更新的KSVD解法为例，首先将优化目标拆成逐行的：

$\min_{B}\|X-BA\|_F^2\rightarrow \min_{b_i}\|E_i-b_i\alpha^i\|_F^2$

其中 $E_i=X-\sum_{j\neq i}b_j\alpha^j$ 是固定的，对他进行奇异值分解以取得最大奇异值所对应的正交向量(类似PCA降维）。
但是这里直接做SVD分解会同时改变$b,\alpha$，可能会破坏稀疏性。因此这里会对它们做特殊处理：$\alpha$只保留非零元素， $E$仅保留$b$和$a$的非零元素乘积项，然后再进行SVD，这样就保持了第一步得到的稀疏性。

反复迭代上述两部，最终就可以得到字典$B$和稀疏表示$\alpha$。
词汇量$k$的大小会影响稀疏程度。

压缩感知

// TODO 压缩感知
在现实任务中，还有一种常见的需求，就是根据部分信息来恢复全部信息。
按照奈奎斯特采样定理，采样频率达到模拟信号最高频率两倍时，采样后的数字信号就可以保留模拟信号的全部信息。

压缩感知是解决这类问题的一种思路。
假设有长度为$m$的离散信号$x$，采样后得到的信号$y$长度为$n$，且$n\ll m$，即：

$y=\Phi x$

其中$\Phi$是测量矩阵。一般来说上式是一个欠定方程（因为$n\ll m$），因此由$y$通常无法还原出$x$.

我们现在假设一个线性变换$x=\Psi s$, 则有：

$y=\Phi\Psi s=As$

那么我们如果能够还原$s$，就可以得到$x$。粗看这里变换似乎没有解决问题，但是如果$s$能够具有稀疏性，则我们可以很好解决这个问题。
因为稀疏性是的未知因素的影响大为减少，此时式(11.20)中的$\Psi$成为稀疏基，$A$的作用类似于字典，能将信号转换为稀疏表示。

压缩感知关注的是如何利用信号本身所具有的稀疏性，从部分观测样本中恢复原信号。
它可以分为两部分：

感知测量对原始信号进行处理以获得稀疏样本表示涉及傅里叶变换小波变换字典学习稀疏编码等
重构恢复基于稀疏性从少量观测中复原信号也是压缩感知的精髓

关于压缩感知的代表性理论有“限定等距性”（Restricted Isometry Property, RIP）。

通过部分信息来恢复全部信息在现实任务中有重要应用，例如著名的协同过滤（collaborative filtering）.
其中一种解法就是矩阵补全技术（matrix completion）。该问题的形式为：

$\min_{X}\quad rank(X)$ $s.t.\quad (X)_{ij}=(A)_ij, (i,j)\in\Omega$

其中$X$为需要恢复的稀疏信号，$rank(X)$表示矩阵的秩。 $A$是已观测信号，$\Omega$是已知元素的下标。
这个问题是一个NP难的问题，注意到$rank(X)$在集合${X\in\mathbb{R}^{m\times n}: |X|^2 \le 1}$上的凸包是$X$的核范数:

$\|X\|_*=\sum_{j=1}^{min\{m, n\}} \sigma_j(X)$

其中$\sigma_j(X)$表示$X$的奇异值，然后就可以通过最小化矩阵核范数来球近似解：

$\min_{X}\|X\|_*$ $s.t.\quad (X)_{ij}=(A)_{ij},\quad (i, j)\in \Omega$

这样我们就得到一个凸优化问题，可以通过半正定规划来解决。

理论上，当满足一定条件，$A$的秩为$r$, $n\ll m$，则只需要观察到$O(mr\log^2m)$个元素就可以完美恢复出$A$.

习题及参考答案

1. 试编程实现Relief算法，并考察其在西瓜数据集3.0上的运行结果。

略。

2. 试写出Relief-F的算法描述。

不就是书上p250页的内容嘛。。

3. Relief算法是分别考虑每个属性的重要性。试设计一个能考虑每一对属性重要性的改进算法。

组合选取每一对属性的near-hit和near-miss，然后计算这一对属性的相关统计量$\delta^{ij}$。
得到这个二维的相关统计量矩阵后，就可以通过最大生成树等算法来做特征选择。
当然这里会有一个组合爆炸的问题，可以通过采样等方式减缓。

4. 试为LVW设计一个改进算法，即便有运行时间限制，该算法也一定能给出解。

拉斯维加斯改成蒙特卡洛，随机生成特征子集改成启发式的迭代生成子集就行了，方法很多，具体就略了。

5. 结合图11.3，试举例说明L1正则化在何种情形下不能产生稀疏解。

平方误差项等值线和L1范数等值线在象限内相切时。
为什么一定是相切呢。这里的优化目标可以用拉格朗日乘子法将正则化项换为约束，即对L1范数而言我们要在红色矩形框的范围内找到一点尽可能使平方误差项更小，这里很自然就会发现尖角端更容易满足这一条件。
但是当平方误差项等值线它的中心也在原点附近，二者就更容易在象限内相切。

6. 试分析岭回归和支持向量机的联系。

二者的优化目标很相似，Ridge Regression的L2正则化项就是SVM的结构风险. 它们也都可以使用核技巧来适应非线性问题。

7. 试述直接求解L0范数正则化会遇到的困难。

L0正则化的值是模型参数中非零参数的个数，但是这种计数函数又不连续可导，所以很难去求一个闭式解。因此往往用L1正则化去做L0的最优凸近似。

8. 试给出求解L1范数最小化问题中闭式解（11.14）的详细推导过程。