为了解释机器学习的基本设计方法和学习方法，让我们考虑设计一个学习西方跳棋的程序。我们的目标是让它进入西方跳棋世界锦标赛。我们用最明显的标准来衡量它的性能：赢得世界锦标赛的百分比。

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

训练经验的第二个重要属性是学习器能在多大程度上控制训练样例序列。例如，学习器可能依赖于教师选择棋盘状态，并提供每一个正确的移动；或者，学习器可能会提出他们认为特别困惑的棋局，并咨询教师；或者，学习器可以完全控制棋局，间接完成训练分类，就像它在没有教师的情况下学习一样。对于最后一种情况，学习器可以选择以下两种情况中的一种：第一，测试它还没有重新考虑的国际象棋游戏；第二，在最有效的路线上下棋，以磨练它的技能。总结一下，就是

- 超出学习器控制的随机过程提供的训练经验 - 学习器可以向教师提出不同类型的查询 - 通过自动探索环境，学习器收集训练样本 

训练经验的第三个重要属性是训练样本的分布可以很好地表示实例分布众所周知，最终系统的性能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)$。换而言之，每一个训练样例是形式为
$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)$的估计值。