《Machine Learning》，作者Tom Mitchell，卡内基梅隆大学。

第一章 引言

1.1 学习问题的标准描述：

机器学习的定义：

如果一个计算机程序针对某类任务T的用P衡量的性能根据经验E来自我完善， 那么我们称这个计算机程序在从E中学习，针对某类任务T,它的性能用P来衡量。

例子：

对于学习下西洋跳棋的计算机程序，它可以通过和自己下棋获取经验； 它的任务是参与西洋跳棋对弈； 它的性能用它赢棋的能力来衡量。

学习问题的三个特征：

任务的种类， 衡量性能提高的标准， 经验的来源。

（电子书中写作：“衡量任务提高的标准”，系笔误。）

西洋跳棋学习问题：

任务T： 下西洋跳棋

性能标准P： 比赛中击败对手的百分比

训练经验E：和自己进行对弈（经验的来源，经验可以不可以动态增加，随着经验的增加，该计算机程序还能不能动态地提高自己的赢棋能力？）

除此之外，作者又定义了另外两类机器学习问题：

手写识别学习问题：（模式识别问题的一种）

任务T：识别和分类图像中的手写文字

性能标准P：分类的正确率

训练经验E：已知分类的手写文字数据库（数据库不再动态增加？）

机器人驾驶学习问题：

任务T：通过视觉传感器在四车道高速公路上驾驶

性能标准P：平均无差错行驶里程（差错由人监督裁定）

训练经验E：注视人类驾驶时录制的一系列图像和驾驶指令

简单定义：

通过经验提高性能的某类程序。

1.2 设计一个学习系统

设计一个下西洋跳棋的程序，让它进入西洋跳棋世界锦标赛。

1.2.1 选择训练经验

如何选择训练经验的类型？

训练经验的一个关键属性是训练经验能够为系统的决策提供直接或者间接的反馈。拿西洋跳棋举例，直接direct的训练样例包括：各种棋盘状态和相应的正确走子。

与之相反，间接的indirect的训练样例包括：过去对弈的走子序列和最终的结局。

间接的训练经验，有一个信用分配的问题： 也就是，考虑每一次走子对最终结果的贡献程度。

信用分配可能是一个非常难以解决的问题。所以，从直接的训练反馈学习，要比从间接的训练反馈学习容易。

训练经验的第二个关键属性是学习器可以在多大程度上控制训练样例序列。 可能的方式有以下几种：

学习器依赖于施教者选取的棋盘状态和所提供的每一次正确移动；（学习器不控制训练样例序列，由施教者提供训练样例的序列）

学习器可以自己发现它觉得特别困惑的棋局，并向施教者请教正确的走子；（学习器可以控制训练样例序列，这种情况仍然是直接的训练经验）

学习器可以完全控制棋局和训练分类，就像没有施教者，它是自己与自己对弈，并从中学习；（间接的训练经验）

　　对于这一种情况，学习器可以回选择两种可能的得到训练经验的方法： 1， 选择它还未考虑过的全新的棋局； 2 ， 在它目前发现的最有效的路线上的微小变化上对弈；

除此之外，还有另外一些训练经验序列：

　　训练经验是由随机过程提供的；

　　学习器可以向施教者提出不同类型的查询；

　　学习器通过探索环境，来自动搜索环境中的训练样例。

训练经验的第三个关键属性是， 训练样例的分布能多好的表示实例分布。 一般而言，当训练样例的分布与将来的测试样例的分布相似时，学习具有最大的可信度。

可以看到很多机器学习的理论都假设，训练样例和测试样例的分布是一致的。但是，在实践中，这种假设往往是不成立的。

为了完成西洋跳棋学习问题的学习系统的设计，现在需要选择：

1 要学习的知识的确切类型；

2 对于这个目标知识的表示；

3 一种学习机制

1.2.2 选择目标函数

我们从一个对于任何棋局，都能产生合法legal走子的西洋跳棋博弈程序开始。 那么，最终的程序仅需学会从这些合法走子中选择出最佳走子。

这个学习任务代表了一类学习任务： 合法走子定义了一个已知的巨大搜索空间， 但最佳的搜索策略未知。  很多最优化问题，都可以归于此类。

所以，西洋跳棋学习系统需要学习如何从合法走子中作出选择。  很明显， 要学习的信息类型就是这样一个函数或者程序， 它能从所有的给定的棋局中选出最好的走法， 把此函数称为ChooseMove， 并使用ChooseMove: B->M来表示这个函数接受合法棋局集合中的棋盘状态作为输入， 并从合法走子集合中产生一个走子作为输出。  在关于机器学习的所有讨论中， 我们发现把提高任务T的性能P的问题简化为学习像ChooseMove这样的某个特定的目标函数（target function）的问题是很有益处的。

所以，目标函数的选择是一个关键的设计问题。

但是， 学习这个目标函数是非常困难的，因为提供的训练经验都是间接的。

在本例中，可供选择的另外一个目标函数， 是一个评估函数， 它为任意一个棋局赋予一个数字评分。 这个目标函数定义为V，并用V:B->A来表示V把任意一个棋局B映射到一个实数值。  我们让这个目标函数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开始， 双方都采用最优对弈走法后最终达到的终局。

很显然，上述定义是一个递归的定义，对于第四种情况， 对于某一个棋局状态b，要确定它的目标函数值V（b），需要向前搜索到达终局的所有路线。  由于这个定义不能由西洋跳棋程序高效地决定， 这个定义被称为不可操作的定义。

当前的学习目标是发现一个可操作的定义V， 它能够被西洋棋程序采用，并在实际的时间期限内评估棋局，并选取走法。

所以， 学习任务被简化成： 发现一个理想目标函数V的可操作描述。 通常这是非常困难的。  通常情况下，我们仅希望得到一个近似的目标函数，因为这个原因，学习目标函数的过程常常被称为函数逼近。 （function approximation）。 为了区别， 我们一般使用^V来表示程序实际学习到的函数，以便与理想目标函数V进行区分。

1.2.3 选择目标函数的表示

至此，我们已经确定了理想的目标函数V，接下来必须选择一个表示， 被学习程序用来描述要学习的函数^V。 对于这种表示，也有很多种设计选择。 比如：

1 使用一张大表， 对于每一个唯一的棋盘状态， 表中都有一个唯一的表项来确定它的评分值；

2 让程序使用一个规则集合，来匹配棋局的特征， 据此得到它的评分值；

3 采用一个与预定义棋盘特征相关的二次多项式函数；

4 使用人工神经元网络。

选择这个描述包含了一个重要的权衡过程。 为了简化讨论， 现在选择一个简单的表示法：

对于任意给定的棋盘状态， 函数^V可以通过以下棋盘参数的线性组合来计算：

x1： 黑子数量；

x2： 红子数量；

x3：黑王数量；

x4：红王数量；

x5：被红子威胁的黑子数量；（即 会在下一次被红子吃掉的黑子数量）

x6：被黑子威胁的红子数量；

于是，学习程序把^V（b）表示为一个线性函数：

^V（b）= w0 + w1x1 + w2x2 +w3x3 +w4x4 +w5x5 +w6x6

至此，可以看到西洋跳棋程序的部分设计：

任务T: 下西洋跳棋；

性能标准P： 世界锦标赛上击败对手的百分比；

训练经验E：和自己进行对弈；

目标函数：V=Board->A;

目标函数的表示： ^V（b）= w0 + w1x1 + w2x2 +w3x3 +w4x4 +w5x5 +w6x6

其中，前三条定义了这个学习任务；后两条是这个学习任务的设计方案，它们把这个学习任务化简为确定目标函数的表示中的各个参数（权值）的问题。

1.2.4 选择函数逼近算法

为了学习目标函数^V， 需要一组训练样例， 每一个样例表示了一个特定的棋盘状态b和它的训练值Vtran（b）。 也就是说，每一个训练样例是一个形如<b, Vtran(b)>的序偶。

下面我们来描述一个过程， 它先从学习器可以获得的间接训练经验E中得到一组上述的训练样例， 然后基于这些训练样例，调整w1.w6这些参数，使得目标函数的表示能够最佳拟合这些训练样例。

1 估计训练值

注意，训练值是指针对每一个棋局状态b，它所对应的Vtrans（b）值，也就是棋局状态b的目标函数值。

训练值估计法则：

Vtrans（b）<-^V(Successor(b))

这样，我们就可以得到一个序偶集合{<b, Vtran(b)>}，也就可以根据这个序偶集合拟合w0到w6这些权值。

2 调整权值（调参数）

为了确定最适合训练样例的序偶集合的权值， 必须定义什么是“最佳拟合（best fit）训练数据”？ 一种方法是，使得训练值与使用^V（b）预测出的值得误差的平方和E最小。

已经知道一些算法， 可以得到线性函数的权值，使得这个E值最小。

而在这里，我们还需要一个算法， 它可以在有了新的训练样例时进一步精化权值， 一个这样的付费被称为最小均方法（least mean squares），或者LMS训练法则。

1.2.5 最终设计

西洋跳棋学习程序最终被设计成由4个不同的程序模块组成， 这些模块在很多学习系统中是核心组件。 许多机器学习系统都可以使用这四个通用模块来刻画。

1 执行系统Prefromance System

用学会的目标函数来解决特定的任务。 它把新问题（新一盘棋）的一个实例作为输入， 产生一组解答路线作为输出。 

我一开始的理解是，这个执行系统就是用来在比赛中ongoing与人类选手对弈的部分。 但是，执行系统应该仍然是学习系统的一部分。

2 鉴定器

鉴定器的作用是给出一个棋盘实例b与测试样例值Vtrans（b）的序偶的集合，也就是{<b, Vtran(b)>}。

3 泛化器Generalizer

从特定的训练样例出发，猜测一个一般函数， 使得这个函数能够覆盖训练样例集合，以及样例之外的情形。 这也是为什么这个模块被称为泛化器的原因。 泛化器对应LMS算法，输出是一个使用学习到的权值w0到w6描述的函数^V。

4 实验生成器（Experiment Generator）

实验生成器的输入时当前学习到的函数，输出是一个新的问题（比如，一个最初的棋局），供执行系统去探索。

在西洋跳棋学习程序的例子中， 要学习的知识类型被限定为一个单一的线性评估函数， 而这个线性评估函数被限定为仅仅依赖于六个棋盘特征。

如果目标函数真的可以被表示成这些特定参数的线性组合， 那么程序学到这个目标函数的可能性很大。 反之， 则只能希望它能学习到一个目标函数的近似。 因为一个程序不可能学习到它不能表示的东西。

上述设计中， 目标函数V的表示^V太过于简单，只是一个简单的线性函数。 如果我们使用人工神经元网络表示学到的评估函数， 考虑对棋局的完整描述，而不是棋盘的几个参数， 那么这个学习程序的实用性将会大大增强。

1.3 机器学习的一些观点和问题

在机器学习方面， 一个有效的观点是， 机器学习问题经常归结为搜索问题。 即，对一个非常大的假设空间进行搜索， 以确定一个最佳拟合观察到的数据和学习器已有知识的假设。

以西洋跳棋学习器为例， 它输出的假设空间包括， 所有可由权值w0到w6的不同值表示的评估函数。 机器学习的任务就是搜索这个空间， 来定位与训练数据最佳拟合的假设。

在本书的后续章节中，给出了很多基本表示（目标函数的表示，比如线性函数， 人工神经网络等）定义的假设空间的搜索算法。

机器学习的问题

机器学习这门学科致力于回答下面的这些问题：

1 存在什么样的算法，能从特定的训练数据学习一般的目标函数呢？

2 怎样把一个学习任务转换成一个或多个函数逼近问题？

3 关于选择后续的训练经验， 什么样的策略最好？

《机器学习》读书笔记-第一章 引言