基本概念

机器学习(Machine Learning)

机器学习研究的内容是关于在计算机上从数据/经验(data/experience)中产生模型(model)的算法,即学习算法(learning algorithm)。

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

基本术语

  • 数据集(data set):数据的集合,数据是若干条属性与其取值,记录关于对一个事件或对象的描述
  • 示例(instance)/样本(sample):数据集中的每一条数据
  • 属性(attribute)/特征(feature):反映事件或对象在某方面的表现或性质的事项
  • 属性值(attribute value):属性上的取值
  • 属性空间(attribute space)/样本空间(sample space)/输入空间(input space)
  • 特征向量(feature vector):属性空间中任何一点所对应的向量
  • 标记(lable):表示示例结果的信息
  • 样例(example):带有标记的信息示例
  • 标记空间(lable space)/输出空间(output space):所有的标签的集合
  • 测试样本(testing sample):用于对学习模型进行测试的样本数据

一般地,令 D={x1, x2, …, xm} 表示包含 m 个示例的数据集,每个示例由 d 个属性描述,则每个示例 xi=(xi1, xi2, …, xid) 是 d 维样本空间 X 中的一个向量,xi∈X,其中 xij 是 xi 在第 j 个属性上的取值,d 称为样本 xi 的维数(dimensionality)。用(xi,yi)表示第i个样例及其标签yi,yi∈Y。

  • 泛化(generalization):将学习得到的模型应用于新的数据集(测试集)的能力成为泛化能力

通常假设样本空间中全体样本服从一个未知分布(distribution)D,我们获得的每个样本都是独立地从这个分布上采样获得的,即独立同分布(independent and identically distributed,简称iid)。一般而言,训练样本越多,我们得到的关于D的信息越多,这样就越有可能通过学习获得具有强泛化能力的模型。

机器学习的分类

基于学习任务

  • 分类(classification):预测值是离散的
    • 二分类(binary classification):预测值只有两个类别,通常将其中一个成为正类(positive class),另一个成为反类/负类(negative class)
    • 多分类(mutil-class classification):预测值是多个离散的类别
  • 回归(regression):预测值是连续值,其标记空间为实数集
  • 聚类(clustering):将训练集中的数据分成若干个簇,通常情况下这种学习的数据集是无标签的

基于训练数据是否拥有标签

  • 监督学习(supervised learning):训练数据有标签,比如分类和回归
  • 无监督学习(unsupervised learning):训练数据无标签,比如聚类

假设空间

我们把学习过程看作一个在所有假设(hypothesis)组成的空间(假设空间(hypothesis space))中进行搜索的过程,搜索目标是找到与训练集匹配(fit)的假设。假设的表示一旦确定,假设空间及其规模大小就确定了。

现实问题中我们常面临很大的假设空间,但学习过程是基于有限样本训练集进行的,因此,可能有多个假设与训练集一致,即存在着一个与训练集一致的假设集合,称之为版本空间(version space)

归纳偏好

机器学习算法在学习过程中对某种类型假设的偏好,称为归纳偏好(inductive bias),简称为偏好。

任何一个有效的机器学习算法必有其归纳偏好。归纳偏好可看作学习算法自身在一个可能很庞大的假设空间中对假设进行选择的启发式或价值观。

奥卡姆剃刀原则(Occam’s razor)

奥卡姆剃刀原则称“若有多个假设与观察一致,则选最简单的那个”。比如我们通过训练得到有两条可以描述训练样本的曲线,平滑的A曲线可能意味着更加简单。

没有免费的午餐定理(No Free Lunch Theorem,NFL)

没有免费的午餐定理指机器学习的模型总误差与学习算法无关,即学习算法的期望性能相同

但是显然NFL定理是基于一个前提的:所有问题出现的机会相同、或所有问题同等重要。但实际情形并不是这样。

NFL的意义在于让我们更加清楚的认识到,脱离具体问题空泛地比较学习算法的好坏毫无意义

学习算法自身的归纳偏好与问题是否相配,往往会起到决定性的作用

NFL 定理的简单证明过程

全文参考:周志华 著 《机器学习》