本章数据集下载

第6章Spark MLlib基础

传统的机器学习算法，由于技术和单机存储的限制，只能在少量数据上使用。一旦数据量过大，往往需要采用数据抽样的方法。但这种抽样很难保证不走样。近些年随着 HDFS 等分布式文件系统出现，存储海量数据已经成为可能。在全量数据上进行机器学习变得可能或必要，但由于MapReduce计算框架，虽然实现分布式计算，但中间结果需要存在到磁盘，这对这计算过程中需要多次迭代的机器学习，因为通常情况下机器学习算法参数学习的过程都是迭代计算的，不很理想。
Spark的出现，正好弥补了MapReduce的不足，它立足于内存计算，所以特别适合机器学习的迭代式计算。同时Spark提供了一个基于海量数据的分布式运算的机器学习库，同时提供了很多特征选取、特征转换等内嵌函数，大大降低了大家学习和使用Spark的门槛，对很多开发者只需对 Spark 有一定基础、了解机器学习算法的基本原理、以及相关参数的含义和作用，一般都可以通过都可以比较顺利地使用Spark进行基于大数据的机器学习。
Spark在机器学习方面有很多优势，本章主要Spark与机器学习相关的内容。
 Spark MLlib简介
 Spark MLlib架构
 常用的几种数据类型
 基础统计
 RDD、DataFrame及Dataset间的异同
 Spark MLlib常用算法

6.1Spark MLlib简介

MLlib是MLBase一部分，其中MLBase分为四部分：MLlib、MLI、ML Optimizer和MLRuntime。它们的结构如下图：

图6-2 MLBase四部分关系

6.2Spark MLlib架构

6.3数据类型

Spark MLlib的数据类型主要分为四种，下面将分别介绍。
1. 本地向量（Local vector）
其创建方式主要有以下几种：（以下使用Scala语言）

2. 标记点（Labeled point）
标记点是由一个本地向量（密集或稀疏）和一个标签（整数或浮点）组成，这个值的具体内容可以由用户指定。

从文件中直接获取标记点：

3. 本地矩阵（Local matrix）
由行索引、列索引、类型值组成，存放在单机中。

4. 分布式矩阵（Distributed matrix）

6.4 基础统计

6.4.1摘要统计

示例代码如下：

6.4.2相关性

目前Spark支持两种相关性（correlations）系数：皮尔森相关系数（pearson）和斯皮尔曼等级相关系数（spearman）。下面通过示例说明相关系统的如何计算。

6.4.3假设检验

假设检验(Hypothesis testing),Spark MLlib目前支持皮尔森卡方检测（Pearson’s chi-squared tests），包括适配度检测和独立性检测。适配度检测要求输入为Vector, 独立性检验要求输入是Matrix。
代码示例：

6.4.4随机数据生成

代码示例：

6.5 RDD、Dataframe和Dataset

目前，spark.mllib包中基于RDD的APIs已进入维护模式，以后将以spark.ml包中的基于DataFrame的API为主。

6.5.1RDD

RDD是Spark建立之初的核心API。它是一种有容错机制的特殊集合， RDD是不可变分布式弹性数据集，在Spark集群中可跨节点分区，以函数式编程操作集合的方式，进行各种并行操作，提供分布式low-level API来操作，包括transformation和action等。

6.5.2Dataset/DataFrame

DataFrame与RDD相同之处，都是不可变分布式弹性数据集。不同之处在于，DataFrame多了数据的结构信息，即schema，类似于传统数据库中的表。

6.5.3相互转换

RDD、DataFrame和Dataset间可以互相转换。

6.6小结

本章主要介绍了Spark MLlib的一些内容，包括MLlib的生态、架构等内容，同时介绍了Spark MLlib算法底层依赖的基础内容，如数据类型、基础统计等，最后简单介绍了RDD、DataFrame与Dataset间的异同等。后续章节我们将通过一些实例，说明如何把前几章介绍的一些方法应用到具体实例中。

本章数据集下载

第5章 模型选择和优化

本章主要介绍如何使用Spark ML提供的方法及自定义函数等方法来对模型进行调优。我们可以通过Spark ML内建的交叉验证、训练验证拆方法、网格参数等方法进行模型调优，当然也可以自定义函数进行模型优化。
本章主要内容包括：
 模型选择
 交叉验证
 训练验证拆分法
 自定义函数调优

5.1 模型选择

调优可以是对单个的Estimator，比如LogisticRegression，或者对包含多个算法、特征化和其他步骤的整个Pipline。用户可以一次性对整个Pipline进行调优，而不必对Pipline中的每一个元素进行单独的调优。
MLlib支持使用像交叉验证（CrossValidator）和训练验证拆分法（TrainValidationSplit）这样的工具进行模型选择(Model selection)。这些工具需要以下的组件：
 Estimator：用户调优的算法或Pipline
 ParamMap集合：提供参数选择，有时也叫作用户查找的“参数网格”
 Evaluator：衡量模型在测试数据上的拟合程度
在上层，这些模型选择工具的工作方式如下：
 将输入数据切分成训练数据集和测试数据集
 对于每一个（训练数据，测试数据）对，通过ParamMap集合进行迭代：对于每个ParamMap，使用它提供的参数对Estimator进行拟合，给出拟合模型，然后使用Evaluator来评估模型的性能。
 选择表现最好的参数集合生成的模型。

5.2交叉验证

下例使CrossValidator从整个网格的参数中选择合适的参数，而从自动选择最优模型。
在整个参数网格中进行交叉验证是比较耗时的。例如，在下面的例子中，参数网格有3个hashingTF.numFeatures值和2个lr.regParam值，CrossValidator使用2折切分数据。最终将有(3 * 2) * 2 = 12个不同的模型将被训练。在真实场景中，很可能使用更多的参数和进行更多折切分（k=3和k=10都很常见）。使用CrossValidator的代价可能会异常的高，当大数据集比较大时，需要慎重选择。不过采用交叉验证法，对比手动调优，还是有较大优势。
下面通过示例说明如何使用CrossValidator从整个网格的参数中选择合适的参数。
导入必要的包：

配置一个流水线，该流水线包含3个stages: tokenizer, hashingTF, and lr。

使用ParamGridBuilder构造一个parameter grid

流水线，嵌入到CrossValidator实例中，这样流水线的任务都可使用网格参数。
CrossValidator一般需要一个Estimator, 参数集及一个评估器Evaluator。
BinaryClassificationEvaluator缺省的评估指标为AUC(areaUnderROC)。

通过交叉验证模型, 并获取最优参数集，并测试模型

查看最佳模型中各参数值

5.3训练验证拆分法

像CrossValidator一样，TrainValidationSplit最终适合使用最好的ParamMap
和整个数据集的Estimator。

5.4自定义模型选择

the best model was trained with rank = 20 and lambda = 0.1, and numIter = 10, and its RMSE on the test set is 1.0059139723438042.

5.5小结

本章主要介绍了几种模型选择或调优的方法，我们可以从训练的数据集入手，可以从模型参数入手，当然也可把两者结合起来。实际上模型的优化还有很多其他方法，如使用不同的算法、集成算法等等。下一章我们将介绍Spark MLlib一些基础知识，包括Spark MLlib架构、原理、算法及算法依赖的一些库、向量和矩阵等相关内容。

 

第2章 概率与信息论

本章讨论概率论和信息论，概率论是用于表示不确定性陈述的数学框架，即它是对事物不确定性的度量。
在人工智能领域，我们主要以两种方式来使用概率论。首先，概率法则告诉我们AI系统应该如何推理，所以我们设计一些算法来计算或者近似由概率论导出的表达式。其次，我们可以用概率和统计从理论上分析我们提出的AI系统的行为。
计算机科学的许多分支处理的对象都是完全确定的实体，但机器学习却大量使用概率论。实际上如果你了解机器学习的工作原理你就会觉得这个很正常。因为机器学习大部分时候处理的都是不确定量或随机量。
概率论和信息论是众多科学学科和工程学科的基础，也是机器学习、深度学习的重要基础。
如果你对概率论和信息论很熟悉了，可以跳过这章。如果你觉得这些内容还不够，还想进一步了解相关知识，可以参考相关专业教材。

2.1为何要概率、信息论

机器学习、深度学习需要借助概率、信息论？
要回答这个问题，我觉得至少应该了解以下两个问题：
（1）概率、信息论的主要任务；
（2）机器学习、深度学习与概率、信息论有哪些因缘。
概率研究对象不是预习知道或确定的事情，而是预习不确定或随机事件。研究这些不确定或随机事件背后规律或规则。或许有人会说，这些不确定或随机事件有啥好研究？他们本来就不确定或随机的，飘忽不定、不可捉摸。表面上看起来确实如此，有句话说得好：偶然中有必然，必然中有偶然。就拿我们比较熟悉微积分来说吧，如果单看有限的几步，很多问题都杂乱无章，还难处理，但是一旦加上一个无穷大（∞）这个“照妖镜”，其背后规律立显、原来难处理的也好处理了。概率研究的对象也类似。如大数定律、各种分布等等。
信息论主要研究对一个信号包含信息的多少进行量化。它的基本思想是一个不太可能的事件居然发生了，其提供的信息量要比一个非常可能发生的事件更多。这个看起来，也好像与我们的直觉相矛盾。
说起机器学习、深度学习与概率、信息论的因缘可就多了：
（1）被建模系统内在的随机性。例如一个假想的纸牌游戏，在这个游戏中我们假设纸牌被真正混洗成了随机顺序。
（2不完全观测。即使是确定的系统，当我们不能观测到所有驱动系统行为的所有变量或因素时，该系统也会呈现随机性。
（3）不完全建模。例如，假设我们制作了一个机器人，它可以准确地观察周围每一个对象的位置。 在对这些对象将来的位置进行预测时，如果机器人采用的是离散化的空间，那么离散化的方法将使得机器人无法确定对象们的精确位置：因为每个对象都可能处于它被观测到的离散单元的任何一个角落。也就是说，当不完全建模时，我们不能明确的确定结果，这个时候的不确定，就需要借助概率来处理。
由此看来，概率、信息论很重要，机器学习、深度学习确实很需要它们。后续我们可以看到很多实例，见证概率、信息论在机器学习、深度学习中是如何发挥它们作用的。

2.2样本空间与随机变量

样本空间
样本空间是一个实验或随机试验所有可能结果的集合，而随机试验中的每个可能结果称为样本点。例如，如果抛掷一枚硬币，那么样本空间就是集合{正面，反面}。如果投掷一个骰子，那么样本空间就是 {1,2,3,4,5,6}。
随机变量
随机变量，顾名思义，就是“其值随机而定”的变量，一个随机试验有许多可能结果，到底出现哪个预先是不知道的，其结果只有等到试验完成后，才能确定。如掷骰子，掷出的点数X是一个随机变量，它可以取1,2,3,4,5,6中的任何一个，到底是哪一个，要等掷了骰子以后才知道。因此，随机变量又是试验结果的函数，它为每一个试验结果分配一个值。比如，在一次扔硬币事件中，如果把获得的背面的次数作为随机变量X,则X可以取两个值，分别是0和1。如果随机变量X的取值是有限的或者是可数无穷尽的值，如：

2.3概率分布

概率分布用来描述随机变量（含随机向量）在每一个可能取到的状态的可能性大小。概率分布的有不同方式，这取决于随机变量是离散的还是连续的。
对于随机变量X,其概率分布通常记为P(X=x),或X ~P(x)，表示X服从概率分布P(x)。
概率分布描述了取单点值的可能性或概率，但在实际应用中，我们并不关心取某一值的概率，特别是对连续型随机变量，它在某点的概率都是0，这个后续章节将介绍。因此，我们通常比较关心随机变量落在某一区间的概率，为此，引入分布函数的概念。

2.3.1 离散型随机变量

例如，设X的概率分布由例1给出，则
F(2)=P(X≤2)=P(X=0)+P(X=l)=0.04+0.32=0.36
常见的离散随机变量的分布有：
（1）两点分布
若随机变量X只可能取0和1两个值，且它的分布列为P(X=1)=p，P(X = 0) = l − P 其中(0 < P < 1)，则称X服从参数为p的两点分布，记作X~B(1, p)。其分布函数为

（2）二项分布
二项分布是最重要的离散概率分布之一，由瑞士数学家雅各布•伯努利（Jokab Bernoulli）所发展，一般用二项分布来计算概率的前提是，每次抽出样品后再放回去，并且只能有两种试验结果，比如黑球或红球，正品或次品等。二项分布指出，随机一次试验出现的概率如果为p，那么在n次试验中出现k次的概率为：

假设随机变量X满足二项分布，且知道n，p，k等参数，我们如何求出各种情况的概率值呢？方法比较多，这里介绍一种非常简单的方法，利用Python的scipy库可以非常简单，直接利用这个统计接口stats即可，具体如下：

（3）泊松(Poisson)分布
若随机变量X所有可能取值为0，1，2，…，它取各个值的概率为：

这里介绍了离散型随机变量的分布情况，如果X是连续型随机变量，其分布函数通常通过密度函数来描述，具体请看下一节

2.3.2 连续型随机变量

与离散型随机变量不同，连续型随机变量采用概率密度函数来描述变量的概率分布。如果一个函数f(x)是密度函数，满足以下三个性质，我们就称f(x)为概率密度函数。

图2-1 概率密度函数
对连续型随机变量在任意一点的概率处处为0。
假设有任意小的实数∆x，由于{X=x}⊂{x-∆x<X≤x},由式（2.1）分布函数的定义可得：

这个连续分布被称之为正态分布，或者高斯分布。其密度函数的曲线呈对称钟形，因此又被称之为钟形曲线，其中μ是平均值，σ是标准差（何为平均值、标准差后续我们会介绍）。正态分布是一种理想分布。
正态分布如何用Python实现呢？同样，我们可以借助其scipy库中stats来实现，非常方便。

正态分布的取值可以从负无穷到正无穷。这里我们为便于可视化，只取把X数据定义在[-6,6]之间，用stats.norm.pdf得到正态分布的概率密度函数。另外从图形可以看出，上面两图的均值u都是0，只是标准差（σ）不同，这就导致图像的离散程度不同，标准差大的更分散，个中原因，我们在介绍随机变量的数字特征时将进一步说明。

2.4边缘概率

对于多维随机变量，如二维随机变量(X,Y),假设其联合概率分布为F(x,y),我们经常遇到求其中一个随机变量的概率分布的情况。这种定义在子集上的概率分布称为边缘概率分布。
例如，假设有两个离散的随机变量X,Y,且知道P(X,Y),那么我们可以通过下面求和的方法，得到边缘概率P(X):

边缘概率如何计算呢？这里我们通过一个实例来说明。假设有两个离散型随机变量X,Y，其联合分布概率如下：
表1.1：X与Y的联合分布

如果我们要求P(Y=0)的边缘概率，根据式（2.7）可得：
P(Y=0)=P(X=1,Y=0)+P(X=2,Y=0)=0.05+0.28=0.33

2.5条件概率

上一节我们介绍了边缘概率，它是值多维随机变量一个子集（或分量）上的概率分布。对于含多个随机变量的事件中，经常遇到求某个事件在其它事件发生的概率，例如，在表1.1的分布中，假设我们要求当Y=0的条件下，求X=1的概率？这种概率叫作条件概率。条件概率如何求？我们先看一般情况。
设有两个随机变量X,Y,我们将把X=x，Y=y发生的条件概率记为P(Y=y|X=x),那么这个条件概率可以通过以下公式计算：

其中P(Y=0)是一个边缘概率，其值为：P(X=1,Y=0)+P(X=2,Y=0)=0.05+0.28=0.33
而P(X=1，Y=0)=0.05.故P(X=1|Y=0)=0.05/0.33=5/33

2.6条件概率的链式法则

条件概率的链式法则，又称为乘法法则，把式（2.10）变形，可得到条件概率的乘法法则：
P(X,Y)=P(X)xP(Y|X)                                                                                        (2.11)
根据式（2.11）可以推广到多维随机变量，如：
P(X,Y,Z)=P(Y,Z)xP(X|Y,Z)
而P(Y,Z)=P(Z)xP(Y|Z)
由此可得：P(X,Y,Z)=P(X|Y,Z)x P(Y|Z)xP(Z)                                               （2.12）
更多维的情况，以此类推。

2.7独立性及条件独立性

两个随机变量X,Y,如果它们的概率分布可以表示为两个因子的乘积，并一个因子只含x，另一个因子只含y，那么我们就称这两个随机变量互相独立。这句话可能不好理解，我们换一种方式的来表达。或许更好理解。
如果对 ∀x∈X,y∈Y,P(X=x,Y=y)=P(X=x)P(Y=y) 成立，那么随机变量X,Y互相独立。
在机器学习中，随机变量为互相独立的情况非常普遍，一旦互相独立，联合分布的计算就变得非常简单。
这是不带条件的随机变量的独立性定义，如果两个随机变量带有条件，如P(X,Y|Z),它的独立性如何定义呢？这个与上面的定义类似。具体定义如下：
如果对∀x∈X,y∈Y,z∈Z,P(X=x,Y=y|Z=z)=P(X=x|Z=z)P(Y=y|Z=z) 成立
那么随机变量X,Y在给定随机变量Z时是条件独立的。
为便于表达，如果随机变量X,Y互相独立，又可记为X⊥Y,如果随机变量X,Y在给定时互相独立，则可记为X⊥Y|Z。
以上主要介绍离散型随机变量的独立性和条件独立性，如果是连续型随机变量，我们只要把概率换成随机变量的密度函数即可。

2.8期望、方差、协方差

在机器学习、深度学习中经常需要分析随机变量的数据特征及随机变量间的关系等，对于这些指标的衡量在概率统计中有相关的内容，如用来衡量随机变量的取值大小的期望(Expectation)值或平均值、衡量随机变量数据离散程度的方差(Variance)、揭示随机向量间关系的协调方差(Convariance)等。
这些衡量指标的定义及公式就是本节主要内容。
首先我们看随机变量的数学期望的定义：
对离散型随机变量X,设其分布律为：

期望有一些重要性质，具体如下：
设a,b为一个常数，X和Y是两个随机变量。则有：
（1）E(a)=a
（2）E(aX)=aE(X)
（3）E(aX+bY)=aE(X)+bE(Y)                                                                      (2.19)
（4）当X和Y相互独立时，则有：
E(XY)=E(X)E(Y)                                                                                      (2.20)
数学期望也常称为均值，即随机变量取值的平均值之意，当然这个平均，是指以概率为权的加权平均。期望值可大致描述数据的大小，但无法描述数据的离散程度，这里我们介绍一种刻画随机变量在其中心位置附近离散程度的数字特征，即方差。如何定义方差？
假设随机向量X有均值E(X)=a。试验中，X取的值当然不一定恰好是a，可能会有所偏离。偏离的量X-a本身也是一个随机变量。如果我们用X-a来刻画随机变量X的离散程度，当然不能取X-a的均值，因E(X-a)=0 ,说明正负偏离抵消了，当然我们可以取|X-a|这样可以防止正负抵消的情况，但绝对值在实际运算时很不方便。人们就考虑另一种方法，先对X-a平方以便消去符号，然后再取平均得

方差的平方根被称为标准差。
对于多维随机向量，如二维随机向量(X,Y)如何刻画这些分量间的关系？显然均值、方差都无能为力。这里我们引入协方差的定义，我们知道方差是X-EX乘以X-EX的均值，如果我们把其中一个换成Y-EY，就得到E(X-EX)(Y-EY),其形式接近方差，又有X,Y两者的参与，由此得出协方差的定义，随机变量X,Y的协方差，记为：Cov(X,Y)
Cov(X,Y) = E(X-EX)(Y-EY)                                                                             (2.22)
协方差的另一种表达方式：
Cov(X,Y) = E(XY)-EX×EY                                                                               (2.23)
方差可以用来衡量随机变量与均值的偏离程度或随机变量取值的离散度，而协方差则可衡量随机变量间的相关性强度，如果X与Y独立，那么它们的协方差为0。注意反之，并不一定成立，独立性比协方差为0的条件更强。不过如果随机变量X、Y都是正态分布，此时独立和协方差为0是一个概念。
当协方差为正时，表示随机变量X、Y为正相关；如果协方差为负，表示随机变量X、Y为负相关。
为了更好的衡量随机变量间的相关性，我们一般使用相关系数来衡量，相关系数将每个变量的贡献进行归一化，使其只衡量变量的相关性而不受各变量尺寸大小的影响，相关系统的计算公式如下：

求随机变量的方差、协方差、相关系统等，使用Python的numpy相关的函数，如用numpy.var求方差，numpy.cov求协方差，使用numpy.corrcoef求相关系数，比较简单，这里就不展开来说。
在机器学习中多维随机向量，通常以矩阵的方式出现，所以求随机变量间的线性相关性，就转换为求矩阵中列或行的线性相关性。这里我们举一个简单实例，来说明如果分析向量间的线性相关性并可视化结果。这个例子中使用的随机向量（或特征值）共有三个，一个是气温(temp),一个体感温度(atemp),一个是标签（label）说明共享单车每日出租量，以下是这三个特征的部分数据：

这里使用Python中数据分析库pandas及画图库matplotlib 、sns等。

从以上图可以看出，特征temp与atemp是线性相关的，其分布接近正态分布。

2.9贝叶斯定理

贝叶斯定理是概率论中的一个定理，它跟随机变量的条件概率以及边缘概率分布有关。在有些关于概率的解释中，贝叶斯定理（贝叶斯公式）能够告知我们如何利用新证据修改已有的看法。这个名称来自于托马斯•贝叶斯。
通常，事件A在事件B（发生）的条件下的概率，与事件B在事件A（发生）的条件下的概率是不一样的；然而，这两者是有确定的关系的，贝叶斯定理就是这种关系的陈述。贝叶斯公式的一个用途在于通过已知的三个概率函数推出第四个。
贝叶斯公式为：

2.10信息论

信息论是应用数学的一个分支，主要研究的是对信号所含信息的多少进行量化。它的基本想法是一个不太可能的事件居然发生了，要比一个非常可能的事件发生能提供更多的信息。本节主要介绍度量信息的几种常用指标，如信息量、信息熵、条件熵、互信息、交叉熵等。

2.10.1 信息量

1948年克劳德•香农（Claude Shannon）发表的论文“通信的数学理论”是世界上首次将通讯过程建立了数学模型的论文，这篇论文和1949年发表的另一篇论文一起奠定了现代信息论的基础。信息量是信息论中度量信息多少的一个物理量。它从量上反应具有确定概率的事件发生时所传递的信息。香农把信息看作是“一种消除不确定性”的量，而概率正好是表示随机事件发生的可能性大小的一个量，因此，可以用概率来定量地描述信息。
在实际运用中，信息量常用概率的负对数来表示，即，。为此，可能有不少人会问，为何用对数，前面还要带上负号？
用对数表示是为了计算方便。因为直接用概率表示，在求多条信息总共包含的信息量时，要用乘法，而对数可以变求积为求和。另外，随机事件的概率总是小于1，而真实小于1的对数为负的，概率的对数之前冠以负号，其值便成为正数。所以通过消去不确定性，获取的信息量总是正的。

2.10.2 信息熵

信息熵（entropy）又简称为熵，是对随机变量不确定性的度量。熵的概念由鲁道夫•克劳修斯（Rudolf Clausius）于1850年提出，并应用在热力学中。1948年，克劳德•艾尔伍德•香农（Claude Elwood Shannon）第一次将熵的概念引入信息论中，因此它又称为香农熵。
用熵来评价整个随机变量X平均的信息量，而平均最好的量度就是随机变量的期望，即熵的定义如下：

我们利用Python具体实现以下概率p与H(X)的关系：

从这个图形可以看出，当概率为0或1时，H(X)为0，说明此时随机变量没有不确定性，当p=0.5时，随机变量的不确定性最大，即信息量最大。H(X)此时取最大值。

2.10.3 条件熵

设二维随机变量（X,Y）,其联合概率分布为：

注意，这个条件熵，不是指随机变量X在给定某个数的情况下，另一个变量的熵是多少，变量的不确定性是多少？而是期望！因为条件熵中X也是一个变量，意思是在一个变量X的条件下（变量X的每个值都会取），另一个变量Y熵对X的期望。
条件熵比熵多了一些背景知识，按理说条件熵的不确定性小于熵的不确定，即H(Y|X)≤H(Y)，事实也是如此，下面这个定理有力地说明了这一点。
定理：对二维随机变量（X,Y）,条件熵H（Y|X）和信息熵H（Y）满足如下关系：
H(Y|X)≤H(Y)                                                                                                   (2.29)

2.10.4 互信息

互信息（mutual information）又称为信息增益，用来评价一个事件的出现对于另一个事件的出现所贡献的信息量。记为：
I(X,Y)=H(Y)-H(Y|X)                                                                               (2.30)
在决策树的特征选择中，信息增益为主要依据。在给定训练数据集D,假设数据集由n维特征构成，构建决策树时，一个核心问题就是选择哪个特征来划分数据集，使得划分后的纯度最大，一般而言，信息增益越大，意味着使用使用某属性a来划分所得“纯度提升”越大。因此，我们常用信息增益来进行决策树划分属性。
2.10.5 相对熵
相对熵（relative entropy），所谓相对，一般是在两个随机变量之间来说，又被称为KL散度(Kullback–Leibler divergence，KLD)，这里我们假设 p(x) 和 q(x) 是 X 取值的两个概率分布，如p(x)表示X的真实分布，q(x)表示X的训练分布或预测分布。则 p 对 q 的相对熵为：

相对熵有些重要性质：
（1）相对熵不是传统意义上的距离，它没有对称性，即
KL(p(x)||q(x))≠KL(q(x)||p(x))
（2）当预测分布q(x)与真实分布p(x)完全相等时，相对熵为0；
（3）如果两个分别差异越大，那么相对熵也越大；反之，如果两个分布差异越小，相对熵也越小。
（4）相对熵满足非负性，即 KL(p(x)||q(x))≥0

2.10.5 交叉熵

交叉熵可在神经网络(机器学习)中作为损失函数，p表示真实标记的分布，q则为训练后的模型的预测标记分布，交叉熵损失函数可以衡量p与q的相似性。交叉熵作为损失函数还有一个好处是使用sigmoid函数在梯度下降时能避免均方误差损失函数学习速率降低的问题，因为学习速率可以被输出的误差所控制。

第1章 线性代数

线性代数是数学的一个重要分支，广泛应用于科学和工程领域。线性代数，特别是矩阵运算是很多机器学习算法，尤其是深度学习的基础。因此，我们先介绍一些必备的线性代数的知识。
在深度学习的图像处理中，1张图由28*28像素点构成，而这28*28就是一个矩阵；深度学习中神经网络中，权重一般都是矩阵，我们经常把权重矩阵W与输入X相乘，输入X一般是向量，这就涉及矩阵与向量相乘的问题。诸如此类，矩阵及矩阵运算在深度学习中非常普遍，当然也非常重要。

1.1标量、向量、矩阵和张量

在线性代数和机器学习中，通常会遇到以下4种类型的数据。
标量（scalar）：
一个标量就是一个单独的数，一般用小写的的变量名称表示，如a，x等
向量（vector）：

我们可以把向量看作空间中的点，每个元素是不同的坐标轴上的坐标。
向量可以这样表示，那我们如何用编程语言如python来实现呢？如何表示一个向量？如何获取向量中每个元素呢？请看如下示例：

打印结果如下：
5
1 2 4 8

说明这个向量，元素个数为5，向量中索引一般从0开始，如a[0]表示第一个元素1，a[1]
表示第一个元素2， a[2]表示第3个元素4，依次类推。这个从左到右的排列顺序，如果从右到左，我们可用负数来表示，如a[-1]表示第1个元素（注：从右到左），a[-2]表示第2个元素，依次类推。
矩阵（matrix）

我们如何用Python来表示或创建矩阵呢？如果我们希望获取其中某个元素，该如何实现呢？请看如下示例：

打印结果：
[[1 2 3]
[4 5 6]]
6
(2, 3)
1 2 5
[4 5 6]

矩阵我们可以用嵌套向量生成，和向量一样，在numpy中，矩阵的元素的下标索引也是从从开始的。

张量（tensor）
几何代数中定义的张量是基于向量和矩阵的推广，通俗一点理解的话，我们可以将标量视为零阶张量，向量视为一阶张量，那么矩阵就是二阶张量，当然，三阶的就称为三阶张量，以此类推。在机器学习、深度学习中经常遇到多维矩阵，如一张彩色图片就是一个三阶张量，三个维度分别是图片的高度、宽度和色彩数据。
张量（tensor）也是深度学习框架Tensorflow的重要概念。Tensorflow实际上有tensor（张量）+flow（流）构成。
同样我们可以用python来生成张量及获取其中某个元素或部分元素，请看示例：

打印结果如下：
[[[ 0 1 2 3]
[ 4 5 6 7]]

[[ 8 9 10 11]
[12 13 14 15]]]
16
(2, 2, 4)
0 1 5
[4 5 6 7]

转置(transpose)

numpy如何实现转置？很简单，利用张量的T属性即可，示例如下：

打印结果如下：
[[1 2 3]
[4 5 6]]
[[1 4]
[2 5]
[3 6]]

1.2矩阵和向量

矩阵加法和乘法是矩阵运算中最常用的操作之一，两个矩阵相加，需要它们的形状相同，则是对应元素的相加，如：C=A+B,其中。矩阵也可以和向量相加，只要它们的列数相同，相加的结果是矩阵每行与向量相加，这种隐式地复制向量b到很多位置的方式称为广播(broadcasting)，以下我们通过一个代码示例来说明。

打印结果为：
[[11 22 33]
[14 25 36]]

两个矩阵相加，要求它们的形状相同，如果两个矩阵相乘，如A和B相乘，结果为矩阵C,矩阵A和B需要什么条件呢？条件比较简单，只要矩阵A的列数和矩阵B的行数相同即可。如果矩阵A的形状为mxn，矩阵B的形状为nxp，那么矩阵C的形状就是mxp，例如
C=AB，则它们的具体乘法操作定义为：

1.3特殊矩阵与向量

有些特殊类型的矩阵在机器学习或深度学习中经常遇到，如对角矩阵、对称矩阵、单位矩阵、正交矩阵、可逆矩阵等等。向量由正交向量。下面我们逐一进行简要说明。
（1）可逆矩阵

后续我们有更详细的讨论及代码实现。
（2）对角矩阵

从上面两个式子可以看到对角矩阵的简洁高效。
（3）对称矩阵
对称矩阵，对于任意一个n阶方阵A,若A满足： 成立， 则称方阵A为对称矩阵。

1.4线性相关性及向量空间

前面我们介绍了向量、矩阵等概念，接下来我们将介绍向量组、线性组合、线性相关性、秩等重要概念。
由多个同维度的列向量构成的集合称为向量组，矩阵可以可以看成是有行向量或列向量构成的向量组。
1）线性组合

3）向量组的秩

秩是一个重要概念，运行非常广泛，实际上矩阵我们可以看成是一个向量组。如果把矩阵看成是由所有行向量构成的向量组，这样矩阵的行秩就等于行向量组的秩；如果把矩阵看成是由所有列向量构成的向量组，这样矩阵的列秩就等于列向量组的秩。
矩阵的行秩与列秩相等，因此，把矩阵的行秩和列秩统称为矩阵的秩。

1.5范数

数有大小，向量也有大小，向量的大小我们通过范数（Norm）来衡量。范数在机器学习、深度学习中运行非常广泛，特别在限制模型复杂度、提升模型的泛化能力方面效果不错。
p范数的定义如下：


以上说了向量一种度量方式，即通过范数来度量向量或矩阵的大小，并有具体公式，在实际编程中如何计算向量的范数呢？这里我们还是以Python为例进行说明。

打印结果如下：
[ 0. 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9]
4.5
1.68819430161
0.9

看来利用python求向量的范数还是很方便的。

3.6特征值分解

许多数学对象可以分解成多个组成部分。特征分解就是使用最广的矩阵分解之一，即将矩阵分解成一组特征向量和特征值。本节讨论的矩阵都是方阵。
我们先介绍特征值、特征向量的概念。
设A是一个n阶方阵，如果存在实数⋋和n维的非零向量x，满足：
Ax=⋋x                                                     (3.13)
那么把数⋋称为方阵A的特征值，向量x称为矩阵A对应特征值⋋的特征向量。

注意，并不是所有方阵都能进行特征值分解，一个n阶方阵A能进行特征值分解的充分必要条件是它含有n个线性无关的特征向量。
这里我们介绍了给定一个方阵，如何求该方阵的特征向量和特征值的理论方法，这些方法如何用编程语言来实现呢？实现起来是否麻烦？有了Python的帮忙，实现起来非常简单，具体请看如下示例：

打印结果：
[-0.37228132 5.37228132]
[-0.37228132 5.37228132]
[[-0.82456484 -0.41597356]
[ 0.56576746 -0.90937671]]
【说明】
在numpy.linalg模块中：
eigvals() 计算矩阵的特征值
eig() 返回包含特征值和对应特征向量的元组

1.7奇异值分解

上节我们介绍了方阵的一种分解方式，如果矩阵不是方阵，是否能分解？如果能，该如何分解？这节我们介绍一种一般矩阵的分解方法，称为奇异值分解，这种方法应用非常广泛，如降维、推荐系统、数据压缩等等。
矩阵非常重要，所以其分解方法也非常重要，方法也比较多，除了特征分解法，还有一种分解矩阵的方法，被称为奇异值分解（SVD）。将矩阵分解为奇异向量和奇异值。通过奇异分解，我们会得到一些类似于特征分解的信息。然而，奇异分解有更广泛的应用。
每个实数矩阵都有一个奇异值分解，但不一定都有特征分解。例如，非方阵的矩阵没有特征分解，这时我们只能使用奇异值分解。
奇异分解与特征分解类似，只不过这回我们将矩阵A分解成三个矩阵的乘积：
                                                          (1.15)
假设A是一个mxn矩阵，那么U是一个mxm矩阵，D是一个mxn矩阵，V是一个nxn矩阵。这些矩阵每一个都拥有特殊的结构，其中U和V都是正交矩阵，D是对角矩阵（注意，D不一定是方阵）。对角矩阵D对角线上的元素被称为矩阵A的奇异值。矩阵U的列向量被称为左奇异向量，矩阵V 的列向量被称右奇异向量。
SVD最有用的一个性质可能是拓展矩阵求逆到非方矩阵上。
奇异值分解，看起来太复杂，但用python来实现，却非常简单，这得感谢哪些一直致力于Python广大贡献者们。具体请看如下示例：

打印结果：
[ 1.09824632e+01 8.79229347e+00 1.03974857e+00 1.18321522e-15
2.13044868e-32]
[[ 10.98246322 0. 0. ]
[ 0. 8.79229347 0. ]
[ 0. 0. 1.03974857]]

1.8迹运算

迹运算返回的是矩阵对角元素的和:

利用python的numpy对矩阵求迹同样方便。请看以下示例。

打印结果：
15
15
171
171

1.9实例：主成分分析

主成分分析（Principal Component Analysis，PCA）， 是一种统计方法。通过正交变换将一组可能存在相关性的变量转换为一组线性不相关的变量，转换后的这组变量叫主成分。
在许多机器学习、深度学习的应用中，往往需要处理大量样本或大的矩阵，多变量大样本无疑会为研究和应用提供了丰富的信息，但也在一定程度上增加了数据采集的工作量，更重要的是在多数情况下，许多变量之间可能存在相关性，从而增加了问题分析的复杂性，同时对分析带来不便。如果分别对每个指标进行分析，分析往往是孤立的，而不是综合的。盲目减少指标会损失很多信息，容易产生错误的结论。
因此需要找到一个合理有效的方法，在减少需要分析的指标或维度的同时，尽量减少原指标包含信息的损失，以达到对所收集数据进行全面分析的目的。由于各变量间存在一定的相关关系，因此有可能用较少的综合指标分别综合存在于各变量中的各类信息。主成分分析就属于这类降维的方法。
如何实现以上目标呢？这里我们简要说明一下原理，然后使用Python来实现，至于详细的推导过程，大家可参考相关书籍或网上资料。


以下我们Python具体实现一个PCA实例。
以iris为数据集，该数据集可以通过load_iris自动下载。
1）iris数据集简介：
Iris数据集是常用的分类实验数据集，由Fisher, 1936收集整理。Iris也称鸢尾花卉数据集，是一类多重变量分析的数据集。数据集包含150个数据集，分为3类，每类50个数据，每个数据包含4个属性。可通过花萼长度，花萼宽度，花瓣长度，花瓣宽度4个属性预测鸢尾花卉属于（Setosa，Versicolour，Virginica）三个种类中的哪一类。
2）算法主要步骤如下：
（1）对向量X进行去中心化
（2）计算向量X的协方差矩阵，自由度可以选择0或者1
（3）计算协方差矩阵的特征值和特征向量
（4）选取最大的k个特征值及其特征向量
（5）用X与特征向量相乘
3）代码实现

4）我们看一下各特征值的贡献率

从这个图形显示，前2个特征值的方差贡献率超过96%，所以k取2是合理的。

1.10小结

本章主要介绍了线性代数中矩阵及向量有关概念及相关规则和运算，线性代数是理解深度学习所必须掌握的基础数学学科之一。另一门在机器学习中无处不在的重要数学学科是概率论，我们将在下一章介绍。

第22章 强化学习基础

22.1强化学习简介

强化学习是机器学习中的一种算法, 如下图，它是让计算机实现从一开始什么都不懂, 不像监督学习或无监督学习有大量的经验或输入数据, 它基本算自学成才。通过不断地尝试, 从错误或惩罚中学习, 最后找到规律, 学会了达到目的的方法. 这就是一个完整的强化学习过程。

强化学习已经在如游戏，机器人等领域中开花结果。各大科技公司，如中国的百度、阿里美国的谷歌、facebook、微软等更是将强化学习技术作为其重点发展的技术之一。可以说强化学习算法正在改变和影响着这个世界，掌握了这门技术就掌握了改变世界和影响世界的工具。
强化学习应用非常广泛，目前主要领域有：
游戏理论与多主体交互
机器人
电脑网络
车载导航
医学
工业物流
强化学习的原理大致如下图：

其中：
主体（agent）
是动作的行使者，例如配送货物的无人机，或者电子游戏中奔跑跳跃的超级马里奥。
状态（state）
是主体的处境，亦即一个特定的时间和地点、一项明确主体与工具、障碍、敌人或奖 品等其他重要事物的关系的配置。
动作（action）
其含义不难领会，但应当注意的是，主体需要在一系列潜在动作中进行选择。在电子 游戏中，这一系列动作可包括向左或向右跑、不同高度的跳跃、蹲下和站着不动。在 股票市场中，这一系列动作可包括购买、出售或持有一组证券及其衍生品中的任意一 种。无人飞行器的动作选项则包括三维空间中的许多不同的速度和加速度等。
奖励（reward）
是用于衡量主体的动作成功与否的反馈。例如，在电子游戏中，如果马里奥接触一枚 金币，他就能赢得分数。主体向环境发出以动作为形式的输出，而环境则返回主体的 新状态及奖励。
环境(environment)
其主体被“嵌入”并能够感知和行动的外部系统。

输入是：
State
为 Observation，例如迷宫的每一格是一个State
Actions
在每个状态下，有什么行动
Reward
进入每个状态时，能带来正面或负面的回报
输出就是：
Policy
在每个状态下，会选择哪个行动
具体来说就是：
State = 迷宫中Agent的位置，可以用一对座标表示，例如(1,3)
Action = 在迷宫中每一格，你可以行走的方向，例如：｛上，下，左，右｝
Reward = 当前的状态 (current state) 之下，迷宫中的一格可能有食物 (+1) ,也可能有怪兽 (-100)
Policy = 一个由状态 → 行动的函数，即： 函数对给定的每一个状态，都会给出一个行动。
增强学习的任务就是找到一个最优的策略Policy从而使Reward最多。
我们一开始并不知道最优的策略是什么，因此往往从随机的策略开始，使用随机的策略进行试验，就可以得到一系列的状态,动作和反馈：

这就是一系列的样本Sample。增强学习的算法就是需要根据这些样本来改进Policy，从而使得得到的样本中的Reward更好。

22.2强化学习常用算法

强化学习有多种算法,目前比较常用的算法, 有通过行为的价值来选取特定行为的方法, 如 Q-learning, Sarsa, 使用神经网络学习的 DQN(Deep Q Network), 以及DQN的后续算法，还有直接输出行为的 policy gradients等。限于篇幅，这里我们主要介绍几种具有代表性算法。

22.2.1 Q-Learning算法

利用 Q-Learning 训练计算机玩 Atari 游戏的时候，Q-Learning 曾引起了轰动。现在，Q-Learning 依然是一个有重大意义的概念。大多数现代的强化学习算法，都是 Q-Learning 的一些改进。
（1）其主流程大致如下：

（2）Q-learning的伪代码为：
初始化价值表Q(s,a)
观察当前状态 s
根据策略(比如贪心算法)选择一个动作a
执行这个动作，观察奖励r和新状态s
使用观察到的奖励和下一个状态可能的最大奖励来更新状态的价值。更新是基于下述公式和参数。
将状态设置为新状态，并重复该过程，直到达到终端状态。
（3）在Q-Learning中，函数Q(s,a)是代表机器人在状态s时采取动作a所得到的未来价值回报，可能有读者就有疑问了，当前我采取了动作a，我怎么知道我当前这个做法在未来的价值回报是多少？确实不能，如果我们仅仅知道当下的状态、动作，而不知道紧接下来的动作及其回报。
怎么求Q(s,a)是一个摆在我们面前的大问题，虽然我们无法确切的知道Q(s,a)是多少，但是我们可以在心里面假想这个Q(s,a)一定是存在的，一旦Q(s,a)存在，于是我们在每一个状态s时，只需采取满足Q(s,a)最大的那个动作a了。
如何计算Q(s,a)？我们可以回顾一下Bellman方程，即前后两个相邻的Q(s,a)必须满足的关系，简单说就是当前采取的行动的最大价值回报等于瞬时回报加上下一个状态的最大回报。顺此思路，Q-Learning的做法就是使用此Bellman方程不断逼近Q(s,a)。
Q-Learning最简单最直接的做法就是构建一个状态-动作表，该表中存储着每个状态采取每个动作时候的Q值。该做法的流程可以总结如下：
假设状态数目为A，动作数目为B
• 随机初始化数组Q[A, B]
• 定义或获取初始状态s
• 重复以下步骤直到数组Q收敛
(1) 选取一个动作a并且执行
(2) 接受回报R，同时转移到下一个状态s’
(3) 更新Q[s , a]的值
(4) 状态变为s’，并返回到步骤(1)
可以看到，使用Q[s,a]来进行Q-Learning的算法流程非常简单，不过上述算法中有以下几个值得思考的关键点：
第一，如何选取动作a？
如果仅仅是采取贪婪的算法，在每个状态s处挑选让此状态达到最大值的动作a，这种做法眼光太狭隘，只注重眼前利益，不顾长远回报，其使得expoitation达到了最大，exploration却最小，最终陷入局部最优。因此比较好的办法是在选取动作a的时候，既要注重expoitation，又要考虑exploration，可以采取e-greedy算法，设定一定的概率让机器人随机采取动作，其余时候贪婪做出决策。
第二，如何更新Q[s,a]的值？
前面说了，由Bellman方程可知，Q[s,a]=R+max(Q[s',:])，从梯度下降的角度看，这个新的Q[s,a]是在s状态下求出的最大未来回报，也是我们渴望逼近的值，但是我们在更新旧的Q[s,a]的时候，不能将此新的Q[s,a]直接替代旧的Q[s,a]，因为这个新的Q[s,a]只是我们的一种估计，甚至是一种带噪声的估计。因此，不能直接使用新的Q[s,a]去取代旧的Q[s,a]，而应该是让旧的Q[s,a]朝着新的Q[s,a]走一小步，用公式描述就是：
Q[s,a]=Q[s,a]+lr*(R+gamma*max(Q[s',:])-Q[s,a])
其中lr是学习率，gamma是折扣因子，之所以使用折扣因子是因为，环境可能是随机的，我们无法完全确保在下一次采取同样的动作还是会得到同样的回报值。折扣因子一般介于0和1之间。
第三，除了使用e-greedy算法选取动作，是否还可以使用其他技巧？
答案是可以的，比如，在每一个状态s时，当我们计算Q[s,:]的最大值时可以先随机添加一点高斯噪声到Q[s,:]上再求最大值，这样也可以起到了exploration的作用，这种方法的好处就是我们在鼓励exploration的同时也照顾了Q值，而不是纯粹的随机选取。我想，在训练的不同阶段，我们可以组合这两种技巧，比如在训练开始的时候，采取e-greedy算法，而一定周期以后，就采取添加噪声的算法。
Q-Learning算法是一种离策略算法(off-policy)，即其Q函数更新不同于选取动作时遵循的策略，换句话说，Q函数更新时计算了下一个状态的最大价值，但是取那个最大值的时候的行动与当前策略是无关的。后面我们将介绍一种on-policy策略算法，即sarsa算法。
正如我之前所说，Q-Learning是一种off-policy的强化学习算法，即其Q表的更新不同于选取动作时所遵循的策略，换句化说，Q表在更新的时候计算了下一个状态的最大价值，但是取那个最大值的时候所对应的行动不依赖于当前策略。
用公式来表示Q-Learning中Q表的更新：
Q(St,At) = Q(St,At) + lr [R(t+1) + discount * max Q(St+1,a) – Q(St,At)]
根据以上公式，我们就可以写Q-Learning算法描述如下：

其代码如何实现？后面我们将结合具体实例来说明其详细代码实现。

22.2.2 Sarsa算法

Sarsa算法与Q-learning算法非常相似，所不同的就是更新Q值时，Sarca的现实值取R+γQ(S',A')，而不是R+γmax_a'Q(S',a')，而Q learning是使用R+γmax_a'Q(S',a')。
其算法逻辑为：

22.2.3 DQN算法

DQN(Deep Q Network) 由 DeepMind 在 2013 年在 NIPS 提出。它融合了神经网络和 Q learning 的方法。DQN 算法的主要做法是 Experience Replay，其将系统探索环境得到的数据储存起来，然后随机采样样本更新深度神经网络的参数。

Experience Replay 的动机是：
1）深度神经网络作为有监督学习模型，要求数据满足独立同分布。
2）但 Q Learning 算法得到的样本前后是有关系的。为了打破数据之间的关联性，Experience Replay 方法通过存储-采样的方法将这个关联性打破了。
DeepMind 在 2015 年初在 Nature 上发布了文章，引入了 Target Q 的概念，进一步打破数据关联性。Target Q 的概念是用旧的深度神经网络 w− 去得到目标值，下面是带有 Target Q 的 Q Learning 的优化目标。
J=min(r+γmaxa′Q(s′,a′,w−))−Q(s,a,w))2
Q-learning最早是根据一张Q-table，即各个状态动作的价值表来完成的，通过动作完成后的奖励不断迭代更新这张表，来完成学习过程。然而当状态过多或者离散时，这种方法自然会造成维度灾难，所以我们才要用一个神经网络来表达出这张表，也就是Q-Network。
如下图，把Q-table换为神经网络，利用神经网络参数替代Q-table。

通过前面两个卷积层，我们完全不需要费心去理解环境中的状态和动作奖励，只需要将状态参数一股脑输入就好。当然，我们的数据特征比较简单，无需进行池化处理，所以后面两层直接使用全连接即可。
主体算法如下：

22.3强化学习实例

22.3.1强化学习寻宝实例

这节我们用 tabular Q-learning 的方法实现一个小例子, 例子的环境是一个一维世界或一条线段上, 在世界的右边有宝藏, 探索者只要得到宝藏就将获得奖励, 然后以后就记住了得到宝藏的方法。其环境图像如下：

Q-learning 是一种记录行为值 (Q value) 的方法, 每种在一定状态的行为都会有一个值 Q(s, a), 就是说 行为 a 在 s 状态的值是 Q(s, a). s 在上面的探索者游戏中, 就是 o 所在的地点了. 而每一个地点探索者都能做出两个行为 left/right, 这就是探索者的所有可行的 a。
如果在某个地点 s1, 探索者计算了他能有的两个行为, a1/a2=left/right, 计算结果是 Q(s1, a1) > Q(s1, a2), 那么探索者就会选择 left 这个行为. 这就是 Q learning 的行为选择简单规则。

22.3.1.1算法的详细过程

 

22.3.1.2代码实现

这里我使用python3.6
1）导入必要的库

2）创建Q表
对于 tabular Q learning, 我们必须将所有的 Q values (行为值) 放在 q_table 中, 更新 q_table 也是在更新他的行为准则. q_table 的 index 是所有对应的 state (探索者位置), columns 是对应的 action (探索者行为).

格式如下：
# q_table:
"""
left right
0 0.0 0.0
1 0.0 0.0
2 0.0 0.0
3 0.0 0.0
4 0.0 0.0
5 0.0 0.0
"""

3）定义动作
接着定义探索者是如何挑选行为的. 这是我们引入 epsilon greedy 的概念. 因为在初始阶段, 随机的探索环境, 往往比固定的行为模式要好, 所以这也是累积经验的阶段, 我们希望探索者不会那么贪婪(greedy). 所以 EPSILON 就是用来控制贪婪程度的值. EPSILON 可以随着探索时间不断提升(越来越贪婪), 不过在这个例子中, 我们就固定成 EPSILON = 0.9, 90% 的时间是选择最优策略, 10% 的时间来探索.

4）获取环境反馈信息
做出行为后, 环境也要给我们的行为一个反馈, 反馈出下个 state (S_) 和 在上个 state (S) 做出 action (A) 所得到的 reward (R). 这里定义的规则就是, 只有当 o 移动到了 T, 探索者才会得到唯一的一个奖励, 奖励值 R=1, 其他情况都没有奖励。

5）更新环境

6）强化学习主循环

7）运行主程序

运行结果：
Episode 1: total_steps = 46
Episode 2: total_steps = 66
Episode 3: total_steps = 52
Episode 4: total_steps = 21
Episode 5: total_steps = 31
Episode 6: total_steps = 12
Episode 7: total_steps = 10
Episode 8: total_steps = 7
Episode 9: total_steps = 7
Episode 10: total_steps = 7
Episode 11: total_steps = 7
Episode 12: total_steps = 7
Episode 13: total_steps = 7
Episode 14: total_steps = 7
Episode 15: total_steps = 7

Q-table:

left right
0 1.324169e-07 0.000238
1 1.479568e-07 0.001645
2 6.925792e-07 0.009356
3 5.968673e-06 0.042724
4 6.631859e-05 0.152157
5 1.385100e-04 0.407920
6 8.100000e-04 0.794109
7 0.000000e+00 0.000000

从以上结果可以看出，为找到宝藏，前几次查询步骤比较多，但后来，她就越来越聪明了，后来从开始位置，只要7步了，可以说直奔宝藏了。

22.3.2强化学习立杆实例

这里我们用一个走迷宫例子来实现 RL方法，即Sarsa(state-action-reward-state_-action_). 我们从这一个简称可以了解到, Sarsa 的整个循环都将是在一个路径上, 也就是 on-policy, 下一个 state_, 和下一个 action_ 将会变成他真正采取的 action 和 state. 和 Qlearning 的不同之处就在这. Qlearning 的下个一个 state_ action_ 在算法更新的时候都还是不确定的 (off-policy). 而 Sarsa 的 state_, action_ 在这次算法更新的时候已经确定好了 (on-policy)。

整个算法还是一直不断更新 Q table 里的值, 然后再根据新的值来判断要在某个 state 采取怎样的 action. 不过与 Qlearning 不同之处:

1）Sarsa在当前 state 已经想好了 state 对应的 action, 而且想好了 下一个 state_ 和下一个 action_ ，但Qlearning 还没有想好下一个 action_。
2）Sarsa更新 Q(s,a) 的时候基于的是下一个 Q(s_, a_) ,而Qlearning 是基于 maxQ(s_)。

22.3.2.1算法的代码实现

【说明】
环境设计程序maze_env.py, 算法实现程序RL_brain.py，大家可以访问获取：
https://github.com/MorvanZhou/Reinforcement-learning-with-tensorflow/tree/master/contents/3_Sarsa_maze

22.3.3强化学习CartPole实例

在本次实战中，我们不选择Atari游戏，而使用OpenAI Gym中的传统增强学习任务之一CartPole作为练手的任务。游戏示意图如下：

游戏的基本要求就是控制下面的cart移动，使连接在上面的杆保持垂直不倒。这个任务简化到只有两个离散动作，要么向左用力，要么向右用力。而state状态就是这个杆的位置和速度。有关这个游戏环境的详细信息可参考：https://github.com/openai/gym/wiki/CartPole-v0
下面我们就要用DQN来解决这个问题。

22.3.3.1实现这个游戏需要的基础

1）熟悉Python编程，能够使用Python基本的语法
2）对Tensorflow有一定的了解，知道基本的使用
3）知道如何使用OpenAI Gym
4）了解基本的神经网络MLP
5）理解DQN算法

22.3.3.2实现算法

我们将要实现的是最基本的DQN，也就是NIPS 13版本的DQN：

面对CartPole问题，我们进一步简化：
1）无需预处理Preprocessing。也就是直接获取观察Observation作为状态state输入。
2）只使用最基本的MLP神经网络，而不使用卷积神经网络，更不用池化层等。

22.3.3.3导入需要的库

22.3.3.4编写主循环

这里我们按照至上而下的编程方式，先写主函数用来说明整个程序架构，然后再具体编写DQN算法实现。

22.3.3.5相关函数

接下来我们编写一个DQN的函数，DQN的一切都将封装在里面。在主函数中，我们只需调用

egreedy_action输入状态，输出动作，perceive 保存信息。
然后环境自己执行动作，输出新的状态：

然后整个过程就反复循环，一个episode结束，就执行一个。

22.3.3.6 DQN实现

1）编写基本DQN类的结构

DQN一个很重要的功能就是要能存储数据，然后在训练的时候minibatch出来。所以，我们需要构造一个存储机制。这里使用deque来实现。

2）初始化

这里要注意一点就是egreedy的epsilon是不断变小的，也就是随机性不断变小。怎么理解呢？就是一开始需要更多的探索，所以动作偏随机，慢慢的我们需要动作能够有效，因此减少随机。
3）创建Q网络
我们这里创建最基本的MLP，输入层为state_dim(其值为4）个节点、隐含层节点数设置为20，输出层节点数为action_dim(其值为2)

这里我们只用了一个隐层，然后使用relu非线性单元。另外，需注意state 输入的格式，因为使用minibatch，所以格式是[None,state_dim]
4）写perceive函数

这里action值与动作的对应关系为：0表示把cart往左推；1表示把cart往右推、为便于计算起见，对表示动作数据格式做了转换。使用了在神经网络中one hot key的形式，而在OpenAI Gym中则使用单值。什么意思呢？比如我们输出动作是1，那么对应的one hot形式就是[0,1]，如果输出动作是0，那么one hot 形式就是[1,0]。这样做的目的是为了之后更好的进行计算。
在perceive中一个最主要的事情就是存储。然后根据情况进行train。这里我们要求只要存储的数据大于Batch的大小就开始训练。
5）编写action输出函数

输出有两种可能，一个是根据情况输出随机动作，一个是根据神经网络输出。由于神经网络输出的是每一个动作的Q值，因此我们选择最大的那个Q值对应的动作输出。
6）编写training method函数

这里的y_input就是target Q值。我们这里采用Adam优化器，其实随便选择一个必然SGD，RMSProp都是可以的。可能比较不好理解的就是Q值的计算。这里大家记住动作输入是one hot key的形式，因此将Q_value和action_input向量相乘得到的就是这个动作对应的Q_value。然后用reduce_sum将数据维度压成一维。
7）编写training函数

先进行minibatch工作，然后根据batch计算y_batch。最后用optimizer进行优化。
8）测试模型代码

测试中唯一的不同就是我们使用

来获取动作，也就是完全没有随机性，只根据神经网络来输出，没有探索，同时这里也就不再perceive输入信息来训练。

22.3.3.7 完整代码

修改了部分代码，主要是为适应新版本的要求。以下代码我的运行环境为：python3.6,tensorflow1.3,在ipython中运行。

运行结果：

episode: 0 Evaluation Average Reward: 74.7
episode: 100 Evaluation Average Reward: 95.8
episode: 200 Evaluation Average Reward: 67.0
episode: 300 Evaluation Average Reward: 14.1
episode: 400 Evaluation Average Reward: 9.8
episode: 500 Evaluation Average Reward: 9.7
episode: 600 Evaluation Average Reward: 11.3
episode: 700 Evaluation Average Reward: 11.6
episode: 800 Evaluation Average Reward: 11.3
episode: 900 Evaluation Average Reward: 12.2

参考了：
https://zhuanlan.zhihu.com/p/21477488