ML-AlphaGo Zero原理浅析


Introduction

当今有很多人工智能系统是使用监督学习的方法进行训练的,它们被训练成可以模仿人类专家去做出决策。然而:

  1. 在很多领域,监督学习的训练数据是昂贵的,不可靠甚至不可用的。
  2. 很多监督学习模型都存在一些性能上的瓶颈。

相比于强化学习方法:

  1. 模型根据机器自己的经验进行训练,原则上是可以超越人类的水准的。
  2. 强化学习可以运用在一些缺乏人类经验的领域中。

Difference

那么这次的Zero与之前各种版本的Go有哪些不同呢?

  1. 算法上,自对弈强化学习,从随机落子开始学习,不使用人类棋谱。之前Go的各种版本是使用了3000w+的人类棋谱。
  2. 数据结构上,只使用黑子白子两种状态。之前包含了这个点的气等信息。
  3. 模型上,只使用了一个神经网络,同时输出policy和value。之前的版本是将policy和value分成了2个神经网络。
  4. 策略上,基于训练好的神经网络,仅仅使用简单的树形搜索。之前的版本使用的是蒙特卡洛走子演算,使用了一个快速走子网络。

Neural Network

Zero使用的神经网络主要由残差块组成,之所以使用残差块是因为残差网络可以具有更深的深度,提高模型的准确率。残差块的结构如下图所示:

其中的weight layer可以理解成卷积神经网络中的卷积层。残差的含义是预测值与观察值的差,我们用F(x)表示,那么残差等于F(x) = H(x) - x,其中H(x)是预测值,x是观察值。实践证明F(x)在某些情况下是比H(x)更好求的,所以我们令我们的网络直接拟合F(x),那么我们最终希望求得的H(x)可以表示成H(x) = F(x)+x,结构如上图所示。

Zero的神经网络我们用\(f_\theta\)来表示,神经网络的输入是棋盘当前的状态,这个状态首先由1919=361维构成,表示棋盘每一个点,然后再17,表示了前7个状态的历史和一些其他的特征,即输入s=191917。

网络的输出分别是p和v。p是指下一步在每个可能位置落子的概率。下一步的落子标记为a,a也是一个361维度的向量,有360个0和1个1构成,1表示落子的地方,可以表示为\(p_a = Pr(a|s)\)。v指的是在s状态下,获胜的评估,取值-1或者1,分别表示输赢。

MCTS And Self-play

神经网络的训练是通过自我博弈进行的,自我博弈又是通过MCTS进行的,所以我们首先介绍一下Zero中的MCTS。结构如下图所示: mcts

图中有Q、U、P、V和N五种变量: Q(s,a):行动价值
U(s,a):\(U(s,a) = c_{puct}P(s,a)\frac{\sqrt{\Sigma_b N(s,b)}}{1+N(s,a)}\),每次都会对p加入噪声,保证随机性
N(s,a):访问次数,每经过一个节点,这个节点的N就+1
P(s,a):同上文中的p,由神经网络 \( f_\theta \) 计算得到
V(s,a):同上文中的v,由神经网络 \(f_\theta\) 计算得到

a. select方法,从当前棋局状态s出发,select过程中选择max{Q+U}的子树,select一直执行,直到遇到叶子节点 \(s_L\) ,叶子节点是一个终局。
b. expand方法,对叶子节点\(s_L\)进行评估,使用的评估器就是当前最新的\(f_\theta\),然后输出p和v,将v存在节点中,p存在边中。
c. backup方法,更新行动价值Q,等于此时root状态s多有子树评估值v的平均值

每走一步子a,都会先执行1600遍abc,每次在计算U的时候都会加入噪声,保证了随机性,所以1600次完全可以走出不同的走法。1600步之后,这个MCTS已经“枝繁叶茂”了,此时我们执行步骤d,输出一个π,算是MCTS的输出。π是一个361维的向量,表示了下一步a走在棋盘每一个位置的概率,选择概率最该的点落子即可。π的计算公式如下: \[ π(a|s_0)=\frac{N(s_0,a)^{\frac{1}{\tau}}}{\Sigma_b N(s_0,b)^{\frac{1}{\tau}}} \] 其中\(\tau\)是一个用来控制N权重大小的控制参数。

那么我们的自对弈过程实际上就是一个不断使用MCTS进行下棋的过程。MCTS相对于神经网络\(f_\theta\)是更加靠谱的,所以我们使用MCTS中产生的数据用来训练神经网络\(f_\theta\)。自对弈过程如下图所示:


其中z是用来标记这一局的输赢,使用-1或者+1来表示。那么在自对弈过程中就会产生一系列的(s,π,z)的数据,我们将其保存下来用来后面训练神经网络。

Neural Network Training

神经网络的结构图如下图所示:


过程可以描述为:

  1. 神经网络初始化\(\theta_0\)
  2. 每一轮都自对弈一局
  3. 在自对弈的过程中,每一步都是用MCTS进行演算,然后保存(s,π,z)
  4. 从许许多多(s,π,z)中采样(假设这一局经过200步结束了,可能有200组(s,π,z),那么采样其中的一部分出来),然后进行训练。训练的原则是最大化\(f_\theta\)计算出的p和MCTS演算出的π的相似度,最小化\(f_\theta\)计算出的v和MCTS演算出的z的差。

损失函数为: \[ l=(z-v)^2 - π^T log(p) + c\rVert \theta \rVert^2 \] 其中c是L2正则化参数,防止过拟合。

性能表现

performance

a. Elo可以理解为一个对“棋力”的评估,越大越强。这个图表示了各个系统的表现。
b. 表示AI系统模仿人类大师的准确路
c. 表示v和真正能赢的评估z之间的均方差

Conclusion

  1. 在某些领域,只给出基本规则的前提下,不需要任何人类经验知识是可以训练出一个性能超过人类的AI系统。
  2. 强化学习可以获得更好的性能。

分享博文


评论博文


Last one :   LintCode-211StringPermutation

Next article :   彻底学会PCA3-最近重构性的推导