您的位置首页  文体资讯  体育

百度正用AlphaGo算法 解决一个比围棋更难的问题

  • 来源:互联网
  • |
  • 2019-04-22
  • |
  • 0 条评论
  • |
  • |
  • T小字 T大字

  百度硅谷AI实验室的同学们,就在用这个出自谷歌DeepMind的围棋算法,解决一个比围棋复杂得多的数学问题。

  他们解决的问题,叫做“图着色问题”,又叫着色问题,属于前些天让中国奥数队全军覆没的图论。它是最著名的NP-完全问题之一。

  简单来说,就是用尽可能少的颜色,给一张图的顶点上色,相邻顶点的颜色不重复。

  而复杂版……只要顶点足够多,分分钟让人类数学家无从下手,如果有512个顶点,这个问题的复杂度会比围棋高出几百个数量级。

  在这个数学问题上,运动员AlphaGo表现优秀,最高能将一张图所用的颜色减少10%。

  就算你对“图论”、“着色问题”这些词有点陌生,应该也听说过“四色”。这是第一个由计算辅助证明的数学。

  四色告诉我们,只需4种颜色我们就可以让地图上所有相邻国家的颜色互不相同。

  这其实就是一个平面上的着色问题,国家可以简化为顶点,国与国之间的相邻关系可以简化为连接顶点之间的线。对于平面图而言,颜色数k最小等于几?

  历史上数学家已经手工证明了五色(k=5),但是因为运算量太大,在将颜色数量进一步减少到四种(k=4)时却迟迟无决,最终在70年代靠计算机才完成证明。

  一般来说,我们可以用算决这个问题,其基本思是:先尝试用一种颜色给尽可能多的点上色,当上一步完成后,再用第二种尽可能多地给其他点上色,然后再加入第三种、第四种等等,直到把整张图填满。

  或者是用深度优先搜索算法,先一步步给图像着色,若遇到相邻点颜色相同就回溯,再换一种着色方法,直到问题解决为止。

  如果图的顶点数比较少,以上两种方法还可行,但随着顶点数的增加,以上两种算法的局限性就了出来。

  算陷入局部最优解,而深度优先搜索算法的运算量会越来越大,以至于完全不可行。

  图着色问题的复杂度随着顶点数增加而急剧增长。当顶点数达到512时,其可能得状态数就达到达到了10^790,远超围棋的10^460,当然更是比全的粒子数10^80多得多。

  即使中等大小图的状态数也远超围棋,如果顶点数量达到1000万,复杂度会大得惊人,相当于在1后面有4583万个0。

  另外着色问题还有另一个复杂维度,围棋算法可以反复在同一张相同棋盘上进行测试,而图即使顶点相同,因为连接各点的边不相同,结构也不完全相同。

  这些更复杂的问题对算法的训练和推理提出了极大的挑战。而AlphaGo曾在解决这类复杂问题上取得了很大的成功,研究人员也很自然的想到了用它来解决图的着色问题。

  对于这类问题,我们一般采用式搜索算法(heuristic search),就是在状态空间中的搜索对每一个搜索的进行评估,得到最好的,再从这个进行搜索直到达到目标。

  AlphaGo使用的蒙特卡洛树搜索(MCTS)用的就是一种式搜索算法。

  △蒙特卡洛树搜索算法示意图:选择径;扩展树;由神经网络执行模拟;将最终结果反向,更新径节点。

  AlphaGo下棋通过正是这种方法,计算当前棋盘上获胜概率最大的点,直到赢棋为止。

  图着色问题与围棋也有类似之处,它的每一步棋就是给接下来的点填上颜色。它和围棋和象棋一样都可以用强化学习来解决问题,差别则是励。

  在图着色问题中,最明显的励选择是颜色种类,使用的种类越少越好。而在围棋和象棋中,励是游戏的胜负结果。

  在棋类游戏中,让算法在对弈中进化是很一件很自然的事,让表现最好的学习算法与自己对抗,这就是AlphaGo的升级版本AlphaGo Zero。

  AlphaGo Zero没有学习人类棋谱,它只是懂得围棋规则,在不断的对弈中获得提高,谷歌只用了21天,就让这个0基础的升级版打败了5-0战胜柯洁的AlphaGo Master版。

  当AlphaGo进化到自学版本AlphaGo Zero后,它就更适合做图着色问题了,因为着色问题是没有所谓“人类棋谱”可以学习的。

  在图着色问题种,研究人员让AlphaGo Zero与其他算法比赛,看谁用的颜色种类少,这就是算法的励机制。

  和AlphaGo一样,图着色算法也有策略网络(p-network)和价值网络(v-network),p是顶点涂某种颜色的概率,v是最终颜色数量少于之前最佳算法结果的概率。

  1、可扩展性(Scalability):线性O(V)或线性对数O(E+VlogV)时间复杂度,它在更大的图形(比如1000万顶点)上也能使用。

  2、完整图形上下文(Full Graph Context):不同的图有不同的着色策略,因此网络需要有图形结构的信息。

  问题上下文(problem context)是根据刚刚着色的顶点,来安排接下来对哪些顶点进行着色。它在任务开始和结束的时候都是零。问题上下文中包含的顶点数是一个超参数,在实验中设置为8。

  可能颜色上下文(possible color context)是以上顶点集合每种可能用到的颜色。它也是一个超参数,在实验中设置为4。

  策略网络使用全局图形上下文(global graph context),它负责计算将每个颜色选择分配给当前顶点的概率。

  随着填充过程的进行,颜色数量会逐渐增加。为了支持颜色数量的变化,它会首先处理每种颜色,产生一个非标准化分数,然后通过seq2seq模型对该分数进行处理,该模型还会考虑与其他颜色的依赖性。最终通过softmax操作得出归一化的填充颜色概率。

  策略网络利用了具有相同颜色的节点之间的局部关系,提高了准确性,同时还降低了大图计算的时间复杂度。

  价值网络负责从输入数据预测着色问题最终的结果。 问题上下文(problem context)中的顶点与着色顺序存储在对应的序列中。使用seq2seq模型处理此序列,然后将这个序列与图形上下文(graph context)组合起来,并将它们馈送到完全连接的reLU层中,最终结果输入softmax,计算出胜利、失败或平局的概率。

  研究人员用FastColorNet的强化学习过程来训练图着色问题,图形大小从32个顶点到1000万个顶点不等。

  在32K到16M个顶点的图上进行测试,FastColor在训练集中使用的颜色比以往的式搜索算法提高了5%-10%。 尽管在测试集有所逊色,但性能也比先前的算法高出1%-2%。

  虽然提升比例看起来不高,但这种算法显示出解决此类问题的潜力。Twitter上一位网友这样评价:这篇文章以线性复杂度O(n)解决了一个NP完全问题。

  量子位正在招募编辑/记者,工作地点在中关村。期待有才气、有热情的同学加入我们!相关细节,请在量子位号(QbitAI)对话界面,回复“招聘”两个字。

免责声明:本站所有信息均搜集自互联网,并不代表本站观点,本站不对其真实合法性负责。如有信息侵犯了您的权益,请告知,本站将立刻处理。联系QQ:1640731186
友荐云推荐