Sparse编码和字典学习（1）基础知识和python简单实现

1.1 Motivation

字典学习的思想应该源来实际生活中的字典的概念。字典是前辈们学习总结的精华&＃xff0c;当我们需要学习新的知识的时候&＃xff0c;不必与先辈们一样去学习先辈们所有学习过的知识&＃xff0c;我们可以参考先辈们给我们总结的字典&＃xff0c;通过查阅这些字典&＃xff0c;我们可以大致学会到这些知识。

稀疏表示的一个通俗解释&＃xff1a;

设观察到的信号为$\mathbf{y}$, 字典为$\mathbf{A}$&＃xff0c;查找一个稀疏的$\mathbf{x}$&＃xff0c;满足$\mathbf{y}\&＃61;\mathbf{A}\mathbf{x}$

由于$\mathbf{x}$的稀疏性质&＃xff0c;因而&＃xff0c;等式可以改写为如下形式&＃xff1a;

即&＃xff1a;原始信号可被近似表示为稀疏矩阵$\mathbf{x}$中较少的几个量的叠加。
那么&＃xff0c;如何找到这个稀疏矩阵$\mathbf{x}$呢&＃xff1f;
这个问题可以表示为如下的数学形式&＃xff1a;






x


∗



&＃61;




a


r


g


min


⁡



x




∥




x


∥



0

  

s


u


b


j


e


c


t
  

t


o
  


A


x



&＃61;


y




\boldsymbol{x}^*&＃61;\underset{\boldsymbol{x}}{arg\min}\left\| \left. \boldsymbol{x} \right\| _0\,\,subject\,\,to\,\,\boldsymbol{Ax}&＃61;\boldsymbol{y} \right.


x∗&＃61;xargmin​∥x∥0​subjecttoAx&＃61;y
PS&＃xff1a;范数是一种强化的距离概念&＃xff0c;它在定义上比距离多了一条数乘的运算法则。

零范数即p取0。

当P&＃61;0时&＃xff0c;也就是L0范数&＃xff0c;L0范数并不是一个真正的范数&＃xff0c;它主要被用来度量向量中非零元素的个数。
下面&＃xff0c;继续回到正题&＃xff0c;但是&＃xff0c;直接求解这个问题(NP hard)较为困难&＃xff0c;
这个问题可被放松为以下条件形式&＃xff1a;






x


∗



&＃61;


a


r


g


min


⁡



∥




y


−



A


x



∥



2


2

  

s


u


b


j


e


c


t
  

t


o
  


∥




x


∥



0



⩽


ϵ





\boldsymbol{x}^*&＃61;arg\min \left\| \left. \boldsymbol{y}-\boldsymbol{Ax} \right\| _{2}^{2}\,\, subject\,\,to\,\,\left\| \left. \boldsymbol{x} \right\| _0\leqslant \epsilon \right. \right.


x∗&＃61;argmin∥∥∥​y−Ax∥22​subjectto∥x∥0​⩽ϵ
但上式只考虑了观测信号$\mathbf{A}x$和真实信号$\mathbf{y}$之间的平方和误差&＃xff0c;优化过程&＃xff0c;只是添加了一个硬性的L0范数的约束条件&＃xff0c;因而&＃xff0c;迭代过程缺乏对稀疏性的优化&＃xff0c;进而修改为如下形式&＃xff1a;






x


∗



&＃61;


a


r


g


min


⁡



1


2




∥




y


−



A


x



∥



2


2



&＃43;


λ



∥




x


∥



1






\boldsymbol{x}^*&＃61;arg\min \frac{1}{2}\left\| \left. \boldsymbol{y}-\boldsymbol{Ax} \right\| _{2}^{2}&＃43;\lambda \left\| \left. \boldsymbol{x} \right\| _1 \right. \right.


x∗&＃61;argmin21​∥∥∥​y−Ax∥22​&＃43;λ∥x∥1​
探索了下&＃xff0c;获取稀疏解的原理和过程&＃xff0c;实际上LASSO也并不是一种封闭形式的优化过程&＃xff08; a closed form for the lasso solution&＃xff09;&＃xff0c;为了获得稀疏解

1.2 字典学习的流程

因而&＃xff0c;基于上述的一个思想&＃xff0c;字典学习可以被简化为一个“构造工具字典”、“查阅字典”的两个过程。对于“构造工具字典”这一过程&＃xff0c;对字典有以下几点要求&＃xff1a;

• 字典内容尽可能全面&＃xff0c;总结出的字典不应该漏掉数据的关键信息。
• 字典应该尽可能简洁&＃xff0c;即快而准。
• 在占用较小资源前提下尽可能还原知识的特性。

1.3 字典学习的数学模型

更加完整的数学公式推导可以查阅博客【4】

2.1字典学习

实际上&＃xff0c;就是实现了对原始信号的稀疏重构&＃xff0c;类似于压缩感知&＃xff0c;这里指定变换算法为“lasso lars”&＃xff0c; 实际上&＃xff0c;还包含以下几种&＃xff1a;

• ‘lars’: uses the least angle regression method (lars_path);

• ‘lasso_lars’: uses Lars to compute the Lasso solution.

• ‘lasso_cd’: uses the coordinate descent method to compute the Lasso solution (Lasso). ‘lasso_lars’ will be faster if the estimated components are sparse.

• ‘omp’: uses orthogonal matching pursuit to estimate the sparse solution.

• ‘threshold’: squashes to zero all coefficients less than alpha from the projection dictionary * X’.

import numpy as np
from sklearn.datasets import make_sparse_coded_signal
from sklearn.decomposition import DictionaryLearning
X, dictionary, code &＃61; make_sparse_coded_signal(
n_samples&＃61;100, n_components&＃61;15, n_features&＃61;20, n_nonzero_coefs&＃61;10,
random_state&＃61;42, data_transposed&＃61;False
)
dict_learner &＃61; DictionaryLearning(
n_components&＃61;15, transform_algorithm&＃61;&＃39;lasso_lars&＃39;, transform_alpha&＃61;0.1,
random_state&＃61;42,
)
X_transformed &＃61; dict_learner.fit_transform(X)


2.1 稀疏性统计和误差计算

print("sparsity: {}".format(np.mean(X_transformed &＃61;&＃61; 0)))
X_hat &＃61; X_transformed &＃64; dict_learner.components_
print(np.mean(np.sum((X_hat - X) ** 2, axis&＃61;1) / np.sum(X ** 2, axis&＃61;1)))


结果

sparsity: 0.4633333333333333
error: 0.011433365697744878
Process finished with exit code 0

参考资料和文献

【1】 https://scikit-learn.org/stable/modules/generated/sklearn.decomposition.DictionaryLearning.html
【2】http://thoth.inrialpes.fr/people/mairal/spams/documentation.html
【3】https://stats.stackexchange.com/questions/289075/what-is-the-smallest-lambda-that-gives-a-0-component-in-lasso
【4】https://www.cnblogs.com/endlesscoding/p/10090866.html