范数
- $L_0$范数表示向量中非零元素的个数：$\mid\mid x \mid\mid_0 = count(x_i) while x_i \neq 0$
使用这个范数希望参数的大部分元素是0（稀疏数据），通过最优化范数，可以寻找最优稀疏特征，不过这个范数的最优问题是NP难度。
- $L_1$范数表示向量中每个元素绝对值的和：$\mid\mid x \mid\mid_1=\sum_{i=1}^n \mid x_i \mid$
$L_1$范数是$L_0$范数的最优凸优化，常用$L_1$代替$L_0$范数。
$L_2$范数即欧式距离：$\mid\mid x \mid\mid_2=\sqrt{\sum_{i=1}^n x_i^2}$
Forbenius范数：$\mid\mid A \mid\mid_F = \sqrt{\sum\limits_{i=1}^m\sum\limits_{j=1}^n \mid a_{ij} \mid^2}$
子图搜索与特征选择
给定特征集合${a_1,a_2,…,a_d }$，我们可将每个特征看作一个候选子集，对这d个候选单特征子集进行评价，假定$a_2$最优，于是将$a_2$作为第一轮的选定集；然后，在上一轮的选定集中加入一个特征，构成包含两个特征的候选子集，假定在这d-1个候选两特征子集中$(a_2,a_4)$最优，且优于$(a_2)$，于是将$(a_2,a_4)$作为本轮的选定集；
……假定在第it+1轮时，最优的候选(k+1)特征子集不如上一轮的选定集，则停止生成候选子集，并将上一轮选定的k特征集合作为特征选择结果.这样逐渐增加相关特征的策略称为“前向”（forward)搜索。
类似的，若我们从完整的特征集合开始，每次尝试去掉一个无关特征，这样逐渐减少特征的策略称为“后向”（backward)搜索.还可将前向与后向搜索结合起来，每一轮逐渐增加选定相关特征(这些特征在后续轮中将确定不会被去除同时减少无关特征，这样的策略称为“双向”（bidirectional)搜索.
常见的特征选择方法大致分为三类，过滤式、包裹式和嵌入式。
过滤式
过滤式先对数据集进行特征选择，然后再训练学习器，特侦选择过程与后续学习器无关。这相当于先用特征选择过程对初始特征进行过滤，再用过滤后的特征来训练模型。
Relif
过滤式特征选择方法，方法设计了一个相关统计量度量特征的重要性。统计量是一个向量，每个向量分别对应与一个初始特征，而特征子集的重要性则是由子集中每个特征对应的相关统计量分量之和决定。
过滤的方法就是设定一个阈值$\tau$，选择比$\tau$大的相关统计量分量对应的特征即可。
给定训练集${(x_1,y_1),(x_2,y_2),…,(x_m,y_m)}$，对每个示例$x_i$，算法先在$x_i$的同类样本中寻找其最近邻$x_{i,nh}$，称为猜中近邻，再从$x_i$的异类样本中寻找其最近临$x_{i,nm}$，称为猜错近邻，然后相关统计量对应于属性j的分量为：$\delta^j=\sum\limits_i -diff(x_i^j,x_{i,nh}^j)^2+diff(x_i^j,x_{i,nm}^j)^2$
其中$x_a^j$表示样本$x_a$在属性j上的取指，若属性j为离散型，则$diff(x_a^j,x_b^j)=0 if x_a^j==x_b^j else 1$，若是连续型，$diff(x_a^j,x_b^j)=\mid x_a^j-x_b^j \mid$
若$x_i$与其猜中近邻在属性j上的距离小于$x_i$与其猜错近邻的距离，则说明属性j对区分同类与异类样本是有益的，则增大属性j对应的统计分量。
包裹式选择
包裹式特征选择直接把最终将要使用的学习器性能作为特征子集的评价准则。
从最终学习性能来看，包裹式选择比过滤式更好，然而需要的开销要大得多。
LVM
使用随机策略进行子图搜集，并以最终分类器的误差作为特征子集的评价准则。随机搜索，每次都要进行学习，交叉验证的结果作为误差标准比较，所以开销比较大。
嵌入式选择
嵌入式特征选择是将特征选择过程与学习器训练过程融为一体，两者在同一个优化过程中完成，即在学习器训练过程中自动的进行了特征选择。
给定数据集$D={(x_1,y_1),(x_2,y_2),…,(x_m,y_m)}$，我们考虑最简单的线性回归模型，以平方误差为损失函数：
$\min\limits_{\omega} \sum\limits_{i=1}^m (y_i-\omega^Tx_i)^2$
当样本特征很多，样本数目较少时，容易陷入过拟合，此时需要加入正则化项：
$\min\limits_{\omega} \sum\limits_{i=1}^m (y_i-\omega^Tx_i)^2+\lambda\mid\mid \omega \mid\mid_2^2$
$\min\limits_{\omega} \sum\limits_{i=1}^m (y_i-\omega^Tx_i)^2+\lambda\mid\mid \omega \mid\mid_1^2$
分别使用了$L_2,L_1$范数，前者能比后者更易于获得稀疏解：求得的$\omega$有更少的非零向量。所以$\omega$取得的稀疏解意味着初始的d个特征中仅有对应着$\omega$的非零分量特征才会出现在最终模型中，于是求解$L_1$范数正则化的结果是得到了仅采用一部分初始特征的模型，基于$L_1$正则化的学习方法就是一种嵌入式特征选择方法。
稀疏表示与字典学习
稀疏表达形式对学习任务来说有不少的好处，例如线性的SVM之所以在文本数据上有很好的性能，就是因为文本数据使用上述的字频表示后有高度的稀疏性，使大多数问题变得线性可分。同时稀疏表示可以减少存储空间。
若给定数据集D是稠密的，普通非稀疏数据，我们需要一个“字典”，将样本转化成为合适的稀疏表示形式，使得模型复杂度降低，称为字典学习或者稀疏编码。
字典学习侧重于学得字典的过程；稀疏编码偏重对样本进行稀疏表达的过程。
给定数据集（训练集）${x_1,x_2,…,x_m}$，字典学习最简单的形式为$\min\limits_{B,\alpha_i}\sum\limits_{i=1}^m \mid\mid x_i-B\alpha_i \mid\mid_2^2 +\lambda\sum\limits_{i=1}^m \mid\mid \alpha_i \mid\mid_1$
前面的部分是最小化训练样本与学习的字典学习模型之间的误差，后面则是字典学习模型的$L_1$范数，即寻找稀疏数据。
其中B为字典矩阵，k为字典词汇量，由用户设定，$\alpha_i \in R^k$是样本$x_i \in R^d$的稀疏表示。
因为这里我们需要对B和%\alpha%进行学习，我们使用变量交替优化的策略求解。
- 固定字典B，我ie每个样本$x_i$找到相应的$\alpha_i$
$\min\limits_{\alpha_i} \mid\mid x_i-B\alpha_i \mid\mid_2^2 + \alpha\mid \alpha_i \mid_1$
- 固定$\alpha_i$来更新字典B，此时原式改为了$\min\limits_{B}\mid\mid X-BA \mid\mid_F^2$
其中$A=(\alpha_1,\alpha_2,…,\alpha_m)$，
初始化字典B后，迭代这两步，通过设置k的数值控制稀疏程度。
压缩感知
压缩感知关注的是如何利用信号本身所具有的稀疏性，从部分观测样本中恢复原信号。通常认为压缩感知分为：感知测量和重构恢复两个阶段。前者关注如何对原始信号进行处理以获得稀疏样本表示，这方面技术包括傅里叶变换、小波变换以及字典学习和稀疏编码；重构恢复则主要针对基于稀疏性从少量观测中恢复原信号，这部分是压缩感知的核心。
