Tag: all
为什么反向传播比前向传播更高效
为什么反向传播比前向传播更高效
找到了一个很好的解释: 为什么说反向传播算法很高效？要回答这个问题，让我们来考虑另一种计算梯度的方式。设想现在是神经网络研究的早期阶段，大概是在上世纪50年代或60年代左右，并且你是第一个想到使用梯度下降方法来进行训练的人！但是要实现这个想法，你需要一种计算代价函数梯度的方式。你回想了你目前关于演算的知识，决定试一下是否能用链式法则来计算梯度。但是琢磨了一会之后发现，代数计算看起来非常复杂，你也因此有些失落。所以你尝试着寻找另一种方法。你决定把代价单独当做权重的函数（我们一会再来讨论偏置）。将权重写作，并且要对某个权重计算。一个很明显的计算方式是使用近似： 其中是一个大于零的极小数, 是第个方向上的单位向量。换句话说，我们可以通过计算两个差距很小的的代价，然后利用上面的等式来估计。我们可以利用相同的思想来对偏置求偏导。 > 这种方式看起来很不错。它的概念很简单，实现起来也很简单，只需要几行代码。当然了，他看起来要比使用链式法则来计算梯度靠谱多了！ > 然而遗憾的是，虽然这种方式看起来很美好，但当用代码实现之后就会发现，它实在是太慢了。要理解其中的原因的话，设想在我们的神经网络中有一百万个权重，对于每一个不同的权重，为了计算，我们需要计算。这意味着为了计算梯度，我们需要计算一百万次代价函数，进而对于每一个训练样例，都需要在神经网络中前向传播一百万次。我们同样需要计算，因此总计需要一百万零一次前向传播。 > 反向传播的优点在于它仅利用一次前向传播就可以同时计算出所有的偏导，随后也仅需要一次反向传播。大致来说，反向传播算法所需要的总计算量与两次前向传播的计算量基本相等（这应当是合理的，但若要下定论的话则需要更加细致的分析。合理的原因在于前向传播时主要的计算量在于权重矩阵的乘法计算，而反向传播时主要的计算量在于权重矩阵转置的乘法。很明显，它们的计算量差不多）。这与基于等式(46)的方法所需要的一百万零一次前向传播相比，虽然反向传播看起来更复杂一些，但它确实更更更更更快。 > 这种加速方式在1986年首次被人们所重视，极大地拓展了神经网络能够适用的范围，也导致了神经网络被大量的应用。当然了，反向传播算法也不是万能的。在80年代后期，人们终于触及到了性能瓶颈，在利用反向传播算法来训练深度神经网络（即具有很多隐含层的网络）时尤为明显。在本书后面的章节中我们将会看到现代计算机以及一些非常聪明的新想法是如何让反向传播能够用来训练深度神经网络的。 Source: 为什么说反向传播算法很高效 · 神经网络与深度学习 原文无公式, 对照英文原文: Neural networks and deep...
代换密码（Substitution Cipher）与置换密码（Permutation Cipher）
代换密码（Substitution Cipher）与置换密码（Permutation Cipher）
代换密码与置换密码（Substitution Cipher & Permutation Cipher） Tags: #Math #Cryptography #Course 分不清楚这两个完全是翻译的锅 置换（不是置换密码）Permutation（Not Permutation Cipher) 首先置换是数学上的一种操作，是对一组确定的元素进行重新排列 元素不变 只改变顺序 Wikipedia: In mathematics, a permutation of a set "Set (mathematics)") is,...
图灵归约 Turing Reduction
图灵归约 Turing Reduction
把还没解决的问题归约到已经解决的问题上 用已经解决的问题去解决还没解决的问题 密码学原理与实践 Page 167 > 假设我们已经存在一个解决问题 A 的算法 一个A到B的图灵归约即利用构造一个解决问题B的算法, 并且是多项式时间的. 这篇文章译自reductions-and-jokes > > 一个物理学家和一个数学家正坐在教师休息室里。突然间，休息室里的咖啡机着火了。物理学家就拿了一个垃圾桶，把里面的垃圾清空，跑到水池前，给垃圾桶灌满水，随后扑灭了火。由于这个咖啡机着过一次火了，大家都同意把垃圾桶装满水放在这个咖啡机旁边。 > 第二天，同样的两个人又坐在同样的休息室里，咖啡机又一次着火了。这一次，数学家站了起来，把装满水的垃圾桶拿了起来，把里面的水倒掉，又放了一些垃圾在里面，交给了物理学家。这样就把问题归约到了一个之前已经解决过的问题上。 > 虽然这个笑话是讽刺数学家的，但确实很好地解释了归约这个概念。其想法很简单：我们现在遇到了个问题，可以把它转化到一个某个已解决的问题上，而不是一定要直接解决这个问题。从这个意义上来说，归约其实是一种比较懒的解决问题的方式。 > Instead of putting out a fire,...