> For the complete documentation index, see [llms.txt](https://blog.cweihang.io/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://blog.cweihang.io/ml/zzh_ml_notes/melon/ch11.md).

# 特征选择与稀疏学习

## 第11章 特征选择与稀疏学习

* Page247: 冗余特征(redundant feature)

  在特征选择过程中，有一类特征所包含的信息能从其他特征中推演出来，这类特征成为『冗余特征』。\
  例如，考虑立方体对象，若已有特征『底面长』、『底面宽』，则『底面积』是冗余特征，因为它能从『底面长』和『底面宽』得到。\
  冗余特征很多时候不起作用，去除它们会减轻学习过程的负担。但有时又会降低学习任务的难度。例如若学习目标是估算立方体的体积，则『底面积』这个冗余特征的存在将使得体积的估算更加容易；确切地说，若某个冗余特征恰好对应了完成学习任务所需的『中心概念』，则该冗余特征是有益的。
* Page247: 数据预处理(data preprocessing)

  现实世界中数据大体上都是不完整、不一致的脏数据，无法直接进行数据挖掘，或挖掘结果差强人意。为了提高数据挖掘的质量产生了数据预处理技术。它是指在主要的处理以前对数据进行的一些处理。\
  数据预处理有多种方法：数据清理，数据集成，数据变换，数据归约等。在现实机器学习任务中，特征选择也是一个重要的数据预处理过程。
* Page247: 特征选择 & 相关特征(feature selection & relevant feature)

  对一个学习任务，给定的属性集称为特征。对当前学习任务有用的属性称为『相关特征』，没什么用的属性称为『无关特征』。从给定的特征中选出相关特征子集的过程，称为特征选择。
* Page247: 相关特征(relevant feature)

  见特征选择。
* Page248: 子集搜索(subset search)

  从特征集合中选取包含所有重要信息的特征子集，若没有任何领域知识作为先验，就只能遍历所有可能的子集。而这会遭遇组合爆炸问题导致计算不可行。可行的办法是产生一个『候选子集』，评价出它的好坏，基于评价结果产生下一个候选子集，再评价，……直到无法找到更好的候选子集为止。而产生候选子集的过程就是子集搜索。\
  具体而言，给定特征集合 $${a\_1, a\_2, ...., a\_d}$$, 可以将每个特征看作一个候选子集，对这 $$d$$ 个候选单特征子集进行评价，假定 $${a\_2}$$ 最优，于是将 $${a\_2}$$ 作为第一轮的选定集；然后，加入一个特征，构成包含两个特征的候选子集，假定在这 $$d-1$$ 个候选两特征子集中 $${a\_2, a\_4}$$ 最优，且优于 $${a\_2}$$，于是将 $${a\_2, a\_4}$$ 作为本轮选定集；直至最优的候选特征子集不如上一轮的选定集，则停止生成候选子集，并将上一轮的选定集作为特征选择结果。\
  逐渐增加相关特征的策略称为『前向』搜索；类似的，逐渐减少特征的策略称为『后向』搜索；前向与后向搜索结合起来的策略称为『双向』搜索。
* Page248: 子集评价(subset evaluation)

  由于子集搜索过程仅考虑了本轮选定集最优，无法解决这样的问题：例如在第三轮假定选择 $${a\_5}$$ 优于 $${a\_6}$$，于是选定集为 $${a\_2, a\_4, a\_5}$$，然而在第四轮却可能是 $${a\_2, a\_4, a\_6, a\_8}$$ 比所有的 $${a\_2, a\_4, a\_5, a\_i}$$ 都更优。\
  通过对每个候选特征子集，基于训练数据集计算其信息增益，以此作为评价准则。这一过程称为子集评价。\
  具体而言，给定数据集 $$D$$，假定 $$D$$ 中第 $$i$$ 类样本（假定样本属于离散型）所占的比例为 $$p\_i(i = 1,2,...,|y|)$$。对属性子集 $$A$$，假定根据其取值将 $$D$$ 分成了 $$V$$ 个子集 $${D^1, D^2, ..., D^V}$$，每个子集中的样本在 $$A$$ 上取值相同，于是属性子集 $$A$$ 的信息增益为：\
  $$Gain(A) = Ent(D) - \sum\_{v=1}^{V} \frac {|D^v|}{|D|} Ent(D^v)$$，\
  其中信息熵定义为：\
  $$Ent(D) = -\sum\_{i=1}^{|y|} p\_k log\_2 p\_k$$，\
  信息增益 $$Gain(A)$$ 越大，意味着特征子集 $$A$$ 包含的有助于分类的信息越多。\
  更一般的，特征子集 $$A$$ 实际上确定了对数据集 $$D$$ 的一个划分，每个划分区域对应着 $$A$$ 上的一个取值，而样本标记信息 $$Y$$ 则对应着对 $$D$$ 的真实划分，通过估算这两个划分的差异，就能对 $$A$$ 进行评价。与 $$Y$$ 对应的划分的差异越小，则说明 $$A$$ 越好。
* Page249: 过滤式(filter)特征选择

  常见的特征选择方法之一。先对数据集进行特征选择，然后再训练学习器，特征选择过程与后续学习器无关。相当于先用特征选择过程对初始特征进行『过滤』，再用过滤后的特征来训练模型。\
  Relif 是一种著名的过滤式特征选择方法，该方法设计了一个『相关统计量』来度量特征的重要性。该统计量是一个向量，其每个分量分别对应于一个初始特征，而特征子集的重要性则是由子集中每个特征所对应的相关统计量分量之和来决定。最终只需指定一个阈值，然后选择比阈值大的相关统计量分量即可。也可指定欲选取的特征个数 $$k$$，然后选择相关统计量分量最大的 $$k$$ 个特征。时间开销岁采样次数以及原始特征数线性增长，是一个运行效率很高的过滤式特征选择算法。
* Page250: 包裹式(wrapper)特征选择

  常见的特征选择方法之一。直接把最终将要使用的学习器的性能作为特征子集的评价准则。它的目的就是为给定学习器选择有利于其性能、『量身定做』的特征子集。\
  LVW（Las Vegas Wrapper）是一个典型的包裹式特征选择方法。它在拉斯维加斯方法框架下使用随机策略来进行子集搜索，并以最终分类器的误差为特征子集评价准则。计算开销很大，且有可能运行很长时间达不到停止条件。
* Page251: 拉斯维加斯方法(Las Vegas method)

  是一种在电脑运算中永远给出正确解的随机化算法；也就是说，它总是给出正确结果，或是返回失败。 换言之，拉斯维加斯算法不赌结果的正确性，而是赌运算所用资源。它的一个显著特征是它所作的随机性决策有可能导致算法找不到所需的解。一个简单的例子是随机快速排序，他的中心点虽然是随机选择的，但排序结果永远一致。
* Page251: 蒙特卡洛方法(340,384)(Monte Carlo method)

  也称统计模拟方法，是二十世纪四十年代由于科学技术的发展和电子计算机的发明，而提出的一种以概率统计理论为指导、使用随机数来解决问题的数值计算方法。
* Page252: LASSO(261)

  全称 Least Absolute Shrinkage and Selection Operator，对目标损失函数引入 $$L\_1$$ 正则化项，即采用 $$L\_1$$ 范数时，目标损失函数称为 LASSO，如式所示：\
  $$min\_w \sum\_{i=1}^m (y\_i - w^Tx\_i)^2 + \lambda ||w||\_1$$
* Page252: Tikhonov 正则化（L2 正则化）

  当样本特征很多，而样本数相对较少时，要优化的目标损失函数很容易陷入过拟合。为了缓解过拟合问题，对目标损失函数引入正则化项。Tikhonov 正则化（L2 正则化）就是使用 $$L\_2$$ 范数正则化，即：$$||w||\_2^2$$。
* Page252: 岭回归(ridge regression)

  引入 Tikhonov 正则化项（L2 正则化项）的目标损失函数称为岭回归，如式所示：\
  $$min\_w \sum\_{i=1}^m (y\_i - w^Tx\_i)^2 + \lambda ||w||^2\_2$$
* Page252: 嵌入式(embedding)特征选择

  将特征选择过程与学习器训练过程融为一体，两者在同一个优化过程中完成，即在学习器训练过程中自动地进行了特征选择。
* Page253: L1 正则化

  为了缓解过拟合问题，对目标损失函数引入正则化项。L1 正则化就是使用 $$L\_1$$ 范数正则化，即：$$||w||\_1$$。
* Page253: L2正则化

  见 Tikhonov 正则化。
* Page253: Lipschitz 条件

  在使用近端梯度下降对 L1 正则化问题求解时，对优化目标：$$min\_x f(x) + \lambda \lVert x \rVert\_1$$，若 $$f(x)$$ 可导，微分算子 $$\nabla f$$ 满足 L-Lipschitz 条件，即存在常数 $$L>0$$ 使得：\
  $$\lVert \nabla f(x^{'})-\nabla f(x) \rVert\_2^2 \leqslant L \lVert x^{'} - x \rVert\_2^2 \quad (\forall x,x^{'})$$ 在 $$x\_k$$ 附近可将 $$f(x)$$ 通过二阶泰勒展开式近似为：\
  $$f(x)^{\*} \backsimeq f(x\_k) + \langle \nabla f(x\_k), x-x\_k \rangle + \frac {L}{2}\lVert x - x\_k \rVert^2$$\
  L-Lipschitz 条件是指：对于在实数集的子集的函数 $$f: D \subseteq \mathbb{R} \to \mathbb{R}$$，若存在常数 $$K$$，使得 $$\lvert f(a)-f(b)\rvert \leqslant K\lvert a-b\rvert \quad \forall a,b \in D$$，则称 $$f$$ 符合 L-Lipschitz 条件，对于 $$f$$ 最小的常数 $$K$$ 称为 $$f$$ 的 L-Lipschitz 常数。
* Page253: 近端梯度下降(259)(Proximal Gradient Descent)

  在引入 L1 正则项的目标损失函数：\
  $$min \quad f(x) + \lambda \lVert x \rVert\_1$$\
  会遇到求导问题（L1 范数在 $$x=0$$ 处不可导），若 $$f(x)$$ 可导，微分算子 $$\nabla f$$ 满足 L-Lipschitz 条件，在 $$x\_k$$ 附近可将 $$f(x)$$ 通过二阶泰勒展开式近似为：\
  $$f(x)^{*} \backsimeq f(x\_k) + \langle \nabla f(x\_k), x-x\_k \rangle + \frac {L}{2}\lVert x - x\_k \rVert^2$$\
  $$= \frac {L}{2} \lVert x - \lgroup x\_k - \frac {1}{L} \nabla f(x\_k) \rgroup \rVert\_2^2 + const$$，\
  其中 const 是与 $$x$$ 无关的常数，$$\langle .,. \rangle$$ 表示内积，上式最小值在如下 $$x\_{k+1}$$ 获得：\
  $$x\_{k+1} = x\_k - \frac {1}{L} \nabla f(x\_k)$$，\
  若通过梯度下降法对 $$f(x)$$ 最小化，则每一步梯度下降迭代实际上等价于最小化 $$f(x)^{*}$$，类似得到每一步迭代应为：\
  $$x\_{k+1} = arg\ min\_x \frac {L}{2} \lVert x - \lgroup x\_k - \frac {1}{L} \nabla f(x\_k) \rgroup \rVert\_2^2 + \lambda \lVert x \rVert\_1$$，\
  即在每一步对 $$f(x)$$ 进行梯度下降迭代的同时考虑 L1 范数最小化。\
  这种近似求解的方法称为近端梯度下降（Proximal Gradient Descent）。
* Page255: 码书学习 & 字典学习(codebook & dictionary learning)

  为普通稠密表达的样本找到合适的字典，将样本转化为合适的稀疏表示形式，从而使学习任务得以简化，模型复杂度得以降低，通常称为字典学习，亦称为码书学习。字典学习侧重于学得字典的过程。给定数据集 $${x\_1,x\_2,..,x\_m}$$，字典学习最简单的形式为：\
  $$min\_{\bf{B, \alpha\_i}} \sum\_{i=1}^m \lVert x\_i - \bf{B \alpha\_i} \rVert\_2^2 + \lambda \sum\_{i=1}^m \lVert \bf{\alpha\_i} \rVert\_1$$，\
  其中 $$\bf{B} \in \mathbb{R}^{d \times k}$$ 为字典矩阵，$$k$$ 称为字典的词汇量，通常由用户指定，$$\bf{\alpha\_i} \in \mathbb{R}^k$$ 则是样本 $$\bf{x\_i} \in \mathbb{R}^d$$ 的稀疏表示。
* Page255: 稀疏编码(sparse coding)

  字典学习亦称为稀疏编码，后者更侧重于对样本进行稀疏表达的过程。两者通常在同一个优化求解过程中完成。
* Page255: 字典学习(dictionary learning)

  同码书学习。
* Page257: 压缩感知(compressed sensing)

  压缩感知（Compressed sensing），也被称为压缩采样（Compressive sampling）或稀疏采样（Sparse sampling），是一种寻找欠定线性系统的稀疏解的技术。在现实任务中，我们常希望根据部分信息来恢复全部信息，压缩感知就是为处理此类问题提供了方法。\
  压缩感知关注如何利用信号本身所具有的稀疏性，从部分观测样本中恢复信号。通常认为，压缩感知分为感知测量和重构恢复两个阶段。
* Page259: 局部线性嵌入(Locally Linear Embedding) 无。\
  局部线性嵌入（Locally Linear Embedding）是一种非常重要的降维方法。和传统的 PCA，LDA 等关注样本方差的降维方法相比，LLE 关注于降维时保持样本局部的线性特征，由于 LLE 在降维时保持了样本的局部特征，它广泛的用于图像图像识别，高维数据可视化等领域。
* Page259: 协同过滤(collaborative filtering)

  利用某兴趣相投、拥有共同经验之群体的喜好来推荐使用者感兴趣的资讯，个人通过合作的机制给予资讯相当程度的回应（如评分）并记录下来以达到过滤的目的进而帮助别人筛选资讯，回应不一定仅限于特别感兴趣的，特别不感兴趣资讯的记录也相当重要。分为以使用者为基础的协同过滤、以项目为基础的协同过滤和以模型为基础的协同过滤。
* Page260: 核范数 & 迹范数(nuclear norm & trace norm)

  矩阵奇异值之和。
* Page260: 迹范数(trace norm)

  同核范数。