【深度学习基础】5. Long Short Term Memory

标准RNN的问题

如之前所述,RNN 最大的好处是可以利用上下文信息对输入和输出进行建模。但是标准的 RNN 网络,对上下文能够利用的序列长度实际上是有上限的,主要表现在随着前期的输入不断在网络中递归,其对隐藏层和对输出层的影响(这里可以理解为对梯度的贡献),要么衰减到没有了,要么指数级的爆炸了。在实际应用的过程中,这种梯度衰减的影响,使得标准 RNN 基本上只能做 10 个 timestep 以内的序列建模。

我们把这种影响,称为 vanishing gradient 。示意图如下,颜色深浅表达对梯度的贡献,随着序列往后移,前期输入数据产生的梯度的影响越来越弱,基本上后面就没有了:

【深度学习基础】5. Long Short Term Memory

针对这个问题,有很多种改进方案,其中最有效的是 LSTM(Long Short Term Memory)。

LSTM 结构

LSTM 本质上仍然是一种类 RNN 的递归神经网络结构,只不过处理的单元不再是简单的一个 summation hidden unit(直接对输入加权求和后调用激活函数产生输出),而是一个叫 memory block 的结构。这一点很重要,同一个隐藏层的所有的 memory block 之间是平行的,他们相互之间也是能全连接的(主要体现在前后两个 timestep 之间的递归关系)。类似之前的 summation hidden unit ,可以认为是把 summation  unit 扩展成了更复杂的 memory block 。其他的可以认为跟标准 RNN 并没用太多变化,甚至他们可以混合在一起使用。而且标准 RNN 的输出层也不需要做任何变更就可以直接使用。

现在对单一 memoryblock 展开,一个 block 里面包含至少一个 memory cell ,以及三个乘法单元:输入门、输出门、忘记门。这三个门分别模拟对 memory cell 的写、读、重置操作。下图是 LSTM memory block 的示意图,内含一个 memory  cell ,和三个 gate 。大圆圈内的操作表示要对输入进行 sigmoid 变换,f 表示 logistic,g 和 h 表示 tanh ,当然也可以是 logistic :

【深度学习基础】5. Long Short Term Memory

为了更好的理解上述三个门的作用,我们先列出 LSTM unfold 之后的效果:

【深度学习基础】5. Long Short Term Memory

由于 gate 的激活函数是 logistic sigmoid ,所以输出范围是 (0,1) ,0可以认为门要关闭,1 表示门打开,并通过乘法操作作用到相关输出上。举个例子,如果输入门(input gate)持续接近于 0,memory cell 中 input 这部分的输入影响会非常小,它在这个 timestep 的激活值不会被新的输入给覆盖掉(overwrite)。上图中【深度学习基础】5. Long Short Term Memory表示门关闭,【深度学习基础】5. Long Short Term Memory表示门打开,在时刻 1 以后输入门一直是关闭的,因此之前序列的输入产生的梯度影响会一直被传递到后面的 timestep 。与之对应的,forget gate 用来控制之前输入数据对梯度影响的传递,output gate 用来控制输入数据对输出的梯度影响。比如时刻 7,forget gate 关闭, input gate 打开,memory cell 被重置了。

正是借助 memory cell 和上述三个门,可以实现比较长周期的序列输入记忆功能。

LSTM 已经在很多需要长时依赖的合成任务中取得了不错的效果,比如学习长文本的上下文,在实际应用中能解决很多标准 RNN 无法解决的问题。

用一个实际的图来对比标准 RNN 和 LSTM 在 vanishing gradient 问题上的结果,途中的噪声表示梯度的值。可以明显看出 LSTM 对梯度的传递可以更加持久:

【深度学习基础】5. Long Short Term Memory

最后补一个图,是同一个 hidden layer 不同的 LSTM memory block 之间的递归关系示意图:

【深度学习基础】5. Long Short Term Memory

有了之前 RNN 的基础,相信大家应该看的明白。这个图同一层的递归调用关系,实际上是不同 timestep 之间的连接。展开为 RNN 的 unfold 的示意图比较好理解。

数据预处理的影响

讲了LSTM这么多的好处,其实我们忽略了一点:如果我把比较长的输入序列数据预先处理一次,变为比较短的序列数据,也就是对input-output的建模只需要做短时依赖的话,其实可以不用LSTM这么复杂的。

比如一些时序数据,通过调整采样或者一些信号处理的方法,可以把数据进行压缩,变成一个相对短的时序数据,然后用一些短时依赖的模型也是可以取得好的效果。

但是不管怎么说,这种预处理有时候比较麻烦,或者根本不知道如何预处理,或者干脆就不想对原始输入做任何任务相关的预处理,而且有时候此类预处理会带来数据的精度损失,那么一个能处理长时依赖的模型还是很有必要的。

LSTM的数学表达和编程实现

LSTM也是可导的,因此可以用梯度下降的方法来进行训练。它的后向反馈可以用之前提到的BPTT算法来进行梯度更新。但是由于LSTM的memory block包含三个门,BPTT在反馈的时候要对这三个门分别进行梯度更新。公式比较多,我们这里就不详细列出反馈过程了,感兴趣的可以找本LSTM的参考文献详细看看。

我们重点描述LSTM的前馈过程,因为很多symbol编程的Deep Learning框架需要我们编写forward的公式以及编程实现,而backward是可以自动求导的。

下面的公式中,都是把input summation以及activation过程单独列出,a是summation的结果,b是activation的结果。为了方便讲解把两个图放在一起对照。公式中之所以写Cell Output而不是Block Output,主要是因为一个Block可能包含多余1个的Cell,【深度学习基础】5. Long Short Term Memory;同时,【深度学习基础】5. Long Short Term Memory代表其他隐藏层节点(一共H个)的激活输出作为自己Block输入的部分,同样由于Block可能包含多个Cell,所以并没用把h和c混用。当C=1时跟Cell Output 【深度学习基础】5. Long Short Term Memory是一样的。另外就是要注意各项所使用的数据,是本时刻的还是上一时刻的。

【深度学习基础】5. Long Short Term Memory

  • Input Gate

输入:本时刻的所有前一层输入  【深度学习基础】5. Long Short Term Memory ,本层在上一时刻的各个memory block输出 【深度学习基础】5. Long Short Term Memory,还有自己Block内(不含同一层其他Block)所有的Cell(一共C个,【深度学习基础】5. Long Short Term Memory)在上一时刻输出 【深度学习基础】5. Long Short Term Memory(图中虚线部分代表这一项的加权)。

输出:输入加权求和的f激活函数结果(logistic)

  •  Forget Gate

输入:本时刻的所有前一层输入  【深度学习基础】5. Long Short Term Memory ,本层在上一时刻的各个memory block输出 【深度学习基础】5. Long Short Term Memory,还有自己Block内(不含同一层其他Block)所有的Cell(一共C个,【深度学习基础】5. Long Short Term Memory)在上一时刻输出 【深度学习基础】5. Long Short Term Memory(图中虚线部分代表这一项的加权)。

输出:输入加权求和的f激活函数结果(logistic)

  •  Memory Cell

输入:a)本时刻的所有前一层输入  【深度学习基础】5. Long Short Term Memory ,本层在上一时刻的各个memory block输出 【深度学习基础】5. Long Short Term Memory,这部分先加权求和计算g(tanh)激活函数结果 【深度学习基础】5. Long Short Term Memory,并与本时刻InputGate的输出 【深度学习基础】5. Long Short Term Memory相乘;b)本时刻的Forget Gate输出【深度学习基础】5. Long Short Term Memory上一时刻的本Cell输出 【深度学习基础】5. Long Short Term Memory相乘

输出:上述两项输入部分直接求和,无需额外激活函数。

  • Output Gate

输入:本时刻的所有前一层输入  【深度学习基础】5. Long Short Term Memory ,本层在上一时刻的各个memory block输出 【深度学习基础】5. Long Short Term Memory,还有自己Block内(不含同一层其他Block)所有的Cell(一共C个,【深度学习基础】5. Long Short Term Memory)在本时刻输出 【深度学习基础】5. Long Short Term Memory(图中虚线部分代表这一项的加权)。

输出:输入加权求和的f激活函数结果(logistic)

  • Cell Output

输出:本时刻的Cell状态计算h(tanh)激活函数的结果 【深度学习基础】5. Long Short Term Memory 与Output Gate输出【深度学习基础】5. Long Short Term Memory相乘

实际编程过程中,不同的应用LSTM的Memory Block如何构建,门的输入是否需要调整,都会带来很大的影响,要根据应用来进行调整。比如对Memory Block中的虚线部分,也就是公式中各个Gate中关于Cell State的第三项,MXNet的LSTM example代码,就没有包含着一部分。但是在其他应用场景,可能加上这部分后效果就截然不同。所以LSTM的变种问题就很值得深入研究。

 

始发于微信公众号:微信AI

【深度学习基础】4. Recurrent Neural Networks

RNN简介

之前已经了解了 ANN,ANN 的网络连接是无环的。如果我们放宽条件,允许节点之间连接形成环,就是 recurrent neural networks(RNNs)。RNN 有许多种实现,我们这里主要关注一种比较简单的,只在隐藏层内自连接的形式,如下图所示:

之前所有类型的多层感知机都是从一个固定维度的 Input 到 output 的映射,而 RNN 可以对整个输入序列的历史进行建模。理论上,如果 RNN 的隐藏节点足够多,他对序列到序列的映射建模是可以做到任意精度的。RNN 通过将序列数据之前的输入“记忆”在网络内,从而达到提高输出精度的效果。

RNN的unfold展开

很多时候大家看到的 RNN 网络结构都很迷糊。有上面那个图样子的,还有这样的:

还有的是这样的:

实际上第一个图把递归过程画到图里面了,这样就把图画的过于复杂;上面这个图把递归过程按序列的时间顺序(timestep)展开了,也就是 unfold 的表达,但是由于无法跟网络结构对应起来,看起来不够清晰。

引用 wikipedia 上面一个图,这个图把输入(以文本序列为例,就是一个个的词)用 a 表示(下文用 x 表示),隐藏层的输出用 x 表示(下文用 b 表示),最后输出用 y 表示。t 表示的是时间关系,还是以文本为例,t+1 就是 t 的下一个词,但是这个图中 f 也带了下标,不容易看明白。

结合上面三个图,各理解一部分最后综合就好理解了。

RNN 的网络结构上跟 DNN 类似(第一个图去掉 hidden unit 之间的那些连接),但是每个 timestep hidden unit 的输入分两部分(第三个图):一部分是前一层的输出作为本层 unit 的输入,另外一部分是相同 hidden layer 所有的 unit 在上一个 timestep 的输出,这两部分通过不同的权重加权求和,一起作为本时刻的输入。

另外需要理解的是,RNN 并没用若干个 model 用于处理不同的 timestep 数据,而是只有一个 model ,第二个图中一个黑圈代表一个 hidden layer ,不同层的权重 Wi 在所有 timestep 使用的是一份相同的参数,这也就是从 time 1 到5 ,input to hidden 一直是 W1,hidden to hidden 一直是 W2,hidden to output 一直是 W3 。

这里贴一个动画图来辅助理解RNN,不同timestep共用一个NN模型,上一时刻hidden layer的输出,与下一时刻的输入合并作为新的输入。图上面还演示了反馈的过程,这个后面再详细讲述。

RNN的前馈过程

 RNN 的前馈过程与普通的神经网络是一样的,但是有一点需要注意:隐藏层节点的输入,除了有普通的数据输入部分,还有上一时刻(timestep)隐藏层的输出部分。假设输入序列 X 长度为 T(还是以一个句子举例,有 T 个词),输入到一个 RNN 网络中,输入层是 I 个输入单元(也可以直观理解为 word embedding 到 I 维),H 个隐藏单元,K  个输出单元(最后softmax对应的label是K种)。设 是t时刻,输入节点 i 的输入,和 分别 t 时刻隐藏层节点 j 的输入和输出(激活函数的结果)。有下面的关系:

也就是说,任意时刻 t ,隐藏层节点的输入包含原始数据输入和上一时刻隐藏层输出两部分。注意:编程实现的时候,这部分是做矩阵元素的按位求和操作。我们把节点输出的激活函数部分单独分离出来,有如下关系:

计算过程中,比如对一句话进行 RNN 分类,从 t=1 开始到 t=T 结束(一个词一个词的往网络中输入),递归的调用上面的两个公式,得到隐藏层输出。在最后的输出层,由于他不需要递归调用,因此只需要对隐藏层的输出进行全连接加权求和,最后应用 softmax 或者 logistic 激活函数即可:

这里有个疑问:每次输入一个词,理论上都可以前向计算到最后的输出层,得到一个输出层的输出,如果是分类问题,要怎么处理这么多的输出呢?有三种解决办法:

a)     把每个时刻输出结果都存下来,最后合并做一次 pooling ,然后对 pooling 结果做最后到分类 label 的映射;

b)     把每个时刻输出结果都存下来,但是是合并到一个向量上,统一通过输出层做最后到分类 label 的映射;

c)      t=1 到 t=T-1 时刻最后隐藏层的输出都只做下一个 timestep 的输入,而不连接到 output layer ,只保留 t=T 时刻的输出,做到分类 label 的映射。

上述三种方法,经过试验都是可以 work 的,但是由于他们对最后的误差 backward 是有区别的,所以收敛速度和效果也都不一样,大家可以自己试验一下。

另外一个问题是:在起始时刻(输入第一个词的时候),  是没有的,我们简单的将其全部置 0 即可。

RNN的反馈过程

与普通神经网络一样,通过对输出层目标函数的偏导,传递回来对隐藏层网络的权重求导数。目前有两种方案对 RNN 网络的参数进行求导,一种是 real time recurrent learning(RTRL),一种是 backpropagation through time(BPTT)。下面主要介绍 BPTT 算法,因为他比较简单,而且更加高效。

与标准 BP 算法一样,BPTT 也是从最后一层向前面传播。微妙之处是,对于 RNN 的目标函数虽然依赖于隐藏层的激活输出,但是隐藏层的激活输出不但会影响到输出层,而且还会影响下一时刻的隐藏层自身。比如:

其中:,O 是整个RNN训练过程中需要拟合的目标函数, 是激活函数求一阶导数。

要计算一个序列的  ,可以先计算 t=T 的结果,然后递归的调用上面的公式,计算 t-1 时刻的结果,不断往前面推导。需要注意的是:,因为序列的最后面无法产生误差结果。

最后,需要注意的是:用于连接隐藏层节点的输入输出的参数(各种),在所有的 timestep 都是一样的。最后更新的时候,是把整个序列上的所有的导数求和,最后得到权重的梯度:

双向RNN

对于很多序列标注问题,我们是使用前面的已知内容去预测后面的内容。但是仍然有另外一些序列标注问题,上下文都是已知的。文本分类问题就是最典型的此类问题。

显然序列数据的前后元素之间都是有关联的,RNN 描述的就是沿着时间轴方向的关联性。所以理论上我们可以反过来,沿着逆时间轴的顺序对序列数据进一步刻画。这就是双向 RNN 。

具体内容这里就不展开了,留给自己调研学习吧。

【深度学习基础】3. Convolutional Neural Network

通过卷积(Convolution)提取特征

通过之前的文章,一种构建神经网络的方案是将输入层到隐藏层每个节点都设置一个参数权重,构建一个“全连接”的网络。但是这种设计有个问题,在输入层节点,比如 28*28 的小图片上还可行,但是如果图片变大到 96*96 ,那么输入层节点数量接近 1 万了,如果你再制作 100 组 feature ,那么从输入层到隐藏层需要训练的参数是 100 万个,计算量随着输入层大小急剧变大。

当然也可以用“局部连接”的概念来减少需要训练的参数。比如在输入层节点上设置一个滑动窗口,隐藏层只跟窗口内部的少数输入层节点有连接边。比如语音就可以在输入层上面加时间窗来构建“局部连接”网络。

对于图片数据,有个特性就是整个图片不同区域在统计特性上是一致的,针对一个区域设计的特征提取机制,放到其他区域也是可以用的。举个例子:从一个大图上面截取一个 8*8 的小区域,针对这一块数据设计了一系列特征提取算法(也就是 8*8 区域的参数),理论上这个特征提取算法是可以应用在这个大图片上的任何区域的。然后把这个滑动窗口从大图片的左上角到右下角整个的过一遍,每一处都执行卷积操作(矩阵按位乘并全局求和),把原始图片转换到一个新的特征空间。

下面的图片是一个例子,对于一个 5*5 的图像使用一个 3*3 的小窗口进行卷积。需要注意的是:黄色区域内的参数是通过训练过程中学出来的,不是手工编的。然后如果一共开发了比如 N 组这样的小窗口( N 组特征提取器,大小各异),通过卷积操作后,会得到 N 组的卷积特征结果集。

上面的例子泛化一点,假设图片大小是 r*c ,卷积窗口是 a*b 覆盖一个 的图片区域,那么可以设置一个卷积核  来学习这一块的特征,其中  是处理函数,可以是 sigmoid 或者其他,比如上面图中的例子 是图像输入层到隐藏层的权重和 bias 。一共学到了 k 组特征( k 个卷积核),卷积处理后,图片会被转化到 k*(r-a+1)*(c-b+1) 维的卷积特征。

泛化一点,如果我们不认为这是一个图像,而只是一个数据的矩阵,那么数据来源就可以不限定为图像像素了。比如词向量( word2vec )或者各种具有局部 context 关系的 embedding 数据,都应该是可以用卷积层来操作的。比如短文本句子,卷积窗口的宽度等于词向量的维度( 因为词向量被截断后意义不大 ),高度等于窗口要覆盖的上下文词数量( 比如5个词 ),那么卷积操作是可以处理文本数据上下文关系的。窗口在短文本句子上滑动,就是在处理一个个的局部语义片段。

池化(Pooling)

通过上面的卷积操作,理论上已经提取到了很多特征可以直接训练分类器了。但是由于简单算一下,如果对 96*96 的图片通过 8*8 的窗口进行卷积并得到了 400 组特征,那么最后产生的卷积特征是 400*(96-8+1)*(96-8+1)=300 万维。

直接对 300 万维特征进行训练,不但训练计算量非常大,而且很容易过拟合。

回到之前提到的图像不同区域之间的统计特性一致性,那么理论上对一个图像的不同区域再做一次相同的统计汇总,得到的特性应该仍然是一致的。比如对不同区域分块后求平均,或者求最大值。通过这种对不同区域进行统计汇总,可以显著降低特征数据的维度,因此也可以改善过拟合问题。这个过程叫做“池化”,或者 “mean pooling” , “max pooling” 。下图是一个池化过程的示意图:

选择m*n大小的窗口进行卷积特征的池化,那么直接把卷积特征划分到不连续的m*n分块,直接在分块上进行求平均或者最大值的操作,就可以完成池化的过程了。需要注意的是,不同的卷积特征(特征提取器输出的结果)需要独立的进行池化,池化之后的数据才进入全连接的操作输入到下一层。

池化的平移不变性

根据上面的 pooling 的内容讲解,如果我们是在相同的 filter 所产生的特征中进行相邻连续区域的 pooling ,那么所得到的 pooling 结果具有平移不变性。举个简单的例子:用 max pooling 对一个卷积层结果进行池化,那么原始的图像进行了小范围的移动,实际上得到的 pooling 层结果应该是一样的。这种平移不变性在图像处理的时候非常有用,比如手写体识别,label 是一样的,但是如果图像稍微平移了一点,识别程序应该足够 robust ,仍然能识别它。

随机梯度下降和动量(Momentum)

在最优化方法中,有一类方法是全局求最优的梯度方向,比如 L-BFGS(limited memory BFGS),但是这类方案在数据量和模型都大到不能装进内存的时候,单机无法完成。而且这类方法是对整体训练数据进行最优化求解,因此无法对新的数据进行训练,也就是 online-learning 。随机梯度下降(StochasticGradient Descent,SGD)可以解决此类问题。

SGD 用在神经网络的训练上,不但可以避免计算全量数据的 BP 运算复杂度,而且仍然可以快速收敛。

SGD 的公式之前在线性回归的时候已经介绍过了:一般实现的时候,都是使用一个 mini-batch 的 instance 对梯度更新一次,mini-batch 一般取 256 。这么做的好处是防止单条记录更新一次产生的抖动,使得梯度方向更加稳定,同时可以直接将计算操作变成矩阵运算进行加速。

是梯度更新的学习率,可以保持恒定的值也可以进行动态调整。有很多方法可以进行调整,这里就不进一步深入了。

SGD 一个需要注意的问题是训练数据应该在每轮迭代的时候进行随机打乱,如果训练数据是按照某种规则进行排列的,一般训练过程的收敛性也无法保障。

SGD 训练过程中另外一个需要注意的问题是如果目标函数在最优解附近有抖动,而且具有局部很陡的峰值,那么常规 SGD 会在局部峰值的位置震荡。很不幸 DNN 就具有这样的特点。一个解决办法是在梯度更新的时候增加动量:

上式中 是一个与梯度维度一样的速度向量,是上面提到的学习率,用来决定本次梯度更新要联合使用之前多少轮的梯度值。一般在初始化阶段 取 0.5 ,在网络稳定后可以增大到 0.9 。

卷积神经网络(CNN)

了解了卷积和池化的概念后,我们可以定义卷积神经网络:通过一个或者多个卷积层,同时配合池化操作,然后将结果通过全连接隐藏层构建的多层神经网络。

卷积神经网络的好处是通过局部连接和池化可以对二维的图像进行空间建模,同时显著减少网络参数。

关于 CNN 的实现细节描述如下:

假设一个图片宽和高都是 m ,有 r 个通道(比如 RGB 就是 3 通道),那么输入层(图片像素)到卷积层的输入维度是 m*m*r (为了方便起见我们可以先不管 r ,可以理解为把一个通道的卷积做 r 次)。然后我们定义一个 n*n 大小的卷积窗口,制作 k 个卷积核,这样可以将图像转化到 k 组 m-n+1 长宽的矩形区域 。卷积层的输出是  来学习这一块的特征,其中是 sigmoid 函数,是图像输入层到隐藏层的权重和 bias 。在卷积结果之上,我们再定义一个 p*p 大小的池化区域,进行 mean 或者 max pooling 采样(一般 p 取的比较小,2-5 之间)。池化结果之后,会进入到全连接的隐藏层。

下图是一个 CNN 的示意图,不同颜色的节点代表不同的 channel 和 feature 。

卷积神经网络的BP算法求解

假设是 l+1 层的误差项,那么对于 CNN 的最后几层全连接层,可以通过常规 BP 算法进行误差反向传递:,并且进行梯度更新:

如果第 l 层是卷积和池化层,此时的误差传递要稍微变更一下:

式中 k 是卷积核(filter)的下标, 是激活函数的导数,这里为了方便并没用写是对激活函数的参数进行求导,实际上对参数求导的话会再多一项激活函数输入向量 x ,从而得到维度一样的向量,并可以进行按位乘操作。upsample 操作是池化操作的反向过程,如果是 mean pooling ,就把误差项均匀传递到所有的池化层输入节点上;如果是 max pooling ,就把误差项直接传递给产生 max 值的这个输入节点上。

最后是计算 filter 的梯度更新。Filter 权值的梯度通过对误差项矩阵和图片数据进行卷积来计算,然后把所有结果累计求和,就是卷积函数的梯度更新项。对于 bias 的梯度更新更简单,filter 误差项直接求和就是对应的 bias 更新。梯度公式如下所示:

看上面的公式, 是一个转置,* 是卷积,通过残差矩阵反向卷积的过程。W 应该是 a*b 维的,是如何得到的呢?a 是 r*c 维的,是 (r-a+1)*(c-b+1) 维的,这两个矩阵进行卷积操作,实际上可移动区域是 a 行 b 列,计算得到的也就是 W 的梯度矩阵。

这部分的具体代码,可以看 caffe 或者 mxnet 的源代码来理解,斯坦福的 deep learning 教程上有 matlab 代码。

需要注意的是:如果在计算最后的代价函数的时候,考虑了对训练数据样例大小做平均的话,在进行梯度反馈的时候,也需要进行求平均操作。

卷积核的编程实现

通过上面的讲解,我们知道卷积过程其实是对图像(泛化一点理解,应该是一个矩阵,不限里面的数据是什么类型)中的某一块单独提取出来进行一个特定的计算把他映射到另外一个矩阵,或者使用数字信号处理的概念,我们是对这一小块矩阵进行了一个滤波操作留下我们想要的内容。这也是为什么有些地方把这个过程叫做 filter 。

那么理论上不同的卷积操作应该是预先定义了很多不同的卷积核或者滤波器,通过在原始矩阵上面滑动进行局部滤波,得到新的矩阵数据。但是我们在一些深度学习编程框架,比如 MXNet 上只看到需要配置 filter 的数量,并没有说可以指定使用何种方式的滤波操作。这是怎么回事呢?

这一块的内部实现是这样的:如果我指定当前是一个卷积层,并把 filter 设置为 20 ,实际上窗口大小和卷积函数的操作是一模一样的,只不过卷积函数的参数(W和b)的初始化值不一样。因为卷积和池化之后的全连接层,每次做 BP 计算的时候得到的传递回来的误差是一个全局误差,并不会因为 filter 不同而由不同,所以各个初始化不一样的filter在使用一个相同的全局梯度值进行更新,可以保证其最后训练得到的模型中filter的最终权重也是不一样的。

上面这一点可以借助 word2vec 的 CBOW 模型加强理解,CBOW 的投影层得到的梯度值是一个全局的,把他更新到 context 窗口上各个 word ,得到的效果也是不一样的。

 

【深度学习基础】2. 有监督的神经网络

多层神经网络

之前我们讨论的线性回归和逻辑回归都是对 进行线性关系建模的,如果我们希望对其进行非线性关系建模,神经网络是一个方法,而且它可以对比较复杂的非线性关系进行建模。

我们先来看神经网络最基本的单元“神经单元”的定义:

上面的例子中,有一个激活函数我们一般选择一个 sigmod 函数作为f的实现,比如 logistic 函数:当然我们也可以使用tanh函数,或者 Rectifier 激活函数(使用 Rectifier 作为激活函数的 Unit 叫做 Rectified Linear Units, ReLu )或者其他一些 Rectifier 的变种。三种函数的输入对比如下图所示:

tanh(z) 可以看做是 sigmoid 的拉伸版本,他的值域是 (-1,1),而 logistic 是 (0,1) 。 ReLU 则是当 Z 大于 0 时斜率为 1 的线性函数,小于 0 时始终输出 0 。

三种不同的激活函数在进行梯度求导的时候也是各不相同。Logistic 梯度是,tanh函数的梯度是  

Rectifier的梯度在 大于 的时候是 ,其他为 

理论上 Rectifier 在 点是不可导的,但是由于我们训练神经网络的时候用很大量的数据,梯度更新的时候是所有 instance 的梯度求和,一处 z=0 不至于影响整个梯度下降的过程,所以我们把 z=0 时的梯度也定义为 

另外一个需要注意的是,我们把 bias(也叫截距)这一项单独写出来了,定义为公式中的 ,而不是同一使用来定义。

神经网络模型

我们把很多的神经元串联起来,下一层的输入是上一层的输出,从而组成一个小型的网络,比如下图:

最左边一层我们叫输入层(input layer),最右边一层叫做输出层(output layer),中间部分都叫做隐藏层(hidden layer)。定义一些变量:

是神经网络的层数,比如这里是3

是第 层网络,比如是输入层,

是输出层是神经网络的参数,表示连接第l层的节点 与连接第 l+1 层的节点 之间的边的权重(注意下标和节点对应关系,因为 与 相乘时是转置过的)。

是连接到l+1层第i个节点的 bias

是第l层网络的节点个数(不包含 bias 节点)

是第l层第i个节点的输出值(activation),对于l=1的输入层

对于输入层,我们也统一到了这个参数上,如果引入一个新的定义 ,上式可以简化为:

我们把这个 l -> l+1 逐层计算输出的过程叫做前馈(forward propagation)。通过 blas 等向量和矩阵运算库,我们可以很方便的把前馈过程表达为向量矩阵的线性代数运算,从而提高计算速度。

神经网络可以定义很多中间层,从而使得网络很 deep(这也是 DNN 的来源),同时输出层还可以定义多个输出节点来预测多个值,比如下面的网络示意图:

上面这个网络中,。这种网络可以专门用来对多分类问题进行建模。

可以看到,如果不存在输入层,直接输入对输出,如果输出层节点为 1,且激活函数为 logistic ,其实就是逻辑回归。如果输出层节点多于 ,且激活函数为 softmax ,就是 softmax regression 

BP算法 backpropagation Algorithm

 

我们使用最小均方误差来定义代价函数,对于单条记录有:

对于所有的m条训练数据合并计算代价函数,可以得到如下的代价函数:

其中第一部分定义的是误差平方和的平均值,第二项是正则化因子,也叫权值衰减 (weight decay),专门用来惩罚数值太大的权值,防止训练过程中发生过拟合。正则化因子控制前后两项的相对权重。

上面的损失函数既可以用于分类问题,也可以用于回归问题。分类问题的时候认为 y=0 或者 ,回归问题的时候需要先把 值归一化到 [0,1] 然后进行训练。

现在目标转化为求一组值使得  的值最小化。虽然  是一个非凸函数,使用梯度下降的最优化求解可能会收敛到局部最优,而非全局最优,但是实际应用中,我们这么做并没用太大的问题。

需要注意的是, 一定要使用随机值来进行初始化,而不能统一设置为 或者其他的一模一样的数,因为这样的话会使得隐藏层每个节点的连接参数都是一样的,这样计算出来后隐藏层节点的结果也都是一样的,然后逐层向前计算,最后的结果就是 x 原封不动的传输到了最后一层。这会让训练程序直接停止,因为无法计算梯度。这个随机初始化的过程,目的就是消除对称性。

根据之前使用梯度下降法更新参数的经验,我们知道现在我们需要用  分别求偏导,用于更新参数。按照严格的数学求解应该是这样的:

为了能更方便的求解,我们都使用 BP 算法。关于 BP 算法先说一个不太好理解的版本:首先对每一个训练样例 (x, y) 先进行前向计算得到最后一层的激活输出 (activations) ,然后对隐藏层的每一层 的每个节点 ,依次计算一个误差项,用于评估最后一层的输出误差中有多少是这个节点产生的。再说一个我自己理解的版本:如果网络并没有隐藏层,输入直接对接到输出,那么就是普通的逻辑回归或者 softmax 回归的求偏导更新过程;现在网络有很多隐藏层,前向计算过程中,是输入一层层传递过来的,而传递过程中与连接权重矩阵相乘的过程,本质上是一次次的空间变换(矩阵乘法就是两侧空间的 transfer 过程,可降维,可升维,可旋转缩放,可非线性变换等等各种),那么现在最后一层的误差来了,我们应该干什么呢?应该通过矩阵的另外一端把误差重新进行空间变换映射回去,并层层传递到第一个隐藏层。后面我们对照公式再具体讲一下。

对于输出层的 可以通过计算输出与真实值之间的最小二乘的导数来得到,而对于隐藏层,我们可以认为是所有使用 作为输入的下一层的节点的误差项进行加权求和(反向的矩阵空间变换)的结果。

BP 算法描述如下:

1.      先使用前向计算,一直计算得到输出层的结果;

2.      对于输出层的每个节点 ,计算 

3.      对所有的隐藏层,l= nl-1, nl-2, …, 3, 2,给每个节点 计算:

4.      使用 计算偏导项:

注意以上的乘 操作都是按位操作的,而且 我们同样可以使用矩阵和向量运算来加速。假设 是 sigmoid 函数,根据前面的推导我们可以直接得到,这样可以直接代入上面的公式中使用。

使用 mini-batch 来进行数据的批量计算,我们可以把上面过程使用矩阵形式来表达,梯度下降的算法过程如下:

1.         对于所有层 ,设置梯度

注意:是矩阵,是向量,他们是用来存储梯度值的。与用来存储权重的 和 维度是一样的。

2.         对于所有训练样例 i=1,2,…,m

a.       使用 BP 算法计算梯度

 

注意:这里的 也是矩阵方式的表达,比如输出层,隐藏层 。这里的  就是把下一层误差反向映射回来的过程,那为什么还有 这一部分呢?因为我们要计算的实际上参数的梯度下降方向。

b.      更新Wb的梯度

3.         更新参数 和 

如此一直迭代训练,便可以不断减小代价函数  直到模型收敛或者达到一定的训练迭代次数。

softmax regression输出层

使用 softmax regression 作为输出层时,代价函数求导得到的误差项表表达应该如下式,后面的误差传递过程保持不变:

常见的激活函数求导

通过上面的内容,我们知道多层神经网络的 BP 算法求解,大体的公式都是固定的模式化的,有一个可变的地方就是激活函数求导 。一般常见的三种激活函数:  logistic ,  tanh ,  Rectifier ,我们可以简单的把它们记录下来以便直接使用。

注意:以下部分都用进行了简化,实际上应该是对 求偏导,需要多补充一部分函数内求导的部分。

Rectifierfor z<=0;  for z>0

logistic      

tanh

【深度学习基础】1.监督学习和最优化

如今深度学习如火如荼,各种工具和平台都已经非常完善。各大训练平台比如 TensorFlow 让我们可以更多的聚焦在网络定义部分,而不需要纠结求导和 Layer 的内部组成。本系列我们来回顾一下深度学习的各个基础环节,包括线性回归,BP 算法的推导,卷积核和 Pooling,循环神经网络,LSTM 的  Memory Block 组成等,全文五篇,前三篇是斯坦福深度学习 wiki 整理,第四第五两篇是 Alex Graves 的论文读书笔记,图片来自网络和论文,有版权问题请联系我们。

线性回归

假如一个 target label 是与各种要素Xi呈线性关系的,我们可以用线性回归来拟合,,认为

为了达到数据拟合的目的,可以用最小二乘的方法来训练调整参数  ,也就是找到一组参数 ,使得最小化。

此问题的一类求解方法是通过梯度下降,每次对 进行求导,并不断沿梯度下降的方向更新,使得 不断减小并趋向于 0 。我们对公式中的每个 分别求偏导数,可以得到:   。

这个公式在编程的时候如何实现呢?首先我们把每一个 和 对应的数据叫做一个 instance ,一般是机器学习训练数据里面的一行。通过当前的向量,先求得  ,他一般是一个浮点数,直接与  相减得到偏导公式的后一部分,我们叫它为残差。然后直接对该 instance 中的每个位置的 (如果有值的话)乘上这个残差,得到对应元素位置的 的偏导数。

这样得到的偏导数也是一个向量,里面的元素与向量一一对应。我们选定一个叫学习率的参数 ,将这个偏导数向量更新到向量上,就完成了一次迭代: 。

重复上述过程,直到足够小,我们就得到了需要的参数。这样当我们拿到一组新的 ,但是不知道他对应的 是多少时,可以通过  计算得到一个近似的 ,也就是我们所说的预测过程。

逻辑回归

上面讲的线性回归可以用来预测连续值,但是很多时候我们希望做的是一个分类问题,也就是预测一个 instance 属于某个分类(比如:是/否,A/B/C等)的概率。逻辑回归就是完成此类任务的一个比较简单的方案。

在之前的线性回归的基础上,如果要预测的 y 是一个离散值(简单起见,后面以来举例,多个离散值同样可以简化为若干个二值问题),我们增加一个叫 sigmoid 或者 logistic 的操作,把上面的连续值域映射到 [0, 1] ,我们认为他代表该 instance 对应这个 y 取值的概率:

与上面的线性回归类似,现在我们的目标是找到一组参数,使得每个 instance 预测出来的概率最大化,即 y=1 的时候  尽可能大,而 y=0 的时候 尽可能大。回想我们学过的概率论,对于这样的一组二项分布数据  我们的目标是似然概率最大化:

求 L 最大化的问题,同样可以通过求 -L 最小化来实现,与线性回归参数求解一样,同样通过梯度下降法来更新向量。在直接进行求导之前,先对 -L 取 log ,将连乘变为累加,方便求导:

一旦我们求得了一组合适的参数,就可以对新的不含 label ( y 值) 的 instance 进行预测,比如 ,我们可以认为要预测的 y 取值为 1 。

现在来看看通过梯度下降如何求借。通用需要对进行每一项求偏导,推导过程需要先对公式进行简化和合并:

所以对前一部分求偏导  ,对后一部分也求偏导

,代入上面的  可以得到:

更新方式与线性回归类似:

程序实现上,同样先是拿到  后计算,然后与进行按位乘操作,得到 的每个元素位,然后对进行按位的更新。

编程过程中的向量化
在程序开发的过程中,我们不可能对每个 instance 的每个位用 for 循环来操作,一般将和 x 当做一整个向量,用 blas 这样的科学计算库来进行加速。

对于多条 instance 的 x 可以当做一个矩阵,和 y 分别是两个一维向量,这样可以进一步使用 blas 的矩阵计算进行加速。

由于逻辑回归通常是对超高维的和 x 进行计算,在进行预测的时候 x 是非常稀疏的,只有少数元素不为 0 ,此时对于单条记录计算  反而是通过一个  index->weight  的 hashmap 查找对应位置的来计算更方便。

梯度计算的调试检查
在进行开发的时候,有时候不确定我们的推导或者公式编码是否正确,这时候需要从数据上推断结果是否正确。有一个简单的办法是通过近似的导数来检查。

因此实际进行调试的时候,我们可以通过   算一个近似值,来跟我们编码后的梯度求导进行对比。一般取 时,求导公式得到的结果与上面的近似值会有至少 4 位有效数字是一致的。

上面是对一维变量进行求导。如果是逻辑回归这样的参数,通常是一个向量,我们如何检查呢?有一个办法是对每一维独立检查,比如有 N 维,我们从 0 到 N-1 ,分别只对这一维单独加减 EPSILON ,其他元素保持不变。然后应用上面的方法,来独立检查这一维的求导结果是否正确。

Softmax regression
上面介绍的逻辑回归是一个二值化问题,y 的取值只有 0 和 1 ,如果我们的预测任务  ,那么我们需要 softmax regression 来进行建模和预测。简单一些理解,可以认为 softmax regression 是 K 个 logistic regression 的归一化:

需要注意的是, 本身就是一个向量,类似逻辑回归里面的 ,因为 x 作为输入对于所有的 K 个分类都是一样的,所以每个分类都有一个属于自己的  向量,所有的 K 个  一起叫做 softmax regression 的模型,该模型的概率表达是:

还是按照前面的套路,我们需要定义一个代价函数来定义模型对数据拟合的代价,并且通过最优化方法使得代价最小化。首先定义指示函数:

通过对所有 instance 拟合的概率最大化,有:

同样取负数把优化目标变为最小化,然后取 log ,得到代价函数:

下面的求导,为了推导方便,我们直接对  进行求导,实际操作的时候是对向量元素的操作。先单独对求和部分里面的     进行求导:

上式是对所有的 k 无差别化的求偏导,结合前面的系数   进行展开, 展开后只剩下   ,后面部分实际上就是   ,因此:

在编程实现的时候,  是一个向量,因此仍然需要按位操作求导和更新。同时,我们发现每一个 instance 实际上都要对 1,2,…,K 的所有进行梯度计算和更新,当 的时候 ,  前面多了一项  ,而对于其他的   仍然是能计算梯度值的,因为实际中即使当  时模型仍然是有概率值的,并不是 0 。

逻辑回归可以看做是 softmax  regression 在 K=2 的时候的特殊情况,那么什么时候使用逻辑回归,什么时候使用 softmax regression 呢?举一个例子,对一篇讲金融和互联网结合的文章进行分类,如果你只允许每篇文章有一个分类值,选互联网就不能是金融,那么就用 softmax regression ,所有 K 个值是归一化的,每次只能输出一个概率最大值作为结果。如果允许给文章打上 <金融,互联网> 两个标签,则可以训练两个逻辑回归分类器,对金融和互联网的概率分别预测。

与逻辑回归的差别:上面我们提到 LR 和 softmax 都可以对 K=2 的任务进行回归预测,而且两种 label 的概率之和都是 1 ,看起来模型训练的时候,二分类问题用两种算法应该是没有区别的?其实不然,从上面的 softmax 求导过程可以发现   对预测结果等于 1 和等于 0 的两部分分别计算误差,更新梯度;而 LR 只利用一个误差来更新梯度。因此同样是二分类问题,softmax 的收敛速度比 LR 更快一些。

梯度下降法

此处可以延展开很多内容,比如随机梯度下降,牛顿法,L-BFGS 等。建议自己系统性的学习了解一下。

 

深度强化学习系列四:状态空间的泛化和DQN

Q-Learning回顾

1) 假设我们进行了很多试验,每次的表达是 (s, a, r, s’, a’, r’, s’’, a’’, r’’, s’’’…)2) 利用每一次transition的结果 (s, a, r, s’) 进行 Q 值更新,

存储 Q(s,a) 值的表虽然是随机初始化的,但是通过 agent 与 environment 的交互,反复迭代,最后会收敛,从而得到最优策略。

上一章我们讲到了可以用时域差分的学习方法,进行Q-Learning来求解最优的策略。

Exploration vs. Exploitation

这是强化学习中非常重要的一个概念。

强化学习希望能根据试验数据学习得到一个最优的策略 ,但是实际上在模型收敛之前我们并不知道什么策略才是最优的 。因此 ,我们需要在 exploration 和 exploitation 之间做一个权衡:一定情况下我们按照目前已知的 “最好” 的策略来执行action(exploitation),但是另外一些情况下,我们需要尝试新的选择,没准我们可以得到更好的结果(exploration)。

最简单的控制 exploration 的方法,就是设置一个随机概率,比如按  小概率随机选择 action,大概率情况下按照目前的policy 来执行 action 。

这种简单粗暴的方式的问题是,当模型都快收敛了,他仍然是在每个状态按概率随机选择action,所以一个改进的办法是随着迭代次数的增加,也慢慢变小。但是有一个更好的解决方案,就是把 exploration  合并在求解策略的过程中一起来表达。

1) 定义一个函数u是一个值(比如Q值或者状态值),n是到达该状态的次数,k是一个奖励系数。

2) 把Q-Learning里面的Q值更新步骤更新为:

由于Q值的计算是需要考虑后续若干 time step 的影响的,在n很小的时候,Q 值由于计算的不够科学,那么依靠k/n,仍然有一定概率会选择执行某个 action 进行尝试;当路径尝试的比较充分后,k/n会非常的小,前面的Q 值占主要的影响成分。

状态空间的泛化

最基本的Q-Learning我们可以看到,需要保存一个(s,a)大小的 Q 值表格,用于记录所有的 Q 值。

但是现实生活中,状态可能是极其海量甚至是无限的,我们不可能把他们全部遍历,也没有那么大的空间把这么大的Q值表装内存里面。所以我们需要像机器学习模型开发特征一样,对状态进行一些泛化,比如:用一些特征来描述当前状态,这样类似状态都是可描述的;同时,对于 Q-Learning 所需要的数据量也会大大减少。

上图这个例子足以说明问题:他们是三种不同的状态,尤其是第三个图和第一个图,右上角少了一个白点。如果按照严格定义,他们必须是三种不同的state,然后结果是我们会先崩溃。所以必须用一些特征来描述他们,使得类似状态具有泛化能力。

状态的特征表达及模型训练

如果我们有机器学习的相关基础,这里就很好说了。简单几句话就是做一些手绘特征来描述当前的状态,比如上面的图:离你最近的豆子的距离,离你最近的 ghost 的距离,当前全局有多少 ghost 等等。

在特征表达的基础上,假设状态的值和状态的描述是紧密相关的(确实也是这样的),那么我们可以把状态的特征和状态值建立一组映射,简单一点,采用线性关系:

把它和Q-Learning结合在一起,通过Q-Learning迭代过程中产生的误差就可以对feature的权重进行梯度更新了。

过程如下:

1) 实验得到 transition(s, a, r, s’)

2) 定义 

3) 对Q(s,a)和w进行更新:

上述过程可以用类似线性回归的方式来辅助理解,但是并不能完全等同。

对于线性回归,使用最小二乘计算误差可以得到误差为:

对w求偏导有:

SGD进行更新:

事实上,扩号中间的误差,近似的可以解释为上面Q值迭代的 difference 。

既然说到了如何手绘特征,那么肯定也会有特征过拟合的问题,这里就不细讲了,了解机器学习的人都有基础。

Deep Q Network

上述描述state的方法显然是与应用场景捆绑的非常死的,因为feature是手工定制的,那么对于一类问题就无法用一种模型来解决。比如玩Atari视频小游戏,每种游戏的 state 如何描述都需要手工定制特征。所以就有了deeplearning和 Q-learning 结合的思路,用 deeplearning 来拟合 Q(s,a) values,用 Q-learning的方法来计算target并得到需要回传的误差,从而训练深度神经网络,得到更好的 Q(s,a) 模型。鉴于融入了网络参数,现在对Q的表示,写为

如果用深度神经网络来拟合Q值函数,有如下两种做法:a)把action的值作为网络的输入,与 state 一起直接建模;b)使用同样的输入和参数,在输出层把各个 action 分开,分别计算他们的 Q Value。

上面写的那个线性拟合的 Q 值函数表达,可以看做是第一种形式。现在推荐采用第二种方式,因为学习的时候,只需要一次前向计算,就可以得到所有action枚举值对应的 Q Value,也能一次性得到最大的那个,正是我们进行强化学习想要的。

按照 DeepMind 的论文描述的方案,他们玩 Atari 视频小游戏的强化学习模型是这样的:输入层使用最近的4帧画面,分别转换成84*84的灰度图,把他们作为含4个 channel 的图像输入 CNN,经过三个卷积层和两个全连接层(具体参数见论文)后,对于最后一层的每个神经元使用线性激活函数进行输出。由于 Atari 游戏一共是18个可选的 action,因此整个网络最后一层的输出节点数是18,每个节点的输出值,都认为是在当前 state选择对应 action 时候的 Q Value。

现在问题回到了对Q Value的线性回归拟合问题,可以直接使用最小二乘的方法来进行最优化求解:

具体步骤如下:

1.  给定输入后进行一次前向计算,得到所有可用action的QValues输出;

2. 选定一个action a执行后,这个时候会来到新的state s’,并且得到一个reward r。重复步骤 1,对s’计算一次Q Values,并选择输出最大的那个

3. 根据步骤 2 的结果计算 action a应该拟合的目标是,对于 a 以外的那些输出节点,把他们应该拟合的 target 设置成步骤 1 里面的输出值,这样他们得到的误差是0;

4. 通过 BP 算法对整个 CNN 网络进行更新。

Experience Replay

虽然现在可以通过深度神经网络来拟合 Q 值函数了,但是人们发现这种非线性的拟合并不是特别稳定。事实上早先提出可以进行特征泛化的时候肯定也有人试过神经网络,但是 DeepMind 为啥就能做出效果呢?

他们用了一个很重要的技巧叫做 experience replay。具体做法是把大量尝试路劲上的<s, a, r, s’>都用一个容器存起来,叫做 replay memory。在训练整个 Q 值网络的时候,我们主要是要训练 的表达,而不限于是在哪个time step,所以干脆每个 mini-batch 直接从 replaymemory里面随机采样一批<s, a, r, s’>的样例出来进行训练。之所以这样做,而不是攒一系列邻近 time step 的样例来进行BP,是因为这种随机采样的没有依赖关系的样例可以消除样例之间的相似性,避免训练过程落入局部最优。而且这种训练方法,也和现实世界更加接近,试想旁观别人玩游戏,我们也都是在记各种场景的处理策略,而非记忆一段连续的游戏样本。

引入 experience  replay后,还考虑 exploration-exploitation,最后的训练过程如下:

1. 根据初始化的网络,结合state s,以 的概率随机选择一个 action,否则选择 Q 值最大的那个 action 输出;

2. 选定一个 action a 执行后,这个时候会来到新的 state s’,并且得到一个 reward r。把<s,a, r, s’>存入 replay  memory  D;

3. 从D中随机采样出一批样例<ss,aa, rr, ss’>送入 DQN,每个样例计算两个 Q 值:

和每个样例输出最大的那个 ;

4. 使用作为误差训练整个 DQN 模型。

延伸内容

目前我们讨论了离散状态的 MDP ,也讲到了非离散状态的状态描述,但是 action 空间仍然是离散的。如何描述连续的 action 空间,比如对话模型中机器人根据上下文描述的对话状态,选择如何回答(执行哪个操作)的策略描述,不是那么容易用离散空间来描述的。相关内容还需要进一步补充。

 

深度强化学习系列三:强化学习的概念和求解方法

Reinforcement Learning (RL)基本概念

一个真实的决策系统分两部分,agent是我们要学习的智能决策模型,environment  是我们要观察的交互对象。根据 environment  和从中抽象得来的状态描述(state), 以及根据 agent 的 action 得到的反馈 reward,agent 根据决策模型做出一个动作的决策,此 action的执行又会改变environment,也就是我们会来到一个新的state(MDP里面s, a, s’的关系)。

我们的目标是:从交互过程中训练agent让它学习如何决策能获得期望最大化的累计rewards。

与经典MDP不同的是,environment并不是可以严格定义的(现实生活总是如此),因此transition (s, a, r, s’)可能并没有解析解,只能不断的实验,通过我们的决策过程产生的一系列可观测样例(observed samples of outcomes)来学习相关策略。MDP虽然states transition有不确定性,但是他的搜索树,是可以离线画好的,不需要“学习”。

更细致一些的对比,MDP的几个基本参数:S, A,T(s, a, s’), R(s, a, s’),MDP的目标是获得最优的策略 。强化学习的目标,也是学习到最优的策略,但是差异点是:并不知道 T 或者 R 的确切表达,他需要不断尝试各种 states 和 actions 来学习T或者 R 。MDP 是可以提前知道火坑是不好的,RL 是真的要往火坑里面跳,通过“血的教训”尝试得到结论。

基于模型的学习方法

这个方法暂时先简单的表达一下:反复暴力穷举尝试各种(s, a)组合,通过观察到的s’,统计计数后归一化可以到到一个近似的 ,同时收集environment反馈的reward,可以得到一个近似的 。暴力穷举的足够多后,我们且认为相关概率的置信度比较高,也就是我们得到了一个可以用的MDP。

剩下的就是通过值迭代的方案,求解MDP的“最优”策略

基于被动学习的方法

之所以叫被动学习,是因为依靠agent大量实验,然后你从别人的踩坑过程里面学习经验教训,得到自己想要的结论。而上面基于模型的方法,是主动出击,自己暴力穷举各种组合,用于计算自己需要的一个近似概率模型。

回想MDP的策略迭代方法,就可以用在这里。固定一种策略,反复试验,收集大量样例及反馈的reward,不考虑T的情况下,仅根据单条样例计算状态值。最后把所有状态值求平均,认为这是一个合理的结果。事实上,只要观测样本足够多,确实也是一个合理的结果。

上述方法的优点是不需要显式的计算T,R;缺点是这种大量的尝试并没有利用已有信息,比如已经走过的路在下一次尝试的时候要重新走,因为时间不能倒退,假设是s(1), s(2), s(3)。现在需要重复实验s(1), s(2)后还有哪种转换可能,是没有办法从s(3)退回到上一状态的,必须重来。所以需要大量实验才能收集到一个可用的state values数据。

当然,你说我写代码的时候把状态暂存就可以了。但是一次实验有多少time step,有多少state和action组合完全未知,可能相当的巨大。理论上讲,这种方式不具有可扩展性和普适性。

时域差分的学习方法

仔细分析上面的问题可以发现,如果按照某固定policy,执行策略验证这样的思路,被动学习存储大量样例求平均是为了让状态值在统计意义上更加可靠;而在真实的环境中,大概率的transition (s, a, s’, r)本身就应该在实验序列里面会更大概率的出现,因此如果我们在一份状态值的基础上,不断合并修正量,理论上大概率的transition的贡献也是大的。类似于最优化方法里面的最速梯度下降和随机梯度下降,一个是收集全数据后全局层面看最合适的方向,一个是在大量样本上直接按样本更新,具有代表性的样本数量多了总体优化方向仍然是正确的。

时域差分的学习方法就被提出来了:

1) 按照现有的策略(比如初始化的固定策略)指导的思路走,得到

2) 每次尝试,都按照如下公式对进行更新:

计算该条样本的目标状态值

把本样例的状态值更新到全局状态值

上式换一种写法

上面公式可以解读为,本条样例状态值与期望值之间的误差,通过步长alpha更新到。随着大量的实验,应该会收敛到一个稳定值。

具体编程实现的时候,回想一下之前的定义,V(s)是一个大表,所有的s都有对应的值,所以上面的都是可以查表得到的。

时域差分的方法,看起来确实解决了策略验证的问题,能收集全一个values of states的大表,但是当我们要进行策略更新时,发现走不下去了:

策略更新居然依赖的是Q-state value而不是state value,而Q值又依赖于T和R。我们忙活了这么多就是为了不显式计算T和R,结果白忙活了。

Q-Learning方法

MDP的值迭代求解方法:

但是V*(s)和Q*(s, a)的关系是:

所以本身我们也可以把值迭代求解方法表示成Q值迭代的形式:

还是按照上面时域差分的方案:

1) 随机产生样例,得到(s, a, s’, r);

2) 每次尝试,都按照如下公式对Q(s,)进行更新:

计算该条样本的状态值

把本样例的状态值更新到全局状态值:

当我们尝试的实验次数足够多,可以证明Q-Learning最后它仍将收敛到最优策略,虽然我们一开始在产生样例的时候action是随机选的。

同理,编程实现的时候,Q(s,a)是一个大表,所有的s和a都是可枚举的,所以公式中的可以查表得到,按照公式对表里面的值进行迭代更新。

下一次迭代的时候,策略可以按进行决策,当然,还有一些其他的因素需要考虑,下一节会详细描述。

未完待续……

 

深度强化学习系列二:马尔科夫决策过程求解

需要求解的最优量

上一部分把求解马尔科夫过程(MDP)的基本概念讲完了,我们已经知道 MDP是如何描述状态转换的过程的了。现在目标是希望结合状态转换函数和奖励函数,求解得到一个最优的策略   follow 他的决策,使得到累计奖励的期望最大化。

说到奖励,又需要对每一步,也就是当前 state 情况下,能评估出大概能获得多少奖励。对奖励信息了解的全面了,把握规律了,才有可能学习到好的策略。

根据需要,定义如下三个量,上标的 *,代表是最优值:

state s的 value:V*(s),他是从状态 s 出发执行最优动作后,期望获得的累计收益;

q-state (s, a) 的 value:Q*(s,a),他是从状态 s 出发,当前已经选定了执行动作 a,此后都执行最优动作,期望获得的累计收益;

最优策略 π*(s):状态s的最优动作。

从程序上理解:V(s) 可以理解为一张大表,表里面的元素位是所有的states,值是最优动作期望的最大收益;Q(s, a) 也是一张大表,不过表里面元素数量是 states*actions,每个元素位是 <某 state, 某 action> 的组合,值是在该 state 执行该 action,之后都是最优动作的情况下期望的最大收益;π (s) 也是一张大表,每个元素位是状态,值是该状态的最优动作

定义好上述三个量,我们要给一个 MDP 求他的最优解,就有两个方法了:可以学习如何表达 V*(s) 或者 Q*(s, a) ,把这个东西求得了最优解,每个状态下查表就知道应该如何决策了;也可以不显式的求状态值,而是一步到位学习一个 π*(s) 的表达,直接根据状态 s 和 π* 就知道要选择哪个action。

状态值(Values of States)及其递归定义

从上面的定义,不难看出,V*(s)和Q*(s, a)的关系是:V*(s)=maxaQ*(s,a) ,再看Q*(s, a) 的定义,他只明确了当前一步的 action a,后续步骤仍然是执行最优动作,所以后续的(假设下一步状态是 s’)待打折的奖励是 V*(s’);当前 transition的奖励 R(s,a,s’);本次动作 a 会转换到哪些状态都是有可能的,所以他是当前 action 可能转换到的所有后继状态  s’ 的一个加权平均:

式中是上一节提到的折扣系数。

把 Q*(s, a) 的完整表达代入 V*(s) 有:

我们可以发现,s’ 是 s 的后继状态,这说明最优的状态值,是可以递归表达的!

当然,如果我们不是展开 Q*(s,a),而是展开 V*(s’),q-state 的值函数也是可以递归表达的。上述方程,我们叫做 Bellman 方程。

 

 

基于状态值迭代最优策略求解

注意

由于我们习惯从0开始数,有些教材,比如 OpenAI 的教材上, 是 的下一个状态。而伯克利的 AI 课程,是通过当前 time step 到结束态的步数来计数的,也就是 是结束态,表示离结束态还有 k 步的状态 s 的值,它的 time step 下标是反过来计数的。两者的主要差异在于,值迭代是从后往前递归,那么下标反过来更好理解;策略迭代是从前往后迭代优化,所以下标按正常顺序比较好理解。为了避免搞混了顺序,我后面的所有下标都从 0 开始,到 T 结束。

Bellman 方程指导我们,要想得到最优结果拿到最大期望的累计奖励,需要 2 步:

1. 第一个动作要做对了(当前状态的最优动作);

2. 后续所有动作和转换都保持最优(因为是一个迭代过程)。

把上面的步骤反过来看:假设后面都是最优的,选取当前能获得最大收益的最优动作,逐步回溯把状态的最优值都求出来的过程,实际上就是 MDP 期望最大化的求解过程。

我们设定结束态 (最后的大奖励包含在 T-1 步的 R(s, a, s’) 里面了),往回递归可以得到:

每轮迭代回溯到开始状态需要的计算复杂度,只要折扣系数小于1,多次迭代后可以证明值函数会收敛,得到一个稳定的状态值结果。简单证明:如果 T 不大,所有值都可计算。如果T非常大,结束态是一个常量的情况下,由于折扣系数(且小于 1 )的存在,回溯的计算过程中的差异是足够小的,因此逐步回溯一定会收敛。

状态值的大表收敛后,当我们需要进行决策,可以通过查表,选择能让 V(s) 最大化的那个 action 执行。

基于策略迭代最优策略求解

值迭代是一种从后向前反推最优策略的方法,另外一种解决方法,是对策略的迭代求解:假设我们有一个好的策略 π:S—>A,我们就可以知道当前什么动作最好,并且后面一直保持最优。

为了解决这个问题,首先我们要有一个评估方法,不论策略是否最优,需要知道通过他能获得多少累计奖励,然后再看能否通过迭代优化,下一次把累计奖励提升。好在我们有 V(s) 的计算公式,只不过计算得到的不是最优值而已,但是仍然是可以量化对比的。

下面开始策略迭代的第一步:先固定住策略 π ,比如他就是一个随机的 (s,a) 状态表,或者是一个执行某个固定 action a 一条路走到黑的规则。不管怎么样,我们有了一个可执行的 π 了。

下面两个图,左边的是最优策略的做法,它遍历所有 action 并选择所有 action 里面能获得期望最大累计收益的一个;右边是固定策略,它根据 s 直接指定一个动作 π(s) ,按照这个路径执行。

这里我们可能会有个疑问,follow π (s),action 的分支路径是有了,从  q-state (s, π (s)) 到下一状态 s’ 的转换路径选哪条?别忘记了,我们面对的问题是一个真实的具有反馈的系统,比如他是一个游戏,或者自动驾驶,我们在 state s 执行action π (s),最后会转到那个状态,死了还是活着,掉沟里面还是撞到墙了,外部系统都是有直接反馈的,也就是 s’ 是外部对我们的动作的一个反馈结果,在策略迭代的过程中,s’ 是可以获得的。

然后我们就按照这个固定策略把过程走一遍,最后仍然可以得到一个递归关系来计算该策略下的值状态。需要注意的是,这里没有 max 操作了,因为每次只有一个特定的 action 在执行。

按照上面状态值收敛性的证明,我们需要把一个策略反复运行,直到状态值收敛,每轮迭代的计算复杂度是  因为 action 是直接得到的,不需要遍历所有 action 取最大。

举个例子,下面的图是两旁都是火坑,reward=-10,最上面是宝石,reward=100 的一个迷宫游戏,两个策略分别是:一直向右走和一直向前走。令  最后经过大量实验,通过 Bellman 公式回溯计算各步 ,可以得到两种策略各个状态的  如下图:

为什么 GO RIGHT 策略上面还有值?因为系统具有的不确定性,虽然是向右走,仍然有一定概率会向上(补充一下细节,伯克利的 AI 课程里面有关这个机器人找宝石的例子,都设置了 80% 的概率按指定方向走,同时各有 10% 的概率会向左右两边走)。就像开车持续踩油门会不会爆缸,随着外部环境不一样,整个事件的不确定性都是不一样的。

能对策略进行状态值评估后,我们可以对策略进行改进,并进行下一轮的状态评估。如此往复直到策略收敛为止。迭代步骤如下:

1).对当前策略进行多次迭代直到状态值收敛:

2).对所有状态 s,取能获得最大累计收益的 action a ,来更新 π(s):

值迭代和策略迭代的对比

事实上两种迭代求解方法,都是在用动态规划求解马尔科夫决策过程,并且都能达到最优值。

值迭代虽然不显式的对策略进行计算,但是迭代求解最优值的过程中,是需要隐式挑选最优策略的;而策略迭代虽然主要是更新 π (s),但是他是结合当前策略为每个 state 挑选能最大化状态值的 action。

一般来说,基于策略的迭代比基于值的迭代要收敛的更快一些。

MDP 与强化学习

到目前为止,MDP 的基本概念讲完了。我们发现一个问题,一直以来举例用的机器人走迷宫的游戏,从 q-state 到 s’ 的转移概率我们是定好了的。也就是给定规则,给定 transition model,我们可以离线的计算出最优策略,而不需要试探性的做很多尝试。解决问题的过程,是在解决一个规划问题。

但是,现实生活中我们要解决的问题虽然源自于 MDP,但是外部系统的特性是未知的,我们没有有关 transition model 的先验知识,关于反馈的收集,状态空间的探索,都需要我们不断的尝试。甚至 state 和 action 空间也不是离散的,而是在一个连续空间建模。因此需要一些方法在线的学习计算相关部分。这就是后面要讲的强化学习。

未完待续……

 

深度强化学习系列一:马尔科夫决策过程简介

前言

强化学习简短概括:通过观察机器人在与外界系统的决策交互过程中,产生的状态变化以及带来的收益,学习一个最优的决策模型,使得未来进行自动决策的时候能获得期望最大化累积收益

这里有两个很重要的概念在后面的文章中反复提到,也是要解决的问题,需要牢记。一个是累积收益,不能只看眼前的一步决策,简单粗暴的用贪心策略。同时要考虑交互过程状态转移的不确定性,目标是求解累积收益的期望最大化,而不能简单理解为能用if else表达的动态规划。

为了能更好的理解深度强化学习,我们需要从最开始的马尔科夫决策过程开始,逐步深入,最后才能明白为什么我们需要用深度神经网络结合强化学习,以及这样做解决了什么问题。文章内容是通过学习伯克利的 AI 课程后转写的,有讲的不明白的地方,可以去看一下原始课程的视频,8-11课。

最后一篇后,我们可以用 DQN 开发一个学习机器,自动玩 flappy bird 。效果如下:

 

下面开始第一部分。

不确定的搜索问题

不确定性主要是用来描述现实生活中的一些环境因素对你做出的决策的响应是不确定的。他并不像我们写的程序严格的按照 if else 的分支来走,而是事件响应的结果包含一些受环境影响的随机性因素。搜索在这里是一个大的概念,不是我们说的狭义的“搜索引擎”。它是面向一个目标进行(搜索)路径的规划,可以理解为像搜索树一样的寻找目标。

两者结合,不确定的搜索问题,可以简单理解为在按照某种方式进行(搜索)寻路的过程中,存在不确定性,并不是严格意义上的不是向左就是向右子树转移的过程。

一个简单的例子,让机器人沿着峭壁走去取宝石,向左走向右走,也可以向前走,如果看成是一个取宝石的路径搜索问题,从一个点出发,有左右前三个子树可以转移,到达下一个状态后,又可以左右前。但是在真实环境中,这个问题是含有不确定性的。即使发出的动作是向右走,会不会有一定概率掉到火坑里面(局面实际上转变成了向前走),都是可能的。这种不确定性,我们可以观察学习到,但是发生的过程完全不受我们控制。

确定性和随机性可以用下面一个图简单的表示(此时请抛开程序员 if else hard code的思维)。左图是理想情况,系统作出的决策是向上走,永远只有一个结果就是机器人向上挪动;右图更贴近于真实环境,系统作出的决策是向上走,但是在一个具有不确定性的环境下,最后的响应会是机器人往哪个方向挪动,是具有一定随机性的,随机性的分布,这个取决于环境。举个例子,真实环境下路面可能打滑,你希望向上走,脚滑了一下就掉左边坑里面了,😊

在这种具有不确定性的环境中,一般我们都会设定一个目标(比如赢或者输),在向目标前进去做决策路径搜索的时候,我们希望过程中的累积收益最大化。

比如以上面机器人自动学习走迷宫的游戏为例,游戏的目标就是找到宝石,并且避免掉入火坑。我们可以把目标达成(获得宝石或者掉进火坑)设定为结束态,机器人在这两个状态下会得到一个大额的奖励或者惩罚。只要没到结束态,每走一步,都会得到一个当前存活的奖励。当然,这个存活奖励也可以为负数,比如你始终在里面打转刷分,或者一直拖着不达成目标(结束游戏)是不可行的。

我们希望有一个模型能自动学会如何玩这个游戏(描述如何对状态和动作路径进行搜索,解决一个问题),最后的目标是,到达结束态后,使得所有奖励累加和最大化。

 马尔科夫决策过程( MDP)

上述不确定性问题可以用马尔科夫决策过程来描述。我们先给出一些马尔科夫决策过程的符号定义:

a. 一个状态(state)s的集合 

b. 一个动作(action)a的集合 

c. 一个转换函数 T(s, a, s’),简单理解为条件概率 P(s’|s, a)

d. 一个奖励(reward)函数R(s, a, s’),这包含中间激励和最后结束态的大奖励

e. 给定一个初始状态,有的教材标记为

f.(可能需要)给定一个结束状态,有的教材记序列长度为T,结束态标记为 

MDP是一类不确定性的搜索问题,我们的目标是结合奖励函数搜索一个可行的状态转换路径(state 和 action 的序列)使得奖励最大化。

至于为什么叫马尔科夫决策过程呢?那是因为认为状态转换,只跟当前时刻的 state 和 action 有关:

决策体现在你要根据 state 和潜在的奖励,选择一个 action ;不确定性体现在转换函数,状态 s 下执行动作 a ,最后到达的状态 s’ 具有不确定性,奖励 R 同理。

 策略(Policy)

在一个确定性的单agent搜索问题中,我们搜索的目标,是一个从起始状态到结束态的最优的路径规划,或者一个 action 的序列。但是在 MDP 中,由于不确定性的存在,我们无法得到一个严格的序列,我们只能得到一个最优的决策函数,由它告诉我们每一步应该怎么走,我们称之为策略(policy),标记为 ,策略可以告诉我们在当前 state 情况下要做什么 action 。而按照最优的策略的执行路径,是最大化期望收益的过程。

把上面的游戏数字化,可以发现当奖励函数不一样的时候,最优策略是不一样的。注意火坑(reward=-1)左边的 state ,如果每一步得到的 reward 是 -0.01,最优策略是向左走,这样有一定概率进入上面和下面的状态,而多次尝试的累计 reward 负数并不会太大;相反,如果单步 reward 被设置成 -2.0,这个状态的最佳策略是直接跳进火坑,死了也就是-1.0,比其他任何  action 得到的收益都要大。

MDP搜索树

为了方便理解 MDP,我们把 MDP 的状态转移展开,然后整个求期望奖励最大化的过程,可以看做是一个期望最大化的搜索树里面的搜索过程(需要时刻牢记不确定性)。

解释一下下面的图,他引入了一个很重要的概念:q-state。我们在一个状态s,follow 策略选择了动作 a,这里需要引入一个中间态的树节点 (s,a) ,称之为 q-state 。这个节点的意思是,(s,a) 完成了决策过程,但是状态转换并没有完成,因为 (s,a) 得到的是哪个 s’,这里面还具有一些不确定性,也就是 P(s’|s,a) 的存在。q-state 还需要经过一个 transition 才最后输出 s’,同时得到奖励 R(s,a, s’)。

累计奖励的折扣问题

上面说到了我们的策略需要得到的是从开始到结束态的期望奖励累计总和最大化,那么就会面临一个问题:每一次状态转换都会得到或大或小的 reward ,显然我们要兼顾考虑当前转换的 reward ,同时也要考虑此次转换对后续的影响以及后续能获得的 reward 。那么最优策略在进行路径搜索的时候,是优先抓住当前 reward ,还是优先考虑积攒到后面再一次性变现?当不同时期的 reward 大小出现明显差异时,谁都知道要取大的。但是当 reward 大小并没有明显差异时,是先苦后甜还是先甜后苦,如何决策呢?

结合我们的最终目标,是最大化奖励的总和。那么更合理的策略,是把当前能获得的奖励都拿到手。除非未来的奖励能出现暴涨性的升值,否则相同价值的东西放在以后兑现,总是没有现在直接拿到手里值钱的。

由此就引出了奖励的折扣问题,我们站在当前 timestep ,去计算未来的综合收益时,需要对未来的奖励进行打折,打折系数记为,那么下一个 time step 的奖励就是 ,下下一个time step 是 

打折除了是考虑价值贬值,也有利于算法收敛。因为到达结束态的决策过程可能是非常长,甚至是一个无限的状态转换序列(比如 flappybird ),我们也不可能无限期的计算,去考虑未来的收益。引入折扣系数后,基本可以忽略未来步后的影响,也就是定义了一个当前状态需要考虑的未来有效时间区域。

当然,除了引入折扣系数的方法,还有其他方法来处理无限序列问题,这里就不展开讲了。可以看伯克利 AI 课程的视频。

所有图片版权来自于伯克利教程,或者网络。如有版权冲突请联系我们。

连续决策过程中的奖励定义清楚后,下一篇文章我们将讲述如何求解最优策略,来获取期望最大化的累积奖励,敬请期待。