目录
0 写在前面
机器学习强基计划聚焦深度和广度,加深对机器学习模型的理解与应用。“深”在详细推导算法模型背后的数学原理;“广”在分析多个机器学习模型:决策树、支持向量机、贝叶斯与马尔科夫决策、强化学习等。强基计划实现从理论到实践的全面覆盖,由本人亲自从底层编写、测试与文章配套的各个经典算法,不依赖于现有库,可以大大加深对算法的理解。
1 稀疏表示与稀疏编码
类比真实的《现代汉语字典》,其中约有3500个常用字,而一篇文档可能只使用了其中15%的字,若将每个文档看作一个样本,每个字作为一个特征,字在文档中出现的频率作为特征取值,那么一篇文档的特征向量约有85%的零元素。但不同主题的文档使用的主要词汇可能相差很大(比如古风诗词和科幻小说),导致稀疏分布不同
因此稀疏表示不会掩盖真实特征,相反,甚至可能使困难的学习问题变得线性可分,而且得益于计算机科学对稀疏矩阵的研究,稀疏化使机器学习在计算和存储方面更高效
那这里稠密和稀疏的概念与维数灾难有什么关系呢?
机器学习任务中通常面临高维特征空间,若特征维数为40,则要实现密采样就需要
所以本节研究的对象是特征的稠密与稀疏,而维数灾难里讨论的是特征空间中样本的稠密与稀疏
稀疏编码(sparse coding)研究给定字典时如何用尽量稀疏的表示还原样本,形式化为
必须指出,
同解,此时可采用PGD等凸优化技术求解。然而因为不能保证
2 匹配追踪MP算法
匹配追踪(Matching Pursuit, MP)的核心思想是挑选少数几个影响力最大的字典原子重构原始样本,其余字典原子置零,在稀疏化的同时保证主要信息不丢失。MP采用样本在字典原子方向的投影绝对值衡量影响力,其原理类似余弦相似度
其中
的字典原子并用相应影响力更新编码向量,更新后的稀疏表示应比前几轮迭代更逼近原始样本,所以当重构误差小于阈值时即得最优的稀疏表示。如图所示为算法示意图,直观地,残差不断减小。
3 正交匹配追踪OMP算法
MP算法的缺陷在于残差只与本轮迭代选择的字典原子正交,即同一字典原子可能在迭代中被重复选择,例如上图第二轮迭代后的残差
与MP算法最大的区别在于最小二乘编码的计算,使得
即残差与字典原子正交,保证了更新的效率。采用最小二乘法而非施密特正交化的原因是对整个字典正交化的计算复杂度太高,且造成计算浪费(未被选择的原子也被正交化)
完整代码通过下方名片联系博主获取
🔥 更多精彩专栏:
文章出处登录后可见!