前言

感觉看的越来越水，有点想快点到深度学习了

第十一章

在上一章的讨论中，我们探讨了通过数学变换实现数据降维的方法。然而，降维其实还存在一种更为直接的方式，那就是简单地舍弃部分数据维度（即属性）。这个想法初看可能显得不太合理，但经过仔细思考就会发现其实际可行性：在现实世界的数据采集中，我们获得的样本属性通常存在以下两个典型问题：

• 属性与业务场景不相关：不同的分析任务关注的数据特征各不相同，某些属性可能对当前分析目标毫无贡献
• 属性间存在依赖关系：某些属性可能完全或部分地由其他属性线性组合或推导得出，包含冗余信息
  基于这些观察，我们需要从原始属性集合中筛选出与研究目标密切相关的属性（即关键特征），同时剔除那些无关紧要或冗余的属性（即无关特征）。这个过程本质上是对数据维度进行有依据的筛选，经过筛选就减少了样本空间的维度。

11.1 子集搜索与评价

在特征选择过程中，当缺乏领域知识时，我们需要考虑所有可能的特征子集，然而这是不可行的。比如设原始样本空间的维度$d=30$时，需要遍历$2^{30}-1$个子集，算不了。因此，我们不得不采用贪心算法来近似求解。贪心算法主要有以下三种实现方式：

前向选择的具体步骤如下：

1. 初始化一个空的特征集合$\mathcal{S}=\varnothing$。
2. 遍历所有未被选中的特征，将每个特征单独加入$\mathcal{S}$，形成$D$个单特征候选子集。使用某种评价标准对这些子集进行评分，选择得分最高的特征永久加入$\mathcal{S}$。
3. 此时$\mathcal{S}$包含一个特征。继续遍历剩余特征，将它们逐个加入$\mathcal{S}$，形成$D-1$个双特征候选子集。再次评分，选择使性能提升最大的特征加入$\mathcal{S}$。
4. 重复上述过程，每次都在当前$\mathcal{S}$的基础上添加最能提升性能的特征。当新增特征无法带来性能提升，或达到预设特征数量时停止。最终得到的$\mathcal{S}$即为所选特征子集。

后向剔除的具体步骤如下：

1. 初始化包含所有特征的集合S={所有特征}\mathcal{S} = \{\text{所有特征}\}S={所有特征}。
2. 遍历$\mathcal{S}$中的所有特征，暂时移除每个特征，形成$D$个$D-1$维候选子集。使用评价标准评分后，永久移除对性能影响最小的特征。
3. 此时$\mathcal{S}$包含$D-1$个特征。继续遍历剩余特征，暂时移除每个特征并评分，永久移除最不重要的特征。
4. 重复上述过程，每次移除对性能影响最小的特征。当移除任何特征都会显著降低性能，或达到预设特征数量时停止。

双向搜索结合了前向和后向策略：

1. 从当前集合外部选择能带来最大性能提升的新特征。
2. 从当前集合内部移除导致性能下降最小的现有特征。
3. 比较这两种操作的收益，选择更有利的操作执行。

是不是很像决策树和层次类聚呀

需要注意的是，由于这些方法都采用贪心策略，可能会陷入局部最优解。举例来说，如果在早期步骤中选择了特征$A$，但在后续步骤中可能会发现特征$B$和特征$C$的组合实际上具有更好的效果，这种由于贪心策略导致的次优选择是难以避免的。此外，在算法实现过程中，我们需要对当前选择的特征子集进行质量评估，这就要求我们建立一个有效的评价机制来度量特征子集的优劣。目前常见的特征选择方法主要可以分为以下三种类型：

• 过滤式
• 包裹式
• 嵌入式

11.2 三种选择

11.2.1 过滤式选择

过滤式特征选择是在模型训练之前进行的特征筛选过程，其特点是不依赖于具体的学习算法，仅通过分析特征本身的统计特性与标签之间的关联性来评估特征重要性。这种方法通过预先设定的统计指标来筛选特征，具有计算效率高和通用性强的特点。

过滤式方法的实施步骤如下：

1. 确定特征评估指标：选取合适的统计量作为特征重要性的衡量标准，这些指标通常用于评估特征对目标变量的区分能力或相关性强度。
2. 计算特征得分：针对数据集中的每个特征，独立计算其对应的评估指标得分。这个步骤会对所有候选特征进行遍历计算。
3. 特征排序：根据上一步计算得到的特征得分，对所有特征按照得分高低进行降序排列。
4. 特征子集选择：
   • 基于阈值筛选：设定一个分数临界值，保留所有得分超过该阈值的特征。
   • 基于数量筛选：预先确定需要选择的特征数量$k$，然后选取排序后前$k$个得分最高的特征。

以Relief方法为例，这是一种专门针对二分类问题设计的基于样本采样的特征选择算法。该方法的观点是：优质特征应该能够有效区分不同类别的样本，同时保持同类样本之间的相似性。

首先，在训练集$D=\{({\mathbf{x}}_1,y_1),\dots ,({\mathbf{x}}_m,y_m)\}$中选取一个样本${\mathbf{x}}_i$，然后进行以下操作：

• 在同类样本中找出与${\mathbf{x}}_i$最接近的样本${\mathbf{x}}_{ih}$（下标$h$表示hit）
• 在异类样本中找出与${\mathbf{x}}_i$最接近的样本${\mathbf{x}}_{im}$（下标$m$表示miss）

对于这两个最近邻样本，我们需要计算它们在各个特征上的差异程度。理想的特征应该满足：同类样本间差异小（一致性高），异类样本间差异大（区分度高）。因此，对于样本${\mathbf{x}}_i$的特征$j$，其差异得分计算如下：
$${\delta }_i^j=-diff({\mathbf{x}}_i^j,{\mathbf{x}}_{ih}^j{)}^2+diff({\mathbf{x}}_i^j,{\mathbf{x}}_{im}^j{)}^2$$

为了得到特征$j$的整体评估得分，需要对多个样本的计算结果进行累加：
$${\delta }^j=\sum _{i=1}^n{\delta }_i^j=\sum _{i=1}^n(-diff({\mathbf{x}}_i^j,{\mathbf{x}}_{ih}^j{)}^2+diff({\mathbf{x}}_i^j,{\mathbf{x}}_{im}^j{)}^2)$$
其中$n\le m$表示不需要对所有样本进行计算。这里的$diff(x_1,x_2)$函数用于计算两个样本在特征$j$上的差异：

• 连续型特征：通常采用归一化的绝对差值，计算公式为：
  $$diff(x_1,x_2)=\frac{|x_1-x_2|}{\max (X_j)-\min (X_j)}$$
  其中$\max (X_j)$和$\min (X_j)$分别是特征$j$的最大值和最小值。
• 离散型特征：采用简单的相等性判断：
  • 若$x_1=x_2$，则$diff(x_1,x_2)=0$
  • 若$x_1\ne x_2$，则$diff(x_1,x_2)=1$

对于多分类问题，原始的Relief算法无法直接处理，但它的改进版本Relief-F能够很好地解决这个问题。Relief-F的基本思想是将多种异类类别的贡献按照它们在数据集中的比例进行加权求和：

$${\delta }_i^j=-\text{diff}({\mathbf{x}}_i^j,{\mathbf{x}}_{ih}^j{)}^2+\sum _{c\ne y_i}\left[P(c)\cdot \text{diff}({\mathbf{x}}_i^j,{\mathbf{x}}_{i{m}_c}^j{)}^2\right]$$

在这个公式中：

• $y_i$表示当前样本${\mathbf{x}}_i$的真实类别标签。
• ${\mathbf{x}}_{ih}^j$是样本${\mathbf{x}}_i$在特征$j$上同类最近邻的取值。
• ${\mathbf{x}}_{i{m}_c}^j$是样本${\mathbf{x}}_i$在特征$j$上类别$c$的最近邻的取值。
• $P(c)$表示类别$c$在整个数据集中的先验概率（即该类样本数占总样本数的比例）。

11.2.2 包裹式选择

指望入职前所述过滤式特征选择的最大特点是与学习算法无关，通用性强。但其通用性也决定了它在特定学习算法上表现相对较浅。而包裹式特征选择则放弃通用性，专为特定学习算法设计。它根据学习器的实际表现评价特征子集（需多次训练模型），因此在该算法上性能更优，但代价是计算复杂度显著增加。

以 LVW (Las Vegas Wrapper) 算法为例，它基于 Las Vegas 算法 (LVA)，LVA 是一种随机化算法，保证结果正确但运行时间不确定。这意味着 LVW 会持续搜索直到找到最优或次优子集，最终必定能找到正确解，只是所需时间无法预知。与蒙特卡洛算法（固定时间，结果可能不准）不同，LVW 只要运行就一定能得到正确解。这使其适合高精度要求但对时间不敏感的任务。

LVW 算法的目标是找到一个包含最少特征的子集，同时保证在这个子集上训练出的学习器性能满足预设的要求。算法的整体流程如下：

1. 随机生成特征子集：与子集搜索中提到的贪心算法不同，LVW 通过随机方式生成候选特征子集。
2. 评估子集性能：使用预设的学习器在验证集上评估该子集的性能。
3. 更新最佳子集：如果当前随机生成的子集满足性能要求，并且其包含的特征数量少于当前已知的最佳子集，则更新最佳子集。
4. 重复迭代：重复上述过程，直到达到预设的迭代次数或找到一个满意的解。

具体来说：
假设我们有一个数据集 $D=\{({\mathbf{x}}_1,y_1),\dots ,({\mathbf{x}}_m,y_m)\}$，其中包含 $d$ 个特征。我们需要设定以下参数：

• 评估器$\mathcal{L}$：用于评估特征子集性能的机器学习模型（例如决策树、SVM、神经网络等）。
• 性能评估指标$Per$（Performance）：衡量 $\mathcal{L}$ 性能的指标，例如分类准确率 $acc$ 或错误率 $error$。
• 最大尝试次数 $T_{max}$：算法运行的最大迭代次数，避免无限循环。
• 性能阈值：期望模型达到的最低性能要求。
  初始化：
• 将当前找到的“最佳”特征子集 $S_{best}$ 设置为包含所有特征的集合
• 将当前“最佳”子集对应的模型$Per$指标设置为一个相对较差的初始值。
  • 如果 $Per$ 是准确率（我们希望最大化），那么 $Pe{r}_{best}$ 初始化为 $0$ 或一个非常小的负数
  • 如果 $Per$ 是错误率（我们希望最小化），那么 $Pe{r}_{best}$ 初始化为 $1.0$ 或一个非常大的正数。
• 将当前尝试次数 $t$ 初始化为 0。
  迭代搜索：
  重复以下步骤，直到 $t\ge T_{max}$：

1. 随机生成特征子集 $S^{\prime }$：
   • 从所有 $d$ 个特征中，随机选择一个特征子集 $S^{\prime }$。
2. 评估特征子集 $S^{\prime }$：
   • 使用训练集 $D_{train}$ 上的 $S^{\prime }$ 特征子集训练学习器 $\mathcal{L}$。
   • 在独立的验证集 $D_{val}$ 上评估训练好的模型，得到$Per$指标 $Pe{r}_{S^{\prime }}$。
   • （为了更稳健，通常会使用交叉验证来计算$Per$指标的平均值）。
3. 更新最佳子集（以最大化准确率为例）：
   • 如果 $Pe{r}_{S^{\prime }}\ge Pe{r}_{best}$：
     • 若 $Pe{r}_{S^{\prime }}>Pe{r}_{best}$（找到一个$Per$更好的子集）：
       • 更新 $S_{best}=S^{\prime }$。
       • 更新 $Pe{r}_{best}=Pe{r}_{S^{\prime }}$。
     • 若 $Pe{r}_{S^{\prime }}=Pe{r}_{best}$（找到一个$Per$相同但可能特征更少的子集）：
       • 若 $|S^{\prime }|<|S_{best}|$（当前子集特征数量更少）：
         • 更新 $S_{best}=S^{\prime }$。
         • 更新 $Pe{r}_{best}=Pe{r}_{S^{\prime }}$。
4. 增加尝试次数：$t=t+1$。

返回结果：
算法终止后，返回 $S_{best}$ 作为选定的特征子集。

11.2.3 嵌入式选择与$L_1$正则化

过滤式选择是在模型训练开始之前就进行特征筛选。这种方法的优点是计算速度快、操作简单直观；但缺点在于筛选出的特征可能不是最适合特定模型的组合，因为它没有考虑模型本身的特性和实际预测性能。

包裹式选择采用不同的思路，它将特征选择过程与模型的性能评估直接挂钩。这种方式通常能够找到预测性能更优的特征子集，但其计算成本非常高，而且由于需要评估大量特征组合，存在过拟合风险。

为了在计算效率和模型性能之间取得平衡，嵌入式选择被提出。这种方法将特征选择整合到模型训练过程中，使得模型在优化参数的同时，自动完成特征选择。当模型训练结束时，特征选择的结果也就自然确定了。

嵌入式方法的具体实现通常是在模型的目标函数中直接加入特征选择机制。这个机制的工作原理是对不重要的特征施加惩罚，通过这种惩罚使得那些不重要的特征对应的权重系数$w_i$逐渐变小，最终可能会完全归零（即达到$w_i=0$的状态）。当某个特征的权重系数变为$0$时，这个特征就会被自动排除在模型之外，不再参与后续的预测过程。在实际应用中，$L_1$正则化是最常用且最具代表性的嵌入式特征选择实现方式。

关于$L_1$正则化，我们在6.3节已经做过详细介绍。这里我们以最简单的线性回归模型为例来说明其具体应用。假设原始的目标函数是：
$$\underset{\mathbf{w}}{\min }\sum _{i=1}^m(y_i-{\mathbf{w}}^T{\mathbf{x}}_i{)}^2$$
当我们引入$L_1$惩罚项$\lambda \Vert \mathbf{w}{\Vert }_1$（其中$\lambda >0$）后，优化目标就变为：
$$\underset{\mathbf{w}}{\min }\sum _{i=1}^m(y_i-{\mathbf{w}}^T{\mathbf{x}}_i{)}^2+\lambda \Vert \mathbf{w}{\Vert }_1$$

选择使用$L_1$正则化的主要原因在于它更容易得到稀疏解（即包含大量零分量的解）。为了更直观地理解这一点，可以想象一个几何解释：在没有惩罚项的情况下，最优解会落在误差函数的某个象限中；当加入惩罚项后，相当于要求解必须位于以原点为中心的某个区域内。对于$L_1$正则化来说，这个区域是一个菱形（在二维情况下是菱形，高维情况下是多面体），而误差函数的等高线是椭圆。当椭圆从最优解位置开始向外膨胀时，第一个与惩罚项边界相交的点就是我们的新解。由于$L_1$正则化的边界存在尖角（顶点），这个交点有很大概率会落在坐标轴上，从而使得某些特征的权重正好为零。相比之下，$L_2$正则化的边界是光滑的圆形/球面，交点落在坐标轴上的概率要小得多，因此$L_1$正则化更容易产生稀疏解。

既然产生了稀疏解，这意味着零分量权重对应的特征就不再重要，这里已经完成了特征选择的过程。接下来我们来看$L_1$正则化如何求解。首先需要明确的是，我们不能直接使用标准的梯度下降法，因为$L_1$惩罚项在零点处存在不可导点（即函数图像出现尖角）。为了解决这个问题，我们采用近端梯度法来进行优化。

首先我们关注目标函数中的光滑部分，即损失函数部分：
$$f(\mathbf{w})=\sum _{i=1}^m(y_i-{\mathbf{w}}^T{\mathbf{x}}_i{)}^2$$
如果这个函数满足$L$-利普希茨连续的条件，我们就可以为其构造一个二次上界：
$$f(\mathbf{w})\le \left(f({\mathbf{w}}_k)+\nabla f({\mathbf{w}}_k{)}^T(\mathbf{w}-{\mathbf{w}}_k)+\frac{L}{2}\Vert \mathbf{w}-{\mathbf{w}}_k{\Vert }_2^2\right)$$

现在我们来推导标准梯度下降的过程。为了简化表达式，我们暂时忽略常数项$f({\mathbf{w}}_k)$等不影响优化结果的部分。我们的优化目标可以表示为：
$$\arg \underset{\mathbf{w}}{\min }\left(\nabla f({\mathbf{w}}_k{)}^T\mathbf{w}+\frac{L}{2}\Vert \mathbf{w}-{\mathbf{w}}_k{\Vert }_2^2\right)$$

将范数平方项展开：
$$\Vert \mathbf{w}-{\mathbf{w}}_k{\Vert }_2^2={\mathbf{w}}^T\mathbf{w}-2{\mathbf{w}}^T{\mathbf{w}}_k+{\mathbf{w}}_k^T{\mathbf{w}}_k$$
我们只保留与$\mathbf{w}$相关的项：
$$\nabla f({\mathbf{w}}_k{)}^T\mathbf{w}+\frac{L}{2}({\mathbf{w}}^T\mathbf{w}-2{\mathbf{w}}^T{\mathbf{w}}_k)=\frac{L}{2}{\mathbf{w}}^T\mathbf{w}+(\nabla f({\mathbf{w}}_k)-L{\mathbf{w}}_k{)}^T\mathbf{w}$$

通过配方法，我们可以将这个表达式重写为：
$$\frac{L}{2}{\Vert \mathbf{w}-\left({\mathbf{w}}_k-\frac{1}{L}\nabla f({\mathbf{w}}_k)\right)\Vert }_2^2$$
显然，这个表达式的最小值在${\mathbf{w}}_{k+1}={\mathbf{w}}_k-\frac{1}{L}\nabla f({\mathbf{w}}_k)$处取得。这个推导表明，标准梯度下降法的本质是：在每一步迭代中，都在最小化原函数的一个二次近似。

现在我们将这个思想应用到完整的$L_1$正则化问题中：
$$\sum _{i=1}^m(y_i-{\mathbf{w}}^T{\mathbf{x}}_i{)}^2+\lambda \Vert \mathbf{w}{\Vert }_1$$
可以得到类似的更新公式：
$${\mathbf{w}}_{k+1}=\arg \underset{\mathbf{w}}{\min }\left(\frac{L}{2}{\Vert \mathbf{w}-\underset{\text{定义为}\mathbf{z}}{\underbrace{\left({\mathbf{w}}_k-\frac{1}{L}\nabla f({\mathbf{w}}_k)\right)}}\Vert }_2^2+\lambda \Vert \mathbf{w}{\Vert }_1\right)$$

这个公式可以这样理解：

1. 首先沿着光滑部分的负梯度方向走一步，得到一个中间点$\mathbf{z}$。
2. 然后寻找一个新的点$\mathbf{w}$，它需要满足两个条件：既要尽可能接近$\mathbf{z}$（由第一项$\Vert \mathbf{w}-\mathbf{z}{\Vert }_2^2$控制），又要使自身的$L_1$范数尽可能小（由第二项$\lambda \Vert \mathbf{w}{\Vert }_1$控制）。

由于$\Vert \mathbf{w}{\Vert }_1={\sum }_j|w_j|$和$\Vert \mathbf{w}-\mathbf{z}{\Vert }_2^2={\sum }_j(w_j-z_j{)}^2$都是可分离的，我们可以对$\mathbf{w}$的每个分量$w_j$单独求解：
$$\underset{w_j}{\min }\left(\lambda |w_j|+\frac{L}{2}(w_j-z_j{)}^2\right)$$

这个子问题的解可以通过软阈值算子表示：
$$w_j=\{\begin{array}{ll}{z}_j-\frac{\lambda }{L}& \text{如果 }{z}_j>\frac{\lambda }{L}\\ z_j+\frac{\lambda }{L}& \text{如果 }{z}_j<-\frac{\lambda }{L}\\ 0& \text{如果 }|z_j|\le \frac{\lambda }{L}\end{array}$$

这里的推导用到了次梯度的概念

因为是闭式解，所以可以快速求解。

11.3 稀疏表示与字典学习

设想我们有一个数据集 $D$，它是一个矩阵，其中每一行代表一个样本，每一列代表一个特征。在特征选择中，我们通过减少列数（即特征数量）来简化数据。
现在我们考虑另一种数据简化思路，当一个样本向量中存在大量 $0$ 元素时，我们称其具有稀疏性。当样本具有稀疏性时，每个样本可以较为容易地分解为少数几个主要特征，这显然会降低学习任务的复杂度。现实中我们的样本多半不具备稀疏性，但特征数量却又实实在在地远大于样本数，这意味着稠密样本可以通过某些办法变得稀疏，这正是字典学习方法所要解决的问题。

我们可以通过线性空间的概念来理解稀疏性。在一个高维空间中，如果只有少量的数据点分布其中，那么总是可以通过重新构建坐标系的方式，使得这些数据点尽可能落在坐标轴上。这样一来，大多数坐标分量就会变为 $0$，这个过程也就是字典学习的基本思想。
另外引入中提到每一行代表一个样本，在本节之后的所有内容中样本都由列向量表示

我们首先假设存在一个变换矩阵 $\mathbf{B}\in {\mathbb{R}}^{d\times k}$，这个矩阵通常被称为字典（之所以称为字典，可以参考相关教材中的解释）。其中，$d$ 表示原始样本的特征维度，$k$ 表示稀疏样本的特征维度，也称为字典的词汇量（即字典矩阵的列数）。设 $\mathbf{x}\in {\mathbb{R}}^d$ 为原始样本，$\mathbf{\alpha }\in {\mathbb{R}}^k$ 为对应的稀疏表示。我们的目标是让经过字典变换后的稀疏样本能够尽可能准确地重构原始样本，因此可以建立以下优化问题：
$$\underset{\mathbf{B},\mathbf{\alpha }}{\min }\sum _{i=1}^m\Vert {\mathbf{x}}_i-\mathbf{B}{\mathbf{\alpha }}_i{\Vert }_2^2$$
其中，$\Vert \cdot {\Vert }_2$ 表示 $L_2$ 范数，用于衡量重构误差。

进一步，我们希望稀疏表示 $\mathbf{\alpha }$ 具有尽可能少的非零元素，因此可以在优化目标中加入稀疏性约束。具体来说，引入 $L_0$ 范数来统计 $\mathbf{\alpha }$ 中非零分量的个数，优化问题变为：
$$\underset{\mathbf{B},\mathbf{\alpha }}{\min }\sum _{i=1}^m\Vert {\mathbf{x}}_i-\mathbf{B}{\mathbf{\alpha }}_i{\Vert }_2^2+\lambda \Vert {\mathbf{\alpha }}_i{\Vert }_0$$
然而，由于 $L_0$ 范数的优化是一个 NP 难问题，在实际应用中通常难以直接求解。因此，我们通常使用 $L_1$ 范数作为 $L_0$ 范数的凸松弛近似，从而将优化目标转化为：

$$\underset{\mathbf{B},\mathbf{\alpha }}{\min }\sum _{i=1}^m\Vert {\mathbf{x}}_i-\mathbf{B}{\mathbf{\alpha }}_i{\Vert }_2^2+\lambda \Vert {\mathbf{\alpha }}_i{\Vert }_1$$

当字典 $\mathbf{B}$ 固定时，这就是 LASSO 问题。为了同时优化两个变量 $\mathbf{B}$ 和 $\mathbf{\alpha }$，可以采用交替优化的方法：先固定其中一个变量优化另一个变量，然后交替进行，通过多次迭代逐步逼近最优解。

具体来说，首先固定字典 $\mathbf{B}$ 不变，此时优化目标简化为：
$$\underset{{\mathbf{\alpha }}_1,{\mathbf{\alpha }}_2,\dots ,{\mathbf{\alpha }}_m}{\min }\sum _{i=1}^m\left(\Vert {\mathbf{x}}_i-\mathbf{B}{\mathbf{\alpha }}_i{\Vert }_2^2+\lambda \Vert {\mathbf{\alpha }}_i{\Vert }_1\right)$$
由于每个样本对应的稀疏编码 ${\mathbf{\alpha }}_i$ 之间是相互独立的，因此这个优化问题可以分解为 $m$ 个独立的 LASSO 子问题，而 LASSO 问题之前已经解过。

第二步我们固定$\mathbf{A}$，这时正则化项$\lambda \Vert \mathbf{\alpha }{\Vert }_1$的值就也被固定，可以暂时从优化目标中移除。现在需要集中精力优化字典矩阵$\mathbf{B}$，具体来说就是要解决以下问题：
$$\underset{\mathbf{B}}{\min }\sum _{i=1}^m\Vert {\mathbf{x}}_i-\mathbf{B}{\mathbf{\alpha }}_i{\Vert }_2^2$$
这个优化问题也可以表示为Frobenius范数的形式：${\min }_{\mathbf{B}\in {\mathbb{R}}^{d\times k}}\Vert \mathbf{X}-\mathbf{BA}{\Vert }_F^2$。有多种算法可以求解这个问题，这里我们选择KSVD算法。KSVD算法的思想是：每次迭代只更新字典矩阵的一个原子（即一列向量）。但仅仅这样更新会导致优化不充分，因此KSVD算法在更新第$k$个原子${\mathbf{b}}_k$时，会同步优化稀疏编码矩阵$\mathbf{A}$中与该原子对应的第$k$行${\mathbf{\alpha }}_k^T$。

为了更清楚地展示这个过程，我们可以将矩阵乘积$\mathbf{BA}$展开：
$\mathbf{BA}={\sum }_{j=1}^K{\mathbf{b}}_j{\mathbf{a}}_j^T$。于是优化目标可以重新表述为：
$$\begin{array}{rl}\Vert \mathbf{X}-\mathbf{BA}{\Vert }_F^2& ={\Vert \mathbf{X}-\sum _{j=1}^K{\mathbf{b}}_j{\mathbf{a}}_j^T\Vert }_F^2\\ & ={\Vert \left(\mathbf{X}-\sum _{j\ne k}{\mathbf{b}}_j{\mathbf{a}}_j^T\right)-{\mathbf{b}}_k{\mathbf{a}}_k^T\Vert }_F^2\end{array}$$
这里我们特别将第$k$项分离出来，并定义误差矩阵${\mathbf{E}}_k=\mathbf{X}-{\sum }_{j\ne k}{\mathbf{b}}_j{\mathbf{a}}_j^T$。这个误差矩阵具有明确的意义：它表示当排除第$k$个原子时，原始数据矩阵$\mathbf{X}$与当前重构结果之间的差异。由于在更新第$k$列时，其他所有列${\mathbf{b}}_j$（$j\ne k$）及其对应的系数${\mathbf{a}}_j^T$都保持不变，因此${\mathbf{E}}_k$在当前优化步骤中是一个已知的、可以预先计算的常量矩阵。

通过这样的分解，原始优化问题就简化为如下形式：
$$\underset{{\mathbf{b}}_k,{\mathbf{a}}_k^T}{\min }\Vert {\mathbf{E}}_k-{\mathbf{b}}_k{\mathbf{a}}_k^T{\Vert }_F^{2}s.t.\Vert {\mathbf{b}}_k{\Vert }_2^2=1$$
由于$\mathbf{A}$是稀疏矩阵，我们只需要关注那些非零元素对应的部分。最后对这个子问题进行奇异值分解，就能得到当前迭代步骤中最优的字典$\mathbf{B}$更新。

最后经过多轮迭代，我们就找到了最优字典$\mathbf{B}$和稀疏表示$\mathbf{A}$

11.4 压缩感知

奈奎斯特采样定理告诉我们：为了无损地重建一个模拟信号，采样频率 $f_s$ 必须至少是该信号最高频率分量 $f_{max}$ 的两倍，即 $$f_s\ge 2f_{max}$$这样，采集到的数字信号就能保留模拟信号的全部信息。然而，在实际应用中，我们获取数据后常常要做的第一件事就是压缩，这意味着原始信号中本来就存在大量冗余。因此一个自然的想法便随之产生：我们能否跳过采集海量冗余数据的步骤，直接采集信号的“精华”部分，从而在采样阶段就获得一个近似“压缩后”的版本，之后再通过特定的算法重构出原始信号呢？

对于一般的非稀疏信号，这个想法是不现实的，因为这意味着在任何坐标系下，信号的每一个分量都承载着不可或缺的信息。但是，一旦信号是稀疏的，理论上我们就可以设计一个测量矩阵 $\mathbf{\Phi }\in {\mathbb{R}}^{n\times m}$，将高维信号的特征维度从 $m$ 压缩到 $n$（这里 $m$ 是原始高维信号的维度，并且 $m\gg n$）。这个过程可以表示为 $$\mathbf{y}=\mathbf{\Phi }\mathbf{x}$$ 其中，$\mathbf{x}$ 是原始的高维信号，而 $\mathbf{y}$ 则是我们实际中采集到的低维测量值。

显然，整个过程由两个部分组成：

1. 稀疏表示：这一步的目标是将高维信号 $\mathbf{x}$ 转换为一种稀疏的表示形式。也就是说，存在一个稀疏基矩阵 $\mathbf{\Psi }\in {\mathbb{R}}^{m\times m}$，使得等式 $\mathbf{x}=\mathbf{\Psi }\mathbf{s}$ 成立。在这里，$\mathbf{s}$ 就是信号 $\mathbf{x}$ 在基 $\mathbf{\Psi }$ 下的稀疏表示（注意，${\mathbf{\Psi }}^{-1}$ 才是真正的稀疏变换）。上一节提到的字典学习就是为了寻找这样的 $\mathbf{\Psi }$，其他常见的例子包括通过傅里叶变换将时域信号变换到频域，信号在频域中通常是稀疏的。

2. 重构恢复：将稀疏表示代入测量过程，我们便得到新的关系式 $$\mathbf{y}=\mathbf{\Phi }(\mathbf{\Psi }\mathbf{s})=(\mathbf{\Phi }\mathbf{\Psi })\mathbf{s}=\mathbf{As}$$在这个等式中，$\mathbf{y}$ 是已知的测量数据，而矩阵 $\mathbf{A}=\mathbf{\Phi }\mathbf{\Psi }\in {\mathbb{R}}^{n\times m}$ 是由两个已知矩阵相乘得到的，因此也是已知的。所以，只要我们能解出稀疏向量 $\mathbf{s}$，就能通过 $\mathbf{x}=\mathbf{\Psi }\mathbf{s}$ 这个关系式，精确地重构出原始的高维信号 $\mathbf{x}$。

但是，方程
$$\mathbf{y}=\mathbf{As}$$
是一个典型的欠定线性系统，因为未知数的数量 $m$ 远大于方程的数量 $n$，这意味着它拥有无穷多组解。幸运的是，我们还有一个额外的先验条件：向量 $\mathbf{s}$ 是稀疏的。利用这个稀疏性，我们就可以将求解线性方程组的问题，转化为一个优化问题：
$$\underset{\mathbf{s}}{\min }\Vert \mathbf{s}{\Vert }_0\text{subject to}\mathbf{y}=\mathbf{As}$$
正如之前讨论过的，求解 $L_0$ 范数最小化是一个NP难问题。因此，在实践中，我们通常将其松弛为求解 $L_1$ 范数最小化的问题，优化目标变为：
$$\underset{\mathbf{s}}{\min }\Vert \mathbf{s}{\Vert }_1\text{subject to}\mathbf{y}=\mathbf{As}$$
然而，使用 $L_1$ 范数替代 $L_0$ 范数并非毫无代价。这种替代的有效性，取决于矩阵 $\mathbf{A}$ 是否满足一个重要的性质，即限定等距性 (Restricted Isometry Property, RIP)。如果矩阵 $\mathbf{A}$ 满足 $k$-限定等距性，那么上述两个优化问题的解就是一致的。形式化地讲，对于任意一个 $k$-稀疏向量 $\mathbf{s}$（即 $\Vert \mathbf{s}{\Vert }_0\le k$），存在一个很小的常数 ${\delta }_k\in [0,1)$，使得：
$$(1-{\delta }_k)\Vert \mathbf{s}{\Vert }_2^2\le \Vert \mathbf{As}{\Vert }_2^2\le (1+{\delta }_k)\Vert \mathbf{s}{\Vert }_2^2$$
这个性质保证了矩阵 $\mathbf{A}$ 在作用于稀疏向量时，能够近似地保持向量的欧几里得长度（即范数）。一个非常重要的结论是，高斯随机矩阵、伯努利随机矩阵等随机矩阵有极高的概率满足限定等距性（RIP）。

最后，我们来看一个与压缩感知思想一脉相承的例子：矩阵补全 (Matrix Completion)。想象一下这个场景：我们想知道一群人对一批书籍的评分，但每个人只读过并评价了其中的一小部分书，形成了一个不完整的评分矩阵。

	《笑傲江湖》	《万历十五年》	《人间词话》	《云海玉弓缘》	《人类的故事》
赵大	5	?	?	3	2
钱二	?	5	3	?	5
孙三	5	3	?	?	?
李四	3	?	5	4	?

这里的核心假设是，用户的偏好和书籍的属性是由少数几个潜在因素（如作者、类别、写作风格等）决定的。因此，完整的评分矩阵虽然巨大，但其内在信息是高度相关的，这使得该矩阵具有低秩 (low-rank) 的特性。一个低秩矩阵可以看作是稀疏向量在高维空间中的推广。矩阵补全的目标就是利用已知的少量评分，恢复出整个低秩矩阵。这个问题可以被形式化为以下优化问题：
$$\underset{\mathbf{X}}{\min }\text{rank}(\mathbf{X})\text{s.t.}{\mathbf{X}}_{ij}={\mathbf{A}}_{ij},(i,j)\in \Omega$$
$\Omega$ 表示我们已知的元素位置 $(i,j)$，这也是一个NP难题，这里我们用核范数做近似即：
$$\Vert \mathbf{X}{\Vert }_{\ast }=\sum _k{\sigma }_k(\mathbf{X})$$
其中$\Vert \cdot {\Vert }_{\ast }$为核范数，${\sigma }_k(\mathbf{X})$为奇异值，于是优化目标转为
$$\underset{\mathbf{X}}{\min }\Vert \mathbf{X}{\Vert }_{\ast }\text{s.t.}{\mathbf{X}}_{ij}={\mathbf{A}}_{ij},\forall (i,j)\in \Omega$$

这是一个凸优化问题，使用半正定规划可解。