热门关键字:  必博bbo官方网站手机版  
你现在的位置:首页 > 资料下载 > 内容

强化学习实验里到底需要多少个随机种子的严格证明

2018-08-20 来源:本站

  雷锋网 AI 科技评论按:在机器学习和深度强化学习研究中,可重复性成为了最近最为热门、最常被人诟病的话题之一。复现一篇基于强化学习的文章远比想象的难,具体分析可参照《lessons learned from reproducing a deep RL paper》。

  事实上,一般情况下,源代码库并不总是被完整发布的,科学性的论文中时常会省略部分实现技巧。近期,Herderson 等人对造成复现困难的各种参数进行了深入的调查。他们使用了当下热门的深度强化学习的算法,如 DDPG、ACKTR、TRPO 和 PPO 等,并结合 OpenAI Gym 中的经典基准测试,如 Half-Cheetah, Hopper 和 Swimmer 等,研究代码库、网络大小、激活函数、奖励缩放或随机种子对性能产生的影响。结果中最令人惊讶的是,同样的算法、用同一组超参数进行训练时,每一次运行后的结果也会大相径庭。

  也许最令人惊讶的是:使用相同的超参数和 10 个不同的随机种子运行相同的算法 10 次,其中 5 个种子的表现做平均和另外 5 个种子做平均,得到的两条学习曲线仿佛是来自两个不同的统计分布的。然后,他们展示了这样一个表格:

  该表显示了 Henderson 等人参考的所有深度 RL 论文使用了少于5粒种子。更糟糕的是,一些论文实际上展现了最佳表现的平均值!正如 Henderson 等人刚才展示的那样,算法表现的不稳定性使得研究者可以通过挑选种子的方式声称某个算法比另一个算法的表现更好,即便事实上并不是这样。这个问题的解决方案是使用更多随机种子,以平均更多不同试验的结果,最终获得更稳健的算法性能度量。那么,到底使用多少才是合适的呢?应该使用 10 个,还是应该像 Mania 等人提出的那样使用 100?答案当然是,看情况。

  如果您阅读此博客,我猜您肯定处于以下情况:您希望比较两种算法的性能,以确定哪种算法在给定环境中表现最佳。不幸的是,相同算法的两次运行通常会产生不同的性能数值。这可能是由于各种因素造成的,例如随机发生器产生的种子(随机种子,简称种子)、智能体的初始条件、环境的随机性等。

  本文中描述的部分统计过程可以在 Github 上找到。这篇文章可在 ArXiv 上找到。雷锋网 AI 科技评论对全文进行了编译。

  一段算法的表现可以通过数学建模成一个随机的变量并且在环境中运行该算法可以得到实现将这个过程重复遍,可以得到统计样本。一个随机变量通常可以用其平均值和其标准偏差

  比较两个表现分别为和的算法。如果和遵循正态分布。描述它们差值的随机变量也满足正态分布,并且,。在这种情况下,平均值的估算值为,并且的估算值为。影响效果可以用两个表现的平均差值来表示:。

  测试两个算法的性能差在数学上等同于测试它们运行结果的差值与的差。那么,根据上面的推理,从随机变量和产生的两个样本和相减得到的变量所得的进行计算即为所需的样本。

  为了说明本文中提出的概念,采用两种算法(Algo1 和 Algo2),并在 OpenAI Gym 框架中的 Half-Cheetah 环境中进行比较。所使用的实际算法在这里并不那么重要,稍后会公布。首先,进行初步研究,对每个算法设定 N = 5 个随机种子,并在图2中绘制结果。该图显示了平均学习曲线% 置信区间。学习曲线 个评价时段中的奖励的累积值。该算法性能的度量值是过去 10 个点(即最后 100个评价时段)的平均性能。从图中可以看出,Algo1 的表现似乎优于 Algo2;而且,越靠近结尾的位置,置信区间的重叠也并不多。当然,我们需要在得出任何结论之前进行统计学的测试。

  这些假设指的是双尾的情况。如果你有一个先验的算法表现最好,假设为Algo1,也可以使用单尾版本:

  在一开始,统计学家经常会使用零假设。一旦一个样本从获得了,可以估算观测数据的概率为极值。极值的含义是远离零假设的数值,即的数值远离0。概率的值可以回答下面的问题:观测一个样本或更加极端的样本出现的概率,假设两个算法的表现没有本质的不同时。在数学上,可以使用单尾版本的公式来描述这一过程:

  当这个概率变得非常低时,这意味着两个没有性能差异的算法产生收集的样本是非常不可能的。差异明显可以表现为概率在单尾情况下比的值小,并在双尾情况下比的数值小。通常将的数值设置为0.05或者更低。值得注意的是,尽管概率很低,依然是二十分之一的几率出现误报,即在声称没有差异时存在真正地差异。

  第一种错误是在没有真正差异时声称算法优于另一算法的优越性。注意,我们称之为显着性水平和类型-I 误差 α 的概率,因为它们都指的是相同的概念。在统计检验的假设下,选择 α 的显着性水平强制执行I型误差 α 的概率。

  第二种错误则是在有差异的时候忽略差异的出现,即在实际算法有性能差异的时候错过了发表问斩的机会。

  为了进行性能评估,必须首先确认需要使用的统计实验。在 Herderson 的论文中,two-sample t-test 和自举置信区间试验可用于此目的。Herderson 等人也同时推荐了 Kolmogorov-Smirnov 实验,用于测试两个样本是否来自同一个分布区间。但这种测试不能用于比较 RL 算法,因为它不能证明任何顺序关系。

  为了验证两个种群具有相同的均值的假设(零假设)。一个 2-sample t-test 可以在两个种群的变量假设为一致时进行测试。但是,这种假设在对比两个不同的算法时并不是每次都成立的(比如 DDPG 和 TRPO 算法)。在这种情况下,2-sample t-test的变种 Welchs test 被提出了。T-test 包含几个假设:

  基于这些假设,可以通过如下公式对统计值 t 和自由度 v 进行描述,这里使用 Welch–Satterthwaite公式:

  同时,,是两个样本的经验标准偏差,N 为样本的大小(两个样本的大小是一样的)。那么 t-statistics 默认遵循 t-distribution,是钟型的,同时其宽度取决于自由度。自由度越高,分布越扁平。

  t-distribution 由其概率密度函数(图中左侧曲线)定义。累积分布函数为的概率总和,即为:

  在上图中,代表在单尾情况下满足的 t-value。当时,概率p 小于 α,实验结果否定了零假设。另一方面,当小于时,概率p 的值大于α,实验未否定零假设。从图片上可以看出,将阈值设置为,会导致上文所提到的第二种错误。出现错误的几率是图中深蓝色阴影所表示的部分,可以用数学的方式表达如下:

  值得注意的是,并不意味着两个算法之间没有差异。只能表明没有足够的证据证明在置信度的基础下差异是存在的(也可能意味着第二种错误的情况)。噪音可能会妨碍测试检测差异的能力。在这种情况下,增加样本量N 可以帮助发现差异。

  选择 t-test 的显著级别 α 会导致第一种错误的情况。但是,上图显示的是减少这种概率归结为提高的值,这最终导致了第二种错误的出现。通过提高样本的数量N,降低β,同时保持 α 为恒定值,可以使估算的更加准确,这最终使得图片中的分布曲线更为扁平,更小的 β 值。下一部分介绍了在同时满足α和 β 的情况下,选择合适的样本数量N 的方法。

  Bootstrapped 置信区间是一种不对性能差异的分布做出任何假设的方法。它通过在实际收集的样本中重新采样并通过计算每个生成的样本的平均值来估计置信区间。

  给定正态分布的真实平均μ和标准偏差σ,一个简单的公式给出95%置信区间。但在这里,考虑一个未知的分布F(给定一个算法的性能分布)。正如我们上面看到的,经验平均值是其真实均值的无偏估计,但是我们如何计算的置信区间?一种解决方案是使用Bootstrapp原理。

  假设有一个测试样本,其中N 是样本的数量。通过原始样本内的置换采样,可以得到经验bootstrap的样本,标记为,其样本数量与原测试数量是相同的。在bootstrap原理中,对于原始样本上和自举样本上计算的任何统计数据,其变化是保持一致的。更多的解释和理由可以从麻省理工学院的这份文章中找到。因此,可以通过bootstrap样本的变化量来近似经验平均值的变化(这里可以值变化范围)。

  Bootstrap的样本数量B 需要选择相对较大的值(如1000)。如果置信区间的范围不包含0,这就意味着置信为时,差值只为正或者负(范围最大值最小值均为正或均为负)。通过这种方式,可以清楚的获得两个算法的性能表现的统计显著差值。可以通过如下链接,参考一个实际应用。

  这里,设置α=0.05会导致第一种错误的出现。对两个有5个随机种子样本进行Welchs test和bootstrap置信区间测试,p-value 为0.031,。由于p-value 低于α,同时CI1置信区间并不包含0,两个测试都是通过的。这意味着两个实验结果都表明了算法Algo1和Algo2的性能表现有显著不同,且有95%的置信度。若真的检测失败,即仅仅存在 5% 的可能性会误报出算法性能有显著不同的结果。

  它们都是权威的DDPG的实现算法。代码库可以从资料库下载。这就意味着是一个真假设,并且两个算法的平均值是相同的。第一个结论是错误的,必须要承认,在这里实验结果是第一种错误,即在正确的时候否认了。但是,统计测试通常伴随着一些假设,这导致最终实验碰到第一种错误。

  在实验实现环节,强制选择 α 作为显著等级的选择。第二种错误β现在需要进行估算。β是在为真的否认失败的概率。当影响因子和第一种错误的概率 α 是常数时,β 是样本数量 N 的函数。选择样本的数量 N 来满足 β 的需求就称为统计功率分析(statistical power analysis)。这回答了文章最一开始提出的问题:若显著等级为 α ,选择多大的样本容量来满足 1-β 的概率发现影响因子?下一章节将会介绍在Welchs test中选择合适的 N 的步骤。

  在这里,为以0为中心点t-distribution的累积分布函数,为临界值,为影响因子的t-value。

  为了更好的理解本文的含义,使用两个DDPG的算法:一个有执行扰动(Algo1),一个有参数扰动(Algo2)。两个算法都在OpenAI Gym框架下的Half-Cheetah环境中执行。

  为了实际的获得β,首先需要进行两个算法的标准偏差的估算。在这个步骤中,算法在环境中计算,并获得两个大小为 n 的样本 x1 和 x2 。然后对其经验平均值和标准偏差进行计算。

  这里,设置样本容量为n=5,经验平均值为(3523,4905),经验标准偏差=(1341,990),如下图描述,其中红色曲线,蓝色曲线。从图中可以看出,两个算法的表现有轻微的不同,并且。

  给定一个统计测试(如Welchs test),一个显著等级α(如 α =0.05)和Algo1、Algo2的经验估算标准偏差,可以计算得到β,通过基于样本容量 N 和影响因子。

  若N 在[2, 50]中取,取自于,通过前文公式计算,V 和。最后,通过前文公式计算第二种错误的概率β 。下图展示了β 在不同的时的数值变化曲线。黑色虚线是 从图中可以读取到,N=5 时,β=0.51。这意味着当影响因子为1382时,有51%的概率得到第二种错误的实验结果。为了使错误概率降低到20%以下,N 的选择需要大于10(图中,β=0.19 的点)。

  上述实验中,当N=10时,满足影响因子为1382的概率条件,并在welchs test的前提之下,使用的经验估算值为。但是,需要值得注意的是,这样的实验结果是基于多个近似,包括,并假设了t-value的钟形分布。

  这里,设置N=10,并执行Welchs test和bootstrap测试。通过实验,获得Algo1和Algo2的经验平均值和经验标准偏差。这两个实验结果都否定了,Welchs test的p-value 为0.0037,并且bootstrap测试的差值置信区间为。两个实验都通过了。在下图中,N=5 和N=10 的曲线都绘制了。将样本容量提高到10时,原本在样本容量为5的情况下不能被识别的显著差异就显示出来了。有更多的随机种子,估算的更具鲁棒性,更多的证据可以证明Algo2的性能比Algo1算法的性能好,这可以通过图片中的尖峰进行识别。

  给定相应的假设,t-test 和 bootstrap 实验在选择显著等级为α 时,都面临第一种错误的问题。为了得到正确的错误概率信息,这些假设都需要被仔细的检查。首先,基于实验数据,需要计算第一种错误概率的经验评估,并展示:1)bootstrap测试对小样本容量极度敏感;2)t-test的结果可能会对非正太分布的数据有偏差。然后,在实验中,也验证了,低样本数导致了s1和s2的估算值的不准确性,并造成β 计算较大的误差,最终造成从实验中反馈的样本数量需求也偏低。

  使用示例二中的Algo1算法。经过42次实验,如上的过程,N 的选择范围为[2,21]。下图展现了实验的结果。在α=0.05的情况下,当N取值过小时,经验估算的false positive的几率比基准值高出很多。

  在实验中,bootstrap测试的置信区间不能使用在小样本量的计算中(10)。即使是在这种情况下,产生第一种错误的概率在实验中被低估了(应为10%,而实验结果为5%)。Welchs test降低了这种影响力,但在样本容量很小的时候,反而更难得到正确的结果了。综上,在实验时,需将α 的值设置为0.05以下,以确保true positive的概率低于0.05。在示例一中,N=5,则遇到了第一种错误。在上图中,这种可能性在bootstrap测试中得到约10%的计算结果,Welchs测试中获得了高于5%的结果。

  基于样本容量 N 和标准偏差的经验估算值,Welchs test计算了 t 的统计信息和自由度 V 。当 N 的值很低时,S1和S2估算值低于实际的标准偏差值。这导致了更小的 V 和 更低的,并最终影响了低 β 值。最后,更低的β 在环路中影响了样本容量的选择。这对样本容量N 的计算有着显著影响。下图在两个分布和中,false positive几率β 。图中两个结果的区别是,左侧的图片使用了真实的数值进行计算,而右侧的图片使用了经验评估值。从实验结果可以看出,不管使用哪一种数值,基于β 的样本容量的选择是一致的。

  在本文中,详细的介绍了在比较两个强化算法的时候遇到的统计问题。并定义了第一种错误和第二种错误,同时还提出了ad-hoc统计测试的方法进行性能对比测试。最后,作者还介绍了在测试中选择正确的样本数量的方法,并通过实际案例进行了分析和描述。

  本文最重要的意义并不仅限于方法和应用的介绍,而是基于本文的理论进行的后续的研究。通过挑战Welchs test和bootstrap测试的假设,作者发现了几个问题。首先,作者发现了在实验中,经验推断值和理论实际值的显著差异。为了规避这个问题,作者提出了N=20的最低样本容量要求,指出bootstrap测试必须使用在样本数量N20的情况下,只有满足这样的要求,才能符合false positive几率的要求(0.05)。其次,样本容量N的要求在计算中很大的取决于的精度。为了顺利的进行推算和计算,在实验一开始就需要选择系统的大于功率分析的规定。

  最后,作者非常谦虚的留言:需要注意的是,本文的作者并不是一个专业的统计学者,如果在文中发现任何统计学上的问题,请随时与作者联系~