|
|
Line 18: |
Line 18: |
| 上式前第一部分是利用基向量将特征集重构为样本数据所产生的误差,第二部分为稀疏性惩罚项(sparsity penalty term),用于保证特征集的稀疏性。 | | 上式前第一部分是利用基向量将特征集重构为样本数据所产生的误差,第二部分为稀疏性惩罚项(sparsity penalty term),用于保证特征集的稀疏性。 |
| | | |
- | 但是,如目标函数所示,它的约束性并不强――按常数比例缩放A的同时再按这个常数的倒数缩放s,结果不会改变误差大小,却会减少稀疏代价(表达式第二项)的值。因此,需要为A中每项Aj 增加额外约束
| + | 但是,如目标函数所示,它的约束性并不强――按常数比例缩放<math>A</math>的同时再按这个常数的倒数缩放<math>s</math>,结果不会改变误差大小,却会减少稀疏代价(表达式第二项)的值。因此,需要为<math>A</math>中每项<math>A_j</math>增加额外约束<math>A_j^TA_j \le 1</math>。问题变为: |
- | | + | |
- | [原文]
| + | |
- | | + | |
- | However, the objective function as it stands is not properly constrained - it is possible to reduce the sparsity cost (the second term) by scaling <math>A</math> by some constant and scaling <math>s</math> by the inverse of the same constant, without changing the error. Hence, we include the additional constraint that that for every column <math>A_j</math> of <math>A</math>,
| + | |
- | <math>A_j^TA_j \le 1</math>. Our problem is thus:
| + | |
- | | + | |
- | [初译]
| + | |
- | | + | |
- | 但是,目标函数在不改变重建误差的前提下,可以通过常数倍缩放<math>A</math>同时以该常数倒数等比例缩放<math>s</math>降低稀疏代价(目标函数第二项)。因此,需要为<math>A</math>中每项<math>A_j</math> 增加额外约束<math>A_j^TA_j \le 1</math>。问题变为:
| + | |
- | | + | |
- | [一审]
| + | |
- | | + | |
- | 但是,目标函数在不改变重建误差的前提下,可以通过常数倍扩大<math>A</math>同时以该常数倒数等比例缩放<math>s</math>降低稀疏代价(目标函数第二项)。因此,需要为<math>A</math>中每项<math>A_j</math> 增加额外约束<math>A_j^TA_j \le 1</math>。问题变为:
| + | |
- | | + | |
- | [原文]
| + | |
| | | |
| :<math> | | :<math> |
Line 42: |
Line 27: |
| </math> | | </math> |
| | | |
- | [原文]
| + | 遗憾的是,因为目标函数并不是一个凸函数,所以不能用梯度方法解决这个优化问题。但是,在给定<math>A</math>的情况下,最小化<math>J(A, s)</math>求解<math>s</math>是凸的。同理,给定<math>s</math>最小化<math>J(A, s)</math>求解<math>A</math>也是凸的。这表明,可以通过交替固定<math>s</math>和A分别求解<math>A</math>和<math>s</math>。实践表明,这一策略取得的效果非常好。 |
| | | |
- | Unfortunately, the objective function is non-convex, and hence impossible to optimize well using gradient-based methods. However, given <math>A</math>, the problem of finding <math>s</math> that minimizes <math>J(A, s)</math> is convex. Similarly, given <math>s</math>, the problem of finding <math>A</math> that minimizes <math>J(A, s)</math> is also convex. This suggests that we might try alternately optimizing for <math>A</math> for a fixed <math>s</math>, and then optimizing for <math>s</math> given a fixed <math>A</math>. It turns out that this works quite well in practice.
| + | 但是,以上表达式带来了另一个难题:不能用简单的梯度方法来实现约束条件<math>A_j^TA_j \le 1 \; \forall j</math>。因此在实际问题中,此约束条件还不足以成为“权重衰变”("weight decay")项以保证A的每一项值够小。这样我们就得到一个新的目标函数: |
| | | |
- | [初译]
| |
- |
| |
- | 遗憾的是,因为目标函数并不是一个凸函数,所以不能用梯度方法解决这个优化问题。但是,在给定<math>A</math>通过最小化<math>J(A, s)</math>求解<math>s</math>的问题是凸函数。同理,给定<math>s</math>通过最小化<math>J(A, s)</math>求解<math>A</math>的问题也是凸函数。这表明,可以通过交替固定<math>s</math>和<math>A</math>分别求解<math>A</math>和<math>s</math>。实践表明,这一策略取得的效果非常好。
| |
- |
| |
- | [一审]
| |
- |
| |
- | 遗憾的是,因为目标函数并不是一个凸函数,所以不能用梯度方法解决这个优化问题。但是,在给定<math>A</math>通过最小化<math>J(A, s)</math>求解<math>s</math>的问题是凸问题。同理,给定<math>s</math>通过最小化<math>J(A, s)</math>求解<math>A</math>的问题也是凸问题。这表明,可以通过交替固定<math>s</math>和<math>A</math>分别求解<math>A</math>和<math>s</math>。实践表明,这一策略取得的效果非常好。
| |
- |
| |
- | [原文]
| |
- |
| |
- | However, the form of our problem presents another difficulty - the constraint that <math>A_j^TA_j \le 1 \; \forall j</math> cannot be enforced using simple gradient-based methods. Hence, in practice, this constraint is weakened to a "weight decay" term designed to keep the entries of <math>A</math> small. This gives us a new objective function:
| |
- |
| |
- | [初译]
| |
- |
| |
- | 但是,问题的表示形式带来了另一个难题:其约束条件<math>A_j^TA_j \le 1 \; \forall j</math> 不能简单的应用到梯度方法中。因此在实际问题中,此约束条件被弱化为“权重衰变”("weight decay")项用于保证<math>A</math>的每一项值够小。至此得到一个新的目标函数:
| |
- |
| |
- | [一审]
| |
- |
| |
- | 但是,问题的表示形式带来了另一个难题:其约束条件<math>A_j^TA_j \le 1 \; \forall j</math> 不能在简单的梯度方法中实施。因此在实际问题中,此约束条件被弱化为“权重衰变”("weight decay")项以保证<math>A</math>的每一项值够小。至此得到一个新的目标函数:
| |
- |
| |
- | [原文]
| |
| | | |
| :<math> | | :<math> |
| J(A, s) = \lVert As - x \rVert_2^2 + \lambda \lVert s \rVert_1 + \gamma \lVert A \rVert_2^2 | | J(A, s) = \lVert As - x \rVert_2^2 + \lambda \lVert s \rVert_1 + \gamma \lVert A \rVert_2^2 |
| </math> | | </math> |
- |
| |
- | (note that the third term, <math>\lVert A \rVert_2^2</math> is simply the sum of squares of the entries of A, or <math>\sum_r{\sum_c{A_{rc}^2}}</math>)
| |
- |
| |
- | [初译]
| |
| | | |
| (注意上式中第三项, <math>\lVert A \rVert_2^2</math>等价于<math>\sum_r{\sum_c{A_{rc}^2}}</math>,是A各项的平方和) | | (注意上式中第三项, <math>\lVert A \rVert_2^2</math>等价于<math>\sum_r{\sum_c{A_{rc}^2}}</math>,是A各项的平方和) |
| | | |
- | [一审]
| + | 这一目标函数带来了最后一个问题,即L1范数在0点处不可微影响了梯度方法的应用。尽管可以通过其他非梯度下降方法避开这一问题,但是本文通过使用近似值“平滑”L1范数的方法解决此难题。使用<math>\sqrt{x + \epsilon}</math>代替<math>\left| x \right|</math>,对L1范数进行平滑,其中<math>\epsilon</math>是“平滑参数”("smoothing parameter")或者“稀疏参数”("sparsity parameter")(如果<math>\epsilon</math>远大于<math>x</math>, 则<math>x + \epsilon</math>的值由<math>\epsilon</math>主导,其平方根近似于 )。在下文提及拓扑稀疏编码时,“平滑”会派上用场。 |
- | | + | |
- | (注意上式中第三项, <math>\lVert A \rVert_2^2</math>等价于<math>\sum_r{\sum_c{A_{rc}^2}}</math>,是A各项的平方和)
| + | |
- | | + | |
- | [原文]
| + | |
- | | + | |
- | This objective function presents one last problem - the L1 norm is not differentiable at 0, and hence poses a problem for gradient-based methods. While the problem can be solved using other non-gradient descent-based methods, we will "smooth out" the L1 norm using an approximation which will allow us to use gradient descent. To "smooth out" the L1 norm, we use <math>\sqrt{x + \epsilon}</math> in place of <math>\left| x \right|</math>, where <math>\epsilon</math> is a "smoothing parameter" which can also be interpreted as a sort of "sparsity parameter" (to see this, observe that when <math>\epsilon</math> is large compared to <math>x</math>, the <math>x + \epsilon</math> is dominated by <math>\epsilon</math>, and taking the square root yields approximately <math>\sqrt{\epsilon}</math>). This "smoothing" will come in handy later when considering topographic sparse coding below.
| + | |
- | | + | |
- | Our final objective function is hence:
| + | |
- | | + | |
- | [初译]
| + | |
- | | + | |
- | 这一目标函数带来了最后一个问题,即L1范数在0点不可微影响了梯度方法的应用。尽管可以通过其他非梯度下降方法避开这一问题,但是本文通过使用近似值“平滑”L1范数的方法解决此难题。使用 <math>\sqrt{x + \epsilon}</math> 代替 <math>\left| x \right|</math>对L1范数进行平滑,其中<math>\epsilon</math>是“平滑参数”("smoothing parameter")或者“稀疏参数”("sparsity parameter")(如果<math>\epsilon</math>远大于<math>x</math>,则<math>x + \epsilon</math> 的值由<math>\epsilon</math>主导,其平方根近似于<math>\sqrt{\epsilon}</math>)。考虑拓扑稀疏编码时,“平滑”会派上用场。
| + | |
| | | |
| 因此,最终的目标函数是: | | 因此,最终的目标函数是: |
- |
| |
- | [一审]
| |
- |
| |
- | 这一目标函数表现出最后一个问题,即L1范数在0点不可微影响了梯度方法的应用。尽管可以通过其他非梯度下降方法避开这一问题,但是本文通过使用近似值“平滑”L1范数的方法解决此难题。使用 <math>\sqrt{x + \epsilon}</math> 代替 <math>\left| x \right|</math>对L1范数进行平滑,其中<math>\epsilon</math>是“平滑参数”("smoothing parameter")或者“稀疏参数”("sparsity parameter")(如果<math>\epsilon</math>远大于<math>x</math>,则<math>x + \epsilon</math> 的值由<math>\epsilon</math>主导,其平方根近似于<math>\sqrt{\epsilon}</math>)。后文可见考虑拓扑稀疏编码时,“平滑”会派上用场。
| |
- |
| |
- | 因此,最终的目标函数是:
| |
- |
| |
- | [原文]
| |
| | | |
| :<math> | | :<math> |
| J(A, s) = \lVert As - x \rVert_2^2 + \lambda \sqrt{s^2 + \epsilon} + \gamma \lVert A \rVert_2^2 | | J(A, s) = \lVert As - x \rVert_2^2 + \lambda \sqrt{s^2 + \epsilon} + \gamma \lVert A \rVert_2^2 |
| </math> | | </math> |
- |
| |
- | (where <math>\sqrt{s^2 + \epsilon}</math> is shorthand for <math>\sum_k{\sqrt{s_k^2 + \epsilon}}</math>)
| |
- |
| |
- | [初译]
| |
| | | |
| ( <math>\sqrt{s^2 + \epsilon}</math>是 <math>\sum_k{\sqrt{s_k^2 + \epsilon}}</math>的简写) | | ( <math>\sqrt{s^2 + \epsilon}</math>是 <math>\sum_k{\sqrt{s_k^2 + \epsilon}}</math>的简写) |
| | | |
- | [一审]
| + | 该目标函数可以通过以下过程迭代优化: |
- | | + | |
- | (其中 <math>\sqrt{s^2 + \epsilon}</math>是 <math>\sum_k{\sqrt{s_k^2 + \epsilon}}</math>的简写)
| + | |
- | | + | |
- | [原文]
| + | |
- | | + | |
- | This objective function can then be optimized iteratively, using the following procedure:
| + | |
- | <ol>
| + | |
- | <li>Initialize <math>A</math> randomly
| + | |
- | <li>Repeat until convergence
| + | |
- | <ol>
| + | |
- | <li>Find the <math>s</math> that minimizes <math>J(A, s)</math> for the <math>A</math> found in the previous step
| + | |
- | <li>Solve for the <math>A</math> that minimizes <math>J(A, s)</math> for the <math>s</math> found in the previous step
| + | |
- | </ol>
| + | |
- | </ol>
| + | |
- | | + | |
- | [初译]
| + | |
- | | + | |
- | 该目标函数可以通过以下过程迭代优化: | + | |
| <ol> | | <ol> |
| <li>随机初始化<math>A</math> | | <li>随机初始化<math>A</math> |
| <li>重复以下步骤直至收敛: | | <li>重复以下步骤直至收敛: |
| <ol> | | <ol> |
- | <li>根据上一步给定的<math>A</math>,求解能够最小化<math>J(A, s)</math>的<math>s</math> | + | <li>根据上一步给定的<math>A</math>,求解能够最小化<math>J(A, s)</math>的<math>s</math> |
- | <li>根据上一步得到的<math>s</math>,求解能够最小化<math>J(A, s)</math>的<math>A</math> | + | <li>根据上一步得到的<math>s</math>,,求解能够最小化<math>J(A, s)</math>的<math>A</math> </ol> |
- | </ol>
| + | |
| </ol> | | </ol> |
- |
| |
- | [一审]
| |
- |
| |
- | 该目标函数可以通过以下过程迭代优化:
| |
- | <ol>
| |
- | <li>随机初始化<math>A</math>
| |
- | <li>重复以下步骤直至收敛:
| |
- | <ol>
| |
- | <li>根据上一步给定的<math>A</math>,求解能够最小化<math>J(A, s)</math>的<math>s</math>
| |
- | <li>根据上一步得到的<math>s</math>,求解能够最小化<math>J(A, s)</math>的<math>A</math>
| |
- | </ol>
| |
- | </ol>
| |
- |
| |
- |
| |
| [原文] | | [原文] |
| | | |