稀疏表示

稀疏表示是指将原始信号表达为字典元素的一个线性组合，如中，我们用x表示原始信号(列向量)，D为我们得到的字典(dictionary)，a即为在字典D上原始信号x的表达。

稀疏表示的意义在于降维。

将数据集D表示为矩阵，每一行对应一个样本，每列对应于一种特征。特征选择所考虑的问题是特征具有稀疏性：即矩阵中的许多列与当前学习无关。通过特征选择去掉这些列，则学习器训练过程仅需在较小的矩阵上进行，学习难度会有所降低，计算和存储开销减小，模型的可解释性也会提高。此外，模型的输入因素减少了，模型建立的输入输出关系会更清晰。

现在看另一种“稀疏性”：D对应的矩阵存在很多零元素，杂乱分布，而非整行整列的形式。比如文档分类中，每行是一个文档样本，每列代表一个字，字在文档中出现的频率作为特征取值。《康熙字典》有47035个汉字，则矩阵有4万多列。而文档中很多字不会出现，导致每一行有大量的零元素。

当样本具有稀疏表示时，它有以下优势：

  • 数据具有稀疏性能使得大多数问题变得线性可分；
  • 稀疏样本有高效的存储方法，不会造成存储的巨大负担。

这便是稀疏表示与字典学习的基本出发点。

字典学习

稀疏矩阵即矩阵的每一行/列中都包含了大量的零元素，且这些零元素没有出现在同一行/列，对于一个给定的稠密矩阵，若我们能通过某种方法找到其合适的稀疏表示，则可以使得学习任务更加简单高效，我们称之为稀疏编码（sparse coding）或字典学习（dictionary learning）。

给定一个数据集，字典学习/稀疏编码指的便是通过一个字典将原数据转化为稀疏表示，因此最终的目标就是求得字典矩阵B及稀疏表示α，使用变量交替优化的策略能较好地求得解。

给定数据集有m个元素，字典学习最简单的形式为：

​

其中为字典矩阵，k称为字典的词汇量，通常有用户指定，则是样本的稀疏表示。显然，式子中的第一项是希望由能很好地重构，第二项则是希望尽量稀疏。

求解上述优化问题，最终求得字典和样本的稀疏表示。用户可设置k的大小来控制字典规模，从而影响稀疏程度。

压缩感知

压缩感知是指直接感知压缩后的信息，其目的是从尽量少的数据中提取尽量多的信息。

在实际问题中，为了方便传输和存储，我们一般将数字信息进行压缩，这样就有可能损失部分信息，如何根据已有的信息来重构出全部信号，这便是压缩感知的来源。与特征选择、稀疏表示不同的是：它关注的是如何利用信号本身具有的稀疏性，通过欠采样信息来恢复全部信息。压缩感知的前提是已知的信息具有稀疏表示。

下面是关于压缩感知的一些背景：

  • 压缩感知最初提出时，是针对稀疏信号x，给出观测模型时，要有怎么样的，通过什么样的方式可以从y中恢复出x（稀疏信号是指这个信号x中非零元素的个数远小于其零元素的个数）。
  • 然而很多信号本身并非是稀疏的，比如图像信号，此时可以通过正交变换，将信号投影到另外一个空间，而在这个空间中，信号变得稀疏了，然后可以由模型，即，来恢复原始信号x。
  • 后来，人们发现不仅能够通过正交变换得到稀疏信号，还可以通过一个字典D，得到稀疏信号， 是稀疏表示，为了增强变换后信号的稀疏性，通常D是过完备的。模型表示为, 记为感知矩阵。这个模型就是现在最常用的模型。

Python实现

from scipy.sparse import csr_matrix
row = np.array([0, 0, 1, 2, 2, 2])
col = np.array([0, 2, 2, 0, 1, 2])
data = np.array([1, 2, 3, 4, 5, 6])
sparse_matrix = csr_matrix((data, (row, col)), shape=(3, 3)) # 稀疏矩阵
dense_matrix = sparse_matrix.toarray() # 稠密矩阵
print(dense_metrix)
>>>array([[1, 0, 2],
         [0, 0, 3],
         [4, 5, 6]])

使用csr_matrix函数，输入非零元素的值及其对应的横纵坐标，可以得到对应的稀疏表示。

参考资料

  1. 特征哈希(Feature Hashing)
  2. Trevor Hastie et al. The Elements of Statistical Learning, 2001.
  3. Kilian Weinberger et al. Feature Hashing for Large Scale Multitask Learning, 2010.
  4. Joshua Attenberg et al. Collaborative Email-Spam Filtering with the Hashing-Trick, 2009.
  5. https://www.zhihu.com/question/264165760/answer/277634591
  6. sklearn.feature_extraction.FeatureHasher
  7. sklearn学习笔记2 Feature_extraction库
  8. 特征选择和稀疏学习
  9. 《西瓜书》笔记11：特征选择与稀疏表示（三）
  10. 特征选择与稀疏学习
  11. https://www.zhihu.com/question/24124122/answer/50403932
  12. https://blog.csdn.net/u014595019/article/details/52433754
  13. PCA算法详解
  14. 主成分分析（PCA）原理详解
  15. 主成分分析PCA算法：为什么去均值以后的高维矩阵乘以其协方差矩阵的特征向量矩阵就是“投影”？
  16. 用Python的sklearn库进行PCA(主成分分析)
  17. 用scikit-learn学习主成分分析(PCA)
  18. 独立成分分析（Independent Component Analysis）
  19. 独立成分分析 ( ICA ) 与主成分分析 ( PCA ) 的区别在哪里？
  20. 独立成分分析ICA系列4:ICA的最优估计方法综述
  21. ICA-独立成分分析
  22. 独立成分分析Independent component analysis(ICA)
  23. 线性判别分析LDA原理总结
  24. 一文读懂特征工程
  25. 线性判别分析LDA详解
  26. LinearDiscriminantAnalysis
  27. 用scikit-learn进行LDA降维
  28. https://blog.csdn.net/u010705209/article/details/53518772
  29. https://blog.csdn.net/u012162613/article/details/42214205
  30. https://blog.csdn.net/qianhen123/article/details/40077873
  31. https://github.com/ceys/jdml/wiki/ALS
  32. 美团点评技术团队之深入FFM原理与实践
  33. [深度学习笔记（一）稀疏自编码器] (https://blog.csdn.net/u010278305/article/details/46881443)
  34. Field-aware Factorization Machines for CTR Prediction ,Yuchin Juan et al.
  35. Factorization Machines, Steffen Rendle et al.[2010]
  36. http://deeplearning.stanford.edu/wiki/index.php/UFLDL_Tutorial
  37. 局部线性嵌入(LLE)原理总结
  38. Locally linear embedding(LLE)局部线性嵌入-降维
  39. LocallyLinearEmbedding
  40. 用scikit-learn研究局部线性嵌入(LLE)
  41. 聚类和降维的区别与联系
  42. 聚类算法
  43. 受限玻尔兹曼机（RBM）学习笔记
  44. 受限制玻尔兹曼机RBM原理简介
  45. 从SNE到t-SNE
  46. t-SNE完整笔记
  47. SNE降维与可视化
  48. 比PCA降维更高级 —— t-SNE聚类算法实现指南

results matching ""

    No results matching ""