博文
[CV论文读讲] JMLR11－Learning with Structured Sparsity
||
相关PPT下载详见 “视觉计算研究论坛”「SIGVC BBS」：http://www.sigvc.org/bbs/thread-51-1-1.html
ICML2009视频地址：http://videolectures.net/icml09_huang_lwss/
作者主页（中科院自动化所2003级毕业生）：http://ranger.uta.edu/~huang/
代码地址：http://ranger.uta.edu/~huang/R_StructuredSparsity.htm
代码需要在matlab里先mex GraphPruneMex.cpp才能运行
各位同学，大家好，今天我主要介绍一下“Learning with Structured Sparsity”这篇文章，作者是Huang Junzhou。
此文最开始发表在2009年的ICML会议上，这只是他们工作的一个缩略版本，
又因为理论证明很多复杂，读起来很费力。后来在2011年的JMLR期刊上，作者又给出了一个长达42页的详细版本。文章主要介绍了一种他们提出的结构稀疏
方法，结构稀疏是标准稀疏的一个延伸拓展，但是它与group sparsity是有不同的，它允许在特征集上的任意结构。文章主要贡献就是在分析group sparsity的基础上，提出了
一个strong group sparsity的理论框架，然后基于此框架提出了一个基于编码长度的结构稀疏模型，然后给出了一种叫做StructOMP的结构稀疏的解法。
概要：
动机
编码长度与结构稀疏模型
算法介绍——StructOMP
实验结果
今天主要内容在于分析文章的idea来源，编码长度与结构稀疏模型，解决此问题的一个算法—structOMP，以及实验结果分析。
首先简要介绍一下标准稀疏模型，x1--xp为n维列向量，他们组成了一个n*p的矩阵X，这也叫做design matrix或者data matrix，y为n维观测向量，
y与X通常认为是存在一个线性关系，beta为系数向量，kexi为噪声向量。稀疏方法认为这个系数向量beta通常是具有稀疏性的，即beta中由很少
的几个非零元素和大量的零元素组成。Beta的支撑集就是定义为beta中非零元素的下标的集合，这个集合的元素个数称为L0范数。Beta的
L1范数表示beta中所有元素的绝对值求和。
通常我们知道数据矩阵X与观测向量y，我们希望知道y与X的关系beta。定义一个残差损失函数为平方误差函数，L0模型即求解在系数非零
元素个数小于等于k个的条件下使得这个残差平方和最小的beta系数向量。这个问题通常被认为是NP难的组合优化问题，解决这个问题的方法通常是
暴力穷举的方法，即把beta的所有组合求一次残差，再去找那个目标系数向量。
然而在实际应用中，这是不可取的，因此一种方法就是通常对上述L0模型进行近似求解，即通过对限制条件进行松弛，将L0范数限制变为L1范数限制。也就是标准稀疏模型，例如
LASSO和BP。另一种方法就是贪婪的方法，例如OMP。
系数除了稀疏性以外，还具有某种结构属性（Line/Tree/Graph 结构等等）。
Group sparsity
Multi-Task Learning
Group Sparsity及其变种证明了它比standard sparsity要好。但缺乏理论证明为什么会如此，因此作者提出一个strong group sparsity的理论框架。
在实际的应用中，我们除了知道系数向量是稀疏的，可能还知道它存在某种结构属性，例如下面将会介绍的Line结构，树结构，图结构等等。
这些工作之前都有人进行过研究，主要的方法就是group sparsity的方法和multi-task learning的方法。
什么是group sparsity呢？一般是指non-overlapping group sparsity，即将系数变量分为几个groups，每个group之间是没有重叠的。这是最一般的情况。
Group sparsity的正则化项是L21范数，即一次惩罚一个group，这个group里面的所有系数都为0，而不被惩罚的那些groups的系数都不为零，因为
2范数不保证稀疏。这就是group sparsity的最一般形式。
除了group sparsity之外，multi-task learning的模型也是类似的表达。
在他的另一篇论文the benefit of group sparsity里面，他提出了一个strong group sparsity的理论框架，目的是为了说明，在什么条件下，group lasso
的结果比standard lasso的结果要好。主要使用group sparsity去度量一个稀疏信号的复杂度，不只是系数的稀疏性。理论证明较复杂，短时间内实在是
无法理解。
这是结构稀疏的几个例子。
第一个图是line structure sparsity。其中每个节点表示系数中的一个变量，黑色的点表示选择的变量，白色的点表示未选择的变量，可以看到
包含19个变量的这个系数被分为了6个预定义的groups，而且每个group之间是没有重叠的。这些group表示一个连通分量。因此，在文中的
条件下，g=2,|F|=7。
左下图表示一个hierarchical structure层次结构的例子——tree structure。
这个树结构中黑色的点表示被选择的变量，白色的点表示未被选择的变量。这个树结构里面的变量选择遵循一个条件，
那就是如果一个节点被选择，那么它的父节点必然被选择，而后继节点可以不被选择。上图中，有8个节点被选择了。
进行变量选择的时候，从根节点开始遍历，每次碰到一个节点，会有2个选择，要么选择左边节点，要么选择右边节点，
要么两个节点都选择，因此在每个节点处有3个选择，因此这个节点可以编码为log_2(3)。因此这种树结构的编码长度
就是选择的节点总数乘以log2(3)这么多。
另一种层次结构就是图像的小波表示，我想就是小波不断分解，形成的那种层次结构吧。
右下图表示一个graph structure,这个图结构是最常见的在图像处理中的连通域的一个模型，图像的每个像素表示图中的
一个节点，那些黑色的节点表示在一个连通域内，上图中有2个连通域。被选择的节点个数有|F|=11。
本文中提出的这种基于系数编码复杂度的结构稀疏的idea主要来源于信息论里面的MDL原理。也就是最小描述长度原理。
最小描述长度原则是将奥卡姆剃刀形式化后的一种结果。
奥克姆剃刀原则是机器学习很基本的一个原则：又称简单性原理，是科学界常用的一个准则，具体表述为，如果多个理论同时都能解释某一现象，那么我们优先取利用假设最少的理论，这个理论被认为是最好的。
最小描述长度( MD ) 原理是 Rissane 在研究通用编码时提出的。其基本原理是对于一组给定的实例数据 D ， 如果要对其进行保存 ，为了节省存储空间， 一 般采用某种模型对其进行编码压缩，然后再保存压缩后的数据。同时， 为了以后正确恢复这些实例数据， 将所用的模型也保存起来。所以需要保存的数据长度( 比特数)
等于这些实例数据进行编码压缩后的长度加上保存模型所需的数据长度， 将该数据长度称为总描述长度。最小描述长度( MD L ) 原理就是要求选择总描述长度最小的模型。
文中的那个基于系数编码长度正则化的方法与MDL类似，那么首先来解释一下几个关于编码的概念。
第一个概念就是前缀编码。什么是前缀编码呢？学过计算机的应该很好理解。
给定一个序列的集合，若不存在一个序列是另一个序列的前缀，则该序列集合称为前缀码。
比如，编码为010,011中，01就是这两个编码的前缀，因此他们是前缀编码。
如下图中所示的，最后一列，这里面的编码任何一个都不是另一个的前缀，他就是前缀码，也称为instantaneous编码。
Kraft不等式，公式如图所示，其中cl(F)表示要编码集合F的长度。|F|表示集合中的元素个数，这个公式表示什么意思呢？
如果要使用前缀编码来编码集合I的子集F，那么需要满足上述不等式条件。这个不等式条件用概率理解的话，有点类似
累积分布函数。
文章里面引用这个理论，是为了说明他们提出的block coding scheme是满足这个不等式的，因此这种前缀编码策略
用在论文里面有了理论基础。
I表示系数的下标集合。
F表示下标的子集，对于这样的F，可以分配给它一个成为cost的代价，这个代价就是编码集合F的编码长度的上界。
这样就把系数向量与编码理论结合起来了，然后又证明了这样的编码方式是满足Kraft不等式的。
很明显，右边两个式子是成立的。
与 MDL类似，定义了一个正则化项为集合F中的非零元素个数加上编码集合F的代价。这样的正则化项与MDL是不同的。
为什么要加上|F|这一项呢？文中给出的理由就是：从贝叶斯统计观点来看，Kraft不等式中的2^-cl(F)表示集合F出现的概率，
因此F满足一个生成式模型。首先根据集合I和概率2^-cl(F)得到不同的F，然后生成F的系数。因此基于这个考虑，
需要把|F|中的非零元素的个数也加上去。
|F|表示学习系数向量的学习复杂度。
Cl(F)表示模型选择的复杂度。
以上，因此需要把两者加起来。
有了上面的基础知识，那么作者定义了一个结构稀疏编码复杂度，就是选择的系数支持属于F的一个子集，
然后最小化这个子集的结构编码复杂度，也就是该系数的结构稀疏编码复杂度。
把这个编码复杂度正则化添加到一般的LASSO的模型中，也就是作者提出的结构稀疏方法。
S是一个可调节的因子，类似下面的lambda.
解决上述问题通常有2种方法，一种就是凸优化松弛的方法，把L0松弛为L1问题。
第二种方法就是贪婪算法，作者就是使用类似OMP提出了一个StructOMP的结构贪婪算法，为了
解决本文提出的问题。
在介绍作者提出的方法之前，首先介绍一种前向逐步回归的贪婪算法。
输入A就是系数theta的支撑集，X为数据矩阵，Y为观测矩阵，sigma为终止条件。
首先在给定的系数支撑集上进行OLS模型拟合，得到一个模型，然后将剩余的变量与模型残差求相关，
得到那个相关性最小的变量，如果这个相关性小于一定的阈值，表示这个变量不需要添加到集合中了。
反之，把这个新的变量添加到集合中，再去拟合一个模型，以此来达到变量选择的目的。
作者提出的StructOMP与上面的类似，
J为下标集合
B为下标结合的子集的集合，文中定义是每一个下标组成一个子集
那么根据文中编码复杂度的定义，是一定存在一个编码代价函数使得Kraft不等式得到满足的。
对于任意的下标子集A，可以得到一个编码复杂度，总的编码复杂度就是子集A的编码复杂度加上A中的非零元素个数。
这个总的编码复杂度就是模型中的正则化项。
给定下标子集A,数据矩阵X，观测向量Y，下标子集B，fx(A)表示选择了当前变量之后的预测函数，
也就是在当前模型下的数据拟合误差，也称为经验误差
然后拟合当前模型
通过一个策略选择需要加入到集合中的block集合，这是一个什么策略呢？就是每增加一个单位的编码复杂度时，
损失函数下降最快的那个块。每次迭代这样的块，选取让这个函数最大的那个块，如果得到的结构稀疏条件满足时，
就终止，反之，把那个块加入到下标集合中，重复。
值得指出的就是，对于平方误差损失函数，可以定义上面那个准则函数为fai(B)，分子表示在这个集合下的目标函数的的平方差，
分母表示编码长度的增加。
Pf是OLS解决方案。
在实际的应用中，常常使用最下面那个公式去选取blocks中的第k个block。如果那个block满足条件，就把他添加到集合中。
这是有理论支持的，但是我没看懂。
作者做的实验，主要考虑的是图结构稀疏。
这个实验比较了3中方法：Lasso,OMP,group Lasso
这名了结构稀疏对比标准稀疏的优势。
数据矩阵是通过人为生成的，加入了独立同分布的标准高斯噪声。
量化评估准则为重构误差，他表示算法估计出来的系数向量与真实值之间的相对误差。
首先是一个一维强稀疏信号的实验。
信号长度为512，稀疏度为64，可以看到，信号的结构先验为4，即可分为4个groups，实验中
采样个数为160。这是使用OMP,LASSO，Group LASSO以及文中提出的StructOMP的结果。
在这个例子中呢，同一个group的相邻两个成分可以组成一个graph structure。
投影矩阵X为独立同分布的高斯分布矩阵。
在输出上加入了sigma=0.01的噪声。
因为不知道信号中到底有多少个groups，因此在group lasso中假设了4种情况，分别假设groups的个数为2,4,8,16。
可以看到，group lasso的结果比起omp和lasso是要好很多的，但是跟structomp想比还是差得很远。
为了研究采样个数与重构误差、算法执行时间之间的关系，分别测试不同的采样个数，看重构误差是多少。
这是在1维弱稀疏信号上的实验。512维的信号中有95%的系数为0。
可以将这个信号分为2个groups，即两个连通区域。再分别进行实验。
对弱稀疏信号的稳定性也是很好的！鲁棒性比较强。
为了研究噪声对重构算法的影响，作者进行了如下实验：
改变噪声的sigma值。
固定n=3k=192,然后每个噪声级别做100次重复，取均值画图如此。
可见，structOMP的噪声鲁棒性很强，重构误差是最小的。
噪声鲁棒性在弱稀疏信号上表现更明显。
https://blog.sciencenet.cn/blog-4099-637990.html
上一篇：[CV论文读讲] TIP06－Image denoising via sparse and redunda
下一篇：[CV论文读讲] [2012.9.12]Multi-feature Multi-task LMNN
