第一章 - 绪论

机器学习定义

经典定义

利用经验改善系统自身的性能

随着时代发展，主要研究智能数据分析的理论和方法，并已成为智能数据分析的源泉之一。

课后题

1. 机器学习的经典定义是：利用（）改善系统自身的性能。
   • 经验
   • 专家
   • 规则
   • 实践
2. 随着机器学习领域的发展，目前主要研究以下哪个领域的理论和方法？
   • 汇编语言
   • 程序设计
   • 硬件
   • 智能数据分析
3. 机器学习利用经验，必须对以下哪个选项进行分析？
   • 天气
   • 数据
   • 生活
   • 语言

典型的机器学习过程

要进行机器学习，先要有数据.假定我们收集了一批关于西瓜的数据，例如（色泽= 青绿；根蒂= 蜷缩；敲声= 浊响），（色泽= 乌黑；根蒂= 稍蜷；敲声=沉闷），（色泽= 浅白；根蒂= 硬挺；敲声=清脆），……, 每对括号内是一条记录,意思是 “取值为”

这组记录的集合称为一个“数据集”（data set）, 其中每条记录是关于一个事件或对象（这里是一个西瓜）的描述，称为一个 “示例”（instance）或 “样本 " （sample）. 反映事件或对象在某方面的表现或性质的事项，例如 “色泽”“根蒂” “敲 声 " 称 为 “属 性 “（attribute）或 “特征”（feature）; 属性上的取值，例如 “青绿” " 乌 黑 " 称 为 “属性值”时 tribute value）. 属性张成的空间 称为“属性空间” （attribute space）、 “样本空间”（sample space）或 “输入空间”.例如我们把 “色泽” “根蒂” “敲声”作为三个坐标轴，则它们张成一个用于描述西瓜的三维空间，每个西瓜都可在这个空间中找到自己的坐标位置.由于空间中的每个点对应一个坐标向量，因此我们也把一个示例称为一个“特征向量”（feature vector）.

一般地，令 D = { $x_1,x_2,...x_m$}，表示包含m个示例的数据集，每个示例由 d 个属性描述（例如上面的西瓜数据使用了 3 个属性），则每个示例$X_i$= （$x_{i}1;x_{i}2;...x_{i}d$）是 d 维样本空间X中的一个向量，d 称为样本$X_i$的 “维数 "（dimensionality）.

从数据中学得模型的过程称为“学习”（learning）或 “训练”（training）,这个过程通过执行某个学习算法来完成.训练过程中使用的数据称为“训练数据 “（training data）, 其中每个样本称为一个“训练样本” （training sample）,训练样本组成的集合称为“训练集 "（training set）. 学得模型对应了关于数据的某种潜在的规律，因此亦称“假设 "（hypothesis）; 这种潜在规律自身,则称为 “真相”或 “真实”（ground-truth）, 学习过程就是为了找出或逼近真相.本书有时将模型称为“学习器”（learner）, 可看作学习算法在给定数据和参数空间上的实例化.

可以总结我们的机器学习过程为，首先收集数据，对数据进行处理，选择合适的算法进行训练，得到模型，模型使得我们可以预测新的数据。其过程如下图所示

今后我们要体需要体会如下内容：

• 一个算法针对什么样的数据是有效的？
• 这样的数据需要满足什么样的特点？
• 而它产生的模型又是在什么情况下会有效？
• 这样的模型本身又具有什么样的特点？

课后题

1. 课程的西瓜数据集中，“好瓜、坏瓜”是一个西瓜样例的什么？
   • 属性
   • 类别标记
   • 没有意义
   • 数据集名称
2. 对于要预测的新的数据样本，它的类别标记是？
   • 已知的
   • 未知的
   • 都可以
   • 负类
3. 机器学习的模型，_ 是_（是/不是）从数据中产生的。

计算学习理论

PAC理论，全称为"Probably Approximately Correct"理论，是机器学习领域中一种重要的理论框架，主要用于描述学习算法的泛化能力。PAC理论由Valiant在1984年提出，其核心思想是：如果一个学习算法在有限的样本上能够以高概率近似正确地学习到目标概念，那么这个算法就被认为是有效的。

PAC理论主要包括以下几个关键概念：

1. 概念（Concept）：在PAC理论中，概念通常指的是一个分类函数，它可以将输入的实例映射到一个标签上，例如在二分类问题中，标签可能是0或1。

2. 假设空间（Hypothesis Space）：假设空间是所有可能的概念的集合。学习算法需要在这个空间中选择一个概念，以尽可能地接近真实的概念。

3. 样本（Sample）：样本是一组输入实例和对应的标签，用于训练学习算法。

4. 学习算法（Learning Algorithm）：学习算法是一个过程，它接收一组训练样本，并输出一个概念，即一个分类函数。

5. 泛化误差（Generalization Error）：泛化误差是学习算法在未知数据上的平均错误率，即算法输出的错误标签与真实标签之间的差异。

6. PAC学习（Probably Approximately Correct Learning）：如果存在一个学习算法，对于任何给定的概念，以及任何ε > 0和δ > 0，当样本数量足够大（通常与1/ε和1/δ有关）时，算法能够在概率至少为1-δ的情况下，找到一个概念，其泛化误差不超过ε，那么这个概念就被认为是PAC可学习的。

PAC理论的重要性在于，它提供了一种形式化的框架来分析和比较不同的学习算法。通过PAC理论，我们可以量化学习算法的泛化能力，并理解在给定的样本大小和错误容忍度下，算法的性能如何。此外，PAC理论也为设计更有效的学习算法提供了理论基础。

然而，PAC理论也有其局限性。例如，它通常假设数据是独立同分布的（i.i.d.），这在现实世界中并不总是成立。此外，PAC理论主要关注算法的泛化能力，而不是其计算效率或实际应用中的其他因素。尽管如此，PAC理论仍然是理解机器学习算法性能的一个重要工具。

PAC理论中并没有一个特定的"公式"来描述整个理论，但是它确实包含了一些关键的数学概念和定义，这些可以用数学公式来表达。以下是PAC理论中一些核心概念的数学表达：

1. 泛化误差（Generalization Error）：
   $\text{Generalization Error}={\mathrm{Pr}}_{(x,y)\sim D}[h(x)\ne y]$
   这里，$h$是学习算法选择的概念（分类函数），$(x,y)$是从分布 $D$ 中抽取的样本，$Pr$表示概率。

2. PAC学习的定义：
   一个概念类 $\mathcal{C}$ 是PAC可学习的，如果存在一个学习算法 $A$，对于任意的 $ϵ>0$和 $\delta >0$，当样本量 $m$足够大时，$A$ 能够在概率至少为 $1-\delta$ 的情况下找到一个概念 ( h )，使得 $h$的泛化误差不超过 $ϵ$：
   $\mathrm{Pr}[\text{Generalization Error}>ϵ]\le \delta$

   对于这个表达式我们要思考两个问题：
   ①为什么不追求|f(x)-y|=0？
   ②为什么这里需要算概率？而不是一个绝对化的数值？

   理解上述问题，需要我们对于人工智能在研究什么性质的问题有一定理解。经济学习通常在解决什么样的问题？这个问题具有高度的不确定性、复杂性，甚至我不知道如何下手去解决这个问题。当我们的知识已经不能精确地给我们结果的时候，我们才需要使用机器学习。这样从数据里面去分析，期望从数据里面能找到答案。那么，这时候我们不能指望这个答案是100%准确的，毕竟这不是那种我们已经清楚了解的问题。这一段分析，也是只从问题性质的了解。
   我们不妨换一个角度来理解。从“计算的要求”来理解。我们一定都知道一个问题“P?=NP”。P问题是什么？——在多项式时间内，我们一定能找到这个问题的解。NP问题是什么？——在多项式时间内，我给你一个解，请帮我判定这个解是不是这个问题的解。我们经常做的问题，哪怕给了我们解，我们能否在多项式时间内验证这个解有多好？有多差？都很有可能做不到。故，如果“|f(x)-y|=0”且概率值为1，也就是说，我们每一次运行都能够得到确定的最佳答案，即构造性的证明了“P=NP以及NP之外的其他问题”。
   所以，既然做不到绝对精确。那么我们不妨可以放宽一些要求。|f(x)-y|我希望你尽可能的接近，虽然他不是绝对接近。同时，我们还能进一步放松要求，我们确认让这个概率让这个概率趋于1，即执行某算法很多次，其中很多次这个模型都做到了，那我们就很满意了。
   所以，在机器学习这门课程中，大家一定要放在心里面——我们是以很高的概率得到一个很好的模型，一定是有这两个前提，所以是概率近似正确的。

3. VC维（Vapnik-Chervonenkis Dimension）：
   VC维是衡量假设空间复杂度的一个概念，可以用以下方式定义：对于任意的 $m$个样本，假设空间 $\mathcal{H}$ 能够将这些样本以所有可能的方式进行分类的最大 $m$ 值就是VC维 $d$：
   d = max ⁡ { m : 对于任意的 { ( x 1 , y 1 ) , . . . , ( x m , y m ) } , ∀ y ′ ∈ { 0 , 1 } m , ∃ h ∈ H  s.t.  ∀ i , h ( x i ) = y i ′ } d = \max \{ m : \text{对于任意的} \{(x_1, y_1), ..., (x_m, y_m)\}, \forall y' \in \{0, 1\}^m, \exists h \in \mathcal{H} \text{ s.t. } \forall i, h(x_i) = y'_i \} d=max{m:对于任意的{(x1​,y1​),...,(xm​,ym​)},∀y′∈{0,1}m,∃h∈H s.t. ∀i,h(xi​)=yi′​}

4. PAC学习的样本复杂度：
   根据VC维，可以得出PAC学习所需的最小样本复杂度 $m$的一个上界：
   $m\ge \frac{d\log (1/\delta )+\log (1/ϵ)}{ϵ}$
   这个公式说明了为了达到一定的泛化误差 $ϵ$和失败概率$\delta$，所需的最小样本数量与VC维 $d$成正比。

这些公式和概念是PAC理论的基础，它们帮助我们理解学习算法在不同条件下的性能和所需的样本量。

课后题

1. 计算学习理论中最重要的理论模型是？
   • 计算模型
   • 数据模型
   • 机器学习
   • PAC
2. 以下哪个是对概率近似正确（PAC）的正确解释？
   • 以很低概率得到不好的模型
   • 以很低概率得到很好的模型
   • 以很高概率得到很好的模型
   • 以很高概率得到不好的模型

基本术语

1. 数据集（Dataset）：
   数据集是用于训练和测试机器学习模型的一组数据。它通常由多个示例组成，每个示例都是一个具体的实例，包含多个属性或特征。

2. 训练集（Training Set）：
   训练集是数据集中的一部分，用于训练学习算法。通过在训练集上学习，算法尝试发现数据中的模式和规律。

3. 测试集（Test Set）：
   测试集是数据集中的另一部分，用于评估学习算法的性能。测试集通常在算法训练完成后使用，以检验模型的泛化能力。

4. 示例（Instance）/样例（Example）：
   示例不包括结果，只包含描述。样例包含描述和结果。

5. 样本（Sample）：
   样本通常指的是从总体中抽取的用于分析的个体或子集。在机器学习中，样本可以指单个数据点，也可以指整个训练集或测试集。

6. 属性（Attribute）/特征（Feature）：
   属性是数据集中用于描述示例的变量。在机器学习中，属性通常被视为特征，特征是输入数据的单个测量或属性，用于帮助模型做出预测。

7. 属性值：
   属性值是特定属性的具体值。例如，在客户数据集中，“年龄”是一个属性，而具体的数值（如30岁）则是这个属性的属性值。

8. 属性空间/样本空间/输入空间：
   属性空间、样本空间和输入空间通常可以互换使用，它们指的是所有可能的属性组合的集合。在机器学习中，输入空间是模型接收的输入数据的集合。

9. 特征向量（Feature Vector）：
   特征向量是一个数学表示，它将示例的每个特征值组织成一个向量。例如，如果一个示例有年龄、性别和收入三个特征，其特征向量可能是 [30, 男, 50000]。

10. 标记空间/输出空间：
    标记空间或输出空间指的是模型预测结果的所有可能值的集合。在分类问题中，输出空间可能是一组类别标签；在回归问题中，输出空间可能是一个连续的数值范围。
    当然，让我们继续解释这些机器学习中的术语：

11. 分类（Classification）：
    分类是监督学习中的一种任务，目的是预测给定示例的类别或标签。例如，根据电子邮件的内容判断其是否为垃圾邮件。

12. 回归（Regression）：
    回归同样是监督学习中的一种任务，但它的目标是预测一个连续的数值，如房价预测或股票价格预测。

13. 二分类（Binary Classification）：
    二分类是分类问题的一个特例，其中目标是将示例分为两个类别，通常表示为正类（positive class）和反类（negative class），如垃圾邮件检测。

14. 多分类（Multiclass Classification）：
    多分类是分类问题的一种，其中目标是将示例分为多个类别。例如，根据图片内容识别不同的动物种类。

15. 正类（Positive Class）：
    在二分类问题中，正类通常指的是我们感兴趣的类别，例如在疾病诊断中，正类可能是“患病”。

16. 反类（Negative Class）：
    反类在二分类问题中指的是我们不感兴趣的类别或背景类别，例如在疾病诊断中，反类可能是“健康”。

17. 未见样本（Unseen Instance）：
    未见样本指的是模型在训练阶段没有见过的数据点。模型的泛化能力可以通过其在未见样本上的表现来评估。

18. 未知“分布”：
    这通常指的是数据的真实分布，即数据生成的过程或机制。在机器学习中，我们通常无法完全了解数据的分布。

19. 独立同分布（i.i.d.）：
    独立同分布是假设数据集中的每个样本都是从同一个未知分布中独立抽取的，并且每个样本的抽取都是相同的分布。这是许多机器学习算法的基本假设。

20. 泛化（Generalization）：
    泛化指的是模型对新数据（未见样本）的预测能力。一个好的模型不仅在训练数据上表现良好，而且能够泛化到新数据上。

21. 假设（Hypothesis）：
    在机器学习中，假设是模型对输入数据和输出标签之间关系的猜测或预测。它是从训练数据中学习得到的函数或模型。

22. 真相（Ground-Truth）：
    真相或真实标签是每个示例对应的正确标签或值，它是训练和评估模型时用来比较预测正确性的基准。

23. 学习器（Learner）：
    学习器是执行学习过程的算法或模型。它从训练数据中学习，并尝试构建一个能够预测新数据的假设。

课后题

1. 课程视频中，训练数据中的“色泽”是什么？
   • 属性
   • 属性值
   • 类别标记
   • 样本
2. 以下哪个选项指的是机器学习中的假设（hypothesis）？
   • 属性
   • 标记
   • 数据
   • 学到的模型
3. 多分类问题___可以 _（可以/不可以）分解为若干个二分类问题。

归纳偏好

归纳偏好（Inductive Bias）是指在机器学习算法中所引入的关于目标函数的先验知识或假设，用以帮助算法从有限的训练数据中更好地进行推断和泛化。由于训练数据集总是有限的，算法需要某种形式的归纳偏好来推测未见数据的表现，以避免过拟合和提高泛化能力。归纳偏好可以体现在算法的结构、假设、约束、先验分布等多个方面。

以下是归纳偏好的一些主要方面和实现方式：

1. 假设空间（Hypothesis Space）

归纳偏好可以通过限制算法的假设空间来实现。例如，线性回归假设数据可以用一个线性函数来表示，这种限制使得算法在有限数据下能够更好地泛化。假设空间越小，归纳偏好越强，模型越容易泛化，但也可能限制了模型的表达能力。

2. 先验知识（Prior Knowledge）

在贝叶斯方法中，归纳偏好可以通过先验分布来体现。先验分布代表了对模型参数的初始假设，在没有观察到数据之前，这些先验知识指导了模型的学习过程。例如，拉普拉斯平滑中的先验分布帮助模型避免对罕见事件的过度自信。

3. 正则化（Regularization）

正则化是通过添加惩罚项来约束模型参数的大小，从而引入归纳偏好的一种方法。例如，L2正则化（岭回归）通过惩罚权重的平方和，使模型更倾向于选择较小的权重，从而避免过拟合。L1正则化（Lasso回归）则通过惩罚权重的绝对值，使得一些权重变为零，从而实现特征选择。

4. 模型架构（Model Architecture）

深度学习中的神经网络架构设计也是一种归纳偏好。例如，卷积神经网络（CNN）利用局部连接和权重共享的归纳偏好来捕捉图像的局部特征和空间不变性。循环神经网络（RNN）通过循环结构捕捉序列数据中的时间依赖性。

5. 数据增强（Data Augmentation）

数据增强是通过对训练数据进行变换和扩展来引入归纳偏好的一种方法。例如，在图像分类中，使用旋转、缩放、裁剪等操作来生成更多的训练样本，帮助模型更好地泛化到未见数据。

6. 迁移学习（Transfer Learning）

迁移学习通过利用在相关任务上训练好的模型参数来引入归纳偏好。例如，使用在大规模图像数据集上预训练的卷积神经网络作为特征提取器，可以显著提高在小数据集上的图像分类性能。

7. 随机性（Stochasticity）

某些算法通过引入随机性来实现归纳偏好。例如，随机森林通过构建多个决策树并取其平均结果来减小过拟合的风险。每个决策树的训练数据和特征选择都是随机的，从而引入了多样性和稳健性。

归纳偏好在机器学习中的作用至关重要，它决定了模型在有限数据下的表现和泛化能力。不同的任务和数据集需要不同的归纳偏好，因此选择合适的归纳偏好是构建高性能机器学习模型的关键。

这段文字提供了对归纳偏好（Inductive Bias）的另一种解释，特别强调了奥卡姆剃刀（Occam’s Razor）的原理。下面是对这段文字的详细解读，以及归纳偏好在机器学习中的应用。

归纳偏好和奥卡姆剃刀

奥卡姆剃刀的基本原则是“如无必要，勿增实体”，也就是说，在多个解释中，选择最简单的那个。这个原则在科学研究和机器学习中非常重要，特别是当我们面对很多可能的假设时。

更“平滑”的假设

文中提到，如果我们认为更“平滑”的假设更“简单”，那么在一个图中，两条线的比较，选择较为平滑的曲线。平滑的曲线被认为是更简单的，因此更符合奥卡姆剃刀的原则。

实际应用中的复杂性

然而，奥卡姆剃刀并非总是可行。例如，两个看似简单的假设可能在实际应用中难以区分优劣，这时候我们需要借助其他方法来判断。这段文字还提到，在实际问题中，假设是否成立是需要通过大量数据和模型来验证的。

归纳偏好在机器学习中的重要性

归纳偏好决定了学习算法在训练数据不足时如何进行推断和泛化。它是一种关于模型结构和参数的先验知识，有助于在有限数据上构建有效的模型。以下是归纳偏好的一些具体应用：

1. 模型选择：在模型选择过程中，我们通常会选择复杂度适中的模型，而不是过于复杂的模型。这种选择本身就是一种归纳偏好，基于对泛化能力的假设。

2. 正则化技术：如前所述，正则化通过添加惩罚项限制模型复杂度，从而引入归纳偏好。例如，L2正则化倾向于选择小的权重值，使模型更为平滑和简单。

3. 特征选择：在高维数据中，选择少量重要特征有助于提高模型的泛化能力，这种选择也是基于归纳偏好，认为少量重要特征能够更好地描述数据。

4. 先验分布：在贝叶斯学习中，先验分布反映了归纳偏好，通过在参数估计中引入先验知识，帮助模型更好地适应数据。

归纳偏好的挑战

归纳偏好的引入需要在简单性和复杂性之间找到平衡。一方面，过于简单的模型可能无法捕捉数据的真实结构；另一方面，过于复杂的模型则容易过拟合。因此，选择合适的归纳偏好需要结合具体问题和数据特点进行综合考虑。

总之，归纳偏好是机器学习中的一个核心概念，影响模型选择、训练和泛化性能。理解并合理应用归纳偏好，是构建高效机器学习系统的关键。

课后题

1. 归纳偏好指机器学习算法在学习过程中，对以下哪个选项的偏好？
   • 数据
   • 某种类型假设
   • 标记
   • 运行速度
2. 以下哪个选项是指“奥卡姆剃刀”原则？
   • 若有多个假设与观察一致，则随机选一个
   • 若有多个假设与观察一致，则选既不简单又不复杂的那个
   • 若有多个假设与观察一致，则选最简单的那个
   • 若有多个假设与观察一致，则选最复杂的那个

NFL定理

NFL定理，全称为“无免费午餐定理”（No Free Lunch Theorem），是机器学习和优化领域中的一个重要理论。该定理由David Wolpert和William Macready在1996年提出，揭示了关于算法性能的一个基本限制。NFL定理主要说明，对于所有可能的问题而言，没有任何一个算法能够在所有情况下都表现优于其他算法。

NFL定理的基本内容

NFL定理的主要内容可以概括为以下几点：

1. 算法在所有问题上的平均性能相同：
   如果我们考虑所有可能的目标函数，对于这些函数的均匀分布，没有任何一个算法在所有这些函数上的表现会优于其他算法。换句话说，任何两个优化算法在所有可能的目标函数上的平均表现是相同的。

2. 问题分布决定了算法的优劣：
   NFL定理的一个重要推论是，某些算法在特定类型的问题上可能表现优异，但在其他类型的问题上则可能表现较差。因此，算法的优劣取决于我们所遇到的问题分布。

3. 没有普适最优算法：
   NFL定理表明，不存在一个在所有问题上都最优的算法。这意味着在选择算法时，必须根据具体的问题特性和数据分布进行调整和选择。

NFL定理的数学表述

NFL定理的数学表述可以通过一些简单的符号来表达。设$\mathcal{X}$为搜索空间，$\mathcal{Y}$为目标值空间，$\mathcal{F}$为目标函数集合，其中每个函数$f:\mathcal{X}\to \mathcal{Y}$将搜索空间的元素映射到目标值空间。对于一个优化算法$A$，我们可以定义它在函数$f$上的性能为$\mathcal{P}(A,f)$。

NFL定理指出，对于所有可能的算法集合$\mathcal{A}$和目标函数集合$\mathcal{F}$，有以下关系成立：

${\sum }_{f\in \mathcal{F}}\mathcal{P}(A,f)={\sum }_{f\in \mathcal{F}}\mathcal{P}(B,f)$

对于任意两个算法(A)和(B)，它们在所有可能的目标函数上的平均性能是相同的。

NFL定理的意义和影响

1. 定制算法的重要性：
   由于没有普适最优算法，因此在实际应用中，算法需要根据具体的问题和数据进行定制。理解问题的性质和数据的分布对于选择合适的算法至关重要。

2. 算法组合与集成：
   NFL定理的启示之一是，通过结合多种算法的优点，可以在不同问题上取得更好的效果。例如，集成学习方法（如Bagging和Boosting）通过组合多个基学习器来提高整体性能。

3. 对新算法的评估：
   NFL定理提醒我们，在开发和评估新算法时，需要明确它们的适用范围和局限性。任何新算法都不可能在所有情况下都优于现有算法。

4. 问题特性的研究：
   NFL定理强调了研究问题特性的重要性。通过理解问题的结构和特点，可以设计出更有效的算法。

NFL定理的局限性

虽然NFL定理在理论上具有重要意义，但在实际应用中，存在一些局限性：

1. 假设所有问题均匀分布：
   NFL定理假设所有可能的目标函数是均匀分布的，但在实际中，许多问题具有特定的结构和规律，这使得某些算法在特定领域表现更好。

2. 忽略了实际中的算法性能差异：
   实际中的算法性能不仅取决于问题的分布，还与算法的实现、优化技巧和计算资源等因素有关。

3. 实用性和可解释性：
   在实际应用中，算法的实用性和结果的可解释性也是重要考虑因素，而不仅仅是性能的均值。

总结

无免费午餐定理是机器学习和优化领域中的一个基本理论，揭示了算法性能的本质限制。它提醒我们，在选择和设计算法时，需要充分考虑具体问题的特性和数据的分布。理解和应用NFL定理，可以帮助我们在实际应用中做出更为合理和有效的算法选择。

课后题

1. 以下哪种说法描述了NFL定理？
   • 一个算法a若在某些问题上比另一个算法b好，必存在另一些问题没算法b好
   • 机器学习算法需要数据
   • 所有机器学习问题问题出现的机会相同
   • 一个算法a若在某些问题上比另一个算法b好，a一定比b需要更多数据
2. 以下哪个选项是NFL定理的重要前提？
   • 所有“问题”难度不同
   • 所有“问题”出现的机会服从任意分布
   • 所有“问题”出现的机会不相同
   • 所有“问题”出现的机会相同