《机器学习》笔记一

一、绪论

1.1、什么是机器学习？

机器学习是人工智能（AI）的一个分支，其核心目标是让计算机能够从数据中自动“学习”——也就是说，不需要人为编写每一个规则，而是通过算法和统计模型提取数据中的规律，从而对未知数据进行预测或做出决策。

深度学习：神经网络类的机器学习算法。

人工智能 > 机器学习 > 深度学习

1.2、机器学习中的一些基本概念

算法

算法是指从数据中学得模型的具体方法，例如线性回归、对数几率回归、决策树等。算法的输出称为模型，通常可以看作具体的函数或抽象函数。例如一元线性回归算法产出的模型可表示为

f(x) = wx + b

样本

样本（Sample）指数据集中单个、具体的实例或观测值。每个样本代表一个独立个体（如图片、文本、交易记录、传感器读数等），通常由多个特征（属性）构成，并用向量表示。

为什么使用向量表示样本数据？

抽象化：为了让计算机理解现实事物，必须将其抽象为数学形式，而计算机擅长数学运算。
线性代数的优势：向量能用各个维度描述事物的特征。
例如，用色泽、根蒂和敲声这 3 个特征描述西瓜，可表示为 $\boldsymbol{x}=(\text{青绿};\text{蜷缩};\text{清脆})$

样本空间

样本空间（Sample Space）也称为输入空间（Input Space）或属性空间（Attribute Space）。
由于样本以特征向量表示，自然对应一个向量空间，通常用花式大写字母 $\mathcal{X}$ 表示。

数据集

数据集（Data Set）一般用集合表示，如

D = \{\boldsymbol{x}_1, \boldsymbol{x}_2, \dots, \boldsymbol{x}_m\}

假设每个样本含有 $d$ 个特征，则第 $i$ 个样本可写为

\boldsymbol{x}_i = (x_{i1}; x_{i2}; \dots; x_{id})

其中 $x_{ij}$ 表示样本 $\boldsymbol{x}_i$ 在第 $j$ 个属性上的取值。

模型

从数据中学习得到模型的过程称为学习（Learning）或训练（Training），训练过程中使用的数据称为训练数据，每个数据点为训练样本，而这些训练样本构成的集合称为训练集。
学得的模型对应了数据的某种潜在规律，也称为假设（Hypothesis）；而真实的潜在规律则称为真相（Ground-truth）。
在某些文献中，模型也被称为学习器（Learner），即在给定数据和参数空间下学习算法的实例化结果。

一般流程：

收集样本：例如收集 100 个样本。
划分数据：将样本分为 80 个训练样本（训练集）和 20 个测试样本（测试集）。
训练模型：选择某个机器学习算法，在训练集上进行学习，得到模型。
测试评估：使用测试集检验模型的泛化效果。

例如，在判断西瓜好坏时，我们默认好瓜与坏瓜背后有某种规律存在，算法学得的模型便是这种规律的近似（即假设），而不同的算法和参数配置可能学到不同的规律。

标记

在机器学习中，标记指样本中需要学习的目标信息。例如，在判断西瓜好坏时，“好瓜”和“坏瓜”就是样本的标记。

数学表示：第 $i$ 个样本的标记为 $y_i$ ，标记空间记为 $\mathcal{Y}$ 。
完整的样本表示通常为 $(\boldsymbol{x}, y)$ 。

根据标记的取值类型不同（离散型和连续性），可将机器学习任务分为以下两类：

分类任务：标记取值为离散型
- 二分类：如 $\mathcal{Y} = \{0, 1\}$ 或 $\{-1, +1\}$
- 多分类：类别超过两个
回归任务：标记取值为连续型，通常 $\mathcal{Y} = \mathbb{R}$

无论分类或回归，学习到的模型都可以看作从输入空间 $\mathcal{X}$ 到输出空间 $\mathcal{Y}$ 的映射函数

y = f(\boldsymbol{x})

另外，根据是否使用标记信息，可分为：

监督学习（Supervised Learning）：训练过程中利用标记信息（例如线性模型）。
无监督学习（Unsupervised Learning）：训练时不利用标记信息（例如聚类）。

泛化

泛化能力是衡量模型对未知数据预测准确性的关键指标。

例如，假设训练集中有 3 个样本：

$\boldsymbol{x}_1 = (\text{青绿};\text{蜷缩})$ , 标记为“好瓜”
$\boldsymbol{x}_2 = (\text{乌黑};\text{蜷缩})$ , 标记为“好瓜”
$\boldsymbol{x}_3 = (\text{浅白};\text{蜷缩})$ , 标记为“好瓜”

若真相为“只要根蒂蜷缩就是好瓜”，则：

算法 A 可能学到“色泽为青绿、乌黑或浅白且根蒂蜷缩时为好瓜”
算法 B 则学到“只要根蒂蜷缩就是好瓜”

对于新样本 $\boldsymbol{x} = (\text{金黄};\text{蜷缩})$ ，模型 B 的预测更符合真相，说明其泛化能力更优。

总结：

数据：决定模型效果的上限（数据量、特征工程等）。因为数据量大即表示累计的经验多，因此模型学习到的经验也多，自然表现效果越好。

算法：帮助模型不断逼近这个上限。不同的算法学习得到的模型效果自然有高低之分，效果越好则越逼近上限，即逼近真相。

分布

这里的分布指概率论中的概率分布。通常假设样本来自一个未知的分布 $\mathcal{D}$ ，并且样本是独立同分布的。收集的样本越多，反映的 $\mathcal{D}$ 信息越全面，模型预测也越接近真相。

假设空间

假设空间（hypothesis space） 是所有候选模型（即所有可能的输入到输出映射函数）的集合（比如上面“算法 A” 和“算法 B”）。

选择合适的假设空间至关重要：

过大的假设空间可能导致模型过于复杂，出现过拟合问题。
过小的假设空间可能无法捕捉数据中的复杂模式，导致欠拟合。

归纳偏好

归纳偏好（Inductive Bias） 指的是学习算法在从有限的训练数据中归纳出一般规律时所依赖的一系列先验假设或倾向。由于现实中我们只能获得有限的数据，而数据本身无法完整描述所有可能的情况，因此在面对新数据进行预测时，算法必须依靠某种“偏好”来在所有可能的假设中做出选择。如果没有归纳偏好，算法就会在训练数据上“等效”的多个假设之间徘徊，无法确定性地推广到未见过的数据上。

作用

帮助模型选择：在训练模型时，可能会有多个模型都能很好地拟合训练数据，但在对未知数据进行预测时，不同模型的表现可能会有很大差异。归纳偏好可以帮助算法从这些候选模型中选择一个最符合其偏好的模型，以便更好地进行泛化。
提高泛化能力：通过引入归纳偏好，算法可以在一定程度上避免过拟合，使得学习到的模型能够更好地适应未知的测试数据，从而提高模型的泛化能力。

常见类型：

奥卡姆剃刀原则：这是一种很常见的归纳偏好。它主张“如无必要，勿增实体”，即在所有能够解释训练数据的假设中，选择最简单的那个假设。例如在决策树学习中，优先选择复杂度较低、节点较少的决策树，认为简单的模型更不容易过拟合，更可能具有良好的泛化能力。
平滑性假设：假设数据在空间中是平滑分布的，即距离相近的数据点具有相似的输出值。比如在基于实例的学习算法（如K近邻算法）中，就隐含了这种归纳偏好，它认为一个未知样本的类别应该与它周围的已知样本类别相似。
一致性偏好：算法倾向于选择与训练数据一致程度最高的假设。例如在分类问题中，一个分类器如果能够对训练数据中的所有样本都进行正确分类，那么在其他条件相同的情况下，它会被认为是一个更好的模型。

无免费午餐定理

假设样本空间 $\mathcal{X}$ 和假设空间 $\mathcal{H}$ 都是离散的（离散意味着它们包含的元素是可以逐个列举的，而非连续的取值）。令 $P(h|X, \mathfrak{L}_a)$ 代表算法 $\mathfrak{L}_a$ 基于训练数据 $X$ 产生假设 $h$ 的概率，再令 $f$ 代表我们希望学习的真实目标函数。 $\mathfrak{L}_a$ 的 “训练集外误差”，即 $\mathfrak{L}_a$ 在训练集之外的所有样本上的误差为

E_{ote}(\mathfrak{L}_a|X, f) = \sum_{h} \sum_{x \in \mathcal{X}-X} P(x) \mathbb{I}(h(x) \neq f(x)) P(h|X, \mathfrak{L}_a)

这个公式描述的是 在给定训练集 $X$ 和目标函数 $f$ 的情况下，某种学习算法 $\mathfrak{L}_a$ 产生的假设 $h$ 的期望泛化误差。它衡量了在训练集之外（即 $\mathcal{X} - X$ 包含“测试集数据”、“未来可能遇到的真实世界数据”、“验证集数据”）的样本点上的错误率:

左侧部分： $E_{ote}$ 代表的是 泛化误差的期望值（“out-of-training error”，即训练外误差）。它表示在训练集 $X$ 和目标函数 $f$ 已知的情况下，由学习算法 $\mathfrak{L}_a$ 产生的假设 $h$ 的期望误差。
求和符号：
- 外层求和 ：表示对所有可能的假设 $h$ 进行求和。
- 内层求和 ：表示对所有 未在训练集中出现的数据点 $x$ 进行求和。
概率密度 $P(x)$ ：
- 这个项表示未见样本点 $x$ 出现的概率分布。它用于衡量样本空间 $\mathcal{X} - X$ 内不同样本的出现概率。
- 不同的重要性不同：某些在真实数据分布中很常见，而另一些几乎不会出现。如果一个非常少见，即，即使在这个点上预测错误，它对整体误差的贡献也很小。
- 作用是加权不同的输入点对泛化误差的贡献：
  - 若某个的很大（例如高频输入），它的误差会对总误差影响更大。
  - 若某个的很小，它的误差几乎不会影响整体结果。
指示函数：
- 是真实的目标函数（真实的标记）。
- 是学习到的假设函数（模型的预测）。
- 这是一个 指示函数（Indicator Function），当学习算法产生的假设 $h(x)$ 与真实函数 $f(x)$ 不一致时，它的值为 $1$ ；否则为 $0$ 。
- 误差衡量方式为 0-1 损失，即：表示如果预测错误，损失是 1，否则是 0。
  - 如果，那么。
  - 如果，那么。
- 这部分衡量了假设 $h$ 在点 $x$ 上的错误情况。
后验概率：
- 通过训练数据和学习算法，我们得到一个假设（可能是某个机器学习模型）。
- 是 假设在已知训练数据和学习算法下的后验概率，即 在当前学习条件下，模型选择某个假设的概率。
- 同样的训练数据 ，可能会产生不同的假设，尤其是当训练过程中存在随机性（如随机初始化、随机采样等）。
- 这些假设并不是等可能的，而是具有一定的后验概率。
- 由于泛化误差取决于 具体选择的假设 ，我们需要对所有可能的假设进行加权平均，权重就是 后验概率 。

该公式的核心思想是：考虑所有可能的假设 $h$ 和所有训练集中未见的点 $x$ ，计算学习算法在这些点上的错误率的加权平均。

假设：若均匀分布，则有一半的对的预测与不一致。基于公式

E_{ote}(\mathfrak{L}_a|X, f) = \sum_{h} \sum_{x \in \mathfrak{X}-X} P(x) \mathbb{I}(h(x) \neq f(x)) P(h|X, \mathfrak{L}_a)

则对所有可能的按均匀分布对误差求和则有(两边同时乘上 )：

\begin{aligned} \sum_{f} E_{ote}(\mathfrak{L}_a| X,f) &= \sum_f \sum_h \sum_{\boldsymbol{x}\in\mathcal{X}-X}P(\boldsymbol{x})\mathbb{I}(h(\boldsymbol{x})\neq f(\boldsymbol{x}))P(h| X,\mathfrak{L}_a)&1\\ &=\sum_{\boldsymbol{x}\in\mathcal{X}-X}P(\boldsymbol{x}) \sum_hP(h| X,\mathfrak{L}_a)\sum_f\mathbb{I}(h(\boldsymbol{x})\neq f(\boldsymbol{x}))&2 \\ &=\sum_{\boldsymbol{x}\in\mathcal{X}-X}P(\boldsymbol{x}) \sum_hP(h| X,\mathfrak{L}_a)\cfrac{1}{2}2^{| \mathcal{X} |}&3 \\ &=\cfrac{1}{2}2^{| \mathcal{X} |}\sum_{\boldsymbol{x}\in\mathcal{X}-X}P(\boldsymbol{x}) \sum_hP(h| X,\mathfrak{L}_a)&4 \\ &=2^{| \mathcal{X} |-1}\sum_{\boldsymbol{x}\in\mathcal{X}-X}P(\boldsymbol{x}) \cdot 1 &5 \\ \end{aligned}

最后得到

\sum_{f} E_{ote}(\mathfrak{L}_a| X,f) = 2^{|\mathcal{X}|-1} \sum_{x \in \mathcal{X}-X} P(x) \cdot 1

总误差竟然与学习算法无关！对于任意两个学习算法和，我们都有

\sum_{f} E_{ote}(\mathfrak{L}_a| X,f) = \sum_{f} E_{ote}(\mathfrak{L}_b| X,f)

也就是说，无论学习算法多聪明、学习算法多笨拙，它们的期望性能竟然相同！这就是 “没有免费的午餐”定理（No Free Lunch Theorem，简称 NFL 定理）

无免费午餐定理（No Free Lunch Theorem） 是机器学习和优化领域中的一个基本理论，它表明：如果将所有可能的问题（或目标函数、数据生成分布）平均起来看，没有哪种算法能够在所有问题上都优于其他算法。换句话说，对于所有可能的问题而言，每种算法的平均表现都是相同的。这意味着：

如果一个算法在某些特定任务上表现很好，那么在其他任务上它的表现可能会较差；
要想在某个具体任务上获得优秀的表现，必须在算法中引入与该任务相关的先验假设（即归纳偏好或归纳偏置）。

因此，无免费午餐定理提醒我们，任何一个泛化能力良好的学习算法，都必须依赖于某种形式的领域知识或先验假设；否则，如果算法对所有问题都一视同仁，它就无法针对特定问题做出有效的优化

公式解释：

$1 \to 2$ ：只是把求和符号换了个位置。

$2 \to 3$ ：

这个结论来自于目标函数的 均匀性假设，即所有可能的目标函数具有相同的概率分布，并且每个点处的取值是独立的。

1. 目标函数的数量

设输入空间共有个可能的值。
是一个二元函数，即。
因此，所有可能的目标函数的总数是：。
因为对于每个 $x$ ，可以取 0 或 1，两种情况是独立的。

2. 计算某个固定的处的情况

现在，我们关注一个特定的输入点，并固定一个假设函数。
在所有可能的目标函数中，每个 独立地可以取 0 或 1。
由于所有的分布是均匀的，对于某个固定的：
- 有一半的取 0，
- 另一半的取 1。
这意味着：
- 当时，在一半情况下成立，而在另一半情况下成立。
- 当时，在一半情况下成立，而在另一半情况下成立。
因此，和 匹配的概率是 ，而 不匹配的概率也是 。

3. 计算错误的情况

由于只是一个指示函数：

如果，那么。
如果，那么。

在所有个目标函数中，有一半使得预测正确，另一半使得预测错误。因此：

$3 \to 4$ ：只是移动了下位置

$4 \to 5$ ：所有的 $h$ 发生的概率加起来就是 1 不过多解释。

归纳偏好与无免费午餐定理的关系：

无免费午餐定理指出，对于所有可能的数据分布，没有一种机器学习算法可以在所有情况下都优于其他算法。归纳偏好与无免费午餐定理密切相关，正是因为存在归纳偏好，不同的机器学习算法才会在不同的问题和数据分布上表现出优劣差异。如果没有归纳偏好，所有算法在平均意义下的性能都是相同的。归纳偏好使得算法能够针对特定类型的数据和问题进行优化，从而在某些情况下取得更好的效果，但同时也意味着它在其他一些情况下可能表现不佳。

Ryo's blog