稀疏贝叶斯学习(Spar Bayesian Learning)
张智林（Zhilin Zhang ）
z4zhang@ucsd.edu
Department of Electrical and Computer Engineering, University of California, San Diego,
La Jolla, CA 92093-0407, USA
1 引言
稀疏贝叶斯学习（Spar Bayesian Learning, SBL ）最初作为一种机器学习算法由Tipping 于2001年前后提出[Tipping2001]，随后被引入到稀疏信号恢复/压缩感知领域[Wipf2004,Ji2008]。Wipf 和Rao 等人对SBL 进行了深入的理论研究。与广泛使用的基于L1惩罚项的算法（比如Lasso ，Basis Pursuit ）相比（以下简称L1算法），SBL 具有一系列显著的优势：（１）在无噪情况下，除非满足一些严格的条件
[Donoho2003]，L1算法的全局最小点（global minimum ）并不是真正的最稀疏的解［Wipf2004]。因此，在一些应用中，当真实的解是最稀疏的解，采用SBL 是更好的选择。（２）当感知矩阵（nsing matrix ）的列与列相关性很强时，L1算法的性能会变得非常差。事实上不光是L1算法，绝大多数已知的
压缩感知算法（比如Approximate Message Passing 算法，Matching Pursuit 算法）在这种情况下性能都会变得很差。相比之下，SBL 算法仍旧具有良好的性能［Wipf_NIPS2011]。因此，在雷达追踪，波达方向估计，脑源定位，特征提取，功率谱估计等一些列领域，SBL 都具备显著的优势。（３）业已证明，SBL 算法等价于一种迭代加权L1最小化算法（iterative reweighted L1 minimization ），而L1算法仅仅只是其第一步[Wipf2010]。Candes 等人指出，迭代加权L1最小化算法更易获得真正的最稀疏解[Candes2008]。从这个角度也就不难理解SBL 的优越性。（４）在很多实际问题中，所期望的稀疏解常常有一些结构，而利用这些结构可以获得更好的性能[ModelCS ]。作为一种贝叶斯算法，SBL 算法对利用这些解的结构信息提供了更多的灵活性。这种灵活性最主要来自于SBL 采用参数化的高斯分布为解的先验分布。最近Zhang 和Rao 提出了块稀疏贝叶斯学习框架(Block Spar Bayesian Learning, BSBL)[Zhang_IEEE2011, Zhang_TSP2012]。该框架提供了一种利用解的空间结构（spatial structure ）和时序结构（temporal structure ）的解决方案。由其框架得到的算法在多任务学习（multi-task learning ）[Wan2012]，生理信号的无线传输和远程监控[Zhang_TBME2012a, Zhang_TBME2012b ]，脑源定位和脑－机接口[Zhang_PIEEE2012]等许多领域获得了极大的成功。
下面将首先介绍基本的SBL 框架，然后对BSBL 框架及其算法进行详细介绍，并在最后给出一些代表性的实验结果。
2稀疏贝叶斯学习
压缩感知的基本模型可描述为:
v Ax y += （1） 其中为N×M的感知矩阵，为N×1维压缩信号，为M维待求的解向量，为未知的噪声向量。为求解，SBL 假设中的每个元素都服从一个参数化的均值为０方差为A y x v x x i γ的高斯分布[Wipf2004]：鸡豆花
M i N x p i i i ,,1),,0();("==γγ （2）
其中表示中的第i 个元素，i x x i γ是未知的参数，将会由算法自动估计出来。这样一种先验分布常被称为automatic relevance 先验分布，最初出现于人工神经网络领域[ARD1996]。在算法运行中，绝大部分的i γ将会变成０（无噪情况下）或者趋于０（有噪情况下）。SBL 通常会采用一个阈值将趋近于０的i γ置为０（该阈值的大小通常和信噪比有关）。当0=i γ时，相应的则为０。因此，i x i γ与解的稀疏程度密切相关，也从而决定了i γ的学习规则是SBL 算法中最核心的部分。在SBL 框架中，噪声通常假设为高斯白噪声向量，即v ),,0();(I v λλN p =其中λ为噪声方差。根据以上的假设，利用贝叶斯规则很容易获得后验分布，其也为一高斯分布。当所有的未知参数(即{}λγ,1M
i i =)都被估计出来后，x 的最大后验估计(Maximum A Posterior)由这个高斯分布的均值给出。而这些未知参数可以由第二类最大似然估计(Type II Maximum Likelihood)获得[Tipping2001, MacKay1992]。
在以上的SBL 框架中，我们把i γ作为一未知的确定性参数，而没有把它视为一随机变量从而进一步假设它的先验分布。事实上，这等同于假设i γ的先验分布是一个non-informative prior 。Wipf 和Rao 已从理论上证明，这种SBL 框架可以获得真正的解（即最稀疏的解）[Wipf2004]，而若对i γ赋予一个非non-informative prior ，有可能导致算法的不稳定或者解的不正确[Wipf_PhDThesis ]。另外也需注意到，Tipping 提出的SBL 算法[Tipping2001]是假定的precision （即方差的倒数）具有一参数化的Gamma prior ，而这些参数最终被固定为某些特殊的值使得具有一improper prior ，即i x i x i i x x p 1)(∝。这种prior 类似于Laplace prior ，起着促进稀疏解的作用。通过比较Wipf 和Rao 的SBL 算法和Tipping 的算法，我们不难发现，前者的SBL 算法恰好是后者的SBL 算法取该improper prior 的形式。从这个角度也不难理解为什么前者的SBL 算法可以获得稀疏解。
除了Tipping,Wipf 等人的SBL 算法外，还有其它一些SBL 算法赋予的precision 其它的分布，或者假设的先验分布为一Laplace prior[BCSlaplace ]。这些算法多数情况下无法证明其全局解是真正稀疏解（即最稀疏解），或者本身稳定性存在问题，不能保证良好的收敛性能。值得注意的是，赋予不同的先验分布并不能导致相应的SBL 算法在实际应用中具有明显的优势。这是因为大多数实际问题都和理想的感知压缩模型相去甚远，比如感知矩阵(nsing matrix)的列与列之间具有强相关性，噪声很强，并不是非常稀疏等等。在这些情况下，不少参数的估计将会有较大的误差，从而导致最终的解具有较大的误差。最明显的是，绝大多数SBL 算法对噪声方差i x i x i x x λ的估计都不有效，尤其是当感知矩
阵的列与列之间具有强相关性且噪声很大的时候。而对该方差估计的准确性对x 的估计的准确性影响非常大。Zhang 和Rao 最近给出了噪声方差的另外一个学习规则［Zhang_IEEE2011］。试验表明该学习规则可以获得更加鲁棒的效果。
事实上要想在实际中获得更好的结果，充分利用解的自身结构信息是更加有效的策略。接下来我们将介绍利用解的空间结构信息和时序结构信息的SBL 算法。特别的，我们将介绍如何利用解的各个元素
之间的相关性来提升算法的性能。安全通知
胡萝卜是什么颜色３利用解的结构信息的稀疏贝叶斯学习
３.１ 解的空间信息和块稀疏贝叶斯学习
解的空间信息是指在模型（１）中解向量具有某些结构。最常见的结构是块结构（block structure ），或称为组群结构（group structure ）［groupLasso, ModelCS, Eldar2010BSS ］，即
x （3）
T d d d T g g g T x x x x ],,,,,,[11111 ""
"x x x +−=基于这个块划分的基本压缩感知模型（即公式(1)(3)）称为块稀疏模型（Block Spar Model ）。在这个模
型中，解向量x 可以划分为g 个块结构（每个块结构包含的元素有多有少）
，而x 的非零的元素则聚集在少数几个块内。基于这个模型，目前已经有了不少算法，比如Group Lasso [groupLasso ], Block-OMP
[Eldar2010BSS ], Block-CoSaMP [ModelCS ]等等。遗憾的是，很少有算法考虑每个块内的元素之间的相关性（幅值的相关性）。为方便，以下我们称该相关性为块内相关性(Intra-Block Correlation)。
好听的吉他曲块内相关性之所以还没有引起重视，是因为在大多数情况下目前已有的算法并没有显示出其性能受到该相关性的影响。块内相关性对算法性能的影响直到最近才被Zhang和Rao通过提出块稀疏贝叶斯学习（Block Spar Bayesian Learning, BSBL）而发现[Zhang_TSP2012]，并被成功的运用到非稀疏生理信号的无线传输［Zhang_TBME2012a, Zhang_TBME2012b ］。
在BSBL中，每一个块被假设为满足一多元高斯分布：
i x ),()(i i i N p B 0x γ= （3） 其中为一未知的正定矩阵，用于对该块内的元素之间的相关结构进行建模，而i B i γ为一未知的参数，用于决定该块是否为。类似于基本的生猴子是什么意思
SBL 框架，当00=i γ，相应的块0x =i 。这样的prior 可以认为是一种结构化的Automatic Relevance Prior 。由于automatic relevance determination(ARD)机制，在算法学习过程中大多数i γ最终为０或者趋近于０，从而促成了解的块稀疏性(Block Sparsity)。同样，假设噪声服从),();(I 0v λλN p =。这样我们可以利用贝叶斯规则得到x 的后验分布。利用第二类最大似然估计可以估计出各种参数，从而最终得到x 的最大后验估计值。
Zhang 和Rao 证明［Zhang_IEEE2011］，在无噪情况下BSBL 的全局解即是真正的最稀疏解；而无论的值是多少都不影响这一结论。事实上，的值仅仅只影响算法的局部解的性质，即算法收敛到局部解的概率。这一结论带来了极大的好处，那就是我们可以灵活采用一些策略来规范化（regularize ）的估计从而克服overfitting ，而无须担忧是否会影响到算法的全局解的性质。在［Zhang_IEEE2011, Zhang_TSP2012, Zhang_ICASSP2012］中多种规范化策略被提出来。比如当每个块包含有同样数目的元素时，我们可以平均所有的得到一矩阵B ，把它作为每个的最终估计值［Zhang_TSP2012］。我们还可以进一步对B 做规范化，使i B i B i B i B i B I B B η+←，其中η为一正的常数［Zhang_IEEE2011］。试验表明，
存在若干中规范化策略，均可获得类似的性能。
从算法层次上来说，BSBL 揭示了在标准的压缩感知试验条件下一个有意思的现象［Zhang_TSP2012,
RaoZhangJin2012］：当算法忽略块内相关性时（即所有的矩阵都被强制为单位矩阵），无论块内相关性是大是小，算法的性能并不发生显著的变化；当算法利用块内相关性时（即运行矩阵的学习规则），算法的性能随块内相关性的增大而提高。考虑到目前绝大多数算法都没有利用块间相关性，我们不难得到一个启示：通过改进已有的算法（比如Group Lasso ）使其可以利用块间相关性，我们可以进一步提升该算法的性能。
i B i B 事实上，在［Zhang_TSP2012］中，Zhang 和Rao 揭示了BSBL 与Group Lasso 等许多算法的联系。Zhang 和Rao 证明，BSBL 的代价函数（cost function ）等价于下面一迭代加权算法：
∑=−++−=g
i i i T i k i k w 11)(22)1(min arg x B x Ax
y x x λ （４）
其中k 为迭代次数，为一加权因子，其值取决于上一次迭代的结果。显然，当所有的为单位矩阵，且所有的加权均相同且恒为一常数时，该算法即为Group Lasso 的最常见形式。这一联系提供了如何改进已有的基于i w i B i w ∑=g i q p i 1x 惩罚项的算法。感兴趣的读者可以参考［Zhang_ICML2011］了解如何改进类
似Group Lasso 的算法（即1,2==q p ）
，或者参考［Zhang_ICASSP2011］了解如何改进迭代加权L2最小化算法（）。另外一方面，（４）也提供了如何提高BSBL 算法的速度的一种方案。试验表明，在大多数情况下只需要迭代３－５次便可收敛，而每一次迭代也即运行一次Group Lasso 。考虑到目前Group Lasso 的运算速度不断提升，采用这种迭代方式的BSBL 算法的速度也将同步提升。 2,2==q p 注意到在公式（３）中块的划分是已知的。在一些情况下这种划分是无法获知的。对于这种情况，文献[Zhang_ICASSP2012, Zhang_TSP2012]提出了一种扩展BSBL 框架。根据这种框架，未知块划分的情况被转化为一种简单的BSBL 模型，而在这种BSBL 模型中每个块的长度成为一种规范化参数(regularization parameter)。试验表明这种扩展BSBL 框架在噪声情况下尤为有效。
值得一提的是，即使块结构未知，BSBL 框架在有些情况下也仍然适用。在［Zhang_TBME2012a , Zhang_TBME2012b ］中，BSBL 被用于恢复非稀疏的但是具有相关结构的生理信号，成功的解决了压缩传感应用在生理信号的低能耗无线传输的瓶颈问题。在试验部分我们将给出一个代表性的例子。
３.２ 解的时序信息描写人物神态的四字词语
在一些应用中（比如波达方向估计，源定位，雷达探测），在相继的时刻（假设为时刻，，……，1t 2t L t ）我们可以建立一系列基本的压缩传感模型：)()()(111t t t v Ax y +=， ，……，)()()(222t t t v Ax
y +=)()()(L L L t t t v Ax y +=。在这些模型里，感知矩阵均一样，每个解向量（）的非零元素的位置也一样（但幅值可能不一样）。我们可以把这L 个模型A )(n t x L n ,,1"=
李小凯
合并到一起，写成矩阵的形式：
V AX Y +=
其中)](,),([1L t t y y Y "=，)](,),([1L t t x x X "=。根据前面的假设，仅有少数几行是非零行，而绝大多数行都为零行。这样一种模型称为多观测向量模型（Multiple Measurement Vector Model, MMV ）［Cotter2005］。相比于仅使用一个观测向量的模型（即这L 个基本压缩传感模型中的任意一个），MMV 模型能够更加准确的估计出非零行的位置（或者说每个解向量的非零元素的位置），从而更准确的获得最终的解［RaoZhangJin2012,Cotter2005, Eldar2010, Tang2011］。
X )(n t x 目前已有不少针对该模型的MMV 算法，包括基于这种MMV 模型的SBL 算法［Wipf2007］。遗憾的是，绝大多数算法都忽略了中每一个非零行内的元素之间的相关性。试验显示［Zhang_IEEE2011］，如果算法中不考虑这些行内的相关性，算法的性能将会极大的降低。为利用这些行内的相关性，Zhang 和Rao 注意到块稀疏模型与MMV 模型的联系，把BSBL 框架用于MMV 模型，而行内的相关结构则由BSBL 框架中的矩阵来建模，从而得到了利用时序结构的SBL 算法［Zhang_IEEE2011］。这种利用时序结构的SBL 算法相比于其它MMV 算法具有明显的优势。
X i B 需要指出的是，利用时序结构信息的MMV 算法不但可以用于信号处理领域，还可以用于机器学习领域，作为一种多任务学习（multi-task learning ）算法用于特征提取。在 [Wan2012]中，利用时序结构的SBL 算法与常见的多任务学习算法的联系被揭示出来；前者可以视为一种具有自适应核（adaptive kernels ）的多任务学习算法，可以自动捕捉数据的内在结构，因而较传统的多任务学习算法以及依靠人工设定核的多任务学习算法更加优越。
３.3解的空-时结构信息和时变信息
BSBL 框架提供了一种思路来灵活的合并解的空间结构信息和时序结构信息。此外，利用BSBL 框架还可以有效利用解的时变结构信息。限于篇幅我们不在这里做介绍。对这两个部分感兴趣的读者可以参考综述 [RaoZhangJin2012]。
4试验仿真
4.1 非稀疏的生理信号的压缩传感及其在医学远程监控中的应用
经由无线体域网（Wireless Body-Area Network, WBAN ）的生理信号的远程监控是目前医疗通讯领域的一个主要发展方向。最近开始有学者提出把压缩传感技术用于这一领域[Mamaghanian2011,
Dixon_BME2012, Eduardo2010]。压缩传感技术用于这一领域有很明显的优势：（1）当采用元素仅
为0或者1 的稀疏矩阵（binary spar matrix ）为传感矩阵时，压缩传感可以比传统的小波压缩技术更加减少无线体域网的能量的损耗[Mamaghanian2011]。而减少能量损耗是无线体域网研究的一个核心问题
[Milenkovic2006, Calhoun2012]。（2）从压缩质量上来看，压缩传感和小波压缩有类似的压缩率和恢复质量。
但是压缩传感技术在这一领域取得的成果仅仅局限在及少数几种特别稀疏的生理信号（比如非常干净无噪的成人心电图信号），或者局限在少数几种特殊用途上。压缩传感技术还不能用于更多的生理信号（比如胎儿心电图信号，脑电图信号），以及还不能用于更为广泛的用途。这主要是因为：
（１）绝大多数的生理信号是非稀疏的信号，即使被投影到变换域上（比如小波域）仍旧不足够稀疏［Zhang_TBME2012a ］。尽管这些生理信号可以认为是一种可压缩（compressive ）的信号（即：虽然信号的所有元素都非零，但是只有少数一些元素显著非零，而绝大部分元素接近为零），但是压缩传感算法只能保证恢复信号中的显著的非零元素，而接近为零的元素无法准确恢复。但是对于医学远程监控
宽容的名言
