1. 机器学习的定义

A computer program is said to learn from experience E with respect to some task T and some performance measure P, if its performance on T, as measured by P, improves with experience E.

---- Tom Mitchell(1998)

假设用P来评估计算机程序在某任务类T上的性能，若一个程序通过利用经验E在T上获得了性能的改善，则我们说关于T和P，该程序对E进行了学习。

2. 基本术语

在计算机系统中，“经验”通常以“数据”的形式存在，如关于西瓜的一批数据：

(色泽 = 青绿；根蒂 = 蜷缩；敲声 = 浊响；)
(色泽 = 乌黑；根蒂 = 稍蜷；敲声 = 沉闷；)
(色泽 = 浅白；根蒂 = 硬挺；敲声 = 清脆；)
... ...

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

令 \(\mathbf{D} = \{\vec{x_1}, \vec{x_2}, ..., \vec{x_m}\}\) 表示包含 m 个示例的数据集，每个示例 \(\vec{x_i}\) 由 d 个属性描述（上面西瓜的例子使用了 3 个属性），则每个示例 \(\mathbf{\vec{\boldsymbol{x}_i}} = (x_{i1}; x_{i2}; ...;x_{id})\) 是 d 维样本空间 \(\mathcal{X}\) 中的一个向量，\(\mathbf{\vec{\boldsymbol{x}_i}}\) ∈ \(\mathcal{X}\)。其中，\(\boldsymbol{x}_{ij}\) 是 \(\vec{x_i}\) 在第 j 个属性上的取值（例如，上述第 3 个西瓜在第 2 个属性上的取值是“硬挺”）。d 称为样本 \(\vec{x_i}\) 的维数（dimensionality）。

从数据中学得的结果，我们称之为模型或学习器（learner），从数据中学得模型的过程称为学习（learning）或训练（training），这个过程通过执行某个学习算法来完成。
训练中使用的数据称为训练数据（training data），其中的每一个样本称为训练样本（training sample），训练样本组成的集合称为训练集（training set）。
学习模型对应了关于数据的某种潜在规律，称为假设（hypothesis）。而潜在规律自身称为真相/真实（ground-truth）。

要学得一个能判断是不是好瓜的预测（prediction）模型，光有示例数据是不够的，还需要训练样本的结果信息，例如：

((色泽 = 青绿；根蒂 = 蜷缩；敲声 = 浊响；)，好瓜)

这里关于示例结果的信息，如“好瓜”，称为标记（label）。拥有标记的示例，称为样例（example）。一般使用 \(\mathbf{(\vec{\boldsymbol{x}_i}, y_i)}\) 表示第 i 个样例。其中 y_i ∈ Y 是示例 \(\vec{x_i}\) 的标记，Y 是所有标记的集合，亦称为标记空间（label space）或输出空间。

一般的，预测任务是通过训练集 \(\mathbf{\{(\vec{\boldsymbol{x}_1}, y_1), (\vec{\boldsymbol{x}_2}, y_2), ..., (\vec{\boldsymbol{x}_m}, y_m)}\}\) 进行学习， 建立一个从输入空间 \(\mathcal{X}\) 到输出空间 Y 的映射 f : \(\mathcal{X}\) \(\longrightarrow\) Y 。
学得模型后，使用该模型进行预测的过程称为测试（testing）。被预测的样本称为测试样本（testing sample）。例如在学得 \(f\) 后，对测试样本 \(\vec{x_i}\) 可以得到其预测标记记为 y = \(f\)(\(\boldsymbol{x}\))。

根据训练数据是否有标记信息，学习任务可大致分为两大类：

• 监督学习（supervised learning）
  • 分类（classification）：预测结果是离散值的学习任务，如“好瓜”、“坏瓜”。
    • 二分类（binary classification）：只涉及两个类别的学习任务，通常称其中一个类为正类（positive class），另一个类称为反类（negative class）。通常令 Y = {-1, +1} ，或 Y = {0, 1}。
    • 多分类（multi-class classification）：涉及多个类别的学习任务。|Y| > 2。
  • 回归（regression）：预测结果是连续值的学习任务，如西瓜成熟度 0.95、0.37。Y = \(\mathbb{R}\)，\(\mathbb{R}\)为实数集。
• 无监督学习（unsupervised learning）
  • 聚类（clustering）：将训练集分为若干个组，每组称为一个簇（cluster）。

学得的模型适用于新样本的能力称为泛化（generalization）能力。通常假设，样本空间中全体样本服从一个未知的分布（distribution），记做 D。我们获得的样本都是独立地从这个分布上采样获得的，即独立同分布（independent and identically distributed，简称 i.i.d）。一般训练样本越多，则得到的关于 D 的信息越多，就越可能获得强泛化能力的模型。

3. 假设空间

归纳和演绎是科学推理的两大基本手段：

• 归纳（induction）：从特殊到一般的泛化过程，即从具体事实归纳出一般性规律。
• 演绎（deduction）：从一般到特殊的特化（specialization）过程，即从基本原理推演出具体状况。

而“样本中学习”显然是一个归纳过程，因此称为归纳学习（inductive learning）。广义的归纳学习大体相当于从样例中学习；狭义的归纳学习要求从训练数据中学得概念（concept），因此也称为概念学习或概念形成。

概念学习中最基本的是布尔概念学习，即对可表示为0/1布尔值的目标概念的学习，如是、不是。

我们把学习过程看做一个在所有假设组成的空间中进行搜索的过程，搜索目标是找到与训练集匹配（fit）的假设。
在学习过程中可能有多个假设与训练集一致，即存在一个与训练集一致的假设集合，我们称之为版本空间（version space）。

4. 归纳偏好

通过学习得到的模型对应了假设空间中的一个假设。对于一个具体的学习算法，必须要产生一个模型，就需要从版本空间中挑选一个假设对应的模型。这时学习算法本身的偏好就会起到关键作用。
机器学习算法在学习过程中对某种类型假设的偏好，称为归纳偏好（inductive bias），简称为偏好。
奥卡姆剃刀（Occam's razor）是一种常用的、自然科学研究中最基本的原则，即：若多个假设与观察一致，则选择最简单的那个（When you have two competing theories that make exactly the same predictions, the simpler one is better.）。

对于一个学习算法 \(\mathfrak{L_a}\)，若它在某些问题上比学习算法 \(\mathfrak{L_b}\) 好，则必然存在另一些问题，\(\mathfrak{L_b}\) 比 \(\mathfrak{L_a}\) 好。
没有免费的午餐定理（No Free Lunch Theorem，简称 NFL）：无论学习算法 \(\mathfrak{L_a}\) 多聪明，学习算法 \(\mathfrak{L_b}\) 多笨拙，它们的期望性能相同。

证明如下：
考虑二分问题，且真实目标函数可以是任何函数 \(\mathcal{X}\) \(\longrightarrow\) {0, 1}，函数空间为 \(\{0,1\}^{\vert \mathcal{X} \vert}\)。\(f\) 为任何能将样本映射到 {0, 1} 的函数且均匀分布，即不止一个 \(f\) 且每个 \(f\) 出现的概率相等。
例如，样本空间只有两个样本时：\(\mathcal{X} = \{\boldsymbol{x_1}, \boldsymbol{x_2}\}\)，\(\vert \mathcal{X} \vert = 2\)，那么所有的真实目标函数 \(f\) 为：

\[f_1:f_1(\boldsymbol{x}_1)=0,f_1(\boldsymbol{x}_2)=0;\\ f_2:f_2(\boldsymbol{x}_1)=0,f_2(\boldsymbol{x}_2)=1;\\ f_3:f_3(\boldsymbol{x}_1)=1,f_3(\boldsymbol{x}_2)=0;\\ f_4:f_4(\boldsymbol{x}_1)=1,f_4(\boldsymbol{x}_2)=1; \]

一共 \(2^{\vert \mathcal{X}\vert} = 2^2 = 4\) 个真实目标函数。所以通过算法 \(\mathfrak{L}_a\) 学得的模型 \(h(\boldsymbol{x})\) 对每个样本无论预测值是 0 还是 1，都有一半的 \(f\) 与之预测值相等，一半的 \(f\) 与之预测值不同。例如模型 \(h(\boldsymbol{x})\) 对 \(\boldsymbol{x}_1\) 的预测值为1，也即 \(h(\boldsymbol{x}_1)=1\)，那么有且只有 \(f_3\) 和 \(f_4\) 与 \(h(\boldsymbol{x})\) 的预测值相等， \(f_1\) 和 \(f_2\) 与 \(h(\boldsymbol{x})\) 的预测值不等。

​ 假设样本空间 \(\mathcal{X}\) 和 假设空间 \(\mathcal{H}\) 都是离散的。令 \(P(h\vert X, \mathfrak{L_a}\)) 代表算法 \(\mathfrak{L_a}\) 基于训练数据 \(\mathcal{X}\) 产生假设 h 的概率， 再将 \(f\) 代表我们希望学习的真实目标函数。\(\mathfrak{L_a}\) 的训练集外误差，即 \(\mathfrak{L_a}\) 在训练集之外的所有样本上的误差为：

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

其中 \(\mathbb{I}(\cdot)\) 是指示函数，若 \(\cdot\) 为真则取1， 否则取0。

​ 对所有可能的 \(f\) 对 \(\mathfrak{L_a}\) 的误差求和：

\[\begin{aligned} \sum_{f}E_{ote}(\mathfrak{L}_a\vert 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\vert X,\mathfrak{L}_a)\\ &=\sum_{\boldsymbol{x}\in\mathcal{X}-X}P(\boldsymbol{x}) \sum_hP(h\vert X,\mathfrak{L}_a)\sum_f\mathbb{I}(h(\boldsymbol{x})\neq f(\boldsymbol{x}))\\ &=\sum_{\boldsymbol{x}\in\mathcal{X}-X}P(\boldsymbol{x}) \sum_hP(h\vert X,\mathfrak{L}_a)\cfrac{1}{2}2^{\vert \mathcal{X} \vert}\\ &=\cfrac{1}{2}2^{\vert \mathcal{X} \vert}\sum_{\boldsymbol{x}\in\mathcal{X}-X}P(\boldsymbol{x}) \sum_hP(h\vert X,\mathfrak{L}_a)\\ &=2^{\vert \mathcal{X} \vert-1}\sum_{\boldsymbol{x}\in\mathcal{X}-X}P(\boldsymbol{x}) \cdot 1 & {\text{(4.1)}} \end{aligned} \]

从式子 (4.1) 可以看出，总误差与学习算法 \(\mathfrak{L}\) 无关，对于任意两个学习算法，\(\mathfrak{L_a}\) 和 \(\mathfrak{L_b}\) ，可以得到：

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

然而，NFL定理的前提是：所有问题出现的机会相同，或所有问题同等重要，即假设了 f 为均匀分布。但实际情况中我们只关注自己正在解决的问题，只要一个解决方案在该问题上表现良好，至于该解决方案在其它问题、或其他类似问题上表现是否良好我们并不关心。所以，脱离实际问题，空泛地讨论“什么学习算法更好”毫无意义，学习算法自身的归纳偏好与问题是否匹配，往往起到决定性的作用。