写在前面
本系列文章为《机器学习》教材的学习笔记, 在记录教材知识点的同时, 也尝试写下自己的理解与对知识点与公式的扩展与深入. 本系列文章所使用数学符号与教材可能有所不同, 但不影响正确性.
机器学习的概念
“朝霞不出门, 晚霞行千里”, 通过朝霞或晚霞的出现, 我们就能判断当天的天气好坏, 从而决定当天的行程, 这是我们的经验判断. 经验判断更基础却更不易察觉的例子是, 我们生活过的每一天里太阳东升西落, 我们却却从未怀疑过明天太阳是否升起. 默认太阳照常升起也是经验判断.
我们通过已有的经验对未来做出有一定效力的预判, 如果让计算机帮忙, 告诉计算机已有的经验, 让计算机为我们做出更复杂的预判, 这就是机器学习.
机器学习(machine learning)是一门致力于研究如何通过计算的手段, 利用经验来改善系统自身的性能的学科.
“经验”以”数据”的形式存在, 机器学习研究的主要内容, 是关于在计算机上从数据中产生”模型“(model)的算法, 即“学习算法”(learning algorithm).
“学习算法”, 即机器从”经验”, 即”数据”, 中学得”知识”的算法. 把经验数据提供给学习算法, 它就能基于这些数据产生模型.
“模型” 可以类比为一个”学到知识的人”. 若提供给他一定的观察信息, 如今天有朝霞, 他就能做出判断今天天气不好. 若提供给模型一些数据, 模型就能根据这些数据产生相应的判断.
基本术语
假设现在有一批关于西瓜的数据：
- (色泽=青绿；根蒂=蜷缩；敲声=浊响)
- (色泽=乌黑；根蒂=稍蜷；敲声=沉闷)
- (色泽=浅白；根蒂=硬挺；敲声=清脆)
每个括号内是一条记录，”=”意思是”取值为”.
这组记录的集合称为一个“数据集”(data set), 其中每条记录是关于一个事件或对象的描述，称为一个示例”(instance)或”样本“(sample).
“色泽”反映了西瓜在某方面的性质, 这样反应事件或对象在某方面的表现或性质的事项，称为”属性“(attribute)或”特征“(feature), 属性上的取值称为”属性值“(attribute value). 属性张成的空间称为”属性空间“(attribute space)、”样本空间“(sample space)或”输入空间”.
“属性张成的空间”可以理解为, 把样本看作空间中的一个点, 如”(色泽=青绿；根蒂=蜷缩；敲声=浊响)” 作为三维空间中的一个点, “(色泽=乌黑；根蒂=稍蜷；敲声=沉闷)”作为空间中的另一个点, 属性有不同的取值, 所有这些可能的取值对应的样本点构成的空间即是”属性张成的空间”.
由于空间中的每一个点对应一个坐标向量，因此我们也把一个示例称为一个”特征向量“(feature vector).
一般地, 令 $D=\lbrace\boldsymbol{x}_1,\boldsymbol{x}_2,\cdots,\boldsymbol{x}_m\rbrace$ 表示包含了 $m$ 个示例的数据集, 每个示例由 $d$ 个属性描述，则每个示例
\[\boldsymbol{x}_i=\left(x^{(1)}_i,x^{(2)}_i,\cdots,x^{(d)}_i\right)^\text{T}\]是 $d$ 维样本空间的 $\mathcal{X}$ 的一个向量，$\boldsymbol{x}_i\in \mathcal{X}$，其中 $x_i^{(j)}$ 是 $\boldsymbol{x}_i$ 在第 $j$ 个属性上的取值，$d$ 称为样本 $\boldsymbol{x}_i$ 的”维数“(dimensionality).
从数据中学得模型的过程称为”学习“(learning)或”训练“(training), 这个过程通过执行某种学习算法来完成. 训练过程中使用的数据称为”训练数据“(training data). 其中每个样本称为一个”训练样本“(training sample), 训练样本组成的集合称为”训练集“(training set). 学得模型对应了关于数据的某种潜在规律, 因此亦称为”假设“(hypothesis). 这种潜在规律自身, 则称为”真相“或”真实“(ground-truth). 学习过程就是为了找出或逼近真相.
注意, 用学习算法学得的模型仅仅是关于数据的潜在规律的某种假设. 若将数据的某种潜在规律视作一个函数(function), 则学得的模型就是对这个函数的近似, 它也是一个函数. 我们可能永远也无法知道真正的函数是什么样的, 只能得到它的近似.
若要建立关于”预测“(prediction)的模型, 需要获得训练样本的”结果”信息, 例如”((色泽=青绿;根蒂=蜷缩;敲声=浊响), 好瓜)”. 这里关于示例结果的信息, 例如”好瓜”, 称为”标记“(label); 拥有了标记信息的示例, 则称为”样例“(example). 一般地, 用 $(\boldsymbol{x}_i,y_i)$ 表示第 $i$ 个样例, 其中 $y_i\in\mathcal{Y}$ 是示例 $\boldsymbol{x}_i$ 的标记, $\mathcal{Y}$ 是所有标记的集合, 称为”标记空间“(label space)或”输出空间”.
若想要预测的是离散值, 此类学习任务称为”分类“(classification); 若想要预测的是连续值, 此类学习任务称为”回归“(regression).
对只涉及两个类别的”二分类“(binary classification)任务, 通常称一个类为”正类“(positive class), 另一个类为”反类“(negative class, 亦称负类); 涉及多个类别时, 则称为”多分类“(multi-class classification)任务.
一般地, 预测任务是希望通过对训练集 $\lbrace(\boldsymbol{x}_1,y_1),(\boldsymbol{x}_2,y_2),\cdots,(\boldsymbol{x}_m,y_m)\rbrace$ 进行学习, 建立一个从输入空间 $\mathcal{X}$ 到输出空间 $\mathcal{Y}$ 的映射
\[f:\mathcal{X}\mapsto \mathcal{Y}.\]对二分类任务, 通常令 $\mathcal{Y}=\lbrace-1,+1\rbrace$ 或 $\lbrace0.1\rbrace$ ; 对于多分类任务, $\vert\mathcal{Y}\vert>2$ ; 对于回归任务, $\mathcal{Y}=\mathbb{R}$.
学得模型后, 使用其进行预测的过程称为”测试“(testing), 被预测的样本称为”测试样本“(testing sample).
还可以对西瓜做”聚类“(clustering), 即将训练集中的西瓜分成若干组, 每组称为一个”簇“(cluster); 这些自动形成的簇可能对应一些潜在的概念划分. 在聚类学习中, 这些潜在的概念划分事先是不知道的, 而且学习过程中使用的训练样本通常不拥有标记信息.
聚类的一个例子是, 如果有六张图片, 三张为狗, 三张为猫. 让一般人去给这六张图片分类, 人们很自然的会将狗分为一类, 猫分为一类. 如果把这六张图片提供给模型, 模型可能将这六张图片分为两类, 其中一类动物毛色为黄色, 另一类动物毛色为白色. 这个例子是想说明, 模型在划分数据时, 是根据数据的相似程度划分, 并没有潜在的概念划分.
根据训练数据是否拥有标记信息, 学习任务可大致分为:
- 监督学习(supervised learning), 代表是分类和回归
- 无监督学习(unsupervised learning), 代表是聚类
机器学习的目标是使学得的模型能很好地适用于”新样本”, 学得模型适用于新样本的能力, 称为”泛化“(generalization)能力. 通常假设样本空间中全体样本都服从一个未知”分布“(distribution) $\mathcal{D}$ , 我们获得的每个样本都是独立地从这个分布上采样获得的, 即”独立同分布“(independent and identically distributed, 简称 $i.i.d$). 一般而言, 训练样本越多, 得到的关于 $\mathcal{D}$ 的信息越多, 就更有可能通过学习获得具有强泛化能力的模型.
假设空间
归纳(introduction)与演绎(deduction)是科学推理的两大手段.
- 归纳(induction)：特殊到一般的”泛化”(generalization)
- 演绎(deduction)：从一般到特殊的”特化”(specialization)
归纳与演绎同时也可以作为我们获取知识的手段, 即学习的手段. 机器学习也是如此, 学习算法从数据中学习, 从样例中学习, 这是一个归纳的过程, 也就是”归纳学习“(inductive learning).
归纳学习:
- 广义: 从样例中学习
- 狭义: 从训练数据中学得概念(concept)，亦称为”概念学习”或”概念形成”
概念学习中最基本的是布尔概念学习, 即对”是”、”不是”这样的可表示为 0/1 布尔值的目标概念的学习.
可以把学习的过程看作一个在所有假设(hypothesis)组成的空间中进行搜索的过程, 搜索目标是找到与训练集”匹配“(fit)的假设. 回到上文中的类比. 如果训练集中的数据存在一个潜在的规律, 而这个规律可以表示为一个函数, 学习的过程就是在含有许多函数的假设集(通常有无数个函数)中, 找到最匹配潜在规律的那个函数.
由于学习过程是基于有限样本训练集进行的, 训练集中的样本可能不足以体现样本的潜在规律, 而且假设空间往往十分庞大, 因此可能有多个假设与训练集展现出的规律一致, 会存在着一个与训练集一致的”假设集合”, 称之为”版本空间“(version space).
归纳偏好
对于版本空间中多个与训练集一致的假设, 一个具体的学习算法需要产生一个具体的模型, 即在版本空间中选择出一个假设作为模型. 机器学习算法在学习过程中对某种类型的假设的偏好, 称为”归纳偏好“(inductive bias).
任何一个有效的机器学习算法必有其归纳偏好, 否则就无法从版本空间中选择出一个假设, 这将导致产生的模型可能在每次进行预测时, 随机从版本空间中抽选一个假设, 从而使得基于假设预测的结果也是随机的.
归纳偏好可看作学习算法自身在一个可能的假设空间中对假设进行选择的启发式或”价值观”. “奥卡姆剃刀“(Occam’s razor) 是一种常用的、自然科学研究中最基本的原则, 即”若有多个假设与观察一致, 则选最简单的那个”. 但在实际情况中, 我们难以定义不同的假设哪一个更”简单”, 这时便需要借助其他机制来判断.
归纳偏好对应了学习算法本身所做出的关于”什么样的模型更好” 的假设, 在具体的现实问题中, 这个假设是否成立, 即算法的归纳偏好是否与问题本身匹配, 大多数时候直接决定了算法能否取得好的性能.
假设现有一训练集 $T$, 使用学习算法 $\mathcal{L}_a$ 基于某种归纳偏好从训练集 $T$ 中学习得到模型 $A$, 使用学习算法 $\mathcal{L}_b$ 基于另一种归纳偏好学习得到模型 $B$, 模型 $A,B$, 在训练集上的表现一致, 都很好. 但对于训练集以外的数据, 模型 $A, B$ 的表现无法确定. 可能 $A$ 与训练集外的样本更一致, 也可能 $B$ 与训练集外的样本更一致.
对于一个学习算法 $\mathcal{L}_a$ , 若它在某些问题上表现得比学习算法 $\mathcal{L}_b$ 好, 则必然存在另一些问题, 学习算法 $\mathcal{L}_b$ 表现得比 $\mathcal{L}_a$ 好. 既然这样, 该如何比较学习算法 $\mathcal{L}_a$ 和 $\mathcal{L}_b$ 的好坏呢? 我们接下来试着讨论一下它们的期望性能.
简单起见, 假设样本空间 $\mathcal{X}$ 和假设空间 $\mathcal{H}$ 都是离散的. 令 $P(h\vert X,\mathcal{L}_a)$ 代表学习算法 $\mathcal{L}_a$ 基于训练数据 $X$ 产生假设 $h$ 的概率, 再令 $f$ 代表我们希望学习的真实目标函数. $\mathcal{L}_a$ 的”训练集外误差”, 即 $\mathcal{L}_a$ 在训练集之外的所有样本上的误差的期望为
\[E_{ote}(\mathcal{L}_a\vert 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,\mathcal{L}_a)\]这个式子表示了 $\mathcal{L}_a$ 基于训练数据产生的 $h$ 在训练集外的数据产生的误差的期望, 其中 $\mathbb{I}(\cdot)$ 是指示函数, 若 $\cdot$ 为真则取值 1, 否则取值 0.
考虑二分类问题, 且真实目标函数可以是任何函数 $\mathcal{X}\mapsto \lbrace0,1\rbrace$, 函数空间为 $\lbrace0,1\rbrace^{\vert\mathcal{X}\vert}$. 这里假设目标函数是任何能将样本映射到 ${0,1}$ 的函数. 当存在不止一个 $f$ 时, 假设每个 $f$ 出现的概率相等, $f$ 服从均匀分布. 例如当样本空间只有两个样本时, $\mathcal{X}=\lbrace x_1,x_2\rbrace, \vert\mathcal{X}\vert=2$, 则所有可能的真实目标函数 $f$ 如下:
\[f_1:f_1(\boldsymbol{x}_1)=0, f_1(\boldsymbol{x}_2)=0\\ f_2:f_1(\boldsymbol{x}_1)=0, f_1(\boldsymbol{x}_2)=1\\ f_3:f_1(\boldsymbol{x}_1)=1, f_1(\boldsymbol{x}_2)=0\\ f_4:f_1(\boldsymbol{x}_1)=1, f_1(\boldsymbol{x}_2)=1\]一共有 $2^{\vert\mathcal{X}\vert}=4$ 个可能的真实目标函数. 对所有可能的 $f$ 按均匀分布对误差求和, 有
\[\begin{align} \sum_fE_{ote}(\mathcal{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,\mathcal{L}_a)\\ &=\sum_{\boldsymbol{x}\in\mathcal{X}-X}P(\boldsymbol{x})\sum_{h}P(h|X,\mathcal{L}_a)\sum_f\mathbb{I}(h(\boldsymbol{x})\neq f(\boldsymbol{x})) \end{align}\]通过学习算法 $\mathcal{L}_a$ 学习出的模型 $h(\boldsymbol{x})$ 对每个样本 $\boldsymbol{x}$ 无论预测值为 0 还是 1, 都必然有一半的 $f$ 与其一致, 相应的就必然有一半的 $f$ 与其不一致, 即 $h(\boldsymbol{x})\neq f(\boldsymbol{x})$ . 于是
\[\begin{align} \sum_fE_{ote}(\mathcal{L}_a|X,f)&=\frac{1}{2}2^{|\mathcal{X}|}\sum_{\boldsymbol{x}\in\mathcal{X}-X}P(\boldsymbol{x})\sum_{h}P(h|X,\mathcal{L}_a)\\ &=2^{|\mathcal{X}|-1}\sum_{\boldsymbol{x}\in\mathcal{X}-X}P(\boldsymbol{x})\cdot 1 \end{align}\]上式的结果告诉我们, 总的期望误差与学习算法无关. 于是我们知道, 对于任意两个学习算法 $\mathcal{L}_a$ 和 $\mathcal{L}_b$ , 都有
\[\sum_fE_{ote}(\mathcal{L}_a|X,f)=\sum_fE_{ote}(\mathcal{L}_b|X,f)\]也就是说, 任意两个学习算法 $\mathcal{L}_a$ 和 $\mathcal{L}_b$ 的期望性能相同, 这就是”没有免费的午餐“定理(No Free Lunch Theorem, 简称 NFL 定理)[Wolpert, 1996; Wolpert and Macready, 1995].
需要注意的是, NFL 定理的重要前提是: 所有”问题”出现的机会相同、或所有问题同等重要. 但实际情况是, 我们只需要关注某个具体的问题. 而且在实际情况中, 上述 “$f$ 均匀分布”的假设也是不成立的.
NFL 定理的重要性在于告诉我们, 要针对具体问题分析什么是好的学习算法, 不能泛泛而谈.
