|
今天写的是一篇大杂烩，不过，Berkeley Lab的Dr. Shao有言曰：“大杂烩好，现实就是个大杂烩，界限都是人为划的”。康华兄这几天有点忙，我代他写一点四不像的文章，应一下急。大部分内容很粗浅的，也有少部分需要一定的专业数学知识或者计算机知识。 一、香农和闯迷宫的老鼠 伟大的科学家、信息理论的创立者香农并非在所有方面都是天才，比如他的语言天赋就比较弱，当他力争同时取得电子工程硕士和数学博士学位时，所有条件都合乎要求，除了两门外语：法语和德语。于是香农请了家庭教师(tutor)，全力以赴(buckle down)地练习这两门语言，经过几个月的苦练后，终于通过了两种语言的测试，其中德语测试了两次才通过，最终香农一下子取得两个学位——电子工程硕士和数学博士，按照现在的语言来说，香农就是典型的“学霸”了。 图1 香农和信息熵公式 除了创立信息理论之外，香农也是计算机和人工智能的先驱者，早在1950年，香农就写作了《利用计算机编程博弈》的论文，要知道那时计算机刚发展不久，运行速度非常慢。后来很多计算机博弈方面的编程都遵循香农论文中提出的思想。香农是国际象棋爱好者，1965年受邀到苏联参加会议时，还和苏联的国际象棋世界冠军鲍特维尼克下过一盘棋呢。
图2 第六位国际象棋世界冠军鲍特维尼克(左) 在对弈中 香农的业余爱好也不少，比如杂耍和骑独轮车，此外香农发明了很多稀奇古怪的玩具，其中之一是闯迷宫的电子老鼠。 图3 香农在专心致志地玩杂耍 图4 香农发明的闯迷宫的电子老鼠 香农发明的闯迷宫的电子老鼠当然不是简单地为了好玩，而是研究电子老鼠如何通过自我学习找到走出迷宫的路径。 二、AlphaGo与机器学习 当香农被问及人工智能的前景时，香农指出在当时计算机尽管拥有超强的运算能力，但在处理原始信息方面还没达到人类智能的水准。他认为仅仅在机器复制人类的视觉能力方面就已经是一项相当艰巨的任务了。但是，他补充道：“我认为，几十年后机器智能超越人类是完全可以预期的。”香农真不愧是人工智能方面的先知，在几十年前就预测了AlphaGo和AlphaGo的改进版Master的存在。 2016年3月，围棋世界冠军李世石在于AlphaGo对抗中以1:4败北。
图5 AlphaGo以4:1击败围棋世界冠军李世石 从2016年12月29日晚起，一个注册为“Master”、标注为韩国九段的“网络棋手”连续打败柯洁、朴廷桓、古力等多位世界冠军，在两家围棋对弈网站总战绩54胜0败，后来证实Master即AlphaGo的改进版，曾完爆日本超一流高手的聂卫平也完败在Master之下。 图6 棋圣聂卫平完败Master AlphaGo是通过自我学习不断提高围棋水平的。那么，AlphaGo是如何学习的呢？ AlphaGo团队在《Nature》上发表“Masteringthe game of Go with deep neural networks and tree search”的论文，对AlphaGo的学习过程进行了深入剖析。 一切具有完全信息的博弈都有一个最优价值函数v*(s)，通过递归计算可以得到搜索树上的v*(s)，s为棋子的位置或状态。 对于围棋来说，搜索的复杂度大约为250150，穷尽搜索是不可能的，但是通过对策略p(a|s)的估计，可以大大减少搜索量，p(a|s)表示棋子处于状态s时所有可能走法a的概率分布。 神经网络的训练包括如下几个阶段的机器学习：开始是策略网络pσ的监督学习(supervised learning)，直接从职业围棋高手的对局中学习得来，此外同时训练一个快速策略pπ；然后是策略网络pρ的加强学习(reinforcementlearning)，采用自我对弈的方法优化最后的结果；最后训练价值网络vθ，预测通过加强学习策略网络进行自我对弈的获胜者。AlphaGo很好地将策略网络和价值网络与蒙特卡洛树搜索(Monte Carlo tree search, MCTS)结合起来。 图7 四种策略网络 图8 AlphaGo的神经网络结构 策略网络随机采样状态-动作对 (s, a)，采用随机梯度递增准则来最大化状态s时选择棋步a的似然值，即 对监督学习策略网络进行十三层训练，数据库取自著名的KGS围棋服务器的三千万对局谱(!!)，对，是三千万局！绝对是海量的对局谱。本人从读大学开始喜欢上中国象棋，最好成绩是读硕士研究生时拿过个人冠军，读博士研究生时代表本校参加南京高校研究生(博士研究生和硕士研究生)中国象棋团体赛，拿过团体冠军，可是我估计从学棋到现在，自己打中国象棋谱不会超过3000局。如果我有足够的精力和时间能打谱超过30,000局的话，我也可以成为超一流高手了。据称，AlphaGo每下一盘棋，光电费成本就是3000美元！因此，对付AlphaGo最有效的办法就是“断电”，釜底抽薪，AlphaGo立马从神坛跌落，变成废铁一堆。此外，AlphaGo还不是单机作战，而是运用了云计算，用网络将众多计算机联合起来进行运算。 此外，还有策略网络的加强学习、价值网络的加强学习、策略网络和价值网络中的搜索、对AlphaGo棋力的评估等，Nature文献上都有详细介绍，这里不细述。 三、迷宫中的老鼠与马尔科夫链 前面提到香农的闯迷宫的老鼠，我也有一个闯迷宫的老鼠，不过这个迷宫没有出口，这只倒霉的老鼠只能永远在迷宫里穿来穿去。这是我在《随机信号分析》课程上讲到马尔科夫链时，出给学生做的一道练习题，题目如下： 一只老鼠放在下图所示迷宫内，每个小房间里有若干个通道通向隔壁房间，每单位时间老鼠经过通道跑到相邻小房间里，老鼠从每个小房间的每个通道经过的概率都相等(例如如果老鼠位于房间1，那么它通过每个通道的概率都是1/2)。开始时老鼠位于5号房间里，问经过4单位时间后老鼠分别位于各个房间的概率。老鼠平均位于每个房间的概率各是多少？ 图9 迷宫中的老鼠 老鼠当前位于某个房间的概率，只与前一单位时间老鼠位于哪个房间有关，显然这是一个马尔科夫链。所谓“马尔科夫链”，指随机序列当前时刻取某一状态的概率，只与最近的早先时刻状态有关，而与更早时刻的状态无关，即“过去决定现在而不决定将来”。每个人的成长都是一个马尔科夫链，不是吗？将来的成就只与现在的能力和努力程度有关，与过去的关系是不大的。我在课堂上经常鼓励学生从现在开始发愤图强，不要受过去的影响，因为过去决定现在，而不决定将来。 那么，上面的练习题怎么做呢？这要用到转移概率的概念，转移概率的定义为 即在时刻k随机事件X状态为i的条件下，时刻k + 1随机事件X状态为j的概率。上面定义的是一步转移概率，同样地，也可以定义多步转移概率。 于是，老鼠的转移概率矩阵为
具有P这种形式的矩阵称为“随机矩阵”。 由于老鼠的初始状态为
那么，经过4单位时间后，老鼠分别位于各个房间的概率分布为
即经过4单位时间后，老鼠位于第1和第5个房间的概率分别为1/2，而位于其他房间的概率都为0。 同理，老鼠平均位于每个房间的概率为 P'的计算可以在πPn中取n→∞实现，但是计算发现，当n为奇数时，其值为[0, 1/3, 0, 1/3, 0, 1/3]；当n为偶数时，其值为[1/3, 0, 1/6, 0, 1/2, 0]。因此，综合考虑，老鼠位于1、3、5、这三个房间的概率分别为1/6, 0, 1/12, 0, 1/4，而位于2、4、6、这三个房间的概率都为1/3。 四 矩阵的哈密尔顿-凯莱定理 上面出现计算一个随机矩阵的无穷次方P∞，这里介绍计算Pn的三种方法： 方法一：利用哈密尔顿-凯莱(Hamilton-Caylay)定理，该定理如下： 设 是n阶矩阵A的特征多项式，则
方法二：如果是对称阵，可以用相似矩阵将矩阵对角化；如果是一般的非零矩阵，可以用谱分解；对于任意矩阵，可以用Jordan标准型。 方法三：对于具有遍历性(遍历性的概念可以参考有关教材)的马尔科夫链的转移概率矩阵，由于存在平稳分布，所以一个简单的方法是用MATLAB计算矩阵的一个高次方，比如20次方或者30次方，那么结果的每一行都不变，都是该遍历态马尔科夫链的平稳分布。 |
|
|
