[人工智能]从西洋跳棋开始机器学习

机器学习定义

对于某类任务T和性能度量P，如果一个计算机程序在T上以P衡量的性能指标随着经
验E而自我完善，那么我们称这个计算机程序在从经验E中学习

例如，对于学习下西洋跳棋的计算机程序，它可以通过和自己下棋获得经验；它的任务是参与西洋跳棋对弈；它的性能 用它赢棋的能力来衡量。通常，为了很好地定义一个学习问题，我们必须明确这三个特征：任务的种类、衡量任务提高的标准、经验的来源。

以下有三个例子
西洋跳棋学习问题

- 任务T：下西洋跳棋
- 性能标准：比赛中击败对手的百分比
- 训练经验E：和自己进行对弈

手写识别学习问题

- 任务T：识别和分类图像中的手写文字
- 性能标准：分类的正确率
- 训练经验E：已知分类的手写文字数据库

机器人驾驶学习问题

- 任务T：通过视觉传感器在四车道高速公路上驾驶
- 性能标准：平均无差错行驶里程（差错由人来进行监督）
- 训练经验E：注视人类驾驶时录制的一系列图像和驾驶指令

设计一个学习系统

为了说明机器学习的基本设计方法和学习途径，让我们考虑设计一个学习下西洋跳棋的程序。我们的目标是让它进入西洋跳棋世界锦标赛。我们采用最显而易见的标准衡量它的性能：在世界锦标赛获胜的百分比。

选择训练经验

我们面临的第一个设计问题是选择训练经验的类型，使系统从中进行学习。给学习器提供的训练经验对它的成败有着重大的影响。一个关键属性是训练经验能否为系统的决策提供直接或者间接的反馈。例如，对于西洋跳棋，系统可以从直接的训练样例（各种棋盘状态和相对应的正确走子，即棋谱）中学习，也可以从间接的训练样例（很多对弈的序列和最终的结局）中学习。对于后者，对弈中较早走子的正确性必须从对弈最终的输赢来推断。这时学习器又面临一个信用分配问题，也就是考虑每一步走子对最终结果的贡献度。信用分配可能是一个非常难以解决的问题，因为如果后面下得很差的话，那么即便开始的走子是最佳的，这盘棋也会输掉，那么我们能否认最开始走子是不行的吗？所有，从直接的训练反馈中学习要比间接反馈学习容易。

训练经验的第二个重要属性是学习器可以在多大程度上控制训练样例序列。例如，学习器可能依赖施教者选取棋盘状态和提供每一次正确的移动；或者，学习器可能自己提出它认为特别困惑的棋局并向施教者请教正确的走子；或者，学习器可以完全控制棋局，间接的完成训练分类，就像没有施教者时它和自己对弈进行学习一样。对于最后一种情况，学习器可能选择以下两组情况中的一种：第一，试验它还未重新考虑过的棋局；第二，在它目前发现的最有效的路线的微小变化上对弈，以磨砺它的技能。做一下总结，即

- 训练经验是以超乎学习器控制的随机过程提供的
- 学习器可向施教者提出不同类型的查询
- 学习器通过自动探索环境来搜集训练样例

训练经验的第三个重要属性是训练样例的分布能够多好地表示实例分布我们知道，最终系统的性能P是通过后者来衡量的。一般而言，当训练样例的分布和将来的测试样例的分布相似，学习具有最大的可信度。对于我们的西洋跳棋学习，性能指标P是该系统在世界锦标赛上获胜的百分比。如果它的训练经验E仅仅由它和自己对弈的训练组成，便存在一个明显的危险：这个训练可能不能充分地代表该系统以后被测试时的情形。 例如，学习器可能在训练中从未遇到过某些致命的棋局，而这些棋局又很有可能被人类世界冠军所采用。实际上，学习的样例通常与最终系统被评估时的样例有着一定的差异，学习器必须能够从中学习。假如世界级的西洋棋棋手都没兴趣教一个程序下期，那么我们就不进行学习了吗？现在有一个重要的问题是，目前多数机器学习理论都依赖于训练样例和测试样例分布一致这一假设，尽管我们需要这样的假设来得到理论的结果，但是同样的必须牢记在实践中这个假设经常是不成立的。 即掌握了样例的一种分布，不一定会使它对其它的分布也有着很好的性能。如果是基于训练样例和测试样例分布一致这一假设，那么我们收集到的训练集合测试集必须大而且完备。

因此，完了完成这个学习系统的设计，现在需要选择：

- 要学习的知识的确切表示
- 对于这个目标知识的表示
- 一种学习机制

选择目标函数

下一个设计选择是决定要学习的知识的确切类型以及执行程序该如何使用这些知识。我们从一个对于任何棋局都能产生合法走子的西洋跳棋博弈程序开始。那么，最终的程序仅须学会从这些合法的走子中选择最佳的走子即可。这个学习任务代表了一类任务：合法走子定义了某个已知的巨大搜索空间，但最佳的搜索策略未知。很多最优化问题都可归于此。例如，对于生产过程的调度和控制问题。生产中的每一步都要很清楚，但调度这些写步骤的最佳策略未知。

为了学习从合法走子中做出选择，很明显，要学习的信息类型就是一个程序或者函数，它对任何给定的棋局都能选出最好的走法。可称此函数为ChooseMove，并用记法ChooseMove：B ->M来表示这个函数以合法棋局集合中的棋盘状态作为输入，并从合法走子集合中产生某个走子作为输出。在关于机器学习的所有讨论中，我们发现了可以把提高任务T的性能P的问题简化为学习像ChooseMove 这样某个特定的目标函数的问题。所有目标函数的选择是一个关键的设计。

尽管在例子中很明显把ChooseMove作为目标函数，但我们会发现学习这个目标函数会非常的困难，原因是提供给系统的是间接的训练经验。另外一个可供选择的目标函数是一个评估函数，它为任何给定棋局赋予一个数字评分。可以发现，对于本例，学习这个目标函数更简单。令这个目标函数为V，并用V：B -> R 来表示V把任何合法的棋局映射到某一实数值（用R表示实数集合）。我们让这个目标函数V给号的棋局赋予较高的评分。如果系统能够成功地学会这个目标函数V，那么它便能使用此函数轻松的找到当前棋局的最佳走法。实现的方法是，先产生每一个合法走子对应的所有后续棋局，然后使用V来选取其中最佳的后续棋局，从而选择最佳走子。

对于任意棋局，目标函数V的准确值应该是多少呢？当然任何对较好的棋局赋予较高分数的评估函数都适用。然而，最好在那些产生最佳对弈的众多方法中定义一个特定的目标函数V。可以看到，这将使得设计一个训练算法变得简单。因此，对于集合B中的任何的棋局状态b，我们如下定义目标函数V(b):

1. 如果b是一最终的胜局，那么V(b) = 100
2. 如果b是一最终的负局，那么V(b) = -100
3. 如果b是一最终的和局，那么V(b) = 0
4. 如果b不是最终棋局，那么V(b) = V(b')，其中b'是从b开始双方都采用最优对弈后可达到的终局。

当然，由于这个定义的递归性，它的运算效率不高，所以这个定义对于西洋跳棋比赛者不可用。除了无关紧要的前三种终局情况，对于某一个棋盘状态（情况4），b决定它的值V(b)需要向前搜索到达终局的所有路线！有意这个定义不能由西洋跳棋程序高效地运行，这个定义被称为不可操作的定义。当前的学习目标是发现一个可操作的定义V，它能够被西洋跳棋程序用来在合理的时间内评估棋局并选取走法。

所以在这种情况下，学习任务被简化成发现一个理想目标函数V的可操作性描述。通常要完美地学习这样一个V的可操作的形式是非常困难的。事实上，通常我们仅仅希望学习算法得到近似的目标函数。在当前讨论中，用V’来表示程序中世纪学习到的函数，以区别理想目标函数V’。

选择目标函数表示

现在，我们已经有了确定的理想的目标函数V了，接下来，我们必须为它选择一个表示，它被学习程序用来描述要学习的函数V’。对此，也有很多设计选择。例如，可以V’表示为一张大表，对于每个惟一的棋盘状态，表中有惟一的表项来确定它的状态值。或者，可以让程序用一个规则集合来匹配棋局的特征以表示V’，或采用一个与预定义棋盘特征有关的二次多项式函数，或者用人工神经元网络。通常，选择这个描述包含一个重要的权衡过程。一方面，我们总希望选取一个非常有表征能力的描述，以最大可能地逼近理想的目标函数V。另一方面，越有表征能力的描述需要越多的训练数据，使程序能够从它表示的多种假设中选择。为了简化讨论，现在选择一个简单的表示法：对于任何给定的棋盘状态，函数*V’*可以通过以下棋盘参数的线性组合来计算：

$x_1$:棋盘上黑子的数量
$x_2$:棋盘上红子的数量
$x_3$:棋盘上黑王的数量
$x_4$:棋盘上红王的数量
$x_5$:被红子威胁的黑子数量（即会在下一次被红子吃掉的黑子数量，下同）
$x_6$:被黑子威胁的红子数量
于是，学习程序把*V’(b)*表示为了一个线性函数：
V’(b) = $w_0+w_1{x}_1+w_2{x}_2+w_3{x}_3+w_4{x}_4+w_5{x}_5+w_6{x}_6$
其中，$w_0$到$w_6$为数字系数，或者叫权，由学习算法来选择。在决定某一棋盘状态值时，权$w_1$到$w_6$决定了不同的棋盘特征的相对重要性，而权$w_0$为一个附加的棋盘状态值常量。

那么，我们现在的学习任务是：

• 任务T：下西洋跳棋
• 性能标准：比赛中击败对手的百分比
• 训练经验E：和自己进行对弈
• 目标函数：V’：B -> R
• 目标函数的表示：
  V’(b) = $w_0+w_1{x}_1+w_2{x}_2+w_3{x}_3+w_4{x}_4+w_5{x}_5+w_6{x}_6$

前三条是对学习任务的说明，后两条制定了为实现这个学习程序的设计方案。这个设计的关键作用是把学习西洋跳棋战略的问题简化为学习目标函数中系数$w_0$到$w_6$的问题。

选择函数逼近算法

为了学习目标函数V’，需要一系列训练样例，每一个样例描述了特定的棋盘状态b和它的训练值$V_{train}(b)$。换而言之，每一个训练样例是形式为
<b,$V_{train}(b)$>的序偶。举个例子来说，下面的训练实例描述了一个黑棋取胜（此时红棋已经没有子了，$x_2=0$）的棋盘状态b。他的目标函数值$V_{train}(b)$ = +100
< <$x_1=3,x_2=0,x_3=1,x_4=0,x_5=0,x_6=0$>, +100>
下面描述了一个过程，它先从学习器可得的简介训练经验中推导出上面的训练样例，然后调整权值$w_i$以最佳你和这些训练样例。

1.估计训练值
根据以上的学习模型，学习器可以得到的训练信息仅仅是对弈最后的胜负。另一方面，我们需要训练样例为每个棋盘状态赋予一个分值。给对弈结束时的棋盘状态评分容易，然而要给对弈结束前的大量中间棋盘状态评分就不是那么的容易了。因为，正如前文所说，一盘棋的最终输赢未必能够说明这盘棋当中的每一个棋盘状态的好坏。例如，即使某个程序输了一盘棋，仍会有这样的情况，这盘棋前面的棋局应被给予很高的评价，失败的原因在于后来糟糕的走法。

尽管估计中间棋局训练值具有内在的模糊性，但令人惊讶的是有一个简单的方法却取得了良好的效果。这种方法是把任何中间棋局b的训练值$V_{train}(b)$赋以V’(Successor(b))，其中V’是机器学习目前采用的V的近似函数，Successor(b)表示b之后再轮到程序走棋时的棋盘状态（也就是程序走了一步和对手回应一步后的棋局）。估计训练值的方法可被归纳为:
训练值估计法则：$V_{train}(b)$ <- $V^{\prime }(Successor(b))$

或许这看起来就离谱，只是用当前的V’ 来估计训练值，这一训练值又用来更新V’。但是，我们是在用后续棋局Successor(b) 的估计值来估计棋局b的值。凭直觉我们可以看到，越接近游戏结束的棋局，V’ 越趋向于精确。事实上，在特定条件下，这种基于对后续棋局进行估计的迭代估计训练值的方法，已被证明可以近乎完美地收敛到$V_{train}(b)$的估计值。

2.调整权值
剩下的事情就是为这个学习算法选择最适合的训练样例{<b,$V_{train}(b)$>}的权$w_i$。第一步必须定义最佳你和训练数据的含义。一种常用的方法是把最佳的假设（或权向量集合）定义为使训练值和假设V’ 预测出的值间误差平方和E最小
$$E\equiv \sum _{<b,V_{train}(b)>\in TrainingExample}(V_{train}(b)?V^{\prime }(b){)}^2$$

至此，我们的目标就是寻找权值或V’，使对于观测到的训练数据E值最小。

已知的一些算法可以得到线性函数的权使此定义的E最小化。在这里需要一个算法，他可以在有了新的训练样例时进一步改进权值，并且它对估计的训练数据中过的插错有好的健壮性。一个这样的算法被称作最小均方法，或者叫LMS训练法则。对于每一训练样例，它把权值想减小这个训练数据误差的方向略微调整。这个算法可被看做对可能的假设（权值）空间进行随机的梯度下降搜索，以使误差平方和E最小化。
LMS算法的定义：
对于每一个训练样例<$b$,$V_{train}(b)$>

• 使用当前的权计算V’(b)
• 对每一个权值$w_i$进行如下更新
  $$w_i\leftarrow w_i+\eta (V_{train}(b)?V^{\prime }(b))x_i$$

这里的$\eta$是一个小的常数（比如0.1），用来调整权值更新的幅度。为了直观地理解这个权值更新法则的工作原理，请注意，当误差$(V_{train}?V^{\prime }(b))$为0时，权不会被改变。当$(V_{train}?V^{\prime }(b))$为正时（例如，当V’(b)太低时），每一个权值会根据其对应的特征值增加一定的比例。这回提升V’(b) 的值而减小误差。如果某个参数$x_i$为0，那么它的值不会因为这个误差而改变，这样就使只有那些在训练样例的棋局中确实出现的特征的权值才被更新。令人吃惊的是，在一定的条件下，这种简单的权值调整方法被证明可以收敛到$V_{train}$值的最小误差平方接近。