强化学习的数学原理学习笔记 - 时序差分学习(Temporal Difference)

2024-01-07 20:37:44


本系列文章介绍强化学习基础知识与经典算法原理,大部分内容来自西湖大学赵世钰老师的强化学习的数学原理课程(参考资料1),并参考了部分参考资料2、3的内容进行补充。

系列博文索引:(更新中)

参考资料:

  1. 【强化学习的数学原理】课程:从零开始到透彻理解(完结)(主要)
  2. Sutton & Barto Book: Reinforcement Learning: An Introduction
  3. 机器学习笔记

*注:【】内文字为个人想法,不一定准确

概览:RL方法分类

图源:https://zhuanlan.zhihu.com/p/36494307
*图源:https://zhuanlan.zhihu.com/p/36494307

时序差分学习(Temporal Difference,TD)

先前的内容介绍了如何在无模型(model-free)的情况下,基于蒙特卡洛方法(Monte Carlo,MC)来进行策略评估。实际上,无模型的强化学习方法还有另外一个重要分支:时序差分学习(Temporal Difference,TD)。

最基础的时序差分学习估计状态值,而后续提出的Sarsa和Q-learning方法则直接对动作值进行估计。

*注:时序差分的原理部分依赖于随机优化理论,可参阅本文后续的随机近似(SA)&随机梯度下降(SGD)章节。

TD for state values

Basic TD

最原始的TD Learning算法:在策略评估中估计给定策略 π \pi π的状态值 v π v_\pi vπ?,本质上是在无模型的情况下求解贝尔曼方程(解法类似于RM算法,详见后一章节)。

  • v t + 1 ( s t ) = v t ( s t ) ? α ( s t ) [ v t ( s t ) ? [ r t + 1 + γ v t ( s t + 1 ) ] ] v_{t+1}(s_t) = v_t(s_t) - \alpha(s_t) [v_t (s_t) - [r_{t+1} + \gamma v_t(s_{t+1})] ] vt+1?(st?)=vt?(st?)?α(st?)[vt?(st?)?[rt+1?+γvt?(st+1?)]]
    • * α t ( s t ) \alpha_t (s_t) αt?(st?)是学习率,通常设为很小的常数
  • v t + 1 ( s ) = v t ( s ) , ? s ≠ s t v_{t+1} (s) = v_t (s), \quad \forall s \neq s_t vt+1?(s)=vt?(s),?s=st?

t = 0 , 1 , 2 , ? t =0, 1,2, \cdots t=0,1,2,?时刻,更新被访问状态 s t s_t st?的状态值估计 v t + 1 ( s t ) v_{t+1}(s_t) vt+1?(st?),但不更新其他未访问状态的状态值估计。

TD的目标:使得估计值 v t ( s t ) v_{t}(s_t) vt?(st?)接近 v ˉ t \bar{v}_t vˉt?(*对于估计动作值的TD算法而言,是使得 q t ( s t , a t ) q_t(s_t, a_t) qt?(st?,at?)接近于 q ˉ t \bar{q}_t qˉ?t?
v t + 1 ( s t ) ? new?estimation = v t ( s t ) ? current?estimation ? α ( s t ) [ v t ( s t ) ? [ r t + 1 + γ v t ( s t + 1 ) ? TD?target? v ˉ t ] ? TD?error? δ t ] \underbrace{v_{t+1}(s_t)}_{\text{new estimation}} = \underbrace{v_t(s_t)}_{\text{current estimation}} - \alpha(s_t) [\overbrace{v_t (s_t) - [\underbrace{r_{t+1} + \gamma v_t(s_{t+1})}_{\text{TD target } \bar{v}_t}]}^{\text{TD error } \delta_t} ] new?estimation vt+1?(st?)??=current?estimation vt?(st?)???α(st?)[vt?(st?)?[TD?target?vˉt? rt+1?+γvt?(st+1?)??] ?TD?error?δt??]

  • TD target v ˉ t = r t + 1 + γ v t ( s t + 1 ) \bar{v}_t = r_{t+1} + \gamma v_t(s_{t+1}) vˉt?=rt+1?+γvt?(st+1?)
  • TD error δ t = v t ( s t ) ? [ r t + 1 + γ v t ( s t + 1 ) ] = v t ( s t ) ? v ˉ t \delta_t = v_t (s_t) - [r_{t+1} + \gamma v_t(s_{t+1})] = v_{t}(s_t) - \bar{v}_t δt?=vt?(st?)?[rt+1?+γvt?(st+1?)]=vt?(st?)?vˉt?
    • t t t t + 1 t+1 t+1两个时刻的difference
    • 描述了 v t v_t vt? v π v_\pi vπ?之间的差异( v t v_t vt?是对 v π v_\pi vπ?的估计):若 v t = v π v_t = v_\pi vt?=vπ?,则 δ t = 0 \delta_t = 0 δt?=0

这种最原始的TD算法不能用来估计动作值,也不能用来搜索最优策略。

*注:不同文献和资料中的公式表述存在差异,比如Sutton书中(参考资料2)的TD形式如下:
V ( S t ) ← V ( S t ) + α [ R t + 1 + γ V ( S t + 1 ) ? V ( S t ) ] V(S_t) \larr V(S_t) + \alpha [R_{t+1} + \gamma V(S_{t+1}) - V(S_t)] V(St?)V(St?)+α[Rt+1?+γV(St+1?)?V(St?)]

TD算法本质上是求解贝尔曼期望方程(Bellman Expectation Equation):
v π ( s ) = E [ R + γ v π ( S ′ ) ∣ S = s ] , s ∈ S v_\pi(s) = \mathbb{E} [R + \gamma v_\pi (S') | S = s], \quad s \in S vπ?(s)=E[R+γvπ?(S)S=s],sS

TD算法的收敛性:如满足以下条件,则当 t → ∞ t\rarr\infin t时, v t ( s ) v_t(s) vt?(s)可以收敛至 v π ( s ) v_\pi(s) vπ?(s)(w.p.1, ? s ∈ S \forall s \in \mathcal{S} ?sS
? s ∈ S \forall s \in \mathcal{S} ?sS ∑ t a t ( s ) = ∞ \textstyle\sum_{t} a_t(s) = \infin t?at?(s)= ∑ t a t 2 ( s ) < ∞ \textstyle\sum_{t} a_t^2(s) < \infin t?at2?(s)<
*需要对每个状态访问很多次(理论上是无穷次)

🟡TD vs. MC

TD / SarsaMC
Online:可以使用每步的reward,立即更新状态/动作值Offline:需要等待每个episode数据采集完毕
Continuing & Episodic tasks仅Episodic tasks
Bootstrapping:依赖于初始估计和历史估计Non-bootstrapping:直接估计,不依赖初始值
Lower estimation variance:只依赖少数几个随机变量Higher estimation variance:依赖的随机变量较多

TD估计的期望是有偏的,因为其依赖于初始估计(Bootstrapping),但随着数据量的增加,最终会收敛到正确的估计值;相反,MC的期望是无偏估计。

🟦Sarsa (TD for action values)

Basic Sarsa

目标:估计给定策略 π \pi π的动作值 q π ( s , a ) q_\pi(s, a) qπ?(s,a)
数据: { ( s t , a t , r t + 1 , s t + 1 , a t + 1 ) } \{(s_t, a_t, r_{t+1}, s_{t+1}, a_{t+1})\} {(st?,at?,rt+1?,st+1?,at+1?)}

SARSA(State-Action-Reward-State-Action) 算法:

  • q t + 1 ( s t , a t ) = q t ( s t , a t ) ? α t ( s t , a t ) [ q t ( s t , a t ) ? [ r t + 1 + γ q t ( s t + 1 , a t + 1 ) ] ] q_{t+1} (s_{t}, a_t) = q_{t} (s_{t}, a_t) - \alpha_t (s_t, a_t) [q_{t} (s_t, a_t) - [r_{t+1} + \gamma {\color{red} q_t (s_{t+1}, a_{t+1})}]] qt+1?(st?,at?)=qt?(st?,at?)?αt?(st?,at?)[qt?(st?,at?)?[rt+1?+γqt?(st+1?,at+1?)]]
  • q t + 1 ( s , a ) = q t ( s , a ) , ? ( s , a ) ≠ ( s t , a t ) q_{t+1} (s, a) = q_t (s, a), \quad \forall (s, a) \neq (s_t, a_t) qt+1?(s,a)=qt?(s,a),?(s,a)=(st?,at?)
    • α t ( s t , a t ) \alpha_t (s_t, a_t) αt?(st?,at?)是取决于 s t s_t st? a t a_t at?的学习率

*与原始TD算法的差异:将公式中的 v ( s t ) v(s_t) v(st?)替换为 q ( s t , a t ) q(s_t, a_t) q(st?,at?),因此Sarsa是TD算法的动作值估计的版本

Sarsa求解贝尔曼期望方程的动作值形式:
q π ( s , a ) = E [ R + γ q π ( S ′ , A ′ ) ∣ s , a ] , ? s , a q_\pi(s, a) = \mathbb{E} [R + \gamma q_\pi (S', A') | s, a], \quad \forall s, a qπ?(s,a)=E[R+γqπ?(S,A)s,a],?s,a
其中, R ~ p ( R ∣ s , a ) R \sim p (R | s ,a) Rp(Rs,a) S ′ ~ p ( S ′ ∣ s , a ) S' \sim p(S' | s, a) Sp(Ss,a) A ′ ~ π ( A ′ ∣ S ′ ) A' \sim \pi(A' | S') Aπ(AS) ~ \sim 表示服从某种概率分布)。

注意到Sarsa所依赖的5个变量中,在给定 s t s_t st? a t a_t at?的情况下,只有 a t + 1 a_{t+1} at+1?依赖于策略 π t \pi_t πt?,而 r t + 1 r_{t+1} rt+1? s t + 1 s_{t+1} st+1?本身并不依赖于策略,而是依赖于转移概率分布(通过采样确定)。

Sarsa收敛性类似于TD,略。

Sarsa+策略提升的完整算法:(也属于GPI框架)

  • 更新动作值(策略评估):Sarsa的公式,略
  • 更新策略(策略提升):ε-Greedy方法,基于 q t + 1 ( s t , a ) q_{t+1} (s_t, a) qt+1?(st?,a)立即更新
    • π k + 1 ( a ∣ s t ) = { 1 ? ε ∣ A ∣ ( ∣ A ∣ ? 1 ) if? a = arg?max ? a q t + 1 ( s t , a ) ε ∣ A ∣ otherwise \pi_{k+1}(a|s_t) = \begin{cases} 1-\frac{\varepsilon}{|\mathcal{A}|} (|\mathcal{A}|-1) &\text{if } a = \argmax_a q_{t+1}(s_t, a) \\ \frac{\varepsilon}{|\mathcal{A}|} &\text{otherwise} \end{cases} πk+1?(ast?)={1?Aε?(A?1)Aε??if?a=argmaxa?qt+1?(st?,a)otherwise?

Sarsa有两个变体:Expected Sarsa和n-step Sarsa

变体1:Expected Sarsa

  • q t + 1 ( s t , a t ) = q t ( s t , a t ) ? α t ( s t , a t ) [ q t ( s t , a t ) ? [ r t + 1 + γ E q t ( s t + 1 , A ) ] ] q_{t+1} (s_{t}, a_t) = q_{t} (s_{t}, a_t) - \alpha_t (s_t, a_t) [q_{t} (s_t, a_t) - [r_{t+1} + \gamma {\color{red} \mathbb{E} q_t (s_{t+1}, A)}]] qt+1?(st?,at?)=qt?(st?,at?)?αt?(st?,at?)[qt?(st?,at?)?[rt+1?+γEqt?(st+1?,A)]]
  • q t + 1 ( s , a ) = q t ( s , a ) , ? ( s , a ) ≠ ( s t , a t ) q_{t+1} (s, a) = q_t (s, a), \quad \forall (s, a) \neq (s_t, a_t) qt+1?(s,a)=qt?(s,a),?(s,a)=(st?,at?)

其中, E q t ( s t + 1 , A ) = v t ( s t + 1 ) \mathbb{E} q_t (s_{t+1}, A) = v_t (s_{t + 1}) Eqt?(st+1?,A)=vt?(st+1?)是状态值而非动作值

Expected Sarsa求解以下形式的贝尔曼公式:
q π ( s , a ) = E [ R t + 1 + γ v π ( S t + 1 ) ∣ S t = s , A t = a ] q_\pi (s, a) = \mathbb{E} [R_{t+1} + \gamma v_\pi(S_{t+1}) | S_t =s, A_t =a] qπ?(s,a)=E[Rt+1?+γvπ?(St+1?)St?=s,At?=a]

与Sarsa的区别:

  • 改变了TD Target
  • 需要更多的计算量,但减少了随机变量个数(不需要对 a t + 1 a_{t+1} at+1?采样),随机性减少

变体2:n-step Sarsa

n-step Sarsa是Sarsa的推广,统一了Sarsa和MC的思想

  • Sarsa基于单步采样进行估计,MC基于∞步采样进行估计,因此n-step Sarsa相当于是二者的折中
  • n-step Sarsa既不是online的,也不是offline的(或者是是特殊的online方法)

image.png

公式及其他细节略。
n-step Sarsa本身仅用于策略估计,也可以和策略提升相结合。

🟦Q-learing (TD for optimal action values)

Q-learing直接估计最优动作值,因此不需要策略评估-策略提升的过程。

  • q t + 1 ( s t , a t ) = q t ( s t , a t ) ? α t ( s t , a t ) [ q t ( s t , a t ) ? [ r t + 1 + γ max ? a ∈ A q t ( s t + 1 , a ) ] ] q_{t+1} (s_{t}, a_t) = q_{t} (s_{t}, a_t) - \alpha_t (s_t, a_t) [q_{t} (s_t, a_t) - [r_{t+1} + \gamma {\color{red} \max_{a \in \mathcal{A}} q_t (s_{t+1}, a)}]] qt+1?(st?,at?)=qt?(st?,at?)?αt?(st?,at?)[qt?(st?,at?)?[rt+1?+γmaxaA?qt?(st+1?,a)]]
  • q t + 1 ( s , a ) = q t ( s , a ) , ? ( s , a ) ≠ ( s t , a t ) q_{t+1} (s, a) = q_t (s, a), \quad \forall (s, a) \neq (s_t, a_t) qt+1?(s,a)=qt?(s,a),?(s,a)=(st?,at?)

Q-learing和Sarsa在公式上的唯一区别是TD target(公式的红字部分)。每个状态下,Q-learing在对action进行优化,但Sarsa只是依据当前策略选择action。

Sarsa求解贝尔曼方程,但Q-learing求解贝尔曼最优方程:
q ( s , a ) = E [ R t + 1 + γ max ? a q ( s t + 1 , a ) ∣ S t = s , A t = a ] , ? s , a q(s, a) = \mathbb{E} [ R_{t+1} + \gamma \max_a q(s_{t+1}, a) | S_t =s, A_t = a ], \quad \forall s,a q(s,a)=E[Rt+1?+γmaxa?q(st+1?,a)St?=s,At?=a],?s,a

此外,Sarsa属于on-policy算法,而Q-learing属于off-policy算法。

  • Sarsa所需的 a t + 1 a_{t+1} at+1?依赖于 π t \pi_t πt?,之后根据动作值估计来更新策略为 π t + 1 \pi_{t+1} πt+1?,可见其行为策略与目标策略相同
  • Q-learing所需的数据为 { ( s t , a t , r t + 1 , s t + 1 ) } \{(s_t, a_t, r_{t+1}, s_{t+1})\} {(st?,at?,rt+1?,st+1?)},这4个变量都不依赖于特定策略(或者说可以由任意策略生成),因此其行为策略与目标策略可以不同
    • *二者相同时,Q-learing即为on-policy

Q-learing算法步骤(off-policy):
由行为策略 π B \pi_B πB?生成若干episode,每个episode包含 { s 0 , a 0 , r 1 , s 1 , a 1 , r 2 , ? ? } \{ s_0, a_0, r_1, s_1, a_1, r_2, \cdots \} {s0?,a0?,r1?,s1?,a1?,r2?,?}

  • *例子: π B \pi_B πB?可以取 ε = 1 \varepsilon =1 ε=1的ε-Greedy,保证对每个动作等概率探索

在每个episode的每个时间步 t = 0 , 1 , 2 , ? t=0,1,2,\cdots t=0,1,2,?中:

  • 更新最优动作值(q-value)的估计:Q-learing的公式,略
  • 更新目标策略 π T \pi_T πT? π T , t + 1 = { 1 if? a = arg?max ? a q t + 1 ( s t , a ) 0 otherwise \pi_{T, t+1} = \begin{cases} 1 &\text{if } a = \argmax_a q_{t+1} (s_t, a) \\ 0 &\text{otherwise} \end{cases} πT,t+1?={10?if?a=argmaxa?qt+1?(st?,a)otherwise?
    • 是greedy,但不是ε-greedy(不需要探索)

对于off-policy的Q-learing而言,行为策略的探索性越强,其目标策略收敛于最优策略的速度越快。

🟡TD算法汇总

所有估计动作值的TD算法可以由下式统一表示:
q t + 1 ( s t , a t ) = q t ( s t , a t ) ? α t ( s t , a t ) [ q t ( s t , a t ) ? q ˉ t ] q_{t+1} (s_{t}, a_t) = q_{t} (s_{t}, a_t) - \alpha_t (s_t, a_t) [q_{t} (s_t, a_t) - {\color{blue} \bar{q}_t}] qt+1?(st?,at?)=qt?(st?,at?)?αt?(st?,at?)[qt?(st?,at?)?qˉ?t?]
其中, q ˉ t \bar{q}_t qˉ?t?为TD target,而TD算法的目标即使得 q t ( s t , a t ) q_t(s_t,a_t) qt?(st?,at?)接近 q ˉ t \bar{q}_t qˉ?t?,或者说缩小TD error( q t ( s t , a t ) ? q ˉ t q_{t} (s_t, a_t) - {\bar{q}_t} qt?(st?,at?)?qˉ?t?)。

不同算法的差异在于 q ˉ t \bar{q}_t qˉ?t?的形式不同:【注意到,TD和MC实际上是有关联的,主要差异是采样的数量不同】

算法 q ˉ t \bar{q}_t qˉ?t?形式
Sarsa q ˉ t = r t + 1 + γ q t ( s t + 1 , a t + 1 ) \bar{q}_t = r_{t+1} + \gamma q_{t} (s_{t+1}, a_{t+1}) qˉ?t?=rt+1?+γqt?(st+1?,at+1?)
Expected-Sarsa q ˉ t = r t + 1 + γ ∑ a π t ( a ∣ s t + 1 ) q t ( s t + 1 , a ) \bar{q}_t = r_{t+1} + \gamma \textstyle\sum_a\pi_t(a|s_{t+1}) q_{t} (s_{t+1}, a) qˉ?t?=rt+1?+γa?πt?(ast+1?)qt?(st+1?,a)
n-step Sarsa q ˉ t = r t + 1 + γ r t + 2 + ? + γ n q t ( s t + n , a t + n ) \bar{q}_t = r_{t+1} + \gamma r_{t+2} + \cdots + \gamma^{n} q_{t} (s_{t+n}, a_{t+n}) qˉ?t?=rt+1?+γrt+2?+?+γnqt?(st+n?,at+n?)
Q-learning q ˉ t = r t + 1 + γ max ? a q t ( s t + 1 , a ) \bar{q}_t = r_{t+1} + \gamma \textstyle\max_a q_{t} (s_{t+1}, a) qˉ?t?=rt+1?+γmaxa?qt?(st+1?,a)
Monte Carlo q ˉ t = r t + 1 + γ r t + 2 + ? + γ ∞ r t + ∞ \bar{q}_t = r_{t+1} + \gamma r_{t+2} + \cdots + \gamma^{\infin} r_{t+\infin} qˉ?t?=rt+1?+γrt+2?+?+γrt+?(均为单步折扣奖励,没有 q t q_t qt?

不同算法求解的公式也不同:
image.png

*随机近似(SA)&随机梯度下降(SGD)

【*注:本节内容主要是为理解时序差分的原理提供资料,但与强化学习核心内容关系不大,可以跳过。】

考虑求解均值估计(Mean Estimation)问题,MC利用采样的算数均值来估计期望,但缺点是需要等待所有样本收集完毕后再进行计算。
另一种求解思路:用增量和迭代方法进行计算,有多少数据利用多少数据。

举例:如何增量和迭代式地计算均值?
w k + 1 = 1 k ∑ i = 1 k x i w_{k+1} = \frac{1}{k} \sum_{i=1}^{k} x_i wk+1?=k1?i=1k?xi?,可知 w k + 1 = w k ? 1 k ( w k ? x k ) w_{k+1} = w_k - \frac{1}{k} (w_k - x_k) wk+1?=wk??k1?(wk??xk?)。基于该方式,只需要基于过去的均值计算结果 w k w_k wk?和新采样 x k x_k xk?,即可计算出总体均值【思路上有点像是EWMA】。采样数量越多,计算结果越准确。

可以对上式进一步推广,得到 w k + 1 = w k ? α k ( w k ? x k ) w_{k+1} = w_k - {\color{red}\alpha_k} (w_k - x_k) wk+1?=wk??αk?(wk??xk?),其中 α k > 0 \alpha_k>0 αk?>0。可以证明,当 α k \alpha_k αk?满足一定条件时,其迭代的计算结果会收敛至期望值。这是一种特殊的随机近似(SA)/随机梯度下降(SGD)算法。

随机近似(Stochastic Approximation,SA):一类随机迭代算法,适用于方程求解或优化问题,但不需要目标函数/方程的表达式/导数形式。

Robbins-Monro(RM)算法

目标:在不知道 g ( w ) g(w) g(w)的具体形式的情况下(视作黑盒),求解 g ( w ) = 0 g(w) = 0 g(w)=0,设其解为 w ? w^* w?
* g ( w ) g(w) g(w)须为单调递增

RM算法:
w k + 1 = w k ? a k g ~ ( w k , η k ) w_{k+1} = w_k - a_k \tilde{g} (w_k, \eta_k) wk+1?=wk??ak?g~?(wk?,ηk?)

  • w k w_k wk?:对 w ? w^* w?的第 k k k次估计
  • g ~ ( w k , η k ) = g ( w k ) + η k \tilde{g} (w_k, \eta_k) = g(w_k) + \eta_k g~?(wk?,ηk?)=g(wk?)+ηk?,其中 η k \eta_k ηk?是噪声,因此 g ~ \tilde{g} g~?表示对 g g g的带有噪声的观测
  • a k > 0 a_k>0 ak?>0:系数

RM算法依赖于数据:

  • 输入序列: { w k } \{w_k\} {wk?}
  • 带噪声的输出序列: { g ~ ( w k , η k ) } \{\tilde{g} (w_k, \eta_k)\} {g~?(wk?,ηk?)}

RM定理(收敛性):在RM算法中,当以下三个条件成立时, w k w_k wk?会按照概率1(w.p.1)收敛至 w ? w^* w?

  1. g ( w ) g(w) g(w)的梯度需满足: 0 < c 1 ≤ ? w g ( w ) ≤ c 2 , ? w 0 < c_1 \leq \nabla_{w} g(w) \leq c_2, \quad\forall w 0<c1??w?g(w)c2?,?w
    1. g g g须为单调递增,以保证 g ( w ) = 0 g(w)=0 g(w)=0的解存在且唯一
    2. g g g的梯度(对于多元函数,导数沿梯度方向取最大值)须有上界,以避免函数发散
  2. a k a_k ak?需满足: ∑ k = 1 ∞ a k = ∞ \textstyle\sum_{k=1}^{\infin} a_k = \infin k=1?ak?= ∑ k = 1 ∞ a k 2 < ∞ \textstyle\sum_{k=1}^{\infin} a_k^2 < \infin k=1?ak2?<
    1. 平方和小于无穷:随着 k → ∞ k\rarr\infin k a k a_k ak?收敛至0
    2. 和等于无穷: a k a_k ak?收敛至0的速度不能太快
  3. η k \eta_k ηk?需满足: E [ η k ∣ H k ] = 0 \mathbb{E} [\eta_k | \mathcal{H}_k] = 0 E[ηk?Hk?]=0 E [ η k 2 ∣ H k ] < ∞ \mathbb{E} [\eta_k^2 | \mathcal{H}_k] < \infin E[ηk2?Hk?]<
    1. η k \eta_k ηk?的均值为0且方差有界
    2. 常见情形: { η k } \{\eta_k\} {ηk?}为独立同分布随机序列(但不要求是正态分布)

a k a_k ak?的常见选择: a k = 1 k a_k = \frac{1}{k} ak?=k1?(或非常小的常数,为了避免最近采样的权重下降)

  • ∑ k = 1 ∞ a k = ∞ \textstyle\sum_{k=1}^{\infin} a_k = \infin k=1?ak?=

欧拉常数(Euler-Mascheroni constant)
γ = lim ? n → ∞ ( ∑ k = 1 n 1 k ? ln ? n ) ≈ 0.557 \gamma = \lim_{n\rarr\infin} (\sum_{k=1}^{n}\frac{1}{k} - \ln n) \approx 0.557 γ=limn?(k=1n?k1??lnn)0.557
n → ∞ n\rarr\infin n时, ln ? n → ∞ \ln n\rarr\infin lnn,因此可知 ∑ k = 1 ∞ 1 k = ∞ \sum_{k=1}^{\infin}\frac{1}{k} = \infin k=1?k1?=

  • ∑ k = 1 ∞ a k 2 < ∞ \textstyle\sum_{k=1}^{\infin} a_k^2 < \infin k=1?ak2?<

巴塞尔问题(Basel Problem)
∑ k = 1 ∞ 1 k 2 = π 2 6 < ∞ \sum_{k=1}^{\infin}\frac{1}{k^2} = \frac{\pi^2}{6} < \infin k=1?k21?=6π2?<

随机梯度下降(Stochastic Gradient Descent,SGD)

SGD是RM算法的一种特殊情况。

目标:求解以下优化问题
min ? w J ( w ) = E [ f ( w , X ) ] \min_w \quad J(w) = \mathbb{E} [f(w, X)] wmin?J(w)=E[f(w,X)]

  • w w w:待优化参数
  • X X X:随机变量, E \mathbb{E} E是关于 X X X的期望
  • w w w X X X可以是标量或向量,函数 f ( ? ) f(\cdot) f(?)为标量

*最小化用梯度下降,最大化用梯度上升

求解方法1:GD
w k + 1 = w k ? α k ? w E [ f ( w k , X ) ] = w k ? α k E [ ? w f ( w k , X ) ] w_{k+1} = w_k - \alpha_k \nabla_w \mathbb{E}[f(w_k, X)] = w_k - \alpha_k \mathbb{E}[\nabla_w f(w_k, X)] wk+1?=wk??αk??w?E[f(wk?,X)]=wk??αk?E[?w?f(wk?,X)]

  • 缺陷:期望难以直接计算

求解方法2:BGD(Batch Gradient Descent),基于数据采样计算期望
E [ ? w f ( w k , X ) ] ≈ 1 n ∑ i = 1 n ? w f ( w k , x i ) \mathbb{E}[\nabla_w f(w_k, X)] \approx \frac{1}{n} \sum_{i=1}^{n} \nabla_w f(w_k, x_i) E[?w?f(wk?,X)]n1?i=1n??w?f(wk?,xi?) n n n次采样)
w k + 1 = w k ? α k 1 n ∑ i = 1 n ? w f ( w k , x i ) w_{k+1} = w_k - \alpha_k \frac{1}{n} \sum_{i=1}^{n} \nabla_w f(w_k, x_i) wk+1?=wk??αk?n1?i=1n??w?f(wk?,xi?)

  • 缺陷: w k w_k wk?的每次迭代都需要很多采样

求解方法3:SGD
w k + 1 = w k ? α k ? w f ( w k , x k ) w_{k+1} = w_k - \alpha_k \nabla_w f(w_k, x_k) wk+1?=wk??αk??w?f(wk?,xk?)

  • 与GD的差异:将真实梯度(true gradient) E [ ? w f ( w k , X ) ] \mathbb{E}[\nabla_w f(w_k, X)] E[?w?f(wk?,X)]替换为随机梯度(stochastic gradient) ? w f ( w k , x k ) \nabla_w f(w_k, x_k) ?w?f(wk?,xk?)
  • 与BGD的差异:仅采样一次( n = 1 n=1 n=1

SGD收敛性:若以下三个条件成立,则 w k w_k wk?会按照概率1(w.p.1)收敛至 w ? w^* w? ? w E [ f ( w , X ) ] = 0 \nabla_w \mathbb{E} [f(w, X)] = 0 ?w?E[f(w,X)]=0的解)

  1. 0 < c 1 ≤ ? w 2 f ( w , X ) ≤ c 2 0 < c_1 \leq \nabla_{w}^2 f(w, X) \leq c_2 0<c1??w2?f(w,X)c2?(二阶梯度)
    1. f ( ? ) f(\cdot) f(?)是严格凸函数(标量)
  2. ∑ k = 1 ∞ a k = ∞ \textstyle\sum_{k=1}^{\infin} a_k = \infin k=1?ak?= ∑ k = 1 ∞ a k 2 < ∞ \textstyle\sum_{k=1}^{\infin} a_k^2 < \infin k=1?ak2?<
  3. { x k } k = 1 ∞ \{x_k\}_{k=1}^{\infin} {xk?}k=1?为独立同分布(i.i.d)

SGD的收敛模式:

  • w k w_k wk?距离 w ? w^* w?较远时,SGD的表现与GD相似,即 w k w_k wk?随着迭代不断向 w ? w^* w?逼近
  • w k w_k wk?距离 w ? w^* w?较近时,SGD会表现出较大的随机性,即 w k w_k wk? w ? w^* w?附近波动

BGD / MBGD / SGD

算法形式说明
BGD w k + 1 = w k ? α k 1 n ∑ i = 1 n ? w f ( w k , x i ) w_{k+1} = w_k - \alpha_k \frac{1}{n} \sum_{i=1}^{n} \nabla_w f(w_k, x_i) wk+1?=wk??αk?n1?i=1n??w?f(wk?,xi?)基于所有采样,最接近于均值
MBGD (mini batch) w k + 1 = w k ? α k 1 m ∑ j ∈ I k ? w f ( w k , x j ) w_{k+1} = w_k - \alpha_k \frac{1}{m} \sum_{j \in \mathcal{I}_k} \nabla_w f(w_k, x_j) wk+1?=wk??αk?m1?jIk???w?f(wk?,xj?)基于部分采样( ∣ I k ∣ = m ≤ n \vert \mathcal{I}_k \vert=m \leq n Ik?=mn
SGD w k + 1 = w k ? α k ? w f ( w k , x k ) w_{k+1} = w_k - \alpha_k \nabla_w f(w_k, x_k) wk+1?=wk??αk??w?f(wk?,xk?)基于单个采样

MBGD可以视作BGD和SGD的一种中间情况

  • m = 1 m=1 m=1:MBGD即为SGD
  • m = n m=n m=n:MBGD接近于BGD,但不完全相同
    • BGD对每个采样使用1次,MBGD是从 n n n个采样中随机选取 n n n次,每个采样被使用的次数可能超过一次【大概是有放回和不放回的区别】

文章来源:https://blog.csdn.net/LvGreat/article/details/135442977
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。