稀疏编码

From Ufldl

Jump to: navigation, search
Line 55: Line 55:
\end{align}</math>
\end{align}</math>
-
 
+
为了确定分布<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 74: Line 61:
\end{align}</math>
\end{align}</math>
-
 
+
此时,我们将“稀疏”假设加入进来——假设任何一幅图像都是由相对较少的一些源特征组合起来的。因此,我们希望 <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 94: Line 67:
\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>a_i</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 139: Line 81:
\end{align}</math>
\end{align}</math>
-
其中 <math><.></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>\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> 的最大值来估算以上积分。估算方法如下:
Line 177: Line 89:
\end{align}</math>
\end{align}</math>
 +
跟之前一样,我们可以通过减小 <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 212: Line 98:
\end{array}</math>
\end{array}</math>
-
 
+
其中 <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 231: Line 104:
\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>\mathbf{x}</math> 来优化系数 <math>a_i</math> ,第二个是一次性处理多个样本对基向量 <math>\mathbf{\phi}</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>L_1</math> 范式作为稀疏惩罚函数,对 <math>a^{(j)}_i</math> 的学习过程就简化为求解 <math>L_1</math> 范式正则化的最小二乘法问题,这个问题在域 <math>a^{(j)}_i</math> 内为凸,已经有很多技术方法来解决这个问题(诸如CVX之类的凸优化软件可以用来解决L1正则化的最小二乘法问题)。如果 <math>S(.)</math> 是可微的,比如是对数惩罚函数,则可以采用基于梯度算法的方法,如共轭梯度法。

Revision as of 17:02, 16 March 2013

Personal tools