高效稀疏编码算法1 Introduction稀疏编码提供了发现对于外来刺激简明表示的一系列算法；给予未标记的输入数据，它 学习可以抓住数据高水平特征的基函数。当一个稀疏编码算法英语到自然图像时，学习的基 函数就类似于视觉皮层中的神经元感受野;此外，当应用到其他自然刺激例如语音和视频时， 稀疏编码产生局部基函数。不同于其他无监督学习技术例如主成分分析，稀疏编码可以应用 到学习超完备基函数，其中基函数的维度大于输入数据维度。稀疏编码同样可以通过稀疏化 它们的刺激来生成基函数之间抑制模型。同样的性质可以在生物神经元中观察到，这样使得 稀疏编码得到视觉皮层的合理模型。尽管关于稀疏编码模型有良好的前景，我们认为它们的发展很大程度上被昂贵的计算代 价所阻碍。特别是学习大维度，超完备代表时就会极度耗费计算资源。在这篇文章中，我们 提出了一类基于变量两组子集的交替优化的高效稀疏编码。这类优化问题是凸问题;特别地， 对于第一个子集的优化是一范数最小二乘问题；第二个子集则是二范数最小二乘问题。我们 描述了每个算法并经验地分析了它们的表现。我们的方法允许我们高效地学习来及自然图像 的高维度超完备基函数。我们证明了结果学习基展示了终止情况和对于传统感受野之外刺激 的调整。此外，稀疏编码同样提供了对于V1区神经元这些现象的局部解释。在最近的工作 中，我们展示了学习高水平特征的简明表示可以应用到监督分类任务。2 Preliminaries稀疏的目标就是将输入向量表示为少量的(未知的)“基函数”的加权线性组合。这些 基函数可以抓住输入数据中的高水平特征。具体地说，每个输入的向量匚一收可以简单 T 且T,地由基函数.：厂晾和稀疏加权向量或系数：-使得来表示。这些基函数是超完备的(nk)，这样可以抓取输入数据的大量值。稀疏编码是可以使用无标签数据自动获取良好的基向量。标准生成模型假设重构误差是，且是标准高斯分布协方差为。为了支持稀疏系数，每个系数一的优先 分布定义为广顼：七，其中是稀疏函数，是一个常数。例如，我 们可以使用如下函数：仆勺 | 1 (Lj penally function)I姒勺=0）,一 （如果- 0），或者0（如果- =0）。仅仅考虑非零系数，式（4）简化为标准无约束的二次最优化问题（QP），这样就可以高效地解析求解。因此，牌）我们的算法尝试去找到，或者说是“猜出”系数-的特征；无论是怎么猜测我们都能够高 效地求解出无约束QP问题。此外，如果初始值是错误的，算法会系统地改善搜索值。为了简化符号表示，我们将算法表示为下面等效的最优化问题：miiiin血e J3）=皿一一711111：（5）其中一是一个常数，特征标志搜索算法仔算法1中所示。它保持了潜在非零系数的活 跃子集和相应的标志一一其他的系数必须是零值，并且系统地搜索最优的活跃子集和系数标 志。算法通过一系列“特征标志步骤”来进行：在每一步，它对活跃子集和其标志进行猜测，I!.并计算无约束QP问题的解析解,、；接着通过在当前解和二F0之间的高效离散线性搜索，它会不断更新解，活跃子集和标志（详见算法1）。我们将会表现每一步会减小目标 函数f（x），最终算法总会收敛到最优解。算法1特征标志搜索算法1初始化.w二;，：活跃子集；=，其中代表标志- 2从零系数x中，选择=莒”诅0臧 ，激活Xj （将i加入活跃子集）仅当它局部提高目标函数，即：如果，那么令 =一-，活跃子集：=L 活跃子集。如: 一；那么令=，活跃子集：二:活跃子集。3特征标志步骤：令I是A的子矩阵，其仅仅包含相应活跃子集的列。令和”分别是和门相对于活跃子集的子向量。计算无约束QP问题的解析解（ - I ）：企5 ：=（指丁0）T（0丁g -展/2）从到的闭合线性部分进行离散线性搜索:检查目标函数在和其他所有系数标志变化点的值。更新到有着最小目标函数值的点。去掉在活跃子集中的零值，并更新:=4检查最优化条件：（a） 对于非零系数的最优化条件：一 厂如果条件（a）不满足，转到步骤3（不做任何激活）；否则检查条件（b）如ll【 * Vru - 0（b） 对于零系数的最优化条件：四 二X 如果条件（b）不满足，转到步骤2；否则返回x为最终解。为了证明收敛，令系数向量x和所给的活跃子集和标志向量I一致如果对所有的i满足 下面两个条件：（i）如果i在活跃子集中，那么一，（ii）如果i不在活跃子 集中，那么 一 I。1.引理3.1考虑最优化问题（5）增加额外限制：x是同所给的活跃子集和标志向量相一致。 那么，如果当前系数二是同活跃子集和标志向量相一致，但是对于步骤3的增广问题并不 是最优的，特征标志步骤是保证严格减小目标函数。简略证明。令是J，相对于所给活跃子集中系数的子向量。仔步骤3中，考虑到平滑的二 在考虑两:LUWL -一会严格地减小目标函数；（ii）如果 -不是和所给的活跃子集和标志向量 一致，令为在到，线性部分的第一个零交叉点（其中任何系数改变其标志），那么很明显了 ，而且由于.，的凸性质-，因此我们可以得到-，- .：。因此，在步骤3中描述的离散线性搜索保证了目标函数值的减少。引理3.2考虑最优化问题（5）增加额外限制：x是同所给的活跃子集和标志向量相一致。如果系数在步骤2的初始对于增广问题是最优的，但对问题（5）不是最优的，特征标志 步骤保证严格减小目标函数。简略证明。因为二对于增广问题是最优的，它满足最优化条件（a），但是不满足条件（b）；&ly 4h| 义-因此，在步骤2中，存在一些i,使得；这些第i个系数被激活，i被加*-mc入活跃子集中。在步骤3中，考虑平滑二次函数.，一 幅一，| - 一疽观察到：（i）因为在：一的泰勒展开仅在有一阶项（对其他系数使用条件4（a），我们得到任何局部减小.的方向必须和活跃的标志相一致，（ii）因为，并不是、的 CA最优点，必须在.,一附近沿着、到的方向减小。从（i）和（ii）得知，从，到的线性搜索方向必须和活跃-匚的标志相一致。最终，因为当和活跃子集相一致时一； ,，或者相一致的，或者从、至卜的第一零交叉点有最 小目标函数值（同引理3.1相似）。定理3.3特征标志搜索算法对于最优化问题（5）在有限的步数内收敛到全局最优点简单证明。从上述的引理中，它遵循着特征标志步骤总是严格地减小目标函数f（x）。在步 骤2的开始，x要不满足最优化条件4 （a），要不是零向量；在哪种条件下，x都是同当前 的活跃子集和标志向量相一致，并且对于上述引理描述的增广问题必须是最优的。因为所有 可能的活跃子集和系数标志是有限的，而且没有重复的一对（因为目标函数值是严格减少的）， 步骤2-4（b）的外层循环是不能无期限地重复。这样是正确的是因为步骤3-4（a）总是导致要 不退出到步骤4（b），要不减少活跃子集的大小。注意到从任意起始点开始计算需要一点小的改进：在初始化，和活跃子集，得到一个初 始解，我们需要进行步骤3而不是步骤1。当初始解在最优解附近，特征标志搜索可以比初 始值是更快地得到最优解。4Learning bases using the Lagrange dual在这一小节中，我们提出一种在固定系数S情况下求解基于基B的最优化问题（3）。该 问题简化为下列问题：minimizeX HS|#（6）subj巳S to留 c? Vj = 1,这是有二次约束的最小二乘问题。通常来说，这类约束最小化问题可以通过迭代投影梯 度下降方法。然而，使用拉格朗日对偶会更加高效。首先，考虑拉格朗日算符：71 k（瓦荷 =trace （X - 3$）丁（X - 8闵）+ %（】哈 - 6,（7）j=l ，=1其中每个_,是对偶变量。对B解析地最小化，我们得到朗格朗日对偶:(3)(9)P(A) = imn(Z?:A) = trace (XTX - X5T(55T +-混),其中上-、。 的梯度和海塞矩阵分别有下式计算:-|X$T 昭丁 +A)T邪-乌-2 (SST + A)-1(X5t)tA5t(SSt + A)-1) (S$T + A)-1). ? (10)C/AjUAf*讨w 其中，三-是第i个单位向量。我们可以通过使用牛顿法或者共轭梯度法来优化拉格朗 日对偶（8）。在最大化：后，我们得到最优基B如下所示:归丁 = （SST + 八）一1（5丁）丁.（11）求解对偶的优势是它相比较于原始的方法使用了更少的最优化变量。例如，最优化 R E般1网。、顼