【机器学习基础】第一课:机器学习基本概念

机器学习定义,基本术语,假设空间,归纳偏好

Posted by x-jeff on October 13, 2018

【机器学习基础】系列博客为参考周志华老师的《机器学习》一书,自己所做的读书笔记。
本文为原创文章,未经本人允许,禁止转载。转载请注明出处。

1.机器学习的定义

首先,我们先来看一下机器学习的定义。机器学习的定义有很多,这里列出了比较常见的一个定义。

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

2.机器学习的基本术语

我们结合一个西瓜数据集来帮助理解这些术语:

编号 色泽 根蒂 敲声 好瓜
1 青绿 蜷缩 浊响
2 乌黑 蜷缩 浊响
3 青绿 硬挺 清脆
4 乌黑 稍蜷 沉闷
  • 数据集(data set):记录的集合。例如上表就是一个数据集。
  • 示例(instance)或样本(sample):每条记录(即关于对象的描述)。
  • 属性(attribute)或特征(feature):上表中有三个属性(特征),即色泽、根蒂和敲声。
  • 属性值(attribute value):每个属性的取值即为属性值。诸如青绿、乌黑等等。
  • 属性空间(attribute space)或样本空间(sample space)或输入空间:属性张成的空间。大家可以这样理解:如果每个样本(示例)有3个属性(特征),x轴表示属性1,y轴表示属性2,z轴表示属性3,坐标轴上的值代表属性值,则每个样本(示例)都会对应三维空间的一个点,每个点其实可以理解为一个向量,因此,也把一个样本(示例)称为一个“特征向量”样本空间的计算:例如有20个属性,每个属性有10个可能取值,则样本空间的规模为$10^{20}$。
  • 维数:一般地,令$D=\lbrace x_1,x_2,…,x_m \rbrace$表示包含m个示例的数据集,每个示例有d个属性。则每个示例$x_i=(x_{i1};x_{i2};…;x_{id})$是d维样本空间中的一个向量,d称为样本$x_i$的维数。
  • 样例(example):拥有了标记(label)信息的示例,称为样例。用$(x_i,y_i)$表示第i个样例,其中$y_i\in Y$。Y是所有标记的集合,亦称“标记空间”(label space)或“输出空间”。上表中1-4行,每行都是一个样例。如果没有label,则每一行都是一个样本(示例)。
  • 分类模型:预测值为离散值(如二分类、多分类等)。
  • 回归模型:预测值为连续值。
  • 有监督学习(亦称有导师学习):👉详细介绍
  • 无监督学习(亦称无导师学习):👉详细介绍
  • 泛化能力(generalization):学得模型适用于新样本的能力,称为泛化能力。
  • 独立同分布:假设样本空间中全部样本服从一个未知“分布”D,我们获得的每个样本都是独立地从这个分布上采样获得的,即“独立同分布”。
  • 归纳(induction)与演绎(deduction):是科学推理的两大基本手段。归纳:从特殊到一般的泛化过程。演绎:从一般到特殊的特化过程。

3.假设空间

机器学习中的学习指的就是从样本中学习的过程,可以看作一个在所有假设组成的空间中进行搜索的过程,搜索目标是找到与训练集“匹配”的假设。

例如,我们有一个西瓜数据集,西瓜分为好瓜,坏瓜两种,每个样本有3个属性:色泽、根蒂、敲声。3个属性分别有3,2,2种可能的取值。

我们的目的是根据这些特征,判断一个瓜是否是好瓜(这是一个典型的二分类问题,在这里,我们假设正例=“好瓜”)。
我们先来看一下怎么构建假设空间。以“色泽”属性为例,该属性有3个属性值,简化记为$\lbrace a,b,c \rbrace$,则集合$\lbrace a,b,c \rbrace$的非空子集即为根蒂属性在假设空间的取值情况,为$\lbrace a \rbrace$,$\lbrace b \rbrace$,$\lbrace c \rbrace$,$\lbrace a,b \rbrace$,$\lbrace a,c \rbrace$,$\lbrace b,c \rbrace$,$\lbrace a,b,c \rbrace$,共7种,若不考虑$\lbrace a,b \rbrace$,$\lbrace a,c \rbrace$,$\lbrace b,c \rbrace$的情况,还剩4种取值,即$\lbrace a \rbrace$,$\lbrace b \rbrace$,$\lbrace c \rbrace$,$\lbrace a,b,c \rbrace$。其中,$\lbrace a,b,c \rbrace$指的是无论色泽取哪个值,结局都是好瓜,可以用通配符*表示。此外,还有一种特殊情况,就是“好瓜”这个概念根本就不存在,不管各个属性如何取值,结果一直都不是好瓜。因此,假设空间的规模为:$(3+1)(2+1)(2+1)+1=37$。
然后我们对假设空间进行搜索,搜索过程中不断删除与正例不一致的假设,和(或)与反例一致的假设。最终将会获得与训练集一致(即对所有训练样本能够进行正确判断)的假设。 与训练集一致的“假设集合”,称之为“版本空间”

4.归纳偏好

但是“版本空间”中可能存在等效假设,所以需要归纳偏好来解决这个问题。

针对等效假设举个例子,如果在版本空间中存在这样两个假设:

  • 假设1:若满足色泽=*,根蒂=蜷缩,敲声=*,则判定为好瓜,否则为坏瓜。
  • 假设2:若满足色泽=*,根蒂=蜷缩,敲声=清脆,则判定为好瓜,否则为坏瓜。

若测试集有一条记录为色泽=青绿,根蒂=蜷缩,敲声=沉闷,同时符合假设1和假设2的条件,但是按照假设1,则判定为好瓜,按照假设2,则判定为坏瓜,此时便存在等效假设现象,需要“归纳偏好”来解决这个问题。

任何一个有效的机器学习算法必有其归纳偏好,否则它将被假设空间中看似在训练集上“等效”的假设所迷惑,每次结果可能都不一样。

归纳偏好举例:“奥卡姆剃刀”原则,即“若有多个假设与观察一致,则选最简单的那个”。但是“奥卡姆剃刀”原则的缺点也很明显,有时候无法判断哪个假设更简单。

“没有免费的午餐”定理(No Free Lunch Theorem,NFL):
重要前提:所有“问题”出现的机会相同,或所有问题同等重要。

  • 算法A:聪明的算法
  • 算法B:随机胡猜的笨拙算法

可以得到这样一个结论:算法A和算法B的期望性能一样,产生的总误差与算法无关。所以,算法无优劣之分(包括随机胡猜),但是针对特定的某一具体问题,才会有优劣之分。同一算法在不同问题中表现也不尽相同。