【周志华机器学习】学习笔记一：绪论

1. 机器学习基本术语

机器学习machine learning：致力于研究如何通过计算的手段，利用经验来改善系统自身的性能。
学习算法learning algorithm：关于在计算机上从数据中产生的模型model的算法。

数据集dataset：记录的集合；
示例instance / 样本sample：每条记录是关于一个事件或对象的描述；
属性attribute / 特征feature：反映事件或对象在某方面的表现或性质的事项；
属性值 attribute value：属性上的取值；
属性空间attribute space / 样本空间 sample space / 输入空间：属性组成的空间；
特征向量feature vector：由于空间中的每一个点对应的一个坐标向量。

一般地，令$D=x_1,x_2,\dots \dots ,x_m$表示包含m个示例的数据集，每个示例由d个属性描述，则每个示例$x_i=(x_{i}1,x_{i}2\dots \dots ,x_{i}d)$是d维样本空间中的一个向量，$x_{i}j$是$x_i$在第j个属性上的取值，d称为样本xi的维数。

从数据中学得模型的过程称为学习或训练，这个过程通过执行某个学习算法来完成。训练过程中使用的数据称为训练数据training data，训练样本、训练集。学得模型对应了关于数据的某种潜在的规律为假设hypothesis；这种潜在规律自身，则称为真相或真实ground-truth；模型也叫学习器learner。预测prediction需要训练样本的结果信息，为标签label。$(x_i,y_i)$为第i个示例与标记，Y是所有标记的集合，亦称为标记空间，或输出空间。

预测的离散值是分类classification；预测的连续值为回归regression。只设计两个类别为二分类binary classification，一个类为正类positive class，另一个为反类negative class；涉及多个类别为多分类multi-class classification 任务。预测任务是希望通过对训练集进行学习，建立一个从输入空间到输出空间的映射f: X-> Y。

学得模型后，使用其进行预测的过程称为测试testing，被预测的样本为测试样本testing sample。学得f后，对测试样例x，得预测标记 y=f(x)。
还可以对训练集中的数据分成若干组，每组称为一个簇cluster。

通过训练数据是否拥有标记信息，学习任务可大致划分为两大类：监督学习surprised learning和无监督学习unsurprised learning。

学得模型适用于新样本的能力，称为泛化能力。

通常假设样本空间中全体样本服从一个未知分布distribution D，我们获得的每个样本都是独立地从这个分布上采样获得的，即独立同分布independent and indentically distributed i.i.d. 。

2. 假设空间

归纳induction与演绎deduction是科学推理的两大基本手段。
归纳是从特殊到一般的泛化过程，即从具体的事实归结出一般性规律；
演绎是从一般到特殊的特化过程，即从基础原理推演出具体状况。

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

3. 归纳偏好

问题：不同模型的训练集假设一致，但是对应的模型在面临新的样本的时候却产生不同的输出，哪个是正确的？

机器学习算法在学习过程中对某种类型假设的偏好，称为归纳偏好inductive bias。归纳偏好可以看作学习算法自身在一个可能庞大的假设空间中对假设进行选择的启发式或价值观。比如以下的一个一般性原则来引导算法确立正确的偏好：奥卡姆剃刀：若有多个假设与观察一致，则选择最简单的那个。

归纳偏好对应了学习算法本身所做出的关于什么样的模型更好的假设。

没有免费午餐定理No Free Lunch Theorem，简称NFL定理：在所有问题出现的机会相同，或所有问题同样重要时，无论学习算法A多么聪明，B多么笨拙，它们的期望值都相同，即误差与学习算法无关。

它为了让我们认识到，脱离具体问题，空乏地谈论“什么学习算法更好”无意义，因为若考虑所有潜在的问题，所有学习算法都一样好。要谈论算法的相对优劣，必须要针对具体的学习问题，在某些问题上表现好的学习算法，在另一些问题上可能不尽如人意。