稀疏编码

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 9: Line 6:
\mathbf{x} = \sum_{i=1}^k a_i \mathbf{\phi}_{i}  
\mathbf{x} = \sum_{i=1}^k a_i \mathbf{\phi}_{i}  
\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> 是稀疏的意思就是说:对于一组输入向量,我们只想有尽可能少的几个系数远大于零。选择使用具有稀疏性的分量来表示我们的输入数据是有原因的,因为绝大多数的感官数据,比如自然图像,可以被表示成少量基本元素的叠加,在图像中这些基本元素可以是面或者线。同时,比如与初级视觉皮层的类比过程也因此得到了提升。
 +
我们把有 <math>m</math> 个输入向量的稀疏编码代价函数定义为:
我们把有 <math>m</math> 个输入向量的稀疏编码代价函数定义为:
Line 19: Line 19:
\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 48: Line 56:
\end{align}</math>  
\end{align}</math>  
-
因为无论我们如何选择<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>\mathbf{\phi}</math> ,经验分布函数 <math>P^*(\mathbf{x})</math> 都是常量,也就是说我们只需要最大化对数似然函数 <math>P(\mathbf{x}\mid\mathbf{\phi})</math> 。
 +
假设 <math>\nu</math> 是具有方差 <math>\sigma^2</math> 的高斯白噪音,则有下式:
:<math>\begin{align}
:<math>\begin{align}
Line 55: Line 64:
\end{align}</math>
\end{align}</math>
-
为了确定分布<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}
P(\mathbf{a}) = \prod_{i=1}^{k} P(a_i)
P(\mathbf{a}) = \prod_{i=1}^{k} P(a_i)
\end{align}</math>
\end{align}</math>
 +
此时,我们将“稀疏”假设加入进来——假设任何一幅图像都是由相对较少的一些源特征组合起来的。因此,我们希望 <math>a_i</math> 的概率分布在零值附近是凸起的,而且峰值很高。一个方便的参数化先验分布就是:
此时,我们将“稀疏”假设加入进来——假设任何一幅图像都是由相对较少的一些源特征组合起来的。因此,我们希望 <math>a_i</math> 的概率分布在零值附近是凸起的,而且峰值很高。一个方便的参数化先验分布就是:
Line 66: Line 77:
P(a_i) = \frac{1}{Z}\exp(-\beta S(a_i))
P(a_i) = \frac{1}{Z}\exp(-\beta S(a_i))
\end{align}</math>
\end{align}</math>
 +
这里 <math>S(a_i)</math> 是决定先验分布的形状的函数。
这里 <math>S(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>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}
:<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>
 +
那么,我们的问题就简化为寻找:
那么,我们的问题就简化为寻找:
Line 80: Line 94:
\mathbf{\phi}^*=\text{argmax}_{\mathbf{\phi}} < \log(P(\mathbf{x} \mid \mathbf{\phi})) >
\mathbf{\phi}^*=\text{argmax}_{\mathbf{\phi}} < \log(P(\mathbf{x} \mid \mathbf{\phi})) >
\end{align}</math>
\end{align}</math>
 +
这里 <math><.></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 89: Line 105:
\end{align}</math>
\end{align}</math>
-
跟之前一样,我们可以通过减小 <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> 加一个限制以防止这种情况发生。
最后,我们可以定义一种线性生成模型的能量函数,从而将原先的代价函数重新表述为:
最后,我们可以定义一种线性生成模型的能量函数,从而将原先的代价函数重新表述为:
Line 97: Line 114:
  &= \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)  
  &= \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{array}</math>
\end{array}</math>
 +
其中 <math>\lambda = 2\sigma^2\beta</math> ,并且关系不大的常量已被隐藏起来。因为最大化对数似然函数等同于最小化能量函数,我们就可以将原先的优化问题重新表述为:
其中 <math>\lambda = 2\sigma^2\beta</math> ,并且关系不大的常量已被隐藏起来。因为最大化对数似然函数等同于最小化能量函数,我们就可以将原先的优化问题重新表述为:
Line 104: Line 122:
\end{align}</math>
\end{align}</math>
-
使用概率理论来分析,我们可以发现,选择 <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> 。
+
 
 +
使用概率理论来分析,我们可以发现,选择 <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> 。
 +
 
== 学习算法 ==
== 学习算法 ==
 +
使用稀疏编码算法学习基向量集的方法,是由两个独立的优化过程组合起来的。第一个是逐个使用训练样本 <math>\mathbf{x}</math> 来优化系数 <math>a_i</math> ,第二个是一次性处理多个样本对基向量 <math>\mathbf{\phi}</math> 进行优化。
使用稀疏编码算法学习基向量集的方法,是由两个独立的优化过程组合起来的。第一个是逐个使用训练样本 <math>\mathbf{x}</math> 来优化系数 <math>a_i</math> ,第二个是一次性处理多个样本对基向量 <math>\mathbf{\phi}</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>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>,虽然已经有了更有效的方法,比如求解拉格朗日对偶函数(Lagrange dual)。
用 <math>L_2</math> 范式约束来学习基向量,同样可以简化为一个带有二次约束的最小二乘问题,其问题函数在域 <math>\mathbf{\phi}</math> 内也为凸。标准的凸优化软件(如CVX)或其它迭代方法就可以用来求解 <math>\mathbf{\phi}</math>,虽然已经有了更有效的方法,比如求解拉格朗日对偶函数(Lagrange dual)。
 +
根据前面的的描述,稀疏编码是有一个明显的局限性的,这就是即使已经学习得到一组基向量,如果为了对新的数据样本进行“编码”,我们必须再次执行优化过程来得到所需的系数。这个显著的“实时”消耗意味着,即使是在测试中,实现稀疏编码也需要高昂的计算成本,尤其是与典型的前馈结构算法相比。
根据前面的的描述,稀疏编码是有一个明显的局限性的,这就是即使已经学习得到一组基向量,如果为了对新的数据样本进行“编码”,我们必须再次执行优化过程来得到所需的系数。这个显著的“实时”消耗意味着,即使是在测试中,实现稀疏编码也需要高昂的计算成本,尤其是与典型的前馈结构算法相比。
 +
 +
 +
 +
==中英文对照==
 +
 +
:稀疏编码 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