/
optimization_for_training_deep_models.tex
1924 lines (1557 loc) · 125 KB
/
optimization_for_training_deep_models.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
% !Mode:: "TeX:UTF-8"
% Translator: Yujun Li
\chapter{\glsentrytext{deep_model}中的优化}
\label{chap:optimization_for_training_deep_models}
% 267 head
\gls{DL}算法在许多情况下都涉及到优化。
例如,模型中的进行推断(如\,\glssymbol{PCA})涉及到求解优化问题。
我们经常使用解析优化去证明或设计算法。
在\gls{DL}涉及到的诸多优化问题中,最难的是\gls{NN}训练。
甚至是用几百台机器投入几天到几个月来解决单个\gls{NN}训练问题,也是很常见的。
因为这其中的优化问题很重要,代价也很高,因此研究者们开发了一组专门为此设计的优化技术。
本章会介绍\gls{NN}训练中的这些优化技术。
% 267 mid
如果你不熟悉基于梯度优化的基本原则,我们建议回顾\chapref{chap:numerical_computation}。
该章简要概述了一般的\gls{nume_optimization}。
本章主要关注这一类特定的优化问题:寻找\gls{NN}上的一组参数$\Vtheta$,它能显著地降低\gls{cost_function} $J(\Vtheta)$,该\gls{cost_function}通常包括整个\gls{training_set}上的性能评估和额外的\gls{regularization}项。
% 267 mid
首先,我们会介绍在\gls{ML}任务中作为训练算法使用的优化与纯优化有哪些不同。
接下来,我们会介绍导致\gls{NN}优化困难的几个具体挑战。
然后,我们会介绍几个实用算法,包括优化算法本身和初始化参数的策略。
更高级的算法能够在训练中自适应调整\gls{learning_rate},或者使用\gls{cost_function}二阶导数包含的信息。
最后,我们会介绍几个将简单优化算法结合成高级过程的优化策略,以此作为总结。
% 268 head
\section{学习和纯优化有什么不同}
\label{sec:how_learning_differs_from_pure_optimization}
用于\gls{deep_model}训练的优化算法与传统的优化算法在几个方面有所不同。
\gls{ML}通常是间接作用的。
在大多数\gls{ML}问题中,我们关注某些性能度量$P$,其定义于\gls{test_set}上并且可能是不可解的。
因此,我们只是间接地优化$P$。
我们希望通过降低\gls{cost_function} $J(\Vtheta)$来提高$P$。
这一点与纯优化不同,纯优化最小化目标$J$本身。
训练\gls{deep_model}的优化算法通常也会包括一些针对\gls{ML}\gls{objective_function}的特定结构进行的特化。
% 268 mid
通常,\gls{cost_function}可写为\gls{training_set}上的平均,如
\begin{equation}
\label{eq:8.1}
J(\Vtheta) = \SetE_{(\RVx, \RSy) \sim\hat{p}_\text{data}} L(f(\Vx ; \Vtheta), y), % ??
\end{equation}
其中$L$是每个样本的\gls{loss_function},$f(\Vx;\Vtheta)$是输入$\Vx$时所预测的输出,$\hat{p}_{\text{data}}$是\gls{empirical_distribution}。
\gls{supervised_learning}中,$y$是目标输出。
在本章中,我们会介绍不带\gls{regularization}的\gls{supervised}学习,$L$的变量是$f(\Vx;\Vtheta)$和$y$。
不难将这种\gls{supervised_learning}扩展成其他形式,如包括$\Vtheta$或者$\Vx$作为参数,或是去掉参数$y$,以发展不同形式的\gls{regularization}或是\gls{unsupervised_learning}。
% 268 mid
\eqnref{eq:8.1}定义了\gls{training_set}上的\gls{objective_function}。
通常,我们更希望最小化取自\emph{\gls{DGD}}\,$p_{\text{data}}$的期望,而不仅仅是有限\gls{training_set}上的对应\gls{objective_function}:
\begin{equation}
\label{eq:8.2}
J^*(\Vtheta) = \SetE_{(\RVx, \RSy) \sim p_\text{data}} L(f(\Vx ;\Vtheta),y). % ??
\end{equation}
% 268 end
\subsection{\glsentrytext{empirical_risk_minimization}}
\label{sec:empirical_risk_minimization}
\gls{ML}算法的目标是降低\eqnref{eq:8.2}所示的期望\gls{generalization_error}。
这个数据量被称为\firstgls{risk}。
在这里,我们强调该期望取自真实的\gls{underlying}分布$p_{\text{data}}$。
如果我们知道了真实分布$p_{\text{data}}(\Vx, y)$,那么最小化风险变成了一个可以被优化算法解决的优化问题。
然而,我们遇到的\gls{ML}问题,通常是不知道$p_\text{data}(\Vx, y)$,只知道\gls{training_set}中的样本。
% 269 head
将\gls{ML}问题转化回一个优化问题的最简单方法是最小化\gls{training_set}上的期望损失。
这意味着用\gls{training_set}上的\gls{empirical_distribution}\,$\hat{p}(\Vx,y)$替代真实分布$p(\Vx,y)$。
现在,我们将最小化\firstgls{empirical_risk}:
\begin{equation}
\label{eq:8.3}
\SetE_{\RVx, \RSy \sim \hat{p}_\text{data}} [L(f(\Vx ; \Vtheta), y)] % ?? \RVx
= \frac{1}{m} \sum_{i=1}^m L( f(\Vx^{(i)}; \Vtheta), y^{(i)}) ,
\end{equation}
其中$m$表示训练样本的数目。
% 269 mid
基于最小化这种平均\gls{training_error}的训练过程被称为\firstgls{empirical_risk_minimization}。
在这种情况下,\gls{ML}仍然和传统的直接优化很相似。
我们并不直接最优化\gls{risk},而是最优化\gls{empirical_risk},希望也能够很大地降低\gls{risk}。
一系列不同的理论构造了一些条件,使得在这些条件下真实\gls{risk}的期望可以下降不同的量。
% 269 mid
然而,\gls{empirical_risk_minimization}很容易导致\gls{overfitting}。
高\gls{capacity}的模型会简单地记住\gls{training_set}。
在很多情况下,\gls{empirical_risk_minimization}并非真的可行。
最有效的现代优化算法是基于\gls{GD}的,但是很多有用的\gls{loss_function},如$0-1$损失,没有有效的导数(导数要么为零,要么处处未定义)。
这两个问题说明,在\gls{DL}中我们很少使用\gls{empirical_risk_minimization}。
反之,我们会使用一个稍有不同的方法,我们真正优化的目标会更加不同于我们希望优化的目标。
% 269 end
\subsection{\glsentrytext{surrogate_loss_function}和\glsentrytext{early_stopping}}
\label{sec:surrogate_loss_functions_and_early_stopping}
% 269 end
有时,我们真正关心的\gls{loss_function}(比如分类误差)并不能被高效地优化。
例如,即使对于\gls{linear_classifier}而言,精确地最小化$0-1$损失通常是不可解的(复杂度是输入维数的指数级别)\citep{Marcotte-92}。
在这种情况下,我们通常会优化\firstgls{surrogate_loss_function}。
\gls{surrogate_loss_function}作为原目标的代理,还具备一些优点。
例如,正确类别的负对数似然通常用作$0-1$损失的替代。
负对数似然允许模型估计给定样本的类别的条件概率,如果该模型效果好,那么它能够输出期望最小分类误差所对应的类别。
% 270 head
在某些情况下,\gls{surrogate_loss_function}比原函数学到的更多。
例如,使用对数似然替代函数时,在\gls{training_set}上的$0-1$损失达到$0$之后,\gls{test_set}上的$0-1$损失还能持续下降很长一段时间。
这是因为即使$0-1$损失期望是零时,我们还能拉开不同类别的距离以改进分类器的鲁棒性,获得一个更强壮的、更值得信赖的分类器,从而,相对于简单地最小化\gls{training_set}上的平均$0-1$损失,它能够从训练数据中抽取更多信息。
% 270 head
一般的优化和我们用于训练算法的优化有一个重要不同:训练算法通常不会停止在\gls{local_minimum}。
反之,\gls{ML}通常优化\gls{surrogate_loss_function},但是在基于\gls{early_stopping}(\secref{sec:early_stopping})的收敛条件满足时停止。
通常,\gls{early_stopping}使用真实\gls{underlying}\gls{loss_function},如\gls{validation_set}上的$0-1$损失,并设计为在\gls{overfitting}发生之前终止。
与纯优化不同的是,\gls{early_stopping}时\gls{surrogate_loss_function}仍然有较大的导数,而纯优化终止时导数较小。
% 270 mid
\subsection{\gls{batch}算法和\gls{minibatch}算法}
\label{sec:batch_and_minibatch_algorithms}
\gls{ML}算法和一般优化算法不同的一点是,\gls{ML}算法的\gls{objective_function}通常可以分解为训练样本上的求和。
%\gls{ML}优化算法通常使用整个\gls{cost_function}中的一部分项去更新其参数。
\gls{ML}中的优化算法在计算参数的每一次更新时通常仅使用整个\gls{cost_function}中一部分项来估计\gls{cost_function}的期望值。
% 270 mid
例如,\gls{maximum_likelihood_estimation}问题可以在对数空间中分解成各个样本的总和:
\begin{equation}
\label{eq:8.4}
\Vtheta_{\text{ML}} = \underset{\Vtheta}{\argmax} \sum_{i=1}^m
\log p_{\text{model}} (\Vx^{(i)}, y^{(i)}; \Vtheta) .
\end{equation}
% 270 mid
最大化这个总和等价于最大化\gls{training_set}在\gls{empirical_distribution}上的期望:
\begin{equation}
\label{eq:8.5}
J(\Vtheta) = \SetE_{\RVx, \RSy \sim\hat{p}_\text{data}}
\log p_{\text{model}} (\Vx,y ; \Vtheta) .
\end{equation}
% 270 end
优化算法用到的\gls{objective_function}$J$中的大多数属性也是\gls{training_set}上的期望。
例如,最常用的属性是梯度:
\begin{equation}
\label{eq:8.6}
\nabla_{\Vtheta} J(\Vtheta) = \SetE_{\RVx, \RSy \sim\hat{p}_{\text{data}}}
\nabla_{\Vtheta} \log p_{\text{model}} (\Vx,y; \Vtheta) .
\end{equation}
% 271 head
准确计算这个期望的计算代价非常大,因为我们需要在整个数据集上的每个样本上评估模型。
在实践中,我们可以从数据集中随机采样少量的样本,然后计算这些样本上的平均值。
% 271 head
回想一下,$n$个样本均值的\gls{standard_error}(\eqnref{eq:5.46})是$\sigma/\sqrt{n}$,其中$\sigma$是样本值真实的\gls{standard_deviation}。
分母$\sqrt{n}$表明使用更多样本来估计梯度的方法的回报是低于线性的。
比较两个假想的梯度计算,一个基于$100$个样本,另一个基于$10,000$个样本。
后者需要的计算量是前者的$100$倍,但却只降低了$10$倍的均值\gls{standard_error}。
如果能够快速地计算出梯度估计值,而不是缓慢地计算准确值,那么大多数优化算法会收敛地更快(就总的计算量而言,而不是指更新次数)。
% 271 mid
另一个促使我们从小数目样本中获得梯度的统计估计的动机是\gls{training_set}的冗余。
在最坏的情况下,\gls{training_set}中所有的$m$个样本都是彼此相同的拷贝。
基于采样的梯度估计可以使用单个样本计算出正确的梯度,而比原来的做法少花了$m$倍时间。
实践中,我们不太可能真的遇到这种最坏情况,但我们可能会发现大量样本都对梯度做出了非常相似的贡献。
使用整个\gls{training_set}的优化算法被称为\firstgls{batch}或\firstgls{deterministic}梯度算法,因为它们会在一个大\gls{batch}中同时处理所有样本。
这个术语可能有点令人困惑,因为这个词``\gls{batch}''也经常被用来描述\gls{minibatch}\gls{SGD}算法中用到的\gls{minibatch}样本。
通常,术语``\gls{batch}\gls{GD}''指使用全部\gls{training_set},而术语``\gls{batch}''单独出现时指一组样本。
例如,我们普遍使用术语``\gls{batch}大小''表示\gls{minibatch}的大小。
% 271 mid
每次只使用单个样本的优化算法有时被称为\firstgls{stochastic}或者\firstgls{online}算法。
术语``\gls{online}''通常是指从连续产生样本的数据流中抽取样本的情况,而不是从一个固定大小的\gls{training_set}中遍历多次采样的情况。
% 271 end
% 272 head
大多数用于\gls{DL}的算法介于以上两者之间,使用一个以上,而又不是全部的训练样本。
传统上,这些会被称为\firstgls{minibatch}或\firstgls{minibatch_stochastic}方法 ,现在通常将它们简单地称为\firstgls{stochastic}方法。
随机方法的典型示例是\gls{SGD},这将在\secref{sec:stochastic_gradient_descent_chap8}中详细描述。
% 272 mid
\gls{minibatch}的大小通常由以下几个因素决定:
\begin{itemize}
\item 更大的\gls{batch}会计算更精确的梯度估计,但是回报却是小于线性的。
\item 极小\gls{batch}通常难以充分利用多核架构。
这促使我们使用一些绝对最小\gls{batch},低于这个值的小\gls{batch}处理不会减少计算时间。
\item 如果\gls{batch}处理中的所有样本可以并行地处理(通常确是如此),那么内存消耗和\gls{batch}大小会正比。
对于很多硬件设施,这是\gls{batch}大小的限制因素。
\item 在某些硬件上使用特定大小的数组时,运行时间会更少。
尤其是在使用\,\glssymbol{GPU}\,时,通常使用$2$的幂数作为\gls{batch}大小可以获得更少的运行时间。
一般,$2$的幂数的取值范围是$32$到$256$,$16$有时在尝试大模型时使用。
% 272 mid
\item
可能是由于小\gls{batch}在学习过程中加入了\gls{noise},它们会有一些\gls{regularize}效果~\citep{Wilson-2003}。
\gls{generalization_error}通常在\gls{batch}大小为$1$时最好。
因为梯度估计的高方差,小\gls{batch}训练需要较小的\gls{learning_rate}以保持稳定性。
因为降低的\gls{learning_rate}和消耗更多步骤来遍历整个\gls{training_set}都会产生更多的步骤,所以会导致总的运行时间非常大。
\end{itemize}
% 272 mid
不同的算法使用不同的方法从\gls{minibatch}中获取不同的信息。
有些算法对采样误差比其他算法更敏感,这通常有两个可能原因。
一个是它们使用了很难在少量样本上精确估计的信息,另一个是它们以放大采样误差的方式使用了信息。
仅基于梯度$\Vg$的更新方法通常相对鲁棒,并能使用较小的\gls{batch}获得成功,如$100$。
使用\gls{hessian}矩阵$\MH$,计算如$\MH^{-1}\Vg$更新的二阶方法通常需要更大的\gls{batch},如$10,000$。
这些大\gls{batch}需要最小化估计$\MH^{-1}\Vg$的波动。
假设$\MH$被精确估计,但是有\gls{poor_conditioning}数。
乘以$\MH$或是其逆会放大之前存在的误差(这个示例中是指$\Vg$的估计误差)。
即使$\MH$被精确估计,$\Vg$中非常小的变化也会导致更新值$\MH^{-1}\Vg$中非常大的变化。
当然,我们通常只会近似地估计$\MH$,因此相对于我们使用具有较差条件的操作去估计$\Vg$,更新$\MH^{-1}\Vg$会含有更多的误差。
% 273 head
% 273 head
\gls{minibatch}是随机抽取的这点也很重要。
从一组样本中计算出梯度期望的\gls{unbiased}估计要求这些样本是独立的。
我们也希望两个连续的梯度估计是互相独立的,因此两个连续的\gls{minibatch}样本也应该是彼此独立的。
很多现实的数据集自然排列,从而使得连续的样本之间具有高度相关性。
例如,假设我们有一个很长的血液样本测试结果清单。
清单上的数据有可能是这样获取的,头五个血液样本于不同时间段取自第一个病人,接下来三个血液样本取自第二个病人,再随后的血液样本取自第三个病人,等等。
如果我们从这个清单上顺序抽取样本,那么我们的每个\gls{minibatch}数据的偏差都很大,因为这个\gls{minibatch}很可能只代表着数据集上众多患者中的某一个患者。
在这种数据集中的顺序有很大影响的情况下,很有必要在抽取\gls{minibatch}样本前打乱样本顺序。
对于非常大的数据集,如数据中心含有几十亿样本的数据集,我们每次构建\gls{minibatch}样本时都将样本完全均匀地抽取出来是不太现实的。
幸运的是,实践中通常将样本顺序打乱一次,然后按照这个顺序存储起来就足够了。
之后训练模型时会用到的一组组\gls{minibatch}连续样本是固定的,每个独立的模型每次遍历训练数据时都会重复使用这个顺序。
然而,这种偏离真实随机采样的方法并没有很严重的有害影响。
不以某种方式打乱样本顺序才会极大地降低算法的性能。
% 273 mid
很多\gls{ML}上的优化问题都可以分解成并行地计算不同样本上单独的更新。
换言之,我们在计算\gls{minibatch}样本$\MX$上最小化$J(\MX)$的更新时,同时可以计算其他\gls{minibatch}样本上的更新。
这类\gls{asynchronous}并行分布式方法将在\secref{sec:large_scale_distributed_implementations}中进一步讨论。
% 273 end
\gls{minibatch}\gls{SGD}的一个有趣动机是,只要没有重复使用样本,
它将遵循着真实\emph{\gls{generalization_error}}(\eqnref{eq:8.2})的梯度。
很多\gls{minibatch}\gls{SGD}方法的实现都会打乱数据顺序一次,然后多次遍历数据来更新参数。
第一次遍历时,每个\gls{minibatch}样本都用来计算真实\gls{generalization_error}的\gls{unbiased}估计。
第二次遍历时,估计将会是\gls{biased}的,因为它重新抽取了已经用过的样本,而不是从和原先样本相同的\gls{DGD}中获取新的无偏的样本。
% 274 head
我们不难从\gls{online_learning}的情况中看出\gls{SGD}最小化\gls{generalization_error}的原因。
这时样本或者\gls{minibatch}都是从数据\firstgls{stream}中抽取出来的。
换言之,\gls{learner}好像是一个每次看到新样本的人,
每个样本$(\Vx,y)$都来自\gls{DGD}~$p_{\text{data}}(\Vx,y)$,而不是使用大小固定的\gls{training_set}。
这种情况下,样本永远不会重复;每次更新的样本是从分布$p_\text{data}$中采样获得的无偏样本。
% 274 mid
在$\Vx$和$y$是离散时,以上的等价性很容易得到。
在这种情况下,\gls{generalization_error}(\eqnref{eq:8.2})可以表示为
\begin{equation}
\label{eq:8.7}
J^*(\Vtheta) = \sum_{\Vx} \sum_y p_{\text{data}}(\Vx, y) L(f(\Vx; \Vtheta),y),
\end{equation}
上式的准确梯度为
\begin{equation}
\label{eq:8.8}
\Vg = \nabla_{\Vtheta} J^*(\Vtheta) = \sum_{\Vx} \sum_y p_{\text{data}}
(\Vx, y) \nabla_{\Vtheta} L(f(\Vx;\Vtheta),y) .
\end{equation}
在\eqnref{eq:8.5}和\eqnref{eq:8.6}中,我们已经在对数似然中看到了相同的结果;现在我们发现这一点在包括似然的其他函数$L$上也是成立的。
在一些关于$p_\text{data}$和$L$的温和假设下,在$\Vx$和$y$是连续时也能得到类似的结果。
% 274 mid
因此,我们可以从\gls{DGD}~$p_\text{data}$抽取\gls{minibatch}样本$\{ \Vx^{(1)}, \dots,\Vx^{(m)} \}$以及对应的目标$y^{(i)}$,然后计算该\gls{minibatch}上损失函数关于对应参数的梯度
\begin{equation}
\label{eq:8.9}
\hat{\Vg} = \frac{1}{m} \nabla_{\Vtheta} \sum_i L(f(\Vx^{(i)};\Vtheta),y^{(i)} ).
\end{equation}
以此获得\gls{generalization_error}准确梯度的\gls{unbiased}估计。
最后,在\gls{generalization_error}上使用\,\glssymbol{SGD}\,方法在方向$\hat{\Vg}$上更新$\Vtheta$。
% 274 end
当然,这个解释只能用于样本没有重复使用的情况。
然而,除非\gls{training_set}特别大,通常最好是多次遍历\gls{training_set}。
当多次遍历数据集更新时,只有第一遍满足\gls{generalization_error}梯度的\gls{unbiased}估计。
但是,额外的遍历更新当然会由于减小\gls{training_error}而得到足够的好处,以抵消其带来的\gls{training_error}和\gls{test_error}间差距的增加。
% -- 275 head
随着数据集的规模迅速增长,超越了计算能力的增速,
\gls{ML}应用每个样本只使用一次的情况变得越来越常见,甚至是不完整地使用\gls{training_set}。
在使用一个非常大的\gls{training_set}时,\gls{overfitting}不再是问题,而\gls{underfitting}和计算效率变成了主要的顾虑。
读者也可以参考~\cite{bottou-bousquet-2008}中关于训练样本数目增长时,\gls{generalization_error}上计算瓶颈影响的讨论。
% -- 275 mid
\section{\glsentrytext{NN}优化中的挑战}
\label{sec:challenges_in_neural_network_optimization}
优化通常是一个极其困难的任务。
传统的\gls{ML}会小心设计\gls{objective_function}和约束,以确保优化问题是凸的,
从而避免一般优化问题的复杂度。
在训练\gls{NN}时,我们肯定会遇到一般的\gls{nonconvex}情况。
即使是\gls{convex_optimization},也并非没有任何问题。
在这一节中,我们会总结几个训练\gls{deep_model}时会涉及到的主要挑战。
% -- 275 mid
\subsection{\glsentrytext{ill_conditioning}}
\label{sec:ill_conditioning}
在优化凸函数时,会遇到一些挑战。
这其中最突出的是\,\gls{hessian}\,矩阵$\MH$的\gls{ill_conditioning}。
这是\gls{nume_optimization}、\gls{convex_optimization}或其他形式的优化中普遍存在的问题,更多细节请回顾\secref{sec:beyond_the_gradient_jacobian_and_hessian_matrices}。
% -- 275 mid
\gls{ill_conditioning}问题一般被认为存在于\gls{NN}训练过程中。
\gls{ill_conditioning}体现在\gls{SGD}会``卡''在某些情况,此时即使很小的更新步长也会增加\gls{cost_function}。
% -- 275 mid
回顾\eqnref{eq:4.9},\gls{cost_function}的二阶\gls{taylor}级数展开预测\gls{GD}中的$-\epsilon\Vg$会增加
\begin{equation}
\frac{1}{2} \epsilon^2 \Vg^\top \MH\Vg - \epsilon\Vg^\top\Vg
\end{equation}
到代价中。
当$\frac{1}{2} \epsilon^2 \Vg^\top\MH\Vg$超过$\epsilon\Vg^\top\Vg$时,梯度的\gls{ill_conditioning}会成为问题。
判断\gls{ill_conditioning}是否不利于\gls{NN}训练任务,我们可以监测平方梯度范数$\Vg^\top\Vg$和$\Vg^\top \MH\Vg$。
在很多情况中,梯度范数不会在训练过程中显著缩小,但是$\Vg^\top\MH\Vg$的增长会超过一个数量级。
其结果是尽管梯度很强,学习会变得非常缓慢,因为\gls{learning_rate}必须收缩以弥补更强的\gls{curvature}。
如\figref{fig:chap8_grad_norm_increases}所示,成功训练的\gls{NN}中,梯度显著增加。
% -- 276 head
% -- 276 end
\begin{figure}[!htb]
\ifOpenSource
\centerline{\includegraphics{figure.pdf}}
\else
\centerline{\includegraphics{Chapter8/figures/grad_norm_increases_color}}
\fi
\caption{\gls{GD}通常不会到达任何类型的\gls{critical_points}。
此示例中,在用于对象检测的\gls{convolutional_network}的整个训练期间, 梯度范数持续增加。
\emph{(左)}各个梯度计算的范数如何随时间分布的散点图。
为了方便作图,每\gls{epoch}仅绘制一个梯度范数。
我们将所有梯度范数的移动平均绘制为实曲线。
梯度范数明显随时间增加,而不是如我们所期望的那样随训练过程收敛到\gls{critical_points}而减小。
\emph{(右)}尽管梯度递增,训练过程却相当成功。
\gls{validation_set}上的分类误差可以降低到较低水平。
}
\label{fig:chap8_grad_norm_increases}
\end{figure}
% -- 276 end
% -- 276 mid
尽管\gls{ill_conditioning}还存在于除了\gls{NN}训练的其他情况中,有些适用于其他情况的解决\gls{ill_conditioning}的技术并不适用于\gls{NN}。
例如,\gls{newton_method}在解决带有\gls{poor_conditioning}的\,\gls{hessian}\,矩阵的\gls{convex_optimization}问题时,是一个非常优秀的工具,
但是我们将会在以下小节中说明\gls{newton_method}运用到\gls{NN}时需要很大的改动。
% -- 276 mid
\subsection{\glsentrytext{local_minima}}
\label{sec:local_minima}
\gls{convex_optimization}问题的一个突出特点是其可以简化为寻找一个\gls{local_minimum}的问题。
任何一个\gls{local_minimum}都是\gls{global_minimum}。
有些凸函数的底部是一个平坦的区域,而不是单一的\gls{global_minimum},但该平坦区域中的任意点都是一个可以接受的解。
优化一个凸问题时,若发现了任何形式的\gls{critical_points},我们都会知道已经找到了一个不错的可行解。
% -- 277 head
对于\gls{nonconvex}函数时,如\gls{NN},有可能会存在多个\gls{local_minima}。
事实上,几乎所有的\gls{deep_model}基本上都会有非常多的\gls{local_minima}。
然而,我们会发现这并不是主要问题。
% -- 277 mid
由于\firstgls{model_identifiability}问题,\gls{NN}和任意具有多个等效参数化\gls{latent_variable}的模型都会具有多个\gls{local_minima}。
如果一个足够大的\gls{training_set}可以唯一确定一组模型参数,那么该模型被称为\gls{identifiable}。
带有\gls{latent_variable}的模型通常是不\gls{identifiable},因为通过相互交换\gls{latent_variable}我们能得到等价的模型。
例如,考虑\gls{NN}的第一层,我们可以交换单元$i$和单元$j$的传入权重向量、传出权重向量而得到等价的模型。
如果\gls{NN}有$m$层,每层有$n$个单元,那么会有$n!^m$种排列\gls{hidden_unit}的方式。
这种不可辨认性被称为\firstgls{weight_space_symmetry}。
% -- 277 mid
除了\gls{weight_space_symmetry},很多\gls{NN}还有其他导致不可辨认的原因。
例如,在任意\gls{rectified_linear}网络或者~\gls{maxout}~网络中,
我们可以将传入权重和\gls{bias_aff}扩大$\alpha$倍,然后将传出权重扩大$\frac{1}{\alpha}$倍,而保持模型等价。
这意味着,如果\gls{cost_function}不包括如\gls{weight_decay}这种直接依赖于权重而非模型输出的项,那么\gls{rectified_linear}网络或者~\gls{maxout}~网络的每一个\gls{local_minimum}都在等价的\gls{local_minima}的$(m\times n)$维双曲线上。
% -- 277 mid
这些\gls{model_identifiability}问题意味着\gls{NN}\gls{cost_function}具有非常多、甚至不可数无限多的\gls{local_minima}。
然而,所有这些由于不可辨识性问题而产生的\gls{local_minima}都有相同的\gls{cost_function}值。
因此,这些\gls{local_minima}并非是\gls{nonconvex}所带来的问题。
% -- 277 mid
如果\gls{local_minima}相比\gls{global_minimum}拥有很大的\gls{cost},\gls{local_minima}会带来很大的隐患。
我们可以构建没有\gls{hidden_unit}的小规模\gls{NN},其\gls{local_minima}的\gls{cost}比\gls{global_minimum}的\gls{cost}大很多~\citep{Sontag-cs89,Brady89,Gori-pami91}。
如果具有很大\gls{cost}的\gls{local_minima}是常见的,那么这将给基于梯度的优化算法带来极大的问题。
% -- 277 end
对于实际中感兴趣的网络,是否存在大量\gls{cost}很高的\gls{local_minima},优化算法是否会碰到这些\gls{local_minima},都是尚未解决的公开问题。
多年来,大多数从业者认为\gls{local_minima}是困扰\gls{NN}优化的常见问题。
如今,情况有所变化。
这个问题仍然是学术界的热点问题,但是学者们现在猜想,对于足够大的\gls{NN}而言,
大部分\gls{local_minima}都具有很小的\gls{cost_function},我们能不能找到真正的\gls{global_minimum}并不重要,而是需要在参数空间中找到一个\gls{cost}很小(但不是最小)的点~\citep{Saxe-et-al-ICLR13,Dauphin-et-al-NIPS2014-small,GoodfellowOptimization15,Choromanska-et-al-AISTATS2015}。
% 278 head
很多从业者将\gls{NN}优化中的所有困难都归结于\gls{local_minima}。
我们鼓励从业者要仔细分析特定的问题。
一种能够排除\gls{local_minima}是主要问题的检测方法是画出梯度范数随时间的变化。
如果梯度范数没有缩小到一个微小的值,那么该问题既不是\gls{local_minima},也不是其他形式的\gls{critical_points}。
%这种消极的测试可以排除局部极小值是造成问题的原因。
在高维空间中,很难明确证明\gls{local_minima}是导致问题的原因。
许多并非\gls{local_minima}的结构也具有很小的梯度。
% 278 mid
\subsection{高原、\glsentrytext{saddle_points}和其他平坦区域}
\label{sec:plateaus_saddle_points_and_other_flat_regions}
对于很多高维\gls{nonconvex}函数而言,\gls{local_minima}(以及\gls{maxima})事实上都远少于另一类梯度为零的点:\gls{saddle_points}。
\gls{saddle_points}附近的某些点比\gls{saddle_points}有更大的\gls{cost},而其他点则有更小的\gls{cost}。
在\gls{saddle_points}处,\gls{hessian}\,矩阵同时具有正负特征值。
位于正特征值对应的特征向量方向的点比\gls{saddle_points}有更大的\gls{cost},反之,位于负特征值对应的特征向量方向的点有更小的\gls{cost}。
我们可以将\gls{saddle_points}视为\gls{cost_function}某个横截面上的\gls{local_minimum},同时也可以视为\gls{cost_function}某个横截面上的\gls{local_maximum}。
\figref{fig:chap4_saddle_3d_color}\,给了一个示例。
% 278 mid
多类随机函数表现出以下性质:低维空间中,\gls{local_minima}很普遍。
在更高维空间中,\gls{local_minima}很罕见,而\gls{saddle_points}则很常见。
对于这类函数$f:\SetR^n \to \SetR$而言,\gls{saddle_points}和\gls{local_minima}的数目比率的期望随$n$指数级增长。
我们可以从直觉上理解这种现象——\gls{hessian}\,矩阵在\gls{local_minimum}处只有正特征值。
而在\gls{saddle_points}处,\gls{hessian}\,矩阵则同时具有正负特征值。
试想一下,每个特征值的正负号由抛硬币决定。
在一维情况下,很容易抛硬币得到正面朝上一次而获取\gls{local_minimum}。
在$n$-维空间中,要抛掷$n$次硬币都正面朝上的难度是指数级的。
具体可以参考~\cite{Dauphin-et-al-NIPS2014-small},它回顾了相关的理论工作。
% -- 278 end
很多随机函数一个惊人性质是,当我们到达\gls{cost}较低的区间时,\gls{hessian}\,矩阵的特征值为正的可能性更大。
和抛硬币类比,这意味着如果我们处于低\gls{cost}的\gls{critical_points}时,抛掷硬币正面朝上$n$次的概率更大。
这也意味着,\gls{local_minima}具有低\gls{cost}的可能性比高\gls{cost}要大得多。
具有高\gls{cost}的\gls{critical_points}更有可能是\gls{saddle_points}。
具有极高\gls{cost}的\gls{critical_points}就很可能是\gls{local_maxima}了。
% -- 279 head
以上现象出现在许多种类的随机函数中。
那么是否在\gls{NN}中也有发生呢?
\cite{Baldi89}从理论上证明,不具非线性的浅层\gls{AE}(\chapref{chap:autoencoders}中将介绍的一种将输出训练为输入拷贝的\gls{feedforward_network})只有\gls{global_minima}和\gls{saddle_points},没有\gls{cost}比\gls{global_minima}更大的\gls{local_minima}。
他们还发现这些结果能够扩展到不具非线性的更深的网络上,不过没有证明。
这类网络的输出是其输入的线性函数,但它们仍然有助于分析非线性\gls{NN}模型,因为它们的\gls{loss_function}是关于参数的\gls{nonconvex}函数。
这类网络本质上是多个矩阵组合在一起。
\cite{Saxe-et-al-ICLR13}精确解析了这类网络中完整的学习动态,表明这些模型的学习能够捕捉到许多在训练具有非线性\gls{activation_function}的\gls{deep_model}时观察到的定性特征。
\cite{Dauphin-et-al-NIPS2014-small}通过实验表明,真实的\gls{NN}也存在包含很多高\gls{cost}\gls{saddle_points}的\gls{loss_function}。
\cite{Choromanska-et-al-AISTATS2015}提供了额外的理论论点,表明另一类和\gls{NN}相关的高维随机函数也满足这种情况。
% -- 279 mid
\gls{saddle_points}激增对于训练算法来说有哪些影响呢?
对于只使用梯度信息的一阶优化算法而言,目前情况还不清楚。
\gls{saddle_points}附近的梯度通常会非常小。
另一方面,实验中\gls{GD}似乎可以在许多情况下逃离\gls{saddle_points}。
\cite{GoodfellowOptimization15}可视化了最新\gls{NN}的几个学习轨迹,\figref{fig:chap8_plot_atmu_relu_5}\,给了一个例子。
这些可视化显示,在突出的\gls{saddle_points}附近,\gls{cost_function}都是平坦的,权重都为零。
但是他们也展示了\gls{GD}轨迹能够迅速逸出该区间。
\cite{GoodfellowOptimization15}也主张,应该可以通过分析来表明连续时间的\gls{GD}会逃离而不是吸引到\gls{saddle_points},但对\gls{GD}更现实的使用场景来说,情况或许会有所不同。
% -- 279 mid
% 280 head
\begin{figure}[!htb]
\ifOpenSource
\centerline{\includegraphics{figure.pdf}}
\else
\centerline{\includegraphics{Chapter8/figures/plot_atmu_relu_5}}
\fi
\caption{\gls{NN}\gls{cost_function}的可视化。
这些可视化对应用于真实\gls{object_recognition}和\gls{NLP}任务的\gls{feedforward_neural_network}、\gls{convolutional_network}和\gls{recurrent_network}而言是类似的。
令人惊讶的是,这些可视化通常不会显示出很多明显的障碍。
大约2012年,在\gls{SGD}开始成功训练非常大的模型之前,相比这些投影所显示的\gls{NN}\gls{cost_function}的表面通常被认为有更多的\gls{nonconvex}结构。
该投影所显示的主要障碍是初始参数附近的高\gls{cost}\gls{saddle_points},但如由蓝色路径所示,\glssymbol{SGD}\,训练轨迹能轻易地逃脱该鞍点。
大多数训练时间花费在横穿\gls{cost_function}中相对平坦的峡谷,可能由于梯度中的高噪声、或该区域中~\gls{hessian}~矩阵的\gls{poor_conditioning},或者需要经过间接的弧路径绕过图中可见的高``山'' 。
图经~\citet{GoodfellowOptimization15}许可改编。
}
\label{fig:chap8_plot_atmu_relu_5}
\end{figure}
% 280 head
% -- 279 end
对于\gls{newton_method}而言,\gls{saddle_points}显然是一个问题。
\gls{GD}旨在朝``下坡''移动,而非明确寻求\gls{critical_points}。
而\gls{newton_method}的目标是寻求梯度为零的点。
如果没有适当的修改,\gls{newton_method}就会跳进一个\gls{saddle_points}。
高维空间中\gls{saddle_points}的激增或许解释了在\gls{NN}训练中为什么\gls{second_order_method}无法成功取代\gls{GD}。
\cite{Dauphin-et-al-NIPS2014-small}介绍了二阶优化的\firstgls{saddle_free_newton_method},并表明和传统算法相比有显著改进。
\gls{second_order_method}仍然难以扩展到大型\gls{NN},但是如果这类无鞍算法能够扩展的话,还是很有希望的。
% -- 280 mid
除了\gls{minima}和\gls{saddle_points},还存在其他梯度为零的点。
例如从优化的角度看与\gls{saddle_points}很相似的\gls{maxima},很多算法不会被吸引到\gls{maxima},除了未经修改的\gls{newton_method}。
和\gls{minima}一样,许多种类的随机函数的\gls{maxima}在高维空间中也是指数级稀少。
% -- 280 mid
也可能存在恒值的、宽且平坦的区域。
在这些区域,梯度和\,\gls{hessian}\,矩阵都是零。
这种退化的情形是所有\gls{nume_optimization}算法的主要问题。
在凸问题中,一个宽而平坦的区间肯定包含\gls{global_minima},但是对于一般的优化问题而言,
这样的区域可能会对应着\gls{objective_function}中一个较高的值。
% -- 280 end
\subsection{悬崖和\glsentrytext{explode_gradient}}
\label{sec:cliffs_and_exploding_gradients}
% 281 head
多层\gls{NN}通常存在像悬崖一样的斜率较大区域,如\figref{fig:chap8_cliff}所示。
这是由于几个较大的权重相乘导致的。
遇到斜率极大的悬崖结构时,梯度更新会很大程度地改变参数值,通常会完全跳过这类悬崖结构。
% 281 head
% 281 end
\begin{figure}[!htb]
\ifOpenSource
\centerline{\includegraphics{figure.pdf}}
\else
\centerline{\includegraphics{Chapter8/figures/cliff_color}}
\fi
\caption{高度非线性的\gls{DNN}或\gls{RNN}的\gls{objective_function}通常包含由几个参数连乘而导致的参数空间中尖锐非线性。
这些非线性在某些区域会产生非常大的导数。
当参数接近这样的悬崖区域时,\gls{GD}更新可以使参数弹射得非常远,可能会使大量已完成的优化工作成为无用功。
图经 \citet{Pascanu+al-ICML2013-small}许可改编。}
\label{fig:chap8_cliff}
\end{figure}
% 281 end
不管我们是从上还是从下接近悬崖,情况都很糟糕,但幸运的是我们可以用使用\secref{sec:clipping_gradients}介绍的启发式\firstgls{gradient_clipping}来避免其严重的后果。
其基本想法源自梯度并没有指明最佳步长,只说明了在无限小区域内的最佳方向。
当传统的\gls{GD}算法提议更新很大一步时,启发式\gls{gradient_clipping}会干涉来减小步长,从而使其不太可能走出梯度近似为\gls{steepest}方向的悬崖区域。
悬崖结构在\gls{RNN}的\gls{cost_function}中很常见,因为这类模型会涉及到多个因子的相乘,其中每个因子对应一个\gls{time_step}。
因此,长期时间序列会产生大量相乘。
% 281 mid
% 281 end
\subsection{\glsentrytext{long_term_dependency}}
\label{sec:long_term_dependencies}
当\gls{computational_graph}变得极深时,\gls{NN}优化算法会面临的另外一个难题就是\gls{long_term_dependency}问题——由于变深的结构使模型丧失了学习到先前信息的能力,让优化变得极其困难。
深层的\gls{computational_graph}不仅存在于\gls{feedforward_network},还存在于之后介绍的\gls{recurrent_network}中(在\chapref{chap:sequence_modeling_recurrent_and_recursive_nets}中描述)。
因为\gls{recurrent_network}要在很长时间序列的各个时刻重复应用相同操作来构建非常深的计算图,并且模型参数共享,这使问题更加凸显。
% 282 head
例如,假设某个\gls{computational_graph}中包含一条反复与矩阵$\MW$相乘的路径。
那么$t$步后,相当于乘以$\MW^t$。
假设$\MW$有特征值分解$\MW = \MV \text{diag}(\Vlambda) \MV^{-1}$。
在这种简单的情况下,很容易看出
\begin{equation}
\MW^t = (\MV \text{diag}(\Vlambda) \MV^{-1})^t = \MV\text{diag}(\Vlambda)^t \MV^{-1}.
\end{equation}
当特征值$\lambda_i$不在$1$附近时,若在量级上大于$1$则会爆炸;若小于$1$时则会消失。
\firstgls{vanish_explode_gradient}是指该\gls{computational_graph}上的梯度也会因为$\text{diag}(\Vlambda)^t$大幅度变化。
\gls{vanish_gradient}使得我们难以知道参数朝哪个方向移动能够改进\gls{cost_function},而\gls{explode_gradient}会使得学习不稳定。
之前描述的促使我们使用\gls{gradient_clipping}的悬崖结构便是\gls{explode_gradient}现象的一个例子。
% 282 mid
此处描述的在各\gls{time_step}重复与$\MW$相乘非常类似于寻求矩阵$\MW$的最大特征值及对应特征向量的\firstgls{power_method}。
从这个观点来看,$\Vx^\top\MW^t$最终会丢弃$\Vx$中所有与$\MW$的主特征向量正交的成分。
% 282 mid
\gls{recurrent_network}在各\gls{time_step}上使用相同的矩阵$\MW$,而\gls{feedforward_network}并没有。
所以即使使用非常深层的\gls{feedforward_network},也能很大程度上有效地避免\gls{vanish_explode_gradient}~\citep{Sussillo14}。
% 282 mid
在更详细地描述\gls{recurrent_network}之后,我们将会在\secref{sec:the_challenge_of_long_term_dependencies}进一步讨论\gls{recurrent_network}训练中的挑战。
% 282 mid
\subsection{非精确梯度}
\label{sec:inexact_gradients}
大多数优化算法的先决条件都是我们知道精确的梯度或是\,\gls{hessian}\,矩阵。
在实践中,通常这些量会有\gls{noise},甚至是\gls{biased}的估计。
几乎每一个\gls{DL}算法都需要基于采样的估计,至少使用训练样本的\gls{minibatch}来计算梯度。
% 282 end
在其他情况,我们希望最小化的\gls{objective_function}实际上是难以处理的。
当\gls{objective_function}不可解时,通常其梯度也是难以处理的。
在这种情况下,我们只能近似梯度。
这些问题主要出现在第三部分中更高级的模型中。
例如,\gls{contrastive_divergence}是用来近似\gls{BM}中难以处理的对数似然梯度的一种技术。
% 283 head
各种\gls{NN}优化算法的设计都考虑到了梯度估计的缺陷。
我们可以选择比真实\gls{loss_function}更容易估计的\gls{surrogate_loss_function}来避免这个问题。
% 283 mid
\subsection{局部和全局结构间的弱对应}
\label{sec:poor_correspondence_between_local_and_global_structure}
迄今为止,我们讨论的许多问题都是关于\gls{loss_function}在单个点的性质——若$J(\Vtheta)$是当前点$\Vtheta$的\gls{poor_conditioning},或者$\Vtheta$在悬崖中,或者$\Vtheta$是一个下降方向不明显的\gls{saddle_points},那么会很难更新当前步。
% 283 mid
如果该方向在局部改进很大,但并没有指向\gls{cost}低得多的遥远区域,那么我们有可能在单点处克服以上所有困难,但仍然表现不佳。
% 283 mid
\cite{GoodfellowOptimization15}认为大部分训练的运行时间取决于到达解决方案的轨迹长度。
如\figref{fig:chap8_plot_atmu_relu_5}所示,学习轨迹将花费大量的时间探寻一个围绕山形结构的宽弧。
% 283 mid
大多数优化研究的难点集中于训练是否找到了\gls{global_minimum}、\gls{local_minimum}或是\gls{saddle_points},但在实践中\gls{NN}不会到达任何一种\gls{critical_points}。
\figref{fig:chap8_grad_norm_increases}表明\gls{NN}通常不会到达梯度很小的区域。
甚至,这些\gls{critical_points}不一定存在。
例如,\gls{loss_function} $-\log p(y\mid\Vx;\Vtheta)$ 可以没有\gls{global_minimum},而是当随着训练模型逐渐稳定后,渐近地收敛于某个值。
对于具有离散的$y$和~\ENNAME{softmax}~分布$p(y\mid\Vx)$的分类器而言,若模型能够正确分类\gls{training_set}上的每个样本,则负对数似然可以无限趋近但不会等于零。
同样地,实值模型$p(y\mid\Vx) = \mathcal{N}(y;f(\Vtheta),\beta^{-1})$的负对数似然会趋向于负无穷——如果$f(\Vtheta)$能够正确预测所有\gls{training_set}中的目标$y$,学习算法会无限制地增加$\beta$。
\figref{fig:chap8_bad_global}给出了一个失败的例子,即使没有\gls{local_minima}和\gls{saddle_points},该例还是不能从局部优化中找到一个良好的\gls{cost_function}值。
% 283 end
% 284 head
\begin{figure}[!htb]
\ifOpenSource
\centerline{\includegraphics{figure.pdf}}
\else
\centerline{\includegraphics{Chapter8/figures/bad_global_color}}
\fi
\caption{如果局部表面没有指向全局解,基于局部下坡移动的优化可能就会失败。
这里我们提供一个例子,说明即使在没有\gls{saddle_points}或\gls{local_minima}的情况下,优化过程会如何失败。
此例中的\gls{cost_function}仅包含朝向低值而不是\gls{minima}的渐近线。
在这种情况下,造成这种困难的主要原因是初始化在``山''的错误一侧,并且无法遍历。
在高维空间中,学习算法通常可以环绕过这样的高山,但是相关的轨迹可能会很长,并且导致过长的训练时间,如\figref{fig:chap8_plot_atmu_relu_5}所示。
}
\label{fig:chap8_bad_global}
\end{figure}
% 284 head
未来的研究需要进一步探索影响学习轨迹长度和更好地表征训练过程的结果。
% 284 mid
许多现有研究方法在求解具有困难全局结构的问题时,旨在寻求良好的初始点,而不是开发非局部范围更新的算法。
% 284 mid
\gls{GD}和基本上所有的可以有效训练\gls{NN}的学习算法,都是基于局部较小更新。
之前的小节主要集中于为何这些局部范围更新的正确方向难以计算。
我们也许能计算\gls{objective_function}的一些性质,如近似的有偏梯度或正确方向估计的方差。
在这些情况下,难以确定局部下降能否定义通向有效解的足够短的路径,但我们并不能真的遵循局部下降的路径。
\gls{objective_function}可能有诸如\gls{poor_conditioning}或不连续梯度的问题,使得梯度为\gls{objective_function}提供较好近似的区间非常小。
在这些情况下,步长为$\epsilon$的局部下降可能定义了到达解的合理的短路经,但是我们只能计算步长为$\delta \ll \epsilon$的局部下降方向。
在这些情况下,局部下降或许能定义通向解的路径,但是该路径包含很多次更新,因此遵循该路径会带来很高的计算代价。
有时,比如说当\gls{objective_function}有一个宽而平的区域,或是我们试图寻求精确的\gls{critical_points}(通常来说后一种情况只发生于显式求解\gls{critical_points}的方法,如\gls{newton_method})时,局部信息不能为我们提供任何指导。
在这些情况下,\gls{local_descent}完全无法定义通向解的路径。
在其他情况下,局部移动可能太过贪心,朝着下坡方向移动,却和所有可行解南辕北辙,如\figref{fig:chap8_bad_global}所示,或者是用舍近求远的方法来求解问题,如\figref{fig:chap8_plot_atmu_relu_5}所示。
目前,我们还不了解这些问题中的哪一个与\gls{NN}优化中的难点最相关,这是研究领域的热点方向。
% 285 head
不管哪个问题最重要,如果存在一个区域,我们遵循\gls{local_descent}便能合理地直接到达某个解,并且我们能够在该良好区域上初始化学习,那么这些问题都可以避免。
最终的观点还是建议在传统优化算法上研究怎样选择更佳的初始化点,以此来实现目标更切实可行。
% 285 mid
\subsection{优化的理论限制}
\label{sec:theoretical_limits_of_optimization}
一些理论结果表明,我们为\gls{NN}设计的任何优化算法都有性能限制\citep{Blum92,JuddBook,wolpert96no}。
通常这些结果不影响\gls{NN}在实践中的应用。
% 285 mid
一些理论结果仅适用于\gls{NN}的单元输出离散值的情况。
然而,大多数\gls{NN}单元输出光滑的连续值,使得局部搜索求解优化可行。
一些理论结果表明,存在某类问题是不可解的,但很难判断一个特定问题是否属于该类。
其他结果表明,寻找给定规模的网络的一个可行解是很困难的,
但在实际情况中,我们通过设置更多参数,使用更大的网络,能轻松找到可接受的解。
此外,在\gls{NN}训练中,我们通常不关注某个函数的精确\gls{minimum},而只关注将其值下降到足够小以获得一个良好的\gls{generalization_error}。
对优化算法是否能完成此目标进行理论分析是非常困难的。
因此,研究优化算法更现实的性能上界仍然是学术界的一个重要目标。
% 285 end
% 286 head
\section{基本算法}
\label{sec:basic_algorithms}
之前我们已经介绍了\gls{GD}(\secref{sec:gradient_based_optimization}),即沿着整个\gls{training_set}的梯度方向下降。
这可以使用\gls{SGD}很大程度地加速,沿着随机挑选的\gls{minibatch}数据的梯度下降方向,就像\secref{sec:stochastic_gradient_descent_chap5}和\secref{sec:batch_and_minibatch_algorithms}中讨论的一样。
% 286 head
\subsection{\glsentrytext{SGD}}
\label{sec:stochastic_gradient_descent_chap8}
\glsacr{SGD}及其变种很可能是一般\gls{ML}中应用最多的优化算法,特别是在\gls{DL}中。
如\secref{sec:batch_and_minibatch_algorithms}中所讨论的,按照\gls{DGD}抽取$m$个\gls{minibatch}(独立同分布的)样本,通过计算它们梯度均值,我们可以得到梯度的\gls{unbiased}估计。
% 286 mid
\algref{alg:sgd}展示了如何沿着这个梯度的估计下降。
% 286 mid
% 286 end
\begin{algorithm}[ht]
\caption{\gls{SGD}(\glssymbol{SGD})在第$k$个训练迭代的更新}
\label{alg:sgd}
\begin{algorithmic}
\REQUIRE \gls{learning_rate} $\epsilon_k$
\REQUIRE 初始参数$\Vtheta$
\WHILE{停止\gls{criterion}未满足}
\STATE 从\gls{training_set}中采包含$m$个样本$\{ \Vx^{(1)},\dots, \Vx^{(m)}\}$ 的\gls{minibatch},其中$\Vx^{(i)}$对应目标为$\Vy^{(i)}$。
\STATE 计算梯度估计: $\hat{\Vg} \leftarrow +
\frac{1}{m} \nabla_{\Vtheta} \sum_i L(f(\Vx^{(i)};\Vtheta),\Vy^{(i)})$
\STATE 应用更新:$\Vtheta \leftarrow \Vtheta - \epsilon \hat{\Vg}$
\ENDWHILE
\end{algorithmic}
\end{algorithm}
% 286 end
% 286 mid
\glssymbol{SGD}\,算法中的一个关键参数是\gls{learning_rate}。
之前,我们介绍的\,\glssymbol{SGD}\,使用固定的\gls{learning_rate}。
在实践中,有必要随着时间的推移逐渐降低\gls{learning_rate},因此我们将第$k$步迭代的\gls{learning_rate}记作$\epsilon_k$。
% 286 mid
这是因为\,\glssymbol{SGD}\,中梯度估计引入的噪声源($m$个训练样本的随机采样)并不会在\gls{minimum}处消失。
相比之下,当我们使用\gls{batch}\gls{GD}到达\gls{minimum}时,整个\gls{cost_function}的真实梯度会变得很小,之后为$\mathbf{0}$,因此\gls{batch}\gls{GD}可以使用固定的\gls{learning_rate}。
保证\,\glssymbol{SGD}\,收敛的一个充分条件是
\begin{equation}
\label{eq:8.12}
\sum_{k=1}^\infty \epsilon_k = \infty,
\end{equation}
且
\begin{equation}
\label{eq:8.13}
\sum_{k=1}^\infty \epsilon_k^2 < \infty.
\end{equation}
% 287 head
实践中,一般会线性衰减\gls{learning_rate}直到第$\tau$次迭代:
\begin{equation}
\label{eq:8.14}
\epsilon_k = (1-\alpha) \epsilon_0 + \alpha \epsilon_\tau
\end{equation}
其中$\alpha = \frac{k}{\tau}$。
在$\tau$步迭代之后,一般使$\epsilon$保持常数。
% 287 mid
\gls{learning_rate}可通过试验和误差来选取,通常最好的选择方法是监测\gls{objective_function}值随时间变化的学习曲线。
与其说是科学,这更像是一门艺术,我们应该谨慎地参考关于这个问题的大部分指导。
使用线性策略时,需要选择的参数为$\epsilon_0$,$\epsilon_\tau$,$\tau$。
通常$\tau$被设为需要反复遍历\gls{training_set}几百次的迭代次数。
通常$\epsilon_\tau$应设为大约$\epsilon_0$的$1\%$。
主要问题是如何设置$\epsilon_0$。
若$\epsilon_0$太大,学习曲线将会剧烈振荡,\gls{cost_function}值通常会明显增加。
温和的振荡是良好的,容易在训练随机\gls{cost_function}(例如使用\,\gls{dropout}\,的\gls{cost_function})时出现。
如果\gls{learning_rate}太小,那么学习过程会很缓慢。
如果初始\gls{learning_rate}太低,那么学习可能会卡在一个相当高的\gls{cost}值。
通常,就总训练时间和最终\gls{cost}值而言,最优初始\gls{learning_rate}的效果会好于大约迭代$100$次左右后最佳的效果。
因此,通常最好是检测最早的几轮迭代,选择一个比在效果上表现最佳的\gls{learning_rate}更大的\gls{learning_rate},但又不能太大导致严重的震荡。
% 287 mid
\glssymbol{SGD}\,及相关的\gls{minibatch}亦或更广义的基于梯度优化的在线学习算法,一个重要的性质是每一步更新的计算时间不依赖训练样本数目的多寡。
即使训练样本数目非常大时,它们也能收敛。
对于足够大的数据集,\glssymbol{SGD}\,可能会在处理整个\gls{training_set}之前就收敛到最终\gls{test_set}误差的某个固定容差范围内。
% 287 mid
% 287 end
研究优化算法的收敛率,一般会衡量\firstgls{excess_error} $J(\Vtheta) - \min_{\Vtheta} J(\Vtheta)$,即当前\gls{cost_function}超出最低可能\gls{cost}的量。
\glssymbol{SGD}\,应用于凸问题时,$k$步迭代后的\gls{excess_error}量级是$O(\frac{1}{\sqrt{k}})$,在强凸情况下是$O(\frac{1}{k})$。
除非假定额外的条件,否则这些界限不能进一步改进。
\gls{batch}\gls{GD}在理论上比\gls{SGD}有更好的收敛率。
然而,Cram\'er-Rao界限~\citep{Cramer-1946,Rao-1945}指出,\gls{generalization_error}的下降速度不会快于$O(\frac{1}{k})$。
\cite{bottou-bousquet-2008-small}因此认为对于\gls{ML}任务,不值得探寻收敛快于$O(\frac{1}{k})$的优化算法——更快的收敛可能对应着\gls{overfitting}。
此外,渐近分析掩盖了\gls{SGD}在少量更新步之后的很多优点。
对于大数据集,\glssymbol{SGD}\,只需非常少量样本计算梯度从而实现初始快速更新,远远超过了其缓慢的渐近收敛。
本章剩余部分介绍的大多数算法在实践中都受益于这种性质,但是损失了常数倍$O(\frac{1}{k})$的渐近分析。
我们也可以在学习过程中逐渐增大\gls{minibatch}的大小,以此权衡\gls{batch}\gls{GD}和\gls{SGD}两者的优点。
% 288 mid
了解\,\glssymbol{SGD}\,更多的信息,请查看~\cite{Bottou98}。
% 288 mid
\subsection{\glsentrytext{momentum}}
\label{sec:momentum}
虽然\gls{SGD}仍然是非常受欢迎的优化方法,但其学习过程有时会很慢。
\gls{momentum}方法~\citep{polyak1964some}旨在加速学习,特别是处理高\gls{curvature}、小但一致的梯度,或是带\gls{noise}的梯度。
\gls{momentum}算法积累了之前梯度指数级衰减的移动平均,并且继续沿该方向移动。
\gls{momentum}的效果如\figref{fig:chap8_momentum}所示。
% 288 mid
% 289 head
\begin{figure}[!htb]
\ifOpenSource
\centerline{\includegraphics{figure.pdf}}
\else
\centerline{\includegraphics{Chapter8/figures/momentum_color}}
\fi
\caption{\gls{momentum}的主要目的是解决两个问题:\gls{hessian}\,矩阵的\gls{poor_conditioning}和随机梯度的方差。
我们通过此图说明\gls{momentum}如何克服这两个问题的第一个。
等高线描绘了一个二次\gls{loss_function}(具有\gls{poor_conditioning}的\,\gls{hessian}\,矩阵)。
横跨轮廓的红色路径表示\gls{momentum}学习规则所遵循的路径,它使该函数最小化。
我们在该路径的每个步骤画一个箭头,表示\gls{GD}将在该点采取的步骤。
我们可以看到,一个\gls{poor_conditioning}的二次\gls{objective_function}看起来像一个长而窄的山谷或具有陡峭边的峡谷。
\gls{momentum}正确地纵向穿过峡谷,而普通的梯度步骤则会浪费时间在峡谷的窄轴上来回移动。
比较\figref{fig:chap4_poor_conditioning_color},它也显示了没有\gls{momentum}的\gls{GD}的行为。
}
\label{fig:chap8_momentum}
\end{figure}
% 289 head
从形式上看,\gls{momentum}算法引入了变量$\Vv$充当速度角色——它代表参数在参数空间移动的方向和速率。
速度被设为负梯度的指数衰减平均。
名称\firstgls{momentum}来自物理类比,根据牛顿运动定律,负梯度是移动参数空间中粒子的力。
\gls{momentum}在物理学上定义为质量乘以速度。
在\gls{momentum}学习算法中,我们假设是单位质量,因此速度向量$\Vv$也可以看作是粒子的\gls{momentum}。
\gls{hyperparameter}$\alpha\in[0,1)$决定了之前梯度的贡献衰减得有多快。
更新规则如下:
\begin{align}
\Vv & \leftarrow \alpha \Vv - \epsilon \nabla_{\Vtheta} \left( \frac{1}{m} \sum_{i=1}^m L(\Vf(\Vx^{(i)}; \Vtheta), \Vy^{(i)} ) \right), \\
\Vtheta & \leftarrow \Vtheta + \Vv .
\end{align}
速度$\Vv$累积了梯度元素$\nabla_{\Vtheta}( \frac{1}{m} \sum_{i=1}^m L( \Vf(\Vx^{(i)}; \Vtheta), \Vy^{(i)} ) )$。
相对于$\epsilon$,$\alpha$越大,之前梯度对现在方向的影响也越大。
带\gls{momentum}的\,\glssymbol{SGD}\,算法如\algref{alg:momentum}所示。
% 289 end
% 289 mid
\begin{algorithm}[ht]
\caption{使用\gls{momentum}的\gls{SGD}(\glssymbol{SGD})}
\label{alg:momentum}
\begin{algorithmic}
\REQUIRE \gls{learning_rate} $\epsilon$, \gls{momentum}参数 $\alpha$
\REQUIRE 初始参数 $\Vtheta$,初始速度 $\Vv$
\WHILE{没有达到停止\gls{criterion}}
\STATE 从\gls{training_set}中采包含$m$个样本$\{ \Vx^{(1)},\dots, \Vx^{(m)}\}$ 的\gls{minibatch},对应目标为$\Vy^{(i)}$。
\STATE 计算梯度估计:$\Vg \leftarrow
\frac{1}{m} \nabla_{\Vtheta} \sum_i L(f(\Vx^{(i)};\Vtheta),\Vy^{(i)})$
\STATE 计算速度更新:$\Vv \leftarrow \alpha \Vv -
\epsilon \Vg$
\STATE 应用更新:$\Vtheta \leftarrow \Vtheta + \Vv$
\ENDWHILE
\end{algorithmic}
\end{algorithm}
% 289 mid
% 289 end
之前,步长只是梯度范数乘以\gls{learning_rate}。
现在,步长取决于梯度\emph{序列}的大小和排列。
当许多连续的梯度指向相同的方向时,步长最大。
如果\gls{momentum}算法总是观测到梯度$\Vg$,那么它会在方向$-g$上不停加速,直到达到最终速度,其中步长大小为
\begin{equation}
\frac{\epsilon \norm{\Vg}}{1-\alpha} .
\end{equation}
因此将\gls{momentum}的\gls{hyperparameter}视为$\frac{1}{1-\alpha}$有助于理解。
例如,$\alpha=0.9$对应着最大速度$10$倍于\gls{GD}算法。
% 290 head
在实践中,$\alpha$的一般取值为$0.5$,$0.9$和$0.99$。
和\gls{learning_rate}一样,$\alpha$也会随着时间不断调整。
一般初始值是一个较小的值,随后会慢慢变大。
随着时间推移调整$\alpha$没有收缩$\epsilon$重要。
% 290 mid
我们可以将\gls{momentum}算法视为模拟连续时间下牛顿动力学下的粒子。
这种物理类比有助于直觉上理解\gls{momentum}和\gls{GD}算法是如何表现的。
% 290 mid
粒子在任意时间点的位置由$\Vtheta(t)$给定。
粒子会受到净力$\Vf(t)$。
该力会导致粒子加速:
\begin{equation}
\Vf(t) = \frac{\partial^2}{\partial t^2} \Vtheta(t) .
\end{equation}
与其将其视为位置的二阶\gls{differential_equation},我们不如引入表示粒子在时间$t$处速度的变量$\Vv(t)$,将牛顿动力学重写为一阶\gls{differential_equation}:
\begin{align}
\Vv(t) &= \frac{\partial}{\partial t} \Vtheta(t) , \\
\Vf(t) &= \frac{\partial}{\partial t} \Vv(t) .
\end{align}
由此,\gls{momentum}算法包括通过数值模拟求解\gls{differential_equation}。
求解\gls{differential_equation}的一个简单数值方法是欧拉方法,通过在每个梯度方向上小且有限的步来简单模拟该等式定义的动力学。
% 290 mid
这解释了\gls{momentum}更新的基本形式,但具体什么是力呢?
力正比于\gls{cost_function}的负梯度$-\nabla_{\Vtheta} J(\Vtheta)$。
该力推动粒子沿着\gls{cost_function}表面下坡的方向移动。
\gls{GD}算法基于每个梯度简单地更新一步,而使用\gls{momentum}算法的牛顿方案则使用该力改变粒子的速度。
我们可以将粒子视作在冰面上滑行的冰球。
每当它沿着表面最陡的部分下降时,它会累积继续在该方向上滑行的速度,直到其开始向上滑动为止。
% 291 head
另一个力也是必要的。
如果\gls{cost_function}的梯度是唯一的力,那么粒子可能永远不会停下来。
想象一下,假设理想情况下冰面没有摩擦,一个冰球从山谷的一端下滑,上升到另一端,永远来回振荡。
要解决这个问题,我们添加另一个正比于$-\Vv(t)$的力。
在物理术语中,此力对应于粘性阻力,就像粒子必须通过一个抵抗介质,如糖浆。
这会导致粒子随着时间推移逐渐失去能量,最终收敛到\gls{local_minimum}。
% 291 mid
为什么要特别使用$-\Vv(t)$和粘性阻力呢?
部分原因是因为$-\Vv(t)$在数学上的便利——速度的整数幂很容易处理。
然而,其他物理系统具有基于速度的其他整数幂的其他类型的阻力。
例如,颗粒通过空气时会受到正比于速度平方的湍流阻力,而颗粒沿着地面移动时会受到恒定大小的摩擦力。
这些选择都不合适。
湍流阻力,正比于速度的平方,在速度很小时会很弱。
不够强到使粒子停下来。
非零值初始速度的粒子仅受到湍流阻力,会从初始位置永远地移动下去,和初始位置的距离大概正比于$O(\log t)$。
因此我们必须使用速度较低幂次的力。
如果幂次为零,相当于干摩擦,那么力太强了。
当\gls{cost_function}的梯度表示的力很小但非零时,由于摩擦导致的恒力会使得粒子在达到\gls{local_minimum}之前就停下来。
粘性阻力避免了这两个问题——它足够弱,可以使梯度引起的运动直到达到最小,但又足够强,使得坡度不够时可以阻止运动。
% 291 end
\subsection{\glsentrytext{nmomentum}}
\label{sec:nesterov_momentum}
受Nesterov加速梯度算法\citep{Nesterov83b,Nesterov03}启发,\cite{sutskeverimportance}提出了\gls{momentum}算法的一个变种。
这种情况的更新规则如下:
\begin{align}
\Vv &\leftarrow \alpha\Vv - \epsilon \nabla_{\Vtheta} \left[
\frac{1}{m} \sum_{i=1}^m L\big( \Vf(\Vx^{(i)}; \Vtheta + \alpha \Vv), \Vy^{(i)} \big)
\right], \\
\Vtheta &\leftarrow \Vtheta + \Vv ,
\end{align}
其中参数$\alpha$和$\epsilon$发挥了和标准\gls{momentum}方法中类似的作用。
\gls{nmomentum}和标准\gls{momentum}之间的区别体现在梯度计算上。
\gls{nmomentum}中,梯度计算在施加当前速度之后。
因此,\gls{nmomentum}可以解释为往标准\gls{momentum}方法中添加了一个\emph{校正因子}。
完整的\,\gls{nmomentum}算法如\algref{alg:nesterov}所示。
% 292 mid
% 292 head
\begin{algorithm}[ht]
\caption{使用\,\gls{nmomentum}的\gls{SGD}(\glssymbol{SGD})}
\label{alg:nesterov}
\begin{algorithmic}
\REQUIRE \gls{learning_rate} $\epsilon$, \gls{momentum}参数 $\alpha$
\REQUIRE 初始参数 $\Vtheta$,初始速度 $\Vv$
\WHILE{没有达到停止\gls{criterion}}
\STATE 从\gls{training_set}中采包含$m$个样本$\{ \Vx^{(1)},\dots, \Vx^{(m)}\}$ 的\gls{minibatch},对应目标为$\Vy^{(i)}$。
\STATE 应用临时更新: $\tilde{\Vtheta} \leftarrow \Vtheta + \alpha \Vv$
\STATE 计算梯度(在临时点):$\Vg \leftarrow