CA50A431-C466-4155-BB60-FD9B7DFAE6EF

1 - 子集搜索与评价

1.1 - 特征

特征的定义：Feature，属性

按照对当前学习任务是否有用，可分为：

  • 有用 → 相关特征 Relevant Feature
  • 没用 → 无关特征 Irrelevant Feature

1.2 - 特征选择 Feature Selection

概述：

  • 从给定的特征集合中选择出相关特征子集的过程
  • 一个重要的数据预处理(data preprocessing)过程

原因（Why）：

  • ①属性过多造成“维数灾难”
  • ②去除不相关特征可降低学习任务的难度

注意

  1. 必须确保不丢失重要特征，缺失重要特征会影响后续学习过程。
  2. 数据集相同，不同的学习任务的重要特征往往不同。

冗余特征(redundant feature, 可通过其他特征推演得出）：

  • ①大多数情况无用
  • ②有时可以降低学习难度 → 该特征对应学习任务所需的某一“中间概念”

⭐️假定：

  • ①数据中不涉及冗余特征
  • ②初始的特征集合中包含了所有重要信息

1.3 - 如何选取特征子集？

  • 若无背景知识作为先验假设，只能遍历所有可能子集 → 不可行，组合爆炸
  • 选用“候选子集”，在此基础上增减特征，根据评价准则得到最优特征子集

特征选择方法

（1） “前向”(forward) 搜索

  • ①将特征集合中每个特征看做一个候选子集，依次评价，选取最优的候选子集作为第一轮的选定集；
  • ②往最优的候选子集里加入一个特征，依次评价，若得到的最优候选子集优于上一轮的选定集，则本轮的选定集为本轮的最优候选子集；
  • …
  • 直至第k+1轮的最优候选子集劣于第k轮的选定集，则停止生成候选子集，取第k轮选定集作为特征选择结果。
  • 从一个特征开始，逐步增加特征，直至达到最优结果

（2）“后向”(backward) 搜索

  • 从完整特征集合开始，逐步剔除特征，直至达到最优结果

（3）“双向”(bidirectional) 搜索

  • 结合“前向”与“后向”搜索

Summary

以上三种方法都是“贪心”策略，因为：

  1. 仅考虑使本轮选定集最优
  2. 不穷举可能错过最佳特征子集

e.g. 第三轮假定选择$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}$都更优

1.5 - 子集评价 (subset evaluation)

以“分类”问题为例：

第二个环节是“子集评价”(subset evaluation)问题．给定数据集$D$,假定$D$中第$i$类样本所占的比例为$p_i (i = 1,2,…,|\cal{Y}|)$．为便于讨论，假定样本属性均为离散型．对属性子集$A$，假定根据其取值将$D$分成了$V$个子集${D_1,D_2,…,D_V}$，每个子集中的样本在$A$上取值相同，于是我们可计算属性子集$A$的信息增益

-w509

假设每个属性有：$v$个可取值，则$V = v^{|A|}$，这可能是一个很大的值，因此实践中通常是从子集搜索过程中前一轮属性子集的评价值出发来进行计算。

-w492

信息增益$Gain(A$越大，意味着特征子集$A$包含的有助于分类的信息越多．于是，对每个候选特征子集，我们可基于训练数据集$D$来计算其信息增益，以此作为评价准则．

更一般的，特征子集$A$实际上确定了对数据集$D$的一个划分，每个划分区域对应着$A$上的一个取值，而样本标记信息$Y$则对应着对$D$的真实划分，通过估算这两个划分的差异，就能对$A$进行评价．与y对应的划分的差异越小，则说明A越好．信息嫡仅是判断这个差异的一种途径，其他能判断两个划分差异的机制都能用于特征子集评价．

许多“多样性度量”如不合度量、相关系数等，稍加调整即可用于特征子集评价，参见8.5.2节。

Summary

  • 信息增益 Gain(A)
  • 其他能判断特征子集划分与样本标记信息划分差异的机制

2 - 特征选择方法

  • 特征选择方法 = 子集选择 + 子集评价
  • 三类方法：①过滤式；②包裹式；③嵌入式

2.1 - 过滤式(Filter)选择

  • 特点：特征选择 → 训练学习器，特征选择与学习器训练无关
  • 运行效率：很高，运行时间随采样次数、特征数目线性增长（Relief）
  • 著名方法：Relief (Relevant Features) 法

  • 适用范围：二分类问题（改进的Relief-F法可处理多分类问题）

  • 方法概述：设计“相关统计量”来度量特征的重要性（Key: 如何设计“相关统计量”），指定阈值$τ$或欲选取特征个数$k$来决定所选特征。

  • 关键概念：

    • 相关统计量：向量，初始特征对应分量，特征子集重要性由初始特征对应分量加总得到

  • 相关概念：

    • 猜中近邻 near-hit：在某个样本的同类样本中，距离该样本最近的样本
    • 猜错近邻 near-miss：在某个样本的异类样本中，距离该样本最近的样本

  • 算法原理：（针对二分类问题，即样本标记只有两个取值）

    • ①计算每个样本与$nh$、$nm$在某初始特征上的距离，平均；
    • ②$d(猜中) < d(猜错)$ ，则该属性对区分同、异类样本有益，增加该统计量分量（$d(猜错)$系数为正）；反之（$d(猜中)$系数为负），减少。

显然，Relief的关键是如何确定相关统计量．给定训练集${(x_1, y_1),(x_2,y_2), .. .,(x_m,y_m)}$，对每个示例$\boldsymbol{x}_i$，Relief先在$\boldsymbol{x}i$的同类样本中寻找其最近邻$\boldsymbol{x}{i,nh}$，称为“猜中近邻”(near-hit)，再从$\boldsymbol{x}i$的异类样本中寻找其最近邻$\boldsymbol{x}{i,nh}$，称为“猜错近邻”(near-miss). 然后，相关统计量对应于属性$j$的分量为 -w469

其中$x_a^j$表示样本$\boldsymbol{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) = |x_a^j - x_b^j|$，注意$x_a^j, x_b^j$已规范化到$[0,1]$区间．

算法步骤

  • ①将属性规范化到$[0, 1]$区间；
  • ②取样本$\boldsymbol{x}i$，计算其与其他样本的距离，确定$x{i,nh}$和$x_{i,nm}$;
  • ③对样本$\boldsymbol{x}_i$，计算其在每个属性$j$上与$nh$和$nm$的$diff（某种距离度量）$;
  • ④计算相关统计量对应属性$j$的分量$\delta^j$

式（11.3）中的$i$指出了用于平均的样本下标．实际上Relief只需在数据集的采样上而不必在整个数据集上估计相关统计量[Kira and Rendell, 1992]．显然， Relief的时间开销随采样次数以及原始特征数线性增长，因此是一个运行效率很高的过滤式特征选择算法．

Relief是为二分类问题设计的，其扩展变体Relief-F [Kononenko, 1994]能处理多分类问题．假定数据集$D$中的样本来自$|\cal{Y}|$个类别．对示例$\boldsymbol{x}_i$，若它属于第$k$类$k \in {1,2,…|\cal{Y}| }$，则Relief-F先在第k类的样本中寻找$\boldsymbol{x}i$的最近邻示例$\boldsymbol{x}{i,nh}$并将其作为猜中近邻，然后在第$k$类之外的每个类中找到一个$\boldsymbol{x}i$的最近邻示例作为猜错近邻，记为$\boldsymbol{x}{i,l,nm} (l=1,2,…,|\cal{Y}|\, ; \, l\neq k)$．于是，相关统计量对应于属性$j$的分量为

-w472

其中$p_l$为第$l$类样本在数据集$D$中所占的比例．

2.2 - 包裹式(Wrapper)选择

  • 特点：
    • 把最终使用的学习器性能作为特征子集的评价标准，“量身定做”
    • 性能一般优于过滤式方法
    • 过多特征数目和较大停止条件控制参数会增加训练耗时，再加上运行时间限制可能无解（LVW）
  • 运行效率：通常>>过滤式方法（多次训练学习器耗时长）
  • 著名方法：LVW (Las Vegas Wrapper)

  • 适用范围：- -

  • 方法概述：

    • 子集选择：用随机策略在Las Vegas Method框架下搜索
    • 子集评价：最终分类器的误差

  • 关键定义：

    • 循环条件：$t < T$
    • $T$ - 【停止条件控制参数】最大连续循环次数限制（连续循环T次后，学习器仍未改进则退出循环）
    • $t$ - 连续循环次数flag

  • 相关定义&标记：

    • $E$ - 学习器误差；$d$ - 特征子集中特征个数；$A$ - 特征子集。
    • 上轮标记：$E, d, A^\ast$
    • 本轮标记：$E’,d’,A’$

  • 算法步骤：

-w602

注：

  • 1-4：初始化；
  • 8：在本轮特征子集A’上，用Cross Validation估计学习器误差）；
  • 9：保留条件：OR（本轮误差 < 上轮误差，本轮误差 = 上轮误差 & 本轮特征个数 < 上轮特征个数）

因为LVW算法是在Las Vegas Method框架下建立的，所以若初始特征数目很多、T较大，则LVW算法可能运行很长时间都达不到停止条件。即，若再加上时间限制，可能给不出解。

拉斯维加斯方法和蒙特卡罗方法是两个以著赌城名字命名的随机化方法．两者的主要区别是：若有时间限制，则拉斯维加斯方法或者给出满足要求的解，或者不给出解，而蒙特卡罗方法一定会给出解，虽然给出的解未必满足要求；若无时间限制，则两者都能给出满足要求的解．

2.3 - 嵌入式(Embedding)选择

  • 特点：在训练学习器过程中自动进行特征选择，训练学习器与特征选择同时完成
  • 运行效率：- -
  • 著名方法：L1范数正则化
  • 适用范围：以线性回归模型为例
  • 关键概念：
    • 岭回归(ridge regression)
    • LASSO ( Least Absolute Shrinkage and Selection Operator)
  • 方法概述：

令最优化目标函数为平方差损失函数 -w524

因为(11.5)在特征多、样本少时容易过拟合。为了缓解过拟合，对(11.5)引入正则化项。 引入L1范数正则化，得 “LASSO”： -w492 其中，正则化参数$λ > 0$。求出(11.7)的解即得所选特征子集及最终学习器。

注意

  • 用其他p范数也可以。事实上，对ω施加“稀疏约束”（即希望ω的非零分量尽可能少）最自然的是使用L0范数，但L0范数不连续，难以优化求解，因此常使用L1范数。
  • 若引入L2范数正则化，得 “岭回归”： -w503

summary

  • L1范数和L2范数正则化都能降低过拟合风险，且L1效果优于L2
  • L1范数比L2求得的ω会有更少的分量，即更容易获得“稀疏”(sparse)解。

范数

p-范数 (p-norm):

若$\boldsymbol{x} = [x_1, x_2, \cdots,x_n]^T$，那么$\boldsymbol{x}$的$p$范数为：$||\boldsymbol{x}||_p = (|x_1|^p + |x_2|^p + \cdots + |x_n|^p)^{\frac{1}{p}}$

  • $1$-范数：$||\boldsymbol{x}||_1 = (|x_1| + |x_2| + \cdots + |x_n|)$
  • $2$-范数：$||\boldsymbol{x}||_2 = (|x_1|^2 + |x_2|^2 + \cdots + |x_n|^2)^{\frac{1}{2}}$
  • $\infty$-范数：$||\boldsymbol{x}||_{\infty} = \max (|x_1| + |x_2| + \cdots + |x_n|)$

❓ 解释L1范数更容易获得稀疏解： -w639

为了理解这一点，我们来看一个直观的例子：假定$\boldsymbol{x}$仅有两个属性，于是无论式（11.6）还是（11.7）解出的$\boldsymbol{w}$都只有两个分量，即$w_1, w_2$，我们将其作为两个坐标轴，然后在图中绘制出式（11.6）与（11.7）的第一项的“等值线”，即在$(w_1, w_2)$空间中平方误差项取值相同的点的连线，再分别绘制出$L_1$范数与$L_2$范数的等值线，即在$(w_1, w_2)$空间中$L_1$范数取值相同的点的连线，以及$L_2$范数取值相同的点的连线，如图11.2所示．式（11.6）与（11.7）的解要在平方误差项与正则化项之间折中，即出现在图中平方误差项等值线与正则化项等值线相交处．由图11.2可看出，采用$L_1$范数时平方误差项等值线与正则化项等值线的交点常出现在坐标轴上，即$w_1$或$w_2$为0，而在采用$L_2$范数时，两者的交点常出现在某个象限中，即$w_1$或$w_2$均非$0$;换言之，采用$L_1$范数比$L_2$范数更易于得到稀疏解．

  • Q：为什么“子集选择”与“子集评价”同时完成？

  • A：$ω$解出稀疏解 ⇒ 初始特征中仅有系数非零的特征才有作用（经过筛选被留在最终学习器中，此方法就是“嵌入式”的特征选择方法）

  • Q：如何求解L1正则化问题？

  • A：使用“近端梯度下降”（Proximal Gradient Descent, PGD）方法。

$L_1$正则化问题的求解可使用近端梯度下降（Proximal Gradient Descent, 简称PGD) [Boyd and Vandenberghe, 2004]．具体来说，令$\Delta$表示微分算子，对优化目标 -w601

若$f(x)$可导，且$\nabla f$满足L-Lipschitz条件，即存在常数$L>0$使得 -w602

则在$\boldsymbol{x}_k$附近可将$f(\boldsymbol{x})$通过二阶泰勒展式近似为

-w595

其中$const$是与$\boldsymbol{x}$无关的常数$\langle \cdot \, , \, \cdot \rangle $表示内积．显然，式（11.10）的最小值在如下$\boldsymbol{x}_{k+1}$获得： -w591

于是，若通过梯度下降法对$f(\boldsymbol{x})$进行最小化，则每一步梯度下降迭代实际 上等价于最小化二次函数$\hat{f}(\boldsymbol{x})$．将这个思想推广到式（11.8)，则能类似地得到其每一步迭代应为 -w595

即在每一步对$f(\boldsymbol{x})$进行梯度下降迭代的同时考虑$L_1$范数最小化.

对于式（11.12)，可先计算$\boldsymbol{z} = \boldsymbol{x}_k - \frac{1}{L} \nabla f(\boldsymbol{x}_k)$，然后求解 -w596

令$x^i$表示$\boldsymbol{x}$的第$i$个分量，将式（11.13）按分量展开可看出，其中不存在$x^i x^j (i \neq j)$这样的项，即$\boldsymbol{x}$的各分量互不影响，于是式（11.13)有闭式解

-w602

其中$x{k+1}^i$与户分别是$\boldsymbol{x}{k+1}$与$\boldsymbol{z}$的第$i$个分量．因此，通过PGD能使LASSO和其他基于$L_1$范数最小化的方法得以快速求解．

3 - 稀疏表示与字典学习

适用场景：

需要进行特征选择的特征是“稀疏”的。若把数据集看做一个矩阵$D$，则$D$的某些列（特征）是与当前学习任务无关的，应去除。

以“字典”为例解释稀疏表示：

  • 数据集矩阵$D$中有很多零元素，零散分布的（不是整行或整列的）。

若令 $样本 ← 文本文档$，$特征 ← 文本中的每个字$，$特征取值 ← 每个字出现的次数$，以$D$的行表示样本，$D$的列表示特征，则$D$是稀疏的。

稀疏的好处：

  1. 用字频形式表示文本文档，呈现稀疏特征，使大部分问题线性可分，可用线性支持向量机处理；
  2. 对稀疏矩阵的高效储存方法，大大减轻了储存负担。

合适的稀疏【恰当稀疏】：

  1. 用“康熙字典”作列特征（生僻字太多），很可能使D稀疏过头【“过度稀疏”】，用“现代汉语词典”可能稀疏程度适中【“恰当稀疏”】。
  2. “恰当稀疏”可体现稀疏的好处，利于处理学习任务；“过度稀疏”则不能。

⭐️How?如何实现“恰当稀疏”？

– 【字典学习dictionary learning（稀疏编码sparse coding）】

Goal:

与文本文档的处理类似，我们对其他任务（如，图像识别）学习出一个“字典”，利用“恰当稀疏”优势，完成学习任务。

字典学习侧重字典的产生过程，稀疏编码侧重统计频次的过程。本书不加区分，以字典学习代替。字典，亦称“码书”（code book）；字典学习，亦称“码书学习”（ciodebook learning）

给定数据集${ \boldsymbol{x}_1, \boldsymbol{x}_2, \cdots, \boldsymbol{x}_m}$，字典学习最简单的形式为

-w605

其中$\boldsymbol{B} \in \mathbb{R}^{d \times k}$为字典矩阵，$k$称为字典的词汇量，通常由用户指定，$\boldsymbol{\alpha}_i \in \mathbb{R}^k$则是样本$\boldsymbol{x}_i \in \mathbb{R}^d$的稀疏表示．显然，式（11.15）的第一项是希望由$\boldsymbol{\alpha}_i$能很好地重构$\boldsymbol{x}_i$，第二项则是希望$\boldsymbol{\alpha}_i$尽量稀疏．

与LASSO相比，式（11.15）显然麻烦得多，因为除了类似于式（11.7）中$\boldsymbol{w}$的$\boldsymbol{\alpha}_i$，还需学习字典矩阵$\boldsymbol{B}$．不过，受LASSO的启发，我们可采用变量交替优化 的策略来求解式（11.15).

首先在第一步，我们固定住字典$\boldsymbol{B}$，若将式（11.15）按分量展开，可看出其中不涉及$\alpha_i^u \alpha_i^v$这样的交叉项，于是可参照LASSO的解法求解下式，从 而为每个样本$\boldsymbol{x}_i$找到相应的$\boldsymbol{\alpha}_i$:

-w599

在第二步，我们固定住$\boldsymbol{\alpha}_i$来更新字典$\boldsymbol{B}$，此时可将式（11.15）写为

-w592

其中$\boldsymbol{X}=( \boldsymbol{x}_1, \boldsymbol{x}_2, \cdots, \boldsymbol{x}_m) \in \mathbb{R}^{d \times m}$, $\boldsymbol{A}=(\boldsymbol{\alpha}_1, \boldsymbol{\alpha}_2, … ,\boldsymbol{\alpha}_m) \in \mathbb{R}^{k \times m}$, $||\cdot||_F$是矩阵的Frobenius范数．式（11.17）有多种求解方法，常用的有基于逐列更新策略的KSVD [Aharon et al., 2006]．令$\boldsymbol{b}_i$表示字典矩阵$\boldsymbol{B}$的第$i$列，$\boldsymbol{\alpha}_i$表示稀疏矩阵$\boldsymbol{A}$的第$i$行，式（11.17）可重写为 -w585

在更新字典的第$i$列时，其他各列都是固定的，因此$\boldsymbol{E}i = \sum{j \neq i} \boldsymbol{b}_j \boldsymbol{\alpha}^j$是固定的，于是最小化式（11.18）原则上只需对$\boldsymbol{E}_i$进行奇异值分解以取得最大奇异值所对应的正交向量．然而，直接对$\boldsymbol{E}_i$进行奇异值分解会同时修改$\boldsymbol{b}_i$和$\boldsymbol{\alpha}^i$，从而可 能破坏$\boldsymbol{A}$的稀疏性．为避免发生这种情况，KSVD对$\boldsymbol{E}_i$和$\boldsymbol{\alpha}^i$进行专门处理：$\boldsymbol{\alpha}^i$仅保留非零元素，$\boldsymbol{E}_i$则仅保留$\boldsymbol{b}_i$与$\boldsymbol{\alpha}^i$的非零元素的乘积项，然后再进行奇异值分解，这样就保持了第一步所得到的稀疏性．

初始化字典矩阵$\boldsymbol{B}$之后反复迭代上述两步，最终即可求得字典$\boldsymbol{B}$和样本$\boldsymbol{x}_i$的稀疏表示$\boldsymbol{\alpha}^i$。在上述字典学习过程中，用户能通过设置词汇量$k$的大小来控制字典的规模，从而影响到稀疏程度．