品读《吴恩达机器学习》第三部分

在《吴恩达机器学习》第三部分：无监督学习，推荐系统，强化学习（Unsupervised Learning, Recommenders, Reinforcement Learning），我们将会学习：

• 无监督学习
  • 聚类算法
  • 异常检测
• 推荐系统
• 强化学习

无监督学习

无监督学习是在没有标签的数据中自动寻找某些规律。
聚类任务是典型的无监督学习任务，通过某些特征将相似的人或事物自动归为一类。
无监督学习任务还有异常检测（找出一些不寻常的数据）和维度降低（使用更少的数字对数据进行压缩）。

聚类算法

聚类算法着眼于数据点的数量，并自动找出彼此相关或相似的数据点。

对于监督学习，训练集包含输入特征 x 和标签 y 。

对于无监督学习，训练集只包含输入特征 x ，但没有标签或目标标签 y 。因为我们不能告诉算法我们想要预测的“正确答案 y ”是什么，相反，要让算法去找寻数据的共同点。

也就是说，聚类算法会像上图这样查看训练集，并试着将其分成簇（clustering），即一组彼此相似的点。
在课程的第一部分，我们曾介绍过聚类算法的一些应用，比如：熊猫新闻的分组、怀着不同目的来网站学习的人群和根据DNA数据归类相似人群。

K 均值聚类算法（K-means）的直观理解

如上图所示，K-means算法首先会随机猜测给出的两个簇的中心位置（即簇质心），之后算法会重复执行两个步骤：

1. 将点分配给簇质心（clusters centriod）
2. 移动簇质心

第一步是为簇质心分配点。
算法会遍历图中每一个点，然后分析它是更接近红色簇质心还是蓝色簇质心，并将此点分配给离它更近的簇质心。

将所有点遍历后，分配情况如下图所示：

第二步是，算法会遍历所有的红点，然后对它们取平均值，并将红色簇质心移动到红点的平均值位置。同样的，蓝色的点和簇质心也一样。

然后我们重复上述的两步。
对于第一步，由于簇质心位置改变，自然与点的距离也改变了，这样会导致一些红点变为蓝点、一些蓝点变为红点。
对于第二步，由于有些点的颜色改变了，红点和蓝点的平均值自然也改变了，各自的簇质心的位置也发生了变化。

经过多次重复这两步，最终红蓝簇质心的位置会落定，这意味着此刻 K-means 聚类算法已经收敛了。

K 均值聚类算法的详细代码

K-means算法中，K 代表簇质心的个数，μ_K 代表各个簇质心向量（位置含x、y轴坐标，二维向量），一开始簇质心是随机初始化的。
第一步中，m 是点的个数，x⁽ⁱ⁾ 是训练样本（各个点向量），c⁽ⁱ⁾ 是距离训练样本 x⁽ⁱ⁾ 最近簇质心的索引（从1到K，示例中只能为1或2）。
第二步中，根据索引 c⁽ⁱ⁾ 不同，来计算簇质心向量 μ_K 。
多次重复，直至簇质心全部落定，不再发生变化。

但算法可能出现的一种情况是，有一个簇没有被分配到任何的训练样本（即点），这该怎么办呢？

最常见的做法是消减簇，得到 K=K-1 ，簇数量减一。
如果我们真的很需要簇，另一种做法是重新随机初始化簇质心。

另外，即使数据分离不是很明显，K-means算法仍然能起作用并给出有参考价值的结果。

优化目标

很多监督学习算法会输入训练集，构成代价函数，然后使用梯度下降或其他算法来优化代价函数，而K-means算法其实也在优化一个特定的代价函数。

一个新的符号：当 K = c⁽ⁱ⁾ 时，μ_c⁽ⁱ⁾ 时样本 x⁽ⁱ⁾ 分配到的簇的簇质心。
代价函数 J 的公式如上图所示，双竖线表示 x⁽ⁱ⁾ 和 μ_c⁽ⁱ⁾ 之间距离的平方。
通俗地说，K-means 的代价函数 J 时每个训练样本 x⁽ⁱ⁾ 之间的平均平方距离，以及训练样本 x⁽ⁱ⁾ 被分配到的簇质心的位置。这个代价函数 J 也被叫做畸变函数（distortion function）。

如上图所示，代价函数 J 的值就是所有红点和蓝点差值的平方的平均值。

如上图，对于 K-means 算法，我们在重复算法的两步时：
对于第一步，将点分配给簇质心，这意味着通过更新 c⁽ⁱ⁾ 以最小化代价函数 J ，同时保持 μ_K 不变。
对于第二步，移动簇质心到分配点的平均值，这意味着通过更新 μ_K 以最小化代价函数 J ，同时保持 c⁽ⁱ⁾ 。
实际上，重复上述两步是为了最小化平方距离的值，根据代价函数 J 的表达式，显然也最小化了 J 。

在每一次迭代中，distortation 代价函数应该下降或保持不变，如果其上升了，说明代码存在错误。

初始化 K-means 聚类算法

K-means 聚类算法的第一步是随机选取簇质心的位置，但是我们如何随机选取呢？

我们应该总是尝试去减少训练样本的簇质心 K 的数量，一般 K<m ，因为如果 K 超过 m ，就没有足够的训练样本使得每个簇质心至少有一个训练样本。
之前的例子中，簇质心一开始是完全随机选择的，但是更常见的方式是从所有的训练样本中随机选择。

假定我们要从给定的数据集中找到 3 个簇，三次不同的随机初始化簇质心并经过 K-means 算法，我们可以得到三个簇分类完全不同的结果。
对于这三种结果，三种 K-means 挑选出的簇，我们要选择代价函数 J 值最低的。并把其作为我们簇质心的随机选择。

直观理解是：总的来看，各个簇质心和其分配的点的距离平均值更小。

总算法的过程如上图，一般我们会随机初始化簇质心 50~1000 次。相比于只运行一次 K-means ，这样会为我们提供更好的簇的选择。

选择簇的数量

K-means 算法需要我们提供想要查找的簇数 K ，但我们如何确定 K 的值呢？

对于数据本身来说，并不能明确表现出它有多少簇。

一种尝试选择簇数量的方法叫肘部法则，它所做的是把代价函数 J 看作簇数量 K 的函数，观察其曲线选择手肘处点。
而很多代价函数只是平滑的减少，并没有一个清晰的肘部作为 K 的值。此外，一直最小化 J 去选取对应的 K 也不是好方法，因为这样总会使 K 值最大。

建议的方法是，我们根据 K-means 在稍后或下游任务中的表现来评估具体的 K 值合不合适。
例如，我们卖衣服，当K-means聚类算法得出K=3和K=5两种结果时，此时的决定权在于我们。也就是说要在尺码生产的成本和尺码售卖的热度中进行衡量，来决定我们最终应该选择几个簇。

异常检测

发现异常事件

异常检测算法（anomaly detection）是通过观察正常事件的未标记数据集，从而学会检测异常或在异常事件发生时发出危险信号。

我们以飞机引擎为例，引擎的制造中有很多特征，比如图中给出的热量产生 x₁ 和振动强度 x₂ 。当将一批引擎作为数据集（以X⁽ⁱ⁾表示）时， x₁ 和 x₂ 是作为每一个数据向量的一个特征。
当有一个新的引擎 X_test 时，我们可以检测它是否有异常。以 x₁ 和 x₂ 建立图像，将数据集样本对应到图中，此时可以观察 X_test 的位置，即 ok 处正常， anomaly 处异常。

最常见的进行异常检测方法是通过一种成为密度估计（density estimation）的技术，当我们得到有 m 个样本的训练集时，首先要为 X 的概率建立一个模型 P(X)，算法会尝试找出具有高概率的特征 x₁ 和 x₂ 的值，已经在数据集中不太可能有/遇见概率小的值。
当我们获取测试样本 X_test 后，我们会通过 P(X) 计算它的概率，同时会引出一个新的值 ε ， ε 是用于区分正常和异常的阈值。
我们只需计算 P(X_test) 与 ε 的大小，即可判断这个测试样本是否有异常。
现在，异常检测常用于检测金融欺诈。

高斯（正态）分布

高斯分布实际上就是我们中学学过的正态分布。

正态分布曲线下的面积始终为1。

正态分布的几个参数： μ 是数据集的平均值， σ² 是方差。
在单个数字的情况下，将数据集填入图像，越靠近中间的样本越正常，而散落在边缘的样本很可能有异常。

异常检测算法

我们拥有一个数量为 m 的训练集，其中每一个样本 X 都含有 n 个特征，即每个样本 X 都是拥有 n 个特征（x）的向量。
给定这个训练集，我们将进行密度估计，从而得出模型 P(X) 。而 P(X) 是样本向量中每个特征概率的乘积，其中每一项含有 x_i 、 μ_i 和 σ_i²。

异常检测算法构建：

1. 选择可能标示异常样本的特征 x_i
2. 计算从 X⁽¹⁾ 到 X^(m) 每个特征 x 的平均值 μ 和方差 σ²
3. 得到新样本 X ，计算 P(X) ，与 ε 比较，得出其是否异常

图中给出含有 2 个特征的训练样本图像，可以根据两个测试样本与 ε 比较来判断其是否异常。更直观的体现方式是，在以 x₁ 和 x₂ 为轴所作的图像中，正常的测试样本更靠近簇中心，而异常的测试样本散落在边缘。

开发和评估异常检测系统

实数评估：用于评估我们的学习算法。
对于训练集，我们把所有例子视作只是假设为正常的（y=0）；对于交叉验证集和测试集，除了正常的例子，也会包含一些异常的（y=1）。

上图就是一种应用了实数评估的检测方法，对训练集、交叉验证集和测试集进行例子分配。

如果没有足够数据来创建单独的测试集，可以将测试集的数据直接并入交叉验证集，只是围绕 ε 和特性选择的一些决策会过度适应交叉验证集，因此其性能可能没有预期那么好，但这仍是数据不足时的最佳选择。

实际评估算法：

1. 通过训练集拟合模型 P(X)
2. 在交叉验证集或测试集上计算 P(X)，并与 ε 进行比较，预测是否异常
3. 查看算法对交叉验证集或测试集的预测结果和标签 y 匹配的准确性
4. 利用准确性结果来更好的选择 ε 的值

异常检测vs监督学习

当我们有一些 y=1 的正样本（异常）和大量 y=0 的负样本（正常）时，如何判断使用异常检测还是使用监督学习？

• 当有非常少的正样本和大量的负样本，选择异常检测；当均有大量的正样本和负样本，选择监督学习。
• 当有许多类型不同的异常，或可能会有未知的异常，选择异常检测；当有足够多的正样本供算法了解，并且未来的正样本很可能与训练集中的样本相似时，选择监督学习。

异常检测和监督学习的一些常用例子：

• 异常检测：金融欺诈、制造业（发现从未发现的新缺陷）、检测数据中心的机器
• 监督学习：垃圾邮件分类、制造业（查找已知、出现过的缺陷）、天气预报、疾病分类

选择特征

在监督学习中，即使有些特征不完全正确或与问题无关，由于算法有足够的监督信号（即足够的标签 y ），所以其运行结果尚可。
但对于异常检测，仅从未标记数据中学习，很难找出要忽略的特征，所以选择异常检测算法的特征需要更谨慎。

一个帮助选择特征的方法：尽可能确保特征是高斯分布的，若并非高斯，可以对特征进行改变使其变得高斯分布。

另一种方法是：如果在交叉验证集上性能不佳，可以对异常检测算法进行误差分析。
通俗来说，就是查看算法在哪里出错，然后尝试改进。
通常做法是，先训练模型，然后查看算法在交叉验证集中没能检测出的异常，然后查看这些异常样本，考虑是否有必要新建一个特征，从而使算法能够发现这些异常。
对于图中例子，我们希望对于正常样本，P(X) 要大于等于 ε ， 对于异常样本，P(X) 要小于 ε 。但是最常见的问题是正异常样本的 P(x) 值都很大，这时我们应该查看异常样本并发现导致其异常的特征，加入这个特征，这样有助于将此样本与普通样本区分开来并能提升算法的性能。

推荐系统

协同过滤

做出推荐

我们建立一个推荐系统的框架，以用户推荐电影为例，数字代表评分，问号代表暂无评级。
n_u 代表用户数量， n_m代表电影数量， r(i, j)=1 代表用户 j 给电影 i 评过分， y^(i,j) 代表用户 j 给电影 i 的评分是 y 。

使用每个项目的特征

在上一节建立的推荐系统框架上，再增加两个特征 x₁ 和 x₂ ，代表这部电影有多大程度上是浪漫电影或动作电影。我们将其作为每一部电影的特征向量，例如 x⁽¹⁾ 所示。
我们可以将预测模型设为 \(w^{(j)}·x^{(i)}+b^{(j)}\) ，代表预测用户 j 给电影 i 的评分。其中，w 和 b 是用户的参数， x 是电影的特征向量。这个模型非常类似于线性回归。
图中示例，假设已知 w⁽¹⁾ 和 b⁽¹⁾ ，则用户 1 对电影 3 的预测评分为 w⁽¹⁾ · x⁽³⁾ + b⁽¹⁾ = 4.95。

用 m^(j) 代表用户 j 已评分的电影数量。
由于所用的算法非常类似于线性回归，其代价函数也与线性回归的非常相似。其中 y^(i,j)是用户对电影的真实评分，并且我们只对用户已评分的电影（即r(i, j)=1）求和，最后在结尾加上正则化项。
对于推荐系统， m^(j)只是一个常量，不会影响 w 和 b 的值，因此可以直接划去。

刚才给出的代价函数是对单个用户而言的，我们可以直接学习所有用户的参数。在上面的代价函数的基础上，对 n_u 个用户进行求和，就得出了学习所有用户参数的代价函数。

协同过滤算法

上一节我们给出了两个特征 x₁ 和 x₂ ，但当我们没有这些特征呢？

假设我们已经以某种方式学习了四个用户的参数，通过 \(w^{(j)}·x^{(i)}+b^{(j)}\) 和真实评分列出式子，从而可以反推电影 i 的特征向量 x⁽ⁱ⁾ 。重要的是，只有我们在拥有多个用户数据的情况下，才能预测电影的特征向量，因为若只有一个用户，则没有足够的信息来弄清楚特征 x₁ 和 x₂ 的含义。

已知所有用户的参数 w 和 b ，要学习特定电影的特征 x⁽ⁱ⁾ ，代价函数与上一节的十分相似，仅仅将所求项和正则化项的数改变即可。同样的，求所有电影的特征，只需对其求和。

将求用户参数 w 和 b 与求电影特征 x 的代价函数结合，即可得到最终的代价函数。

结合后的代价函数，特定电影的特征 x 也变成了参数，所以进行梯度下降时，还需要加上 x 这一项。

二值标签

推荐系统或协同过滤算法的许多应用都涉及二值标签，即不给出具体评分，而是给出是和否的答案。

• 1 代表展示项目后参与，例如购买、收藏、花费至少30s观看和点击
• 0 代表展示项目后未参与
• ? 代表项目还未被展示

从类似线性回归的协同过滤算法，推广到二值标签，我们会发现它更像逻辑回归，从而可以得出类似逻辑回归的代价函数。

协同过滤实现细节

均值归一化

首先进行均值归一化，算法运行会更有效。

有一个新的名为 Eve 的用户，但他没有对任何电影做出评分。如果我们用代价函数进行预测，参数 w 和 b 最终的结果都是 0 ，那么通过类似于线性回归的模型所预测出的评分也将都会是 0 。我们显然不期盼这样的结果，所以我们将表中黄色部分的数据建立成一个二维矩阵，如上图右侧所示。

将每部电影的评分计算出平均值，并将这些平均值聚集成一个向量 μ， μ 是每部电影平均评分的向量且仅对特定电影评过分的用户进行统计。
之后用原矩阵减去 μ 得到新矩阵，其中每一个值都是 y^(i,j) ，即用户 j 给电影 i 的评分。
我们可以用这些值来学习 w^(j) 、b^(j)、x⁽ⁱ⁾ ，再通过模型来预测对用户 j 来说电影 i 的评分，但因为在均值归一化中减去了 μ ，为了不预测出负分，我们要在最后加回 μ_i 。
由此，我们可以计算出用户 Eve 对电影 1 的初始预测评分是 2.5 ，这更接近平均分，而不是直接预测为 0 。

查找相关项目

协同过滤算法为我们提供了一种查找相关项目的方法。

给定电影 i 的特征 x⁽ⁱ⁾ ，如果想找到相关电影，可以尝试找到特征向量 x^(k) 与 x⁽ⁱ⁾ 相似的电影 k 。
特别的是，找到给定特征向量 x^(k) ，判断它是否类似于 x⁽ⁱ⁾ 的方法是：
计算向量 x^(k) 和 x⁽ⁱ⁾ 距离的平方（向量中每一项相减的平方），并求和。接着我们选出求和最小的几个 x^(k) ，这就是与电影 i 相似的几部电影。

协同过滤算法的一些局限性：

• 冷启动问题
  • 如何对很少有用户评价的新项目进行排名？
  • 如何向仅对少数项目评过分的新用户展示一些合理的东西？
• 无法提供一种自然的方式来使用 附加信息 或者 有关项目或用户的附加信息
  • 即使收集了足够多的信息来为用户针对性的提供提示，但实际上用户有着完全不同的行为方式

基于内容过滤

协同过滤vs内容过滤

协同过滤算法会根据其他和我们评分相近的用户的评分，向我们推荐物品。
基于内容过滤的算法会根据用户和物品的特征，做出匹配之后向用户推荐。也就是说，它需要每个用户的一些特征和每个物品的一些特征，所以我们仍需获得用户对某些物品的评分数据。

\(x^{(j)}_u\) 代表每个用户的特征，\(x^{(i)}_m\) 代表每部电影的特征。然而，这两个特征在大小上可能非常不同。
之前我们预测用户 j 给电影 i 的评分为：w_j · x_i + b_j ，为开发基于内容过滤的算法可去掉 b （不会损害算法性能）。
\(v^{(j)}_u\) 是从用户 j 的特征 \(x^{(j)}_u\) 计算出的数字列表，而 \(v^{(i)}_m\) 是从电影 i 的特征 \(x^{(i)}_m\) 计算出的数字列表。这两个向量的点积可以很好的预测用户 j 给电影 i 的评分。需要注意的是，\(v^{(j)}_u\) 和 \(v^{(i)}_m\) 的大小必须相同，即拥有相同的项数。

深度学习实现内容过滤

为了计算 v_u 和 v_m ，我们将使用神经网络。用户网络和电影网络可以假设具有不同数量的隐藏层以及每个隐藏层可以具有不同数量的单元，只有输出层需要具有相同维度的大小。那么预测值即 v_u 和 v_m 的点积。
目前的描述中，我们预测的评分是 0~5 ，如果使用二值标签，则可以将 sigmoid 函数应用于此，并使用它来预测 y^(i,j) 的概率。

实际上，我们可以将用户网络和电影网络绘制在一个图表中，就好像是一个单一的神经网络。
再构建代价函数 J 来训练用户网络和电影网络的所有参数，这要求我们有一些用户对某些电影进行评分的数据。

对于给定具体的电影，查找其他类似的电影的方法和之前提到的协同过滤非常相像。
寻找其他电影 k ，使得描述电影 k 的向量和描述电影 i 的向量的距离平方和很小，即找到了相似电影。
另外，这可以提前预计算，提前为每部电影找到与其相似的电影，这样就可以在用户浏览的同时展示这些电影。

从大目录中推荐

面对大量数据时，许多大规模推荐系统的实现分为两个步骤：

• 数据检索（retrival）
• 排名（ranking）

第一步是数据检索。在数据检索期间，将生成由一大堆看似合理的候选项目构成的列表。
之后可能会做的是：

1. 对于用户观看的最后 10 部电影，找到 10 部最相似的电影
2. 对于用户最多观看过的 3 种类型，找到评分最高的 10 部电影
3. 在用户所在国家或地区评分最高的 20 部电影

将这些电影集合成一个列表，并删除重复项和已观看/已购买项。

第二步是排名。得到数据检索的列表后，通过学习好的模型给出的预测评分进行排名，再将排名后的结果展示给用户。
一个额外的优化是，如果提前计算过所有电影的 v_m ，那我们只需要计算所有用户的 v_u，并计算这两个向量的点积，即可相对较快地计算出预测值。

我们需要为算法做出的决定之一是在数据检索过程中要检索多少项：
检测更多的项目会获得更好的性能，但是算法会变得更慢。为了分析和优化对检索项目数量的取舍，建议进行离线实验来观察检索额外项目会产生多少更相关的推荐。

强化学习

强化学习介绍

什么是强化学习

以通过强化学习让直升机自动飞行为例。
我们的任务是，在给定直升机位置的前提下决定如何移动控制杆。在强化学习中，我们将直升机的位置、方向、速度等称为状态 s ，所以任务是找到一个函数，将直升机的状态映射到动作 a ，意味着要推动控制杆多少才能保持直升机在空中平衡与飞行。
强化学习的关键输入是奖励/奖励函数，来告知直升机飞行的好坏，并给予正负面的奖励。
总的来说，强化学习的关键思想是，不需要告诉它每个输入的正确输出是什么，只需通过指定的奖励函数告诉它做的好与不好；而算法的工作是自己想明白如何选择好的行动。

案例：火星漫游者

给定 6 个状态（1~6），火星车坐落在状态4，而状态 1 （更重要）和状态 6 具有调查任务，通过奖励函数反应这两个状态的价值。所以，状态 1 奖励是 100 ，状态 6 奖励是 40 ，而其他状态均为 0 。
火星车可以向任意方向移动，到达状态 1 或 6 后，我们称之为终止状态，意味着在终止状态得到奖励后便不再发生动作。
在每个时间步骤中，机器都处于某种状态 s ，可以选择某个动作 a ，得到动作后状态的奖励 R(s) ，以及到达的新状态 s’ 。当学习特定的强化学习算法时，会看到上述四项：状态、行动、奖励、下一个状态，其中奖励是和状态 s 相关，而不是下一个状态 s’ 。

强化学习中的回报

每个状态有不同的奖励，经历不同的状态可以得到不同的奖励，但如何取舍不同组动作所得到的奖励呢？

回报（return）被定义为所走每一步状态的奖励和，并由折扣系数进行加权。
折扣系数 γ 的作用是让算法在每一状态的奖励有所损耗，从而作为回报的衡量尺度。常见的折扣系数接近 0.9、0.99.0.999这样的数字。

不同方向移动最终带来的回报不同，将只左走和只右走的回报对比并结合，即可得出最优解。

强化学习中的策略

我们的目标是提出一个策略函数 π ，它的工作是将任意状态 s 作为输入，并将其映射到它希望我们采取的某个动作 a 。图中的 π(x) 根据图中最下策略得出。

强化学习的目标是找到一个策略 π(x) ，来决定每一步应该采取什么动作才能使得回报最大化。

回顾关键概念

许多相同形式的状态、动作、奖励等也可以被用在其他应用程序。

马尔可夫决策过程（MDP）是指未来仅取决于当前状态，而不取决于是如何到达此状态的。

状态-动作值函数

函数定义

状态动作值函数用 Q(s, a)表示，它是关于所处状态 s 和做出行动 a 的函数。
Q(s, a)为对应的回报：从状态 s 开始，采取行动 a 一次，在这之后表现最佳。所以在上述描述后，采取任何行动都会带来尽可能高的回报。
但奇怪的是，如果我们知道什么是最佳行为，已经知道在每个状态下的最佳行动，为什么还要计算 Q(s, a)？
为解决这个问题，我们想出一种方法来计算 Q 函数，甚至在我们想出最佳策略之前。Q(s, a) 中的 s 是从状态 s 开始， a是行动，然后根据下一状态显示的策略来进行下一步移动，如 Q(2, →) 所示。
对不同的状态和动作的 Q(s, a) 所算出的回报值是不同的，如上图中所示，状态 1~6 向左向右的回报值不同。状态动作值函数总是用字母 Q 表示，所以通常被称为 Q 函数，因此 Q 函数和状态动作值函数可以互相使用。

我们会发现，假设在状态 2 ，Q(s, a) 是 50，实际上是状态 2 的最大可能回报。同样地，状态 3、4、5 的 Q(s, a)都是其最大可能回报。
结果表明，从任何状态 s 得到的最佳回报是 Q(s, a) 在采取不同行动下的最大值。例如状态 4 ，Q(4, →)=10，而 Q(4, ←)=12.5 ，这两个值中较大的 12.5 是状态 4 的最佳回报。
如果我们要享受最佳的回报，那么采取的行动 a 需要让 Q(s, a) 更大。也就是说，状态 s 下最佳的动作 a 实际上能最大化 Q(s, a)。
如果可以计算出每个状态和每个动作的 Q(s, a) ，我们要做的是观察并选择能最大化 Q(s, a) 的动作 a，以及某个策略 π(s) ，其挑选出的动作 a 能得到最大的 Q(s, a)。
另外，Q 函数有时会写成 Q* ，有时也称为最优 Q 函数。

贝尔曼方程（Bellman Equation）

贝尔曼方程可以帮助我们计算状态动作值函数。

上图中，给出一些参数的定义以及贝尔曼方程的具体公式。s’ 和 a’ 代表下一个状态和下一个动作。

如上图所示，由贝尔曼方程计算 Q 值。

第一项 \(R(s)\) 是可以立刻得到的奖励，有时也被称为即时奖励。
第二项 \(\gamma \max_{a'}Q(s',a')\) 是从状态 s 开始，采取动作 a 之后，到达新状态 s’ ，我们表现最佳且从 s’ 处得到最佳回报，所以这一项就是 Q(s’, a’) 的最大值。
贝尔曼方程实际上运用了动态规划的思想，所以图中的两个式子相等。

上图是两式相等更为直观的体现。

随机环境

一个随机环境的例子是，假设命令火星车向左移动，大部分时间都会成功，但如果有 10% 或 0.1 的时间它实际上会滑向相反的方向呢？
我们已经把回报写成了这些折扣奖励的和，但当强化学习问题仍不明朗时，我们难以看到一个确定的序列奖励。所以在随机强化学习问题中，我们感兴趣的不是最大化回报，因为那是一个随机数。我们感兴趣的是最大化折扣奖励总和的平均值，这里的平均值指的是取所有不同序列奖励的总和的平均值，我们称之为期望回报。这意味着我们要最大化折扣奖励总和的期望均值，用 E 来表示。
所以强化学习算法的工作是选择一个策略 π 来最大化折扣奖励总和的期望。

总之，当我们有一个随机强化学习问题或随机马尔可夫决策过程时，我们的目标是选择一个策略，告诉我们采取什么动作 a 和状态 s ，以最大化期望回报。
有所不同的是，当我们在状态 s 处采取动作 a 时，下一个状态 s’ 是随机的，所以我们在 \(\max_{a'}Q(s',a')\) 放置一个期望运算符 E 。

连续状态空间

连续状态应用的案例

例如，火星车可以在一组离散的状态（6个状态）的任意一个，更近一步，它可以位于大量连续位置中的任何一个，即一条线上的任何地方。所以我们可以用 0 到 6 中的任意数字来表示位置，比如 2.7 公里。
另一个例子，我们控制卡车的应用程序。卡车的状态 s 包括横坐标 x 、纵坐标 y 、角度 θ 、x 方向的速度 、y 方向的速度和汽车角度变化的速度，所以汽车的状态将由这6个数字组成的向量表示。

对于控制直升机，其状态包含的数据就更多。

登陆月球案例

这个案例是，我们控制一架着陆器，要求在适当时候发射推进器，使着陆器安全降落在两旗之间。控制推进器可以朝下、左、右三个方向移动，所以我们有四种动作可以选择：
nothing：无动力 left：左推进器（向右飞） right：右推进器（向左飞） main：主推进器（向上飞）
所以着陆器的状态 s 包含多项，前四项不再解释，θ 和 θ点 分别代表着陆器向左倾斜或向右倾斜多少，l 和 r 分别代表着陆器的左右脚是否落地。前六项都是任意数字，l 和 r 只能是 0 或 1。

这是着陆器的奖励函数，对于最后判定结果的不同，奖励值也不同。设计者实际上会费心去考量我们会采取哪些行为，并将其编入奖励函数之中，以激励产生更多想要的行为和更少不想要的行为（比如crash）。
当我们自己构建强化学习应用程序时，指定奖励函数会比指定每个状态（state）下应该采取的正确行动（action）要容易得多。

所以针对月球登陆问题，我们的目标是学习一个策略 π ，当给定一个状态 s 时，采取动作 a=π(s) ，以最大化折扣奖励的总和。一般情况下，lunar lander 会使用非常大的折扣因子 γ ，比如 γ=0.985 。

学习状态价值函数

我们要训练一个神经网络来计算或近似状态动作价值函数 Q(s,a)。

我们把状态 s 和动作 a 放在一起作为输入。具体来说，状态是之前看到的 8 个数字的列表（x 到 r），动作是 nothing、left、right 和 main 并且使用 one-hot 特征向量编码。
此外，我们还将 Q(s,a) 看作神经网络需要近似的目标值 y 。
如果我们能在隐藏层和输出层中用适当的参数选择来训练神经网络，那么每当着陆器处于某个状态 s 时，我们可以使用神经网络计算所有四个动作的 Q(s,a) ，从中找出 Q 值最高的并选择对应的动作 a

此时，问题就变成，如何训练用于输出 Q(s,a) 的神经网络呢？
方法是：使用贝尔曼方程来创建一个包含大量 x、y 样本对的训练集，然后使用监督学习，从状态动作对到目标值 Q(s,a) 的映射。

当提出上述方法的时候，问题就又变成了，我们如何获取一个包含大量 x、y 的训练集供神经网络学习呢？
我们会采取随机动作，通过尝试不同的动作，我们会观察到在某些状态下采取可能好动作或不好动作的大量样本。之后我们得到了对应状态下的一些奖励 R(s) ，作为动作的结果，我们得到新状态 s’ 。所以我们会看到(s, a, R(s) , s’)这个元组。
随机产生 10000 个元组，足以创建一个训练样本 (x, y) ，而元组中前两个元素用于计算 x ，后两个元素用于计算 y 。x 包含状态 s 和动作 a 共 12 个数字，y 将使用贝尔曼方程的右侧计算。
计算 y 时，Q(s’, a’) 从哪得来呢？
实际上，最初我们不知道什么是 Q 函数，我们可以完全随机的猜测 Q 函数，随着一步步的进行，对 Q 的猜测会越来越好。

来看看学习 Q 函数的完整算法：

1. 随机初始化神经网络的所有参数
2. 重复做：
   • 在着陆器上随机采取一些动作，得到对应的元组
   • 存储 10000 个最近出现的元组
   • 训练神经网络：
     • 创建一个包含 10000 个样本的训练集
     • 训练 Q_new ，Q_new 学习取近似 y
   • 令 Q = Q_new

如果我们运行这个算法，从 Q 函数的随机猜测开始，但是使用贝尔曼方程反复尝试改进 Q 函数的估计。通过多次这样做，采取很多动作训练一个模型来提高对 Q 函数的猜测，所以对于训练的下一个模型，它会对 Q 函数有更好的估计，然后训练的再下一个模型会更好。当更新 Q = Q_new 时，那么下一次训练模型对 Q(s’, a’) 的估计会更好。
所以我们运行算法时，希望每次得到的 Q(s’, a’) 都是对 Q 的更好的估计，运行算法足够长的时间后，这实际上将成为 Q(s, a) 真实值的一个很好的估计，由此我们可以用它来为 MDP 挑选好的动作。这种算法有时被称为 DQN 算法，代表 DQ 网络。

算法改进1：改善神经网络结构

这是我们之前看到的神经网络架构，输入 12 个数字并输出 Q(s, a) ，每当我们处于某种状态时，我们必须在神经网络中分别进行 4 次推理才能计算出这 4 个值，从而选择最大 Q 值的动作 a 。
事实证明，训练单个神经网络同时输出所有 4 个值会更有效。

这是修改后的神经网络架构，输入是着陆器状态 s 的 8 个数字，现在输出单元有 4 个，神经网络让它们输出四种动作的 Q 值。
所以，神经网络的工作是同时计算，当我们处于状态 s 时，所有四个可能动作的 Q 值。这样效率更高，只运行一次推理就可以得到所有的四个值，然后快速选择最大化 Q(s, a) 的动作 a。
注意到贝尔曼方程中有一个步骤，我们必须计算 a’ 上 Q(s’, a’) 的最大值，这个神经网络也使计算它更有效，因为我们同时为所有动作获得 Q(s’, a’) 的 a’ ，所以我们只需选择最大值来计算贝尔曼方程右侧的值。

算法改进2：ε-贪婪策略（ε-greedy）

算法中的一个步骤是在着陆器中随机采取动作，所以当学习算法还在运行时，我们并不知道在每个状态下采取的最佳动作是什么，也还没有对 Q(s, a) 有一个很好的估计，所以这一步我们要采取什么动作？

• 选择1：
  • 在任意状态 s 下挑选能使 Q(s, a) 最大的动作 a
• 选择2：
  • 大多数时候，假设概率为 0.95 ，选择使 Q(s, a) 最大化的动作 a
  • 极少数情况，假设概率为 0.05 ，随机选择动作 a

通常情况下，选择2是更为一般的做法。原因如下：
假设由于某种原因， Q(s, a) 是随机初始化的，所以学习算法认为发动主推进器不是一个好主意，也许神经网络参数初始化的结果使得 Q(s, main) 总是很低。在这种情况下，因为神经网络总是试图选择最大化 Q(s, a) 的动作 a ，那么它永远不会尝试发动主推进器。
所以因为随机初始化，如果神经网络确实有一些动作可能偶尔不太行，但选择1意味着算法永远不会尝试那些动作，而在选择2下，每一步我们都有小概率尝试不同的动作，这样就可以打破神经网络的局限性。
这种随机选择动作的想法有时被称为探索步骤（exploration），直接采取最大化 Q(s, a) 的动作有时被称为贪婪动作（greedy）或在文献中被称为利用/剥削步骤（exploitation）。
选择2有一个名字叫做 ε-贪婪策略，这里 ε=0.05，是随机选择一个动作的概率。

算法改进3：小批量（mini- batch）和软更新（soft update）

mini-batch 既可以加快强化学习算法的运行速度，也适用于加快监督学习。我们从监督学习入手，当数据集非常大时（例如1亿个样本），算法在梯度下降的每一步都需要在1亿个样本上计算平均值，以至于速度奇慢无比。
相反，我们可以选择一个更小的数字 m’ ，暂时令 m’=1000，在每一步中我们不使用所有的数亿个样本，而是使用 m’ 个样本。这样，梯度下降的每次迭代都只需要关注 1000 个而不是 1 亿个样本，花费的时间更少，算法效率提升。

mini-batch 梯度下降所做的是，在算法的每一次迭代中会聚焦于不同部分的数据子集。反映在图像上，就是每一次迭代会在图中增添一些点。

对比批梯度下降（batch）和小批量梯度下降（mini-batch）：

• 批梯度下降：梯度每下降一次，都会使参数更接近代价函数的全局最小值
• 小批量梯度下降：也许每一次不是最佳的梯度下降方向，但平均而言，mini-batch梯度下降倾向于观察全局最小值，不可靠且产生噪声（noise），但每次迭代消耗的算力更少

mini-batch版本的强化学习算法如下图：

软更新（soft update）可以让算法可靠地收敛。

Q = Q_new 这一步会使 Q 发生非常突然的变化，如果神经网络不太好且比旧的还要糟糕，很可能会用更糟糕的神经网络覆盖 Q 函数。
软更新有助于防止 Q 变得更糟糕。

特别的，神经网络 Q 有参数 w 和 b ，当我们训练新的神经网络时，会得到新的参数 w 和 b 。在原始算法中，我们会让 w=w_new ，b=b_new ，即 Q=Q_new 的具体步骤。
在软更新中，我们要做的是每训练一个新的神经网络时， w 只会用到一点点新值 w_new ，b 也一样。这些数字 0.01 和 0.99 是我们可以设置的超参数，控制着更新 w 和 b 的速度，且这两个数字的和为 1 。软更新降低了强化学习算法振荡或不收敛或具有其他不良性质的可能性。

至此，第三部分（无监督学习，推荐系统，强化学习）结束。