11.1 子集搜索与评价

我们将属性称为特征
相关特征：对当前学习任务有用的属性。
无关特征：对当前学习任务无用的属性。
特征选择：从给远的特征集合中选择出相关特征子集的过程。

特征选择是显示机器学习任务中重要的"数据预处理"过程。
有两个意义：
① 减少无关属性，减轻维数灾难。
② 留下关键属性，降低学习任务的难度。

特征选择的过程中要保证不丢失重要特征，否则将降低学习器性能。假设初始的特征集包含了所有重要特征。

欲从初始的特征集合中选取一个包含了所有重要信息的特征子集，可行的做法是产生一个"候选子集"，评价出它的好坏，基于评价结果产生下一个候选子集，再对其进行评价……这个过程持续进行下去，直至无法找到更好的候选子集为止。

上述过程涉及两个关键环节:
如何根据评价结果获取下一个候选特征子集?
如何评价候选特征子集的好坏?

给定特征集合{a₁,a₂,……,a_d}，可以将每个特征看作一个候选子集。

环节1：子集搜索问题(如何根据评价结果获取下一个候选特征子集?)
1）前向搜索
对d个候选子集进行评价，假设{a₂}最优，于是将{a₂}作为第一轮的选定集；
然后，在选定集中加上一个特征，构成两个特征的候选子集，即{a₂,a_i}(i≠2)，假定在这d-1个候选子集中，{a₂,a₄}最优，且优于{a₂}，则作为选定集，
重复这样的过程，直到第k+1轮，最优的候选子集{a₂,a₄,……,a_i}不如第k轮的选定集时，则停止生成候选子集，并将第k轮的选定集作为特征选择结果。

2）后向搜索
从完整的特征集开始，每次尝试去掉一个无关特征，逐渐减少特征。

3）双向搜索
将前向与后向搜索结合起来，每一轮逐渐增加选定相关特征(这些特征在后续轮中将确定不会被去除)，同时减少无关特征。
环节2：子集评价问题(如何评价候选特征子集的好坏?)
假定样本属性均为离散型的。给定数据集D，D中第i类样本所占的比例为p_i(i=1,2,3,……,|Y|)。对属性子集A，假定根据其取值将分成了V个子集{D¹, D² ,...,D^V}，每个子集中的样本在A上取值相同(4.2有相应详细解释)，可得属性子集A的信息增益

信息增益Gain(A)越大，意味着特征子集A包含的重要信息越多。于是，将信息增益作为评价准则。

将上述的子集搜索机制和子集评价机制结合，就是特征选择方法。
常见的特征选择方法大致可分为三类:
过滤式、包裹式和嵌入式

11.2 过滤式选择

过滤式方法先对数据集进行特征选择，然后再训练学习器，即先用特征选择过程对初始特征进行"过滤"，再用过滤后的特征来训练模型。其中常用的过滤式特征选择方法是Relief。

Relief过滤式特征选择方法
Relief是为二分类问题设计的。该方法利用"相关统计量"来度量特征的重要性。该统计量是一个向量，每个分量分别对应于一个初始特征。
特征子集的重要性则是由子集中每个特征所对应的相关统计量分量之和来决定。
最终只需指定一个阈值，然后选择比阈值大的相关统计量的分量所对应的特征即可。或者指定选取k特征个数，然后选择前k大相关统计量即可。

由上面可以知道，Relief关键在于如何确定统计量。

给定数据集{(x₁,y₁),(x₁,y₁),……,(x_m,y_m)}，在Relief中，对每个样本x_i有：
"猜中近邻"(near-hit)：同类样本中，与x_i最近邻的样本x_i,nh。
"猜错近邻"(near-miss)：异类样本中，与x_i最近邻的样本x_i,nm。

对于每个属性j的相关统计量的分量为

其中，x_a^j表示样本x_a在属性j上的取值；
对diff(x_a^j,x_b^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])
从上式中可以看出：
1）若x_i与其猜中近邻样本x_j,nh在属性j上的距离小于x_i与其猜错近邻样本x_j,nj在属性j上的距离，则说明属性j对区分同类与异类样本是有益的，故增大属性j所对应的统计量分量。
2）反之，若大于的话，则说明属性j对于分类起负作用，故减小属性j所对应的统计量分量。
3）最后，基于每个样本x_i在属性j上的估计结果进行平均，就得到属性j的统计量分量，分量值越大，则对应属性的分类能力就越强。

Relief-F是用于多分类的。
假定数据集D中的样本来自Y个类别。对样本x_i，若它属第k类(k∈{1,2,,…,Y})，
则Relief-F先在第k类的样本中寻找x_i的最近邻样本x_i,nh并将其作为猜中近邻，
然后在第k类之外的每个类中找到一个x_i的最近邻样本作为猜错近邻，记为x_i,l,nm (l=1,2,…,Y;且l≠k)。
且记p_l记为第l类样本在数据集D中的占比。

于是，相关统计量对应于属性j的分量为

11.3 包裹式选择

包裹式特征选择直接把最终将要使用的学习器性能作为特征子集的评价准则。包裹式特征选择的目的就是为给定学习器选择最有利于其性能、 "量身定做"的特征子集。

LVW是常用的包裹时特征选择方法。
LVW基于拉斯维加斯框架下使用随机策略来进行子集搜索，并以最终分类器的误差作为特征子集评价标准。

拉斯维加斯方法

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

11.4 嵌入式选择与L1正则化

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

给定数据集D={(x₁,y₁),(x₂,y₂),……,(x_m,y_m)}，以线性回归模型为学习模型，以平方误差为损失函数，则优化目标为

当样本特征很多，而样本数相对较少时，很容易陷入过拟合。因此为了缓解过拟合，可以对上式引入正则化项。

若引入L₂范数正则化，则优化目标称为"岭回归"，很够显著降低过拟合风险。
但我们可以引入更好的L₁范数正则化，则有

其中，λ>0，称为LASSO(最小绝对收缩选择算子)。L₁不仅可以降低过拟合风险，还可以更容易求得"稀疏解"，即LASSO求得的w会有更少的非零分量。
通过一个直观的例子来理解：假设x仅有两个属性，于是有w₁,w₂，将他们作为坐标轴；
然后画出，上式中 第一项的"等值线"，即Σ_i=1^m(y_i-w^Tx_i)²的等值线，即在(w₁,w₂)空间中平方误差项取值相同的点的连线；
接着分别画出，L₁范数和L₂范数的等值线。在(w₁,w₂)空间中L₁范数取值相同的点的连线，以及L₂范数取值相同的点的连线。

可以看出，采用L₁范数时，平方误差项等值线与L₁范数等值线的交点常出现在坐标轴上，即w₁或w₂取值为0；
而采用L₂范数时，两者的交点常出现在某个象限中，即w₁或w₂均不为0；也就是说，采用L₁范数比L₂范数更易于得到稀疏解。

基于L₁正则化的学习方法就是一种嵌入式特征选择方法，其特征选择过程与学习器训练过程融为一体，同时完成。

PGD求解L1正则化问题
可以使用近端梯度下降去求解L1正则化问题。
1）优化目标
令▽表示微分算子，对优化目标：

若f(x)可导，且▽f 满足L-Lipschitz（利普希茨连续条件），即存在常数L＞0使得：

2）泰勒展开
则在x_k处我们可以泰勒展开：

上式是严格相等，由L-Lipschitz条件我们可以看到：

这里给出了一个L的下界，且下界的形式与二阶导函数形式类似，从而泰勒展开式的二阶导便通过L替代，从而严格不等也变成了近似：

3）简化泰勒展开式
化简上式：

其中φ(x_k)是与x无关的const常数.

4）简化优化问题
这里若通过梯度下降法对f(x)进行最小化，则每一步下降迭代实际上等价于最小化二次函数f(x)，从而推广到我们最上面的优化目标，类似的可以得到每一步的迭代公式:

令

则我们可以先计算z，再求解优化问题：

5）求解上式

参考链接：
https://blog.csdn.net/kabuto_hui/article/details/88534460

11.5 稀疏表示与字典学习

稀疏表示
数据集D以矩阵表示，每一行为一个样本，每一列为一个属性。特征选择所考虑的问题是特征具有“稀疏性”，即矩阵中的许多列与当前学习任务无关，我们需要通过特征选择去除这些列。

考虑另一种稀疏性：在数据集 D 所对应的矩阵中存在很多零元素，但这些零元素并不是以整列、整行形式存在的。当样本具有这样的稀疏表示时，对学习任务有不少好处，比如稀疏表示的数据更容易线性可分。同时，稀疏表示的数据在存储上的负担不大。

我们可以通过将数据转换为“恰当稀疏”的形式，获得稀疏表示的好处，简化学习任务。这种为普通稠密表达的样本找到合适的字典，将样本转化为稀疏表示形式，从而使学习任务得以简化，模型复杂度得以降低，通常称为“字典学习”，亦称“稀疏编码”。
字典学习
给定数据集{x₁,x₂,…,x_m}，字典学习最简单的形式为

其中B∈R^dxk为字典矩阵；k称为字典的词汇量，通常由用户指定；
α_i∈R^k则是样本x_i∈R^d的稀疏表示。上式中，第一项希望由α重构x_i，第二项则是希望α尽量稀疏。

我们采用变量交替优化的策略来求解上式。
第一步：固定字典矩阵B，更新上式中的分量，我们可以用LASSO的解法(上一节中有讲过)来求解，从而为每个样本x_i找到相应的α_i。

分量

第二步：固定α_i，更新字典B，原式写为

求解该式的策略有基于逐列更新的K-SVD。令b_i表示字典矩阵B的第i列，α_i表示稀疏矩阵A的第i行，上式可以写为

在更新字典的第i列时，其他列是固定的，因此E_i是固定的，只需要对上式进行奇异值分解得到最大奇异值所对应的正交向量即可。
但是，这样做会破坏第一步得到的稀疏性，因此K-SVD在奇异值分解之前，对E_i和α_i做专门处理：αⁱ只保留非零元素，E_i只保留b_i与αⁱ的非零元素的乘积项；然后再进行奇异值分解。

反复迭代上述两步，最终即可求得字典B和样本x_i的稀疏表示 α_i。

稀疏表示的具体的过程简单描述如下：
1）确定映射字典的词汇量k，并初始化字典B，d*k，其中d为样本属性数
2）固定住字典B，用LASSO求得样本集 X 通过字典映射后的稀疏表示a_i
3）固定住α_i来更新字典B，K-SVD进行求解。
4）反复第2、3步，最终可得合适的字典B和样本X的稀疏表示a_i。

代码实现

1）载入数据，可以随便找一个张图片

import numpy as np
import pandas as pd
from scipy.io import loadmat
 
train_data_mat = loadmat("../data/train_data2.mat")
 
train_data = train_data_mat["Data"]
train_label = train_data_mat["Label"]
 
print(train_data.shape, train_label.shape)

2）初始化字典

u, s, v = np.linalg.svd(train_data)
n_comp = 50
dict_data = u[:, :n_comp]

3）字典更新

def dict_update(y, d, x, n_components):
    """
    使用KSVD更新字典的过程
    """
    for i in range(n_components):
        index = np.nonzero(x[i, :])[0]
        if len(index) == 0:
            continue
        # 更新第i列
        d[:, i] = 0
        # 计算误差矩阵
        r = (y - np.dot(d, x))[:, index]
        # 利用svd的方法，来求解更新字典和稀疏系数矩阵
        u, s, v = np.linalg.svd(r, full_matrices=False)
        # 使用左奇异矩阵的第0列更新字典
        d[:, i] = u[:, 0]
        # 使用第0个奇异值和右奇异矩阵的第0行的乘积更新稀疏系数矩阵
        for j,k in enumerate(index):
            x[i, k] = s[0] * v[0, j]
    return d, x

4）迭代更新求解
可以指定迭代更新的次数，或者指定收敛的误差。

from sklearn import linear_model
 
max_iter = 10
dictionary = dict_data
 
y = train_data
tolerance = 1e-6
 
for i in range(max_iter):
    # 稀疏编码
    x = linear_model.orthogonal_mp(dictionary, y)
    e = np.linalg.norm(y - np.dot(dictionary, x))
    if e < tolerance:
        break
    dict_update(y, dictionary, x, n_comp)
 
sparsecode = linear_model.orthogonal_mp(dictionary, y)
 
train_restruct = dictionary.dot(sparsecode)

字典学习以及稀疏特征详细理解：
https://www.cnblogs.com/hdu-zsk/p/5954658.html

字典学习过程详解：
https://www.cnblogs.com/endlesscoding/p/10090866.html#_label0

奇异值分解：
https://www.cnblogs.com/endlesscoding/p/10033527.html
https://blog.csdn.net/weixin_42462804/article/details/83905320

11.6 压缩感知

在现实任务中，我们希望可以通过部分信息来恢复全部信息。因为在实际中为了便于数据的传输存储，人们通常会将数据进行压缩，这有可能会损失一部分信息，而传输的过程中又可能会丢失一部分信息。这时候拥有根据接收到的受损的数据来恢复全部数据的能力就很重要了。压缩感知为解决此类问题提供了灵感。

假设有长度为m的离散信号x，以一个采样率进行采样，得到长度为n的采样后信号y(y也称"测量值")，其中n远小于m，有

其中，Φ∈R^nxm是对信号x的测量矩阵，它确定了以某个频率进行采样以及如何将采样样本组成采样后的信号。
若已知Φ和x，很容易求出y；但由于上式是一个欠定方程(方程的个数少于未知函数的个数)，即使将y和Φ传输给对方，也难以还原原来的x。(假定x本身不是稀疏的)

若有个线性变化Ψ∈R^mxm，使得x=Ψs，且s具有稀疏性，y可以表示为

s具有稀疏性，就可以很好解决欠定方程的问题，因为稀疏性使得未知因素大大减少。Ψ称为稀疏基，而A=ΦΨ的作用类似于字典，能将信号转化为稀疏表示。于是，若能根据y恢复s，就可以通过x=Ψs求出原来信号x。
s可以通过处理后会转化稀疏信号。如，傅里叶转换等。
压缩感知关注的是如何利用信号本身所具有的稀疏性，从部分观测样本中恢复原信号。
它可以分为两个阶段：
1）感知测量
对原始信号进行处理以获得稀疏样本表示，涉及傅里叶变换、小波变换、字典学习、稀疏编码等、
2）重构恢复
基于稀疏性从少量观测中复原信号，是压缩感知的精髓。
压缩感知的重要理论："限定等距性"(RIP)
对一个nxm(n远小于m)矩阵A，若有常数ε∈(0,1)使得任意向量s和任意A的子矩阵A_k∈R^nxk遵循下式，则称A满足k限定等距性

A满足k限定等距性

这时，可以通过下面的优化问题从y中恢复稀疏信号s，再恢复得到x。

压缩感知问题就可通过L₁范数最小化问题求解，例如上式可转为LASSO的等价形式再通过PGD求解。
压缩感知有很多应用。
如矩阵补全技术。该问题的形式为：

其中X为需要恢复的稀疏信号，rank(X)表示矩阵的秩。 A是已观测信号，Ω是已知元素的下标(i,j)的集合。
注意到，rank(X)在集合X∈R^m×n:||X||²_F≤1}上的凸包是X的核范数:

核范数

其中σ_j(X)表示X的奇异值，即矩阵的核范数为矩阵的奇异值之和。
我们可以将优化目标转化为，通过最小化矩阵核范数来求解，有

上式是一个凸优化问题，可以通过半正定规划SDP求解。
理论上，当满足一定条件，A的秩为r, n≪m，则只需要观察到O(mrlog2m)个元素就可以完美恢复出A。