第六章 机器学习之稀疏学习
简单介绍稀疏学习所处的位置,作用,以及常见应用.
6.1 L1正则化
相关定义:
在先前未观测到的输入上表现良好的能力被称为泛化（generalization）
欠拟合是指模型不能在训练集上获得足够低的误差。而过拟合是指训练误差和和测试误差之间的差距太大。 通过调整模型的容量（capacity），我们可以控制模型是否偏向于过拟合或者欠拟合。通俗地，模型的容量是指其拟合各种函数的能力。
则化是指我们修改学习算法，使其降低泛化误差.
\[\min *{\boldsymbol{w}} \sum*{i=1}^{m}\left(y_{i}-\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}*{i}\right)^{2}+\lambda|\boldsymbol{w}|*{2}^{2}\][解析]：该式为加入了$\mathrm{L}_2$正规化项的优化目标，也叫”岭回归”，$\lambda$用来调节误差项和正规化项的相对重要性，引入正规化项的目的是为了防止$w$的分量过太而导致过拟合的风险。
对于一个学习任务，给定了属性集，其中某些属性可能对于学习来说是很关键的，但是有些属性可能就意义不大。从给定的特征集合中选出相关特征子集的过程称作特征选择feature selection。常见的特征选择方法大致可分为三类：过滤式filter、包裹式wrapper、嵌入式embedding 。
6.2 稀疏表示与字典学习(dictionary learning)
稀疏表示(sparse representation)
为普通稠密表达的样本找到合适的字典,将样本转化为合适的稀疏表示形式,从而使学习任务 得以简化,模型复杂度得以降低,通常称为“字典学习”,亦称“稀疏编码”(sparse coding).
核心算法步骤如下:
输入: 字典𝐃,原始样本向量𝐘,稀疏度K;
输出: 的一稀疏的逼近;
初始化: 残差r0=y,索引集∧0=∅,t=1;
循环执行步骤1-5
步骤一: 找出残差r和字典𝐃的列d的积中最大值所对应的脚标p
步骤二: 更新索引集∧t 的=∧t-1,一人一凡,一记录找到的传感矩阵中的重建原子集合
中,中卜,汽,
步骤由最小二乘得到又一少一电划
步骤更新残差叮夕一电又,二
步骤判断是否满足,若满足,则停止迭代若不满足,则执行步骤
【」口 【」口勺 【」高睿,赵瑞珍 基于压缩传感的匹配追踪重建算法研究. 2009.6
\min {\boldsymbol{x}} f(\boldsymbol{x})+\lambda|\boldsymbol{x}|{1}
\mathbf{R}^{m \times K}
\min {\boldsymbol{x}{i}}\left|\boldsymbol{y}{i}-\mathbf{D} \boldsymbol{x}{i}\right|{2}^{2}+\lambda\left|\boldsymbol{x}{i}\right|_{1}
\min {\mathbf{D}}|\mathbf{Y}-\mathbf{D X}|{F}^{2}
D^{(t)}=Y\left(X^{(t-1)}\right)^{\mathrm{T}}\left(X^{(t-1)}\left(X^{(t-1)}\right)^{\mathrm{T}}\right)^{-1}
|\cdot|_{F}
随着稀疏表示模型的发展，研究者们会为所有样本学习一个字典，然而，不管是整体稀疏表示，还是分组稀疏表示，其基本思想都是使用训练样本作为基来线性组合表示一幅图像，即均将整个样本训练集作为“字典”，但是这种“字典”是冗余的且针对特定任务不具有判别性，于是，很多字典学习（Dictionary Learning，DL）方法涌现在稀疏信号处理领域。初期的最优方向算法（Method of Optimal Directions，MOD）[17]是最早的字典学习方法，此方法利用最小二乘法来更新字典并获得稀疏表示系数，但计算过程繁琐复杂，后来考虑到 MOD 的优化问题，在线字典学习方法（Online Dictionary Learning，ODL）[18]被提出，同样使用交替更新的方式来获得最优的字典和稀疏表示系数，在 2006 年又有研究者提出了经典的 K-SVD 算法[4]，此算法以 K 均值聚类为思想基础，在优化求解过程中，按列对字典原子进行更新，同时更新稀疏表示系数，且具有较快收敛的特点，但它与 Mate-face-learning 方法[19]都属于非监督的字典学习方法，因为均未用到样本的类别标签信息。这些字典学习方法虽然对信号有较好的表示能力，但对于图像分类与人脸识别等任务没有较强的判别能力.
因此，针对图像分类任务，研究者们考虑在字典学习方法中使用类别结构信息，对稀疏表示系数或字典施加相关约束同时使用多种范数约束[20]，旨在学习一个具有判别性的字典和稀疏性的表示系数，从而获得有益于图像分类性能的字典学习模型。如基于 K-SVD 的判别性 K-SVD 算法（Discriminative K-SVD，D-KSVD）[21]，此算法为所有类别学习一个通用字典，同时学习一个线性分类器，使得来自同一个类的信号具有相似的稀疏编码，从而获取具有判别能力的字典。而经典的标签一致性 K-SVD 算法（Label Consistent K-SVD，LC-KSVD）[22][23]是根据类别标签信息，构造判别性稀疏矩阵，并将其对稀疏表示系数进行约束,充分利用了样本中的判别信息且得到一个更具判别性的字典。2011 年，Yang 等人利用 Fisher 判别性准则，通过实现最小化类内距离及最大化类间距离，构造相关约束项，提出了 Fisher 判别性字典学习算法（Fishe Discriminative Dictionary Learning，FDDL）[24][25]，此算法使得稀疏表示系数具有判别性，且获得一个结构化的判别性字典。2014 年，Li 等人提出低秩正则化判别字典学习方法（Discriminative Dictionary Learning with Low-rank Regularization，D2L2R2）[26],此算法基于 Fisher 思想，对稀疏系数和类字典同时施加低秩约束。鉴于 Fisher 准则在字典学习模型中表现出的优势，2015 年，Vu 等人根据 Fisher 思想提出判别特征导向字典学习（Discriminative Feature-Oriented Dictionary Learning，DFDL）[27][28],从类内和类间角度构造重构误差项来学习判别性字典和稀疏表示系数，并在医学图像分类任务上获得了可观的效果。甚有学者基于特征的共性与个性思想，提出共同字典和特殊字典学习（The Commonality and The Particularity，COPAR）[29]，且在 2015 年，Vu 等人提出了低秩-共同字典学习（Low-rank Shared Dictionary Learning，LRSDL）[30][31]，对共同字典进行低秩约束，提升了训练速度。
事实上，为了获取复杂图像更有效的信息，且鉴于深度学习在图像分类领域的广
泛应用，Snigdha 等人于 2016 年提出了贪婪深度字典学习方法（Greedy Deep
Dictionary Learning，DDL）[
37]，此方法将传统单层字典学习方法中的稀疏系数定义为稀疏特征，算法首先通过原始样本获得第一层的字典和稀疏特征，接着基于第一层的稀疏特征获取下一层的字典和稀疏特征，依次学习最终得到最深层次的字典和稀疏特征，后将最终获取的特征输入分类器模型，获得分类结果。DDL 不仅学习到更深层结构的字典还得到了更多样化且具表征性的特征，这样的深层结构特征更益于分类任务；并且 DDL 适应于大样本的分类，比局限于小样本分类的 DL 更具优势。2017 年，Snigdha 等人又针对高光谱图像的分类提出判别鲁棒性深度字典学习模型（Discriminative Robust Deep Dictionary Learning，DRDDL[38]，该模型根据高光谱图像的特性，在 DDL 模型的基础上用1L 范数约束原始样本的重构误差项，并融合标签信息学习一个分类器参数，从而提升高光谱图像的分类性能。
1 Problem statement
1.1 Properties of the dictionary
2 Algorithms
2.1 Method of optimal directions (MOD)
2.2 K-SVD
2.3 Stochastic gradient descent
2.4 Lagrange dual method
2.5 LASSO
2.6 Parametric training methods
2.7 Online dictionary learning (LASSO approach)
3 Applications
4 References
https://en.wikipedia.org/wiki/Sparse_dictionary_learning https://github.com/permfl/dictlearn python to sparse https://gist.github.com/BlueNexus/599962d03a1b52a8d5f595dabd51dc34
6.3 压缩感知(compressed sensing)
https://en.wikipedia.org/wiki/Compressed_sensing
