Post Detail

大话增强学习

Hugiss  

大话逻辑回归一文中,我们说到如果只能选择一个机器学习算法,我选择逻辑回归。那么如果可以选择两个呢?第二个算法我选择增强学习。

本文由Hugiss.com原创,转载请注明出处。

机器学习的类别

机器学习基本可以分为这么三类。

  • 监督学习或半监督学习
  • 非监督学习
  • 增强学习

前两者更倾向于环境感知,而增强学习更倾向于智能决策。今天我们就来学习一下增强学习,也称强化学习,Reinforcement Learning。

增强学习和监督学习的区别是,

  • 监督学习就像‘体育老师教体育课’,老师告诉你该做什么动作。
  • 增强学习就像‘数学老师给体育课代课’,老师也不知道应该做什么动作,但是老师会评价谁做得好,什么动作好,什么动作差。

增强学习的理论基础是马尔科夫过程。我们挨个介绍。

马尔科夫过程(Markov process)

说人话,意思就是我由现在很穷变为未来很富的概率,和我过去很穷或很富没关系。

好了,说完了。

马尔科夫决策过程(Markov Decision Process)

MDP模型

马尔科夫决策过程呢,就是要考虑如何由现在很穷变为未来很富。总得做点什么,比如努力学习买彩票等动作。为方便描述,我们定义几个变量

S状态集合: {s1:现在很穷,s2:未来很富}

A动作集合: {a1:努力学习,a2:买彩票,a3:撩妹}

我们一般假设(本假设不一定成立)s1 -> a1 -> s2的概率比s1 -> a2 -> s2的概率要高。于是,我们有了概率P(s',s,a)即在s进行a到达s'的概率。本文中我们的P都是1,不是1的情况也很好处理,概率加权即可。

由于努力学习不一定比买彩票有效,但是坚持不懈的努力学习总体而言还是比买彩票要好,所以家长们会在你努力学习后立刻给个小奖励R。一般而言R(a1)>R(a2),R(a1)>R(a3)。

于是我们有了S, A, P, R。

大体讲完了,这个就是马尔科夫决策过程的模型。

然而,有时候我们不知道P,或者R;甚至有时候S或A都太多了。于是马尔科夫决策过程(简称MDP)又分为

  • 知道所有决策信息(S, A, P, R)
  • 知道部分决策信息
    • 只知道(S, A)
    • 只知道部分S(比如AlphaGo下围棋时,S超级大)

MDP决策

前面讲了模型,这里讲决策。即,我现在这样了,下一步该怎么办呢?我们需要有个策略(Policy)来指导做下一步动作。

对于低等动物,虽然它们也有一定的智商,可以进行决策,但是它们考虑的不长远。如金鱼永远只有一个策略,即有吃的就吃,喂多了金鱼就自己吃死了。人就不会这样,因为人考虑的更长远。这里,金鱼在做吃还是不吃这个决策时,只考虑了当前的激励R,没有考虑长远。

而人呢,人会考虑很多步,比如天色尚早晚点吃,或者太晚了吃了要变胖要不健康。即人考虑的是长期激励,即现在决策的激励和未来可能决策的激励都加起来。

longtermreward

然而,这就有问题了。不管我如何决策,这个加起来的值可能都很大,那我该如何决策呢?于是,从直觉出发,我们改进一下策略,过于考虑长远的东西没意义。我们即不只考虑眼前的激励,也不把所有的未来都严格考虑进来。我们加权,权重系数r在[0,1)之间。0就是金鱼,1就是脑瘫,0.5看着就不错。

weightedreward

上面这个公式就是价值函数v(s),即在当前s下,我采取最优策略一直下去,可以得到的总的奖励。

  • 有时候我们知道大结局,即v(s),但不知道各个R
  • 有时候我们知道各个R进而可以计算出v(s)。

可以看出来v(s)和a没有关系,即v(s)衡量的是当前状态的好坏,有点像下棋下到某个局势时,我们说这个有利于哪一方。

说人话,就是v(我现在很穷)肯定小于v(我现在很富)。

那如何做决策呢?我们得把a加进来。既然v(s)衡量了s的优劣,那结合R(s,a),P(s,a,s')是不是就可以和v(s')扯上关系了呢?怎么搞呢?听好了,重点来了。

我们假设到了s'后继续使用最优策略,既假设我们已经知道了v(s')。在s到s'这个过程,我们引入自变量a。于是R0本来表示按照最优策略选择的a,现在我们把R0变成以a为自变量的函数。

qfunction

上式就是针对动作的价值函数q(s,a)。相当于描述了,在现在这盘棋上,我这么走的优劣。那么v(s)和q(s,a)有什么关系呢?想象一下,在s时,我穷尽了各种走法a,最后得到了最佳走法,则可以认为v(s)就是最佳走法时的q(s,a)。即v(s)=max(q(s,a))。而q(s,a)=R(s,a)+r(v(s')),于是,q(s,a)=R(s,a) + r * max(q(s’,a‘)))。这么一推导,是不是很简洁?连Bellman方程都没碰就把结果给搞出来了。其实就是个动态规划啦,我们吃货公司员工入门必备。

qlearning 这个就是大名鼎鼎的Q-Learning算法(严格来讲,Q-learning是一类算法)的一部分

通俗解释,就是在当前棋局s,我选择a进入下一个棋局s'的评分,是我获得的行动激励R(s,a)和状态s'评分之和。r系数权衡了短期激励和长期激励。

如何选择最佳a呢?到Q矩阵里面找到s行,选最大的那个q(s,a)所对应的a即可,即argmax q(s,a)

如何迭代q(s,a)

如果我们知道了已有的q(s',a')和R(s,a),自然我们就可以计算出q(s,a)。但是,这是个鸡生蛋的问题。我们如何更新q(s,a)呢?这个问题其实等价于问Q learning是什么?

qlearupdate

很通俗地解释一下,相当于以前有个old的值,现在又发现了个new的值,该用哪一个呢?只用新的,相当于彻底放弃已有经验。只用老的,相当于不更新。各取一半,相当于取个平均。那就老规矩,加个权重,引入了权重a,得到了更新公式。a也被称为学习速率

小结

总结一下,这个思想就是根据R(s,a)来迭代计算q(s,a),进而得到策略(argmax q)和v(s)。这是一种value function based algorithm

增强学习是一类高级算法,人生也是如此。我们不能只看短期利益,需要权衡长期利益,从而变成人生大赢家。有些人蠢,就是不意识到长期利益的重要性。比如,有些人找工作时一看这个工作给的工资多,就去干了。另一些人还会考虑我干了这个工作以后会如何发展。这就是潜移默化地使用了增强学习做决策。

本文我们介绍了增强学习最重要的两个公式。

qlearning
qlearupdate

根据这个公式,机器人(Agent)不停的以一定策略探索环境,得到反馈,进而改进策略。这就是增强学习的基本思想,增强学习是一大类算法。

可如果我们不知道R(s,a),该怎么办呢?请关注Hugiss人工智能栏目的后续文章。

参考文献

Davlid Silver的Tutorial 必读材料

David Silver的教学资料

David Silver目前(2017)是Google员工(严格来讲,是AlphaBet旗下DeepMind员工)。David Silver早年搞了个游戏公司做CTO,后来公司黄了,他去读了个RL方面的博士并任教一段时间。后来加入了DeepMind,再后来被Google收购了。他的教学资料很严谨易懂。

Show Disqus Comments