机器学习算法地图分享

机器学习算法地图分享

转自微信公众号sigaicn,如有侵权,联系本人,会在48小时内删除。

image.png
image.png
image.png
image.png

强化学习是一类特殊的机器学习算法,如果说有监督学习和无监督学习是要根据预测函数来确定输出标签信息或者聚类类别、降维后的向量,则强化学习算法是要根据当前的状态确定要执行的动作。

强化学习与有监督学习和无监督学习的目标不同,它借鉴于行为主义心理学。算法要解决的问题是智能体在环境中怎样执行动作以获得最大的累计奖励。对于自动行驶的汽车,强化学习算法控制汽车的动作,保证安全行驶。智能体指强化学习算法,环境是类似车辆当前状态与路况这样的由若干参数构成的系统,奖励是我们期望得到的结果,如汽车正确的在路面上行驶而不发生事故。

很多控制、决策问题都可以抽象成这种模型。和有监督学习不同,这里没有标签值作为监督信号,系统只会给算法执行的动作一个评分反馈,这种反馈一般还具有延迟性,当前的动作所产生的后果在未来才会完全得到,另外未来还具有随机性。

强化学习要解决的问题可以抽象成马尔可夫决策过程(Markov Decision Process,简称MDP)。马尔可夫过程的特点是系统下一个时刻的状态由当前时刻的状态决定,与更早的时刻无关。与马尔可夫过程不同的是,在 MDP 中系智能体可以执行动作,从而改变自己和环境的状态,并且得到惩罚或奖励。马尔可夫决策过程可以表示成一个五元组:

{S,A,Pa,Ra,γ}

其中S 和A 分别为状态和动作的集合。假设 t 时刻状态为St,智能体执行动作 a,下一时刻进入状态St

。下一时刻的状态由当前状态以及当前采取的动作决定,是一个随机性变量,这一状态转移的概率为:

(pa(s,s′)=p(st+1=s′|st=s,at=a)

这是当前状态为 s 时行动作 a,下一时刻进入状态s

的条件概率。这个公式表明下一时刻的状态与更早时刻的状态和动作无关,状态转换具有马尔可夫性。有一种特殊的状态叫做终止状态(也称为吸收状态),到达该状态之后不会再进入其他后续状态。对于围棋,终止状态是一局的结束。

执行动作之后,智能体会收到一个立即回报:

Ra(s,s′)

立即回报和当前状态、当前采取的动作以及下一时刻进入的状态有关。在每个时刻 t,智能体选择一个动作at执行,之后进入下一状态 st+1

,环境给出回报值。智能体从某一初始状态开始,每个时刻选择一个动作执行,然后进入下一个状态,得到一个回报,如此反复:

s0→a0S1→a1S2→a2S3⋯

问题的核心是执行动作的策略,它可以抽象成一个函数p,定义了在每种状态时要选择执行的动作。这个函数在状态 s 所选择的动作为:

a = p ()

这是确定性策略。对于确定性策略,在每种状态下智能体要执行的动作是唯一的。另外还有随机性策略,智能体在一种状态下可以执行的动作有多种,策略函数给出的是执行每种动作的概率:

π(a|s)=p(a|s)

即按概率从各种动作中选择一种执行。策略只与当前所处的状态有关,于历史时间无关,在不同时刻对于同一个状态所执行的策略是相同的。

强化学习的目标是要达到我们的某种预期,当前执行动作的结果会影响系统后续的状态,因此需要确定动作在未来是否能够得到好的回报,这种回报具有延迟性。对于围棋,当前走的一步棋一般不会马上结束,但会影响后续的棋局,需要使得未来赢的概率最大化,而未来又具有随机性,这为确定一个正确的决策带来了困难。

选择策略的目标是按照这个策略执行后,在各个时刻的累计回报值最大化,即未来的预期回报。按照某一策略执行的累计回报定义为:

∑+∞t=0γtRat(st,st+1)

这里假设状态转移概率以及每个时刻的回报是已知的,算法要寻找最佳策略来最大化上面的累计回报。

如果每次执行一个动作进入的下一个状态是确定的,则可以直接用上面的累计回报计算公式。如果执行完动作后进入的下一个状态是随机的,则需要计算各种情况的数学期望。为此定义状态价值函数的概念,它是在某个状态 s 下,按照策略p 执行动作,累计回报的数学期望。状态价值函数的计算公式为:

Vπ(s)=∑spπ(s)(s,s′)(Rπ(s)(s,s′)+γVπ(s′))

动作价值函数是智能体按照策略p 执行,在状态 s 时执行具体的动作 a 后的预期回报,计算公式为:

Qπ(s,a)=∑spa(s,s′)(Ra(s,s′)+γVπ(s′))

除了指定初始状态与策略之外,还指定了在状态 s 时执行的动作 a。这个函数衡量的是给定某一策略,在某一状态时执行各种动作的价值。

给定一个策略,可以用动态规划算法计算它的状态价值函数,即策略评估( Policy Evaluation)。在每种状态下执行的动作有多种可能,需要对各个动作计算数学期望。按照定义,状态价值函数的计算公式为:

Vπ(s)=∑aπ(a|s)∑spπ(s)(s,s′)(Rπ(s)(s,s′)+γVπ(s′))

求解时使用迭代法,首先为所有状态的价值函数设置初始值,然后用公式更新所有状态的价值函数,第 k 次迭代时的更新公式为:

Vk+1(s)=∑aπ(a|s)∑spa(s,s′)(Ra(s,s′)+γVk(s′))

算法最后会收敛到真实的价值函数值。

策略评估的目的是为了得到更好的策略,即策略改进。策略改进通过按照某种规则对当前策略进行调整,得到更好的策略。

策略迭代是策略评估和策略改进的结合。从一个初始策略开始,不断的改进这个策略达到最优解。每次迭代时首先用策略估计一个策略的状态价值函数,然后根据策略改进方案调整该策略,再计算新策略的状态价值函数,如此反复直到收敛。这一过程如下图所示:

image.png

在策略迭代算法中,策略评估的计算量很大,需要多次扫描所有状态并不断的更新状态价值函数。实际上不需要知道状态价值函数的精确值也能迭代到最优策略,值迭代就是其中的一种方法。

根据贝尔曼最优化原理,如果一个策略是最优策略,整体最优的解局部一定也最优,因此最优策略可以被分解成两部分:从状态 s  s 采用了最优动作,在状态 s 是采用的策略也是最优的。根据这一原理,每次选择当前回报和未来回报之和最大的动作,价值迭代的更新公式为:

Vk+1(s)=maxaspa(s,s′)(Ra(s,s′)+γVk(s′))

策略迭代算法和价值迭代算法虽然都可以得到理论上的最优解,但是它们的计算过程依赖于状态转移概率以及回报函数。对于很多应用场景,我们无法得到准确的状态模型和回报函数。因此前面介绍的这两种算法在实际问题中使用价值有限。

对于无法建立精确的环境模型的问题,我们只能根据一些状态、动作、回报值序列样本进行计算,估计出价值函数和最优策略。基本思想是按照某种策略尝试执行不同的动作,观察得到的回报,然后进行改进。

蒙特卡洛算法和时序差分算法是解决这这类问题的两种方法。蒙特卡洛算法是一种随机数值算法,它通过使用随机数来近似解决某些难以直接求解的问题。在强化学习中,蒙特卡洛算法可以根据样本得到状态价值函数以及动作价值函数的估计值,用于近似数学期望值。

在上面的例子中,样本是一些随机的点,在用于计算强化学习的价值函数时,样本是一些片段。在这里先定义片段(episode)的概念,它是从某一状态开始,执行一些动作,直到终止状态为止的一个完整的状态和动作序列,这类似于循环神经网络中的时间序列样本。蒙特卡洛算法从这些片段样本中学习,估算出状态价值函数和动作价值函数。实现时的做法非常简单:

按照一个策略执行,得到一个状态和回报序列,即片段。多次执行,得到多个片段。接下来根据这些片段样本估计出价值函数。

蒙特卡洛算法需要使用完整的片段进行计算,这在有些问题中是不现实的,尤其是对于没有终止状态的问题。时序差分算法(Temporal Difference learning,简称 TD 学习)在执行一个动作之后就进行价值函数估计,无需使用包括终止状态的完整片段,它结合了蒙特卡洛算法与动态规划算法的思想。与蒙特卡洛算法一样,TD 算法无需依赖状态转移概率,直接采样计算。TD 算法用贝尔曼方程估计价值函数的值,然后构造更新项。迭代更新公式为:

() = V () + a (+ g( )- V ())

算法用当前动作的立即回报值与下一状态当前的状态价值函数估计值之和构造更新项,更新本状态的价值函数:

+ g(s )

在上式中没有使用状态转移概率,而是和蒙特卡洛算法一样随机产生一些样本来进行计算,因此称为无模型的算法。用于估计状态价值函数时,算法的输入为策略,输出为该策略的状态值函数。

Sarsa 算法用于估计给定策略下的动作价值函数,同样是每次执行一个动作之后就进行更新。它的迭代更新公式为:

(, a ) = Q (, a ) + a (+ g Q ( , a  )- Q (, a ))

由于更新值的构造使用了{,,,‘,‘}这5个变量,因此被命名为Sarsa算法。根据所有状态-动作对的价值函数可以得到最优策略。Q 学习算法估计每个动作价值函数的最大值,通过迭代可以直接找到价值函数的极值,从而确定最优策略,类似于价值迭代算法的思想。

Q(s,a)=Q(s,a)+α(R+γmaxaQ(s′,a′)−Q(s,a))

实现时需要根据当前的动作价值函数的估计值为每个状态选择一个动作来执行,这里有两种方案。第一种方案是随机选择一个动作,这称为探索(exploration)。第二种方案是根据当前的动作函数值选择一个价值最大的动作执行:

a=maxaQ(s,a′)

这称为利用(exploitation)。第三种方案是二前两者的结合,即 e -贪心策略。执行完动作之后,进入状态 s ,然后寻找状态 s 下所有动作的价值函数的极大值,构造更新项。算法最终会收敛到动作价值函数的最优值。用于预测时,在每个状态下选择函数值最大的动作执行,这就是最优策略,具体实现时同样可以采用 e -贪心策略。

前面介绍的算法只能用于状态和动作的集合是有限的离散基且状态和动作数量较少的情况,状态和动作需要人工预先设计。实际应用中的场景可能会很复杂,很难定义出离散的状态;即使能够定义,数量也非常大,无法用数组存储。用一个函数来逼近价值函数或策略函数成为解决这个问题的一种思路,函数的输入是原始的状态数据,函数的输出是价值函数值或策略函数值。

在有监督学习中,我们用神经网络来实现分类或回归函数,同样的,也可以用神经网络可来拟合强化学习中的价值函数和策略函数,这就是深度强化学习的基本思想。在这里,神经网络被用于从原始数据如图像中直接预测出函数值。

在 Q 学习中用表格存储动作价值函数的值,如果状态和动作太多这个表将非常大,在某些应用中也无法列举出所有的状态形成有限的状态集合。解决这个问题的方法是用一个函数来近似价值函数,深度 Q 学习用神经网络来近似动作价值函数。网络的输入是状态,输出是各种动作的价值函数值。下面用一个例子进行说明。算法要实现自动驾驶,将当前场景的图像作为状态,神经网络的输入是这种图像,输出是每个动作对应的 Q 函数值,这里的动作是左转,右转,刹车,加油门等。显然,神经网络输出层的尺寸与动作数相等。

DeepMind 提出了一种用深度 Q 解决 Atari 游戏的方法,使用卷积神经网络拟合 Q 函数,称为深度 Q 网络(简称 DQN)。网络的输入为经过处理后游戏图像画面,原始的画面是210×160 的彩色图像,每个像素的值为[0, 255]之间的整数,所有可能的状态数为:

256210×160×3

这个规模的矩阵无法直接用表格存储。网络的输出值是在输入状态下执行每个动作的 Q 函数值,在这里有 18 个值,代表游戏中的 18 种动作。神经网络用于近似最优 Q 函数:

Q(s,a,θ)≈Qπ(s,a)

其中q 是网络的参数。网络结构如下图所示:

image.png

关键问题是训练样本标签值的与损失函数的设计。这里的目标是逼近最优策略的 Q 函数值,因此可以采用 Q 学习的做法。损失函数用神经网络的输出值与 Q 学习每次迭代时的更新值构造,定义为:

L(θ)=E((R+γmaxa′(s′,a′,θ)−Q(s,a,θ))2)

在这里采用了欧氏距离损失,是神经网络的输出值与 Q 函数估计值之间的误差,与 Q 学习中的更新项相同。另一个问题是如何得到训练样本,和 Q 学习类似,可以通过执行动作来生成样本。实现时,用当前的神经网络进行预测,得到所有动作的价值函数,然后按照策略选择一个动作执行,得到下一个状态以及回报值,以此作为训练样本。

这里还使用了经验回放(Experience Replay)技术。神经网络要求训练样本之间独立同分布,而 Atari 游戏的训练样本是一个时间序列,前后具有相关性。解决这个问题的做法是经验池,将样本存储在一个集合中,然后从中随机采样得到每次迭代所用的训练样本。

深度 Q 学习基于动作价值函数,它用神经网络拟合 Q 函数的最优值,通过函数值间接得到最优策略。如果动作集合是连续的或维数很高,这种方法将面临问题。例如算法要控制机器人在 x  y 方向上移动,每个方向上的移动距离是[-1.-, +1.0]之间的实数,移动距离无法穷举出来离散化成动作集合,因此无法使用基于价值函数的方法。此时可以让神经网络根据输入的状态直接输出 x  y 方向的移动距离,从而解决连续性动作问题。

策略梯度(Policy Gradient)算法[6]是这种思想的典型代表,策略函数网络的输入是图像之类的原始数据。策略函数根据这个输入状态直接预测出要执行的动作:

a = p (s;q )

其中q 是神经网络的参数。对于随机性策略,神经网络的输出是执行每种动作的概率值:

π(a|s;θ)=p(a|s;θ)

这是一种更为端到端的方法,神经网络的映射定义了在给定状态的条件下执行每种动作的概率,根据这些概率值进行采样可以得到要执行的动作。对于离散的动作,神经网络的输出层神经元数量等于动作数,输出值为执行每个动作的概率。对于连续型动作,神经网络的输出值为高斯分布的均值和方差,动作服从此分布。

这里的关键问题是构造训练样本和优化目标函数,在这两个问题解决之后剩下的就是标准的神经网络训练过程。在样本生成问题上,策略梯度算法采用的做法和 DQN 类似,用神经网络当前的参数对输入状态进行预测,根据网络的输出结果确定出要执行的动作,接下来执行这个动作,得到训练样本,并根据反馈结果调整网络的参数。如果最后导致负面的回报,则更新网络的参数使得在面临这种输入时执行此动作的概率降低;否则加大这个动作的执行概率。策略梯度算法在优化目标上和深度 Q 学习不同,深度 Q 学习是逼近最优策略的 Q 函数,而策略梯度算法是通过最大化回报而逼近最优策略。

Comments ( 3 )

  1. Reply湘南一枝花
    不是特别懂,有没有视频教程推荐
  2. ReplyABC
    早点睡吧
  3. Reply文文姐
    希望写一些代码补充一下

Leave a reply

Your email address will not be published.

You may use these HTML tags and attributes:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>