2016-03-12

浅说 AlphaGo

首先, 今天是李世石先生结婚十周年纪念日。 多么值得纪念的一天, 先祝李先生李太太锡婚纪念日愉快, 长长久久! 李先生今日坚强战斗, 虽然不敌电脑的蛮力, 但是回到家还有太太温暖的拥抱, 还有女儿绕膝, 还有无数我这样远远关注比赛, 为他摇旗呐喊, 加油打气的人, 做人还是很美好的。 李先生加油。

再说一件题外事。 其实我不会下围棋, 平时也并不关心围棋界的消息。 这次比赛是从德国最大的科普新闻网站 heise 那里看到的。 当天去查了一下有关 AlphaGo 的资料, 了解到她那套算法是用到经过海量棋谱深度学习以后的模拟神经网络。 而我是了解机器深度学习的原理, 也见识过这一族算法的厉害的。 在计算机视觉, 计算机语音识别等等领域, 这几年都是大量用到这套工具。 虽然是围棋盲, 但是当下就隐隐感觉到了 AlphaGo 来者不善。

我就在 heise 网站留言说: “AlphaGo 的深度学习算法有学到人类最优秀棋手的 think patterns,在实战中还有强劲的实时运算能力找到致胜的道路。 归根到底其实李也是这样子学习棋艺并且作战的。 但是, 实战中计算机不会累也不会漏看什么局面, 它的表现要比人类稳定得多。 如果李在比赛中从头到尾都处于极佳状态, 那他还有点机会。 否则他会很难办。 我衷心祝李好运。”

就是这样一个留言,有被德国的围棋爱好者痛骂, 说李一定会赢。 基本上, heise 的读者已经是些技术宅人。 也就是说, heise 的读者对新技术的理解和接受水平是高于德国民众的平均水平的。 由此可以窥得德国社会对于人工智能怎样运作的理解度和接受度。 所以人工智能很容易在德国社会引起无谓的恐慌和抵触。 所以自动驾驶汽车一类的先进工具注定会在德国遭遇阻力。 所以科普工作者们必须还要做很多事。 好的我今天就是来科普的。 废话讲完, 言归正传。



首先,简单说下为什么下好围棋对计算机来说非常困难。 通常,写棋类对弈的程序, naive 一点的算法, 就是把每一步以及以后的所有可能出现的情况全部列出, 在电脑的内存中建立一种所谓 “搜索树” 的数据结构。 搜索树上的每一个分支,就代表一种走法的 sequence, 这个分支展开直到末端, 就是对弈到底的情况, 就可以看出胜负。 某一个还没有走到底的盘面,就对应于搜索树上末端之前的某个节点。 在这个节点上, 可以根据它后面展开分支上的胜负情况, 给出一个胜负概率。

比如,第 100 步上的某个节点, 后面还有 100 个分支。 这 100 个分支中, 20 个到最后是赢, 80 个是输。 那么这个第 100 步节点上的胜率就是 0.2。 不是一个理想的选择,程序应该看看第 100 步中另外的节点的胜率。 后续步数越多, 就代表搜索树越 “深”。 假如围棋在理论上是 361 步走完, 那么一开始的时候, 它的搜索树的深度是 361。 走到第 300 步的时候, 因为前面的 sequence已经完全确定, 剩下的搜索深度就只有 61 层了。

那么, 这种搜索树, 假如全部分支都展开, 可以有多大呢? 据信息学家 Claude Elwood Shannon计算,国际象棋每一步平均有 20 种不同的走法。 也就是说, 它的搜索树的根部会有 20 个分支, 第二步的每一个分支上, 又有 20 个分支, 依次类推。 走三步就有多少个分支了呢? 20 * 20 * 20 = 8000.  走三十步就是 20^30 个分支。 而围棋棋盘比国际象棋更大。 假如要把所有对弈结果穷尽列举, 那么它的搜索树上会有多少个分支呢? 科学家的计算结果, 大约是 10^170 个。 而我们可以观测到的宇宙中的所有原子, 加起来也不过是 10^80 个。 每一个原子都用来代表围棋下法的一个分支都不够用。 就算开动全世界所有大大小小的电脑一起搜索每一种走子结果, 搜到地老天荒宇宙第二次大爆发都只刚刚搜了个开始。 围棋编程够难吧? 怎么办呢?

有些白痴走法, 比如, 第一步 A1, 第二步 A2, 第三步 A3……是不可能去走的。 于是, 那些白痴程度类似 A1 --> A2 --> A3 的分支, 全部可以砍掉。 假如剩下的分支还是太多, 那就只能随机抽取一些分支搜到底, 再来算一算某个节点上的获胜概率了。  这种随机抽样再计算的方法就是所谓的蒙特卡洛法。 这种算法可以在有限的时间内保证给出一种解答, 但不保证是最优解。 国际象棋规则相对多, 盘面上明显的优劣比较好判断, 按着下棋规则和盘面优劣情况可以砍掉它的搜索树中绝大部分的分支。 接下来的随机抽分支,样本覆盖面比较大, 最后算出来的那几个 “下一步” 的获胜概率就比较准确。 所以光靠这个蒙特卡洛搜索法, 再配合一些局部优化算法, 若干年前就已经战胜人类。 但是围棋不同。 她的搜索树上的分支比国际象棋多出许多。 然后, 用来 “砍树” 的, 直接一些的规则很少。 “用简单规则把搜索分支减少到可控范围” 这条路在围棋上是走不通的。

于是我们必须教给计算机程序一些 “棋理”, 让她能在盘面上作出好的选择。 而围棋的棋理十分玄奥, 而且, 有时同一个盘面同一个布局, 好坏也是众说纷纭。 现在的问题是, 怎样让计算机来学习这些玄虚奥妙, 说也说不清楚的棋理呢?

这里, 就可以用到模拟神经网络和深度学习算法来让计算机自动分析归纳出棋理来了。

所谓的 “模拟神经网络” 也是一种数据结构。 数据结构中的节点好比神经元, 常常用来 classify 一些事情。 连接节点之间的通道则常常代表某种触发或者传输条件。 下面我们来看一个最最简单的, 层数为 2 的模拟神经网络:



上面这个两层的神经网络表达了一个布尔函数 “异或 XOR ”。  这个神经网络, 在第一层(玫红色的那一层)上的节点里输入两个布尔数 X1 和 X2 的值,通过布尔运算规则得出中间值 Z1 和 Z2 (蓝色部分), 这两个中间值再与一下, 得到函数的输出结果 y。 这个例子只是给大家提供一个关于类神经网络的感性认识。

因为我自己对围棋一无所知, 所以用计算机图像识别作例子来简单说明一下这种数据结构的应用。 一张人脸照片上有许多特征, 比如嘴角, 眼角, 鼻翼等处有凹陷, 照片上相应的这些点颜色就比较深。 我们可以想象一下神经网络的某一层就是用来储存照片上这些深色的点的信息。 然后, 还可以找出这些点和点之间的约束条件,比如两个深色点之间的直线距离, 比如相对于头宽的距离, 诸如此类, 就可以进一步确定 “这是一只眼睛”, “这是一张嘴” 等等中间值。 这就是所谓 “模式识别”, 即 pattern recognition。

通常神经网络中的每一层负责侦测图上的一方面或者某些方面的特征信息。 最后综合网络中各层特征信息, 再经过一层或者几层的线性回归模型, 计算机得出这张照片是不是一张人脸的结论。 而这些 “人脸的各个方面的特征”, 在训练的时候则不必由人事先告诉计算机。 只需给计算机一张照片并告诉它这是一张人脸, 就可以。 只要用来训练的照片足够多, 算法就可以很好地归纳出所有这些特征或者模式。

而计算机 “归纳特征” 或者 “归纳模式” 的能力是惊人的。 2012 年的 ImageNet  计算机图像识别竞赛上, 冠军 SuperVision 小组训练出来的神经网络有 8 层, 用到 6000 万个参数 (可以看成是 6000 万个特征)。  那个神经网络识别猫猫狗狗比我厉害多了。 有些罕见猫狗, 长得比较像对方, 凭照片我无法判断是猫还是狗, 而算法的判断则八九不离十。 

至于说那 6000 万个特征, 到底是些什么呢? 那些写算法的科学家自己事先都不知道的, 必须到那个神经网络里去查询一下的。 查询出来的结果, 很多都是连那个科学家自己都觉得匪夷所思。比如 (例子我乱举的, 只是给大家一个印象), “耳朵顶部到耳朵底部的连线跟头部弧线的某个切线的夹角的数值范围”。 一般人类不会去这样看一张图。

大家必须记住的是, 海量照片训练出来的神经网络, 并不是记住某张照片上是什么, 而是把照片上的特征全部都分析归纳过。 所以, 你给它一张新的照片让它判断, 它首先是分析这张照片的特征, 再根据特征来判断, 而不是 “背” 照片。 基本上这个神经网络就是一个知识储存库。

所谓的 “深度学习”,“深度” 是指算法底下那个神经网络的深度。 这个网络越深, 被研究对象的特征也就被分析得越透彻。 比如 Google 的语音识别神经网络, 就深达 30 层, 不得了的事。 模拟神经网络技术已经有 50 多年历史, 但是以前不被重视。 这是因为, 如果训练用的数据太少的话, 它给出的结果很不准确。 但是, 大数据时代的到来令这一族算法获得了新生和极为广泛的应用。 

现在大家可以想像一下怎样用深度学习算法来训练 AlphaGo. 喂给它棋谱, 并且告知最后胜负就可以。 当中的棋理, 就跟图形识别中的特征归纳类似, 算法自己会去归纳总结的。 这就它厉害的地方。

第一, 他并不需要一个顶尖高手给他作教练。 当然那个学习模块内部还是需要一些用来归纳规律的数学模型。 他的建模专家, 只要是个中等程度的棋手, 给那个学习算法适当程度的约束就可以。 太白痴或者太高手都不适合。 对围棋一无所知的建模人员会让那个深度学习模块无所适从。 而太高超的棋手, 可能会把太多自己的想法加到那个选择模型中去, 而他的判断未必是最优的。 
黃士杰这样的棋手, 给深度学习模块作一些指导性的约束, 不太少也不太多, 其实很合适。

第二, 经过海量的棋局对弈训练,一些玄妙高深而难以言传的所谓 “棋理”, 会被 AlphaGo 的深度学习模块整理归纳出来的。 这中间, 有些是我们人类已经知道的, 而有些可能是人类并不知道, 并没有探索过的 “致胜棋理”, 或者说 “致胜围棋哲学”。 围棋对弈中,双方的发挥空间那么大, 发生这样的事 (电脑归纳出人类未知的围棋哲学) 其实很正常。  换句话说, AlphaGo 经过几千万局的对弈, 对围棋棋理的 “理解” 程度, 很可能已经超过了人类。 以上两点,也正是我在德国 heise 那样留言的理由。

机器学习算法训练出来的结果, 即不同盘面下的策略选择和价值判断, 是分别储存在 AlphaGo 的策略网络和价值网络中, 代表 AlphaGo 的 “棋感”。 这种类神经网络的数据结构有一个特点, 就是读取效率非常高。 它们用来给 AlphaGo 提供基于经验知识的 “直觉判断”, 也就是为下一步提出几个最有价值的选点。 这里的 “价值” 以获胜概率表示。

但是, 那个获胜概率也只是一个估计值。 跟水平一般的棋手下, 那两个网络就足够。 相当于, 高手对庸手, 高手凭感觉下棋就可以了。 但是遇到高手时, 那些 “感觉” 就要到上面所说的那个搜索树中老老实实层层展开去验算一下。  但是这时, 因为选点极少,搜索树的宽度已经大大减小, 随机抽取一些分支搜到底, 算出来的结果准确率也相应提高了。

很好理解的是, 棋子越下到后面,搜索树的深度越小, 在给定的时间下, 可以抽取验算的分支就更多, 各个选点上的胜负率就算得越准确。 而在前半局时, 搜索树的分支还太多, 也太深, AlphaGo 也算不准确。 对手足够精明老练且运气好的话, 可能可以占到很大的优势。  越往后 AlphaGo 算得越准确, 所以, 人在占优的情况下还绝对不能出错。 这对人来说太难了。 而如果前半局就处于不利, 后半局基本没有机会翻盘, 就抱着学习的心态下到底吧。

基本上, 看那个算法框架就知道, 围棋已经被人工智能 crack 了。 这次的人机对弈, 其实是对这套算法的一次检验。 就算现在输掉, 假以时日, AlphaGo 胜过人类棋手是必然的事。 完全不必悲观或者害怕。 它不过是人类制造出来的工具, 知道它的运作机理就可以驾驭它。 网上流传很广一个说法我觉得很好: 汽车也是人发明的, 人也不必跟汽车去比谁跑得快呀! 所以我一直一直鼓励大家多少去了解一点机器学习的算法。 了解了就知, 机器算得比我们准比我们快是理所当然的事, 输掉也根本不是什么耻辱。 没有我们发明那些算法, 告诉机器怎样去疯狂地算疯狂地归纳, 它们什么也不懂呀!

AlphaGo 的这套算法, 虽然都不是特别新, 但是正如知乎网上的一位科学家所说的, 它的价值在于它的工程实现。 这个富有逻辑和创意的算法组合给其他类似的 “困难” 问题提供了一个光辉样本。 当中许多问题细节在算法工程上的处理方法, 会给其他问题的算法带来启迪。

最后, 我要说的是, 人工智能再发展, 人仍然有作为人的独特价值。 人的逻辑思维, 机器可以模仿归纳。 但是, 人对某物某人某件事一瞬间的情生意动, 或者天长地久的一往情深, 机器无法模拟得到。 让我们在有生之年好好感受。


谢谢阅读, 下次再见。




 

15 comments:

  1. "但是, 人对某物某人某件事一瞬间的情生意动, 或者天长地久的一往情深, 机器无法模拟得到。"
    --沒有感情的超級機器不正正就是AI使人懼怕的地方嗎?當然,倒過來說,有感情的AI可能更可怕。

    ReplyDelete
    Replies
    1. 没有感情的超级机器不太容易令人产生心理上的依赖感觉,我不觉得可怕。 个人认为,“被需要” 是人活在世上的一个很大的意义。 假如 AI 也会自发地产生感情,那么理论上人就不需要人的陪伴, AI 可以解决人类的感情问题。 当这世界上没有任何一个人需要我的时候,我不知道活着还有什么意义。 太恐怖了。

      Delete
  2. iRobot是科幻小說嗎?睇過alpha go的學習模式,應該知道人類已經可以用軟件去模似一個人腦的運作,即使係target specific,但最基礎的software及電子腦理論,人類已經掌握好了。

    「我是符合邏輯的選擇。它計算出了我有45%的機率生還,但是薩拉只有11%。她也是一個人的孩子,11%也許夠了。每個人類都知道怎麼在警察和12歲的小女孩之間抉擇,但是機器人不會。」看下Alpha Go作出的判斷,正正應驗了電影中這句對白。

    如果要提升人工智能的智力,個人覺得仲有幾個大stage需要做:
    1. 架設實體electronic neuro network,即係將neuron連接電子化,開發電子腦
    2. 機械人的電子腦需要有自我擴充能力,唔可以係出廠之時的hardware設定限制AI的腦力進化
    3. 將感情,創造力,道德等更高層次的抽象概念量化並令AI學習

    係以上3樣條件成功前,iRobot仍然非常有可能實現,當中的USR就是今日的Google, Viki就係Google的Cloud center
    由於電子腦係可見的數十年內應該未能有效實現,機械人的大腦是無法進行人腦的巨大運算,但可以經cloud連上大型server去進行計算,包括肢體運動等需要大量腦力進行操作的運算。所以係iRobot的最後,Viki的server被hack後,所有的機械人均會停止運作。

    Google已經開發出機械狗,加上Alpha Go的實驗成功,距離機械人的時代還遠嗎?iRobot的時間設定是2035年,距離今年尚有9年時間,或許機械人的時代,比我們想像中要更早來臨。

    ReplyDelete
    Replies
    1. 你说的那个 “實體electronic neuro network” 在 1995 年的日本电影 《攻壳机动队》 就有出现过。 那部电影, 包括她的续集, 非常有意思。 假如你还没有看过,我强烈建议。 英文名叫做 Ghost in the shell。

      另外,近两年来在硅谷的大 geek 圈里,关于 technological singularity 的讨论非常热烈。 有几位科学家乐观地认为,Singularity 不远了。 但是个人意见趋向保守。 因为人类历史是迂回发展的,这些超级新技术, 在民主国家里会有一个很长的接受过程。这个关于 singularity 的维基词条,我强烈推荐:https://en.wikipedia.org/wiki/Technological_singularity

      Delete
    2. Google 的二足机器人 Altas 最近有新版本发布,又比以前的版本聪明了些,可以看一下:https://youtu.be/rVlhMGQgDkY

      Delete
    3. 世界末日的信息,主再來的日子近了。有沒有人想到,當人類被機器人滅盡到寥寥可數的人數時:如果你是僅存的數個,你該如何求生?

      有興趣,一起討論。這才是重點!

      Delete
  3. This comment has been removed by the author.

    ReplyDelete
  4. http://hk.thenewslens.com/post/297346/
    AlphaGo到底是如何下棋?兼談幾個對AlphaGo的誤解

    ReplyDelete
    Replies
    1. 谢谢我等下慢慢读。

      Delete
    2. 刚刚读完。 他对类神经网络和深度学习的理解比我深得多, 所以表达出来也准确得多。 谢谢告知尹同学的好文! 很高兴终于读到一篇解释比较准确的中文介绍。 以前在知乎上读过 DarkForest 的作者张博士写的对 AlphaGo 的简短介绍, 但是讲得比较笼统。 尹同学的写法比较有系统性。 唯一有一点保留的是: 没错确实那个学习模块, 对局面的判断完全是基于胜率。 人经验多了以后, 对盘面上的胜率判断渐渐形成了直觉。 这样子找出来的规律是不是也是棋理的一种?

      Delete
    3. 我刚刚到尹相志自己的网志上去看了下, 可是他那里好像没法留言。 没什么,不过是想谢谢分享。 那里没法留言我就在这里感谢一下算了。 另外, 他那个文章的链接我也贴到 thestandnews 上去了, 好文就是要让大家多多看到。

      Delete
    4. Google 自己发布的关于 AlphaGo 的白皮书在这里: https://gogameguru.com/i/2016/03/deepmind-mastering-go.pdf

      Delete
  5. 对不起, 刚刚发现我文章里一个低级错误: “这两个中间值再与一下, 得到函数的输出结果 y”, 应该是: “这两个中间值再或一下, 得到函数的输出结果 y”。 别的错误一定还有。 请看到的同学不吝赐教, 谢谢先。

    ReplyDelete
  6. 看到有很多人担心 AI 超过人类什么的。 这个就是无谓的恐慌了。 要消除这种无谓的恐慌, 就去学点人工智能的算法知识。 真正去了解现代的人工智能算法怎样运作, 了解她的可能性与局限。 不一定要做这方面的专家, 多少了解一点, 给自己培养一些基本的判断力也是好的。

    ReplyDelete
  7. 一套类神经网络的入门好教材: http://lumiverse.io/series/neural-networks-demystified

    ReplyDelete