机器学习 · 第 10 讲：特征选择与稀疏学习

知识框架

特征选择希望从原始属性中选出有用子集，降低维度、减少过拟合并提高可解释性。重点包括子集搜索、子集评价、过滤式选择、包裹式选择、嵌入式选择、$L_1$ 正则、稀疏表示、字典学习、压缩感知和矩阵补全。

给定特征集合 $A=\{a_1,a_2,\ldots,a_d\}$，直接遍历所有子集需要 $2^d$ 次，通常不可行。常见搜索策略：

子集评价可使用信息增益、相关性、交叉验证性能等指标。若用信息增益，子集包含的类别信息越多，评价越高。

Relief 给每个特征一个相关统计量。对样本 $\mathbf{x}_i$，找到同类最近邻 near-hit 和异类最近邻 near-miss：

\[ \delta^j \leftarrow \delta^j -\operatorname{diff}(x_i^j,\operatorname{hit}^j) +\operatorname{diff}(x_i^j,\operatorname{miss}^j). \]

若某特征在同类样本间差异小、异类样本间差异大，则该特征更重要。Relief-F 可扩展到多分类和更复杂情形。

LVW 随机产生特征子集，使用交叉验证估计学习器性能；若性能不下降且特征数更少，则接受该子集。它属于 Las Vegas Wrapper，强调在随机搜索中寻找小而有效的特征集合。

嵌入式选择常写为

\[ \min_{\mathbf{w}} J(\mathbf{w})+\lambda\|\mathbf{w}\|_1. \]

$L_1$ 正则容易产生精确为 $0$ 的权重，因此可直接完成特征选择。相比之下，$L_2$ 正则通常把权重压小但不置零。

近端梯度中的软阈值形式：

\[ w_j \leftarrow \operatorname{sign}(z_j) \max(|z_j|-\eta\lambda,0). \]

当 $|z_j|\le \eta\lambda$ 时，权重被压为 $0$。

稀疏表示认为样本可由少量基向量线性组合：

\[ \mathbf{x}\approx \mathbf{D}\mathbf{\alpha},\qquad \mathbf{\alpha}\ \text{稀疏}. \]

字典学习可写为

\[ \min_{\mathbf{D},\mathbf{A}}\|\mathbf{X}-\mathbf{D}\mathbf{A}\|_F^2 +\lambda\sum_i\|\mathbf{\alpha}_i\|_1. \]

通常交替优化：固定字典求稀疏编码，固定编码更新字典。

压缩感知研究如何从少量线性测量恢复稀疏信号：

\[ \mathbf{y}=\mathbf{\Phi}\mathbf{x},\qquad \mathbf{x}=\mathbf{\Psi}\mathbf{s}, \]

恢复问题常松弛为

\[ \min_{\mathbf{s}}\|\mathbf{s}\|_1 \quad \text{s.t.}\quad \mathbf{y}=\mathbf{\Phi}\mathbf{\Psi}\mathbf{s}. \]

RIP 条件保证测量矩阵近似保持稀疏向量距离。矩阵补全则利用低秩结构，从部分观测恢复完整矩阵，常用核范数作为秩的凸替代。