西瓜书学习笔记(1)
主要内容：机器学习的定义、基本术语、假设空间、归纳偏好
机器学习的定义
正如我们根据过去的经验来判断明天的天气，人们希望从购买经验中挑选一个好瓜，那能不能让计算机帮助人类来实现这个呢？机器学习正是这样的一门学科，人的”经验”对应计算机中的”数据”， 让计算机来学习这些经验数据，生成一个算法模型，在面对新的情况中，计算机便能作出有效的判断，这便是机器学习 。
另一本经典教材的作者 Mitchell 给出了一个形式化的定义，假设：
- P ：计算机程序在某任务类T上的性能。
- T ：计算机程序希望实现的任务类。
- E ：表示经验，即历史的数据集。
若该计算机程序通过利用经验E在任务T上获得了性能P的改善，则称该程序对E进行了学习。
机器学习的一些基本术语
假设我们收集了一批西瓜的数据，例如：(色泽=青绿;根蒂=蜷缩;敲声=浊响) ， (色泽=乌黑;根蒂=稍蜷;敲声=沉闷)， (色泽=浅自;根蒂=硬挺;敲声=清脆)……每对括号内是一个西瓜的记录。定义：
所有记录的集合为： 数据集 。
每一条记录为：一个 示例（instance）或样本（sample） 。
单个的特点(例如西瓜的色泽或敲声)：为 特征（feature）或属性（attribute） 。
对于一条记录，如果在坐标轴上表示，每个西瓜都可以用坐标轴中的一个点表示，一个点也是一个向量，例如（青绿，蜷缩，浊响），即每个西瓜为：一个 特征向量（feature vector） 。
一个样本的特征数为：维数（dimensionality） ，该西瓜的例子维数为3，当维数非常大时会产生”维数灾难”。
计算机程序学习经验数据生成算法模型的过程中，每一条记录称为一个”训练样本”，同时在训练好模型后，我们希望使用新的样本来测试模型的效果，则每一个新的样本称为一个”测试样本”。定义：
所有 训练样本 的集合为： 训练集（trainning set） ，[特殊] 。
所有 测试样本 的集合为： 测试集（test set） ，[一般] 。
机器学习出来的模型适用于新样本的能力为： 泛化能力（generalization） ，即从特殊到一般。
用一个实际例子来说明一下，就像考试之前我们肯定是要反复做题的，为的就是考试能考个好点的成绩。但是考试大多数都是新题，谁也没做过，考前的刷题是为了掌握试题的规律，能够举一反三、学以致用，这样我们在做新题的时候也能够从容面对。这种规律的掌握便是泛化能力，有的同学就能很好掌握这种规律，考试考个高分，也就是说他的”泛化能力”好。
考试考的不好的同学，无非是这三个原因：
- 泛化能力弱，做了很多题，始终掌握不了规律，不管遇到老题还是新题都不会做；
- 泛化能力弱，做了很多题，只会死记硬背，看到考试的新题就懵了；
- 完全不做题，考试都是靠想象力瞎蒙。
在机器学习中，我们把第一类情况称为欠拟合，第二类情况称为过拟合，第三类情况称作不收敛。
西瓜的例子中，我们是想计算机通过学习西瓜的特征数据，训练出一个决策模型，来判断一个新的西瓜是否是好瓜。可以得知我们预测的是：西瓜是好是坏，即好瓜与差瓜两种，是离散值。同样地，也有通过历年的人口数据，来预测未来的人口数量，人口数量则是连续值。定义：
预测值为 离散 值的问题为： 分类（classification） 。
预测值为 连续 值的问题为： 回归（regression） 。
我们预测西瓜是否是好瓜的过程中，很明显对于训练集中的西瓜，我们事先已经知道了该瓜是否是好瓜，学习器通过学习这些好瓜或差瓜的特征，从而总结出规律，即训练集中的西瓜我们都做了标记，称为标记信息。但也有没有标记信息的情形，例如：我们想将一堆西瓜根据特征分成两个小堆，使得某一堆的西瓜尽可能相似，即都是好瓜或差瓜，对于这种问题，我们事先并不知道西瓜的好坏，样本没有标记信息。定义：
训练数据 有标记信息 的学习任务为： 监督学习（supervised learning） ，容易知道上面所描述的分类和回归都是监督学习的范畴。
训练数据 没有标记信息 的学习任务为： 无监督学习（unsupervised learning） ，常见的有聚类和关联规则。
假设空间
我们可以把学习过程看作一个在所有 假设(hypothesis)组成的空间 中进行搜索的过程，搜索目标是找到与训练集”匹配”(fit)的假设，即能够将训练集中的瓜判断正确的假设。
假设空间既”由输入空间到输出空间的映射的集合”，我们把所有可能的由输入空间 X 到输出空间 Y 的映射 f : X$\rightarrow$Y 构成的集合记为$\boldsymbol{H}$，则假设空间$\boldsymbol{F}$为$\boldsymbol{H}$的一个子集，即$\boldsymbol{F}\subseteq\boldsymbol{H}$。也就是我们可以自行选择所考虑问题的假设空间的大小范围，并不一定非要选择包含所有可能性的映射集$\boldsymbol{H}$作为假设空间。
假设的表示一旦确定，假设空间及其规模大小就确定了。这里我们的假设空间由形如”(色泽=?)$\wedge$(根蒂=?)$\wedge$(敲声=?)”的可能取值所形成的假设组成。
例如色泽有”青绿”、”乌黑”、”浅白”这三种可能取值;还需考虑到，也许”色泽”无论取什么值都合适，我们用通配符来表示，例如”好瓜$\Leftrightarrow$(色泽=*)$\wedge$(根蒂=蜷缩)$\wedge$(敲声=浊响)”，即”好瓜是根蒂蜷缩、敲声浊响的瓜，什么色泽都行”。
此外，还需考虑极端情况:有可能”好瓜”这个概念根本就不成立，世界上没有”好瓜”这种东西;我们用$\emptyset$表示这个假设。
这样，若”色泽””根蒂””敲声”分别有3、2、2种可能取值，则我们面临的假设空间规模大小为4x3x3+1=37。
版本空间
现实问题中我们常面临很大的假设空间，但学习过程是基于 有限样本训练集进行的，因此，可能有多个假设与训练集一致，即存在着一个与训练集一致的”假设集合”，我们称之为 版本空间(version space) 。
归纳偏好
对于一个具体的学习算法而言，它必须要产生一个模型。这时，学习算 法本身的”偏好”就会起到关键的作用。
例如，若我们的算法喜欢”尽可能特殊”的模型,则它会选择”好瓜$\leftrightarrow$(色泽=*)$\wedge$(根蒂=蜷缩)$\wedge$(敲声=浊响)”; 但若我们的算法喜欢”尽可能一般”的模型，并且由于某种原因它更”相信”根蒂,则它会选择”好瓜$\leftrightarrow$(色泽=*)$\wedge$(根蒂=蜷缩)$\wedge$(敲声=*)”。
机器学习算法在学习过程中对某种类型假设的偏好，称为 归纳偏好(inductive bias), 或简称为”偏好”。
归纳偏好可看作学习算法自身在一个可能很庞大的假设空间中对假设进 行选择的启发式或”价值观”。
事实上，归纳偏好对应了学习算法本身所做出的关于”什么样的模型更好”的假设。在具体的现实问题中，这个假设是否成立，即算法的归纳偏好是否与问题本身匹配,大多数时候直接决定了算法能否取得好的性能。
“没有免费午餐”定理
在计算机人工智能（AI）领域，“没有免费午餐”（No Free Lunch，NFL）定理 特别指出，不存在一种算法能够在所有可能的问题上都优于其他算法。这一定理对于理解和选择机器学习和优化算法尤其重要。
在机器学习和人工智能中,我们经常面临模型或算法的选择问题。”没有免费午餐”定理明确告诉我们:
没有单一的机器学习模型能够保证在所有可能的问题上都优于其他模型。每个模型都有其擅长和不擅长的问题。
机器学习算法的性能高度依赖于所处理问题的特点以及数据的统计属性。算法和问题域之间的适配性至关重要。
在比较不同的机器学习算法时,必须基于某特定问题和数据集进行比较。在不同问题下进行的比较并无意义。
这一定理强调了针对具体问题设计和选择算法的重要性。它也解释了为什么在机器学习研究中,几乎所有算法和模型的分析都是基于某特定数据集的。
总之，这个定理是让我们意识到，讨论算法的优劣，泛化能力的强弱，都不能脱离实际的问题，要针对具体的问题具体地分析。