SGD算法比较

机器学习中,经常需要解决Empirical risk minimization(ERM)问题,这么晦涩的名字其实很简单,就是对于每个数据样本i定义一个损失J_i(\Vtheta}),总的损失就是

    \[J(\Vtheta}) = \frac{1}{n} \sum_i^n J_i(\Vtheta})\]

然后要找到使J(\Vtheta})最小的\Vtheta}。如SVMLogistic regression甚至分类的CNN都是属于这个问题。
这类模型通常需要使用迭代法求解(Linear regression 有闭解但考虑计算问题,一般也使用迭代法),其中梯度下降法(Gradient Descent)最常用:

    \begin{align*} \Vg_t &\gets \frac{1}{n} \sum_i^n \nabla J_{i}(\Vtheta_{t-1}) \\ \Vtheta_t & \gets \Vtheta_{t-1} - \eta \Vg_t \end{align*}

SGD

遇到数据量大的时候,很难不使用随机梯度下降法(Stochastic gradient descent, SGD)。SGD非常直观,就是随机拿一个或几个数据做个梯度下降,即

(1)   \begin{align*} \Vg_t &\gets \nabla J_{i}(\Vtheta_{t-1}) \\ \Vtheta_t & \gets \Vtheta_{t-1} - \eta \Vg_t \end{align*}

这个梯度\Vg_t是对部分数据计算所得,下面就记为\Vg_t  \gets \nabla J(\Vtheta_{t-1})\Vg_t可以看作是对真实梯度的估计,至少期望上是没有偏差的,因此在应用于凸问题时可以收敛到最优解。但是SGD有很多需要解决的问题

  • 收敛速度跟学习速率\eta关系很大,大\eta容易震荡,小的\eta收敛很慢。人为地在训练中调节是比较困难的,也难以适应数据的特征。
  • 学习速率\eta对所有的\Vtheta的特征都是一样的。事实上,应该\Vtheta中某些特征下降慢,有些快,没有考虑到稀疏性。
  • 容易陷入不太好局部最小或者鞍点。特别是在训练神经网络时,会更明显。

为此大神们设计了很多改进的算法,包括Momentum、NAG、Adagrad、RMSProp、AdaDelta、Adam….。我们一个个看过去。或者可以看这个博客


改进SGD

改进的算法实在有点多,挑几个著名的,我把这几个算法之间的进化关系(也根据出现的时间顺序)画在了一张图中。针对上述问题,主要有两种改进,一是利用物理中动量的思想,保持总的下降方向减小震荡,也比较容易地跳出不太好的局部最小。二是自动调节学习速率\eta

SGD粗略关系(看不清放大看)

不好好研究一下,实在搞不懂这些算法之间的区别。所以接下来仔细看看每个算法,比较一下优缺点。

Momentum

想象一个球从山上滚下来,刚开始速度为0,就会滚得磕磕碰碰(震荡)。经过一段时间动量(Momentum)的累加,震荡就会减少,径直往山下滚。表示为数学公式就是

(2)   \begin{align*} \Vg_t & \gets \nabla J(\Vtheta_{t-1}) \\ \Vv_t & \gets \gamma \Vv_{t-1} + \eta \Vg_t\\ \Vtheta_t & \gets \Vtheta_{t-1} - \Vv_t \end{align*}

可以看到跟(1)式相比就是当前下降的方向要与之前下降的方向加权平均。这里的\gamma一般取0.9就行了。直观上可以减少震荡,能更快的收敛。

NAG

NAG(Nesterov accelerated gradient)核心思想就是利用Momentum预测下一步的梯度,而不是使用当前的\Vtheta

(3)   \begin{align*} \Vg_t & \gets \nabla J(\Vtheta_{t-1} - \gamma \Vv_{t-1}) \\ \Vv_t & \gets \gamma \Vv_{t-1} + \eta \Vg_t\\ \Vtheta_t &\gets \Vtheta_{t-1} - \Vv_t \end{align*}

看出玄机没,在计算\Vg_t的时候使用的不是\Vtheta_{t-1}而是在\Vtheta_{t-1}的基础上再前进\gamma \Vv_{t-1},相当于利用当前的Momentum对下一步将走到哪进行了预测。更详细的介绍可以看这里

AdaGrad

接下来是关于学习速率的——通过算法让学习速率的选择更加容易,或者说是Adaptive Gradient。AdaGrad利用以前的梯度信息\sum_{i=1}^t \Vg_{i,j}^2判断对应的特征j是否经常被更新。因此对稀疏的数据尤其适合。写成向量形式如下:

(4)   \begin{align*} \Vg_t & \gets \nabla J(\Vtheta_{t-1}) \\ G_t &\gets G_t + \Vg_t \odot \Vg_t \\ \Vtheta_t & \gets \Vtheta_{t-1} - \frac{\eta}{\sqrt{G_t + \epsilon}} \odot \Vg_t \end{align*}

注意其中的element-wise操作,为了防止除零,\epsilon取个小量如1e-8。一般\eta取个0.01就不用管了。
在这里停顿,思考2分钟,尝试发现问题。

G_t是递增的,而且可能是比较快的递增,然后就会导致\frac{\eta}{\sqrt{G_t + \epsilon}}很小趋向于0,最后\Vtheta就不会更新了。还有就是,最开始的梯度有必要对很久以后的更新产生影响吗?

但AdaGrad的意义是非凡的,这里这样做的考虑可能是因为证明收敛更容易(见AdaGrad论文,40页我看不下去)。为了更加实用,于是就有了下面站在巨人肩膀上的算法。

RMSProp

这个算法不要太简单。是Hinton在课上提到的,甚至没有发表。RMSProp就是解决AdaGrad中学习速率趋向0的问题的。来看看如何简单。

(5)   \begin{align*} \Vg_t & \gets \nabla J(\Vtheta_{t-1}) \\ G_t &\gets \gamma G_t + (1-\gamma) \Vg_t \odot \Vg_t \\ \Vtheta_t & \gets \Vtheta_{t-1} - \frac{\eta}{\sqrt{G_t + \epsilon}} \odot \Vg_t \end{align*}

对比(4)式,多了对累计的信息的一个指数衰减(\gamma取0.9),AdaGrad的问题就没了。相对AdaGrad,不存在学习速率趋向0的问题,这里的学习速率\eta就可以取小一点如0.001

AdaDelta

AdaDelta也可以解决AdaGrad的问题,虽然经常看成与RMSProp类似的,我感觉AdaDelta更高级点,因为它连初始的学习速率都不用设置,AdaDelta有时相对比较慢。更新如下:

(6)   \begin{align*} \Vg_t & \gets \nabla J(\Vtheta_{t-1}) \\ G_t & \gets \gamma G_t + (1-\gamma) \Vg_t \odot \Vg_t \\ \Delta \Vtheta_t & \gets - \frac{\sqrt{\Delta_{t-1} + \epsilon}}{\sqrt{G_t + \epsilon}} \odot \Vg_t \\ \Vtheta_t & \gets \Vtheta_{t-1} + \Delta \Vtheta_t \\ \Delta_t & \gets \gamma \Delta_{t-1} + (1-\gamma) \Delta\Vtheta_t \odot \Delta \Vtheta_t \end{align*}

对比(5)式,可以发现AdaDelta用\sqrt{\Delta_{t-1} + \epsilon}来估计学习速率。这里的\gamma可以取个0.95。直观来说,就是利用之前的步长们\Delta\Vtheta_t估计下一步的步长,好像很有道理。“更有道理的是,SGD, Momentum或者AdaGrad更新时单位是不对的,或者说我们赋予了\eta一个单位。看(1)式,\Vg_t的单位是\frac{1}{\Vtheta}的单位(假设J没有单位,存疑),用它来更新\Vtheta单位可能就不对。而AdaDelta就没有这个问题\frac{\Delta\Vtheta}{ \frac{\Delta J}{\Delta\Vtheta}} \Vg_t \propto \Delta\Vtheta。”这段存疑,有兴趣的可以看AdaDelta论文

Adam

神器,相见恨晚,好快。我用了之后这种反应。首先Adam利用了AdaGrad和RMSProp在稀疏数据上的优点。对初始化的偏差的修正也让Adam表现的更好。为什么叫Adam呢,因为它是adaptive estimates of lower-order moments(我没理解moments是什么意思,应该是数学里面的moments),对1阶moments(mean)和2阶moments(variance)进行自适应调整。为什么能对初始化的偏差进行修正(Initialization Bias Correction),可以看Adam论文,我有一步没搞清楚。Adam的更新算是最复杂的了:

(7)   \begin{align*} \Vg_t &\gets \nabla J(\Vtheta_{t-1}) \\ \Vm_t & \gets \beta_1 \Vm_{t-1} + (1-\beta_1) \Vg_t \\ G_t & \gets \gamma G_t + (1-\gamma) \Vg_t \odot \Vg_t \\ \alpha & \gets \eta \frac{\sqrt{1-\gamma^t}}{1-\beta^t} \\ \Vtheta_t & \gets \Vtheta_{t-1} - \alpha \frac{\Vm_t}{\sqrt{G_t + \epsilon}} \end{align*}

与论文中的有所不同,我已经写成高效的形式。\beta_1取个0.9(可能需要衰减),\gamma取个0.999\eta取个0.001有时也要来个衰减,如\eta_t = \frac{\eta}{\sqrt{t}}。在复杂优化问题上,调参真的需要经验。但相对其他来说,Adam真的快很多,很多deep learning的优化问题都用Adam。
除了Adam,作者还给出了Adamax这一变种,有兴趣可以看论文。还有加了Nesterov的Adam,NAdam


Python实现

“纸上谈兵终觉浅”,稍微实现一下是必须的,就会发现理解上的不足。网上有很多实现,比如Keras的、Tensorflow的。我实现的应该很简单粗暴,都能看懂,代码见Github(不能保证完全正确),实现logistic regression和MLP的代码都是从Theano的教程的网站获得。当然实验数据用的是机器学习中的果蝇——mnist。

效果对比

跑一个循环所需的时间还是有差别的,但差别不大,可以自己尝试。我分别在logistic regression(凸问题)和MLP上跑了一遍。为了看得清楚,我把cost的曲线光滑了一下,效果如下图所示。

 

performance on logistic regression
performance on logistic regression
performance on MLP
performance on MLP

在这两个模型上,momentum和NAG都表现得差不多,不知道是不是我的实现有问题。Adam和Adamax都算后来居上,反正表现很好。对比AdaGrad和RMSProp,就可以发现AdaGrad到后面收敛慢的问题。AdaDelta最开始下降比较慢,因为人为没有指定学习速率,在MLP上至少比SGD好。我发现是\epsilon的问题,把AdaDelta的\epsilon1e^{-8}改到1e^{-6}表现好很多。 SGD在这两个模型上都能正确收敛,而且不慢,所以不要小瞧SGD。容易看出,算法在不同模型上表现并不一样,跟超参数学习速率\eta等也有关系,不能一概而论,也不要问什么算法最好这种问题,就像女友一样,只有最合适的没有最好的。


总结

虽然针对不同的任务,应该尝试不同的优化算法。我觉得实在不知道用什么就试试Adam。但是在训练过程中自己调整一下学习速率对于复杂优化目标是必要的(个人观点),比如一个epoch乘以0.5啥的。这就得靠经验了。别以为最普通的SGD不行,还是会被很多人使用,因为谁都不知道训练复杂模型的过程中会发生什么,而SGD是最能保证收敛的。

写了3天,好累。


参考

懒人秘籍

文本处理

统计句长并排序:

替换上条指令中某些字符,参考

比较不可见字符,有些时候diff输出是一样的(因为空格的关系)

重排两个对应文件

查询ascii


安全相关

生成随机密码:

umask设置在sudo时不继承,否则当普通用户设置为umask 0077的时候,使用sudo创建的文件,普通用户不能读。(pip的一个大坑)

整人,fork bomb感觉这个威力更大

 


系统管理

定期运行某个脚本,且在开机后马上运行。比如运行翻墙的shadowsocks就很必要。最方便是用crontab:

包管理


生活美好

除scp,rsyn,sshfs这类,更帅的在主机间传输文件(具体):

ssh仅运行一条命令(具体

在shell的一行里运行多条命令(详细


疑惑解答

各种括号的含义(参考stackoverflow

 

装机

 

待续。

字符级机器翻译

最近利用神经网络的机器翻译很火,我认为NMT(Neural machine translation)能有所发展的原因有以下几点:

  1. 数据丰富,WMT15算是与ImageNet同样量级的数据,是训练大型神经网络所必须的。
  2. Bahdanau提出的Attention关系将机器翻译的性能推进一大步。
  3. 很明显能产生经济效益,市场巨大。
  4. 存在很多问题,即研究前景。毕竟相对CNN给图像识别带来的巨大提升,NMT的提升并不是很明显。

我针对的是其中的一个问题:规避大词典。原来都是先把一个数据集中所有单词找出来,把最常用的一些(如90%)做成一个大词典,显然这是冗余的,words和word完全没必要区分。动不动就是50K的单词表,非常耗内存,在像Czech这类语言上更加不行。关键是冗余不优雅。很多研究者都注意到这个问题:

  • subword,就是统计一下符号的频率,如“est”可能是一个符号,能组成“w est,b est”等词,因此称为subword。我觉得还是不够自然,而且效果并不是很好。
  • Hybrid Word-Character Models,相当于把未知的词训练成RNN小单元,据说华为很早就申请专利了。我表示,不能有word。
  • Junyoung Chung提出的不需要显式分隔的模型。提出bi-scale的RNN,我觉得很有意思,但我有个疑问,这跟base的RNN有什么区别?论文中也显示,确实差不多。我不知道为什么性能那么好。由于没有训练时间、训练所用内存等更多信息我无法作出判断。
  • 还有Wang Ling提出的,但是完全不是NMT,需要借助IBM model来对齐和分层训练,而且效果不好。

综上,利用RNN编码一个单词是比较合理自然的想法。可以说人人都能想到,关键是给出高效可行的实现。我实现了个高效纯字符级的机器翻译——Deep Character-Level Neural Machine Translation(DCNMT)。但是有个缺点,需要知道分隔符,也就是空格。不要太苛刻了,对于人来说,阅读“itisalsomoredifficultforhumantoreadwithoutthedelimiter”这种也是不方便的。而且对于中文日文这种没有分隔符的语言,没有必要使用大词典,直接上字符级,因为句子短啊,不存在训练难的问题。所以先将就着用吧。总得来说,DCNMT有几个优点:

  1. 所需训练循环周期比词级的少,在EN-FR上,只要遍历4次数据就差不多了,而词级大概要5次,这很容易get。但是因为更新速度慢一点,导致所花时间差不多。
  2. 内存用的不多。但还是很多,因为theano为了计算快,RNN的中间结果是缓存的,导致有5个RNN的DCNMT用了很多内存(跟词级的差不多)。但这容易解决,见chen的paper还有deepmind的一篇
  3. 能翻译错拼的单词,在论文中我只给出了几个例子,后续给出定量分析。我觉得这是一个diǎo点。

详见论文(An Efficient Character-Level Neural Machine Translation),我也不玩虚的,代码和训好的模型都在github上,反正我也没有毕业问题,管他能不能发呢。

总的架构看图:

我也很佩服自己,怎么能写出这么复杂结构的代码,写完之后改了3个bug(我太tm diǎo了)。多亏了巨人Bahdanau等写的好框架Blocksexamples。我的偶像啊!很高兴,他也star了我的实现。仔细看,有5个RNN子模型,其实跟bi-scale思想类似,先把组成词的字符用RNN编码后,只向上传最后的编码(相当与词级模型的embedding),而不是原来的全部(字符的embedding),因此能节约Encoder和Decoder的内存,也容易训练。 整个流程应该很清楚吧,不清楚可以看论文。。。

训练模型

被爱可可老师发到微博之后,关注的人一下子多了点,有点诚惶诚恐。我觉得很多哥们会在训练的时候遇到问题。如有哥们遇到数据集问题,有哥们遇到版本问题(TypeError: __init__() got an unexpected keyword argument ‘children’)。这是我写这篇博客的原因,我希望能实现更好的实用的模型。几个注意点:

  1. 必须先手动下载对应的数据啊,就在wmt15上,还可能要对validation set和test set做一些处理。可以先选数据量小如en-fi的测试测试,一测就是1周。然后就方便了运行Github仓库中的train.sh就行了。
  2. 务必保持库的更新啊,Blocks更新还算快的,API随时改。我会尽量与最新保持兼容,而不兼顾老版本。
  3. 如果还有问题,请在评论中提问。

测试模型

我训练了几个模型,由于机器和时间受限,没来得及训练其他模型,详见论文github。我希望有人能帮忙训练更深的模型。我不知道这个模型的上限是多少。

如果对机器翻译不敢兴趣,也可以从中学点什么。这个代码中,用了GRU,stacked GRU,stacked Bidirectional GRU以及GRU的变种,关于RNN的几乎的用到了(苦笑)。还有关键的Attention,虽然有点复杂。

欢迎提问,以及改善这个模型。机器翻译很有意义,所以想能做点什么。