高效稀疏编码算法

1、高效稀疏编码算法1 Introduction稀疏编码提供了发现对于外来刺激简明表示的一系列算法；给予未标记的输入数据，它学习可以抓住数据高水平特征的基函数。当一个稀疏编码算法英语到自然图像时，学习的基函数就类似于视觉皮层中的神经元感受野；此外，当应用到其他自然刺激例如语音和视频时，稀疏编码产生局部基函数。不同于其他无监督学习技术例如主成分分析，稀疏编码可以应用到学习超完备基函数，其中基函数的维度大于输入数据维度。稀疏编码同样可以通过稀疏化它们的刺激来生成基函数之间抑制模型。同样的性质可以在生物神经元中观察到，这样使得稀疏编码得到视觉皮层的合理模型。尽管关于稀疏编码模型有良好的前景，我们认为它们

2、的发展很大程度上被昂贵的计算代价所阻碍。特别是学习大维度，超完备代表时就会极度耗费计算资源。在这篇文章中，我们提出了一类基于变量两组子集的交替优化的高效稀疏编码。这类优化问题是凸问题；特别地，对于第一个子集的优化是一范数最小二乘问题；第二个子集则是二范数最小二乘问题。我们描述了每个算法并经验地分析了它们的表现。我们的方法允许我们高效地学习来及自然图像的高维度超完备基函数。我们证明了结果学习基展示了终止情况和对于传统感受野之外刺激的调整。此外，稀疏编码同样提供了对于VI区神经元这些现象的局部解释。在最近的工作中，我们展示了学习高水平特征的简明表示可以应用到监督分类任务。2 Preliminari

3、es稀疏的目标就是将输入向量表示为少量的(未知的)“基函数”的加权线性组合。这些基函数可以抓住输入数据中的高水平特征。具体地说，每个输入的向量匚一N厂可以简单地由基函数-IHi和稀疏加权向量或系数匚二使得u来表示。这些基函数是超完备的(nk),这样可以抓取输入数据的大量值。稀疏编码是可以使用无标签数据自动获取良好的基向量。标准生成模型假设重构误差是一"，且是标准高斯分布协方差为'o为了支持稀疏系数，每个系数二的优先分布定义为汽肌；屮三汽其中，是稀疏函数，是一个常数。例如，我们可以使用如下函数：(|卜j|1(Ljpenallyfunction)命(耳=<(巧+打呕(eps

4、iloiiLjpenaltyfunction)(1)(logfl4-町)(logpenaltytiinction).在这篇文章中，除非提及我们将会使用一范数罚项；一范数正则化是可以产生稀疏系数并且对于不相关特征是稳健的。考虑训练集是m个输入向量和它们相应的（未知）系数。假设基函数先验是均一的，对于基函数和系数的后验估计的最大化就是下列优化问题的解：miiiim叫冇何“LX丄韵西-艺；=1&豺F+#刀笃工;=,（刼）（2）subjectto|Sy|2<c.Vj=1.,n.这个问题可以以更简明的矩阵形式表示：使上是输入矩阵（每列是一个输入向量），毗贮"是基函数矩阵（每列是基

5、函数向量），S即曲是系数矩阵（每列是系数向量）。最优化问题可以写成：iiiiiinnizcBRS丹|无-B弓昨+丘工tJ就纯j）subjecttoWg?§£qPj=11rn.假定一范数罚项或者epsilon一范数罚项是稀疏函数，最优化问题在B中是凸的（S是固定的）或在S中是凸的（B是固定的），但不是同时都是凸的。在这篇文章中我们迭代地求解上述目标函数，通过交替地优化B（基函数）和S（系数）同时固定另一项。对于学习基B,优化问题是有二次项约束的最小二乘问题，这里有一些方法来求解这一类问题，例如通用凸优化求解器（QCQP求解器）以及使用迭代投影的梯度下降法。然而，通用凸优化求解

6、器对于这类问题来说太慢了，梯度下降通常收敛太慢。在这篇文章总，我们推导出拉格朗日对偶，并说明这种方法比基于梯度的方法更加高效。对于学习系数S,最优化问题等效于正则化最小二乘问题。对很多可微的系数函数，我们可以采取基于梯度方法（如共轭梯度）。然而，对于一范数稀疏函数，目标函数并不是连续可微的且最直接的基于梯度方法难以应用其中。在这种情况下，下面的方法可以被采用：通用QP求解器（CVX）,chen等人提出的内部点方法，最小角回归的改进，或者移植法。在这篇文章中，我们提出一种新的算法来求解一范数正则化最小二乘问题并且说明这种方法对于学习稀疏编码基是更为高效的。3 L1-regularizedleas

7、tsquares:Thefeature-signsearchalgorithm考虑到求解（2）式的最优化问题是固定基同时对系数加上一范数罚项，这类问题可以分别优化每个系数来求解：minim%肿）-孚閉|卩+（卅历耳|创（4）注意到如果我们知道片在最优化值的标志（正，零或负），我们可以将I幻丨项替换（I）（E）_,（1）.（I）为为（如果为0）厂亏（如果为<0），或者0（如果为=0）。仅仅考虑非零系数，式（4）简化为标准无约束的二次最优化问题（QP）,这样就可以高效地解析求解。因此，少）我们的算法尝试去找到，或者说是“猜出”系数-的特征；无论是怎么猜测我们都能够高效地求解出无约束QP问题。

8、此外，如果初始值是错误的，算法会系统地改善搜索值。为了简化符号表示，我们将算法表示为下面等效的最优化问题：miniinize/）三加一Ax2711111：其中是一个常数，特征标志搜索算法仔算法1中所示。它保持了潜在非零系数的活跃子集和相应的标志其他的系数必须是零值，并且系统地搜索最优的活跃子集和系数标志。算法通过一系列“特征标志步骤”来进行：在每一步，它对活跃子集和其标志进行猜测，I!.并计算无约束QP问题的解析解'；接着通过在当前解和二D.之间的高效离散线性搜索，它会不断更新解，活跃子集和标志（详见算法1）。我们将会表现每一步会减小目标函数f（x）,最终算法总会收敛到最优解。算法1特

9、征标志搜索算法1初始化:二1：二；,：活跃子集3；=其中-.丄代表标志-2从零系数x中，选择?=arNiaXi如，激活Xj（将i加入活跃子集）仅当它局部提高目标函数，即：如果一，那么令":二一-，活跃子集：=1活跃子集。如果，那么令"匸，活跃子集：二：活跃子集。3特征标志步骤：令I是A的子矩阵，其仅仅包含相应活跃子集的列。令厂和分别是'和门相对于活跃子集的子向量。计算无约束QP问题的解析解（-I''）：=（AT>l）_1（XTy-7/2）从J到；的闭合线性部分进行离散线性搜索:检査目标函数在；和其他所有系数标志变化点的值。更新厂到有着最小目标函

10、数值的点。去掉'在活跃子集中的零值，并更新4检查最优化条件：（a）对于非零系数的最优化条件：-如果条件（a）不满足，转到步骤3（不做任何激活）；否则检查条件（b）(b)对于零系数的最优化条件:如果条件（b）不满足，转到步骤2；否则返回x为最终解。为了证明收敛，令系数向量x和所给的活跃子集和标志向量一致如果对所有的i满足下面两个条件：（i）如果i在活跃子集中，那么'-S（ii）如果i不在活跃子集中，那么一'。引理3.1考虑最优化问题（5）增加额外限制：x是同所给的活跃子集和标志向量相一致。那么，如果当前系数厂是同活跃子集和标志向量相一致，但是对于步骤3的增广问题并不是最优

11、的，特征标志步骤是保证严格减小目标函数。简略证明。令是相对于所给活跃子集中系数的子向量。仔步骤3中，考虑到平滑的二次项函数:卜厂L因为八不是的最优点，我们有现在考虑两种可能的情况：（i）如果'-和所给的活跃子集和标志向量一致，更新J-会严格地减小目标函数；（ii）如果不是和所给的活跃子集和标志向量一致，令为在忆心到也适线性部分的第一个零交叉点（其中任何系数改变其标志），那么很明显：亠；.，而且由于的凸性质-，因此我们可以得到'-/-'因此，在步骤3中描述的离散线性搜索保证了目标函数值的减少。引理3.2考虑最优化问题（5）增加额外限制：x是同所给的活跃子集和标志向量相一致

12、。如果系数儿在步骤2的初始对于增广问题是最优的，但对问题（5）不是最优的，特征标志步骤保证严格减小目标函数。简略证明。因为厂对于增广问题是最优的，它满足最优化条件（a），但是不满足条件（b）；因此，在步骤2中，存在一些i,使得"A；这些第丨个系数被激活，i被加入活跃子集中。在步骤3中，考虑平滑二次函数W一-人丨一"。观察到：(i)因为/在=工匕的泰勒展开仅在王匚有一阶项(对其他系数使用条件4(a),我们得到任何局部减小'*的方向必须和活跃的标志相一致，(ii)因为厂并不是的HA最优点，必须在*''附近沿着到的方向减小。从(门和(ii)得知，从到,:.

13、的线性搜索方向必须和活跃的标志相一致。最终，因为当；和活跃子集相一致时'一'1，或者1：'-相一致的，或者从,至I厂v的第一零交叉点有最小目标函数值(同引理3.1相似)。定理3.3特征标志搜索算法对于最优化问题(5)在有限的步数内收敛到全局最优点简单证明。从上述的引理中，它遵循着特征标志步骤总是严格地减小目标函数f(x)。在步骤2的开始，x要不满足最优化条件4(a)，要不是零向量；在哪种条件下，x都是同当前的活跃子集和标志向量相一致，并且对于上述引理描述的增广问题必须是最优的。因为所有可能的活跃子集和系数标志是有限的，而且没有重复的一对(因为目标函数值是严格减少的)，步

14、骤2-4(b)的外层循环是不能无期限地重复。这样是正确的是因为步骤3-4(a)总是导致要不退出到步骤4(b),要不减少活跃子集的大小。注意到从任意起始点开始计算需要一点小的改进：在初始化"和活跃子集，得到一个初始解，我们需要进行步骤3而不是步骤1。当初始解在最优解附近，特征标志搜索可以比初始值是更快地得到最优解。4LearningbasesusingtheLagrangedual在这一小节中，我们提出一种在固定系数S情况下求解基于基B的最优化问题(3)。该问题简化为下列问题：minimizeXBS|召(6)口山j巳毗to521归爲<c?Vj=1,这是有二次约束的最小二乘问题。通

15、常来说，这类约束最小化问题可以通过迭代投影梯度下降方法。然而，使用拉格朗日对偶会更加高效。首先，考虑拉格朗日算符：71kC(B.X)=trace(X-BSfX-BS)+工嘉(工叽i=l其中每个_',是对偶变量。对B解析地最小化，我们得到朗格朗日对偶:P（A）=trace（XTX-X5T（55T+-cA）,其中量-'的梯度和海塞矩阵分别有下式计算：其中W-是第i个单位向量。我们可以通过使用牛顿法或者共轭梯度法来优化拉格朗#日对偶（8）。在最大化巩入）后，我们得到最优基B如下所示：(11)匚丁=(SST-F求解对偶的优势是它相比较于原始的方法使用了更少的最优化变量。例如，最优化”w

16、-1：1：1""仅需要100个对偶变量。注意到对偶变化是独立于稀疏函数（例如L，epsilonL，或者其他稀疏函数），而且可以延伸到其他相似的模型例如“拓扑”单元。5Experimentalresults5.1Thefeature-signsearchalgorithm我们评估了我们的算法对于四种自然刺激数据集的表现：自然图像，语音，立体图像，和自然图像视频。所有的实验是在Linux机器,配置为AMDOpteron2GHZCPU和2GBRAM。首先，我们评估了特征标志搜索算法对于学习L1稀疏函数系数的表现。我们比较了和之前最先进算法的运行时间和准确性：通用QP求解器，一种有

17、着提前终止的LARS法的改进，移植法，和chen等人的内部点方法；所以的算法都是用MATLAB运行。对于每个数据集，我们使用100个输入向量测试，并测量运行时间和收敛时的目标函数。表1展现了不同系数学习算法的运行时间和准确性（计算最终目标函数的相对误差）。在所有数据集中，特征标志搜索有最好的目标函数值以及最短的运行时间。特征标志搜索和改进的LARS比其他算法的借要更准确。特征标志搜索比Chen等人算法和通用QP求解器用着更小量级的时间，而且比改进LARS和移植法更明显地快。此外，特征标志搜索有着重要的优势就是它可以以任意系数作为初始值（不同于LARS）；我们甚至可以证明当应用到迭代系数学习时，

18、特征标志搜索比LARS有着更高的加速。naturaimage196x512speech500x200stereo28Sx4OOvideo512x200Feature-sign2.16(0)0.5S(fl)1.72(0)0.S3(0)LARS362(0).2S(0)402(0)1.98(0)Grafling13.39(7c-4)4,69(4e-6)HJ2(5c-4)5,8S(2e-4)Chenetal/s8S.61(Sc-5)47.49(Sc-5)66.62(3c-4)47.00(2e-4)QPsolver(CVX)387.9Q(4e-9)IJ08.71(le-8)538.72(7e-9),21

19、9.80(le-8)表1运行时间秒为单位（相对误差在括号内）。对于每个数据集，输入维度k和基的数目n表示为kXno算法的相对误差定义为-',其中是算法得到的最终目标函数值，是所有算法计算得到的最好的目标函数值。5.2Totaltimeforlearningbases对于基学习，拉格朗日对偶函数比有着迭代投影的梯度下降更快，由于空间约束，我们通常忽略这些结果。接下来，我们将直接展示来自自然刺激数据集，对于学习基的稀疏编码的总运行时间。我们评估了系数学习和基学习算法的不同组合效果：来自我们实验的最快的系数学习方法（特征标志搜索，改进LARS和对于L稀疏函数的移植法，以及对于epsilonL

20、稀疏函数的共轭梯度）和最先进的基学习方法（有着迭代投影的梯度下降和拉格朗日对偶变化）。我们四种自然刺激数据集的每种取1000个输入向量作为训练集。我们随机初始化基，并运行每个算法组合（通过交替地优化系数和基）直到收敛。表2展示了不同算法组合的运行时间。首先，我们观察到拉格朗日对偶函数方法比有着迭代投影的梯度下降法对于L1和epsilonL1稀疏函数的表现有显著地提升；一种独特的收敛特征在图1（左）显示。第二，我们观察到，对于L1稀疏函数，特征标志搜索法比改进LARS和移植法表现更好。图1（右）展示了相比较特征标志搜索，改进LARS每次迭代的运行时间是移植法的数倍（对基学习使用同样的梯度下降算法

21、），这证明了显著的效率提升是在迭代的后期；注意到特征标志搜索（和移植法）可以通过前一次迭代初始化系数，然而改进LARS不行。这样的结果证明了特征标志搜索法对于迭代最优化问题是非常有效的，例如学习稀疏编码基。1Lagiiw|frtiutl-Gra-icnld»ce<i1SW30040Q$C0derationsLjsparsityfunctionCcKjfT/BasislearningnEilumljmxguspeechstereovideoFeature-sign/LagDualFeature-sign/GnidDescLARS/LagDualLARS!GradDcM：Graft

22、ing/LagDualGraftingIGradDesc260.01,093.9666.713,085.1720.52.767.924JS.21,280.31.697.717,219,01,025.58.670.843S.2950.61342.712J74.&3.006.06203.3186.6933.21,254.611,022.81,340.53,6S1.9epsilonL!sparsityfunctionCoeIT./BasislearningnaluralitnagespeechstereovideoConjGrad/LagDualConjGrad/GradDesc1,286.

23、65,047.3544.411,93951,942.43.43511,46192,479.2表2；使用不同稀疏函数的不同算法组合运行时间（以秒为单位）图1：加速的证明。左：对比拉格朗日对偶函数和梯度下降对于学习基的收敛。右：改进LARS和移植法相对于特征标志搜索法的每次迭代运行时间。5.3Learninghighlyovercompletenaturalimagebases使用我们的高效算法，我们能够学习如图2所示的自然图像的超完备基，例如，我们能够在2小时学习1024个基（每个14X14个像素）以及在10小时学习2000个基（每个20X20个像素）。相比较，对于基学习的梯度下降法在运行24小

24、时后并没有产生任何合理的基。更进一步，由对每个基拟合Gabor函数参数得到的学习基的概括数据，定性地符合之前报道的数据。a%;,RMlil!sinlsqd»£»g二.-.rKh_N-a槽-/:MB£l产日tp-'l»w册|1.»唐4L'U書.备£aCUEX.1:;1a.illm口iiSLrrldmHEPS.=一石kH趟-鬲'JiHuffsHUH-l*9ia:SSRI53:SE:3S堰富Ifer簸齡EM«RBfeHMHaHH9BI3SES_a=Bw尿mnILw5irJ_ff=SCK字!图2：学

25、习的超完备自然图像基。左：1024个基（每个14X14个像素）右：2000个基（每个20X20个像素）5.4Replicatingcomplexneurosciencephenomena一些V1区神经反应的复杂现象不能够被简单的线性模型解释（其中响应是线性的输入函数）。例如，很多视觉神经元展示了“突然中止”，这其中神经元响应的最优方向和位置的条状图像是被压制成条状长度超过了最优长度。稀疏编码能够通过稀疏化它们的系数（激活）来模拟基（神经元）之间的交互（抑制），并且我们的算法能够使这些现象在超完备基上测试。首先，我们评估突然中止行为是否能在稀疏编码框架中观察到。我们随机产生有着不同方向和长度为1

26、4X14的图像块的条带，并选取刺激条带能够最强地激活每个基，仅仅考虑那些能够被测试条带激活的基。对于每个活跃基，以及相应的最优条带位置和方向，我们变化条带大小从1像素到最大大小，并运行稀疏编码来测量选择基的系数，这是相对于它们最大的系数。如图3（左）所示，对于超完备基，我们观察到很多情况下系数随着条带超过最优点的增长而显著减少。这一结果和某些V1区神经元的突然中止行为相一致。第二，通过使用学习超完备基，我们测试位于中心的非传统感受野效应（nCRF）。我们发现了对于50个随机基的最优条带几次，并检查出这些基是其中最活跃的。对于每一个基，我们测量对于最优条带刺激在周围区域有着和没有排列条带刺激的响应（图3（右）。