一、机器学习定义

1.学科通用定义

机器学习是一门致力于研究如何通过计算手段，利用经验来改善系统自身性能的学科。

其核心逻辑是：让计算机系统不依赖人工预先编写的固定规则，而是从经验数据中自主挖掘规律、构建模型，进而在新的任务场景中表现出更优的性能。

2.Mitchell 形式化定义

1. 若一个计算机程序对于任务 T 和性能度量 P，其性能通过利用经验 E 在 T 上获得改善，则称该程序关于 T 和 P 从 E 中学习。这个定义里的三个核心要素缺一不可，我们可以用垃圾邮件分类的例子理解：

   • 任务 T：判断一封新邮件是否为垃圾邮件；
   • 经验 E：已标注 “垃圾 / 非垃圾” 的历史邮件数据集；
   • 性能度量 P：分类的准确率（正确判断的邮件占总邮件的比例）。随着模型学习的经验 E 越多，它在任务 T 上的准确率 P 越高，就说明这个程序的学习效果越好。

补充核心特点

• 机器学习中，“经验” 的载体是数据，因此它也常被描述为 “从数据中学习” 的学科；
• 机器学习的终极目标是泛化能力—— 模型能对从未见过的新数据做出准确判断，而非仅在训练数据上表现良好。

二、基本术语

1.数据与模型

假定我们收集了一批西瓜的数据，如：（色泽=青绿;根蒂=蜷缩;敲声=浊响)， (色泽=乌黑;根蒂=稍蜷;敲声=沉闷)， (色泽=浅自;根蒂=硬挺;敲声=清脆)……每对括号内是一个西瓜的记录，定义：

数据集：所有记录的集合；D=｛x1,x2,…,xm｝。

示例或样本：对西瓜描述的每条记录；xi=(xi1,xi2,…,xid),d是样本xi的维数即特征数，每一个x是属性描述。

特征或属性：色泽、敲声等对象某方面的表现和性质；

属性空间（样本空间、输入空间）：样本属性张成的空间称为属性空间（样本空间、输入空间）；

特征向量：每个西瓜（每个示例在属性空间的坐标表示）。

模型：也称为学习器，可看作学习算法在给定数据集和参数空间的实例化；

标记（签）：训练集中示例的结果信息；

“学习”或“训练”：学习模型的过程；

测试：学得模型后，使用其进行预测的过程称为“测试”；

训练集：所有训练样本的集合；

测试集：所有测试样本的集合；

泛化能力：“学习”出的模型适用于新样本的能力；

2.模型预测的类别

分类：预测值为离散值的问题，譬如区分邮件是否为垃圾邮件。

回归：预测值为连续值的问题，譬如预测已知特征的房子价格。

根据训练数据有无标记信息可将学习任务分为： 监督学习（分类与回归）和无监督学习（聚类等）；

学习过程：通常假设样本空间中全体样本服从一个未知分布，且“独立同分布”。一般训练样本越多，我们得到的关于该未知分布的信息越多，这样就越有可能通过学习确定分布参数，获得具有强泛化能力的模型。

三、假设空间与归纳偏好

1.假设空间（Hypothesis Space）

假设空间是所有可能用于描述目标概念的假设集合，它包含了对 “目标概念是什么” 的所有合理猜想。在机器学习中，我们的核心任务是从假设空间中找到与真实目标概念最接近的假设 —— 而这个搜索过程的前提，是先明确假设空间的边界和规模。

1.1 假设空间的核心构成（以西瓜问题为例）

要学习 “好瓜” 的概念，首先需定义假设的表示形式：西瓜问题中，假设被表示为 “属性合取式”，即：好瓜 ↔ (色泽 =?) ∧ (根蒂 =?) ∧ (敲声 =?)其中 “?” 的取值有两类：

• 具体属性值：每个属性的实际可能取值（如色泽的 “青绿”“乌黑”“浅白”，根蒂的 “蜷缩”“硬挺”，敲声的 “浊响”“沉闷”）；
• 通配符 “*”：表示 “该属性任意取值都不影响判断”（如 “色泽 =*” 意味着 “无论色泽是什么，只要其他属性满足，就是好瓜”）。

此外，还需考虑极端情况：目标概念本身不成立（如 “世界上没有好瓜”），用符号 “∅” 表示该假设。

1.2 假设空间的规模计算（呼应 “4×4×4+1”）

假设空间的规模由 “每个属性的假设选项数” 决定，规则为：每个属性的选项数 = 具体取值数 + 1（通配符 “*”），再加上极端假设 “∅”。

以西瓜问题的 3 个核心属性为例（文档明确属性取值）：

• 色泽：3 种具体值（青绿、乌黑、浅白）→ 选项数 = 3+1=4；
• 根蒂：3 种具体值（蜷缩、硬挺）→ 选项数 = 3+1=4；
• 敲声：3 种具体值（浊响、沉闷）→ 选项数 = 3+1=4；

由于假设是 “属性合取”（需同时满足所有属性条件），因此 “存在好瓜” 的假设组合数为：4（色泽）× 4（根蒂）× 4（敲声）= 64

再补充 “不存在好瓜” 的极端假设 “∅”，最终假设空间规模为：64 + 1 = 65（即 “4×4×4+1” 的由来）。

1.3 假设空间的本质

假设空间是对 “目标概念可能形态” 的全面枚举，它不依赖训练数据，仅由 “属性个数、属性取值范围” 和 “假设表示形式” 决定。例如，若增加 “纹理” 属性，假设空间规模会进一步扩大。

2.版本空间（Version Space）

版本空间是假设空间中与训练集 “一致” 的假设子集—— 即所有能正确分类训练集中所有样本的假设。它是从假设空间中筛选出来的 “候选假设集合”，因为只有与训练数据匹配的假设，才有可能逼近真实目标概念。

2.1 “与训练集一致” 的定义

若一个假设 h 满足：对训练集中的每一个样本（x,y），都有 h (x)=y（即能正确判断该样本是否为好瓜），则称 h 与训练集一致。

2.2 版本空间的筛选过程（以西瓜问题训练集为例）

文档中表 1.1 的西瓜训练集（部分样例）如下：

筛选要求：

假设：对 “好瓜” 概念的猜想，形式为属性合取式：好瓜 ↔ (色泽=?) ∧ (根蒂=?) ∧ (敲声=?)

与正例一致：一个假设若要保留，必须满足：所有正例都符合该假设的 “好瓜条件”—— 即正例的属性取值完全满足假设中每个属性的约束（具体值需匹配，* 则无需匹配）。反之，若某个正例不符合假设的条件，该假设就与正例矛盾，需排除。

排除与正例矛盾的假设的本质

本质是确保留下的假设能 “覆盖所有正例”—— 即训练集中所有已知的好瓜，都能被假设判定为 “好瓜”（符合假设的条件）。这是版本空间 “与训练集一致” 的核心要求之一（另一要求是 “不覆盖任何反例”）。

如果一个假设连已知的正例都无法包含（把好瓜误判为坏瓜），那么它必然不符合真实的 “好瓜” 概念，因此没有资格进入版本空间。

根据以上规则，最终筛选出的版本空间可能包含以下 3 个假设（文档图 1.2）：

基于此训练集，从假设空间（65 个假设）中筛选出 “一致假设”：

• 排除与正例（好瓜）矛盾的假设：如 “好瓜 ↔ (色泽 = 青绿) ∧ (根蒂 = 硬挺) ∧ (敲声 = 浊响)”（无法解释编号 1 的好瓜）；
• 排除与反例（坏瓜）矛盾的假设：如 “好瓜 ↔ (色泽 =*) ∧ (根蒂 =*) ∧ (敲声 =*)”（会将编号 3 的坏瓜误判为好瓜）。

1. 好瓜 ↔ (色泽 =*) ∧ (根蒂 = 蜷缩) ∧ (敲声 =*)
2. 好瓜 ↔ (色泽 =*) ∧ (根蒂 =*) ∧ (敲声 = 浊响)
3. 好瓜 ↔ (色泽 =*) ∧ (根蒂 = 蜷缩) ∧ (敲声 = 浊响)

2.3 版本空间的本质

版本空间依赖训练数据：训练集不同，筛选出的版本空间也不同；若训练样本足够多，版本空间会逐渐缩小（甚至只剩一个假设）。但由于现实中训练样本有限，版本空间通常包含多个假设 —— 这也是后续需要 “归纳偏好”（如奥卡姆剃刀）选择唯一假设的原因。

2.4 为什么需要版本空间？—— 解决假设空间的 “冗余与矛盾” 问题

假设空间是所有可能假设的全集（如西瓜问题中假设空间规模为 37），但它存在两个关键问题，而版本空间正是为解决这些问题而生：

2.4.1 假设空间包含大量 “无效假设”，需通过数据筛选

假设空间的设计仅基于 “属性个数、属性取值范围” 和 “假设表示形式”（如西瓜问题的 “属性合取式”），并未考虑训练数据的实际情况。其中大量假设会与训练集矛盾：

• 有的假设会将训练集中的正例误判为反例（如 “好瓜 ↔ 色泽 = 青绿 ∧ 根蒂 = 硬挺 ∧ 敲声 = 浊响”，无法解释编号 1 的正例 “根蒂 = 蜷缩”）；
• 有的假设会将训练集中的反例误判为正例（如 “好瓜 ↔ 色泽 =* ∧ 根蒂 =* ∧ 敲声 =*”，会把编号 3 的反例 “根蒂 = 硬挺、敲声 = 清脆” 判为好瓜）。

这些与训练数据矛盾的假设显然不符合 “泛化到新样本” 的目标，必须被排除。而版本空间正是通过训练数据筛选后，仅保留与训练集一致的假设子集，剔除了所有无效假设。

2.4.2 假设空间规模庞大，直接搜索最优假设效率极低

即使是简单的西瓜问题，假设空间也有 37 个假设；若属性更多（如增加 “纹理”“脐部”），假设空间规模会呈指数级增长。直接在如此庞大的空间中寻找 “最优假设”（能正确泛化的假设），计算复杂度极高。

版本空间通过训练数据 “剪枝”，将假设规模从 “庞大的全集” 缩小到 “有限的候选集”（如西瓜问题版本空间仅 3 个假设），大幅降低后续选择最优假设的难度，使机器学习的 “假设搜索” 过程可行。

2.5 版本空间的核心作用

版本空间作为 “与训练集一致的假设子集”，是机器学习从 “数据观测” 到 “模型选择” 的关键中间环节，具体作用可分为 4 点：

2.5.1 缩小假设搜索范围，降低模型选择复杂度

版本空间的核心价值是过滤无效假设，将搜索范围从 “所有可能假设” 聚焦到 “符合数据的候选假设”。例如：

• 西瓜问题中，假设空间有 65 个假设，但通过训练集筛选后，版本空间仅保留 3 个假设（如 “好瓜 ↔ 色泽 =* ∧ 根蒂 = 蜷缩 ∧ 敲声 =”“好瓜 ↔ 色泽 = ∧ 根蒂 =* ∧ 敲声 = 浊响” 等）；
• 后续只需在这 3 个假设中选择，无需遍历 37 个假设，效率显著提升。

2.5.2 保留所有 “合理候选假设”，避免遗漏真实目标概念

由于训练数据通常是有限的（如西瓜问题仅 4 个训练样本），无法唯一确定 “真实目标概念”（即客观存在的 “好瓜” 定义）。版本空间的作用是保留所有与训练数据不矛盾的假设—— 这些假设都有可能是 “真实目标概念的近似”，避免因过早排除某个假设而漏掉正确答案。

例如：若训练数据不足，可能存在多个假设都能正确分类训练集（如西瓜问题的 3 个版本空间假设），此时若直接丢弃部分假设，可能恰好丢掉了与真实目标概念一致的那个。

2.5.3 为 “归纳偏好” 提供决策基础

当版本空间包含多个假设时（大多数情况），机器学习算法必须通过归纳偏好（如 “奥卡姆剃刀”“偏好更简单的假设”）选择唯一假设作为最终模型。版本空间正是归纳偏好发挥作用的 “舞台”：

• 若没有版本空间，直接在假设空间中应用归纳偏好，偏好将无从下手（因为假设空间中既有合理假设，也有矛盾假设）；
• 版本空间已筛选出所有合理假设，归纳偏好只需在这些假设中选择（如西瓜问题中，若偏好 “更简单的假设”，可能选择 “好瓜 ↔ 色泽 =* ∧ 根蒂 = 蜷缩 ∧ 敲声 =*”，因其使用的通配符更多，假设更简洁）。

2.5.4 反映 “数据信息量” 与 “假设不确定性”

版本空间的大小可直观反映训练数据的信息量：

• 当训练数据较少时，版本空间规模较大（如仅 1 个正例和 1 个反例，可能有多个假设符合）；
• 随着训练数据增多，更多矛盾假设被排除，版本空间逐渐缩小；
• 当训练数据足够充分时，版本空间可能仅剩 1 个假设 —— 此时该假设就是唯一与所有数据一致的假设，大概率接近真实目标概念。

这种变化能帮助我们判断 “当前数据是否足够”：若版本空间仍很大，说明数据信息量不足，需补充更多训练样本；若版本空间已缩小到 1 个假设，说明数据已能唯一确定候选假设。

3.归纳偏好

归纳偏好的核心定义是：机器学习算法在假设空间中选择 “更优假设” 的固有倾向或 “价值观”。它的本质是解决 “版本空间的多假设困境”—— 由于训练数据有限，版本空间中通常存在多个与训练集一致的假设（如西瓜问题版本空间有 3 个假设），但这些假设对新样本的预测结果可能完全不同（例：对 “色泽 = 青绿、根蒂 = 蜷缩、敲声 = 沉闷” 的新瓜，不同假设会判为 “好瓜” 或 “坏瓜”）。此时，算法必须通过自身的归纳偏好，从多个候选假设中选择唯一假设，否则无法输出确定的预测结果。

3.1 归纳偏好的作用

若学习算法没有归纳偏好，会陷入两个致命问题：

1. 无法输出确定模型：面对版本空间中的多个假设，算法只能随机选择一个，导致对同一新样本的预测结果不稳定（时而判好瓜、时而判坏瓜），这样的模型毫无实用价值。例：西瓜问题中，若算法无偏好，对新瓜 “色泽 = 浅白、根蒂 = 蜷缩、敲声 = 浊响”，可能随机选 “好瓜↔根蒂 = 蜷缩”（判好瓜），也可能选 “好瓜↔敲声 = 浊响”（也判好瓜），但对 “色泽 = 青绿、根蒂 = 蜷缩、敲声 = 沉闷”，会随机选前一假设（判好瓜）、后一假设（判坏瓜），结果矛盾。

2. 无法泛化到新样本：机器学习的目标是 “泛化”（对未见过的样本正确预测），而非仅 “记忆” 训练样本。若无偏好，算法无法确定 “哪类假设更可能符合真实目标概念”，只能停留在 “训练集上等效”，无法应对新样本。

3.2 归纳偏好的原则

归纳偏好是算法内置的 “选择标准”，不同算法的偏好不同，常见表现有：

3.2.1 对 “简单假设” 的偏好（奥卡姆剃刀原则）

这是最常用的归纳偏好，即 “若多个假设与训练集一致，选择最简单的那个”（奥卡姆剃刀：如无必要，勿增实体）。

• “简单” 的定义：通常指 “假设的描述复杂度低”，例：

  • 西瓜问题中，“好瓜↔(根蒂 = 蜷缩)∧(敲声 =*)” 比 “好瓜↔(根蒂 = 蜷缩)∧(敲声 = 浊响)” 更简单（前者用 1 个具体属性值 + 1 个通配符，后者用 2 个具体属性值）；
  • 回归问题中，“平滑曲线 A（y=-x²+6x+1）” 比 “崎岖曲线 B” 更简单（A 的表达式更简洁）。

• 注意：“简单” 的定义并非绝对，需结合任务场景。例：西瓜问题中，“根蒂 = 蜷缩” 和 “敲声 = 浊响” 哪个假设更简单？需额外引入领域知识（如瓜农经验：根蒂比敲声更能判断成熟度）。

3.2.2 对 “特殊假设” 或 “一般假设” 的偏好

• 偏好 “更特殊的假设”：倾向于选择 “适用范围更窄、约束更严格” 的假设，例：在西瓜版本空间中，选择 “好瓜↔(根蒂 = 蜷缩)∧(敲声 = 浊响)”（仅适用于根蒂蜷缩且敲声浊响的瓜）。
• 偏好 “更一般的假设”：倾向于选择 “适用范围更广、通配符更多” 的假设，例：选择 “好瓜↔(根蒂 = 蜷缩)∧(敲声 =*)”（适用于所有根蒂蜷缩的瓜，无论敲声如何）。

3.3 无免费午餐定理（NFL）

归纳偏好并非 “越优越好”，其有效性严格依赖 “与问题本身的匹配度”，这由无免费午餐定理（NFL） 揭示：

3.3.1 NFL 定理的核心结论

• 若所有可能的问题（目标函数）出现概率相同，则任何学习算法的期望泛化性能都相同 —— 无论算法多 “聪明”（如 SVM），还是多 “笨拙”（如随机胡猜），长期来看性能无差异。

• 例：若存在一半问题中 “根蒂 = 蜷缩” 是好瓜特征，另一半问题中 “根蒂 = 蜷缩” 是坏瓜特征，那么 “偏好根蒂属性” 的算法和 “随机选择” 的算法，期望误差相同。

• NFL定理有一个重要前提:所有"问题"出现的机会相同、或所有问题同等重要.但实际情形并不是这样.很多时候,我们只关注自 己正在试图解决的问题(例如某个具体应用任务),希望为它找到一个解决方案, 至于这个解决方案在别的问题、甚至在相似的问题上是否为好方案,我们并不 关心.例如,为了快速从A地到达B地,如果我们正在考虑的A地是南京鼓 楼、B地是南京新街口,那么"骑自行车"是很好的解决方案;这个方案对A 地是南京鼓楼、B地是北京新街口的情形显然很糟糕,但我们对此并不关心。

• NFL定理最重要的寓意,是让我们清楚地认识到,脱离具体问题,空泛地谈论"什么学习算法更好"毫无意义,因为若考虑所有潜在的问题,则所 有学习算法都一样好.要谈论算法的相对优劣,必须要针对具体的学习问题;在某些问题上表现好的学习算法,在另一些问题上却可能不尽如人意,学习算法 自身的归纳偏好与问题是否相配,往往会起到决定性的作用。

3.3.2 对归纳偏好的启示

• 脱离具体问题谈 “算法优劣” 或 “偏好优劣” 毫无意义：只有针对某一具体问题（如 “判断西瓜好坏”“手写数字识别”），算法的归纳偏好与问题的 “真实规律” 匹配时，才能表现出好性能。例：在西瓜问题中，“偏好根蒂属性” 的算法（因根蒂确实能反映成熟度）比 “偏好色泽属性” 的算法（色泽受品种影响大）泛化性能更好；但在 “判断苹果好坏” 问题中，若 “色泽” 是关键特征，则 “偏好色泽” 的算法更优。

四、机器学习应用开发典型步骤

1. 数据采集与标记

• 采集：收集足够数量且具有多样性的样本，同时保证样本的特征具备有效性（能反映问题核心属性）；

• 标记：针对有监督学习方法，数据标记是必要前提（需为样本标注明确的目标结果，如“好瓜/坏瓜”“垃圾邮件/正常邮件”）。

2. 数据清洗

对采集的原始数据进行预处理，具体包括：统一数据单位、删除无效数据（如缺失关键特征的数据）、剔除重复数据、过滤噪声数据（如异常值、错误记录）。

3. 特征选择

对数据特征进行分析筛选，选取对模型预测有效的特征，常用方式包括：

• 人工选择：基于业务经验和领域知识，直接筛选核心特征；

• 自动选择：借助算法实现特征筛选，典型算法如PCA（主成分分析，用于降维并保留关键信息）。

4. 模型选择与训练

• 模型选择：根据预测系统的学习类型（有监督/无监督）、具体问题领域、数据量大小、训练时长限制、预期准确性等因素，选择适配的模型；

• 数据集划分：将处理后的数据集拆分为训练集和测试集；

• 模型训练：使用训练集对选定的模型进行训练，让模型学习数据中的规律。

5. 模型性能评估和优化

• 性能评估：模型训练完成后，通过对应的性能度量指标评估模型的泛化能力（对新数据的适应能力）；

• 常见性能度量指标：

  • 回归任务：MSE（均方误差）、RMSE（均方根误差）、R²（决定系数）等；

  • 分类任务：R（召回率）、P（精确率）、F1分数、AUC（曲线下面积）等。

• 模型优化：可通过增加数据集规模、调整训练次数、微调模型参数等方式，提升模型性能。

6. 模型使用

当训练出性能满意的模型后，将其本地保存；后续需要使用时，直接加载已保存的模型进行预测，无需重新训练，从而节省预测时间。