机器学习之一：机械式学习

        正如人们有各种各样的学习方法一样，机器学习也有多种学习方法。若按学习时所用的方法进行分类，则机器学习可分为机械式学习、指导式学习、示例学习、类比学习、解释学习等。这是温斯顿在1977年提出的一种分类方法。

有关机器学习的基本概念，可看我文章：机器学习的基本概念-CSDN博客 

接下来我们先探讨第一种：机械式学习。

一、什么是机械式学习

（一）基本思想、定义

1.基本思想

机械式学习（Rote Learning）又称为死记式学习，是一种最为简单直接、原始的机器学习方式，其基本思想是直接存储环境所提供的信息，并在需要时原封不动地检索这些信息来解决问题。它不涉及对数据的深入分析、推理或归纳，仅仅是将输入与相应的输出进行一一对应并记录下来。可以将其类比为学生单纯地死记硬背知识，不理解知识背后的原理和逻辑关系，只是在考试时能够准确地回忆出所背诵的内容。

在机械式学习中，系统所做的就是建立一个庞大的记忆库，当接收到新的输入时，尝试在记忆库中找到匹配的记录，并返回相应的输出。

2.定义

从形式化的角度来看，设输入空间为X，输出空间为 Y。机械式学习系统维护一个记忆表 M，其中存储了一系列的输入-输出对。对于给定的新输入，机械式学习的过程就是在记忆表 M 中查找是否存在使得（这里的相等可以根据具体的应用场景定义合适的匹配标准），如果存在，则返回对应的作为输出；如果不存在，则可能返回一个默认值或者表示无法处理该输入。

例如，在一个简单的英语单词翻译系统中，输入空间X是英语单词的集合，输出空间Y是对应的中文翻译的集合。记忆表 M 中存储了大量的英语单词及其对应的中文翻译，如 ("apple", "苹果")，("book", "书") 等。当输入一个新的英语单词 "cat" 时，系统会在记忆表 M 中查找是否存在 "cat" 这个单词，如果找到了，就返回对应的中文翻译 "猫"。

（二）表示形式、实现过程

1.表示形式

（1）表格形式：这是最常见的表示形式，将输入-输出对以表格的形式存储。每一行代表一个输入-输出对，表格的列分别对应输入和输出。

例如，在一个简单的数字平方计算的机械式学习系统中，记忆表可以如下表示：

输入（数字）	输出（平方）
1	1
2	4
3	9
4	16

（2）哈希表形式：利用哈希函数将输入映射到一个特定的位置，在该位置存储对应的输出。哈希表的优点是查找速度快，能够在接近常数的时间复杂度内完成查找操作。

例如，对于上述英语单词翻译系统，可以使用哈希函数将英语单词映射到哈希表的不同位置，当输入一个单词时，通过哈希函数快速定位到对应的翻译。假设哈希函数为 （其中word[i]表示单词的第 i 个字符，ASCII(word[i])表示该字符的ASCII码值，N 是哈希表的大小），那么对于单词 "apple"，通过哈希函数计算出其在哈希表中的位置，然后在该位置存储 "苹果" 这个翻译。

2.实现过程

（1）数据收集：收集一系列的输入 - 输出对。这些数据可以来自各种渠道，如人工标注、历史记录等。例如，在构建一个图像识别的机械式学习系统时，可以收集大量的图像及其对应的类别标签，如收集许多猫的图像和狗的图像，并分别标注为“猫”和“狗”。

（2）存储：将收集到的输入 - 输出对存储到记忆表中。如果使用表格形式存储，直接将数据添加到表格的相应行中；如果使用哈希表形式存储，则通过哈希函数计算输入的哈希值，将输入 - 输出对存储到对应的哈希桶中。

（3）查询与输出：当接收到新的输入时，在记忆表中进行查询。对于表格形式，遍历表格的每一行，查找与输入匹配的记录；对于哈希表形式，通过哈希函数计算输入的哈希值，直接定位到对应的哈希桶进行查找。如果找到匹配的记录，则返回对应的输出；如果没有找到，则按照预先设定的规则进行处理，如返回一个错误信息或者默认输出。

以一个简单的温度转换机械式学习系统为例（将华氏温度转换为摄氏温度）：

（1）数据收集：已知一些华氏温度及其对应的摄氏温度值，如(32, 0)，(68, 20)，(104, 40)等。

（2）存储：将这些数据存储到一个表格形式的记忆表中。

（3）查询与输出：当输入一个新的华氏温度值，如50时，系统遍历记忆表查找是否存在50这个华氏温度值。如果没有找到，则可能无法准确转换；如果找到匹配的值，则返回对应的摄氏温度值。

（三）算法描述

机械式学习的算法相对简单，主要包括以下几个步骤：

1.初始化记忆表：

创建一个空的记忆表 M，用于存储输入 - 输出对。可以根据具体的需求选择表格形式或哈希表形式等进行存储。

python代码：

# 以表格形式初始化记忆表（Python示例）memory_table = []

2.添加数据到记忆表：

对于每一个输入 - 输出对，将其添加到记忆表 M 中。

python代码：

# 向记忆表中添加数据（Python示例）def add_to_memory(x, y, memory_table):memory_table.append((x, y))return memory_table# 示例调用memory_table = add_to_memory(1, 1, memory_table)

3.查询记忆表：

当接收到新的输入时，在记忆表 M 中查找是否存在与匹配的输入。

python代码：

# 在记忆表中查询（Python示例）def query_memory(x, memory_table):for item in memory_table:if item[0] == x:return item[1]return None# 示例调用result = query_memory(1, memory_table)

4.返回输出：

如果找到匹配的输入，则返回对应的输出；如果没有找到，则根据具体情况返回相应的结果，如默认值或错误信息。

上述算法的时间复杂度主要取决于记忆表的存储结构和大小。如果使用表格形式存储，查询操作的时间复杂度为 O(n)，其中 n 是记忆表中记录的数量；如果使用哈希表形式存储，在理想情况下，查询操作的时间复杂度为 O(1)，但在存在哈希冲突的情况下，时间复杂度可能会增加。

二、典型案例（塞缪尔的跳棋程序）

塞缪尔的跳棋程序是机械式学习的一个经典应用案例，它展示了机械式学习在游戏领域的应用以及如何通过简单的记忆和检索来提高程序的性能。

1.程序背景与目标

塞缪尔开发的跳棋程序旨在通过学习来提高下棋的水平。虽然该程序不仅仅依赖于机械式学习，但机械式学习在其中起到了重要的基础作用。程序的目标是能够与人类棋手或其他程序进行对弈，并尽可能地赢得比赛。

2.机械式学习在程序中的实现

（1）数据收集：在对弈过程中，程序记录了大量的棋盘状态（输入）和在该状态下采取的最佳走法（输出）。每一个棋盘状态都可以用一个特定的编码方式来表示，例如可以将棋盘上每个棋子的位置、棋子的类型等信息编码成一个向量。对于每一个棋盘状态，程序通过与对手对弈或其他评估方式确定最佳的走法。

（2）存储：将收集到的棋盘状态 - 最佳走法对存储到一个记忆表中。由于棋盘状态的数量可能非常庞大，为了提高存储和查询效率，可能会采用一些优化的存储结构，如哈希表。可以使用一个哈希函数将棋盘状态编码映射到哈希表的不同位置，然后在该位置存储对应的最佳走法。

（3）查询与走法选择：当程序面临一个新的棋盘状态时，它会在记忆表中查询是否存在与当前状态匹配的记录。如果找到匹配的记录，则直接采用记忆表中存储的最佳走法；如果没有找到匹配的记录，则可能需要使用其他策略（如启发式搜索）来确定走法，并将新的棋盘状态 - 走法对添加到记忆表中，以便在未来遇到相同或相似的状态时能够直接使用。

3.示例流程说明

（1）假设当前棋盘状态为 S_1，程序首先将 S_1 编码成一个向量表示。

（2）然后通过哈希函数计算该向量的哈希值，根据哈希值在记忆表中查找是否存在匹配的记录。

（3）如果找到了与 S_1 匹配的记录，假设该记录对应的最佳走法为 M_1，则程序选择走法 M_1 进行下一步操作。

（4）如果没有找到匹配的记录，程序启动启发式搜索算法，在当前棋盘状态下评估各种可能的走法，并选择一个被认为是最佳的走法 M_2。同时，将棋盘状态 S_1 和走法 M_2 作为一个新的输入-输出对添加到记忆表中。

（5）程序继续进行对弈，重复上述过程，不断积累经验并更新记忆表。

塞缪尔的跳棋程序CHECKERS采用极大极小方法搜索博弈树，在给定的搜索深度下用估价函数对格局进行评分，然后通过倒推计算求出上层节点的倒推值，以决定当前的最佳走步。

CHECKERS的学习环节把每个格局的倒推值都记录下来，当下次遇到相同的情况时，就直接利用“记住”的倒推值决定最佳走步，而不必重新计算。例如，设在某一格局A时轮到CHECKERS走步，它向前搜索三层，得到如图1所示的捜索树。

图1 博弈搜索树

在图1中，根据对端节点的静态估值，可求得A的倒推值为6，最佳走步是走向C。这时CHECKERS就记住A及其倒推值6。假若在以后的对弈中又出现了格局A且轮到它走步，则它就可以通过检索直接得到A的倒推值，而不必再做倒推计算，这就提高了效率。如果博弈时出现了图2所示的情况，格局A是搜索树的端点，此时使用A的倒推值比使用它的静态估值将更准确，同时由于对A使用了所记忆的倒推值，因而对格局Q来说，相当于搜索深度扩大到六层。

图2 以A为端点的博弈树

机械式学习实质上是用存储空间来换取处理时间。虽然节省了计算时间，但却多占用了

存储空间，当因学习而积累的知识逐渐增多时，占用的空间就会越来越大，检索的效率也将随着下降。所以，在机械式学习中要全面权衡时间与空间的关系，这样才能取得较好的效果。

4.程序的效果与局限

（1）效果：通过不断地记录和利用对弈中的经验，塞缪尔的跳棋程序在一定程度上提高了下棋的水平，能够与一些人类棋手进行有竞争力的对弈。机械式学习使得程序能够快速地利用过去的经验，避免了在相同或相似的情况下重复进行复杂的搜索。

（2）局限：然而，机械式学习也存在一些明显的局限。首先，它只能处理与记忆表中记录完全相同或非常相似的情况，如果遇到全新的、未在记忆表中出现过的棋盘状态，程序可能无法有效地应对。其次，记忆表的大小会随着对弈次数的增加而不断增大，可能会导致存储和查询效率下降。此外，机械式学习不涉及对知识的深入理解和推理，无法从已有的经验中进行归纳和泛化，以应对更广泛的情况。

5.对现代机器学习的启示

塞缪尔的跳棋程序虽然是早期的机器学习尝试，但它为现代机器学习提供了一些重要的启示。一方面，它展示了记忆和经验在学习中的重要性，即使在复杂的任务中，简单的记忆和检索机制也可以起到一定的作用。另一方面，它也揭示了机械式学习的局限性，促使研究人员探索更高级的学习方法，如基于推理、归纳和泛化的学习方法，以提高机器学习系统的智能水平和适应性。

综上所述，机械式学习作为一种基础的机器学习方式，在简单的任务和特定的场景中具有一定的应用价值。塞缪尔的跳棋程序是其典型应用案例，通过对该案例的分析，我们可以更好地理解机械式学习的原理、实现过程以及其优缺点和对现代机器学习的启示。在实际应用中，我们可以根据具体的需求和任务特点，合理地选择是否使用机械式学习，并结合其他学习方法来构建更强大的机器学习系统。