第十一章 特征学习和稀疏学习
11.1 子集搜索与评价
- 对一个学习任务来说，给定属性集，其中有些属性可能很关键、很有用，另一些属性则可能没什么用。
- 对当前学习任务有用的属性称为“相关特征”（relevant feature）
- 没什么用的属性称为“无关特征”（irrelevant feature）
- 从给定的特征集合中选择出相关特征子集的过程，称为“特征选择”（feature selection）
- 特征选择是一个重要的“数据预处理”（data preprocessing）过程。
- 在现实机器学习任务重，获得数据之后通常先进行特征选择，此后再训练学习器。
- 现实任务中经常会遇到维数灾难问题：属性过多。
- 去除不相关特征往往会降低学习任务的难度。
- 特征选择的过程必须保证不丢失重要特征。
- “冗余特征”（redundant feature）所包含的信息能从其他特征中推演出来。
- “子集搜索”（subset search）：
- 前向（forward）搜索：给定特征集合${a_1,a_2,…,a_d}$，可将每个特征看做一个候选子集，对这$d$个候选单特征子集进行评价，假定${a_2}$最优，于是将${a_2}$作为第一轮的选定集，假定在这$d-1$个候选两特征子集中${a_2,a_4}$最优，且优于${a_2}$，于是将${a_2,a_4}$作为本轮的选定集；……假定在第$k+1$轮时，最优的候选$(k+1)$特征子集不如上一轮的选定集，则停止生成候选子集，并将上一轮选定的$k$特征集合作为特征选择结果。
- 后向（backward）搜索：从完整的特征集合开始，每次尝试去掉一个无关特征。
- 双向（bidirectional）搜索：将前向与后向搜索结合起来，每一轮逐渐增加选定相关特征（这些特征在后续轮中将确定不会被去除）、同时减少无关特征。
- 子集评价（subset evaluation）：给定数据集$D$，假定$D$中第$i$类样本所占的比例为$p_i(i=1,2,…,\lvert \mathcal{Y} \rvert)$。假定样本属性均为离散型，对属性子集$A$，假定根据其取值将$D$分成了$V$个子集${D^1,D^2,…,D^V}$，每个子集中的样本在$A$上取值相同，计算属性子集$A$的信息增益：$Gain(A)=Ent(D)-\sum_{v=1}^V\frac{\lvert D^v\rvert}{\lvert D\rvert}Ent(D^v)$。
- 信息熵定义为：$Ent(D)=-\sum_{i=1}^{\lvert\mathcal{Y}\rvert}p_klog_2p_k$
- 信息增益$Gain(A)$越大，意味着特征子集$A$包含的有助于分类的信息越多。
- 对每个候选特征子集，基于训练数据集$D$来计算其信息增益，作为评价准则。
- 更一般的，特征子集A实际上确定了对数据集D的一个划分，每个划分区域对应着A上的一个取值，而样本标记信息Y则对应着对D的真实划分，通过估算这两个划分的差异，就能对A进行评价。
- 与Y对应的划分差异越小，则说明A越好。
- 特征选择方法大致可分为三类：
- 过滤式（filter）
- 包裹式（wrapper）
- 嵌入式（embedding）
11.2 过滤式选择
- 过滤式方法先对数据集进行特征选择，然后再训练学习器，特征选择过程与后续学习器无关。
- Relief（Relevant Features）是一种著名的过滤式特征选择方法，该方法设计了一个“相关统计量”来度量特征的重要性。
- 相关统计量是一个向量，每个分量分别对应于一个初始特征；
- 特征子集的重要性是由子集每个特征所对应的相关统计量之和决定。
- 指定一个阈值$\tau$，选择比$\tau$大的相关统计量分量所对应的特征；也可以指定欲选取的特征个数$k$，选择相关统计量最大的$k$个特征。
- 确定相关统计量：
- 给定训练集${(x_1,y_1),(x_2,y_2),…,(x_m,y_m)}$，对每个示例$x_i$，Relief先在$x_i$的同类样本中寻找其最近邻$x_{i,nh}$，称为“猜中近邻”（near-hit），再从$x_i$的异类样本中寻找其最近邻$x_{i,nm}$，称为“猜错近邻”（near-miss）。
- 相关统计量对应于属性$j$的分量为：$\delta^j=\sum_i-diff(x_i^j,x_{i,nh}^j)^2+diff(x_i^j,x_{i,nm}^j)^2$
- 其中$x_a^j$表示样本$x_a$在属性$j$上的取值；
- $diff(x_a^j,x_b^j)$取决于属性$j$的类型：若属性$j$为离散型，则$x_a^j=x_b^j$时，$diff(x_a^j,x_b^j)=0$，否则为1；若属性$j$为连续型，则$diff(x_a^j,x_b^j)=\lvert x_a^j-x_b^j$，注意$x_a^j,x_b^j$已规范化到[0,1]区间。
- 若$x_i$与其猜中近邻$x_{i,nh}$在属性$j$上的距离小于$x_i$与其猜错近邻$x_{i,nm}$的距离，则说明属性$j$对区分同类与异类样本是有益的，于是增大属性$j$所对应的统计量分量；反之，减小属性$j$所对应的统计量分量。
- 对基于不同样本得到的估计结果进行平均，就得到各属性的相关统计量分量，分量值越大，则对应属性的分类能力越强。
- Relief是为二分类问题设计的，Relief-F能处理多分类问题。
11.3 包裹式选择
- 过滤式特征选择不考虑后续学习器
- 包裹式特征选择直接把最终将要使用的学习器的性能作为特征子集的评价准则。
- 给特定学习器选择最有利于其性能、“量身定做”的特征子集。
- 从最终学习器的性能来看，包裹式特征选择比过滤式特征选择更好；计算开销通常比过滤式特征选择更大。
- LVW（Las Vegas Wrapper）是一个典型的包裹式特征选择方法。
11.4 嵌入式选择与$L_1$正则化
- 嵌入式选择将特征选择与学习器训练过程融为一体，两者在同一个优化过程中完成，即学习器训练过程中自动地进行了特征选择。
- 给定数据集$D={(x_1,y_1),(x_2,y_2),…,(x_m,y_m)}$，其中$X\in\mathbb{R}^d$，$y\in\mathbb{R}$，考虑最简单的线性回归模型，以平方误差为损失函数，优化目标为：$\mathop{min}\limits_{w}\sum_{i=1}^m(y_i-w^Tx_i)^2$
- 当样本特征很多，样本数相对比较少时，训练容易陷入过拟合，为了缓解过拟合问题，对目标函数引入正则化项：$\mathop{min}\limits_{w}\sum_{i=1}^m(y_i-w^Tx_i)^2+\lambda\lVert w\rVert^2_2$，称为“岭回归”（ridge regression）。
- 将正则化项中的$L_2$范数替换为$L_p$范数：令$p=1$，采用$L_1$范数，则有$\mathop{min}\limits_{w}\sum_{i=1}^m(y_i-w^Tx_i)^2+\lambda\lVert w\rVert_1$，该式称为LASSO（Least Absolute Shrinkage and Selection Operator）
- $L_1$范数和$L_2$范数正则化都有助于降低过拟合的风险。
- $L_1$范数有一个额外的好处：更易于获得“稀疏”（sparse）解，即求得的$w$会有更少的非零分量。
- 求解$L_1$范数正则化的结果是得到了仅采用一部分初始特征的模型，即基于$L_1$正则化的学习方法就是一种嵌入式特征选择方法，其特征选择过程与学习器训练过程融为一体。
- $L_1$正则化问题的求解可使用近端梯度下降（Proximal Gradient Descent，简称PGD）
11.5 稀疏表示和字典学习
- 把数据集$D$考虑成一个矩阵，其每行对应于一个样本，每列对应于一个特征。
- 特征选择所考虑的问题是特征具有“稀疏性”，即矩阵中的许多列与当前学习任务无关，通过特征选择去除这些列，则学习器训练过程仅需在较小的矩阵上进行。
- 另一种稀疏性：$D$中所对应的矩阵存在很多零元素，但这些零元素并不是以整列、整行形式存在的。
- 在一般的学习任务中，需要学习出一个字典，为普通稠密表达的样本找到合适的字典，从而将样本转化为合适的稀疏表示形式。
- 字典学习（dictionary learning）：侧重于学的字典的过程
- 稀疏编码（sparse coding）：侧重于对样本进行稀疏表达的过程
11.6 压缩感知
- 现实任务中，希望根据部分信息来恢复全部信息。
- 奈奎斯特（Nyquist）采样定理：领采样频率达到模拟信号最高频率的两倍，则采样后的数字信号就保留了模拟信号的全部信息。
- 假设有长度为$m$的离散信号$x$，如果以远小于奈奎斯特采样定理要求的采样率进行采样，得到长度为$n$的采样信号$y$，$n\ll m$，即$y=\Phi x$
- 其中$\Phi \in \mathbb{R}^{(n\times m)}$是对信号$x$的测量矩阵，它确定了以什么频率进行采样以及如何将采样样本组成采样后的信号。
- 在已知离散信号$x$和测量矩阵$\Phi$时要得到测量值$y$很容易，然而将测量值和测量矩阵传输出去，很难还原出原始信号$x$。
- $y=\Phi x$是一个欠定方程，无法轻易求出数值解。
- 假定存在某个线性变换$\Psi\in\mathbb{R}^{(m\times m)}$，使得$x$可表示为$\Psi s$，于是$y=\Phi\Psi s=As$
- 其中$A=\Phi\Psi\in\mathbb{R}^{(n\times m)}$
- 如果能根据$y$恢复出$s$，则可通过$x=\Psi s$来恢复出信号$x$。
- 如果$s$具有稀疏性，则可以解决欠定问题。$\Psi$称为稀疏基。
- 压缩感知关注如何利用信号本身所具有的稀疏性，从部分观测样本中恢复原信号。
- 压缩感知分为“感知测量”和“恢复重构”两个阶段。
- “感知测量”关注如何对原始信号进行处理已获得稀疏样本表示。涉及傅里叶变换、小波变换、字典学习、稀疏编码等。
- “恢复重构”关注的是如何基于稀疏性从少量观测中恢复原信号，这是压缩感知的精髓。
