Skip to content
Jambity's Blog

Type to search…

↑↓to navigate
Esc

Lecture 6: Stochastic Approximation and Stochastic Gradient Descent

强化学习中的数学原理 | 第六课

RL,强化学习中的数学原理4min read...

这一课主要是为之后的课程补齐一个知识鸿沟，不然后面学temporal-difference learning会觉得那个算法很奇怪

同时随机梯度下降这个方法在之后也有广泛的应用

Revisit the mean estimation problem

知道一个随机变量，要估计他的期望，根据蒙特卡洛法:

为什么我们要关心 mean estimation 这个问题？因为 RL 中 state/action value 经常就用 mean 来估计

New question: how to calculate the mean

我们并不是指 ，因为这样算需要等所有 都算好后才能算，我们要讨论的方法是使用增量式的方法，准备好多少数据就算多少

In particular, suppose

and hence

then, 和之间的关系

Furthermore, consider an algorithm with a more general expression:

这种算法实际可以看做一种 special 的 SA algorithm，也可以看做一种 special 的 stochastic gradient descent algorithm，等之后学了就知道了

Stochastic approximation (SA 随机近似):

  • SA 指一类涉及随机迭代的算法，用于求解方程或者优化问题
  • 同样能求解方程的方法还有梯度下降/上升…SA相比之下的优势是不需要知道求解的方程的表达式、导数、、、

Robbins-Monro (RM) algorithm:

  • 是 SA 领域的一个具有开创性的工作
  • 我们常用的 stochastic gradient descent 随机梯度下降方法是 RM algorithm 的一种特殊形式
  • 开头讲的 mean estimation 问题也是 RM 算法的一种特殊形式

Suppose we would like to fiind the root of the equation

where 是未知量 and 是函数

  • 求解一个函数为0的根是一个应用广泛的问题，例如求解极值时就要求出导数为0的解

所以我们该怎么求解 ?

  • 知道表达式的情况
  • 不知道表达式的情况，例如一个神经网络，我要求解输入什么样的能得到一个0的输出呢

The RM algorithm can solve the problem:

where

  • is the kth estimmate of the root
  • is the kth noisy observation
  • is a positive coefficient

The function is a black box! This algorithm relies on data:

  • Input sequence:
  • Noisy output sequence:

哲学的思想：模型和数据至少要有一个，这里就是没有模型，但有数据

接下来我们要分析为什么 RM 算法能收敛

Intuition: is closer to than

不是严谨证明

要求是单调增的函数

  • when , we have . Then,

and hence is closer to than

  • when , 同理

我们也发现，这个算法要求条件很强，一定要是递增的函数

补上一个算期望的例子，使用RM算法
  1. Consider a function:

我们只要解出的解，就能知道，即估计出了期望

我们不知道，我们只能采样，因此：

进一步又有：

求解的RM算法是：

Suppose we aim to solve the following optimization problem:

  • is the parameter to be optimized
  • is a 随机变量，
  • and 可以是标量或矢量， 是标量

Method 1: gradient descent (GD)

Drawback 缺点：期望的求和很难拿到，我们没有模型，只有数据，所以接下来我们看只有数据的时候用什么方法来求

Method 2: batch gradient descent (BGD)

Drawback: 每次更新时都要采样很多次算期望

Method 3: stochastic gradient descent (SGD)

  • Compared to GD method: Replace the true gradient by the stochastic gradient .
  • Compared to the batch gradient descent method: let

1787885689403

Answer:

  • Exercise 1: 略
  • Exercise 2: 写出 GD 算法来解决这个问题

  • Exercise 3: 写 SGD 算法

  • Note
    • 这和 mean estimation algorithm 的公式一样
    • 意味着 mean estimation algorithm 是SGD的一种特殊情况

其实我们还没证明 SGD 这样不使用期望而直接使用一个是否是收敛的

证明思路就是证明 SGD 是一种特殊的 RM 算法

SGD’s aim is to minimize

Then the RM algorithm for solving Is

这正是 SGD 的公式，因此证明了SGD就是一种特殊的RM

刚才分析了收敛的正确性，现在我们要分析一下收敛时的一些有趣的行为

Question: SGD 使用随机的一个梯度来代替了GD里的期望，这是否会导致SGD在收敛的时候随机性较大？

结论是当离较远时，SGD呈现的行为类似GD，只有当离的较近时，才会产生较大的随机性，这是一个相当良好的性质

大致是通过比较相对误差，具体过程省略了

这里讨论了SGD中不存在随机变量，而是确定的一组值时的形式，我对这一点感触不深，甚至感觉有点显然，可以等之后遇到了实际问题再来回顾

1787889358141

  • BGD 每次要用到所有的采样，这是符合最真实的
  • MBGD 就采样 m 个
  • SGD 采样 1 个

Compare MBGD with BGD and SGD:

  • MBGD 相比 SGD 肯定随机性会下降
  • MBGD 相比 BGD 不需要那么多样本，更加灵活高效
  • MBGD 的 m = n 时，也不完全等于 BGD，因为BGD选取的n个样本是全部样本，不重复，但MBGD是随机采样n次，可能重复

1787889741095

Comments

© Jambity. All rights reserved.......