上篇主要介绍了概率图模型首先从生成式模型与判别式模型的定义出发引出了概率图模型的基本概念即利用图结构来表达变量之间的依赖关系接着分别介绍了隐马尔可夫模型、马尔可夫随机场、条件随机场、精确推断方法以及LDA话题模型HMM主要围绕着评估/解码/学习这三个实际问题展开论述MRF基于团和势函数的概念来定义联合概率分布CRF引入两种特征函数对状态序列进行评价打分变量消去与信念传播在给定联合概率分布后计算特定变量的边际分布LDA话题模型则试图去推断给定文档所蕴含的话题分布。本篇将介绍最后一种学习算法——强化学习。16、强化学习强化学习Reinforcement Learning简称RL是机器学习的一个重要分支前段时间人机大战的主角AlphaGo正是以强化学习为核心技术。在强化学习中包含两种基本的元素状态与动作在某个状态下执行某种动作这便是一种策略学习器要做的就是通过不断地探索学习从而获得一个好的策略。例如在围棋中一种落棋的局面就是一种状态若能知道每种局面下的最优落子动作那就攻无不克/百战不殆了~若将状态看作为属性动作看作为标记易知监督学习和强化学习都是在试图寻找一个映射从已知属性/状态推断出标记/动作这样强化学习中的策略相当于监督学习中的分类/回归器。但在实际问题中强化学习并没有监督学习那样的标记信息通常都是在尝试动作后才能获得结果因此强化学习是通过反馈的结果信息不断调整之前的策略从而算法能够学习到在什么样的状态下选择什么样的动作可以获得最好的结果。16.1 基本要素强化学习任务通常使用马尔可夫决策过程Markov Decision Process简称MDP来描述具体而言机器处在一个环境中每个状态为机器对当前环境的感知机器只能通过动作来影响环境当机器执行一个动作后会使得环境按某种概率转移到另一个状态同时环境会根据潜在的奖赏函数反馈给机器一个奖赏。综合而言强化学习主要包含四个要素状态、动作、转移概率以及奖赏函数。状态X机器对环境的感知所有可能的状态称为状态空间动作A机器所采取的动作所有能采取的动作构成动作空间转移概率P当执行某个动作后当前状态会以某种概率转移到另一个状态奖赏函数R在状态转移的同时环境给反馈给机器一个奖赏。因此强化学习的主要任务就是通过在环境中不断地尝试根据尝试获得的反馈信息调整策略最终生成一个较好的策略π机器根据这个策略便能知道在什么状态下应该执行什么动作。常见的策略表示方法有以下两种确定性策略πxa即在状态x下执行a动作随机性策略Pπx,a即在状态x下执行a动作的概率。一个策略的优劣取决于长期执行这一策略后的累积奖赏换句话说可以使用累积奖赏来评估策略的好坏最优策略则表示在初始状态下一直执行该策略后最后的累积奖赏值最高。长期累积奖赏通常使用下述两种计算方法16.2 K摇摆赌博机首先我们考虑强化学习最简单的情形仅考虑一步操作即在状态x下只需执行一次动作a便能观察到奖赏结果。易知欲最大化单步奖赏我们需要知道每个动作带来的期望奖赏值这样便能选择奖赏值最大的动作来执行。若每个动作的奖赏值为确定值则只需要将每个动作尝试一遍即可但大多数情形下一个动作的奖赏值来源于一个概率分布因此需要进行多次的尝试。单步强化学习实质上是K-摇臂赌博机K-armed bandit的原型一般我们尝试动作的次数是有限的那如何利用有限的次数进行有效地探索呢这里有两种基本的想法仅探索法将尝试的机会平均分给每一个动作即轮流执行最终将每个动作的平均奖赏作为期望奖赏的近似值。仅利用法将尝试的机会分给当前平均奖赏值最大的动作隐含着让一部分人先富起来的思想。可以看出上述两种方法是相互矛盾的仅探索法能较好地估算每个动作的期望奖赏但是没能根据当前的反馈结果调整尝试策略仅利用法在每次尝试之后都更新尝试策略符合强化学习的思tao维lu但容易找不到最优动作。因此需要在这两者之间进行折中。16.2.1 ε-贪心ε-贪心法基于一个概率来对探索和利用进行折中具体而言在每次尝试时以ε的概率进行探索即以均匀概率随机选择一个动作以1-ε的概率进行利用即选择当前最优的动作。ε-贪心法只需记录每个动作的当前平均奖赏值与被选中的次数便可以增量式更新。16.2.2 SoftmaxSoftmax算法则基于当前每个动作的平均奖赏值来对探索和利用进行折中Softmax函数将一组值转化为一组概率值越大对应的概率也越高因此当前平均奖赏值越高的动作被选中的几率也越大。Softmax函数如下所示16.3 有模型学习若学习任务中的四个要素都已知即状态空间、动作空间、转移概率以及奖赏函数都已经给出这样的情形称为“有模型学习”。假设状态空间和动作空间均为有限即均为离散值这样我们不用通过尝试便可以对某个策略进行评估。16.3.1 策略评估前面提到在模型已知的前提下我们可以对任意策略的进行评估后续会给出演算过程。一般常使用以下两种值函数来评估某个策略的优劣状态值函数VVx即从状态x出发使用π策略所带来的累积奖赏状态-动作值函数QQx,a即从状态x出发执行动作a后再使用π策略所带来的累积奖赏。根据累积奖赏的定义我们可以引入T步累积奖赏与r折扣累积奖赏由于MDP具有马尔可夫性即现在决定未来将来和过去无关我们很容易找到值函数的递归关系类似地对于r折扣累积奖赏可以得到易知当模型已知时策略的评估问题转化为一种动态规划问题即以填表格的形式自底向上先求解每个状态的单步累积奖赏再求解每个状态的两步累积奖赏一直迭代逐步求解出每个状态的T步累积奖赏。算法流程如下所示对于状态-动作值函数只需通过简单的转化便可得到16.3.2 策略改进理想的策略应能使得每个状态的累积奖赏之和最大简单来理解就是不管处于什么状态只要通过该策略执行动作总能得到较好的结果。因此对于给定的某个策略我们需要对其进行改进从而得到最优的值函数。最优Bellman等式改进策略的方式为将策略选择的动作改为当前最优的动作而不是像之前那样对每种可能的动作进行求和。易知选择当前最优动作相当于将所有的概率都赋给累积奖赏值最大的动作因此每次改进都会使得值函数单调递增。将策略评估与策略改进结合起来我们便得到了生成最优策略的方法先给定一个随机策略现对该策略进行评估然后再改进接着再评估/改进一直到策略收敛、不再发生改变。这便是策略迭代算法算法流程如下所示可以看出策略迭代法在每次改进策略后都要对策略进行重新评估因此比较耗时。若从最优化值函数的角度出发即先迭代得到最优的值函数再来计算如何改变策略这便是值迭代算法算法流程如下所示16.4 蒙特卡罗强化学习在现实的强化学习任务中环境的转移函数与奖赏函数往往很难得知因此我们需要考虑在不依赖于环境参数的条件下建立强化学习模型这便是免模型学习。蒙特卡罗强化学习便是其中的一种经典方法。由于模型参数未知状态值函数不能像之前那样进行全概率展开从而运用动态规划法求解。一种直接的方法便是通过采样来对策略进行评估/估算其值函数蒙特卡罗强化学习正是基于采样来估计状态-动作值函数对采样轨迹中的每一对状态-动作记录其后的奖赏值之和作为该状态-动作的一次累积奖赏通过多次采样后使用累积奖赏的平均作为状态-动作值的估计并引入ε-贪心策略保证采样的多样性。在上面的算法流程中被评估和被改进的都是同一个策略因此称为同策略蒙特卡罗强化学习算法。引入ε-贪心仅是为了便于采样评估而在使用策略时并不需要ε-贪心那能否仅在评估时使用ε-贪心策略而在改进时使用原始策略呢这便是异策略蒙特卡罗强化学习算法。16.5 AlphaGo原理浅析本篇一开始便提到强化学习是AlphaGo的核心技术之一刚好借着这个东风将AlphaGo的工作原理了解一番。正如人类下棋那般“手下一步棋心想三步棋”Alphago也正是这个思想当处于一个状态时机器会暗地里进行多次的尝试/采样并基于反馈回来的结果信息改进估值函数从而最终通过增强版的估值函数来选择最优的落子动作。其中便涉及到了三个主要的问题1如何确定估值函数2如何进行采样3如何基于反馈信息改进估值函数这正对应着AlphaGo的三大核心模块深度学习、蒙特卡罗搜索树、强化学习。1.深度学习拟合估值函数由于围棋的状态空间巨大像蒙特卡罗强化学习那样通过采样来确定值函数就行不通了。在围棋中状态值函数可以看作为一种局面函数状态-动作值函数可以看作一种策略函数若我们能获得这两个估值函数便可以根据这两个函数来完成(1)衡量当前局面的价值(2)选择当前最优的动作。那如何精确地估计这两个估值函数呢这就用到了深度学习通过大量的对弈数据自动学习出特征从而拟合出估值函数。2.蒙特卡罗搜索树采样蒙特卡罗树是一种经典的搜索框架它通过反复地采样模拟对局来探索状态空间。具体表现在从当前状态开始利用策略函数尽可能选择当前最优的动作同时也引入随机性来减小估值错误带来的负面影响从而模拟棋局运行使得棋盘达到终局或一定步数后停止。3.强化学习调整估值函数在使用蒙特卡罗搜索树进行多次采样后每次采样都会反馈后续的局面信息利用局面函数进行评价根据反馈回来的结果信息自动调整两个估值函数的参数这便是强化学习的核心思想最后基于改进后的策略函数选择出当前最优的落子动作。在此强化学习就介绍完毕。同时也意味着大口小口地啃完了这个西瓜十分记得去年双11之后立下这个Flag现在回想起来大半年的时间里在嚼瓜上还是花费了不少功夫。有人说当你阐述的能让别人看懂才算是真的理解有人说在写的过程中能发现那些只看书发现不了的东西自己最初的想法十分简单当健忘症发作的时候如果能看到之前按照自己思路写下的文字回忆便会汹涌澎湃一些~