一鸣 杜伟报道

你的算法耗尽全球GPU算力都实现不了,DeepMind阿尔法系列被华为怒怼,曾登Nature子刊

近日,DeepMind 之前时间发表在 Nature 子刊的论文被严重质疑。来自华为英国研发中心的研究者尝试实验了 DeepMind 的方法,并表示该论文需要的算力无法实现。

DeepMind强化学习领域具有很高的学术声誉。从 AlphaGo 到 AlphaStar,每一项研究都取得了举世瞩目的成就,但就在最近,DeepMind 的一篇有关多智能体强化学习的论文被华为英国研究中心「打脸」。华为论文指出,DeepMind 的这项研究存在多个问题。

研究者认为,如果要复现近日 DeepMind 登上《Nature》子刊的论文,需要动用高达一万亿美元的算力,这是全球所有算力加起来都不可能实现的。

那么,DeepMind 的这份研究是什么,按照华为论文的说法,存在的问题是什么呢?

  • 华为英国研发机构论文:https://arxiv.org/abs/1909.11628

  • DeepMind 论文:https://arxiv.org/pdf/1903.01373.pdf

被怼的 DeepMind 论文

作为 DeepMind「阿尔法」家族的一名新成员,α-Rank 于今年 7 月登上了自然子刊《Nature Scientific Reports》。研究人员称,α-Rank 是一种全新的动态博弈论解决方法,这种方法已在 AlphaGo、AlphaZero、MuJoCo Soccer 和 Poker 等场景上进行了验证,并获得了很好的结果。

华为论文计算的花销成本(以美元计)如下图 2 所示,其中考虑到了英伟达 Tesla K80 GPU 能够以每小时 0.9 美元、最高 5.6 GFlop/s 的单精度下运行。

图 2:计算α-Rank 时构造转换矩阵 T 的花销成本。

这里请注意,当前全球计算机的总算力约为 1 万亿美元(红色平面)。投影轮廓线表明,由于α-Rank「输入」的算力需求呈指数级增长,用 10 个以上的智能体进行多智能体评估是根本不可能的。

最后,在论文中,华为研究人员提出了一个对α-Rank 的解决方法,名为:α^α-Rank。该方法使用了随机优化策略,能够大大降低计算复杂度。

α-Rank 原理

α-Rank 是 DeepMind 提出的一项强化学习研究,主要针对的是多智能体强化学习的场景。强化学习是一种利用智能体在搜索空间进行探索,并根据其选择的策略给予恰当奖励,使其逐渐收敛到最佳策略上的方法。和一般的强化学习不同,多智能体强化学习中有多个智能体,多个智能体和环境进行交互时就会带来比单个智能体复杂得多的情况。

多智能体系统中,每个智能体都会通过与所在环境的交互来获取奖励值(reward),进而学习改善自己的策略,并获得该环境下行动的最优策略。在单智能体强化学习中,智能体所在的环境是稳定不变的。但是,在多智能体强化学习中,环境是复杂、动态的,因此不可避免地会给学习过程带来诸多困难。

MARL 最简单的形式是独立强化学习(independent RL,InRL),每个学习器不理会其他智能体,将所有互动作为自己(「局部」)环境的一部分。此外,还有许多智能体和环境以及彼此之间进行交互的研究,智能体彼此之间需要协作,形成联合策略(joint strategy)。要评估智能体选择的策略,就需要对联合策略进行评价。

因此,在可扩展的多智能体强化学习策略评估和学习中存在两个主要的困难。首先,联合策略空间(即所有智能体的策略总和)会随着智能体数量的增加而快速增长。其次,这种多智能体的游戏很可能会演变成一种「石头剪刀布」的循环行为,使得评价策略的好坏变得很困难。为了解决第二个问题,很多多智能体强化学习研究只能将智能体研究转换为博弈论的方法,按照最终博弈结果所得到的的固定分数进行评价。

最近,在解决多智能强化学习这一任务上,DeepMind 又提出了一个名为α-Rank 的方法。这是一个基于图和博弈论的多智能体协作评估解决方案。α-Rank 采用了马尔科夫-康利链(Markov Conley Chains),用于表示游戏动态过程,并尝试计算一个固定的分布。对联合策略的排名按照分布产生。

具体而言,DeepMind 的这篇论文将评估多智能体的问题转换为一个马尔科夫链的固定分布。假设有 N 个智能体,每个智能体有 k 个策略,则该马尔科夫链可被定义为一个联合策略图,有着的转移矩阵。而要被计算的固定概率分布 ν∈R^k^N,用于解 Tν=ν。v 的质量函数就是联合策略的排名分数。这一方法的亮点在于将多智能体的联合策略作为一个固定分布,以便进行排名和评估。

图 1:有 3 个智能体。a)每个智能体有 3 个策略(用颜色区分)和 5 个副本。每个智能体集群有一个 Pi 值,用于衡量其选择的策略;b)当一个突变策略(红色星星)发生的时候;c)每个群体选择维持原有策略,或者选择突变策略。

在 α-Rank 中,N 个智能体的策略会通过突变和选择进行评价。开始时,智能体集群会构建多个学习器的副本,并假设每个集群中的所有智能体都会执行同一个固定策略。这样一来,α-Rank 会通过随机采样每个集群中的学习器,用于模拟多智能体的博弈环境。在游戏结束时,每个参与的智能体的可以获得一个收益,这个收益可以用于策略突变和选择。在这里,智能体面临一个概率选择——换成突变策略、维持原有策略,或者随机选择一个和前两个不一样的新策略。这一过程持续,目标是决定一个主要的进化方法,并在所有集群的智能体中传播。

反驳理由

华为论文的反驳理由主要是根据α*-*Rank 的计算复杂度进行批判的。α-Rank 声称能够根据智能体的数量在多项式时间内解出问题,但华为论文认为实际的复杂度会随着智能体数量呈几何级别的增长,实际上是一个 NP 困难问题。

α-Rank 的计算复杂度太高

原始的α-Rank 研究声称其算法可解,因为随着联合策略的数量增加,其算法可在多项式时间内完成。根据这一定义,如果α-Rank 有多项式的复杂度,则计算时间应当和公式:O (N × k)^d,(d 和 N(智能体数量)、K(策略数量)独立)相称。而如果算法要求计算一个固定概率分布,有着一个 k^N 行和列的转移矩阵,则时间复杂度应该是 O(k^N)。很显然,这个结果是几何级的,因此不可解。华为论文的研究者认为,α -Rank 中计算最高的联合策略过程是一个 NP 困难问题。

从以上的计算复杂度研究可以得出一个结论,如果按照α-Rank 的方法计算一个固定概率分布,有着ε个固定策略,且精确度参数ε大于 0,可以有多种算法进行计算,计算复杂度如下表 1 所示。而任何一种现有的计算这个固定概率分布的方法都会因智能体的数量增长呈现几何级的复杂度增长。

表 1:以 N(智能体数量)×K(策略数量)表作为输入时的时间和空间复杂度比较。

α-Rank 的输入定义不清

除了计算复杂度问题,华为论文对α-Rank 的输入进行了讨论。DeepMind 的论文给出了这些智能体的复杂度计算结果,并声明了它们的可解性。但是,华为论文想要阐明的一点是,在没有正式定义输入的情况下,此类定义并不能反映真正的底层时间复杂度,因此很难声称这些智能体的可解性。

为此,华为论文举了解决旅行推销员问题的例子,这位旅行推销员需要造访一系列城市,同时又要按照最短的路线返回最初的城市。尽管大家都知道旅行推销员问题属于一种 NP 困难问题,但按照α-Rank 的思路,这一问题可以简化为「元城市」规模的多项式时间(线性,如可解决)问题,这并不是一种有效的声明。

华为论文指出,即使可以说排列数量确定的情况下可以在多项式复杂度中解决旅行推销员问题,这并不能说明任何类似的算法都是可解的。即使算法可以在多项式时间内解决问题,但其空间是几何级规模的,这并不能说明它是可解决的。因此,要说解决了复杂度的问题,就需要对输入进行调整。

一万亿算力都打不住

在以上问题都没有清楚解决的情况下,华为论文只能按照推测,将α-Rank 的输入考虑作为指数级的收益矩阵。接着,他们进行了一项实验,对仅执行算法 1 中第 3 行的扩展性评估花销进行了计算,同时也考虑到了 DeepMind 本篇论文《α-Rank: Multi-Agent Evaluation by Evolution》中的任务。

华为论文计算了α-Rank 算法 1 中第 3 行的扩展性评估的花销成本。

此外,构建公式 2 中 T 所需的浮点运算总量为

公式 2。

而就构建上述公式 2 中的 T 而言,华为论文计算的花销成本(以美元计)如下图 2 所示,其中考虑到了英伟达 Tesla K80 GPU 能够以每小时 0.9 美元、最高 5.6 GFlop/s 的单精度下运行。

图 2:计算α-Rank 时构造转换矩阵 T 的花销成本。

这里请注意,当前全球计算机的总算力约为 1 万亿美元(红色平面)。投影轮廓线表明,由于α-Rank「输入」的算力需求呈指数级增长,用十个以上的智能体进行多智能体评估是根本不可能的。

同样值得注意的是,华为论文的分析没有考虑存储 T 或计算平稳分布的花销,因而他们的分析是乐观的。

此外,如果将α-Rank 的输入加入收益矩阵并按照 DeepMind 论文的实验跑 AlphaZero,即使用上全球所有算力,也得花上超过 5200 年。

其他的算法也都不可行——在华为研究人员估算下,即使将收益矩阵加入α-Rank 跑 DeepMind 几个著名算法需要用到的资金花费和时间都是天文数字。注意:在这里预设使用全球所有的算力

华为提出改进方法α^α-Rank

华为在其论文中采用了一种随机优化方法,该方法通过对收益矩阵的随机采样而获得解决方案,同时无需存储指数大小的输入。与上表 1 中的内存需求相反,这一方法的复杂度为 O(Nk),每次迭代的复杂度为线性。值得注意的是,在启动任何数字指令之前,大多数其他方法需要存储指数大小的矩阵。尽管在理论上没有导致时间复杂度的减弱,但华为论文利用 double-oracle 启发式来扩展其算法,进而实现了联合策略下的空间减小。事实上,华为论文中的实验表明,α^α-Rank 可以在大型策略空间的数百次迭代下收敛至正确的顶级策略。

华为提出的改进方法。

华为论文表明其α^α-Rank 具有可扩展性,能够成功地在无人驾驶汽车模拟和伊辛模型(Ising model,一种具有数千万可能策略的设置)获得最优策略。他们注意到,当前 SOTA 方法的性能远远无法满足此等规模的需求。α-Rank 认为 4 个智能体最多可以采用 4 种策略。华为论文中的所有实验仅仅是在 64GB 内存和 10 核心英特尔 i9 CPU 的单机上运行的。

图 5:大规模多智能体评估。(a)无人驾驶模拟中最优联合策略组合的收敛性;(b)伊辛模型的平衡状态。

理论Nature强化学习华为DeepMind
1
相关数据
英特尔机构

英特尔是计算创新领域的全球领先厂商,致力于拓展科技疆界,让最精彩体验成为可能。英特尔创始于1968年,已拥有近半个世纪产品创新和引领市场的经验。英特尔1971年推出了世界上第一个微处理器,后来又促进了计算机和互联网的革命,改变了整个世界的进程。如今,英特尔正转型成为一家数据公司,制定了清晰的数据战略,凭借云和数据中心、物联网、存储、FPGA以及5G构成的增长良性循环,提供独到价值,驱动日益发展的智能互联世界。英特尔专注于技术创新,同时也积极支持中国的自主创新,与产业伙伴携手推动智能互联的发展。基于明确的数据战略和智能互联全栈实力,英特尔瞄准人工智能、无人驾驶、5G、精准医疗、体育等关键领域,与中国深度合作。面向未来,英特尔致力于做中国高价值合作伙伴,在新科技、新经济、新消费三个方面,着力驱动产业协同创新,为实体经济增值,促进消费升级。

https://www.intel.com/content/www/us/en/company-overview/company-overview.html
相关技术
华为机构

华为成立于1987年,是全球领先的ICT(信息与通信)基础设施和智能终端提供商。华为的主要业务分布在无线、网络、软件、服务器、云计算、人工智能与大数据、安全、智能终端等领域,发布了5G端到端解决方案、智简网络、软件平台、面向行业的云解决方案、EI企业智能平台、新一代FusionServer V5服务器、HUAWEI Mate等系列智能手机、麒麟系列AI芯片等产品。目前华为拥有18万员工,36所联合创新中心,14所研究院/所/室,业务遍及170多个国家和地区。

http://www.huawei.com/cn
DeepMind机构

DeepMind是一家英国的人工智能公司。公司创建于2010年,最初名称是DeepMind科技(DeepMind Technologies Limited),在2014年被谷歌收购。在2010年由杰米斯·哈萨比斯,谢恩·列格和穆斯塔法·苏莱曼成立创业公司。继AlphaGo之后,Google DeepMind首席执行官杰米斯·哈萨比斯表示将研究用人工智能与人类玩其他游戏,例如即时战略游戏《星际争霸II》(StarCraft II)。深度AI如果能直接使用在其他各种不同领域,除了未来能玩不同的游戏外,例如自动驾驶、投资顾问、音乐评论、甚至司法判决等等目前需要人脑才能处理的工作,基本上也可以直接使用相同的神经网上去学而习得与人类相同的思考力。

随机优化技术

随机优化(SO)方法是生成和使用随机变量的优化方法。 对于随机问题,随机变量出现在优化问题本身的表述中,其涉及随机目标函数或随机约束。

AlphaZero技术

DeepMind 提出的 AlphaZero 不仅征服了围棋,也在将棋、国际象棋等复杂游戏中实现了超越人类的表现。DeepMind 推出的 AlphaGo 曾在围棋项目中取得了超越人类的表现,其研究曾经两次登上 Nature。2018 年 12 月,AlphaGo 的「完全自我博弈加强版」AlphaZero 的论文又登上另一大顶级期刊 Science 的封面。在论文中,AlphaZero 不仅征服了围棋,也在将棋、国际象棋等复杂游戏中实现了超越人类的表现。

参数技术

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

时间复杂度技术

在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述,不包括这个函数的低阶项和首项系数。使用这种方式时,时间复杂度可被称为是渐近的,亦即考察输入值大小趋近无穷时的情况。例如,如果一个算法对于任何大小为 n (必须比 n0 大)的输入,它至多需要 5n3 + 3n 的时间运行完毕,那么它的渐近时间复杂度是 O(n3)。

概率分布技术

概率分布(probability distribution)或简称分布,是概率论的一个概念。广义地,它指称随机变量的概率性质--当我们说概率空间中的两个随机变量具有同样的分布(或同分布)时,我们是无法用概率来区别它们的。

收敛技术

在数学,计算机科学和逻辑学中,收敛指的是不同的变换序列在有限的时间内达到一个结论(变换终止),并且得出的结论是独立于达到它的路径(他们是融合的)。 通俗来说,收敛通常是指在训练期间达到的一种状态,即经过一定次数的迭代之后,训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说,如果采用当前数据进行额外的训练将无法改进模型,模型即达到收敛状态。在深度学习中,损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变,暂时形成收敛的假象。

博弈论技术

博弈论,又译为对策论,或者赛局理论,应用数学的一个分支,1944年冯·诺伊曼与奥斯卡·摩根斯特恩合著《博弈论与经济行为》,标志着现代系统博弈理论的的初步形成,因此他被称为“博弈论之父”。博弈论被认为是20世纪经济学最伟大的成果之一

多智能体系统技术

一个多智能体系统,是由一个在一个环境中交互的多个智能体组成的计算系统。多智能体系统也能被用在解决分离的智能体以及单层系统难以解决的问题。智能可以由一些方法,函数,过程,搜索算法或加强学习来实现。尽管存在相当大的重叠,然而一个多智能体系统并不总是一个基于智能体的模型表现一致。

旅行推销员问题技术

旅行推销员问题是这样一个问题:给定一系列城市和每对城市之间的距离,求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP困难问题,在运筹学和理论计算机科学中非常重要。 TSP是旅行购买者问题与车辆路径问题的一种特殊情况。 在计算复杂性理论中,TSP的做决定版本属于NP完全问题。

强化学习技术

强化学习是一种试错方法,其目标是让软件智能体在特定环境中能够采取回报最大化的行为。强化学习在马尔可夫决策过程环境中主要使用的技术是动态规划(Dynamic Programming)。流行的强化学习方法包括自适应动态规划(ADP)、时间差分(TD)学习、状态-动作-回报-状态-动作(SARSA)算法、Q 学习、深度强化学习(DQN);其应用包括下棋类游戏、机器人控制和工作调度等。

AlphaStar技术

AlphaStar是2019年1月DeepMind推出的打星际争霸2的AI系统。在1月的首次亮相中,DeepMind播放的比赛视频显示AlphaStar击败了两名人类职业选手TOL与MaNa,引起了业内极大的关注。DeepMind 官方博客介绍,AlphaStar 的行为是由一种深度神经网络生成的,该网络从原数据界面(单位列表与它们的特性)接收输入数据,输出构成游戏内行为的指令序列。具体来说,该神经网络使用了一个 transformer 作为躯干,结合了一个深度 LSTM 核、一个带有 pointer 网络的自动回归策略 head 以及一个中心价值基线。

推荐文章
这个帖子是骗子,scientific reports不是nature子刊,虽然是nature旗下的刊物,scientific reports在学术界是四大水刊之首。