稀疏编码

From Ufldl

Jump to: navigation, search
 
Line 1: Line 1:
-
初译:@寅莹
+
== 稀疏编码 ==
-
 
+
-
一审:@大黄蜂的思索
+
-
 
+
稀疏编码算法是一种无监督学习方法,它用来寻找一组“超完备”基向量来更高效地表示样本数据。稀疏编码算法的目的就是找到一组基向量 <math>\mathbf{\phi}_i</math> ,使得我们能将输入向量 <math>\mathbf{x}</math> 表示为这些基向量的线性组合:
稀疏编码算法是一种无监督学习方法,它用来寻找一组“超完备”基向量来更高效地表示样本数据。稀疏编码算法的目的就是找到一组基向量 <math>\mathbf{\phi}_i</math> ,使得我们能将输入向量 <math>\mathbf{x}</math> 表示为这些基向量的线性组合:
Line 10: Line 7:
\end{align}</math>
\end{align}</math>
-
虽然形如主成分分析技术(PCA)能使我们方便地找到一组“完备”基向量,但是这里我们想要做的是找到一组'''“超完备”'''基向量来表示输入向量 <math>\mathbf{x}\in\mathbb{R}^n</math> (也就是说,<math>k > n</math>)。超完备基的好处是它们能更有效地找出隐含在输入数据内部的结构与模式。然而,对于超完备基来说,系数 <math>a_i</math> 不再由输入向量 <math>\mathbf{x}</math>唯一确定。因此,在稀疏编码算法中,我们另加了一个评判标准'''“稀疏性”'''来解决因超完备而导致的退化(degeneracy)问题。
+
 
 +
虽然形如主成分分析技术(PCA)能使我们方便地找到一组“完备”基向量,但是这里我们想要做的是找到一组'''“超完备”'''基向量来表示输入向量 <math>\mathbf{x}\in\mathbb{R}^n</math> (也就是说,<math>k > n</math>)。超完备基的好处是它们能更有效地找出隐含在输入数据内部的结构与模式。然而,对于超完备基来说,系数 <math>a_i</math> 不再由输入向量 <math>\mathbf{x}</math> 唯一确定。因此,在稀疏编码算法中,我们另加了一个评判标准'''“稀疏性”'''来解决因超完备而导致的退化(degeneracy)问题。
 +
 
这里,我们把“稀疏性”定义为:只有很少的几个非零元素或只有很少的几个远大于零的元素。要求系数 <math>a_i</math> 是稀疏的意思就是说:对于一组输入向量,我们只想有尽可能少的几个系数远大于零。选择使用具有稀疏性的分量来表示我们的输入数据是有原因的,因为绝大多数的感官数据,比如自然图像,可以被表示成少量基本元素的叠加,在图像中这些基本元素可以是面或者线。同时,比如与初级视觉皮层的类比过程也因此得到了提升。
这里,我们把“稀疏性”定义为:只有很少的几个非零元素或只有很少的几个远大于零的元素。要求系数 <math>a_i</math> 是稀疏的意思就是说:对于一组输入向量,我们只想有尽可能少的几个系数远大于零。选择使用具有稀疏性的分量来表示我们的输入数据是有原因的,因为绝大多数的感官数据,比如自然图像,可以被表示成少量基本元素的叠加,在图像中这些基本元素可以是面或者线。同时,比如与初级视觉皮层的类比过程也因此得到了提升。
-
我们把有m个输入向量的稀疏编码代价函数定义为:
+
 
 +
我们把有 <math>m</math> 个输入向量的稀疏编码代价函数定义为:
:<math>\begin{align}
:<math>\begin{align}
\text{minimize}_{a^{(j)}_i,\mathbf{\phi}_{i}} \sum_{j=1}^{m} \left|\left| \mathbf{x}^{(j)} - \sum_{i=1}^k a^{(j)}_i \mathbf{\phi}_{i}\right|\right|^{2} + \lambda \sum_{i=1}^{k}S(a^{(j)}_i)
\text{minimize}_{a^{(j)}_i,\mathbf{\phi}_{i}} \sum_{j=1}^{m} \left|\left| \mathbf{x}^{(j)} - \sum_{i=1}^k a^{(j)}_i \mathbf{\phi}_{i}\right|\right|^{2} + \lambda \sum_{i=1}^{k}S(a^{(j)}_i)
\end{align}</math>
\end{align}</math>
 +
此处 <math>S(.)</math> 是一个稀疏代价函数,由它来对远大于零的 <math>a_i</math> 进行“惩罚”。我们可以把稀疏编码目标函式的第一项解释为一个重构项,这一项迫使稀疏编码算法能为输入向量 <math>\mathbf{x}</math> 提供一个高拟合度的线性表达式,而公式第二项即“稀疏惩罚”项,它使 <math>\mathbf{x}</math> 的表达式变得“稀疏”。常量 <math>\lambda</math> 是一个变换量,由它来控制这两项式子的相对重要性。  
此处 <math>S(.)</math> 是一个稀疏代价函数,由它来对远大于零的 <math>a_i</math> 进行“惩罚”。我们可以把稀疏编码目标函式的第一项解释为一个重构项,这一项迫使稀疏编码算法能为输入向量 <math>\mathbf{x}</math> 提供一个高拟合度的线性表达式,而公式第二项即“稀疏惩罚”项,它使 <math>\mathbf{x}</math> 的表达式变得“稀疏”。常量 <math>\lambda</math> 是一个变换量,由它来控制这两项式子的相对重要性。  
-
虽然“稀疏性”的最直接测度标准是 "<math>L_0</math>" 范式(<math>S(a_i) = \mathbf{1}(|a_i|>0)</math>), 但这是不可微的,而且通常很难进行优化。在实际中,稀疏代价函数 <math>S(.)</math> 的普遍选择是<math>L_1</math> 范式代价函数 <math>S(a_i)=\left|a_i\right|_1 </math> 及对数代价函数 <math>S(a_i)=\log(1+a_i^2)</math>。
 
-
此外,很有可能因为减小 <math>a_i</math> 或增加<math>\mathbf{\phi}_i</math> 至很大的常量,使得稀疏惩罚变得非常小。为防止此类事件发生,我们将限制<math>\left|\left|\mathbf{\phi}\right|\right|^2</math> 要小于某常量 <math>C</math>。包含了限制条件的稀疏编码代价函数的完整形式如下:
+
虽然“稀疏性”的最直接测度标准是 "<math>L_0</math>" 范式(<math>S(a_i) = \mathbf{1}(|a_i|>0)</math>),但这是不可微的,而且通常很难进行优化。在实际中,稀疏代价函数 <math>S(.)</math> 的普遍选择是<math>L_1</math> 范式代价函数 <math>S(a_i)=\left|a_i\right|_1 </math> 及对数代价函数 <math>S(a_i)=\log(1+a_i^2)</math> 。
 +
 
 +
 
 +
此外,很有可能因为减小 <math>a_i</math> 或增加 <math>\mathbf{\phi}_i</math> 至很大的常量,使得稀疏惩罚变得非常小。为防止此类事件发生,我们将限制 <math>\left|\left|\mathbf{\phi}\right|\right|^2</math> 要小于某常量 <math>C</math> 。包含了限制条件的稀疏编码代价函数的完整形式如下:
:<math>\begin{array}{rc}
:<math>\begin{array}{rc}
Line 32: Line 35:
\\
\\
\end{array}</math>
\end{array}</math>
 +
 +
== 概率解释 [基于1996年Olshausen与Field的理论] ==
== 概率解释 [基于1996年Olshausen与Field的理论] ==
 +
到目前为止,我们所考虑的稀疏编码,是为了寻找到一个稀疏的、超完备基向量集,来覆盖我们的输入数据空间。现在换一种方式,我们可以从概率的角度出发,将稀疏编码算法当作一种“生成模型”。
到目前为止,我们所考虑的稀疏编码,是为了寻找到一个稀疏的、超完备基向量集,来覆盖我们的输入数据空间。现在换一种方式,我们可以从概率的角度出发,将稀疏编码算法当作一种“生成模型”。
-
我们将自然图像建模问题看成是一种限行叠加,叠加元素包括<math>k</math>个独立的源特征<math>\mathbf{\phi}_i</math>以及加性噪声<math>\nu</math>:
+
 
 +
我们将自然图像建模问题看成是一种线性叠加,叠加元素包括 <math>k</math> 个独立的源特征 <math>\mathbf{\phi}_i</math> 以及加性噪声 <math>\nu</math> :
:<math>\begin{align}
:<math>\begin{align}
Line 42: Line 49:
\end{align}</math>
\end{align}</math>
-
我们的目标是找到一组特征基向量 <math>\mathbf{\phi}</math> ,它使得图像的分布函数 <math>P(\mathbf{x}\mid\mathbf{\phi})</math> 尽可能地近似于输入数据的经验分布函数 <math>P^*(\mathbf{x})</math>。一种实现方式是,最小化 <math>P^*(\mathbf{x})</math> 与 <math>P(\mathbf{x}\mid\mathbf{\phi})</math> 之间的KL散度,此KL散度表示如下:
+
 
 +
我们的目标是找到一组特征基向量 <math>\mathbf{\phi}</math> ,它使得图像的分布函数 <math>P(\mathbf{x}\mid\mathbf{\phi})</math> 尽可能地近似于输入数据的经验分布函数 <math>P^*(\mathbf{x})</math> 。一种实现方式是,最小化 <math>P^*(\mathbf{x})</math> 与 <math>P(\mathbf{x}\mid\mathbf{\phi})</math> 之间的 KL 散度,此 KL 散度表示如下:
:<math>\begin{align}
:<math>\begin{align}
Line 49: Line 57:
-
【原文】
+
因为无论我们如何选择 <math>\mathbf{\phi}</math> ,经验分布函数 <math>P^*(\mathbf{x})</math> 都是常量,也就是说我们只需要最大化对数似然函数 <math>P(\mathbf{x}\mid\mathbf{\phi})</math> 。
-
 
+
假设 <math>\nu</math> 是具有方差 <math>\sigma^2</math> 的高斯白噪音,则有下式:
-
Since the empirical distribution <math>P^*(\mathbf{x})</math> is constant across our choice of <math>\mathbf{\phi}</math>, this is equivalent to maximizing the log-likelihood of <math>P(\mathbf{x}\mid\mathbf{\phi})</math>.
+
-
Assuming <math>\nu</math> is Gaussian white noise with variance <math>\sigma^2</math>, we have that
+
-
 
+
-
 
+
-
【初译】
+
-
 
+
-
因为通过我们对 <math>\mathbf{\phi}</math>的选择,经验分布 <math>P^*(\mathbf{x})</math> 是不变量,这相当于最大化对数似然 <math>P(\mathbf{x}\mid\mathbf{\phi})</math>。
+
-
假设 <math>\nu</math> 是方差为 <math>\sigma^2</math>高斯白噪声,有下式成立。
+
-
 
+
-
 
+
-
【一审】
+
-
 
+
-
因为经验分布函数 <math>P^*(\mathbf{x})</math> 对于所有的 <math>\mathbf{\phi}</math>其结果是常量,这就等于说要最大化对数似然函数 <math>P(\mathbf{x}\mid\mathbf{\phi})</math>。
+
-
假设 <math>\nu</math> 是具有方差 <math>\sigma^2</math>的高斯白噪音,则有下式:
+
:<math>\begin{align}
:<math>\begin{align}
Line 71: Line 65:
-
【原文】
+
为了确定分布 <math>P(\mathbf{x}\mid\mathbf{\phi})</math> ,我们需要指定先验分布 <math>P(\mathbf{a})</math> 。假定我们的特征变量是独立的,我们就可以将先验概率分解为:
-
 
+
-
In order to determine the distribution <math>P(\mathbf{x}\mid\mathbf{\phi})</math>, we also need to specify the prior distribution <math>P(\mathbf{a})</math>. Assuming the independence of our source features, we can factorize our prior probability as
+
-
 
+
-
 
+
-
【初译】
+
-
 
+
-
为决定 <math>P(\mathbf{x}\mid\mathbf{\phi})</math>的分布,需要描述先验分布<math>P(\mathbf{a})</math>。假设原特征分布独立,可分解先验分布如下式:
+
-
 
+
-
 
+
-
【一审】
+
-
 
+
-
为了确定 <math>P(\mathbf{x}\mid\mathbf{\phi})</math>的分布,我们同时要确定先验分布<math>P(\mathbf{a})</math>,假定我们的特征变量是独立的,我们就可得到先验概率为:
+
:<math>\begin{align}
:<math>\begin{align}
Line 90: Line 72:
-
【原文】
+
此时,我们将“稀疏”假设加入进来——假设任何一幅图像都是由相对较少的一些源特征组合起来的。因此,我们希望 <math>a_i</math> 的概率分布在零值附近是凸起的,而且峰值很高。一个方便的参数化先验分布就是:
-
 
+
-
At this point, we would like to incorporate our sparsity assumption -- the assumption that any single image is likely to be the product of relatively few source features. Therefore, we would like the probability distribution of <math>a_i</math> to be peaked at zero and have high kurtosis. A convenient parameterization of the prior distribution is
+
-
 
+
-
:<math>\begin{align}
+
-
P(a_i) = \frac{1}{Z}\exp(-\beta S(a_i))
+
-
\end{align}</math>
+
-
 
+
-
Where <math>S(a_i)</math> is a function determining the shape of the prior distribution.
+
-
 
+
-
 
+
-
【初译】
+
-
 
+
-
在这一点,我们将纳入稀疏假设---假设任一个图像都可能是相对少数源特征的乘积。因此,我们希望 <math>a_i</math> 的分布在零点得到峰值,且有较高的峰度。先验分布的一个合适的参数化是
+
   
   
:<math>\begin{align}
:<math>\begin{align}
Line 109: Line 78:
\end{align}</math>
\end{align}</math>
-
这里 <math>S(a_i)</math> 是一个函数,决定先验分布的形状。
 
 +
这里 <math>S(a_i)</math> 是决定先验分布的形状的函数。
-
【一审】
 
-
至此,我们将“稀疏”的设想加入进来――任一图像都可能是由很少一部分相关特征生成的。因此,我们希望 <math>a_i</math> 的概率分布在零值附近是凸起的,而且形态很陡峭。一个简易的参数化先验分布就是:
+
当定义了 <math>P(\mathbf{x} \mid \mathbf{a} , \mathbf{\phi})</math> 和 <math> P(\mathbf{a})</math> 后,我们就可以写出在由 <math>\mathbf{\phi}</math> 定义的模型之下的数据 <math>\mathbf{x}</math> 的概率分布:
   
   
-
:<math>\begin{align}
 
-
P(a_i) = \frac{1}{Z}\exp(-\beta S(a_i))
 
-
\end{align}</math>
 
-
 
-
这里函数 <math>S(a_i)</math> 决定了先验分布的形状。
 
-
 
-
 
-
【原文】
 
-
 
-
Having defined <math>P(\mathbf{x} \mid \mathbf{a}, \mathbf{\phi})</math> and <math> P(\mathbf{a})</math>, we can write the probability of the data <math>\mathbf{x}</math> under the model defined by <math>\mathbf{\phi}</math> as
 
-
 
:<math>\begin{align}
:<math>\begin{align}
P(\mathbf{x} \mid \mathbf{\phi}) = \int P(\mathbf{x} \mid \mathbf{a}, \mathbf{\phi}) P(\mathbf{a}) d\mathbf{a}
P(\mathbf{x} \mid \mathbf{\phi}) = \int P(\mathbf{x} \mid \mathbf{a}, \mathbf{\phi}) P(\mathbf{a}) d\mathbf{a}
\end{align}</math>
\end{align}</math>
-
and our problem reduces to finding
 
-
 
-
:<math>\begin{align}
 
-
\mathbf{\phi}^*=\text{argmax}_{\mathbf{\phi}} < \log(P(\mathbf{x} \mid \mathbf{\phi})) >
 
-
\end{align}</math>
 
-
 
-
Where <math><.></math> denotes expectation over our input data.
 
-
 
-
 
-
【初译】
 
-
定义了 <math>P(\mathbf{x} \mid \mathbf{a}, \mathbf{\phi})</math> 和 <math> P(\mathbf{a})</math>,在由 <math>\mathbf{\phi}</math> 定义的模型下,我们可以与出数据 <math>\mathbf{x}</math> 的概率为:
+
那么,我们的问题就简化为寻找:
-
+
-
:<math>\begin{align}
+
-
P(\mathbf{x} \mid \mathbf{\phi}) = \int P(\mathbf{x} \mid \mathbf{a}, \mathbf{\phi}) P(\mathbf{a}) d\mathbf{a}
+
-
\end{align}</math>
+
-
 
+
-
我们的问题演化为发现
+
   
   
:<math>\begin{align}
:<math>\begin{align}
Line 154: Line 95:
\end{align}</math>
\end{align}</math>
-
其中 <math><.></math> 表示期望我们的输入数据。
 
-
 
-
 
-
【一审】
 
-
 
-
当定义了 <math>P(\mathbf{x} \mid \mathbf{a}, \mathbf{\phi})</math> 和 <math> P(\mathbf{a})</math>后,我们就可以通过由 <math>\mathbf{\phi}</math> 生成的模型将数据集 <math>\mathbf{x}</math> 的概率确定为:
 
-
 
-
:<math>\begin{align}
 
-
P(\mathbf{x} \mid \mathbf{\phi}) = \int P(\mathbf{x} \mid \mathbf{a}, \mathbf{\phi}) P(\mathbf{a}) d\mathbf{a}
 
-
\end{align}</math>
 
-
 
-
那么,我们的问题就简缩为:
 
-
 
-
:<math>\begin{align}
 
-
\mathbf{\phi}^*=\text{argmax}_{\mathbf{\phi}} < \log(P(\mathbf{x} \mid \mathbf{\phi})) >
 
-
\end{align}</math>
 
-
 
-
这里 <math><.></math> 指的是输入数据的期望值。
 
-
 
-
 
-
【原文】
 
-
 
-
Unfortunately, the integral over <math>\mathbf{a}</math> to obtain <math>P(\mathbf{x} \mid \mathbf{\phi})</math> is generally intractable. We note though that if the distribution of <math>P(\mathbf{x} \mid \mathbf{\phi})</math> is sufficiently peaked (w.r.t. <math>\mathbf{a}</math>), we can approximate its integral with the maximum value of  <math>P(\mathbf{x} \mid \mathbf{\phi})</math> and obtain a approximate solution
 
-
 
-
 
-
【初译】
 
-
 
-
不幸的是,基于所有 <math>\mathbf{a}</math>  获得 <math>P(\mathbf{x} \mid \mathbf{\phi})</math> 难以解决。注意到如果 <math>P(\mathbf{x} \mid \mathbf{\phi})</math> 能够充分地达到峰值(w.r.t. <math>\mathbf{a}</math>),我能近似其整数,通过最大化  <math>P(\mathbf{x} \mid \mathbf{\phi})</math> 而得到一个近似解
 
 +
这里 <math><.></math> 表示的是输入数据的期望值。
-
【一审】
 
-
不幸的是,通过对 <math>\mathbf{a}</math> 的积分计算 <math>P(\mathbf{x} \mid \mathbf{\phi})</math> 通常是难以实现的。虽然如此,我们注意到如果 <math>P(\mathbf{x} \mid \mathbf{\phi})</math> 的分布(对于相应的<math>\mathbf{a}</math>)足够陡峭的话,我们就可以用 <math>P(\mathbf{x} \mid \mathbf{\phi})</math> 的最大值来估算以上积分。估算方法如下:
+
不幸的是,通过对 <math>\mathbf{a}</math> 的积分计算 <math>P(\mathbf{x} \mid \mathbf{\phi})</math> 通常是难以实现的。虽然如此,我们注意到如果 <math>P(\mathbf{x} \mid \mathbf{\phi})</math> 的分布(对于相应的 <math>\mathbf{a}</math> )足够陡峭的话,我们就可以用 <math>P(\mathbf{x} \mid \mathbf{\phi})</math> 的最大值来估算以上积分。估算方法如下:
:<math>\begin{align}
:<math>\begin{align}
Line 193: Line 106:
-
【原文】
+
跟之前一样,我们可以通过减小 <math>a_i</math> 或增大 <math>\mathbf{\phi}</math> 来增加概率的估算值(因为 <math>P(a_i)</math> 在零值附近陡升)。因此我们要对特征向量 <math>\mathbf{\phi}</math> 加一个限制以防止这种情况发生。
-
As before, we may increase the estimated probability by scaling down <math>a_i</math> and scaling up <math>\mathbf{\phi}</math> (since <math>P(a_i)</math> peaks about zero) , we therefore impose a norm constraint on our features <math>\mathbf{\phi}</math> to prevent this.
+
最后,我们可以定义一种线性生成模型的能量函数,从而将原先的代价函数重新表述为:
-
 
+
-
 
+
-
【初译】
+
-
 
+
-
如前所述,增加估计的概率通过缩小 <math>a_i</math> 和放大 <math>\mathbf{\phi}</math> (因为<math>P(a_i)</math> 在零点得到峰值),因此,在特征 <math>\mathbf{\phi}</math> 上增加了一个范数约束避免这种可能。
+
-
 
+
-
 
+
-
【一审】
+
-
 
+
-
跟之前一样,我们就可以通过减小 <math>a_i</math> 或增大 <math>\mathbf{\phi}</math> 来增加概率的估算值(因为<math>P(a_i)</math> 在零值附近陡升)。因此我们要对特征向量 <math>\mathbf{\phi}</math> 加一个限制以防止这种情况发生。
+
-
 
+
-
 
+
-
【原文】
+
-
 
+
-
Finally, we can recover our original cost function by defining the energy function of this linear generative model
+
-
 
+
-
 
+
-
【初译】
+
-
 
+
-
最后,通过定义线性生成模型的能量函数覆盖最初的代价函数。
+
-
 
+
-
 
+
-
【一审】
+
-
 
+
-
最后,我们就可以通过定义一种线性生成模型的能量函数来将原先的代价函数重新表述为:
+
:<math>\begin{array}{rl}
:<math>\begin{array}{rl}
Line 228: Line 116:
-
【原文】
+
其中 <math>\lambda = 2\sigma^2\beta</math> ,并且关系不大的常量已被隐藏起来。因为最大化对数似然函数等同于最小化能量函数,我们就可以将原先的优化问题重新表述为:
-
 
+
-
where <math>\lambda = 2\sigma^2\beta</math> and irrelevant constants have been hidden. Since maximizing the log-likelihood is equivalent to minimizing the energy function, we recover the original optimization problem:
+
-
 
+
-
 
+
-
【初译】
+
-
 
+
-
此处, <math>\lambda = 2\sigma^2\beta</math> 且不相关的常量已被隐藏。因为最大化对数似然等价于最小化能量函数,覆盖最初的的优化问题:
+
-
 
+
-
 
+
-
【一审】
+
-
 
+
-
此处, <math>\lambda = 2\sigma^2\beta</math> ,其中关系不大的常量已被隐藏起来。因为最大化对数似然函数等同于最小化能量函数,我们将原先的优化问题重新表述为:
+
:<math>\begin{align}
:<math>\begin{align}
Line 247: Line 123:
-
【原文】
+
使用概率理论来分析,我们可以发现,选择 <math>L_1</math> 惩罚和 <math>\log(1+a_i^2)</math> 惩罚作为函数 <math>S(.)</math> ,分别对应于使用了拉普拉斯概率 <math>P(a_i) \propto \exp\left(-\beta|a_i|\right)</math> 和柯西先验概率 <math>P(a_i) \propto \frac{\beta}{1+a_i^2}</math> 。
-
 
+
-
Using a probabilistic approach, it can also be seen that the choices of the <math>L_1</math> penalty <math>\left|a_i\right|_1 </math> and the log penalty <math>\log(1+a_i^2)</math> for <math>S(.)</math> correspond to the use of the Laplacian <math>P(a_i) \propto \exp\left(-\beta|a_i|\right)</math> and the Cauchy prior <math>P(a_i) \propto \frac{\beta}{1+a_i^2}</math> respectively.
+
-
 
+
-
 
+
-
【初译】
+
-
 
+
-
使用概率方法,可看作是对 <math>L_1</math> 惩罚项 <math>\left|a_i\right|_1 </math> 和对数惩罚项 <math>\log(1+a_i^2)</math> 的选择,对于 <math>S(.)</math> 对应着Laplacian <math>P(a_i) \propto \exp\left(-\beta|a_i|\right)</math> 和 Cauchy先验 <math>P(a_i) \propto \frac{\beta}{1+a_i^2}</math> 的使用。
+
-
 
+
-
 
+
-
【一审】
+
-
 
+
-
使用概率方法,也可被看成是为基于 <math>L_1</math> 范式的 <math>S(.)</math> 选择使用拉普拉斯定理 <math>P(a_i) \propto \exp\left(-\beta|a_i|\right)</math> 的代价函数 <math>\left|a_i\right|_1 </math> ,还是选择使用柯西先验定理 <math>P(a_i) \propto \frac{\beta}{1+a_i^2}</math> 的对数代价函数 <math>\log(1+a_i^2)</math> 。
+
-
 
+
-
== Learning ==
+
-
 
+
-
'''学习 (一审:算法学习)'''
+
-
 
+
-
 
+
-
【原文】
+
-
 
+
-
Learning a set of basis vectors <math>\mathbf{\phi}</math> using sparse coding consists of performing two separate optimizations, the first being an optimization over coefficients <math>a_i</math> for each training example <math>\mathbf{x}</math> and the second an optimization over basis vectors <math>\mathbf{\phi}</math> across many training examples at once.
+
-
 
+
-
 
+
-
【初译】
+
-
 
+
-
学习一组集基向量 <math>\mathbf{\phi}</math> 使用稀疏编码组成两种独立的优化, 第一类对于每个训练样本基于系数 <math>a_i</math> 的优化,第二类是对多个训练样本,基于向量 <math>\mathbf{\phi}</math> 的优化。
+
-
 
+
-
 
+
-
【一审】
+
-
 
+
-
使用稀疏编码算法学习基向量集的方法由两项各自独立的优化方法来实现,其一是逐个套用样本 <math>\mathbf{x}</math> 对系数 <math>a_i</math> 进行优化,其二是一次性处理多个样本对基向量 <math>\mathbf{\phi}</math> 进行优化。
+
-
 
+
-
 
+
-
【原文】
+
-
 
+
-
Assuming an <math>L_1</math> sparsity penalty, learning <math>a^{(j)}_i</math> reduces to solving a <math>L_1</math> regularized least squares problem which is convex in <math>a^{(j)}_i</math> for which several techniques have been developed (convex optimization software such as CVX can also be used to perform L1 regularized least squares). Assuming a differentiable <math>S(.)</math> such as the log penalty, gradient-based methods such as conjugate gradient methods can also be used.
+
-
 
+
-
 
+
-
【初译】
+
-
 
+
-
假设 <math>L_1</math> 稀疏惩罚,学习 <math>a^{(j)}_i</math> 减化为求解 一个 <math>L_1</math> 的正规化最小二乘问题,即在 <math>a^{(j)}_i</math> 上的凸集问题,针对此已有若干技术 (凸优化软件,如CVX 也被用于解决L1正规化最小二乘)。假定一个可微 <math>S(.)</math> ,如对数惩罚,基于梯度的方法,如共轭梯度方法用来解决优化问题。
+
-
 
+
-
 
+
-
【一审】
+
-
以 <math>L_1</math> 范式稀疏惩罚(代价函数)为例,对 <math>a^{(j)}_i</math> 的学习过程就简化为求解 <math>L_1</math> 范式的正则化最小二乘法问题,这个问题函式在域 <math>a^{(j)}_i</math> 内为凸,已经有很多技术方法可以求得这个凸集(诸如CVX之类的凸优化软件可以用来解决L1范式的正则化最小二乘法问题)。如果可微函数 <math>S(.)</math> 是一个类似对数惩罚函数,则可以采用基于梯度算法的方法如共轭梯度法。
 
 +
== 学习算法 ==
-
【原文】
+
使用稀疏编码算法学习基向量集的方法,是由两个独立的优化过程组合起来的。第一个是逐个使用训练样本 <math>\mathbf{x}</math> 来优化系数 <math>a_i</math> ,第二个是一次性处理多个样本对基向量 <math>\mathbf{\phi}</math> 进行优化。
-
Learning a set of basis vectors with a <math>L_2</math> norm constraint also reduces to a least squares problem with quadratic constraints which is convex in <math>\mathbf{\phi}</math>. Standard convex optimization software (e.g. CVX) or other iterative methods can be used to solve for <math>\mathbf{\phi}</math> although significantly more efficient methods such as solving the Lagrange dual have also been developed.
 
 +
如果使用 <math>L_1</math> 范式作为稀疏惩罚函数,对 <math>a^{(j)}_i</math> 的学习过程就简化为求解 由 <math>L_1</math> 范式正则化的最小二乘法问题,这个问题函数在域 <math>a^{(j)}_i</math> 内为凸,已经有很多技术方法来解决这个问题(诸如CVX之类的凸优化软件可以用来解决L1正则化的最小二乘法问题)。如果 <math>S(.)</math> 是可微的,比如是对数惩罚函数,则可以采用基于梯度算法的方法,如共轭梯度法。
-
【初译】
 
-
<math>L_2</math> 范数约束下学习一组基向量,常简化为有二次约束的最小二乘问题,也是基向量 <math>\mathbf{\phi}</math>上的凸问题。虽然已有更有效的方法,如解决拉格朗日对偶方法,标准凸优化软件(例如 CVX)或其它迭代方法都可用来求解基向量 <math>\mathbf{\phi}</math>
+
<math>L_2</math> 范式约束来学习基向量,同样可以简化为一个带有二次约束的最小二乘问题,其问题函数在域 <math>\mathbf{\phi}</math> 内也为凸。标准的凸优化软件(如CVX)或其它迭代方法就可以用来求解 <math>\mathbf{\phi}</math>,虽然已经有了更有效的方法,比如求解拉格朗日对偶函数(Lagrange dual)。
-
【一审】
+
根据前面的的描述,稀疏编码是有一个明显的局限性的,这就是即使已经学习得到一组基向量,如果为了对新的数据样本进行“编码”,我们必须再次执行优化过程来得到所需的系数。这个显著的“实时”消耗意味着,即使是在测试中,实现稀疏编码也需要高昂的计算成本,尤其是与典型的前馈结构算法相比。
-
用 <math>L_2</math> 范式学习基向量同样可以简化为求解二次约束最小二乘问题,其问题函式在域 <math>\mathbf{\phi}</math>内也为凸。标准凸优化软件(如CVX)或其它迭代方法就可以用来求解 <math>\mathbf{\phi}</math>,虽然已经有了求解拉格朗日对偶函数这样的更有效率的方法。
 
-
【原文】
+
==中英文对照==
-
As described above, a significant limitation of sparse coding is that even after a set of basis vectors have been learnt, in order to "encode" a new data example, optimization must be performed to obtain the required coefficients. This significant "runtime" cost means that sparse coding is computationally expensive to implement even at test time especially compared to typical feedforward architectures.
+
:稀疏编码 Sparse Coding
 +
:无监督学习 unsupervised method
 +
:超完备基 over-complete bases
 +
:主成分分析 PCA
 +
:稀疏性 sparsity
 +
:退化 degeneracy
 +
:代价函数 cost function
 +
:重构项 reconstruction term
 +
:稀疏惩罚项 sparsity penalty
 +
:范式 norm
 +
:生成模型 generative model
 +
:线性叠加 linear superposition
 +
:加性噪声 additive noise
 +
:特征基向量 basis feature vectors
 +
:经验分布函数 the empirical distribution
 +
:KL 散度 KL divergence
 +
:对数似然函数 the log-likelihood
 +
:高斯白噪音 Gaussian white noise
 +
:先验分布 the prior distribution
 +
:先验概率 prior probability
 +
:源特征 source features
 +
:能量函数 the energy function
 +
:正则化 regularized
 +
:最小二乘法 least squares
 +
:凸优化软件convex optimization software
 +
:共轭梯度法 conjugate gradient methods
 +
:二次约束 quadratic constraints
 +
:拉格朗日对偶函数 the Lagrange dual
 +
:前馈结构算法 feedforward architectures
-
【初译】
+
==中文译者==
-
如前所述,稀疏编码有效的限制是:即使在学习一组基向量后,“编码”一个新的数据样本,要获得需要的系数,必须执行优化。这个有效的“运行”代价指的是稀疏编码计算成本高昂,特别当与典型的前馈结构构相比,即使是测试计算代价仍很高。
+
柳翠寅(liucuiyin@163.com),林锋(xlfg@yeah.net),王方(fangkey@gmail.com)
-
【一审】
 
-
综上所述,即使已经学习得到一组基向量,稀疏编码算法还是极有局限性的。为了对一组新样本进行“编码”,必须执行优化才可以得到所需要的系数。即使只是在测试的时候,特别是相比于“前馈”模式,这种巨大的“运行时”成本意味着稀疏编码是极耗运算性能的。
+
{{Languages|Sparse_Coding|English}}

Latest revision as of 08:32, 8 April 2013

Personal tools