机器学习-1 绪论

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 个样例。其中 yiY 是示例 \(\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 为均匀分布。但实际情况中我们只关注自己正在解决的问题,只要一个解决方案在该问题上表现良好,至于该解决方案在其它问题、或其他类似问题上表现是否良好我们并不关心。所以,脱离实际问题,空泛地讨论“什么学习算法更好”毫无意义,学习算法自身的归纳偏好与问题是否匹配,往往起到决定性的作用。

上一篇:标准模板库巧解算法题 前缀和


下一篇:PHP用户连续签到赠送额外积分