西瓜书第11章：特征选择与稀疏学习

---

特征选择

• 从给定的特征集合中选出任务相关特征子集
• 必须确保不丢失重要特征

原因

• 减轻维度灾难：在少量属性上构建模型
• 降低学习难度：留下关键信息

主要步骤：

1. 产生初始候选子集
2. 评价候选子集的好坏
3. 基于评价结果产生下一个候选子集

两个关键环节：子集搜索和子集评价

子集搜索

用贪心策略选择包含重要信息的特征子集

• 前向搜索：逐渐增加相关特征，最优子集初始为空集，特征集合初始时包括所有给定特征
• 后向搜索：从完整的特征集合开始，逐渐减少特征
• 双向搜索：每一轮逐渐增加相关特征，同时减少无关特征

子集评价

• 特征子集确定了对数据集的一个划分
  • 每个划分区域对应着特征子集的某种取值
• 样本标记对应着对数据集的真实划分

特征子集𝐴的信息增益为：

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

特征选择方法

将特征子集搜索机制与子集评价机制相结合，即可得到特征选择方法

过滤式（Relief）

先用特征选择过程过滤原始数据，再用过滤后的特征来训练模型；特征选择过程与后续学习器无关

Relief (Relevant Features) 方法

• 为每个初始特征赋予一个“相关统计量”，度量特征的重要性
• 特征子集的重要性由子集中每个特征所对应的相关统计量之和决定
• 设计一个阈值，然后选择比阈值大的相关统计量分量所对应的特征
• 或者指定欲选取的特征个数，然后选择相关统计量分量最大的指定个数特征

Relief-F?

包裹式（LVW）

LVW（Las Vegas Wrapper）在拉斯维加斯方法框架下使用随机策略来进行子集搜索，并以最终分类器的误差作为特征子集评价准则

基本步骤

• 在循环的每一轮随机产生一个特征子集
• 在随机产生的特征子集上通过交叉验证推断当前特征子集的误差
• 进行多次循环，在多个随机产生的特征子集中选择误差最小的特征子集作为最终解
• 若有运行时间限制，则该算法有可能给不出解

嵌入式

嵌入式特征选择是将特征选择过程与学习器训练过程融为一体，两者在同一个优化过程中完成，在学习器训练过程中自动地进行特征选择

岭回归（$L_2$范数）

$$\min _{\boldsymbol{w}} \sum_{i=1}^{m}\left(y_{i}-\boldsymbol{w}^{\top} \boldsymbol{x}_{i}\right)^{2}+\lambda\|\boldsymbol{w}\|_{2}^{2}$$

LASSO（$L_1$范数）

$$\min _{\boldsymbol{w}} \sum_{i=1}^{m}\left(y_{i}-\boldsymbol{w}^{\top} \boldsymbol{x}_{i}\right)^{2}+\lambda\|\boldsymbol{w}\|_{1}$$

L1正则化问题的求解

近端梯度下降（Proximal Gradient Descend，简称PGD）解法

写出$f(\boldsymbol{x})$的二阶泰勒展式：

$$f(\boldsymbol{x})=f\left(\boldsymbol{x}_{k}\right)+\left\langle\nabla f\left(\boldsymbol{x}_{k}\right), \boldsymbol{x}-x_{k}\right\rangle+\frac{1}{2}\left(\boldsymbol{x}-\boldsymbol{x}_{k}\right)^{\top} \frac{\delta^{2} f\left(\boldsymbol{x}_{k}\right)}{\delta \boldsymbol{x}_{k}^{2}}\left(\boldsymbol{x}-\boldsymbol{x}_{k}\right)$$

假设$f(\boldsymbol{x})$满足L-Lipschitz条件， 即存在常数𝐿 > 0, 使得

$$\left\|\nabla f\left(\boldsymbol{x}^{\prime}\right)-\nabla f(\boldsymbol{x})\right\| \leq L\left\|\boldsymbol{x}^{\prime}-\boldsymbol{x}\right\|_{2}^{2}$$

L-Lipschitz条件代入泰勒展式，可得：

$$\begin{aligned} f(\boldsymbol{x}) & \cong 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} \\ &=\frac{L}{2}\left\|\boldsymbol{x}-\left(\boldsymbol{x}_{k}-\frac{1}{L} \nabla f\left(\boldsymbol{x}_{k}\right)\right)\right\|^{2}+\mathrm{const} \end{aligned}$$

将上式关于𝑓(𝒙)的近似代入到原优化问题中，得

$$\min _{x} \sum_{i=1}^{m} \frac{L}{2}\left\|x-\left(\boldsymbol{x}_{k}-\frac{1}{L} \nabla f\left(\boldsymbol{x}_{k}\right)\right)\right\|^{2}+\lambda\|\boldsymbol{x}\|_{1}$$

每次在$x_k$的附近寻找最优点，不断迭代，即寻找

$$\boldsymbol{x}_{k+1}=\min _{\boldsymbol{x}} \sum_{i=1}^{m} \frac{L}{2}\left\|\boldsymbol{x}-\left(\boldsymbol{x}_{k}-\frac{1}{L} \nabla f\left(\boldsymbol{x}_{k}\right)\right)\right\|^{2}+\lambda\|\boldsymbol{x}\|_{1}$$

假设$\mathbf{z}=\boldsymbol{x}_{k}-1 / L \nabla f\left(\boldsymbol{x}_{k}\right)$，上式有闭式解

$$x_{k+1, i}=\left\{\begin{array}{ll} {z_{i}-\lambda / L} & {z_{i}>\lambda / L} \\ {0} & {\left|z_{i}\right| \leq \lambda / L} \\ {z_{i}+\lambda / L} & {z_{i}<-\lambda / L} \end{array}\right.$$

稀疏表示（字典学习）

为普通稠密表达的样本找到合适的字典，将样本转化为稀疏表示，这一过程称为字典学习

给定数据集 $\left\{\boldsymbol{x}_{1}, \boldsymbol{x}_{2}, \ldots, \boldsymbol{x}_{m}\right\}, \boldsymbol{x}_{i} \in \mathbb{R}^{n \times k}$

学习目标是字典矩阵 $\mathbf{B} \in \mathbb{R}^{d \times k}$ 以及样本的稀疏表示 $\boldsymbol{\alpha}_{i} \in \mathbb{R}^{k}$

𝑘称为字典的词汇量，通常由用户指定

则最简单的字典学习的优化形式为:

$$\min _{\mathbf{B}, \alpha_{i}} \sum_{i=1}^{m}\left\|\mathbf{x}_{i}-\mathbf{B} \boldsymbol{\alpha}_{i}\right\|_{2}^{2}+\lambda \sum_{i=1}^{m}\left\|\boldsymbol{\alpha}_{i}\right\|_{1}$$

字典学习的解法

压缩感知

长度为𝑚的离散信号𝒙，用远小于奈奎斯特采样定理的要求的采样率采样得到长度为𝑛的采样后信号𝒚，𝑛 ≪ 𝑚，即

$$\boldsymbol{y}=\boldsymbol{\Phi} \boldsymbol{x}$$

一般情况下，𝑛 ≪ 𝑚，不能利用𝒚还原𝒙，但是若存在某个线性变换Ψ，使得𝒙 = Ψ𝒔， 𝒔是稀疏向量，即

$$\boldsymbol{y}=\boldsymbol{\Phi} \boldsymbol{x}=\boldsymbol{\Phi} \Psi s=\mathbf{A} \boldsymbol{s}$$

𝐴具有“限定等距性”时，可以近乎完美地恢复𝒔